X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzx_decompress.c;h=a8fbcd7d5e8325542537730ec7fef328754c53a8;hp=57b32890b7813bc57aa7faa3f8d7cae9fd95e4ab;hb=5343bde03c158cc767b1a347a7323d0e33c78d41;hpb=40a690416a3951361ec77d33a723dd4497fb7585 diff --git a/src/lzx_decompress.c b/src/lzx_decompress.c index 57b32890..a8fbcd7d 100644 --- a/src/lzx_decompress.c +++ b/src/lzx_decompress.c @@ -5,7 +5,7 @@ */ /* - * Copyright (C) 2012, 2013, 2014 Eric Biggers + * Copyright (C) 2012, 2013, 2014, 2015 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 @@ -54,14 +54,14 @@ # include "config.h" #endif +#include + #include "wimlib/decompressor_ops.h" #include "wimlib/decompress_common.h" #include "wimlib/error.h" #include "wimlib/lzx_common.h" #include "wimlib/util.h" -#include - /* These values are chosen for fast decompression. */ #define LZX_MAINCODE_TABLEBITS 11 #define LZX_LENCODE_TABLEBITS 10 @@ -91,6 +91,18 @@ struct lzx_tables { 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; +} + /* The main LZX decompressor structure. * * Note: we keep track of most of the decompression state outside this @@ -104,7 +116,7 @@ struct lzx_decompressor { }; /* Read a Huffman-encoded symbol using the precode. */ -static inline u16 +static inline unsigned read_huffsym_using_precode(struct input_bitstream *istream, const u16 precode_decode_table[]) { @@ -113,7 +125,7 @@ read_huffsym_using_precode(struct input_bitstream *istream, } /* Read a Huffman-encoded symbol using the main code. */ -static inline u16 +static inline unsigned read_huffsym_using_maincode(struct input_bitstream *istream, const struct lzx_tables *tables) { @@ -122,7 +134,7 @@ read_huffsym_using_maincode(struct input_bitstream *istream, } /* Read a Huffman-encoded symbol using the length code. */ -static inline u16 +static inline unsigned read_huffsym_using_lencode(struct input_bitstream *istream, const struct lzx_tables *tables) { @@ -131,7 +143,7 @@ read_huffsym_using_lencode(struct input_bitstream *istream, } /* Read a Huffman-encoded symbol using the aligned offset code. */ -static inline u16 +static inline unsigned read_huffsym_using_alignedcode(struct input_bitstream *istream, const struct lzx_tables *tables) { @@ -216,6 +228,8 @@ lzx_read_codeword_lens(struct input_bitstream *istream, u8 *lens, unsigned num_l run_len = 4 + bitstream_read_bits(istream, 1); presym = read_huffsym_using_precode(istream, precode_decode_table); + if (unlikely(presym > 17)) + return -1; len = *len_ptr - presym; if ((s8)len < 0) len += 17; @@ -389,40 +403,34 @@ lzx_read_block_header(struct input_bitstream *istream, } /* - * Decompress an LZX-compressed block of data. + * Decompress a block of LZX-compressed data. * * @block_type: * The type of the block (LZX_BLOCKTYPE_VERBATIM or LZX_BLOCKTYPE_ALIGNED). - * - * @block_size: - * The size of the block, in bytes. - * - * @window: - * Pointer to the beginning of the decompression window. - * - * @window_pos: - * The position in the window at which the block starts. - * + * @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 the block. - * + * 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. */ static int -lzx_decompress_block(int block_type, u32 block_size, - u8 *window, u32 window_pos, +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) { - u8 *window_ptr = &window[window_pos]; - u8 *window_end = window_ptr + block_size; unsigned mainsym; u32 match_len; unsigned offset_slot; @@ -430,12 +438,12 @@ lzx_decompress_block(int block_type, u32 block_size, unsigned num_extra_bits; unsigned ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED); - while (window_ptr != window_end) { + while (out_next != out_block_end) { mainsym = read_huffsym_using_maincode(istream, tables); if (mainsym < LZX_NUM_CHARS) { /* Literal */ - *window_ptr++ = mainsym; + *out_next++ = mainsym; continue; } @@ -443,15 +451,15 @@ lzx_decompress_block(int block_type, u32 block_size, /* Decode the length header and offset slot. */ mainsym -= LZX_NUM_CHARS; - match_len = mainsym & 0x7; - offset_slot = mainsym >> 3; + match_len = mainsym % LZX_NUM_LEN_HEADERS; + offset_slot = mainsym / LZX_NUM_LEN_HEADERS; /* If needed, read a length symbol to decode the full length. */ - if (match_len == 0x7) + if (match_len == LZX_NUM_PRIMARY_LENS) match_len += read_huffsym_using_lencode(istream, tables); match_len += LZX_MIN_MATCH_LEN; - if (offset_slot <= 2) { + if (offset_slot < LZX_NUM_RECENT_OFFSETS) { /* Repeat offset */ /* Note: This isn't a real LRU queue, since using the R2 @@ -475,18 +483,22 @@ lzx_decompress_block(int block_type, u32 block_size, * each offset are encoded using the aligned offset * code. Otherwise, all the extra bits are literal. */ - /*if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3) {*/ - if ((num_extra_bits & ones_if_aligned) >= 3) { - match_offset += bitstream_read_bits(istream, num_extra_bits - 3) << 3; + if ((num_extra_bits & ones_if_aligned) >= LZX_NUM_ALIGNED_OFFSET_BITS) { + match_offset += + bitstream_read_bits(istream, + num_extra_bits - + LZX_NUM_ALIGNED_OFFSET_BITS) + << LZX_NUM_ALIGNED_OFFSET_BITS; match_offset += read_huffsym_using_alignedcode(istream, tables); } else { match_offset += bitstream_read_bits(istream, num_extra_bits); } /* Adjust the offset. */ - match_offset -= LZX_OFFSET_OFFSET; + match_offset -= LZX_OFFSET_ADJUSTMENT; /* Update the match offset LRU queue. */ + BUILD_BUG_ON(LZX_NUM_RECENT_OFFSETS != 3); queue->R[2] = queue->R[1]; queue->R[1] = queue->R[0]; queue->R[0] = match_offset; @@ -494,29 +506,31 @@ lzx_decompress_block(int block_type, u32 block_size, /* Validate the match, then copy it to the current position. */ - if (unlikely(match_len > window_end - window_ptr)) + if (unlikely(match_len > out_block_end - out_next)) return -1; - if (unlikely(match_offset > window_ptr - window)) + if (unlikely(match_offset > out_next - out_begin)) return -1; - lz_copy(window_ptr, match_len, match_offset, window_end, + lz_copy(out_next, match_len, match_offset, out_block_end, LZX_MIN_MATCH_LEN); - window_ptr += match_len; + out_next += match_len; } return 0; } static int -lzx_decompress(const void *compressed_data, size_t compressed_size, - void *uncompressed_data, size_t uncompressed_size, - void *_dec) +lzx_decompress(const void *restrict compressed_data, size_t compressed_size, + void *restrict uncompressed_data, size_t uncompressed_size, + void *restrict _dec) { struct lzx_decompressor *dec = _dec; struct input_bitstream istream; struct lzx_lru_queue queue; - u32 window_pos; + 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; @@ -540,17 +554,15 @@ lzx_decompress(const void *compressed_data, size_t compressed_size, * the compressed data has been decompressed, so there are no more * blocks. */ - for (window_pos = 0; - window_pos < uncompressed_size; - window_pos += block_size) - { + while (out_next != out_end) { + 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 > uncompressed_size - window_pos) + if (block_size > out_end - out_next) return -1; if (block_type != LZX_BLOCKTYPE_UNCOMPRESSED) { @@ -558,9 +570,9 @@ lzx_decompress(const void *compressed_data, size_t compressed_size, /* Compressed block. */ ret = lzx_decompress_block(block_type, - block_size, - uncompressed_data, - window_pos, + out_begin, + out_next, + out_next + block_size, &dec->tables, &queue, &istream); @@ -571,17 +583,15 @@ lzx_decompress(const void *compressed_data, size_t compressed_size, * have been encoded as a literal using mainsym 0xe8. */ if (dec->tables.maincode_lens[0xe8] != 0) may_have_e8_byte = true; + + out_next += block_size; } else { /* Uncompressed block. */ - const u8 *p; - - p = bitstream_read_bytes(&istream, block_size); - if (!p) + out_next = bitstream_read_bytes(&istream, out_next, block_size); + if (!out_next) return -1; - memcpy(&((u8*)uncompressed_data)[window_pos], p, block_size); - /* Re-align the bitstream if an odd number of bytes was * read. */ if (block_size & 1)