X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzms_decompress.c;h=bafe85ee35f5786eaed25fa5194aea1f649ab7a4;hp=0c64a73db286ca822bad0aecc579885a6108f854;hb=151463861a212a1ae7deae7e9844cd0cd1c4343c;hpb=2fd8ff1904371cf9bfbab7105287cc221379552b diff --git a/src/lzms_decompress.c b/src/lzms_decompress.c index 0c64a73d..bafe85ee 100644 --- a/src/lzms_decompress.c +++ b/src/lzms_decompress.c @@ -126,10 +126,9 @@ * references to the first 3 entries at any given time. The queue must be * initialized to the offsets {1, 2, 3, 4}. * - * Repeat delta matches are handled similarly, but for them there are two queues - * updated in lock-step: one for powers and one for raw offsets. The power - * queue must be initialized to {0, 0, 0, 0}, and the raw offset queue must be - * initialized to {1, 2, 3, 4}. + * Repeat delta matches are handled similarly, but for them the queue contains + * (power, raw offset) pairs. This queue must be initialized to + * {(0, 1), (0, 2), (0, 3), (0, 4)}. * * Bits from the binary range decoder must be used to disambiguate item types. * The range decoder must hold two state variables: the range, which must @@ -154,14 +153,14 @@ * it. * * The probability used to range-decode each bit must be taken from a table, of - * which one instance must exist for each distinct context in which a - * range-decoded bit is needed. At each call of the range decoder, the - * appropriate probability must be obtained by indexing the appropriate - * probability table with the last 4 (in the context disambiguating literals - * from matches), 5 (in the context disambiguating LZ matches from delta - * matches), or 6 (in all other contexts) bits recently range-decoded in that - * context, ordered such that the most recently decoded bit is the low-order bit - * of the index. + * which one instance must exist for each distinct context, or "binary decision + * class", in which a range-decoded bit is needed. At each call of the range + * decoder, the appropriate probability must be obtained by indexing the + * appropriate probability table with the last 4 (in the context disambiguating + * literals from matches), 5 (in the context disambiguating LZ matches from + * delta matches), or 6 (in all other contexts) bits recently range-decoded in + * that context, ordered such that the most recently decoded bit is the + * low-order bit of the index. * * Furthermore, each probability entry itself is variable, as its value must be * maintained as n/64 where n is the number of 0 bits in the most recently @@ -198,12 +197,12 @@ * reconstitute the full length. This code must be rebuilt whenever 512 * symbols have been decoded with it. * - * - The delta offset code, used for decoding the offsets of delta matches. + * - The delta offset code, used for decoding the raw offsets of delta matches. * Each symbol corresponds to an offset slot, which corresponds to a base * value and some number of extra bits which must be read and added to the - * base value to reconstitute the full offset. The number of symbols in this - * code is equal to the number of symbols in the LZ offset code. This code - * must be rebuilt whenever 1024 symbols have been decoded with it. + * base value to reconstitute the full raw offset. The number of symbols in + * this code is equal to the number of symbols in the LZ offset code. This + * code must be rebuilt whenever 1024 symbols have been decoded with it. * * - The delta power code, used for decoding the powers of delta matches. Each * of the 8 symbols corresponds to a power. This code must be rebuilt @@ -302,16 +301,17 @@ struct lzms_input_bitstream { const le16 *begin; }; +#define BITBUF_NBITS (8 * sizeof(bitbuf_t)) + /* Bookkeeping information for an adaptive Huffman code */ struct lzms_huffman_rebuild_info { unsigned num_syms_until_rebuild; + unsigned num_syms; unsigned rebuild_freq; + u32 *codewords; + u32 *freqs; u16 *decode_table; unsigned table_bits; - u32 *freqs; - u32 *codewords; - u8 *lens; - unsigned num_syms; }; struct lzms_decompressor { @@ -324,39 +324,31 @@ struct lzms_decompressor { struct lzms_range_decoder rd; struct lzms_input_bitstream is; - /* Match offset LRU queues */ - u32 recent_lz_offsets[LZMS_NUM_RECENT_OFFSETS + 1]; - u64 recent_delta_offsets[LZMS_NUM_RECENT_OFFSETS + 1]; + /* LRU queues for match sources */ + u32 recent_lz_offsets[LZMS_NUM_LZ_REPS + 1]; + u64 recent_delta_pairs[LZMS_NUM_DELTA_REPS + 1]; u32 pending_lz_offset; - u64 pending_delta_offset; + u64 pending_delta_pair; const u8 *lz_offset_still_pending; - const u8 *delta_offset_still_pending; + const u8 *delta_pair_still_pending; - /* States and probabilities for range decoding */ + /* States and probability entries for item type disambiguation */ u32 main_state; - struct lzms_probability_entry main_prob_entries[ - LZMS_NUM_MAIN_STATES]; - u32 match_state; - struct lzms_probability_entry match_prob_entries[ - LZMS_NUM_MATCH_STATES]; - - u32 lz_match_state; - struct lzms_probability_entry lz_match_prob_entries[ - LZMS_NUM_LZ_MATCH_STATES]; - - u32 delta_match_state; - struct lzms_probability_entry delta_match_prob_entries[ - LZMS_NUM_DELTA_MATCH_STATES]; - - u32 lz_repeat_match_states[LZMS_NUM_RECENT_OFFSETS - 1]; - struct lzms_probability_entry lz_repeat_match_prob_entries[ - LZMS_NUM_RECENT_OFFSETS - 1][LZMS_NUM_LZ_REPEAT_MATCH_STATES]; - - u32 delta_repeat_match_states[LZMS_NUM_RECENT_OFFSETS - 1]; - struct lzms_probability_entry delta_repeat_match_prob_entries[ - LZMS_NUM_RECENT_OFFSETS - 1][LZMS_NUM_DELTA_REPEAT_MATCH_STATES]; + u32 lz_state; + u32 delta_state; + u32 lz_rep_states[LZMS_NUM_LZ_REP_DECISIONS]; + u32 delta_rep_states[LZMS_NUM_DELTA_REP_DECISIONS]; + + struct lzms_probability_entry main_probs[LZMS_NUM_MAIN_PROBS]; + struct lzms_probability_entry match_probs[LZMS_NUM_MATCH_PROBS]; + struct lzms_probability_entry lz_probs[LZMS_NUM_LZ_PROBS]; + struct lzms_probability_entry delta_probs[LZMS_NUM_DELTA_PROBS]; + struct lzms_probability_entry lz_rep_probs[LZMS_NUM_LZ_REP_DECISIONS] + [LZMS_NUM_LZ_REP_PROBS]; + struct lzms_probability_entry delta_rep_probs[LZMS_NUM_DELTA_REP_DECISIONS] + [LZMS_NUM_DELTA_REP_PROBS]; /* Huffman decoding */ @@ -366,18 +358,18 @@ struct lzms_decompressor { u32 literal_freqs[LZMS_NUM_LITERAL_SYMS]; struct lzms_huffman_rebuild_info literal_rebuild_info; - u16 length_decode_table[(1 << LZMS_LENGTH_TABLEBITS) + - (2 * LZMS_NUM_LENGTH_SYMS)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); - u32 length_freqs[LZMS_NUM_LENGTH_SYMS]; - struct lzms_huffman_rebuild_info length_rebuild_info; - u16 lz_offset_decode_table[(1 << LZMS_LZ_OFFSET_TABLEBITS) + ( 2 * LZMS_MAX_NUM_OFFSET_SYMS)] _aligned_attribute(DECODE_TABLE_ALIGNMENT); u32 lz_offset_freqs[LZMS_MAX_NUM_OFFSET_SYMS]; struct lzms_huffman_rebuild_info lz_offset_rebuild_info; + u16 length_decode_table[(1 << LZMS_LENGTH_TABLEBITS) + + (2 * LZMS_NUM_LENGTH_SYMS)] + _aligned_attribute(DECODE_TABLE_ALIGNMENT); + u32 length_freqs[LZMS_NUM_LENGTH_SYMS]; + struct lzms_huffman_rebuild_info length_rebuild_info; + u16 delta_offset_decode_table[(1 << LZMS_DELTA_OFFSET_TABLEBITS) + (2 * LZMS_MAX_NUM_OFFSET_SYMS)] _aligned_attribute(DECODE_TABLE_ALIGNMENT); @@ -391,7 +383,6 @@ struct lzms_decompressor { struct lzms_huffman_rebuild_info delta_power_rebuild_info; u32 codewords[LZMS_MAX_NUM_SYMS]; - u8 lens[LZMS_MAX_NUM_SYMS]; }; // struct @@ -417,27 +408,35 @@ lzms_input_bitstream_init(struct lzms_input_bitstream *is, static inline void lzms_ensure_bits(struct lzms_input_bitstream *is, unsigned num_bits) { + unsigned avail; + if (is->bitsleft >= num_bits) return; - if (likely(is->next != is->begin)) - is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next) - << (sizeof(is->bitbuf) * 8 - is->bitsleft - 16); - is->bitsleft += 16; + avail = BITBUF_NBITS - is->bitsleft; - if (likely(is->next != is->begin)) - is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next) - << (sizeof(is->bitbuf) * 8 - is->bitsleft - 16); - is->bitsleft += 16; + if (UNALIGNED_ACCESS_IS_FAST && CPU_IS_LITTLE_ENDIAN && + WORDSIZE == 8 && likely((u8 *)is->next - (u8 *)is->begin >= 8)) + { + is->next -= avail >> 4; + is->bitbuf |= load_u64_unaligned(is->next) << (avail & 15); + is->bitsleft += avail & ~15; + } else { + if (likely(is->next != is->begin)) + is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next) + << (avail - 16); + if (likely(is->next != is->begin)) + is->bitbuf |=(bitbuf_t)le16_to_cpu(*--is->next) + << (avail - 32); + is->bitsleft += 32; + } } /* Get @num_bits bits from the bitbuffer variable. */ static inline bitbuf_t lzms_peek_bits(struct lzms_input_bitstream *is, unsigned num_bits) { - if (unlikely(num_bits == 0)) - return 0; - return is->bitbuf >> (sizeof(is->bitbuf) * 8 - num_bits); + return (is->bitbuf >> 1) >> (BITBUF_NBITS - num_bits - 1); } /* Remove @num_bits bits from the bitbuffer variable. */ @@ -477,15 +476,26 @@ lzms_range_decoder_init(struct lzms_range_decoder *rd, rd->end = in + count; } -/* Decode and return the next bit from the range decoder. - * - * @prob is the chance out of LZMS_PROBABILITY_MAX that the next bit is 0. +/* + * Decode a bit using the range coder. The current state specifies the + * probability entry to use. The state and probability entry will be updated + * based on the decoded bit. */ static inline int -lzms_range_decoder_decode_bit(struct lzms_range_decoder *rd, u32 prob) +lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states, + struct lzms_probability_entry *probs) { + struct lzms_probability_entry *prob_entry; + u32 prob; u32 bound; + /* Load the probability entry corresponding to the current state. */ + prob_entry = &probs[*state_p]; + + /* Get the probability (out of LZMS_PROBABILITY_DENOMINATOR) that the + * next bit is 0. */ + prob = lzms_get_probability(prob_entry); + /* Normalize if needed. */ if (rd->range <= 0xffff) { rd->range <<= 16; @@ -501,136 +511,116 @@ lzms_range_decoder_decode_bit(struct lzms_range_decoder *rd, u32 prob) if (rd->code < bound) { /* Current code is in the 0-bit region of the range. */ rd->range = bound; + + /* Update the state and probability entry based on the decoded bit. */ + *state_p = ((*state_p << 1) | 0) & (num_states - 1); + lzms_update_probability_entry(prob_entry, 0); return 0; } else { /* Current code is in the 1-bit region of the range. */ rd->range -= bound; rd->code -= bound; + + /* Update the state and probability entry based on the decoded bit. */ + *state_p = ((*state_p << 1) | 1) & (num_states - 1); + lzms_update_probability_entry(prob_entry, 1); return 1; } } -/* Decode and return the next bit from the range decoder. This wraps around - * lzms_range_decoder_decode_bit() to handle using and updating the appropriate - * state and probability entry. */ -static inline int -lzms_range_decode_bit(struct lzms_range_decoder *rd, - u32 *state_p, u32 num_states, - struct lzms_probability_entry prob_entries[]) -{ - struct lzms_probability_entry *prob_entry; - u32 prob; - int bit; - - /* Load the probability entry corresponding to the current state. */ - prob_entry = &prob_entries[*state_p]; - - /* Get the probability that the next bit is 0. */ - prob = lzms_get_probability(prob_entry); - - /* Decode the next bit. */ - bit = lzms_range_decoder_decode_bit(rd, prob); - - /* Update the state and probability entry based on the decoded bit. */ - *state_p = ((*state_p << 1) | bit) & (num_states - 1); - lzms_update_probability_entry(prob_entry, bit); - - /* Return the decoded bit. */ - return bit; -} - static int lzms_decode_main_bit(struct lzms_decompressor *d) { - return lzms_range_decode_bit(&d->rd, &d->main_state, - LZMS_NUM_MAIN_STATES, - d->main_prob_entries); + return lzms_decode_bit(&d->rd, &d->main_state, + LZMS_NUM_MAIN_PROBS, d->main_probs); } static int lzms_decode_match_bit(struct lzms_decompressor *d) { - return lzms_range_decode_bit(&d->rd, &d->match_state, - LZMS_NUM_MATCH_STATES, - d->match_prob_entries); + return lzms_decode_bit(&d->rd, &d->match_state, + LZMS_NUM_MATCH_PROBS, d->match_probs); } static int -lzms_decode_lz_match_bit(struct lzms_decompressor *d) +lzms_decode_lz_bit(struct lzms_decompressor *d) { - return lzms_range_decode_bit(&d->rd, &d->lz_match_state, - LZMS_NUM_LZ_MATCH_STATES, - d->lz_match_prob_entries); + return lzms_decode_bit(&d->rd, &d->lz_state, + LZMS_NUM_LZ_PROBS, d->lz_probs); } static int -lzms_decode_delta_match_bit(struct lzms_decompressor *d) +lzms_decode_delta_bit(struct lzms_decompressor *d) { - return lzms_range_decode_bit(&d->rd, &d->delta_match_state, - LZMS_NUM_DELTA_MATCH_STATES, - d->delta_match_prob_entries); + return lzms_decode_bit(&d->rd, &d->delta_state, + LZMS_NUM_DELTA_PROBS, d->delta_probs); } static noinline int -lzms_decode_lz_repeat_match_bit(struct lzms_decompressor *d, int idx) +lzms_decode_lz_rep_bit(struct lzms_decompressor *d, int idx) { - return lzms_range_decode_bit(&d->rd, &d->lz_repeat_match_states[idx], - LZMS_NUM_LZ_REPEAT_MATCH_STATES, - d->lz_repeat_match_prob_entries[idx]); + return lzms_decode_bit(&d->rd, &d->lz_rep_states[idx], + LZMS_NUM_LZ_REP_PROBS, d->lz_rep_probs[idx]); } static noinline int -lzms_decode_delta_repeat_match_bit(struct lzms_decompressor *d, int idx) +lzms_decode_delta_rep_bit(struct lzms_decompressor *d, int idx) { - return lzms_range_decode_bit(&d->rd, &d->delta_repeat_match_states[idx], - LZMS_NUM_DELTA_REPEAT_MATCH_STATES, - d->delta_repeat_match_prob_entries[idx]); + return lzms_decode_bit(&d->rd, &d->delta_rep_states[idx], + LZMS_NUM_DELTA_REP_PROBS, d->delta_rep_probs[idx]); } static void -lzms_init_huffman_rebuild_info(struct lzms_huffman_rebuild_info *info, - unsigned rebuild_freq, - u16 *decode_table, unsigned table_bits, - u32 *freqs, u32 *codewords, u8 *lens, - unsigned num_syms) +lzms_build_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info) { - info->num_syms_until_rebuild = 1; - info->rebuild_freq = rebuild_freq; - info->decode_table = decode_table; - info->table_bits = table_bits; - info->freqs = freqs; - info->codewords = codewords; - info->lens = lens; - info->num_syms = num_syms; + make_canonical_huffman_code(rebuild_info->num_syms, + LZMS_MAX_CODEWORD_LENGTH, + rebuild_info->freqs, + (u8 *)rebuild_info->decode_table, + rebuild_info->codewords); + + make_huffman_decode_table(rebuild_info->decode_table, + rebuild_info->num_syms, + rebuild_info->table_bits, + (u8 *)rebuild_info->decode_table, + LZMS_MAX_CODEWORD_LENGTH); + + rebuild_info->num_syms_until_rebuild = rebuild_info->rebuild_freq; +} + +static void +lzms_init_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info, + unsigned num_syms, unsigned rebuild_freq, + u32 *codewords, u32 *freqs, + u16 *decode_table, unsigned table_bits) +{ + rebuild_info->num_syms = num_syms; + rebuild_info->rebuild_freq = rebuild_freq; + rebuild_info->codewords = codewords; + rebuild_info->freqs = freqs; + rebuild_info->decode_table = decode_table; + rebuild_info->table_bits = table_bits; lzms_init_symbol_frequencies(freqs, num_syms); + lzms_build_huffman_code(rebuild_info); } static noinline void -lzms_rebuild_huffman_code(struct lzms_huffman_rebuild_info *info) +lzms_rebuild_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info) { - make_canonical_huffman_code(info->num_syms, LZMS_MAX_CODEWORD_LEN, - info->freqs, info->lens, info->codewords); - make_huffman_decode_table(info->decode_table, info->num_syms, - info->table_bits, info->lens, - LZMS_MAX_CODEWORD_LEN); - for (unsigned i = 0; i < info->num_syms; i++) - info->freqs[i] = (info->freqs[i] >> 1) + 1; - info->num_syms_until_rebuild = info->rebuild_freq; + lzms_build_huffman_code(rebuild_info); + lzms_dilute_symbol_frequencies(rebuild_info->freqs, rebuild_info->num_syms); } static inline unsigned -lzms_decode_huffman_symbol(struct lzms_input_bitstream *is, - u16 decode_table[], unsigned table_bits, +lzms_decode_huffman_symbol(struct lzms_input_bitstream *is, u16 decode_table[], + unsigned table_bits, u32 freqs[], struct lzms_huffman_rebuild_info *rebuild_info) { unsigned key_bits; unsigned entry; unsigned sym; - if (unlikely(--rebuild_info->num_syms_until_rebuild == 0)) - lzms_rebuild_huffman_code(rebuild_info); - - lzms_ensure_bits(is, LZMS_MAX_CODEWORD_LEN); + lzms_ensure_bits(is, LZMS_MAX_CODEWORD_LENGTH); /* Index the decode table by the next table_bits bits of the input. */ key_bits = lzms_peek_bits(is, table_bits); @@ -654,8 +644,9 @@ lzms_decode_huffman_symbol(struct lzms_input_bitstream *is, sym = entry; } - /* Tally and return the decoded symbol. */ - rebuild_info->freqs[sym]++; + freqs[sym]++; + if (--rebuild_info->num_syms_until_rebuild == 0) + lzms_rebuild_huffman_code(rebuild_info); return sym; } @@ -665,15 +656,29 @@ lzms_decode_literal(struct lzms_decompressor *d) return lzms_decode_huffman_symbol(&d->is, d->literal_decode_table, LZMS_LITERAL_TABLEBITS, + d->literal_freqs, &d->literal_rebuild_info); } +static u32 +lzms_decode_lz_offset(struct lzms_decompressor *d) +{ + unsigned slot = lzms_decode_huffman_symbol(&d->is, + d->lz_offset_decode_table, + LZMS_LZ_OFFSET_TABLEBITS, + d->lz_offset_freqs, + &d->lz_offset_rebuild_info); + return lzms_offset_slot_base[slot] + + lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]); +} + static u32 lzms_decode_length(struct lzms_decompressor *d) { unsigned slot = lzms_decode_huffman_symbol(&d->is, d->length_decode_table, LZMS_LENGTH_TABLEBITS, + d->length_freqs, &d->length_rebuild_info); u32 length = lzms_length_slot_base[slot]; unsigned num_extra_bits = lzms_extra_length_bits[slot]; @@ -683,23 +688,13 @@ lzms_decode_length(struct lzms_decompressor *d) return length; } -static u32 -lzms_decode_lz_offset(struct lzms_decompressor *d) -{ - unsigned slot = lzms_decode_huffman_symbol(&d->is, - d->lz_offset_decode_table, - LZMS_LZ_OFFSET_TABLEBITS, - &d->lz_offset_rebuild_info); - return lzms_offset_slot_base[slot] + - lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]); -} - static u32 lzms_decode_delta_offset(struct lzms_decompressor *d) { unsigned slot = lzms_decode_huffman_symbol(&d->is, d->delta_offset_decode_table, LZMS_DELTA_OFFSET_TABLEBITS, + d->delta_offset_freqs, &d->delta_offset_rebuild_info); return lzms_offset_slot_base[slot] + lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]); @@ -711,6 +706,7 @@ lzms_decode_delta_power(struct lzms_decompressor *d) return lzms_decode_huffman_symbol(&d->is, d->delta_power_decode_table, LZMS_DELTA_POWER_TABLEBITS, + d->delta_power_freqs, &d->delta_power_rebuild_info); } @@ -737,30 +733,30 @@ lzms_decode_items(struct lzms_decompressor * const restrict d, u32 offset; u32 length; - if (d->pending_lz_offset != 0 && - out_next != d->lz_offset_still_pending) - { - BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3); - d->recent_lz_offsets[3] = d->recent_lz_offsets[2]; - d->recent_lz_offsets[2] = d->recent_lz_offsets[1]; - d->recent_lz_offsets[1] = d->recent_lz_offsets[0]; - d->recent_lz_offsets[0] = d->pending_lz_offset; - d->pending_lz_offset = 0; - } - - if (!lzms_decode_lz_match_bit(d)) { + if (!lzms_decode_lz_bit(d)) { /* Explicit offset */ offset = lzms_decode_lz_offset(d); } else { /* Repeat offset */ - BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3); - if (!lzms_decode_lz_repeat_match_bit(d, 0)) { + if (d->pending_lz_offset != 0 && + out_next != d->lz_offset_still_pending) + { + BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3); + d->recent_lz_offsets[3] = d->recent_lz_offsets[2]; + d->recent_lz_offsets[2] = d->recent_lz_offsets[1]; + d->recent_lz_offsets[1] = d->recent_lz_offsets[0]; + d->recent_lz_offsets[0] = d->pending_lz_offset; + d->pending_lz_offset = 0; + } + + BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3); + if (!lzms_decode_lz_rep_bit(d, 0)) { offset = d->recent_lz_offsets[0]; d->recent_lz_offsets[0] = d->recent_lz_offsets[1]; d->recent_lz_offsets[1] = d->recent_lz_offsets[2]; d->recent_lz_offsets[2] = d->recent_lz_offsets[3]; - } else if (!lzms_decode_lz_repeat_match_bit(d, 1)) { + } else if (!lzms_decode_lz_rep_bit(d, 1)) { offset = d->recent_lz_offsets[1]; d->recent_lz_offsets[1] = d->recent_lz_offsets[2]; d->recent_lz_offsets[2] = d->recent_lz_offsets[3]; @@ -771,7 +767,7 @@ lzms_decode_items(struct lzms_decompressor * const restrict d, } if (d->pending_lz_offset != 0) { - BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3); + BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3); d->recent_lz_offsets[3] = d->recent_lz_offsets[2]; d->recent_lz_offsets[2] = d->recent_lz_offsets[1]; d->recent_lz_offsets[1] = d->recent_lz_offsets[0]; @@ -786,30 +782,23 @@ lzms_decode_items(struct lzms_decompressor * const restrict d, if (unlikely(offset > out_next - out)) return -1; - lz_copy(out_next, length, offset, out_end, LZMS_MIN_MATCH_LEN); + lz_copy(out_next, length, offset, out_end, LZMS_MIN_MATCH_LENGTH); out_next += length; d->lz_offset_still_pending = out_next; } else { /* Delta match */ + /* (See beginning of file for more information.) */ + u32 power; - u32 raw_offset, offset1, offset2, offset; - const u8 *matchptr1, *matchptr2, *matchptr; + u32 raw_offset; + u32 span; + u32 offset; + const u8 *matchptr; u32 length; - if (d->pending_delta_offset != 0 && - out_next != d->delta_offset_still_pending) - { - BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3); - d->recent_delta_offsets[3] = d->recent_delta_offsets[2]; - d->recent_delta_offsets[2] = d->recent_delta_offsets[1]; - d->recent_delta_offsets[1] = d->recent_delta_offsets[0]; - d->recent_delta_offsets[0] = d->pending_delta_offset; - d->pending_delta_offset = 0; - } - - if (!lzms_decode_delta_match_bit(d)) { + if (!lzms_decode_delta_bit(d)) { /* Explicit offset */ power = lzms_decode_delta_power(d); raw_offset = lzms_decode_delta_offset(d); @@ -817,62 +806,74 @@ lzms_decode_items(struct lzms_decompressor * const restrict d, /* Repeat offset */ u64 val; - BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3); - if (!lzms_decode_delta_repeat_match_bit(d, 0)) { - val = d->recent_delta_offsets[0]; - d->recent_delta_offsets[0] = d->recent_delta_offsets[1]; - d->recent_delta_offsets[1] = d->recent_delta_offsets[2]; - d->recent_delta_offsets[2] = d->recent_delta_offsets[3]; - } else if (!lzms_decode_delta_repeat_match_bit(d, 1)) { - val = d->recent_delta_offsets[1]; - d->recent_delta_offsets[1] = d->recent_delta_offsets[2]; - d->recent_delta_offsets[2] = d->recent_delta_offsets[3]; + if (d->pending_delta_pair != 0 && + out_next != d->delta_pair_still_pending) + { + BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3); + d->recent_delta_pairs[3] = d->recent_delta_pairs[2]; + d->recent_delta_pairs[2] = d->recent_delta_pairs[1]; + d->recent_delta_pairs[1] = d->recent_delta_pairs[0]; + d->recent_delta_pairs[0] = d->pending_delta_pair; + d->pending_delta_pair = 0; + } + + BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3); + if (!lzms_decode_delta_rep_bit(d, 0)) { + val = d->recent_delta_pairs[0]; + d->recent_delta_pairs[0] = d->recent_delta_pairs[1]; + d->recent_delta_pairs[1] = d->recent_delta_pairs[2]; + d->recent_delta_pairs[2] = d->recent_delta_pairs[3]; + } else if (!lzms_decode_delta_rep_bit(d, 1)) { + val = d->recent_delta_pairs[1]; + d->recent_delta_pairs[1] = d->recent_delta_pairs[2]; + d->recent_delta_pairs[2] = d->recent_delta_pairs[3]; } else { - val = d->recent_delta_offsets[2]; - d->recent_delta_offsets[2] = d->recent_delta_offsets[3]; + val = d->recent_delta_pairs[2]; + d->recent_delta_pairs[2] = d->recent_delta_pairs[3]; } power = val >> 32; raw_offset = (u32)val; } - if (d->pending_delta_offset != 0) { - BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3); - d->recent_delta_offsets[3] = d->recent_delta_offsets[2]; - d->recent_delta_offsets[2] = d->recent_delta_offsets[1]; - d->recent_delta_offsets[1] = d->recent_delta_offsets[0]; - d->recent_delta_offsets[0] = d->pending_delta_offset; + if (d->pending_delta_pair != 0) { + BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3); + d->recent_delta_pairs[3] = d->recent_delta_pairs[2]; + d->recent_delta_pairs[2] = d->recent_delta_pairs[1]; + d->recent_delta_pairs[1] = d->recent_delta_pairs[0]; + d->recent_delta_pairs[0] = d->pending_delta_pair; } - d->pending_delta_offset = raw_offset | ((u64)power << 32); + d->pending_delta_pair = raw_offset | ((u64)power << 32); length = lzms_decode_length(d); - offset1 = (u32)1 << power; - offset2 = raw_offset << power; - offset = offset1 + offset2; + span = (u32)1 << power; + offset = raw_offset << power; - /* raw_offset<> power) != raw_offset)) + /* raw_offset<> power != raw_offset)) return -1; - /* offset1+offset2 overflowed? */ - if (unlikely(offset < offset2)) + /* offset+span overflows? */ + if (unlikely(offset + span < offset)) return -1; - if (unlikely(length > out_end - out_next)) + /* buffer underrun? */ + if (unlikely(offset + span > out_next - out)) return -1; - if (unlikely(offset > out_next - out)) + /* buffer overrun? */ + if (unlikely(length > out_end - out_next)) return -1; - matchptr1 = out_next - offset1; - matchptr2 = out_next - offset2; matchptr = out_next - offset; - do { - *out_next++ = *matchptr1++ + *matchptr2++ - *matchptr++; + *out_next = *matchptr + *(out_next - span) - + *(matchptr - span); + out_next++; + matchptr++; } while (--length); - d->delta_offset_still_pending = out_next; + d->delta_pair_still_pending = out_next; } } return 0; @@ -883,87 +884,84 @@ lzms_init_decompressor(struct lzms_decompressor *d, const void *in, size_t in_nbytes, unsigned num_offset_slots) { /* Match offset LRU queues */ - for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) { + for (int i = 0; i < LZMS_NUM_LZ_REPS + 1; i++) d->recent_lz_offsets[i] = i + 1; - d->recent_delta_offsets[i] = i + 1; - } + for (int i = 0; i < LZMS_NUM_DELTA_REPS + 1; i++) + d->recent_delta_pairs[i] = i + 1; d->pending_lz_offset = 0; - d->pending_delta_offset = 0; + d->pending_delta_pair = 0; /* Range decoding */ lzms_range_decoder_init(&d->rd, in, in_nbytes / sizeof(le16)); d->main_state = 0; - lzms_init_probability_entries(d->main_prob_entries, LZMS_NUM_MAIN_STATES); + lzms_init_probability_entries(d->main_probs, LZMS_NUM_MAIN_PROBS); d->match_state = 0; - lzms_init_probability_entries(d->match_prob_entries, LZMS_NUM_MATCH_STATES); + lzms_init_probability_entries(d->match_probs, LZMS_NUM_MATCH_PROBS); - d->lz_match_state = 0; - lzms_init_probability_entries(d->lz_match_prob_entries, LZMS_NUM_LZ_MATCH_STATES); + d->lz_state = 0; + lzms_init_probability_entries(d->lz_probs, LZMS_NUM_LZ_PROBS); - d->delta_match_state = 0; - lzms_init_probability_entries(d->delta_match_prob_entries, LZMS_NUM_DELTA_MATCH_STATES); + for (int i = 0; i < LZMS_NUM_LZ_REP_DECISIONS; i++) { + d->lz_rep_states[i] = 0; + lzms_init_probability_entries(d->lz_rep_probs[i], + LZMS_NUM_LZ_REP_PROBS); + } - for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++) { - d->lz_repeat_match_states[i] = 0; - lzms_init_probability_entries(d->lz_repeat_match_prob_entries[i], - LZMS_NUM_LZ_REPEAT_MATCH_STATES); + d->delta_state = 0; + lzms_init_probability_entries(d->delta_probs, LZMS_NUM_DELTA_PROBS); - d->delta_repeat_match_states[i] = 0; - lzms_init_probability_entries(d->delta_repeat_match_prob_entries[i], - LZMS_NUM_DELTA_REPEAT_MATCH_STATES); + for (int i = 0; i < LZMS_NUM_DELTA_REP_DECISIONS; i++) { + d->delta_rep_states[i] = 0; + lzms_init_probability_entries(d->delta_rep_probs[i], + LZMS_NUM_DELTA_REP_PROBS); } /* Huffman decoding */ lzms_input_bitstream_init(&d->is, in, in_nbytes / sizeof(le16)); - lzms_init_huffman_rebuild_info(&d->literal_rebuild_info, - LZMS_LITERAL_CODE_REBUILD_FREQ, - d->literal_decode_table, - LZMS_LITERAL_TABLEBITS, - d->literal_freqs, - d->codewords, - d->lens, - LZMS_NUM_LITERAL_SYMS); - - lzms_init_huffman_rebuild_info(&d->length_rebuild_info, - LZMS_LENGTH_CODE_REBUILD_FREQ, - d->length_decode_table, - LZMS_LENGTH_TABLEBITS, - d->length_freqs, - d->codewords, - d->lens, - LZMS_NUM_LENGTH_SYMS); - - lzms_init_huffman_rebuild_info(&d->lz_offset_rebuild_info, - LZMS_LZ_OFFSET_CODE_REBUILD_FREQ, - d->lz_offset_decode_table, - LZMS_LZ_OFFSET_TABLEBITS, - d->lz_offset_freqs, - d->codewords, - d->lens, - num_offset_slots); - - lzms_init_huffman_rebuild_info(&d->delta_offset_rebuild_info, - LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ, - d->delta_offset_decode_table, - LZMS_DELTA_OFFSET_TABLEBITS, - d->delta_offset_freqs, - d->codewords, - d->lens, - num_offset_slots); - - lzms_init_huffman_rebuild_info(&d->delta_power_rebuild_info, - LZMS_DELTA_POWER_CODE_REBUILD_FREQ, - d->delta_power_decode_table, - LZMS_DELTA_POWER_TABLEBITS, - d->delta_power_freqs, - d->codewords, - d->lens, - LZMS_NUM_DELTA_POWER_SYMS); + lzms_init_huffman_code(&d->literal_rebuild_info, + LZMS_NUM_LITERAL_SYMS, + LZMS_LITERAL_CODE_REBUILD_FREQ, + d->codewords, + d->literal_freqs, + d->literal_decode_table, + LZMS_LITERAL_TABLEBITS); + + lzms_init_huffman_code(&d->lz_offset_rebuild_info, + num_offset_slots, + LZMS_LZ_OFFSET_CODE_REBUILD_FREQ, + d->codewords, + d->lz_offset_freqs, + d->lz_offset_decode_table, + LZMS_LZ_OFFSET_TABLEBITS); + + lzms_init_huffman_code(&d->length_rebuild_info, + LZMS_NUM_LENGTH_SYMS, + LZMS_LENGTH_CODE_REBUILD_FREQ, + d->codewords, + d->length_freqs, + d->length_decode_table, + LZMS_LENGTH_TABLEBITS); + + lzms_init_huffman_code(&d->delta_offset_rebuild_info, + num_offset_slots, + LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ, + d->codewords, + d->delta_offset_freqs, + d->delta_offset_decode_table, + LZMS_DELTA_OFFSET_TABLEBITS); + + lzms_init_huffman_code(&d->delta_power_rebuild_info, + LZMS_NUM_DELTA_POWER_SYMS, + LZMS_DELTA_POWER_CODE_REBUILD_FREQ, + d->codewords, + d->delta_power_freqs, + d->delta_power_decode_table, + LZMS_DELTA_POWER_TABLEBITS); } static int @@ -983,9 +981,11 @@ lzms_create_decompressor(size_t max_bufsize, void **d_ret) return 0; } -/* Decompress @in_nbytes bytes of LZMS-compressed data at @in and write the +/* + * Decompress @in_nbytes bytes of LZMS-compressed data at @in and write the * uncompressed data, which had original size @out_nbytes, to @out. Return 0 if - * successful or -1 if the compressed data is invalid. */ + * successful or -1 if the compressed data is invalid. + */ static int lzms_decompress(const void *in, size_t in_nbytes, void *out, size_t out_nbytes, void *_d)