Decompression optimizations
authorEric Biggers <ebiggers3@gmail.com>
Thu, 20 Dec 2012 18:05:42 +0000 (12:05 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Thu, 20 Dec 2012 18:05:42 +0000 (12:05 -0600)
configure.ac
src/decompress.c
src/decompress.h
src/lzx-decompress.c
src/lzx.h
src/util.h

index 03ad48a76ac295ec00f19a55c3ebee117311574d..919d743590b4db2841e00396daa32d36aacc2164 100644 (file)
@@ -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],
index 069403314a0c886d70e52892897c3151ce322f0a..68ab495dac0cabc3aeb60844b55da40aa2f4b3dd 100644 (file)
@@ -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);
-       }
-}
index b4c4579543bbe59b6b57f58704689fc28216582d..ae1c99becda88f81e77146d3957683d65743b575 100644 (file)
@@ -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[],
index 6e4098fffa1c218aae813ec30f558683be4a5df2..a66e6d8b2126384880ca943fb2979141a4182340 100644 (file)
@@ -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);
index 42ae5ce5c51b1198e8af3fa4d0366972b50079ca..ab158d866d21a705fcec9a5f23bcccff837dd90c 100644 (file)
--- a/src/lzx.h
+++ b/src/lzx.h
 
 #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
index 15c68bc022f0d0e775267ccc03b850ea3abe5026..b97731b56730936c68077197a60fe6125fa141a4 100644 (file)
@@ -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);