X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzx_decompress.c;h=cce98e32a96904f850f5da6d3e10c2f11b9f39b5;hp=36d94ebf63d36d7b8d9d5e38c7f78c42ad054bb1;hb=4ee103c6e2a2988e1fb358bfa2dc38dcb621505a;hpb=b5eacd90b7f342710757755aa185e8cfb19f2030 diff --git a/src/lzx_decompress.c b/src/lzx_decompress.c index 36d94ebf..cce98e32 100644 --- a/src/lzx_decompress.c +++ b/src/lzx_decompress.c @@ -64,7 +64,7 @@ /* These values are chosen for fast decompression. */ #define LZX_MAINCODE_TABLEBITS 11 -#define LZX_LENCODE_TABLEBITS 10 +#define LZX_LENCODE_TABLEBITS 9 #define LZX_PRECODE_TABLEBITS 6 #define LZX_ALIGNEDCODE_TABLEBITS 7 @@ -72,33 +72,49 @@ struct lzx_decompressor { - u16 maincode_decode_table[(1 << LZX_MAINCODE_TABLEBITS) + - (LZX_MAINCODE_MAX_NUM_SYMBOLS * 2)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); + DECODE_TABLE(maincode_decode_table, LZX_MAINCODE_MAX_NUM_SYMBOLS, + LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN); u8 maincode_lens[LZX_MAINCODE_MAX_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN]; - - u16 lencode_decode_table[(1 << LZX_LENCODE_TABLEBITS) + - (LZX_LENCODE_NUM_SYMBOLS * 2)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); + DECODE_TABLE(lencode_decode_table, LZX_LENCODE_NUM_SYMBOLS, + LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN); u8 lencode_lens[LZX_LENCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN]; union { - u16 alignedcode_decode_table[(1 << LZX_ALIGNEDCODE_TABLEBITS) + - (LZX_ALIGNEDCODE_NUM_SYMBOLS * 2)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); + DECODE_TABLE(alignedcode_decode_table, LZX_ALIGNEDCODE_NUM_SYMBOLS, + LZX_ALIGNEDCODE_TABLEBITS, LZX_MAX_ALIGNED_CODEWORD_LEN); u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS]; }; union { - u16 precode_decode_table[(1 << LZX_PRECODE_TABLEBITS) + - (LZX_PRECODE_NUM_SYMBOLS * 2)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); + DECODE_TABLE(precode_decode_table, LZX_PRECODE_NUM_SYMBOLS, + LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN); u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS]; + u8 extra_offset_bits[LZX_MAX_OFFSET_SLOTS]; + }; + + union { + DECODE_TABLE_WORKING_SPACE(maincode_working_space, + LZX_MAINCODE_MAX_NUM_SYMBOLS, + LZX_MAX_MAIN_CODEWORD_LEN); + DECODE_TABLE_WORKING_SPACE(lencode_working_space, + LZX_LENCODE_NUM_SYMBOLS, + LZX_MAX_LEN_CODEWORD_LEN); + DECODE_TABLE_WORKING_SPACE(alignedcode_working_space, + LZX_ALIGNEDCODE_NUM_SYMBOLS, + LZX_MAX_ALIGNED_CODEWORD_LEN); + DECODE_TABLE_WORKING_SPACE(precode_working_space, + LZX_PRECODE_NUM_SYMBOLS, + LZX_MAX_PRE_CODEWORD_LEN); }; unsigned window_order; unsigned num_main_syms; + + /* Like lzx_extra_offset_bits[], but does not include the entropy-coded + * bits of aligned offset blocks */ + u8 extra_offset_bits_minus_aligned[LZX_MAX_OFFSET_SLOTS]; + } _aligned_attribute(DECODE_TABLE_ALIGNMENT); /* Read a Huffman-encoded symbol using the precode. */ @@ -156,7 +172,8 @@ lzx_read_codeword_lens(struct lzx_decompressor *d, struct input_bitstream *is, LZX_PRECODE_NUM_SYMBOLS, LZX_PRECODE_TABLEBITS, d->precode_lens, - LZX_MAX_PRE_CODEWORD_LEN)) + LZX_MAX_PRE_CODEWORD_LEN, + d->precode_working_space)) return -1; /* Decode the codeword lengths. */ @@ -332,14 +349,16 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, d->num_main_syms, LZX_MAINCODE_TABLEBITS, d->maincode_lens, - LZX_MAX_MAIN_CODEWORD_LEN)) + LZX_MAX_MAIN_CODEWORD_LEN, + d->maincode_working_space)) return -1; if (make_huffman_decode_table(d->lencode_decode_table, LZX_LENCODE_NUM_SYMBOLS, LZX_LENCODE_TABLEBITS, d->lencode_lens, - LZX_MAX_LEN_CODEWORD_LEN)) + LZX_MAX_LEN_CODEWORD_LEN, + d->lencode_working_space)) return -1; if (block_type == LZX_BLOCKTYPE_ALIGNED) { @@ -347,11 +366,16 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, LZX_ALIGNEDCODE_NUM_SYMBOLS, LZX_ALIGNEDCODE_TABLEBITS, d->alignedcode_lens, - LZX_MAX_ALIGNED_CODEWORD_LEN)) + LZX_MAX_ALIGNED_CODEWORD_LEN, + d->alignedcode_working_space)) return -1; - min_aligned_offset_slot = 8; + min_aligned_offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT; + memcpy(d->extra_offset_bits, d->extra_offset_bits_minus_aligned, + sizeof(lzx_extra_offset_bits)); } else { min_aligned_offset_slot = LZX_MAX_OFFSET_SLOTS; + memcpy(d->extra_offset_bits, lzx_extra_offset_bits, + sizeof(lzx_extra_offset_bits)); } /* Decode the literals and matches. */ @@ -361,7 +385,6 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, unsigned length; u32 offset; unsigned offset_slot; - unsigned num_extra_bits; mainsym = read_mainsym(d, is); if (mainsym < LZX_NUM_CHARS) { @@ -391,31 +414,12 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, recent_offsets[offset_slot] = recent_offsets[0]; } else { /* Explicit offset */ - - /* Look up the number of extra bits that need to be read - * to decode offsets with this offset slot. */ - num_extra_bits = lzx_extra_offset_bits[offset_slot]; - - /* Start with the offset slot base value. */ - offset = lzx_offset_slot_base[offset_slot]; - - /* In aligned offset blocks, the low-order 3 bits of - * each offset are encoded using the aligned offset - * code. Otherwise, all the extra bits are literal. */ - + offset = bitstream_read_bits(is, d->extra_offset_bits[offset_slot]); if (offset_slot >= min_aligned_offset_slot) { - offset += - bitstream_read_bits(is, - num_extra_bits - - LZX_NUM_ALIGNED_OFFSET_BITS) - << LZX_NUM_ALIGNED_OFFSET_BITS; - offset += read_alignedsym(d, is); - } else { - offset += bitstream_read_bits(is, num_extra_bits); + offset = (offset << LZX_NUM_ALIGNED_OFFSET_BITS) | + read_alignedsym(d, is); } - - /* Adjust the offset. */ - offset -= LZX_OFFSET_ADJUSTMENT; + offset += lzx_offset_slot_base[offset_slot]; /* Update the match offset LRU queue. */ STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3); @@ -424,18 +428,11 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, } recent_offsets[0] = offset; - /* Validate the match, then copy it to the current position. */ - - if (unlikely(length > block_end - out_next)) - return -1; - - if (unlikely(offset > out_next - out_begin)) + /* Validate the match and copy it to the current position. */ + if (unlikely(lz_copy(length, offset, out_begin, + out_next, block_end, LZX_MIN_MATCH_LEN))) return -1; - - lz_copy(out_next, length, offset, block_end, LZX_MIN_MATCH_LEN); - out_next += length; - } while (out_next != block_end); return 0; @@ -525,6 +522,20 @@ lzx_create_decompressor(size_t max_block_size, void **d_ret) d->window_order = window_order; d->num_main_syms = lzx_get_num_main_syms(window_order); + /* Initialize 'd->extra_offset_bits_minus_aligned'. */ + STATIC_ASSERT(sizeof(d->extra_offset_bits_minus_aligned) == + sizeof(lzx_extra_offset_bits)); + STATIC_ASSERT(sizeof(d->extra_offset_bits) == + sizeof(lzx_extra_offset_bits)); + memcpy(d->extra_offset_bits_minus_aligned, lzx_extra_offset_bits, + sizeof(lzx_extra_offset_bits)); + for (unsigned offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT; + offset_slot < LZX_MAX_OFFSET_SLOTS; offset_slot++) + { + d->extra_offset_bits_minus_aligned[offset_slot] -= + LZX_NUM_ALIGNED_OFFSET_BITS; + } + *d_ret = d; return 0; }