| // Copyright 2023 The Wuffs Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your |
| // option. This file may not be copied, modified, or distributed |
| // except according to those terms. |
| // |
| // SPDX-License-Identifier: Apache-2.0 OR MIT |
| |
| pub status "#bad LZMA2 header" |
| pub status "#bad bitstream trailer" |
| pub status "#bad code" |
| pub status "#bad decoded length" |
| pub status "#bad distance" |
| pub status "#bad header" |
| pub status "#truncated input" |
| pub status "#unsupported decoded length" |
| pub status "#unsupported properties" |
| |
| pri status "#internal error: inconsistent I/O" |
| pri status "#internal error: inconsistent dictionary state" |
| |
| pub const DECODER_DST_HISTORY_RETAIN_LENGTH_MAX_INCL_WORST_CASE : base.u64 = 0 |
| pub const DECODER_WORKBUF_LEN_MAX_INCL_WORST_CASE : base.u64 = 0xFFFF_FFFF + 273 |
| |
| pub struct decoder? implements base.io_transformer( |
| // In theory, lc ranges in [0 ..= 8]. In practice, to keep the |
| // worst-case size of the statically allocated probs_lit array |
| // managable, we only support configurations where ((lc + lp) <= 4) and |
| // otherwise return "#unsupported properties". |
| // |
| // This matches "LZMA2's limited property condition" described at: |
| // https://github.com/jljusten/LZMA-SDK/blob/781863cdf592da3e97420f50de5dac056ad352a5/DOC/lzma-specification.txt#L192 |
| lc : base.u32[..= 4], // The number of Literal Context bits. Default: 3. |
| lp : base.u32[..= 4], // The number of Literal Position bits. Default: 0. |
| pb : base.u32[..= 4], // The number of Position Bits. Default: 2. |
| |
| format_extension : base.u32, |
| |
| // dict_size is the nominal size of the args.workbuf ringbuffer that |
| // holds historical decoded bytes. The workbuf_len is a little larger: |
| // see "ML" below. |
| dict_size : base.u32, |
| |
| // dict_workbuf_index indexes the args.workbuf ringbuffer, pointing to |
| // where add_history will next write to. |
| dict_workbuf_index : base.u32, |
| |
| // dict_seen is the cumulative sum (saturating at 0xFFFF_FFFF) of the |
| // number of bytes passed to add_history. |
| dict_seen : base.u32, |
| |
| decoded_length : base.u64, |
| |
| lzma2_encoded_length_have : base.u64, |
| lzma2_encoded_length_want : base.u64, |
| lzma2_need_prob_reset : base.bool, |
| lzma2_need_properties : base.bool, |
| lzma2_need_dict_reset : base.bool, |
| |
| prev_lzma2_chunk_was_uncompressed : base.bool, |
| |
| allow_non_zero_initial_byte : base.bool, |
| |
| end_of_chunk : base.bool, |
| |
| stashed_bytes : array[2] base.u8, // 0 is prev_byte, 1 is match_byte. |
| stashed_bits : base.u32, |
| stashed_range : base.u32, |
| stashed_state : base.u32[..= 11], |
| stashed_rep0 : base.u32[..= 0xFFFF_FFFE], |
| stashed_rep1 : base.u32[..= 0xFFFF_FFFE], |
| stashed_rep2 : base.u32[..= 0xFFFF_FFFE], |
| stashed_rep3 : base.u32[..= 0xFFFF_FFFE], |
| stashed_pos : base.u64, |
| stashed_pos_end : base.u64, |
| |
| util : base.utility, |
| ) + ( |
| // 12 is the number of states. 4 is the pb inclusive maximum. |
| // |
| // The AlgOveNN line numbers refer to the ./README.md file. |
| probs_ao00 : array[12 << 4] base.u16, // AlgOve00. |
| probs_ao20 : array[12] base.u16, // AlgOve20. |
| probs_ao40 : array[12] base.u16, // AlgOve40. |
| probs_ao41 : array[12 << 4] base.u16, // AlgOve41. |
| probs_ao60 : array[12] base.u16, // AlgOve60. |
| probs_ao63 : array[12] base.u16, // AlgOve63. |
| |
| // AlgOve22 and what "decodeLen expands to". |
| probs_match_len_low : array[1 << 4] array[1 << 3] base.u16, |
| probs_match_len_mid : array[1 << 4] array[1 << 3] base.u16, |
| probs_match_len_high : array[1 << 0] array[1 << 8] base.u16, |
| |
| // AlgOve80 and what "decodeLen expands to". |
| probs_longrep_len_low : array[1 << 4] array[1 << 3] base.u16, |
| probs_longrep_len_mid : array[1 << 4] array[1 << 3] base.u16, |
| probs_longrep_len_high : array[1 << 0] array[1 << 8] base.u16, |
| |
| // AlgOve23. The first index is min(len-2, 3). There are then 64 |
| // possible slots, so a 6-bit binary tree. |
| probs_slot : array[4] array[1 << 6] base.u16, |
| |
| // This holds the "xxxx" binary trees, packed per below. The first |
| // element and last 13 elements are unused. The index_small_dist_base |
| // constant is set to (Low - 1) and index_small_dist_extra variable |
| // starts at 1. (index_small_dist_base + index_small_dist_extra) ranges |
| // in Low .. High during the "decode a binary tree" loop. |
| // |
| // Slot Low .. High H-L NumberOfXByms |
| // 4 1 .. 2 1 1 |
| // 5 2 .. 3 1 1 |
| // 6 3 .. 6 3 2 |
| // 7 6 .. 9 3 2 |
| // 8 9 .. 16 7 3 |
| // 9 16 .. 23 7 3 |
| // 10 23 .. 38 15 4 |
| // 11 38 .. 53 15 4 |
| // 12 53 .. 84 31 5 |
| // 13 84 .. 115 31 5 |
| probs_small_dist : array[128] base.u16, |
| |
| // This holds the "zzzz" binary tree. |
| probs_large_dist : array[1 << 4] base.u16, |
| |
| // 4 is the (lc + lp) inclusive maximum. The 0x300 holds three 8-bit |
| // binary trees. The first is for (state < 7), when the previous packet |
| // was a LITERAL. The other two trees are for (state >= 7), when it was |
| // an LZ-copy. Which tree gets used depends on the bits in the next |
| // historical byte after the LZ-copy-source, up until the point where |
| // those bits don't match the currently decoded literal byte, when it |
| // drops back to the first tree. |
| probs_lit : array[1 << 4] array[0x300] base.u16, |
| |
| // Here's the size (and cumulative size) of each probs_etc array. This |
| // is in number of u16 elements, so multiply by 2 for byte size: |
| // |
| // probs_ao00 192 192 |
| // probs_ao20 12 204 |
| // probs_ao40 12 216 |
| // probs_ao41 192 408 |
| // probs_ao60 12 420 |
| // probs_ao63 12 432 |
| // probs_match_len_low 128 560 |
| // probs_match_len_mid 128 688 |
| // probs_match_len_high 256 944 |
| // probs_longrep_len_low 128 1072 |
| // probs_longrep_len_mid 128 1200 |
| // probs_longrep_len_high 256 1456 |
| // probs_slot 256 1712 |
| // probs_small_dist 128 1840 |
| // probs_large_dist 16 1856 |
| // probs_lit 12288 14144 |
| // |
| // 1856 is the properties-independent portion of "the number of |
| // probabilities we need to track". The properties-dependent |
| // proportion, the probs_lit array, could in theory be dynamically |
| // sized, depending on (lc + lp). For simplicity, it's statically sized |
| // here, large enough for the worst case, subject to ((lc + lp) <= 4) |
| // per the "LZMA2's limited property condition" comment above. Static |
| // (worst case) allocation is also what XZ-embedded does [Ref0]. |
| // |
| // 1856 is slightly smaller than the 1984 (also called NUM_BASE_PROBS) |
| // used in the current (as of 2024; version 18.05) version of the LZMA |
| // SDK [Ref1]. The difference of (2 * ((16 - 12) << 4)) is because the |
| // LZMA SDK uses what it calls (kNumStates2 << kNumPosBitsMax) instead |
| // of (kNumStates << kNumPosBitsMax) for its IsMatch and IsRep0Long |
| // portions (what Wuffs calls probs_ao00 and probs_ao41), and |
| // (kNumStates2 - kNumStates) = (16 - 12). LZMA (the file format) only |
| // has 12 states, so enlarging to 16 is redundant (and consumes more |
| // memory). It's not immediately obvious why the memory layout was |
| // re-arranged, but the layout is shared with LZMA SDK asm code. |
| // |
| // 1856 is slightly larger than the 1846 mentioned in both the current |
| // (2024) version of the LZMA SDK spec [Ref2] and as what an old (2004) |
| // version of the LZMA SDK code calls LZMA_BASE_SIZE [Ref3]. The |
| // difference of (14 - (2 * 2)) has two parts. 14 comes from the "first |
| // element and last 13 elements are unused" probs_small_dist comment |
| // above, so that the LZMA SDK code can pack their probs array tighter. |
| // 2 (twice, for AlgOve22 'match' and AlgOve80 'longrep') comes from |
| // moving what the LZMA SDK calls "Choice" and "Choice2" probabilties, |
| // repurposing what this decoder calls the otherwise-unused |
| // probs_etc_len_low[0][0] and probs_etc_len_mid[0][0] elements. |
| // |
| // [Ref0] |
| // https://github.com/torvalds/linux/blob/052d534373b7ed33712a63d5e17b2b6cdbce84fd/lib/xz/xz_dec_lzma2.c#L211 |
| // |
| // [Ref1] |
| // https://github.com/jljusten/LZMA-SDK/blob/781863cdf592da3e97420f50de5dac056ad352a5/C/LzmaDec.c#L151 |
| // |
| // [Ref2] |
| // https://raw.githubusercontent.com/jljusten/LZMA-SDK/781863cdf592da3e97420f50de5dac056ad352a5/DOC/lzma-specification.txt |
| // |
| // [Ref3] |
| // https://github.com/jljusten/LZMA-SDK/blob/f287b63f6bb8b88e281f18a9295340c732245167/Source/LzmaDecode.h#L48 |
| ) |
| |
| pri func decoder.add_history!(hist: slice base.u8, workbuf: slice base.u8) base.status { |
| var dict_workbuf_index : base.u64[..= 0xFFFF_FFFF] |
| var dict_size : base.u64[..= 0xFFFF_FFFF] |
| var hist_length : base.u64 |
| var s : slice base.u8 |
| var n_copied : base.u64 |
| var n : base.u64 |
| |
| dict_workbuf_index = this.dict_workbuf_index as base.u64 |
| dict_size = this.dict_size as base.u64 |
| if args.hist.length() == 0 { |
| return ok |
| } |
| |
| // 273 is ML, where ML is the Maximum Length of an LZMA Lempel-Ziv (length, |
| // distance) pair. After an add_history call, args.workbuf[dict_size .. |
| // (dict_size + ML)] duplicates args.workbuf[.. ML]. This simplifies |
| // copying up to (ML + 1) bytes from the ringbuffer, as there is no need to |
| // split the copy around the dict_size boundary. |
| // |
| // This technique is similar to the one used in the std/deflate package |
| // (although that package uses a different value of ML, 258). That package |
| // also extends the nominal dict_size by (ML - 1), not ML as is done here, |
| // because std/deflate copies up to ML bytes, but std/lzma copies up to (ML |
| // + 1) bytes. std/lzma also needs to know the later half of the two-byte |
| // cusp: the first byte after the copied history. |
| if args.workbuf.length() < (dict_size + 273) { |
| return base."#bad workbuf length" |
| } |
| assert args.workbuf.length() >= dict_size via "a >= b: a >= (b + c); 0 <= c"(c: 273) |
| assert dict_size <= args.workbuf.length() via "a <= b: b >= a"() |
| |
| hist_length = args.hist.length() |
| if hist_length > 0xFFFF_FFFF { |
| this.dict_seen = 0xFFFF_FFFF |
| } else { |
| this.dict_seen ~sat+= hist_length as base.u32 |
| } |
| |
| s = args.hist |
| if s.length() >= dict_size { |
| s = s.suffix(up_to: dict_size) |
| args.workbuf.copy_from_slice!(s: s) |
| this.dict_workbuf_index = 0 |
| |
| } else if dict_workbuf_index > dict_size { |
| return "#internal error: inconsistent dictionary state" |
| |
| } else { |
| n_copied = args.workbuf[dict_workbuf_index .. dict_size].copy_from_slice!(s: s) |
| if n_copied < s.length() { |
| n = args.workbuf.copy_from_slice!(s: s[n_copied ..]) |
| this.dict_workbuf_index = (n & 0xFFFF_FFFF) as base.u32 |
| } else { |
| n = dict_workbuf_index ~mod+ n_copied |
| if n < dict_size { |
| assert n < 0xFFFF_FFFF via "a < b: a < c; c <= b"(c: dict_size) |
| this.dict_workbuf_index = n as base.u32 |
| } else { |
| this.dict_workbuf_index = 0 |
| } |
| } |
| } |
| |
| // Have the tail duplicate the head. |
| if (273 > dict_size) or (dict_size > args.workbuf.length()) { |
| return "#internal error: inconsistent dictionary state" |
| } |
| assert 273 <= args.workbuf.length() via "a <= b: a <= c; c <= b"(c: dict_size) |
| args.workbuf[dict_size ..].copy_from_slice!(s: args.workbuf[.. 273]) |
| return ok |
| } |
| |
| pub func decoder.get_quirk(key: base.u32) base.u64 { |
| if args.key == QUIRK_ALLOW_NON_ZERO_INITIAL_BYTE { |
| if this.allow_non_zero_initial_byte { |
| return 1 |
| } |
| |
| } else if args.key == QUIRK_FORMAT_EXTENSION { |
| return this.format_extension as base.u64 |
| } |
| return 0 |
| } |
| |
| pub func decoder.set_quirk!(key: base.u32, value: base.u64) base.status { |
| var v : base.u32 |
| var n : base.u32 |
| |
| if args.key == QUIRK_ALLOW_NON_ZERO_INITIAL_BYTE { |
| this.allow_non_zero_initial_byte = args.value > 0 |
| |
| } else if args.key == QUIRK_FORMAT_EXTENSION { |
| if args.value == 0 { |
| this.format_extension = 0 |
| return ok |
| |
| } else if (args.value & 0xFF) == 1 { |
| if (args.value >> 8) <= 0xFF { |
| this.format_extension = (args.value & 0xFFFF_FFFF) as base.u32 |
| v = this.format_extension >> 8 |
| n = (1 as base.u32) << (v & 0x1F) |
| n ~sat-= (n >> 4) * ((v >> 5) & 7) |
| if (n < (1 << 12)) or ((1 << 29) < n) { |
| return base."#bad argument" |
| } |
| this.dict_size = n |
| return ok |
| } |
| |
| } else if (args.value & 0xFF) == 2 { |
| if (args.value >> 8) <= 40 { |
| this.format_extension = (args.value & 0xFFFF_FFFF) as base.u32 |
| v = this.format_extension >> 8 |
| if v < 40 { |
| this.dict_size = (2 | (v & 1)) << ((v >> 1) + 11) |
| } else { |
| this.dict_size = 0xFFFF_FFFF |
| } |
| return ok |
| } |
| } |
| |
| return base."#bad argument" |
| } |
| return base."#unsupported option" |
| } |
| |
| pub func decoder.dst_history_retain_length() base.optional_u63 { |
| return this.util.make_optional_u63(has_value: true, value: 0) |
| } |
| |
| pub func decoder.workbuf_len() base.range_ii_u64 { |
| var m : base.u64 |
| |
| if this.dict_size == 0 { |
| return this.util.make_range_ii_u64(min_incl: 0, max_incl: 0) |
| } |
| m = (this.dict_size as base.u64) + 273 |
| return this.util.make_range_ii_u64(min_incl: m, max_incl: m) |
| } |
| |
| pub func decoder.transform_io?(dst: base.io_writer, src: base.io_reader, workbuf: slice base.u8) { |
| var mark : base.u64 |
| var dti_status : base.status |
| var ah_status : base.status |
| |
| while true { |
| mark = args.dst.mark() |
| dti_status =? this.do_transform_io?(dst: args.dst, src: args.src, workbuf: args.workbuf) |
| if not dti_status.is_suspension() { |
| return dti_status |
| } else if (dti_status == base."$short read") and args.src.is_closed() { |
| return "#truncated input" |
| } |
| ah_status = this.add_history!(hist: args.dst.since(mark: mark), workbuf: args.workbuf) |
| if ah_status.is_error() { |
| return ah_status |
| } |
| yield? dti_status |
| } |
| } |
| |
| pri func decoder.do_transform_io?(dst: base.io_writer, src: base.io_reader, workbuf: roslice base.u8) { |
| var header_byte : base.u8 |
| var c8 : base.u8 |
| var c32 : base.u32 |
| var prop_byte : base.u8 |
| |
| var lc : base.u32[..= 8] |
| var lp : base.u32[..= 4] |
| var pb : base.u32[..= 4] |
| |
| var length : base.u32 |
| var n_copied : base.u32 |
| |
| var smark : base.u64 |
| var status : base.status |
| |
| this.lzma2_need_prob_reset = true |
| this.lzma2_need_properties = true |
| this.lzma2_need_dict_reset = true |
| |
| // Loop over chunks. LZMA1 has only one (implicit) chunk. For LZMA2's chunk |
| // header, see |
| // https://github.com/jljusten/LZMA-SDK/blob/781863cdf592da3e97420f50de5dac056ad352a5/C/Lzma2Dec.c#L17-L23 |
| while true { |
| if (this.format_extension & 0xFF) == 0 { // LZMA1. |
| prop_byte = args.src.read_u8?() |
| if prop_byte >= 225 { |
| return "#bad header" |
| } |
| lc = (prop_byte % 9) as base.u32 |
| prop_byte /= 9 |
| lp = (prop_byte % 5) as base.u32 |
| pb = (prop_byte / 5) as base.u32 |
| if (lc + lp) > 4 { |
| return "#unsupported properties" |
| } |
| this.lc = lc.min(no_more_than: 4) |
| this.lp = lp |
| this.pb = pb |
| |
| c32 = args.src.read_u32le?() |
| this.dict_size = c32.max(no_less_than: 4096) |
| |
| this.decoded_length = args.src.read_u64le?() |
| if (this.decoded_length >= 0x8000_0000_0000_0000) and |
| (this.decoded_length <> 0xFFFF_FFFF_FFFF_FFFF) { |
| return "#unsupported decoded length" |
| } |
| |
| this.initialize_probs!() |
| |
| } else if (this.format_extension & 0xFF) == 1 { // Lzip. |
| this.lc = 3 |
| this.lp = 0 |
| this.pb = 2 |
| this.decoded_length = 0xFFFF_FFFF_FFFF_FFFF |
| this.initialize_probs!() |
| |
| } else { // LZMA2. |
| while args.src.length() <= 0, |
| post args.src.length() > 0, |
| { |
| yield? base."$short read" |
| } |
| |
| if args.src.peek_u8() == 0x00 { |
| args.src.skip_u32_fast!(actual: 1, worst_case: 1) |
| break |
| } |
| |
| header_byte = args.src.read_u8?() |
| if header_byte < 0x80 { |
| if header_byte < 0x02 { |
| this.lzma2_need_prob_reset = true |
| this.lzma2_need_properties = true |
| this.lzma2_need_dict_reset = false |
| this.initialize_dict!() |
| } else if (header_byte > 0x02) or this.lzma2_need_dict_reset { |
| return "#bad LZMA2 header" |
| } |
| this.prev_lzma2_chunk_was_uncompressed = true |
| |
| c32 = args.src.read_u16be_as_u32?() |
| length = 1 + c32 |
| |
| while true { |
| n_copied = args.dst.limited_copy_u32_from_reader!(up_to: length, r: args.src) |
| this.stashed_pos ~sat+= n_copied as base.u64 |
| if length <= n_copied { |
| break |
| } |
| length -= n_copied |
| if args.dst.length() == 0 { |
| yield? base."$short write" |
| } else { |
| yield? base."$short read" |
| } |
| } |
| continue |
| } |
| this.decoded_length = header_byte as base.u64 |
| |
| c32 = args.src.read_u16be_as_u32?() |
| this.decoded_length = ((this.decoded_length & 0x1F) << 16) + ((1 + c32) as base.u64) |
| |
| c32 = args.src.read_u16be_as_u32?() |
| this.lzma2_encoded_length_want = (1 + c32) as base.u64 |
| |
| if header_byte >= 0xA0 { |
| this.initialize_probs!() |
| this.lzma2_need_prob_reset = false |
| } |
| |
| if header_byte >= 0xC0 { |
| prop_byte = args.src.read_u8?() |
| if prop_byte >= 225 { |
| return "#bad LZMA2 header" |
| } |
| lc = (prop_byte % 9) as base.u32 |
| prop_byte /= 9 |
| lp = (prop_byte % 5) as base.u32 |
| pb = (prop_byte / 5) as base.u32 |
| if (lc + lp) > 4 { |
| return "#bad LZMA2 header" |
| } |
| this.lc = lc.min(no_more_than: 4) |
| this.lp = lp |
| this.pb = pb |
| this.lzma2_need_properties = false |
| } |
| |
| if header_byte >= 0xE0 { |
| this.lzma2_need_dict_reset = false |
| this.initialize_dict!() |
| } else if this.prev_lzma2_chunk_was_uncompressed { |
| // Update the stashed prev_byte and matched_byte. We've copied |
| // an uncompressed chunk since the last compressed chunk. |
| this.update_stashed_bytes?(dst: args.dst, workbuf: args.workbuf) |
| } |
| this.prev_lzma2_chunk_was_uncompressed = false |
| |
| if this.lzma2_need_prob_reset or this.lzma2_need_properties or this.lzma2_need_dict_reset { |
| return "#bad LZMA2 header" |
| } |
| } |
| |
| c8 = args.src.read_u8?() |
| if (c8 <> 0x00) and not this.allow_non_zero_initial_byte { |
| return "#bad code" |
| } |
| this.stashed_bits = args.src.read_u32be?() |
| if this.stashed_bits == 0xFFFF_FFFF { |
| return "#bad code" |
| } |
| this.stashed_range = 0xFFFF_FFFF |
| this.stashed_pos_end = this.stashed_pos ~sat+ this.decoded_length |
| if (this.stashed_pos_end == 0xFFFF_FFFF_FFFF_FFFF) and |
| (this.decoded_length <> 0xFFFF_FFFF_FFFF_FFFF) { |
| return "#unsupported decoded length" |
| } |
| this.lzma2_encoded_length_have = 5 |
| |
| while args.workbuf.length() < ((this.dict_size as base.u64) + 273) { |
| yield? base."$short workbuf" |
| } |
| |
| while true { |
| smark = args.src.mark() |
| status =? this.decode_bitstream?(dst: args.dst, src: args.src, workbuf: args.workbuf) |
| this.lzma2_encoded_length_have ~sat+= args.src.count_since(mark: smark) |
| if status.is_ok() { |
| break |
| } |
| yield? status |
| } |
| |
| if this.decoded_length == 0xFFFF_FFFF_FFFF_FFFF { |
| if this.stashed_bits <> 0 { |
| return "#bad bitstream trailer" |
| } |
| } else if this.stashed_pos <> this.stashed_pos_end { |
| return "#bad decoded length" |
| } else if this.stashed_bits <> 0 { |
| // Almost all LZMA chunks have either an explicit decoded_length or |
| // an End of Stream marker. It is legitimate, though, for a chunk |
| // to have both. We cater for that here. |
| this.decode_optional_end_of_stream?(src: args.src, workbuf: args.workbuf) |
| |
| if this.stashed_bits <> 0 { |
| return "#bad bitstream trailer" |
| } |
| } |
| |
| if (this.format_extension & 0xFF) < 2 { |
| break |
| } else if this.lzma2_encoded_length_have <> this.lzma2_encoded_length_want { |
| return "#bad LZMA2 header" |
| } |
| } |
| } |
| |
| pri func decoder.decode_bitstream?(dst: base.io_writer, src: base.io_reader, workbuf: roslice base.u8) { |
| var status : base.status |
| |
| this.end_of_chunk = false |
| while true { |
| status = this.decode_bitstream_fast!(dst: args.dst, src: args.src, workbuf: args.workbuf) |
| if status.is_error() { |
| return status |
| } |
| if this.end_of_chunk { |
| break |
| } |
| this.decode_bitstream_slow?(dst: args.dst, src: args.src, workbuf: args.workbuf) |
| if this.end_of_chunk { |
| break |
| } |
| } |
| } |
| |
| pri func decoder.update_stashed_bytes?(dst: base.io_writer, workbuf: roslice base.u8) { |
| var dist : base.u32 |
| var which : base.u32 |
| var adj_dist : base.u32 |
| var wb_index : base.u64 |
| |
| while args.dst.length() <= 0 { |
| yield? base."$short write" |
| } |
| |
| dist = 1 |
| which = 0 |
| while which < 2 { |
| if (dist as base.u64) <= args.dst.history_length() { |
| args.dst.limited_copy_u32_from_history!(up_to: 1, distance: dist) |
| if not args.dst.can_undo_byte() { |
| return "#internal error: inconsistent dictionary state" |
| } |
| this.stashed_bytes[which] = args.dst.peek_undo_byte() |
| args.dst.undo_byte!() |
| |
| } else { |
| adj_dist = (((dist as base.u64) - args.dst.history_length()) & 0xFFFF_FFFF) as base.u32 |
| wb_index = (this.dict_workbuf_index as base.u64) ~mod- (adj_dist as base.u64) |
| while wb_index >= 0x8000_0000_0000_0000, |
| inv which < 2, |
| { |
| wb_index ~mod+= this.dict_size as base.u64 |
| } |
| if wb_index >= args.workbuf.length() { |
| return "#internal error: inconsistent dictionary state" |
| } |
| this.stashed_bytes[which] = args.workbuf[wb_index] |
| } |
| |
| dist = 1 + this.stashed_rep0 |
| which += 1 |
| } |
| } |
| |
| // Preconditions: |
| // - this.stashed_pos == this.stashed_pos_end |
| // - this.stashed_pos_end < 0xFFFF_FFFF_FFFF_FFFF |
| pri func decoder.decode_optional_end_of_stream?(src: base.io_reader, workbuf: roslice base.u8) { |
| var w : base.io_writer |
| var status : base.status |
| |
| this.stashed_pos_end = 0xFFFF_FFFF_FFFF_FFFF |
| while true { |
| io_bind (io: w, data: this.util.empty_slice_u8(), history_position: 0) { |
| status =? this.decode_bitstream_slow?(dst: w, src: args.src, workbuf: args.workbuf) |
| } |
| if status.is_ok() { |
| break |
| } else if status == base."$short write" { |
| return "#bad bitstream trailer" |
| } |
| yield? status |
| } |
| this.stashed_pos_end = this.stashed_pos |
| } |
| |
| pri func decoder.initialize_dict!() { |
| this.dict_workbuf_index = 0 |
| this.dict_seen = 0 |
| this.stashed_bytes[0] = 0 |
| this.stashed_bytes[1] = 0 |
| this.stashed_pos = 0 |
| } |
| |
| // initialize_probs sets all of the probs_foo[i][j] values to 1024. |
| pri func decoder.initialize_probs!() { |
| var i : base.u32 |
| var j : base.u32 |
| |
| i = 0 |
| while i < (12 << 4) { |
| this.probs_ao00[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 12 { |
| this.probs_ao20[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 12 { |
| this.probs_ao40[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < (12 << 4) { |
| this.probs_ao41[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 12 { |
| this.probs_ao60[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 12 { |
| this.probs_ao63[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 16 { |
| j = 0 |
| while j < 8, |
| inv i < 16, |
| { |
| this.probs_match_len_low[i][j] = 1024 |
| j += 1 |
| } |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 16 { |
| j = 0 |
| while j < 8, |
| inv i < 16, |
| { |
| this.probs_match_len_mid[i][j] = 1024 |
| j += 1 |
| } |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 256 { |
| this.probs_match_len_high[0][i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 16 { |
| j = 0 |
| while j < 8, |
| inv i < 16, |
| { |
| this.probs_longrep_len_low[i][j] = 1024 |
| j += 1 |
| } |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 16 { |
| j = 0 |
| while j < 8, |
| inv i < 16, |
| { |
| this.probs_longrep_len_mid[i][j] = 1024 |
| j += 1 |
| } |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 256 { |
| this.probs_longrep_len_high[0][i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 4 { |
| j = 0 |
| while j < 64, |
| inv i < 4, |
| { |
| this.probs_slot[i][j] = 1024 |
| j += 1 |
| } |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 128 { |
| this.probs_small_dist[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 16 { |
| this.probs_large_dist[i] = 1024 |
| i += 1 |
| } |
| |
| i = 0 |
| while i < 16 { |
| j = 0 |
| while j < 0x300, |
| inv i < 16, |
| { |
| this.probs_lit[i][j] = 1024 |
| j += 1 |
| } |
| i += 1 |
| } |
| |
| // Reset some other LZMA state too. They're not probabilities, but they |
| // need resetting whenever the probabilities do. |
| this.stashed_state = 0 |
| this.stashed_rep0 = 0 |
| this.stashed_rep1 = 0 |
| this.stashed_rep2 = 0 |
| this.stashed_rep3 = 0 |
| } |
| |
| pri const STATE_TRANSITION_LITERAL : roarray[12] base.u8[..= 11] = [ |
| 0x0, 0x0, 0x0, 0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x4, 0x5, |
| ] |
| |
| pri const STATE_TRANSITION_MATCH : roarray[12] base.u8[..= 11] = [ |
| 0x7, 0x7, 0x7, 0x7, 0x7, 0x7, 0x7, 0xA, 0xA, 0xA, 0xA, 0xA, |
| ] |
| |
| pri const STATE_TRANSITION_LONGREP : roarray[12] base.u8[..= 11] = [ |
| 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0xB, 0xB, 0xB, 0xB, 0xB, |
| ] |
| |
| pri const STATE_TRANSITION_SHORTREP : roarray[12] base.u8[..= 11] = [ |
| 0x9, 0x9, 0x9, 0x9, 0x9, 0x9, 0x9, 0xB, 0xB, 0xB, 0xB, 0xB, |
| ] |
| |
| pri const CLAMP_NO_MORE_THAN_3 : roarray[8] base.u8[..= 3] = [ |
| 0, 1, 2, 3, 3, 3, 3, 3, |
| ] |
