From: Eric Biggers Date: Thu, 20 Dec 2012 18:05:42 +0000 (-0600) Subject: Decompression optimizations X-Git-Tag: v1.2.2~12 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=a6f5add5e9811584ebd75591a6a25cb9686da9a8 Decompression optimizations --- diff --git a/configure.ac b/configure.ac index 03ad48a7..919d7435 100644 --- a/configure.ac +++ b/configure.ac @@ -127,6 +127,17 @@ if test "x$ENABLE_ASSERTIONS" = "xyes"; then AC_DEFINE([ENABLE_ASSERTIONS], [1], [Define to 1 if including assertions.]) fi +AC_MSG_CHECKING([whether to include more assertions]) +AC_ARG_ENABLE([more-assertions], + AS_HELP_STRING([--enable-more-assertions], [include even more assertions]), + [ENABLE_MORE_ASSERTIONS=$enableval], + [ENABLE_MORE_ASSERTIONS=no] + ) +AC_MSG_RESULT([$ENABLE_MORE_ASSERTIONS]) +if test "x$ENABLE_MORE_ASSERTIONS" = "xyes"; then + AC_DEFINE([ENABLE_MORE_ASSERTIONS], [1], [Define to 1 if including more assertions.]) +fi + AC_MSG_CHECKING([whether to include compression verification]) AC_ARG_ENABLE([verify_compression], diff --git a/src/decompress.c b/src/decompress.c index 06940331..68ab495d 100644 --- a/src/decompress.c +++ b/src/decompress.c @@ -31,7 +31,7 @@ int bitstream_read_bytes(struct input_bitstream *stream, size_t n, void *dest) { /* Precondition: The bitstream is 16-byte aligned. */ - wimlib_assert(stream->bitsleft % 16 == 0); + wimlib_assert2(stream->bitsleft % 16 == 0); u8 *p = dest; @@ -68,34 +68,6 @@ int bitstream_read_bytes(struct input_bitstream *stream, size_t n, void *dest) return 0; } -/* Aligns the bitstream on a 16-bit boundary. - * - * Note: M$'s idea of "alignment" means that for some reason, a 16-bit word - * should be skipped over if the buffer happens to already be aligned on such a - * boundary. This only applies for realigning the stream after the blocktype - * and length fields of an uncompressed block, however; it does not apply when - * realigning the stream after the end of the uncompressed block. - */ -int align_input_bitstream(struct input_bitstream *stream, - bool skip_word_if_aligned) -{ - int ret; - if (stream->bitsleft % 16 != 0) { - bitstream_remove_bits(stream, stream->bitsleft % 16); - } else if (skip_word_if_aligned) { - if (stream->bitsleft == 0) { - ret = bitstream_ensure_bits(stream, 16); - if (ret != 0) { - ERROR("Unexpected end of input when " - "aligning bitstream"); - return ret; - } - } - bitstream_remove_bits(stream, 16); - } - return 0; -} - /* * Builds a fast huffman decoding table from a canonical huffman code lengths * table. Based on code written by David Tritscher. @@ -329,12 +301,12 @@ int make_huffman_decode_table(u16 decode_table[], unsigned num_syms, /* Reads a Huffman-encoded symbol when it is known there are less than * MAX_CODE_LEN bits remaining in the bitstream. */ -static int read_huffsym_near_end_of_input(struct input_bitstream *istream, - const u16 decode_table[], - const u8 lens[], - unsigned num_syms, - unsigned table_bits, - unsigned *n) +int read_huffsym_near_end_of_input(struct input_bitstream *istream, + const u16 decode_table[], + const u8 lens[], + unsigned num_syms, + unsigned table_bits, + unsigned *n) { unsigned bitsleft = istream->bitsleft; unsigned key_size; @@ -370,65 +342,3 @@ static int read_huffsym_near_end_of_input(struct input_bitstream *istream, *n = sym; return 0; } - -/* - * Reads a Huffman-encoded symbol from a bitstream. - * - * This function may be called hundreds of millions of times when extracting a - * large WIM file. I'm not sure it could be made much faster that it is, - * especially since there isn't enough time to make a big table that allows - * decoding multiple symbols per lookup. But if extracting files to a hard - * disk, the IO will be the bottleneck anyway. - * - * @buf: The input buffer from which the symbol will be read. - * @decode_table: The fast Huffman decoding table for the Huffman tree. - * @lengths: The table that gives the length of the code for each - * symbol. - * @num_symbols: The number of symbols in the Huffman code. - * @table_bits: Huffman codes this length or less can be looked up - * directory in the decode_table, as the - * decode_table contains 2**table_bits entries. - */ -int read_huffsym(struct input_bitstream *stream, - const u16 decode_table[], - const u8 lengths[], - unsigned num_symbols, - unsigned table_bits, - unsigned *n, - unsigned max_codeword_len) -{ - /* In the most common case, there are at least max_codeword_len bits - * remaining in the stream. */ - if (bitstream_ensure_bits(stream, max_codeword_len) == 0) { - - /* Use the next table_bits of the input as an index into the - * decode_table. */ - u16 key_bits = bitstream_peek_bits(stream, table_bits); - - u16 sym = decode_table[key_bits]; - - /* If the entry in the decode table is not a valid symbol, it is - * the offset of the root of its Huffman subtree. */ - if (sym >= num_symbols) { - bitstream_remove_bits(stream, table_bits); - do { - key_bits = sym + bitstream_peek_bits(stream, 1); - bitstream_remove_bits(stream, 1); - - wimlib_assert(key_bits < num_symbols * 2 + - (1 << table_bits)); - } while ((sym = decode_table[key_bits]) >= num_symbols); - } else { - wimlib_assert(lengths[sym] <= table_bits); - bitstream_remove_bits(stream, lengths[sym]); - } - *n = sym; - return 0; - } else { - /* Otherwise, we must be careful to use only the bits that are - * actually remaining. */ - return read_huffsym_near_end_of_input(stream, decode_table, - lengths, num_symbols, - table_bits, n); - } -} diff --git a/src/decompress.h b/src/decompress.h index b4c45795..ae1c99be 100644 --- a/src/decompress.h +++ b/src/decompress.h @@ -45,7 +45,9 @@ static inline void init_input_bitstream(struct input_bitstream *istream, static inline int bitstream_ensure_bits(struct input_bitstream *istream, unsigned num_bits) { - wimlib_assert(num_bits <= 16); + wimlib_assert2(num_bits <= 16); + + int ret = 0; /* Unfortunately this needs to be different for the different * compression types. LZX requires reading no more than the number of @@ -55,22 +57,24 @@ static inline int bitstream_ensure_bits(struct input_bitstream *istream, * important because this may change the location of a literal byte * read with bitstream_read_byte(). */ #ifdef XPRESS_DECOMP - while (istream->bitsleft < 16) { + if (istream->bitsleft < 16) { #else - while (istream->bitsleft < num_bits) { + if (istream->bitsleft < num_bits) { #endif - if (istream->data_bytes_left < 2) - return 1; - - unsigned shift = sizeof(input_bitbuf_t) * 8 - 16 - - istream->bitsleft; - istream->bitbuf |= (input_bitbuf_t)le16_to_cpu( - *(u16*)istream->data) << shift; - istream->data += 2; - istream->bitsleft += 16; - istream->data_bytes_left -= 2; + if (istream->data_bytes_left >= 2) { + unsigned shift = sizeof(input_bitbuf_t) * 8 - 16 - + istream->bitsleft; + istream->bitbuf |= (input_bitbuf_t)le16_to_cpu( + *(u16*)istream->data) << shift; + istream->data += 2; + istream->bitsleft += 16; + istream->data_bytes_left -= 2; + } else { + ret = 1; + } } - return 0; + wimlib_assert2(ret != 0 || istream->bitsleft >= num_bits); + return ret; } /* Returns the next @num_bits bits in the bit buffer. It must contain at least @@ -78,9 +82,13 @@ static inline int bitstream_ensure_bits(struct input_bitstream *istream, static inline unsigned bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits) { + wimlib_assert2(istream->bitsleft >= num_bits); + int ret; if (num_bits == 0) - return 0; - return istream->bitbuf >> (sizeof(input_bitbuf_t) * 8 - num_bits); + ret = 0; + else + ret = istream->bitbuf >> (sizeof(input_bitbuf_t) * 8 - num_bits); + return ret; } /* Removes @num_bits bits from the bit buffer. It must contain at least @@ -88,6 +96,7 @@ bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits) static inline void bitstream_remove_bits(struct input_bitstream *istream, unsigned num_bits) { + wimlib_assert2(istream->bitsleft >= num_bits); istream->bitbuf <<= num_bits; istream->bitsleft -= num_bits; } @@ -96,15 +105,14 @@ static inline void bitstream_remove_bits(struct input_bitstream *istream, static inline int bitstream_read_bits(struct input_bitstream *istream, unsigned num_bits, unsigned *n) { - int ret; - ret = bitstream_ensure_bits(istream, num_bits); - if (ret != 0) { + int ret = bitstream_ensure_bits(istream, num_bits); + if (ret == 0) { + *n = bitstream_peek_bits(istream, num_bits); + bitstream_remove_bits(istream, num_bits); + } else { ERROR("bitstream_read_bits(): Input buffer exhausted"); - return ret; } - *n = bitstream_peek_bits(istream, num_bits); - bitstream_remove_bits(istream, num_bits); - return 0; + return ret; } /* In the XPRESS format there can be literal length bytes embedded in the @@ -117,14 +125,17 @@ static inline int bitstream_read_bits(struct input_bitstream *istream, * bitstream. Returns -1 if we are at the end of the bitstream. */ static inline int bitstream_read_byte(struct input_bitstream *istream) { - wimlib_assert(istream->bitsleft < 32); + wimlib_assert2(istream->bitsleft < 32); + int ret; if (istream->data_bytes_left == 0) { ERROR("bitstream_read_byte(): Input buffer exhausted"); - return -1; + ret = -1; + } else { + istream->data_bytes_left--; + ret = *istream->data++; } - istream->data_bytes_left--; - return *istream->data++; + return ret; } /* Reads @num_bits bits from the bit buffer without checking to see if that many @@ -141,23 +152,90 @@ bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits) static inline void flush_input_bitstream(struct input_bitstream *istream) { bitstream_remove_bits(istream, istream->bitsleft); - istream->bitsleft = 0; istream->bitbuf = 0; + wimlib_assert2(istream->bitsleft == 0); } extern int bitstream_read_bytes(struct input_bitstream *istream, size_t n, void *dest); -extern int align_input_bitstream(struct input_bitstream *istream, - bool skip_word_if_aligned); +/* Aligns the bitstream on a 16-bit boundary. */ +static inline void align_input_bitstream(struct input_bitstream *istream) +{ + bitstream_remove_bits(istream, istream->bitsleft & 15); +} -extern int read_huffsym(struct input_bitstream *stream, - const u16 decode_table[], - const u8 lengths[], - unsigned num_symbols, - unsigned table_bits, - unsigned *n, - unsigned max_codeword_len); +extern int read_huffsym_near_end_of_input(struct input_bitstream *istream, + const u16 decode_table[], + const u8 lens[], + unsigned num_syms, + unsigned table_bits, + unsigned *n); + +/* + * Reads a Huffman-encoded symbol from a bitstream. + * + * This function may be called hundreds of millions of times when extracting a + * large WIM file. I'm not sure it could be made much faster that it is, + * especially since there isn't enough time to make a big table that allows + * decoding multiple symbols per lookup. But if extracting files to a hard + * disk, the IO will be the bottleneck anyway. + * + * @buf: The input buffer from which the symbol will be read. + * @decode_table: The fast Huffman decoding table for the Huffman tree. + * @lengths: The table that gives the length of the code for each + * symbol. + * @num_symbols: The number of symbols in the Huffman code. + * @table_bits: Huffman codes this length or less can be looked up + * directory in the decode_table, as the + * decode_table contains 2**table_bits entries. + */ +static inline int read_huffsym(struct input_bitstream *istream, + const u16 decode_table[], + const u8 lens[], + unsigned num_syms, + unsigned table_bits, + unsigned *n, + unsigned max_codeword_len) +{ + int ret; + + /* In the most common case, there are at least max_codeword_len bits + * remaining in the stream. */ + if (bitstream_ensure_bits(istream, max_codeword_len) == 0) { + + /* Use the next table_bits of the input as an index into the + * decode_table. */ + u16 key_bits = bitstream_peek_bits(istream, table_bits); + + u16 sym = decode_table[key_bits]; + + /* If the entry in the decode table is not a valid symbol, it is + * the offset of the root of its Huffman subtree. */ + if (sym >= num_syms) { + bitstream_remove_bits(istream, table_bits); + do { + key_bits = sym + bitstream_peek_bits(istream, 1); + bitstream_remove_bits(istream, 1); + + wimlib_assert2(key_bits < num_syms * 2 + + (1 << table_bits)); + } while ((sym = decode_table[key_bits]) >= num_syms); + } else { + wimlib_assert2(lens[sym] <= table_bits); + bitstream_remove_bits(istream, lens[sym]); + } + *n = sym; + ret = 0; + } else { + /* Otherwise, we must be careful to use only the bits that are + * actually remaining. */ + ret = read_huffsym_near_end_of_input(istream, decode_table, + lens, num_syms, + table_bits, n); + } + return ret; +} extern int make_huffman_decode_table(u16 decode_table[], unsigned num_syms, unsigned num_bits, const u8 lengths[], diff --git a/src/lzx-decompress.c b/src/lzx-decompress.c index 6e4098ff..a66e6d8b 100644 --- a/src/lzx-decompress.c +++ b/src/lzx-decompress.c @@ -443,9 +443,12 @@ static int lzx_read_block_header(struct input_bitstream *istream, case LZX_BLOCKTYPE_UNCOMPRESSED: LZX_DEBUG("Found uncompressed block."); - ret = align_input_bitstream(istream, true); + + /* Mystery bit! */ + ret = bitstream_read_bits(istream, 1, &i); if (ret != 0) return ret; + align_input_bitstream(istream); ret = bitstream_read_bytes(istream, sizeof(R), R); if (ret != 0) return ret; @@ -826,7 +829,7 @@ int lzx_decompress(const void *compressed_data, unsigned compressed_len, if (ret != 0) return ret; if (block_size & 1) - align_input_bitstream(&istream, false); + align_input_bitstream(&istream); break; default: wimlib_assert(0); diff --git a/src/lzx.h b/src/lzx.h index 42ae5ce5..ab158d86 100644 --- a/src/lzx.h +++ b/src/lzx.h @@ -49,10 +49,10 @@ #define LZX_MAINTREE_NUM_SYMBOLS (LZX_NUM_CHARS + \ (LZX_NUM_POSITION_SLOTS << 3)) -#define LZX_MAINTREE_TABLEBITS 12 +#define LZX_MAINTREE_TABLEBITS 11 #define LZX_LENTREE_NUM_SYMBOLS 249 -#define LZX_LENTREE_TABLEBITS 12 +#define LZX_LENTREE_TABLEBITS 10 #define LZX_PRETREE_NUM_SYMBOLS 20 #define LZX_PRETREE_TABLEBITS 6 diff --git a/src/util.h b/src/util.h index 15c68bc0..b97731b5 100644 --- a/src/util.h +++ b/src/util.h @@ -131,6 +131,12 @@ extern void wimlib_warning(const char *format, ...) # define wimlib_assert(expr) #endif +#ifdef ENABLE_MORE_ASSERTIONS +#define wimlib_assert2(expr) wimlib_assert(expr) +#else +#define wimlib_assert2(expr) +#endif + #ifdef ENABLE_CUSTOM_MEMORY_ALLOCATOR extern void *(*wimlib_malloc_func)(size_t);