lzx_decompress: decompressor cleanup
authorEric Biggers <ebiggers3@gmail.com>
Sat, 9 Jul 2016 15:01:16 +0000 (10:01 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Sat, 9 Jul 2016 15:01:16 +0000 (10:01 -0500)
include/wimlib/decompress_common.h
src/lzx_decompress.c

index a06ede1..c301647 100644 (file)
@@ -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.  */
index 9a03075..36d94eb 100644 (file)
@@ -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,