From b5eacd90b7f342710757755aa185e8cfb19f2030 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Sat, 9 Jul 2016 10:01:16 -0500 Subject: [PATCH] lzx_decompress: decompressor cleanup --- include/wimlib/decompress_common.h | 9 +- src/lzx_decompress.c | 549 ++++++++++++----------------- 2 files changed, 226 insertions(+), 332 deletions(-) diff --git a/include/wimlib/decompress_common.h b/include/wimlib/decompress_common.h index a06ede14..c3016475 100644 --- a/include/wimlib/decompress_common.h +++ b/include/wimlib/decompress_common.h @@ -173,16 +173,15 @@ bitstream_read_u32(struct input_bitstream *is) } /* Read into @dst_buffer an array of literal bytes embedded in the bitstream. - * Return either a pointer to the byte past the last written, or NULL if the - * read overflows the input buffer. */ -static inline void * + * Return 0 if there were enough bytes remaining in the input, otherwise -1. */ +static inline int bitstream_read_bytes(struct input_bitstream *is, void *dst_buffer, size_t count) { if (unlikely(is->end - is->next < count)) - return NULL; + return -1; memcpy(dst_buffer, is->next, count); is->next += count; - return (u8 *)dst_buffer + count; + return 0; } /* Align the input bitstream on a coding-unit boundary. */ diff --git a/src/lzx_decompress.c b/src/lzx_decompress.c index 9a030759..36d94ebf 100644 --- a/src/lzx_decompress.c +++ b/src/lzx_decompress.c @@ -5,7 +5,7 @@ */ /* - * Copyright (C) 2012, 2013, 2014, 2015 Eric Biggers + * Copyright (C) 2012-2016 Eric Biggers * * This file is free software; you can redistribute it and/or modify it under * the terms of the GNU Lesser General Public License as published by the Free @@ -70,8 +70,7 @@ #define LZX_READ_LENS_MAX_OVERRUN 50 -/* Huffman decoding tables, and arrays that map symbols to codeword lengths. */ -struct lzx_tables { +struct lzx_decompressor { u16 maincode_decode_table[(1 << LZX_MAINCODE_TABLEBITS) + (LZX_MAINCODE_MAX_NUM_SYMBOLS * 2)] @@ -84,117 +83,81 @@ struct lzx_tables { _aligned_attribute(DECODE_TABLE_ALIGNMENT); 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); + u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS]; + }; - u16 alignedcode_decode_table[(1 << LZX_ALIGNEDCODE_TABLEBITS) + - (LZX_ALIGNEDCODE_NUM_SYMBOLS * 2)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); - u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS]; -} _aligned_attribute(DECODE_TABLE_ALIGNMENT); - -/* Least-recently used queue for match offsets. */ -struct lzx_lru_queue { - u32 R[LZX_NUM_RECENT_OFFSETS]; -}; - -static inline void -lzx_lru_queue_init(struct lzx_lru_queue *queue) -{ - for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++) - queue->R[i] = 1; -} + union { + u16 precode_decode_table[(1 << LZX_PRECODE_TABLEBITS) + + (LZX_PRECODE_NUM_SYMBOLS * 2)] + _aligned_attribute(DECODE_TABLE_ALIGNMENT); + u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS]; + }; -/* The main LZX decompressor structure. - * - * Note: we keep track of most of the decompression state outside this - * structure. This structure only exists so that (1) we can store @window_order - * and @num_main_syms for multiple calls to lzx_decompress(); and (2) so that we - * don't have to allocate the large 'struct lzx_tables' on the stack. */ -struct lzx_decompressor { unsigned window_order; unsigned num_main_syms; - struct lzx_tables tables; -}; +} _aligned_attribute(DECODE_TABLE_ALIGNMENT); -/* Read a Huffman-encoded symbol using the precode. */ +/* Read a Huffman-encoded symbol using the precode. */ static inline unsigned -read_huffsym_using_precode(struct input_bitstream *istream, - const u16 precode_decode_table[]) +read_presym(const struct lzx_decompressor *d, struct input_bitstream *is) { - return read_huffsym(istream, precode_decode_table, + return read_huffsym(is, d->precode_decode_table, LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN); } -/* Read a Huffman-encoded symbol using the main code. */ +/* Read a Huffman-encoded symbol using the main code. */ static inline unsigned -read_huffsym_using_maincode(struct input_bitstream *istream, - const struct lzx_tables *tables) +read_mainsym(const struct lzx_decompressor *d, struct input_bitstream *is) { - return read_huffsym(istream, tables->maincode_decode_table, + return read_huffsym(is, d->maincode_decode_table, LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN); } -/* Read a Huffman-encoded symbol using the length code. */ +/* Read a Huffman-encoded symbol using the length code. */ static inline unsigned -read_huffsym_using_lencode(struct input_bitstream *istream, - const struct lzx_tables *tables) +read_lensym(const struct lzx_decompressor *d, struct input_bitstream *is) { - return read_huffsym(istream, tables->lencode_decode_table, + return read_huffsym(is, d->lencode_decode_table, LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN); } -/* Read a Huffman-encoded symbol using the aligned offset code. */ +/* Read a Huffman-encoded symbol using the aligned offset code. */ static inline unsigned -read_huffsym_using_alignedcode(struct input_bitstream *istream, - const struct lzx_tables *tables) +read_alignedsym(const struct lzx_decompressor *d, struct input_bitstream *is) { - return read_huffsym(istream, tables->alignedcode_decode_table, + return read_huffsym(is, d->alignedcode_decode_table, LZX_ALIGNEDCODE_TABLEBITS, LZX_MAX_ALIGNED_CODEWORD_LEN); } /* - * Read the precode from the compressed input bitstream, then use it to decode - * @num_lens codeword length values. - * - * @istream: - * The input bitstream. - * - * @lens: - * An array that contains the length values from the previous time the - * codeword lengths for this Huffman code were read, or all 0's if this is - * the first time. This array must have at least (@num_lens + - * LZX_READ_LENS_MAX_OVERRUN) entries. - * - * @num_lens: - * Number of length values to decode. - * - * Returns 0 on success, or -1 if the data was invalid. + * Read a precode from the compressed input bitstream, then use it to decode + * @num_lens codeword length values and write them to @lens. */ static int -lzx_read_codeword_lens(struct input_bitstream *istream, u8 *lens, unsigned num_lens) +lzx_read_codeword_lens(struct lzx_decompressor *d, struct input_bitstream *is, + u8 *lens, unsigned num_lens) { - u16 precode_decode_table[(1 << LZX_PRECODE_TABLEBITS) + - (LZX_PRECODE_NUM_SYMBOLS * 2)] - _aligned_attribute(DECODE_TABLE_ALIGNMENT); - u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS]; u8 *len_ptr = lens; u8 *lens_end = lens + num_lens; - int ret; - /* Read the lengths of the precode codewords. These are given - * explicitly. */ + /* Read the lengths of the precode codewords. These are stored + * explicitly. */ for (int i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++) { - precode_lens[i] = bitstream_read_bits(istream, - LZX_PRECODE_ELEMENT_SIZE); + d->precode_lens[i] = + bitstream_read_bits(is, LZX_PRECODE_ELEMENT_SIZE); } - /* Make the decoding table for the precode. */ - ret = make_huffman_decode_table(precode_decode_table, - LZX_PRECODE_NUM_SYMBOLS, - LZX_PRECODE_TABLEBITS, - precode_lens, - LZX_MAX_PRE_CODEWORD_LEN); - if (ret) - return ret; + /* Build the decoding table for the precode. */ + if (make_huffman_decode_table(d->precode_decode_table, + LZX_PRECODE_NUM_SYMBOLS, + LZX_PRECODE_TABLEBITS, + d->precode_lens, + LZX_MAX_PRE_CODEWORD_LEN)) + return -1; /* Decode the codeword lengths. */ do { @@ -202,8 +165,7 @@ lzx_read_codeword_lens(struct input_bitstream *istream, u8 *lens, unsigned num_l u8 len; /* Read the next precode symbol. */ - presym = read_huffsym_using_precode(istream, - precode_decode_table); + presym = read_presym(d, is); if (presym < 17) { /* Difference from old length */ len = *len_ptr - presym; @@ -217,17 +179,16 @@ lzx_read_codeword_lens(struct input_bitstream *istream, u8 *lens, unsigned num_l if (presym == 17) { /* Run of 0's */ - run_len = 4 + bitstream_read_bits(istream, 4); + run_len = 4 + bitstream_read_bits(is, 4); len = 0; } else if (presym == 18) { /* Longer run of 0's */ - run_len = 20 + bitstream_read_bits(istream, 5); + run_len = 20 + bitstream_read_bits(is, 5); len = 0; } else { /* Run of identical lengths */ - run_len = 4 + bitstream_read_bits(istream, 1); - presym = read_huffsym_using_precode(istream, - precode_decode_table); + run_len = 4 + bitstream_read_bits(is, 1); + presym = read_presym(d, is); if (unlikely(presym > 17)) return -1; len = *len_ptr - presym; @@ -238,7 +199,8 @@ lzx_read_codeword_lens(struct input_bitstream *istream, u8 *lens, unsigned num_l do { *len_ptr++ = len; } while (--run_len); - /* Worst case overrun is when presym == 18, + /* + * The worst case overrun is when presym == 18, * run_len == 20 + 31, and only 1 length was remaining. * So LZX_READ_LENS_MAX_OVERRUN == 50. * @@ -246,62 +208,41 @@ lzx_read_codeword_lens(struct input_bitstream *istream, u8 *lens, unsigned num_l * can corrupt the previous values in the second half. * This doesn't really matter because the resulting * lengths will still be in range, and data that - * generates overruns is invalid anyway. */ + * generates overruns is invalid anyway. + */ } } while (len_ptr < lens_end); + return 0; } /* - * Read the header of an LZX block and save the block type and size in - * *block_type_ret and *block_size_ret, respectively. - * - * If the block is compressed, also update the Huffman decode @tables with the - * new Huffman codes. - * - * If the block is uncompressed, also update the match offset @queue with the - * new match offsets. - * - * Return 0 on success, or -1 if the data was invalid. + * Read the header of an LZX block. For all block types, the block type and + * size is saved in *block_type_ret and *block_size_ret, respectively. For + * compressed blocks, the codeword lengths are also saved. For uncompressed + * blocks, the recent offsets queue is also updated. */ static int -lzx_read_block_header(struct input_bitstream *istream, - unsigned num_main_syms, - unsigned window_order, - int *block_type_ret, - u32 *block_size_ret, - struct lzx_tables *tables, - struct lzx_lru_queue *queue) +lzx_read_block_header(struct lzx_decompressor *d, struct input_bitstream *is, + u32 recent_offsets[], int *block_type_ret, + u32 *block_size_ret) { int block_type; u32 block_size; - int ret; - bitstream_ensure_bits(istream, 4); + bitstream_ensure_bits(is, 4); - /* The first three bits tell us what kind of block it is, and should be - * one of the LZX_BLOCKTYPE_* values. */ - block_type = bitstream_pop_bits(istream, 3); + /* Read the block type. */ + block_type = bitstream_pop_bits(is, 3); - /* Read the block size. This mirrors the behavior of - * lzx_write_compressed_block() in lzx_compress.c; see that for more - * details. */ - if (bitstream_pop_bits(istream, 1)) { + /* Read the block size. */ + if (bitstream_pop_bits(is, 1)) { block_size = LZX_DEFAULT_BLOCK_SIZE; } else { - u32 tmp; - block_size = 0; - - tmp = bitstream_read_bits(istream, 8); - block_size |= tmp; - tmp = bitstream_read_bits(istream, 8); - block_size <<= 8; - block_size |= tmp; - - if (window_order >= 16) { - tmp = bitstream_read_bits(istream, 8); + block_size = bitstream_read_bits(is, 16); + if (d->window_order >= 16) { block_size <<= 8; - block_size |= tmp; + block_size |= bitstream_read_bits(is, 8); } } @@ -309,86 +250,56 @@ lzx_read_block_header(struct input_bitstream *istream, case LZX_BLOCKTYPE_ALIGNED: - /* Read the aligned offset code and prepare its decode table. - */ + /* Read the aligned offset codeword lengths. */ for (int i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) { - tables->alignedcode_lens[i] = - bitstream_read_bits(istream, + d->alignedcode_lens[i] = + bitstream_read_bits(is, LZX_ALIGNEDCODE_ELEMENT_SIZE); } - ret = make_huffman_decode_table(tables->alignedcode_decode_table, - LZX_ALIGNEDCODE_NUM_SYMBOLS, - LZX_ALIGNEDCODE_TABLEBITS, - tables->alignedcode_lens, - LZX_MAX_ALIGNED_CODEWORD_LEN); - if (ret) - return ret; - /* Fall though, since the rest of the header for aligned offset * blocks is the same as that for verbatim blocks. */ case LZX_BLOCKTYPE_VERBATIM: - /* Read the main code and prepare its decode table. - * - * Note that the codeword lengths in the main code are encoded - * in two parts: one part for literal symbols, and one part for - * match symbols. */ - - ret = lzx_read_codeword_lens(istream, tables->maincode_lens, - LZX_NUM_CHARS); - if (ret) - return ret; - - ret = lzx_read_codeword_lens(istream, - tables->maincode_lens + LZX_NUM_CHARS, - num_main_syms - LZX_NUM_CHARS); - if (ret) - return ret; - - ret = make_huffman_decode_table(tables->maincode_decode_table, - num_main_syms, - LZX_MAINCODE_TABLEBITS, - tables->maincode_lens, - LZX_MAX_MAIN_CODEWORD_LEN); - if (ret) - return ret; - - /* Read the length code and prepare its decode table. */ - - ret = lzx_read_codeword_lens(istream, tables->lencode_lens, - LZX_LENCODE_NUM_SYMBOLS); - if (ret) - return ret; - - ret = make_huffman_decode_table(tables->lencode_decode_table, - LZX_LENCODE_NUM_SYMBOLS, - LZX_LENCODE_TABLEBITS, - tables->lencode_lens, - LZX_MAX_LEN_CODEWORD_LEN); - if (ret) - return ret; + /* Read the main codeword lengths, which are divided into two + * parts: literal symbols and match headers. */ + + if (lzx_read_codeword_lens(d, is, d->maincode_lens, + LZX_NUM_CHARS)) + return -1; + + if (lzx_read_codeword_lens(d, is, d->maincode_lens + LZX_NUM_CHARS, + d->num_main_syms - LZX_NUM_CHARS)) + return -1; + + + /* Read the length codeword lengths. */ + + if (lzx_read_codeword_lens(d, is, d->lencode_lens, + LZX_LENCODE_NUM_SYMBOLS)) + return -1; break; case LZX_BLOCKTYPE_UNCOMPRESSED: - - /* Before reading the three LRU match offsets from the - * uncompressed block header, the stream must be aligned on a - * 16-bit boundary. But, unexpectedly, if the stream is + /* + * The header of an uncompressed block contains new values for + * the recent offsets queue, starting on the next 16-bit + * boundary in the bitstream. Careful: if the stream is * *already* aligned, the correct thing to do is to throw away - * the next 16 bits. */ - - bitstream_ensure_bits(istream, 1); - bitstream_align(istream); - queue->R[0] = bitstream_read_u32(istream); - queue->R[1] = bitstream_read_u32(istream); - queue->R[2] = bitstream_read_u32(istream); + * the next 16 bits (this is probably a mistake in the format). + */ + bitstream_ensure_bits(is, 1); + bitstream_align(is); + recent_offsets[0] = bitstream_read_u32(is); + recent_offsets[1] = bitstream_read_u32(is); + recent_offsets[2] = bitstream_read_u32(is); /* Offsets of 0 are invalid. */ - if (queue->R[0] == 0 || queue->R[1] == 0 || queue->R[2] == 0) + if (recent_offsets[0] == 0 || recent_offsets[1] == 0 || + recent_offsets[2] == 0) return -1; break; @@ -402,73 +313,82 @@ lzx_read_block_header(struct input_bitstream *istream, return 0; } -/* - * Decompress a block of LZX-compressed data. - * - * @block_type: - * The type of the block (LZX_BLOCKTYPE_VERBATIM or LZX_BLOCKTYPE_ALIGNED). - * @out_begin - * The beginning of the (uncompressed) output buffer. - * @out_next - * Pointer to the location in the (uncompressed) output buffer at which - * this block will start. - * @out_block_end - * Pointer to the location in the (uncompressed) output buffer at which - * this block will end. - * @tables: - * The Huffman decoding tables for this block. - * @queue: - * The least-recently-used queue for match offsets. - * @istream: - * The input bitstream, positioned at the start of the block data. - * - * Returns 0 on success, or -1 if the data was invalid. - */ +/* Decompress a block of LZX-compressed data. */ static int -lzx_decompress_block(int block_type, u8 * const out_begin, - u8 * out_next, u8 * const out_block_end, - const struct lzx_tables *tables, - struct lzx_lru_queue *queue, - struct input_bitstream *istream) +lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, + int block_type, u32 block_size, + u8 * const out_begin, u8 *out_next, u32 recent_offsets[]) { - unsigned mainsym; - u32 match_len; - unsigned offset_slot; - u32 match_offset; - unsigned num_extra_bits; - unsigned ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED); + u8 * const block_end = out_next + block_size; + unsigned min_aligned_offset_slot; + + /* + * Build the Huffman decode tables. We always need to build the main + * and length decode tables. For aligned blocks we additionally need to + * build the aligned offset decode table. + */ - while (out_next != out_block_end) { + if (make_huffman_decode_table(d->maincode_decode_table, + d->num_main_syms, + LZX_MAINCODE_TABLEBITS, + d->maincode_lens, + LZX_MAX_MAIN_CODEWORD_LEN)) + return -1; - mainsym = read_huffsym_using_maincode(istream, tables); + if (make_huffman_decode_table(d->lencode_decode_table, + LZX_LENCODE_NUM_SYMBOLS, + LZX_LENCODE_TABLEBITS, + d->lencode_lens, + LZX_MAX_LEN_CODEWORD_LEN)) + return -1; + + if (block_type == LZX_BLOCKTYPE_ALIGNED) { + if (make_huffman_decode_table(d->alignedcode_decode_table, + LZX_ALIGNEDCODE_NUM_SYMBOLS, + LZX_ALIGNEDCODE_TABLEBITS, + d->alignedcode_lens, + LZX_MAX_ALIGNED_CODEWORD_LEN)) + return -1; + min_aligned_offset_slot = 8; + } else { + min_aligned_offset_slot = LZX_MAX_OFFSET_SLOTS; + } + + /* Decode the literals and matches. */ + + do { + unsigned mainsym; + unsigned length; + u32 offset; + unsigned offset_slot; + unsigned num_extra_bits; + + mainsym = read_mainsym(d, is); if (mainsym < LZX_NUM_CHARS) { - /* Literal */ + /* Literal */ *out_next++ = mainsym; continue; } - /* Match */ + /* Match */ /* Decode the length header and offset slot. */ - mainsym -= LZX_NUM_CHARS; - match_len = mainsym % LZX_NUM_LEN_HEADERS; - offset_slot = mainsym / LZX_NUM_LEN_HEADERS; + STATIC_ASSERT(LZX_NUM_CHARS % LZX_NUM_LEN_HEADERS == 0); + length = mainsym % LZX_NUM_LEN_HEADERS; + offset_slot = (mainsym - LZX_NUM_CHARS) / LZX_NUM_LEN_HEADERS; /* If needed, read a length symbol to decode the full length. */ - if (match_len == LZX_NUM_PRIMARY_LENS) - match_len += read_huffsym_using_lencode(istream, tables); - match_len += LZX_MIN_MATCH_LEN; + if (length == LZX_NUM_PRIMARY_LENS) + length += read_lensym(d, is); + length += LZX_MIN_MATCH_LEN; if (offset_slot < LZX_NUM_RECENT_OFFSETS) { /* Repeat offset */ /* Note: This isn't a real LRU queue, since using the R2 - * offset doesn't bump the R1 offset down to R2. This - * quirk allows all 3 recent offsets to be handled by - * the same code. (For R0, the swap is a no-op.) */ - match_offset = queue->R[offset_slot]; - queue->R[offset_slot] = queue->R[0]; - queue->R[0] = match_offset; + * offset doesn't bump the R1 offset down to R2. */ + offset = recent_offsets[offset_slot]; + recent_offsets[offset_slot] = recent_offsets[0]; } else { /* Explicit offset */ @@ -477,169 +397,144 @@ lzx_decompress_block(int block_type, u8 * const out_begin, num_extra_bits = lzx_extra_offset_bits[offset_slot]; /* Start with the offset slot base value. */ - match_offset = lzx_offset_slot_base[offset_slot]; + 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. */ - if ((num_extra_bits & ones_if_aligned) >= LZX_NUM_ALIGNED_OFFSET_BITS) { - match_offset += - bitstream_read_bits(istream, + 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; - match_offset += read_huffsym_using_alignedcode(istream, tables); + offset += read_alignedsym(d, is); } else { - match_offset += bitstream_read_bits(istream, num_extra_bits); + offset += bitstream_read_bits(is, num_extra_bits); } /* Adjust the offset. */ - match_offset -= LZX_OFFSET_ADJUSTMENT; + offset -= LZX_OFFSET_ADJUSTMENT; /* Update the match offset LRU queue. */ STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3); - queue->R[2] = queue->R[1]; - queue->R[1] = queue->R[0]; - queue->R[0] = match_offset; + recent_offsets[2] = recent_offsets[1]; + recent_offsets[1] = recent_offsets[0]; } + recent_offsets[0] = offset; /* Validate the match, then copy it to the current position. */ - if (unlikely(match_len > out_block_end - out_next)) + if (unlikely(length > block_end - out_next)) return -1; - if (unlikely(match_offset > out_next - out_begin)) + if (unlikely(offset > out_next - out_begin)) return -1; - lz_copy(out_next, match_len, match_offset, out_block_end, - LZX_MIN_MATCH_LEN); + lz_copy(out_next, length, offset, block_end, LZX_MIN_MATCH_LEN); + + out_next += length; + + } while (out_next != block_end); - out_next += match_len; - } return 0; } static int lzx_decompress(const void *restrict compressed_data, size_t compressed_size, void *restrict uncompressed_data, size_t uncompressed_size, - void *restrict _dec) + void *restrict _d) { - struct lzx_decompressor *dec = _dec; - struct input_bitstream istream; - struct lzx_lru_queue queue; + struct lzx_decompressor *d = _d; u8 * const out_begin = uncompressed_data; u8 *out_next = out_begin; u8 * const out_end = out_begin + uncompressed_size; - int block_type; - u32 block_size; - bool may_have_e8_byte; - int ret; - - init_input_bitstream(&istream, compressed_data, compressed_size); + struct input_bitstream is; + STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3); + u32 recent_offsets[LZX_NUM_RECENT_OFFSETS] = {1, 1, 1}; + unsigned may_have_e8_byte = 0; - /* Initialize the recent offsets queue. */ - lzx_lru_queue_init(&queue); + init_input_bitstream(&is, compressed_data, compressed_size); - /* Codeword lengths begin as all 0's for delta encoding purposes. */ - memset(dec->tables.maincode_lens, 0, dec->num_main_syms); - memset(dec->tables.lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS); - - /* Set this to true if there may be 0xe8 bytes in the uncompressed data. - */ - may_have_e8_byte = false; + /* Codeword lengths begin as all 0's for delta encoding purposes. */ + memset(d->maincode_lens, 0, d->num_main_syms); + memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS); - /* The compressed data will consist of one or more blocks. The - * following loop decompresses one block, and it runs until there all - * the compressed data has been decompressed, so there are no more - * blocks. */ + /* Decompress blocks until we have all the uncompressed data. */ while (out_next != out_end) { + int block_type; + u32 block_size; - ret = lzx_read_block_header(&istream, dec->num_main_syms, - dec->window_order, &block_type, - &block_size, &dec->tables, &queue); - if (ret) - return ret; - - if (block_size > out_end - out_next) + if (lzx_read_block_header(d, &is, recent_offsets, + &block_type, &block_size)) return -1; - if (block_type != LZX_BLOCKTYPE_UNCOMPRESSED) { - - /* Compressed block. */ + if (block_size < 1 || block_size > out_end - out_next) + return -1; - ret = lzx_decompress_block(block_type, - out_begin, - out_next, - out_next + block_size, - &dec->tables, - &queue, - &istream); - if (ret) - return ret; + if (likely(block_type != LZX_BLOCKTYPE_UNCOMPRESSED)) { - /* If the first 0xe8 byte was in this block, it must - * have been encoded as a literal using mainsym 0xe8. */ - if (dec->tables.maincode_lens[0xe8] != 0) - may_have_e8_byte = true; + /* Compressed block */ + if (lzx_decompress_block(d, &is, block_type, block_size, + out_begin, out_next, + recent_offsets)) + return -1; - out_next += block_size; + /* If the first E8 byte was in this block, then it must + * have been encoded as a literal using mainsym E8. */ + may_have_e8_byte |= d->maincode_lens[0xE8]; } else { - /* Uncompressed block. */ - out_next = bitstream_read_bytes(&istream, out_next, block_size); - if (!out_next) + /* Uncompressed block */ + if (bitstream_read_bytes(&is, out_next, block_size)) return -1; - /* Re-align the bitstream if an odd number of bytes was - * read. */ + /* Re-align the bitstream if needed. */ if (block_size & 1) - bitstream_read_byte(&istream); + bitstream_read_byte(&is); - may_have_e8_byte = true; + /* There may have been an E8 byte in the block. */ + may_have_e8_byte = 1; } + out_next += block_size; } - /* Postprocess the data unless it cannot possibly contain 0xe8 bytes */ + /* Postprocess the data unless it cannot possibly contain E8 bytes. */ if (may_have_e8_byte) lzx_postprocess(uncompressed_data, uncompressed_size); return 0; } -static void -lzx_free_decompressor(void *_dec) -{ - struct lzx_decompressor *dec = _dec; - - ALIGNED_FREE(dec); -} - static int -lzx_create_decompressor(size_t max_block_size, void **dec_ret) +lzx_create_decompressor(size_t max_block_size, void **d_ret) { - struct lzx_decompressor *dec; unsigned window_order; + struct lzx_decompressor *d; window_order = lzx_get_window_order(max_block_size); if (window_order == 0) return WIMLIB_ERR_INVALID_PARAM; - /* The aligned allocation is needed to ensure that the lzx_tables are - * aligned properly. */ - dec = ALIGNED_MALLOC(sizeof(struct lzx_decompressor), - DECODE_TABLE_ALIGNMENT); - if (!dec) + d = ALIGNED_MALLOC(sizeof(*d), DECODE_TABLE_ALIGNMENT); + if (!d) return WIMLIB_ERR_NOMEM; - dec->window_order = window_order; - dec->num_main_syms = lzx_get_num_main_syms(window_order); + d->window_order = window_order; + d->num_main_syms = lzx_get_num_main_syms(window_order); - *dec_ret = dec; + *d_ret = d; return 0; } +static void +lzx_free_decompressor(void *_d) +{ + ALIGNED_FREE(_d); +} + const struct decompressor_ops lzx_decompressor_ops = { .create_decompressor = lzx_create_decompressor, .decompress = lzx_decompress, -- 2.43.0