LZMS: decompression optimizations
authorEric Biggers <ebiggers3@gmail.com>
Fri, 26 Dec 2014 16:56:16 +0000 (10:56 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 26 Dec 2014 17:08:37 +0000 (11:08 -0600)
NEWS
include/wimlib/compiler-gcc.h
include/wimlib/compiler.h
include/wimlib/lzms.h
include/wimlib/lzms_constants.h
src/lzms-common.c
src/lzms-compress.c
src/lzms-decompress.c

diff --git a/NEWS b/NEWS
index ff832a5..b5f7be5 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -7,9 +7,7 @@ Version 1.7.4-BETA:
        Extracting files to a Windows PE in-memory filesystem no longer fails if
        the target files do not yet exist.
 
-       Made more improvements to compression and decompression.  Most notable
-       is about 10% faster XPRESS compression with a tiny improvement in
-       compression ratio.
+       Improved the performance of XPRESS compression and LZMS decompression.
 
        Removed the --with-imagex-progname and --enable-more-assertions
        configure options.
index db6e324..4698330 100644 (file)
@@ -25,6 +25,7 @@
 #endif
 #define _malloc_attribute      __attribute__((malloc))
 #define inline                 inline __attribute__((always_inline))
+#define noinline               __attribute__((noinline))
 
 #define CPU_IS_BIG_ENDIAN      (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
 
index a1f513f..11eaa23 100644 (file)
 #  define _format_attribute(type, format_str, format_start)
 #endif
 
+#ifndef noinline
+#  define noinline
+#endif
+
 #ifndef CPU_IS_BIG_ENDIAN
 #  error "missing required definition of CPU_IS_BIG_ENDIAN"
 #endif
index 94bcba8..91a0e1b 100644 (file)
@@ -7,8 +7,9 @@
 #ifndef _WIMLIB_LZMS_H
 #define _WIMLIB_LZMS_H
 
+#include "wimlib/compiler.h"
 #include "wimlib/lzms_constants.h"
-#include "wimlib/util.h"
+#include "wimlib/types.h"
 
 //#define ENABLE_LZMS_DEBUG
 #ifdef ENABLE_LZMS_DEBUG
@@ -40,49 +41,13 @@ struct lzms_probability_entry {
        u64 recent_bits;
 };
 
-/* LRU queues for LZ matches.  */
-struct lzms_lz_lru_queues {
-
-        /* Recent LZ match offsets  */
-       u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
-
-        /* These variables are used to delay updates to the LRU queues by one
-         * decoded item.  */
-       u32 prev_offset;
-       u32 upcoming_offset;
-};
-
-/* LRU queues for delta matches.  */
-struct lzms_delta_lru_queues {
-
-        /* Recent delta match powers and offsets  */
-       u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
-       u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
-
-        /* These variables are used to delay updates to the LRU queues by one
-         * decoded item.  */
-       u32 prev_power;
-       u32 prev_offset;
-       u32 upcoming_power;
-       u32 upcoming_offset;
-};
-
-/* LRU (least-recently-used) queues for match information.  */
-struct lzms_lru_queues {
-        struct lzms_lz_lru_queues lz;
-        struct lzms_delta_lru_queues delta;
-};
-
 /* Offset slot tables  */
-extern u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
-extern u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
+extern const u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
+extern const u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
 
 /* Length slot tables  */
-extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
-extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
-
-extern void
-lzms_init_slots(void);
+extern const u32 lzms_length_slot_base[LZMS_NUM_LENGTH_SYMS + 1];
+extern const u8 lzms_extra_length_bits[LZMS_NUM_LENGTH_SYMS];
 
 extern unsigned
 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
@@ -98,26 +63,17 @@ lzms_get_offset_slot(u32 offset)
 static inline unsigned
 lzms_get_length_slot(u32 length)
 {
-       return lzms_get_slot(length, lzms_length_slot_base, LZMS_NUM_LEN_SYMS);
+       return lzms_get_slot(length, lzms_length_slot_base, LZMS_NUM_LENGTH_SYMS);
 }
 
-extern void
-lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz);
-
-extern void
-lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta);
-
-extern void
-lzms_init_lru_queues(struct lzms_lru_queues *lru);
-
-extern void
-lzms_update_lz_lru_queue(struct lzms_lz_lru_queues *lz);
+extern unsigned
+lzms_get_num_offset_slots(size_t uncompressed_size);
 
 extern void
-lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
+lzms_init_probability_entries(struct lzms_probability_entry *entries, size_t count);
 
 extern void
-lzms_update_lru_queues(struct lzms_lru_queues *lru);
+lzms_init_symbol_frequencies(u32 freqs[], size_t num_syms);
 
 /* Given a decoded bit, update the probability entry.  */
 static inline void
index 7f87290..aa22aaf 100644 (file)
@@ -7,6 +7,11 @@
 #ifndef _LZMS_CONSTANTS_H
 #define _LZMS_CONSTANTS_H
 
+#define LZMS_MIN_MATCH_LEN                     1
+#define LZMS_MAX_MATCH_LEN                     1073809578
+#define LZMS_MAX_MATCH_OFFSET                  1180427428
+#define LZMS_MAX_BUFFER_SIZE                   (LZMS_MAX_MATCH_OFFSET + 1)
+
 #define LZMS_NUM_RECENT_OFFSETS                        3
 #define LZMS_MAX_INIT_RECENT_OFFSET            (LZMS_NUM_RECENT_OFFSETS + 1)
 #define LZMS_OFFSET_OFFSET                     (LZMS_NUM_RECENT_OFFSETS - 1)
@@ -25,7 +30,7 @@
 #define LZMS_MAX_NUM_STATES                    64
 
 #define LZMS_NUM_LITERAL_SYMS                  256
-#define LZMS_NUM_LEN_SYMS                      54
+#define LZMS_NUM_LENGTH_SYMS                   54
 #define LZMS_NUM_DELTA_POWER_SYMS              8
 #define LZMS_MAX_NUM_OFFSET_SYMS               799
 #define LZMS_MAX_NUM_SYMS                      799
index ee47990..eaa237f 100644 (file)
 #  include "config.h"
 #endif
 
-#include "wimlib/bitops.h"
 #include "wimlib/endianness.h"
 #include "wimlib/lzms.h"
 #include "wimlib/unaligned.h"
-#include "wimlib/util.h"
-
-#include <pthread.h>
-
-/***************************************************************
- * Constant tables initialized by lzms_compute_slots():        *
- ***************************************************************/
 
 /* Table: offset slot => offset slot base value  */
-u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
+const u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1] = {
+       0x00000001, 0x00000002, 0x00000003, 0x00000004,
+       0x00000005, 0x00000006, 0x00000007, 0x00000008,
+       0x00000009, 0x0000000d, 0x00000011, 0x00000015,
+       0x00000019, 0x0000001d, 0x00000021, 0x00000025,
+       0x00000029, 0x0000002d, 0x00000035, 0x0000003d,
+       0x00000045, 0x0000004d, 0x00000055, 0x0000005d,
+       0x00000065, 0x00000075, 0x00000085, 0x00000095,
+       0x000000a5, 0x000000b5, 0x000000c5, 0x000000d5,
+       0x000000e5, 0x000000f5, 0x00000105, 0x00000125,
+       0x00000145, 0x00000165, 0x00000185, 0x000001a5,
+       0x000001c5, 0x000001e5, 0x00000205, 0x00000225,
+       0x00000245, 0x00000265, 0x00000285, 0x000002a5,
+       0x000002c5, 0x000002e5, 0x00000325, 0x00000365,
+       0x000003a5, 0x000003e5, 0x00000425, 0x00000465,
+       0x000004a5, 0x000004e5, 0x00000525, 0x00000565,
+       0x000005a5, 0x000005e5, 0x00000625, 0x00000665,
+       0x000006a5, 0x00000725, 0x000007a5, 0x00000825,
+       0x000008a5, 0x00000925, 0x000009a5, 0x00000a25,
+       0x00000aa5, 0x00000b25, 0x00000ba5, 0x00000c25,
+       0x00000ca5, 0x00000d25, 0x00000da5, 0x00000e25,
+       0x00000ea5, 0x00000f25, 0x00000fa5, 0x00001025,
+       0x000010a5, 0x000011a5, 0x000012a5, 0x000013a5,
+       0x000014a5, 0x000015a5, 0x000016a5, 0x000017a5,
+       0x000018a5, 0x000019a5, 0x00001aa5, 0x00001ba5,
+       0x00001ca5, 0x00001da5, 0x00001ea5, 0x00001fa5,
+       0x000020a5, 0x000021a5, 0x000022a5, 0x000023a5,
+       0x000024a5, 0x000026a5, 0x000028a5, 0x00002aa5,
+       0x00002ca5, 0x00002ea5, 0x000030a5, 0x000032a5,
+       0x000034a5, 0x000036a5, 0x000038a5, 0x00003aa5,
+       0x00003ca5, 0x00003ea5, 0x000040a5, 0x000042a5,
+       0x000044a5, 0x000046a5, 0x000048a5, 0x00004aa5,
+       0x00004ca5, 0x00004ea5, 0x000050a5, 0x000052a5,
+       0x000054a5, 0x000056a5, 0x000058a5, 0x00005aa5,
+       0x00005ca5, 0x00005ea5, 0x000060a5, 0x000064a5,
+       0x000068a5, 0x00006ca5, 0x000070a5, 0x000074a5,
+       0x000078a5, 0x00007ca5, 0x000080a5, 0x000084a5,
+       0x000088a5, 0x00008ca5, 0x000090a5, 0x000094a5,
+       0x000098a5, 0x00009ca5, 0x0000a0a5, 0x0000a4a5,
+       0x0000a8a5, 0x0000aca5, 0x0000b0a5, 0x0000b4a5,
+       0x0000b8a5, 0x0000bca5, 0x0000c0a5, 0x0000c4a5,
+       0x0000c8a5, 0x0000cca5, 0x0000d0a5, 0x0000d4a5,
+       0x0000d8a5, 0x0000dca5, 0x0000e0a5, 0x0000e4a5,
+       0x0000eca5, 0x0000f4a5, 0x0000fca5, 0x000104a5,
+       0x00010ca5, 0x000114a5, 0x00011ca5, 0x000124a5,
+       0x00012ca5, 0x000134a5, 0x00013ca5, 0x000144a5,
+       0x00014ca5, 0x000154a5, 0x00015ca5, 0x000164a5,
+       0x00016ca5, 0x000174a5, 0x00017ca5, 0x000184a5,
+       0x00018ca5, 0x000194a5, 0x00019ca5, 0x0001a4a5,
+       0x0001aca5, 0x0001b4a5, 0x0001bca5, 0x0001c4a5,
+       0x0001cca5, 0x0001d4a5, 0x0001dca5, 0x0001e4a5,
+       0x0001eca5, 0x0001f4a5, 0x0001fca5, 0x000204a5,
+       0x00020ca5, 0x000214a5, 0x00021ca5, 0x000224a5,
+       0x000234a5, 0x000244a5, 0x000254a5, 0x000264a5,
+       0x000274a5, 0x000284a5, 0x000294a5, 0x0002a4a5,
+       0x0002b4a5, 0x0002c4a5, 0x0002d4a5, 0x0002e4a5,
+       0x0002f4a5, 0x000304a5, 0x000314a5, 0x000324a5,
+       0x000334a5, 0x000344a5, 0x000354a5, 0x000364a5,
+       0x000374a5, 0x000384a5, 0x000394a5, 0x0003a4a5,
+       0x0003b4a5, 0x0003c4a5, 0x0003d4a5, 0x0003e4a5,
+       0x0003f4a5, 0x000404a5, 0x000414a5, 0x000424a5,
+       0x000434a5, 0x000444a5, 0x000454a5, 0x000464a5,
+       0x000474a5, 0x000484a5, 0x000494a5, 0x0004a4a5,
+       0x0004b4a5, 0x0004c4a5, 0x0004e4a5, 0x000504a5,
+       0x000524a5, 0x000544a5, 0x000564a5, 0x000584a5,
+       0x0005a4a5, 0x0005c4a5, 0x0005e4a5, 0x000604a5,
+       0x000624a5, 0x000644a5, 0x000664a5, 0x000684a5,
+       0x0006a4a5, 0x0006c4a5, 0x0006e4a5, 0x000704a5,
+       0x000724a5, 0x000744a5, 0x000764a5, 0x000784a5,
+       0x0007a4a5, 0x0007c4a5, 0x0007e4a5, 0x000804a5,
+       0x000824a5, 0x000844a5, 0x000864a5, 0x000884a5,
+       0x0008a4a5, 0x0008c4a5, 0x0008e4a5, 0x000904a5,
+       0x000924a5, 0x000944a5, 0x000964a5, 0x000984a5,
+       0x0009a4a5, 0x0009c4a5, 0x0009e4a5, 0x000a04a5,
+       0x000a24a5, 0x000a44a5, 0x000a64a5, 0x000aa4a5,
+       0x000ae4a5, 0x000b24a5, 0x000b64a5, 0x000ba4a5,
+       0x000be4a5, 0x000c24a5, 0x000c64a5, 0x000ca4a5,
+       0x000ce4a5, 0x000d24a5, 0x000d64a5, 0x000da4a5,
+       0x000de4a5, 0x000e24a5, 0x000e64a5, 0x000ea4a5,
+       0x000ee4a5, 0x000f24a5, 0x000f64a5, 0x000fa4a5,
+       0x000fe4a5, 0x001024a5, 0x001064a5, 0x0010a4a5,
+       0x0010e4a5, 0x001124a5, 0x001164a5, 0x0011a4a5,
+       0x0011e4a5, 0x001224a5, 0x001264a5, 0x0012a4a5,
+       0x0012e4a5, 0x001324a5, 0x001364a5, 0x0013a4a5,
+       0x0013e4a5, 0x001424a5, 0x001464a5, 0x0014a4a5,
+       0x0014e4a5, 0x001524a5, 0x001564a5, 0x0015a4a5,
+       0x0015e4a5, 0x001624a5, 0x001664a5, 0x0016a4a5,
+       0x0016e4a5, 0x001724a5, 0x001764a5, 0x0017a4a5,
+       0x0017e4a5, 0x001824a5, 0x001864a5, 0x0018a4a5,
+       0x0018e4a5, 0x001924a5, 0x001964a5, 0x0019e4a5,
+       0x001a64a5, 0x001ae4a5, 0x001b64a5, 0x001be4a5,
+       0x001c64a5, 0x001ce4a5, 0x001d64a5, 0x001de4a5,
+       0x001e64a5, 0x001ee4a5, 0x001f64a5, 0x001fe4a5,
+       0x002064a5, 0x0020e4a5, 0x002164a5, 0x0021e4a5,
+       0x002264a5, 0x0022e4a5, 0x002364a5, 0x0023e4a5,
+       0x002464a5, 0x0024e4a5, 0x002564a5, 0x0025e4a5,
+       0x002664a5, 0x0026e4a5, 0x002764a5, 0x0027e4a5,
+       0x002864a5, 0x0028e4a5, 0x002964a5, 0x0029e4a5,
+       0x002a64a5, 0x002ae4a5, 0x002b64a5, 0x002be4a5,
+       0x002c64a5, 0x002ce4a5, 0x002d64a5, 0x002de4a5,
+       0x002e64a5, 0x002ee4a5, 0x002f64a5, 0x002fe4a5,
+       0x003064a5, 0x0030e4a5, 0x003164a5, 0x0031e4a5,
+       0x003264a5, 0x0032e4a5, 0x003364a5, 0x0033e4a5,
+       0x003464a5, 0x0034e4a5, 0x003564a5, 0x0035e4a5,
+       0x003664a5, 0x0036e4a5, 0x003764a5, 0x0037e4a5,
+       0x003864a5, 0x0038e4a5, 0x003964a5, 0x0039e4a5,
+       0x003a64a5, 0x003ae4a5, 0x003b64a5, 0x003be4a5,
+       0x003c64a5, 0x003ce4a5, 0x003d64a5, 0x003de4a5,
+       0x003ee4a5, 0x003fe4a5, 0x0040e4a5, 0x0041e4a5,
+       0x0042e4a5, 0x0043e4a5, 0x0044e4a5, 0x0045e4a5,
+       0x0046e4a5, 0x0047e4a5, 0x0048e4a5, 0x0049e4a5,
+       0x004ae4a5, 0x004be4a5, 0x004ce4a5, 0x004de4a5,
+       0x004ee4a5, 0x004fe4a5, 0x0050e4a5, 0x0051e4a5,
+       0x0052e4a5, 0x0053e4a5, 0x0054e4a5, 0x0055e4a5,
+       0x0056e4a5, 0x0057e4a5, 0x0058e4a5, 0x0059e4a5,
+       0x005ae4a5, 0x005be4a5, 0x005ce4a5, 0x005de4a5,
+       0x005ee4a5, 0x005fe4a5, 0x0060e4a5, 0x0061e4a5,
+       0x0062e4a5, 0x0063e4a5, 0x0064e4a5, 0x0065e4a5,
+       0x0066e4a5, 0x0067e4a5, 0x0068e4a5, 0x0069e4a5,
+       0x006ae4a5, 0x006be4a5, 0x006ce4a5, 0x006de4a5,
+       0x006ee4a5, 0x006fe4a5, 0x0070e4a5, 0x0071e4a5,
+       0x0072e4a5, 0x0073e4a5, 0x0074e4a5, 0x0075e4a5,
+       0x0076e4a5, 0x0077e4a5, 0x0078e4a5, 0x0079e4a5,
+       0x007ae4a5, 0x007be4a5, 0x007ce4a5, 0x007de4a5,
+       0x007ee4a5, 0x007fe4a5, 0x0080e4a5, 0x0081e4a5,
+       0x0082e4a5, 0x0083e4a5, 0x0084e4a5, 0x0085e4a5,
+       0x0086e4a5, 0x0087e4a5, 0x0088e4a5, 0x0089e4a5,
+       0x008ae4a5, 0x008be4a5, 0x008ce4a5, 0x008de4a5,
+       0x008fe4a5, 0x0091e4a5, 0x0093e4a5, 0x0095e4a5,
+       0x0097e4a5, 0x0099e4a5, 0x009be4a5, 0x009de4a5,
+       0x009fe4a5, 0x00a1e4a5, 0x00a3e4a5, 0x00a5e4a5,
+       0x00a7e4a5, 0x00a9e4a5, 0x00abe4a5, 0x00ade4a5,
+       0x00afe4a5, 0x00b1e4a5, 0x00b3e4a5, 0x00b5e4a5,
+       0x00b7e4a5, 0x00b9e4a5, 0x00bbe4a5, 0x00bde4a5,
+       0x00bfe4a5, 0x00c1e4a5, 0x00c3e4a5, 0x00c5e4a5,
+       0x00c7e4a5, 0x00c9e4a5, 0x00cbe4a5, 0x00cde4a5,
+       0x00cfe4a5, 0x00d1e4a5, 0x00d3e4a5, 0x00d5e4a5,
+       0x00d7e4a5, 0x00d9e4a5, 0x00dbe4a5, 0x00dde4a5,
+       0x00dfe4a5, 0x00e1e4a5, 0x00e3e4a5, 0x00e5e4a5,
+       0x00e7e4a5, 0x00e9e4a5, 0x00ebe4a5, 0x00ede4a5,
+       0x00efe4a5, 0x00f1e4a5, 0x00f3e4a5, 0x00f5e4a5,
+       0x00f7e4a5, 0x00f9e4a5, 0x00fbe4a5, 0x00fde4a5,
+       0x00ffe4a5, 0x0101e4a5, 0x0103e4a5, 0x0105e4a5,
+       0x0107e4a5, 0x0109e4a5, 0x010be4a5, 0x010de4a5,
+       0x010fe4a5, 0x0111e4a5, 0x0113e4a5, 0x0115e4a5,
+       0x0117e4a5, 0x0119e4a5, 0x011be4a5, 0x011de4a5,
+       0x011fe4a5, 0x0121e4a5, 0x0123e4a5, 0x0125e4a5,
+       0x0127e4a5, 0x0129e4a5, 0x012be4a5, 0x012de4a5,
+       0x012fe4a5, 0x0131e4a5, 0x0133e4a5, 0x0135e4a5,
+       0x0137e4a5, 0x013be4a5, 0x013fe4a5, 0x0143e4a5,
+       0x0147e4a5, 0x014be4a5, 0x014fe4a5, 0x0153e4a5,
+       0x0157e4a5, 0x015be4a5, 0x015fe4a5, 0x0163e4a5,
+       0x0167e4a5, 0x016be4a5, 0x016fe4a5, 0x0173e4a5,
+       0x0177e4a5, 0x017be4a5, 0x017fe4a5, 0x0183e4a5,
+       0x0187e4a5, 0x018be4a5, 0x018fe4a5, 0x0193e4a5,
+       0x0197e4a5, 0x019be4a5, 0x019fe4a5, 0x01a3e4a5,
+       0x01a7e4a5, 0x01abe4a5, 0x01afe4a5, 0x01b3e4a5,
+       0x01b7e4a5, 0x01bbe4a5, 0x01bfe4a5, 0x01c3e4a5,
+       0x01c7e4a5, 0x01cbe4a5, 0x01cfe4a5, 0x01d3e4a5,
+       0x01d7e4a5, 0x01dbe4a5, 0x01dfe4a5, 0x01e3e4a5,
+       0x01e7e4a5, 0x01ebe4a5, 0x01efe4a5, 0x01f3e4a5,
+       0x01f7e4a5, 0x01fbe4a5, 0x01ffe4a5, 0x0203e4a5,
+       0x0207e4a5, 0x020be4a5, 0x020fe4a5, 0x0213e4a5,
+       0x0217e4a5, 0x021be4a5, 0x021fe4a5, 0x0223e4a5,
+       0x0227e4a5, 0x022be4a5, 0x022fe4a5, 0x0233e4a5,
+       0x0237e4a5, 0x023be4a5, 0x023fe4a5, 0x0243e4a5,
+       0x0247e4a5, 0x024be4a5, 0x024fe4a5, 0x0253e4a5,
+       0x0257e4a5, 0x025be4a5, 0x025fe4a5, 0x0263e4a5,
+       0x0267e4a5, 0x026be4a5, 0x026fe4a5, 0x0273e4a5,
+       0x0277e4a5, 0x027be4a5, 0x027fe4a5, 0x0283e4a5,
+       0x0287e4a5, 0x028be4a5, 0x028fe4a5, 0x0293e4a5,
+       0x0297e4a5, 0x029be4a5, 0x029fe4a5, 0x02a3e4a5,
+       0x02a7e4a5, 0x02abe4a5, 0x02afe4a5, 0x02b3e4a5,
+       0x02bbe4a5, 0x02c3e4a5, 0x02cbe4a5, 0x02d3e4a5,
+       0x02dbe4a5, 0x02e3e4a5, 0x02ebe4a5, 0x02f3e4a5,
+       0x02fbe4a5, 0x0303e4a5, 0x030be4a5, 0x0313e4a5,
+       0x031be4a5, 0x0323e4a5, 0x032be4a5, 0x0333e4a5,
+       0x033be4a5, 0x0343e4a5, 0x034be4a5, 0x0353e4a5,
+       0x035be4a5, 0x0363e4a5, 0x036be4a5, 0x0373e4a5,
+       0x037be4a5, 0x0383e4a5, 0x038be4a5, 0x0393e4a5,
+       0x039be4a5, 0x03a3e4a5, 0x03abe4a5, 0x03b3e4a5,
+       0x03bbe4a5, 0x03c3e4a5, 0x03cbe4a5, 0x03d3e4a5,
+       0x03dbe4a5, 0x03e3e4a5, 0x03ebe4a5, 0x03f3e4a5,
+       0x03fbe4a5, 0x0403e4a5, 0x040be4a5, 0x0413e4a5,
+       0x041be4a5, 0x0423e4a5, 0x042be4a5, 0x0433e4a5,
+       0x043be4a5, 0x0443e4a5, 0x044be4a5, 0x0453e4a5,
+       0x045be4a5, 0x0463e4a5, 0x046be4a5, 0x0473e4a5,
+       0x047be4a5, 0x0483e4a5, 0x048be4a5, 0x0493e4a5,
+       0x049be4a5, 0x04a3e4a5, 0x04abe4a5, 0x04b3e4a5,
+       0x04bbe4a5, 0x04c3e4a5, 0x04cbe4a5, 0x04d3e4a5,
+       0x04dbe4a5, 0x04e3e4a5, 0x04ebe4a5, 0x04f3e4a5,
+       0x04fbe4a5, 0x0503e4a5, 0x050be4a5, 0x0513e4a5,
+       0x051be4a5, 0x0523e4a5, 0x052be4a5, 0x0533e4a5,
+       0x053be4a5, 0x0543e4a5, 0x054be4a5, 0x0553e4a5,
+       0x055be4a5, 0x0563e4a5, 0x056be4a5, 0x0573e4a5,
+       0x057be4a5, 0x0583e4a5, 0x058be4a5, 0x0593e4a5,
+       0x059be4a5, 0x05a3e4a5, 0x05abe4a5, 0x05b3e4a5,
+       0x05bbe4a5, 0x05c3e4a5, 0x05cbe4a5, 0x05d3e4a5,
+       0x05dbe4a5, 0x05e3e4a5, 0x05ebe4a5, 0x05f3e4a5,
+       0x05fbe4a5, 0x060be4a5, 0x061be4a5, 0x062be4a5,
+       0x063be4a5, 0x064be4a5, 0x065be4a5, 0x465be4a5,
+       /* The last entry is extra; it is equal to LZMS_MAX_MATCH_OFFSET + 1 and
+        * is here to aid binary search.  */
+};
 
 /* Table: offset slot => number of extra offset bits  */
-u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
+const u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS] = {
+       0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2,
+       2 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4,
+       4 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5,
+       5 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6,
+       7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7,
+       7 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8,
+       8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9,
+       9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9,
+       9 , 9 , 9 , 9 , 9 , 9 , 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
+       10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
+       10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11,
+       11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
+       11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12,
+       12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+       12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+       12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13,
+       13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
+       13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
+       13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+       14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+       14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+       14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+       14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+       15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+       15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+       15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+       15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16,
+       16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+       16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+       16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+       16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+       16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17,
+       17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+       17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+       17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+       17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+       17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+       18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+       18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+       18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+       18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+       18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+       18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+       19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 30,
+};
 
 /* Table: length slot => length slot base value  */
-u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
+const u32 lzms_length_slot_base[LZMS_NUM_LENGTH_SYMS + 1] = {
+       0x00000001, 0x00000002, 0x00000003, 0x00000004,
+       0x00000005, 0x00000006, 0x00000007, 0x00000008,
+       0x00000009, 0x0000000a, 0x0000000b, 0x0000000c,
+       0x0000000d, 0x0000000e, 0x0000000f, 0x00000010,
+       0x00000011, 0x00000012, 0x00000013, 0x00000014,
+       0x00000015, 0x00000016, 0x00000017, 0x00000018,
+       0x00000019, 0x0000001a, 0x0000001b, 0x0000001d,
+       0x0000001f, 0x00000021, 0x00000023, 0x00000027,
+       0x0000002b, 0x0000002f, 0x00000033, 0x00000037,
+       0x0000003b, 0x00000043, 0x0000004b, 0x00000053,
+       0x0000005b, 0x0000006b, 0x0000007b, 0x0000008b,
+       0x0000009b, 0x000000ab, 0x000000cb, 0x000000eb,
+       0x0000012b, 0x000001ab, 0x000002ab, 0x000004ab,
+       0x000008ab, 0x000108ab, 0x400108ab,
+       /* The last entry is extra; it is equal to LZMS_MAX_MATCH_LEN + 1 and is
+        * here to aid binary search.  */
+};
 
 /* Table: length slot => number of extra length bits  */
-u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
+const u8 lzms_extra_length_bits[LZMS_NUM_LENGTH_SYMS] = {
+       0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
+       0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
+       0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
+       0 , 0 , 1 , 1 , 1 , 1 , 2 , 2 ,
+       2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 ,
+       4 , 4 , 4 , 4 , 4 , 5 , 5 , 6 ,
+       7 , 8 , 9 , 10, 16, 30,
+};
 
 unsigned
 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
@@ -53,7 +324,6 @@ lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
        unsigned l = 0;
        unsigned r = num_slots - 1;
        for (;;) {
-               LZMS_ASSERT(r >= l);
                unsigned slot = (l + r) / 2;
                if (value >= slot_base_tab[slot]) {
                        if (value < slot_base_tab[slot + 1])
@@ -66,82 +336,30 @@ lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
        }
 }
 
-static void
-lzms_decode_delta_rle_slot_bases(u32 slot_bases[],
-                                u8 extra_bits[],
-                                const u8 delta_run_lens[],
-                                unsigned num_run_lens,
-                                u32 final,
-                                unsigned expected_num_slots)
+/* Return the number of offset slots used when processing a buffer having the
+ * specified uncompressed size.  */
+unsigned
+lzms_get_num_offset_slots(size_t uncompressed_size)
 {
-       unsigned order = 0;
-       u32 delta = 1;
-       u32 base = 0;
-       unsigned slot = 0;
-       for (unsigned i = 0; i < num_run_lens; i++) {
-               unsigned run_len = delta_run_lens[i];
-               while (run_len--) {
-                       base += delta;
-                       if (slot > 0)
-                               extra_bits[slot - 1] = order;
-                       slot_bases[slot] = base;
-                       slot++;
-               }
-               delta <<= 1;
-               order++;
-       }
-       LZMS_ASSERT(slot == expected_num_slots);
-
-       slot_bases[slot] = final;
-       extra_bits[slot - 1] = fls32(slot_bases[slot] - slot_bases[slot - 1]);
+       if (uncompressed_size < 2)
+               return 0;
+       return 1 + lzms_get_offset_slot(uncompressed_size - 1);
 }
 
-/* Initialize the global offset and length slot tables.  */
-static void
-lzms_compute_slots(void)
+void
+lzms_init_probability_entries(struct lzms_probability_entry *entries, size_t count)
 {
-       /* If an explicit formula that maps LZMS offset and length slots to slot
-        * bases exists, then it could be used here.  But until one is found,
-        * the following code fills in the slots using the observation that the
-        * increase from one slot base to the next is an increasing power of 2.
-        * Therefore, run-length encoding of the delta of adjacent entries can
-        * be used.  */
-       static const u8 offset_slot_delta_run_lens[] = {
-               9,   0,   9,   7,   10,  15,  15,  20,
-               20,  30,  33,  40,  42,  45,  60,  73,
-               80,  85,  95,  105, 6,
-       };
-
-       static const u8 length_slot_delta_run_lens[] = {
-               27,  4,   6,   4,   5,   2,   1,   1,
-               1,   1,   1,   0,   0,   0,   0,   0,
-               1,
-       };
-
-       /* Offset slots  */
-       lzms_decode_delta_rle_slot_bases(lzms_offset_slot_base,
-                                        lzms_extra_offset_bits,
-                                        offset_slot_delta_run_lens,
-                                        ARRAY_LEN(offset_slot_delta_run_lens),
-                                        0x7fffffff,
-                                        LZMS_MAX_NUM_OFFSET_SYMS);
-
-       /* Length slots  */
-       lzms_decode_delta_rle_slot_bases(lzms_length_slot_base,
-                                        lzms_extra_length_bits,
-                                        length_slot_delta_run_lens,
-                                        ARRAY_LEN(length_slot_delta_run_lens),
-                                        0x400108ab,
-                                        LZMS_NUM_LEN_SYMS);
+       for (size_t i = 0; i < count; i++) {
+               entries[i].num_recent_zero_bits = LZMS_INITIAL_PROBABILITY;
+               entries[i].recent_bits = LZMS_INITIAL_RECENT_BITS;
+       }
 }
 
-/* Initialize the global offset and length slot tables if not already done.  */
 void
-lzms_init_slots(void)
+lzms_init_symbol_frequencies(u32 freqs[], size_t num_syms)
 {
-       static pthread_once_t once = PTHREAD_ONCE_INIT;
-
-       pthread_once(&once, lzms_compute_slots);
+       for (size_t i = 0; i < num_syms; i++)
+               freqs[i] = 1;
 }
 
 /*
@@ -341,70 +559,3 @@ lzms_x86_filter(u8 data[restrict], s32 size,
 
        data[tail_idx + 8] = saved_byte;
 }
-
-void
-lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz)
-{
-       /* Recent offsets for LZ matches  */
-       for (u32 i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++)
-               lz->recent_offsets[i] = i + 1;
-
-       lz->prev_offset = 0;
-       lz->upcoming_offset = 0;
-}
-
-void
-lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta)
-{
-       /* Recent offsets and powers for LZ matches  */
-       for (u32 i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) {
-               delta->recent_offsets[i] = i + 1;
-               delta->recent_powers[i] = 0;
-       }
-       delta->prev_offset = 0;
-       delta->prev_power = 0;
-       delta->upcoming_offset = 0;
-       delta->upcoming_power = 0;
-}
-
-
-void
-lzms_init_lru_queues(struct lzms_lru_queues *lru)
-{
-       lzms_init_lz_lru_queues(&lru->lz);
-       lzms_init_delta_lru_queues(&lru->delta);
-}
-
-void
-lzms_update_lz_lru_queue(struct lzms_lz_lru_queues *lz)
-{
-       if (lz->prev_offset != 0) {
-               for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--)
-                       lz->recent_offsets[i + 1] = lz->recent_offsets[i];
-               lz->recent_offsets[0] = lz->prev_offset;
-       }
-       lz->prev_offset = lz->upcoming_offset;
-}
-
-void
-lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta)
-{
-       if (delta->prev_offset != 0) {
-               for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--) {
-                       delta->recent_offsets[i + 1] = delta->recent_offsets[i];
-                       delta->recent_powers[i + 1] = delta->recent_powers[i];
-               }
-               delta->recent_offsets[0] = delta->prev_offset;
-               delta->recent_powers[0] = delta->prev_power;
-       }
-
-       delta->prev_offset = delta->upcoming_offset;
-       delta->prev_power = delta->upcoming_power;
-}
-
-void
-lzms_update_lru_queues(struct lzms_lru_queues *lru)
-{
-       lzms_update_lz_lru_queue(&lru->lz);
-       lzms_update_delta_lru_queues(&lru->delta);
-}
index 3686db0..5f5e374 100644 (file)
@@ -206,6 +206,33 @@ struct lzms_compressor {
        u8 offset_slot_fast[LZMS_NUM_FAST_OFFSETS];
 };
 
+struct lzms_lz_lru_queue {
+       u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
+       u32 prev_offset;
+       u32 upcoming_offset;
+};
+
+static void
+lzms_init_lz_lru_queue(struct lzms_lz_lru_queue *queue)
+{
+       for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++)
+               queue->recent_offsets[i] = i + 1;
+
+       queue->prev_offset = 0;
+       queue->upcoming_offset = 0;
+}
+
+static void
+lzms_update_lz_lru_queue(struct lzms_lz_lru_queue *queue)
+{
+       if (queue->prev_offset != 0) {
+               for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--)
+                       queue->recent_offsets[i + 1] = queue->recent_offsets[i];
+               queue->recent_offsets[0] = queue->prev_offset;
+       }
+       queue->prev_offset = queue->upcoming_offset;
+}
+
 /*
  * Match chooser position data:
  *
@@ -258,7 +285,7 @@ struct lzms_mc_pos_data {
         * entries or current Huffman codewords.  Those aren't maintained
         * per-position and are only updated occassionally.  */
        struct lzms_adaptive_state {
-               struct lzms_lz_lru_queues lru;
+               struct lzms_lz_lru_queue lru;
                u8 main_state;
                u8 match_state;
                u8 lz_match_state;
@@ -898,7 +925,7 @@ lzms_init_adaptive_state(struct lzms_adaptive_state *state)
 {
        unsigned i;
 
-       lzms_init_lz_lru_queues(&state->lru);
+       lzms_init_lz_lru_queue(&state->lru);
        state->main_state = 0;
        state->match_state = 0;
        state->lz_match_state = 0;
@@ -1234,10 +1261,7 @@ lzms_init_range_encoder(struct lzms_range_encoder *enc,
        enc->state = 0;
        LZMS_ASSERT(is_power_of_2(num_states));
        enc->mask = num_states - 1;
-       for (u32 i = 0; i < num_states; i++) {
-               enc->prob_entries[i].num_recent_zero_bits = LZMS_INITIAL_PROBABILITY;
-               enc->prob_entries[i].recent_bits = LZMS_INITIAL_RECENT_BITS;
-       }
+       lzms_init_probability_entries(enc->prob_entries, num_states);
 }
 
 static void
@@ -1291,7 +1315,7 @@ lzms_prepare_compressor(struct lzms_compressor *c, const u8 *udata, u32 ulen,
                                  LZMS_LZ_OFFSET_CODE_REBUILD_FREQ);
 
        lzms_init_huffman_encoder(&c->length_encoder, &c->os,
-                                 LZMS_NUM_LEN_SYMS,
+                                 LZMS_NUM_LENGTH_SYMS,
                                  LZMS_LENGTH_CODE_REBUILD_FREQ);
 
        lzms_init_huffman_encoder(&c->delta_offset_encoder, &c->os,
@@ -1489,8 +1513,6 @@ lzms_create_compressor(size_t max_block_size, unsigned int compression_level,
                goto oom;
        c->optimum_end = &c->optimum[params.optim_array_length];
 
-       lzms_init_slots();
-
        lzms_init_rc_costs();
 
        lzms_init_fast_slots(c);
index 96c501a..b56c4ff 100644 (file)
  * single LZMS-compressed block.  This behavior is the same as that of
  * Decompress() in the Windows 8 compression API when using a compression handle
  * created with CreateDecompressor() with the Algorithm parameter specified as
- * COMPRESS_ALGORITHM_LZMS | COMPRESS_RAW.  Presumably, non-raw LZMS data
- * is a container format from which the locations and sizes (both compressed and
+ * COMPRESS_ALGORITHM_LZMS | COMPRESS_RAW.  Presumably, non-raw LZMS data is a
+ * container format from which the locations and sizes (both compressed and
  * uncompressed) of the constituent blocks can be determined.
  *
  * An LZMS-compressed block must be read in 16-bit little endian units from both
  * directions.  One logical bitstream starts at the front of the block and
  * proceeds forwards.  Another logical bitstream starts at the end of the block
  * and proceeds backwards.  Bits read from the forwards bitstream constitute
- * range-encoded data, whereas bits read from the backwards bitstream constitute
- * Huffman-encoded symbols or verbatim bits.  For both bitstreams, the ordering
- * of the bits within the 16-bit coding units is such that the first bit is the
- * high-order bit and the last bit is the low-order bit.
+ * binary range-encoded data, whereas bits read from the backwards bitstream
+ * constitute Huffman-encoded symbols or verbatim bits.  For both bitstreams,
+ * the ordering of the bits within the 16-bit coding units is such that the
+ * first bit is the high-order bit and the last bit is the low-order bit.
  *
  * From these two logical bitstreams, an LZMS decompressor can reconstitute the
  * series of items that make up the LZMS data representation.  Each such item
  * A traditional LZ match consists of a length and offset; it asserts that the
  * sequence of bytes beginning at the current position and extending for the
  * length is exactly equal to the equal-length sequence of bytes at the offset
- * back in the window.  On the other hand, a delta match consists of a length,
- * raw offset, and power.  It asserts that the sequence of bytes beginning at
- * the current position and extending for the length is equal to the bytewise
- * sum of the two equal-length sequences of bytes (2**power) and (raw_offset *
- * 2**power) bytes before the current position, minus bytewise the sequence of
- * bytes beginning at (2**power + raw_offset * 2**power) bytes before the
- * current position.  Although not generally as useful as traditional LZ
- * matches, delta matches can be helpful on some types of data.  Both LZ and
+ * back in the data buffer.  On the other hand, a delta match consists of a
+ * length, raw offset, and power.  It asserts that the sequence of bytes
+ * beginning at the current position and extending for the length is equal to
+ * the bytewise sum of the two equal-length sequences of bytes (2**power) and
+ * (raw_offset * 2**power) bytes before the current position, minus bytewise the
+ * sequence of bytes beginning at (2**power + raw_offset * 2**power) bytes
+ * before the current position.  Although not generally as useful as traditional
+ * LZ matches, delta matches can be helpful on some types of data.  Both LZ and
  * delta matches may overlap with the current position; in fact, the minimum
  * offset is 1, regardless of match length.
  *
  * queue must be initialized to {0, 0, 0, 0}, and the raw offset queue must be
  * initialized to {1, 2, 3, 4}.
  *
- * Bits from the range decoder must be used to disambiguate item types.  The
- * range decoder must hold two state variables: the range, which must initially
- * be set to 0xffffffff, and the current code, which must initially be set to
- * the first 32 bits read from the forwards bitstream.  The range must be
+ * Bits from the binary range decoder must be used to disambiguate item types.
+ * The range decoder must hold two state variables: the range, which must
+ * initially be set to 0xffffffff, and the current code, which must initially be
+ * set to the first 32 bits read from the forwards bitstream.  The range must be
  * maintained above 0xffff; when it falls below 0xffff, both the range and code
  * must be left-shifted by 16 bits and the low 16 bits of the code must be
  * filled in with the next 16 bits from the forwards bitstream.
  *
- * To decode each bit, the range decoder requires a probability that is
+ * To decode each bit, the binary range decoder requires a probability that is
  * logically a real number between 0 and 1.  Multiplying this probability by the
- * current range and taking the floor gives the bound between the 0-bit region
- * of the range and the 1-bit region of the range.  However, in LZMS,
- * probabilities are restricted to values of n/64 where n is an integer is
- * between 1 and 63 inclusively, so the implementation may use integer
- * operations instead.  Following calculation of the bound, if the current code
- * is in the 0-bit region, the new range becomes the current code and the
- * decoded bit is 0; otherwise, the bound must be subtracted from both the range
- * and the code, and the decoded bit is 1.  More information about range coding
- * can be found at https://en.wikipedia.org/wiki/Range_encoding.  Furthermore,
- * note that the LZMA format also uses range coding and has public domain code
- * available for it.
+ * current range and taking the floor gives the bound between the 0-bit region of
+ * the range and the 1-bit region of the range.  However, in LZMS, probabilities
+ * are restricted to values of n/64 where n is an integer is between 1 and 63
+ * inclusively, so the implementation may use integer operations instead.
+ * Following calculation of the bound, if the current code is in the 0-bit
+ * region, the new range becomes the current code and the decoded bit is 0;
+ * otherwise, the bound must be subtracted from both the range and the code, and
+ * the decoded bit is 1.  More information about range coding can be found at
+ * https://en.wikipedia.org/wiki/Range_encoding.  Furthermore, note that the
+ * LZMA format also uses range coding and has public domain code available for
+ * it.
  *
  * The probability used to range-decode each bit must be taken from a table, of
  * which one instance must exist for each distinct context in which a
  *    of the 8 symbols corresponds to a power.  This code must be rebuilt
  *    whenever 512 symbols have been decoded with it.
  *
- * All the LZMS Huffman codes must be built adaptively based on symbol
- * frequencies.  Initially, each code must be built assuming that all symbols
- * have equal frequency.  Following that, each code must be rebuilt whenever a
- * certain number of symbols has been decoded with it.
+ * Initially, each Huffman code must be built assuming that each symbol in that
+ * code has frequency 1.  Following that, each code must be rebuilt each time a
+ * certain number of symbols, as noted above, has been decoded with it.  The
+ * symbol frequencies for a code must be halved after each rebuild of that code;
+ * this makes the codes adapt to the more recent data.
  *
  * Like other compression formats such as XPRESS, LZX, and DEFLATE, the LZMS
  * format requires that all Huffman codes be constructed in canonical form.
  * This form requires that same-length codewords be lexicographically ordered
  * the same way as the corresponding symbols and that all shorter codewords
  * lexicographically precede longer codewords.  Such a code can be constructed
- * directly from codeword lengths, although in LZMS this is not actually
- * necessary because the codes are built using adaptive symbol frequencies.
+ * directly from codeword lengths.
  *
  * Even with the canonical code restriction, the same frequencies can be used to
  * construct multiple valid Huffman codes.  Therefore, the decompressor needs to
  * construct the right one.  Specifically, the LZMS format requires that the
  * Huffman code be constructed as if the well-known priority queue algorithm is
- * used and frequency ties are always broken in favor of leaf nodes.  See
- * make_canonical_huffman_code() in compress_common.c for more information.
+ * used and frequency ties are always broken in favor of leaf nodes.
  *
  * Codewords in LZMS are guaranteed to not exceed 15 bits.  The format otherwise
  * places no restrictions on codeword length.  Therefore, the Huffman code
  * does so are unimportant, provided that the maximum codeword length parameter
  * is set to at least 15 bits.
  *
- * An LZMS-compressed block seemingly cannot have a compressed size greater than
- * or equal to the uncompressed size.  In such cases the block must be stored
- * uncompressed.
- *
  * After all LZMS items have been decoded, the data must be postprocessed to
  * translate absolute address encoded in x86 instructions into their original
  * relative addresses.
 #include "wimlib/decompress_common.h"
 #include "wimlib/error.h"
 #include "wimlib/lzms.h"
-#include "wimlib/unaligned.h"
 #include "wimlib/util.h"
 
-#include <limits.h>
+/* The TABLEBITS values can be changed; they only affect decoding speed.  */
+#define LZMS_LITERAL_TABLEBITS         10
+#define LZMS_LENGTH_TABLEBITS          10
+#define LZMS_LZ_OFFSET_TABLEBITS       10
+#define LZMS_DELTA_OFFSET_TABLEBITS    10
+#define LZMS_DELTA_POWER_TABLEBITS     8
 
-#define LZMS_DECODE_TABLE_BITS 10
+struct lzms_range_decoder {
 
-/* Structure used for range decoding, reading bits forwards.  This is the first
- * logical bitstream mentioned above.  */
-struct lzms_range_decoder_raw {
        /* The relevant part of the current range.  Although the logical range
         * for range decoding is a very large integer, only a small portion
         * matters at any given time, and it can be normalized (shifted left)
@@ -231,258 +227,222 @@ struct lzms_range_decoder_raw {
 
        /* Pointer to the next little-endian 16-bit integer in the compressed
         * input data (reading forwards).  */
-       const le16 *in;
+       const le16 *next;
 
-       /* Number of 16-bit integers remaining in the compressed input data
-        * (reading forwards).  */
-       size_t num_le16_remaining;
+       /* Pointer to the end of the compressed input data.  */
+       const le16 *end;
 };
 
-/* Structure used for reading raw bits backwards.  This is the second logical
- * bitstream mentioned above.  */
+typedef u64 bitbuf_t;
+
 struct lzms_input_bitstream {
+
        /* Holding variable for bits that have been read from the compressed
-        * data.  The bits are ordered from high-order to low-order.  */
-       /* XXX:  Without special-case code to handle reading more than 17 bits
-        * at a time, this needs to be 64 bits rather than 32 bits.  */
-       u64 bitbuf;
+        * data.  The bit ordering is high to low.  */
+       bitbuf_t bitbuf;
 
-       /* Number of bits in @bitbuf that are used.  */
-       unsigned num_filled_bits;
+       /* Number of bits currently held in @bitbuf.  */
+       unsigned bitsleft;
 
        /* Pointer to the one past the next little-endian 16-bit integer in the
         * compressed input data (reading backwards).  */
-       const le16 *in;
+       const le16 *next;
 
-       /* Number of 16-bit integers remaining in the compressed input data
-        * (reading backwards).  */
-       size_t num_le16_remaining;
+       /* Pointer to the beginning of the compressed input data.  */
+       const le16 *begin;
 };
 
-/* Structure used for range decoding.  This wraps around `struct
- * lzms_range_decoder_raw' to use and maintain probability entries.  */
-struct lzms_range_decoder {
-       /* Pointer to the raw range decoder, which has no persistent knowledge
-        * of probabilities.  Multiple lzms_range_decoder's share the same
-        * lzms_range_decoder_raw.  */
-       struct lzms_range_decoder_raw *rd;
-
-       /* Bits recently decoded by this range decoder.  This are used as in
-        * index into @prob_entries.  */
-       u32 state;
-
-       /* Bitmask for @state to prevent its value from exceeding the number of
-        * probability entries.  */
-       u32 mask;
-
-       /* Probability entries being used for this range decoder.  */
-       struct lzms_probability_entry prob_entries[LZMS_MAX_NUM_STATES];
-};
-
-/* Structure used for Huffman decoding, optionally using the decoded symbols as
- * slots into a base table to determine how many extra bits need to be read to
- * reconstitute the full value.  */
-struct lzms_huffman_decoder {
-
-       /* Bitstream to read Huffman-encoded symbols and verbatim bits from.
-        * Multiple lzms_huffman_decoder's share the same lzms_input_bitstream.
-        */
-       struct lzms_input_bitstream *is;
-
-       /* Pointer to the slot base table to use.  It is indexed by the decoded
-        * Huffman symbol that specifies the slot.  The entry specifies the base
-        * value to use, and the position of its high bit is the number of
-        * additional bits that must be read to reconstitute the full value.
-        *
-        * This member need not be set if only raw Huffman symbols are being
-        * read using this decoder.  */
-       const u32 *slot_base_tab;
-
-       const u8 *extra_bits_tab;
-
-       /* Number of symbols that have been read using this code far.  Reset to
-        * 0 whenever the code is rebuilt.  */
-       u32 num_syms_read;
-
-       /* When @num_syms_read reaches this number, the Huffman code must be
-        * rebuilt.  */
-       u32 rebuild_freq;
-
-       /* Number of symbols in the represented Huffman code.  */
+/* Bookkeeping information for an adaptive Huffman code  */
+struct lzms_huffman_rebuild_info {
+       unsigned num_syms_until_rebuild;
+       unsigned rebuild_freq;
+       u16 *decode_table;
+       unsigned table_bits;
+       u32 *freqs;
+       u32 *codewords;
+       u8 *lens;
        unsigned num_syms;
-
-       /* Running totals of symbol frequencies.  These are diluted slightly
-        * whenever the code is rebuilt.  */
-       u32 sym_freqs[LZMS_MAX_NUM_SYMS];
-
-       /* The length, in bits, of each symbol in the Huffman code.  */
-       u8 lens[LZMS_MAX_NUM_SYMS];
-
-       /* The codeword of each symbol in the Huffman code.  */
-       u32 codewords[LZMS_MAX_NUM_SYMS];
-
-       /* A table for quickly decoding symbols encoded using the Huffman code.
-        */
-       u16 decode_table[(1U << LZMS_DECODE_TABLE_BITS) + 2 * LZMS_MAX_NUM_SYMS]
-                               _aligned_attribute(DECODE_TABLE_ALIGNMENT);
 };
 
-/* State of the LZMS decompressor.  */
 struct lzms_decompressor {
 
-       /* Pointer to the beginning of the uncompressed data buffer.  */
-       u8 *out_begin;
+       /* 'last_target_usages' is in union with everything else because it is
+        * only used for postprocessing.  */
+       union {
+       struct {
 
-       /* Pointer to the next position in the uncompressed data buffer.  */
-       u8 *out_next;
+       struct lzms_range_decoder rd;
+       struct lzms_input_bitstream is;
 
-       /* Pointer to one past the end of the uncompressed data buffer.  */
-       u8 *out_end;
+       /* Match offset LRU queues  */
+       u32 recent_lz_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
+       u64 recent_delta_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
+       u32 pending_lz_offset;
+       u64 pending_delta_offset;
+       const u8 *lz_offset_still_pending;
+       const u8 *delta_offset_still_pending;
+
+       /* States and probabilities for range decoding  */
+
+       u32 main_state;
+       struct lzms_probability_entry main_prob_entries[
+                       LZMS_NUM_MAIN_STATES];
+
+       u32 match_state;
+       struct lzms_probability_entry match_prob_entries[
+                       LZMS_NUM_MATCH_STATES];
+
+       u32 lz_match_state;
+       struct lzms_probability_entry lz_match_prob_entries[
+                       LZMS_NUM_LZ_MATCH_STATES];
+
+       u32 delta_match_state;
+       struct lzms_probability_entry delta_match_prob_entries[
+                       LZMS_NUM_DELTA_MATCH_STATES];
+
+       u32 lz_repeat_match_states[LZMS_NUM_RECENT_OFFSETS - 1];
+       struct lzms_probability_entry lz_repeat_match_prob_entries[
+                       LZMS_NUM_RECENT_OFFSETS - 1][LZMS_NUM_LZ_REPEAT_MATCH_STATES];
+
+       u32 delta_repeat_match_states[LZMS_NUM_RECENT_OFFSETS - 1];
+       struct lzms_probability_entry delta_repeat_match_prob_entries[
+                       LZMS_NUM_RECENT_OFFSETS - 1][LZMS_NUM_DELTA_REPEAT_MATCH_STATES];
+
+       /* Huffman decoding  */
+
+       u16 literal_decode_table[(1 << LZMS_LITERAL_TABLEBITS) +
+                                (2 * LZMS_NUM_LITERAL_SYMS)]
+               _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+       u32 literal_freqs[LZMS_NUM_LITERAL_SYMS];
+       struct lzms_huffman_rebuild_info literal_rebuild_info;
+
+       u16 length_decode_table[(1 << LZMS_LENGTH_TABLEBITS) +
+                               (2 * LZMS_NUM_LENGTH_SYMS)]
+               _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+       u32 length_freqs[LZMS_NUM_LENGTH_SYMS];
+       struct lzms_huffman_rebuild_info length_rebuild_info;
+
+       u16 lz_offset_decode_table[(1 << LZMS_LZ_OFFSET_TABLEBITS) +
+                                  ( 2 * LZMS_MAX_NUM_OFFSET_SYMS)]
+               _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+       u32 lz_offset_freqs[LZMS_MAX_NUM_OFFSET_SYMS];
+       struct lzms_huffman_rebuild_info lz_offset_rebuild_info;
+
+       u16 delta_offset_decode_table[(1 << LZMS_DELTA_OFFSET_TABLEBITS) +
+                                     (2 * LZMS_MAX_NUM_OFFSET_SYMS)]
+               _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+       u32 delta_offset_freqs[LZMS_MAX_NUM_OFFSET_SYMS];
+       struct lzms_huffman_rebuild_info delta_offset_rebuild_info;
+
+       u16 delta_power_decode_table[(1 << LZMS_DELTA_POWER_TABLEBITS) +
+                                    (2 * LZMS_NUM_DELTA_POWER_SYMS)]
+               _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+       u32 delta_power_freqs[LZMS_NUM_DELTA_POWER_SYMS];
+       struct lzms_huffman_rebuild_info delta_power_rebuild_info;
 
-       /* Range decoder, which reads bits from the beginning of the compressed
-        * block, going forwards.  */
-       struct lzms_range_decoder_raw rd;
+       u32 codewords[LZMS_MAX_NUM_SYMS];
+       u8 lens[LZMS_MAX_NUM_SYMS];
 
-       /* Input bitstream, which reads from the end of the compressed block,
-        * going backwards.  */
-       struct lzms_input_bitstream is;
+       }; // struct
 
-       /* Range decoders.  */
-       struct lzms_range_decoder main_range_decoder;
-       struct lzms_range_decoder match_range_decoder;
-       struct lzms_range_decoder lz_match_range_decoder;
-       struct lzms_range_decoder lz_repeat_match_range_decoders[LZMS_NUM_RECENT_OFFSETS - 1];
-       struct lzms_range_decoder delta_match_range_decoder;
-       struct lzms_range_decoder delta_repeat_match_range_decoders[LZMS_NUM_RECENT_OFFSETS - 1];
-
-       /* Huffman decoders.  */
-       struct lzms_huffman_decoder literal_decoder;
-       struct lzms_huffman_decoder lz_offset_decoder;
-       struct lzms_huffman_decoder length_decoder;
-       struct lzms_huffman_decoder delta_power_decoder;
-       struct lzms_huffman_decoder delta_offset_decoder;
-
-       /* LRU (least-recently-used) queues for match information.  */
-       struct lzms_lru_queues lru;
-
-       /* Used for postprocessing.  */
        s32 last_target_usages[65536];
+
+       }; // union
 };
 
-/* Initialize the input bitstream @is to read forwards from the specified
- * compressed data buffer @in that is @in_limit 16-bit integers long.  */
+/* Initialize the input bitstream @is to read backwards from the compressed data
+ * buffer @in that is @count 16-bit integers long.  */
 static void
 lzms_input_bitstream_init(struct lzms_input_bitstream *is,
-                         const le16 *in, size_t in_limit)
+                         const le16 *in, size_t count)
 {
        is->bitbuf = 0;
-       is->num_filled_bits = 0;
-       is->in = in + in_limit;
-       is->num_le16_remaining = in_limit;
+       is->bitsleft = 0;
+       is->next = in + count;
+       is->begin = in;
 }
 
-/* Ensures that @num_bits bits are buffered in the input bitstream.  */
-static int
-lzms_input_bitstream_ensure_bits(struct lzms_input_bitstream *is,
-                                unsigned num_bits)
+/* Ensure that at least @num_bits bits are in the bitbuffer variable.
+ * @num_bits cannot be more than 32.  */
+static inline void
+lzms_ensure_bits(struct lzms_input_bitstream *is, unsigned num_bits)
 {
-       while (is->num_filled_bits < num_bits) {
-               u64 next;
-
-               LZMS_ASSERT(is->num_filled_bits + 16 <= sizeof(is->bitbuf) * 8);
-
-               if (unlikely(is->num_le16_remaining == 0))
-                       return -1;
-
-               next = get_unaligned_u16_le(--is->in);
-               is->num_le16_remaining--;
-
-               is->bitbuf |= next << (sizeof(is->bitbuf) * 8 - is->num_filled_bits - 16);
-               is->num_filled_bits += 16;
-       }
-       return 0;
-
+       if (is->bitsleft >= num_bits)
+               return;
+
+       if (likely(is->next != is->begin))
+               is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next)
+                               << (sizeof(is->bitbuf) * 8 - is->bitsleft - 16);
+       is->bitsleft += 16;
+
+       if (likely(is->next != is->begin))
+               is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next)
+                               << (sizeof(is->bitbuf) * 8 - is->bitsleft - 16);
+       is->bitsleft += 16;
 }
 
-/* Returns the next @num_bits bits that are buffered in the input bitstream.  */
-static u32
-lzms_input_bitstream_peek_bits(struct lzms_input_bitstream *is,
-                              unsigned num_bits)
+/* Get @num_bits bits from the bitbuffer variable.  */
+static inline bitbuf_t
+lzms_peek_bits(struct lzms_input_bitstream *is, unsigned num_bits)
 {
-       LZMS_ASSERT(is->num_filled_bits >= num_bits);
+       if (unlikely(num_bits == 0))
+               return 0;
        return is->bitbuf >> (sizeof(is->bitbuf) * 8 - num_bits);
 }
 
-/* Removes the next @num_bits bits that are buffered in the input bitstream.  */
-static void
-lzms_input_bitstream_remove_bits(struct lzms_input_bitstream *is,
-                                unsigned num_bits)
+/* Remove @num_bits bits from the bitbuffer variable.  */
+static inline void
+lzms_remove_bits(struct lzms_input_bitstream *is, unsigned num_bits)
 {
-       LZMS_ASSERT(is->num_filled_bits >= num_bits);
        is->bitbuf <<= num_bits;
-       is->num_filled_bits -= num_bits;
+       is->bitsleft -= num_bits;
 }
 
-/* Removes and returns the next @num_bits bits that are buffered in the input
- * bitstream.  */
-static u32
-lzms_input_bitstream_pop_bits(struct lzms_input_bitstream *is,
-                             unsigned num_bits)
+/* Remove and return @num_bits bits from the bitbuffer variable.  */
+static inline bitbuf_t
+lzms_pop_bits(struct lzms_input_bitstream *is, unsigned num_bits)
 {
-       u32 bits = lzms_input_bitstream_peek_bits(is, num_bits);
-       lzms_input_bitstream_remove_bits(is, num_bits);
+       bitbuf_t bits = lzms_peek_bits(is, num_bits);
+       lzms_remove_bits(is, num_bits);
        return bits;
 }
 
-/* Reads the next @num_bits from the input bitstream.  */
-static u32
-lzms_input_bitstream_read_bits(struct lzms_input_bitstream *is,
-                              unsigned num_bits)
+/* Read @num_bits bits from the input bitstream.  */
+static inline bitbuf_t
+lzms_read_bits(struct lzms_input_bitstream *is, unsigned num_bits)
 {
-       if (unlikely(lzms_input_bitstream_ensure_bits(is, num_bits)))
-               return 0;
-       return lzms_input_bitstream_pop_bits(is, num_bits);
+       lzms_ensure_bits(is, num_bits);
+       return lzms_pop_bits(is, num_bits);
 }
 
-/* Initialize the range decoder @rd to read forwards from the specified
- * compressed data buffer @in that is @in_limit 16-bit integers long.  */
+/* Initialize the range decoder @rd to read forwards from the compressed data
+ * buffer @in that is @count 16-bit integers long.  */
 static void
-lzms_range_decoder_raw_init(struct lzms_range_decoder_raw *rd,
-                           const le16 *in, size_t in_limit)
+lzms_range_decoder_init(struct lzms_range_decoder *rd,
+                       const le16 *in, size_t count)
 {
        rd->range = 0xffffffff;
-       rd->code = ((u32)get_unaligned_u16_le(&in[0]) << 16) |
-                  ((u32)get_unaligned_u16_le(&in[1]) <<  0);
-       rd->in = in + 2;
-       rd->num_le16_remaining = in_limit - 2;
+       rd->code = ((u32)le16_to_cpu(in[0]) << 16) | le16_to_cpu(in[1]);
+       rd->next = in + 2;
+       rd->end = in + count;
 }
 
-/* Ensures the current range of the range decoder has at least 16 bits of
- * precision.  */
-static int
-lzms_range_decoder_raw_normalize(struct lzms_range_decoder_raw *rd)
-{
-       if (rd->range <= 0xffff) {
-               rd->range <<= 16;
-               if (unlikely(rd->num_le16_remaining == 0))
-                       return -1;
-               rd->code = (rd->code << 16) | get_unaligned_u16_le(rd->in++);
-               rd->num_le16_remaining--;
-       }
-       return 0;
-}
-
-/* Decode and return the next bit from the range decoder (raw version).
+/* Decode and return the next bit from the range decoder.
  *
  * @prob is the chance out of LZMS_PROBABILITY_MAX that the next bit is 0.
  */
-static int
-lzms_range_decoder_raw_decode_bit(struct lzms_range_decoder_raw *rd, u32 prob)
+static inline int
+lzms_range_decoder_decode_bit(struct lzms_range_decoder *rd, u32 prob)
 {
        u32 bound;
 
-       /* Ensure the range has at least 16 bits of precision.  */
-       lzms_range_decoder_raw_normalize(rd);
+       /* Normalize if needed.  */
+       if (rd->range <= 0xffff) {
+               rd->range <<= 16;
+               rd->code <<= 16;
+               if (likely(rd->next != rd->end))
+                       rd->code |= le16_to_cpu(*rd->next++);
+       }
 
        /* Based on the probability, calculate the bound between the 0-bit
         * region and the 1-bit region of the range.  */
@@ -501,100 +461,135 @@ lzms_range_decoder_raw_decode_bit(struct lzms_range_decoder_raw *rd, u32 prob)
 }
 
 /* Decode and return the next bit from the range decoder.  This wraps around
- * lzms_range_decoder_raw_decode_bit() to handle using and updating the
- * appropriate probability table.  */
-static int
-lzms_range_decode_bit(struct lzms_range_decoder *dec)
+ * lzms_range_decoder_decode_bit() to handle using and updating the appropriate
+ * state and probability entry.  */
+static inline int
+lzms_range_decode_bit(struct lzms_range_decoder *rd,
+                     u32 *state_p, u32 num_states,
+                     struct lzms_probability_entry prob_entries[])
 {
        struct lzms_probability_entry *prob_entry;
        u32 prob;
        int bit;
 
        /* Load the probability entry corresponding to the current state.  */
-       prob_entry = &dec->prob_entries[dec->state];
+       prob_entry = &prob_entries[*state_p];
 
        /* Get the probability that the next bit is 0.  */
        prob = lzms_get_probability(prob_entry);
 
        /* Decode the next bit.  */
-       bit = lzms_range_decoder_raw_decode_bit(dec->rd, prob);
+       bit = lzms_range_decoder_decode_bit(rd, prob);
 
        /* Update the state and probability entry based on the decoded bit.  */
-       dec->state = (((dec->state << 1) | bit) & dec->mask);
+       *state_p = ((*state_p << 1) | bit) & (num_states - 1);
        lzms_update_probability_entry(prob_entry, bit);
 
        /* Return the decoded bit.  */
        return bit;
 }
 
+static int
+lzms_decode_main_bit(struct lzms_decompressor *d)
+{
+       return lzms_range_decode_bit(&d->rd, &d->main_state,
+                                    LZMS_NUM_MAIN_STATES,
+                                    d->main_prob_entries);
+}
+
+static int
+lzms_decode_match_bit(struct lzms_decompressor *d)
+{
+       return lzms_range_decode_bit(&d->rd, &d->match_state,
+                                    LZMS_NUM_MATCH_STATES,
+                                    d->match_prob_entries);
+}
+
+static int
+lzms_decode_lz_match_bit(struct lzms_decompressor *d)
+{
+       return lzms_range_decode_bit(&d->rd, &d->lz_match_state,
+                                    LZMS_NUM_LZ_MATCH_STATES,
+                                    d->lz_match_prob_entries);
+}
+
+static int
+lzms_decode_delta_match_bit(struct lzms_decompressor *d)
+{
+       return lzms_range_decode_bit(&d->rd, &d->delta_match_state,
+                                    LZMS_NUM_DELTA_MATCH_STATES,
+                                    d->delta_match_prob_entries);
+}
+
+static noinline int
+lzms_decode_lz_repeat_match_bit(struct lzms_decompressor *d, int idx)
+{
+       return lzms_range_decode_bit(&d->rd, &d->lz_repeat_match_states[idx],
+                                    LZMS_NUM_LZ_REPEAT_MATCH_STATES,
+                                    d->lz_repeat_match_prob_entries[idx]);
+}
+
+static noinline int
+lzms_decode_delta_repeat_match_bit(struct lzms_decompressor *d, int idx)
+{
+       return lzms_range_decode_bit(&d->rd, &d->delta_repeat_match_states[idx],
+                                    LZMS_NUM_DELTA_REPEAT_MATCH_STATES,
+                                    d->delta_repeat_match_prob_entries[idx]);
+}
 
-/* Build the decoding table for a new adaptive Huffman code using the alphabet
- * used in the specified Huffman decoder, with the symbol frequencies
- * dec->sym_freqs.  */
 static void
-lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec)
+lzms_init_huffman_rebuild_info(struct lzms_huffman_rebuild_info *info,
+                              unsigned rebuild_freq,
+                              u16 *decode_table, unsigned table_bits,
+                              u32 *freqs, u32 *codewords, u8 *lens,
+                              unsigned num_syms)
 {
+       info->num_syms_until_rebuild = 1;
+       info->rebuild_freq = rebuild_freq;
+       info->decode_table = decode_table;
+       info->table_bits = table_bits;
+       info->freqs = freqs;
+       info->codewords = codewords;
+       info->lens = lens;
+       info->num_syms = num_syms;
+       lzms_init_symbol_frequencies(freqs, num_syms);
+}
 
-       /* XXX:  This implementation makes use of code already implemented for
-        * the XPRESS and LZX compression formats.  However, since for the
-        * adaptive codes used in LZMS we don't actually need the explicit codes
-        * themselves, only the decode tables, it may be possible to optimize
-        * this by somehow directly building or updating the Huffman decode
-        * table.  This may be a worthwhile optimization because the adaptive
-        * codes change many times throughout a decompression run.  */
-       LZMS_DEBUG("Rebuilding adaptive Huffman code (num_syms=%u)",
-                  dec->num_syms);
-       make_canonical_huffman_code(dec->num_syms, LZMS_MAX_CODEWORD_LEN,
-                                   dec->sym_freqs, dec->lens, dec->codewords);
-#if defined(ENABLE_LZMS_DEBUG)
-       int ret =
-#endif
-       make_huffman_decode_table(dec->decode_table, dec->num_syms,
-                                 LZMS_DECODE_TABLE_BITS, dec->lens,
+static noinline void
+lzms_rebuild_huffman_code(struct lzms_huffman_rebuild_info *info)
+{
+       make_canonical_huffman_code(info->num_syms, LZMS_MAX_CODEWORD_LEN,
+                                   info->freqs, info->lens, info->codewords);
+       make_huffman_decode_table(info->decode_table, info->num_syms,
+                                 info->table_bits, info->lens,
                                  LZMS_MAX_CODEWORD_LEN);
-       LZMS_ASSERT(ret == 0);
+       for (unsigned i = 0; i < info->num_syms; i++)
+               info->freqs[i] = (info->freqs[i] >> 1) + 1;
+       info->num_syms_until_rebuild = info->rebuild_freq;
 }
 
-/* Decode and return the next Huffman-encoded symbol from the LZMS-compressed
- * block using the specified Huffman decoder.  */
-static u32
-lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec)
+static inline unsigned
+lzms_decode_huffman_symbol(struct lzms_input_bitstream *is,
+                          u16 decode_table[], unsigned table_bits,
+                          struct lzms_huffman_rebuild_info *rebuild_info)
 {
-       const u16 *decode_table = dec->decode_table;
-       struct lzms_input_bitstream *is = dec->is;
-       u16 entry;
-       u16 key_bits;
-       u16 sym;
-
-       /* The Huffman codes used in LZMS are adaptive and must be rebuilt
-        * whenever a certain number of symbols have been read.  Each such
-        * rebuild uses the current symbol frequencies, but the format also
-        * requires that the symbol frequencies be halved after each code
-        * rebuild.  This diminishes the effect of old symbols on the current
-        * Huffman codes, thereby causing the Huffman codes to be more locally
-        * adaptable.  */
-       if (dec->num_syms_read == dec->rebuild_freq) {
-               lzms_rebuild_adaptive_huffman_code(dec);
-               for (unsigned i = 0; i < dec->num_syms; i++) {
-                       dec->sym_freqs[i] >>= 1;
-                       dec->sym_freqs[i] += 1;
-               }
-               dec->num_syms_read = 0;
-       }
+       unsigned key_bits;
+       unsigned entry;
+       unsigned sym;
+
+       if (unlikely(--rebuild_info->num_syms_until_rebuild == 0))
+               lzms_rebuild_huffman_code(rebuild_info);
 
-       /* XXX: Copied from read_huffsym() (decompress_common.h), since this
-        * uses a different input bitstream type.  Should unify the
-        * implementations.  */
-       lzms_input_bitstream_ensure_bits(is, LZMS_MAX_CODEWORD_LEN);
+       lzms_ensure_bits(is, LZMS_MAX_CODEWORD_LEN);
 
        /* Index the decode table by the next table_bits bits of the input.  */
-       key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_TABLE_BITS);
+       key_bits = lzms_peek_bits(is, table_bits);
        entry = decode_table[key_bits];
        if (likely(entry < 0xC000)) {
                /* Fast case: The decode table directly provided the symbol and
                 * codeword length.  The low 11 bits are the symbol, and the
                 * high 5 bits are the codeword length.  */
-               lzms_input_bitstream_remove_bits(is, entry >> 11);
+               lzms_remove_bits(is, entry >> 11);
                sym = entry & 0x7FF;
        } else {
                /* Slow case: The codeword for the symbol is longer than
@@ -602,440 +597,381 @@ lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec)
                 * the first (1 << table_bits) entries of the decode table.
                 * Traverse the appropriate binary tree bit-by-bit in order to
                 * decode the symbol.  */
-               lzms_input_bitstream_remove_bits(is, LZMS_DECODE_TABLE_BITS);
+               lzms_remove_bits(is, table_bits);
                do {
-                       key_bits = (entry & 0x3FFF) + lzms_input_bitstream_pop_bits(is, 1);
+                       key_bits = (entry & 0x3FFF) + lzms_pop_bits(is, 1);
                } while ((entry = decode_table[key_bits]) >= 0xC000);
                sym = entry;
        }
 
        /* Tally and return the decoded symbol.  */
-       ++dec->sym_freqs[sym];
-       ++dec->num_syms_read;
+       rebuild_info->freqs[sym]++;
        return sym;
 }
 
-/* Decode a number from the LZMS bitstream, encoded as a Huffman-encoded symbol
- * specifying a "slot" (whose corresponding value is looked up in a static
- * table) plus the number specified by a number of extra bits depending on the
- * slot.  */
-static u32
-lzms_decode_value(struct lzms_huffman_decoder *dec)
+static unsigned
+lzms_decode_literal(struct lzms_decompressor *d)
 {
-       unsigned slot;
-       unsigned num_extra_bits;
-       u32 extra_bits;
-
-       LZMS_ASSERT(dec->slot_base_tab != NULL);
-       LZMS_ASSERT(dec->extra_bits_tab != NULL);
-
-       /* Read the slot (offset slot, length slot, etc.), which is encoded as a
-        * Huffman symbol.  */
-       slot = lzms_huffman_decode_symbol(dec);
-
-       /* Get the number of extra bits needed to represent the range of values
-        * that share the slot.  */
-       num_extra_bits = dec->extra_bits_tab[slot];
-
-       /* Read the number of extra bits and add them to the slot base to form
-        * the final decoded value.  */
-       extra_bits = lzms_input_bitstream_read_bits(dec->is, num_extra_bits);
-       return dec->slot_base_tab[slot] + extra_bits;
+       return lzms_decode_huffman_symbol(&d->is,
+                                         d->literal_decode_table,
+                                         LZMS_LITERAL_TABLEBITS,
+                                         &d->literal_rebuild_info);
 }
 
-/* Copy a literal to the output buffer.  */
-static int
-lzms_copy_literal(struct lzms_decompressor *ctx, u8 literal)
+static u32
+lzms_decode_length(struct lzms_decompressor *d)
 {
-       *ctx->out_next++ = literal;
-       return 0;
+       unsigned slot = lzms_decode_huffman_symbol(&d->is,
+                                                  d->length_decode_table,
+                                                  LZMS_LENGTH_TABLEBITS,
+                                                  &d->length_rebuild_info);
+       u32 length = lzms_length_slot_base[slot];
+       unsigned num_extra_bits = lzms_extra_length_bits[slot];
+       /* Usually most lengths are short and have no extra bits.  */
+       if (num_extra_bits)
+               length += lzms_read_bits(&d->is, num_extra_bits);
+       return length;
 }
 
-/* Validate an LZ match and copy it to the output buffer.  */
-static int
-lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset)
+static u32
+lzms_decode_lz_offset(struct lzms_decompressor *d)
 {
-       u8 *out_next;
-
-       if (length > ctx->out_end - ctx->out_next) {
-               LZMS_DEBUG("Match overrun!");
-               return -1;
-       }
-       if (offset > ctx->out_next - ctx->out_begin) {
-               LZMS_DEBUG("Match underrun!");
-               return -1;
-       }
-
-       out_next = ctx->out_next;
-
-       lz_copy(out_next, length, offset, ctx->out_end, 1);
-       ctx->out_next = out_next + length;
-
-       return 0;
+       unsigned slot = lzms_decode_huffman_symbol(&d->is,
+                                                  d->lz_offset_decode_table,
+                                                  LZMS_LZ_OFFSET_TABLEBITS,
+                                                  &d->lz_offset_rebuild_info);
+       return lzms_offset_slot_base[slot] +
+              lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]);
 }
 
-/* Validate a delta match and copy it to the output buffer.  */
-static int
-lzms_copy_delta_match(struct lzms_decompressor *ctx, u32 length,
-                     u32 power, u32 raw_offset)
+static u32
+lzms_decode_delta_offset(struct lzms_decompressor *d)
 {
-       u32 offset1 = 1U << power;
-       u32 offset2 = raw_offset << power;
-       u32 offset = offset1 + offset2;
-       u8 *out_next;
-       u8 *matchptr1;
-       u8 *matchptr2;
-       u8 *matchptr;
-
-       if (length > ctx->out_end - ctx->out_next) {
-               LZMS_DEBUG("Match overrun!");
-               return -1;
-       }
-       if (offset > ctx->out_next - ctx->out_begin) {
-               LZMS_DEBUG("Match underrun!");
-               return -1;
-       }
-
-       out_next = ctx->out_next;
-       matchptr1 = out_next - offset1;
-       matchptr2 = out_next - offset2;
-       matchptr = out_next - offset;
-
-       while (length--)
-               *out_next++ = *matchptr1++ + *matchptr2++ - *matchptr++;
-
-       ctx->out_next = out_next;
-       return 0;
+       unsigned slot = lzms_decode_huffman_symbol(&d->is,
+                                                  d->delta_offset_decode_table,
+                                                  LZMS_DELTA_OFFSET_TABLEBITS,
+                                                  &d->delta_offset_rebuild_info);
+       return lzms_offset_slot_base[slot] +
+              lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]);
 }
 
-/* Decode a (length, offset) pair from the input.  */
-static int
-lzms_decode_lz_match(struct lzms_decompressor *ctx)
+static unsigned
+lzms_decode_delta_power(struct lzms_decompressor *d)
 {
-       int bit;
-       u32 length, offset;
-
-       /* Decode the match offset.  The next range-encoded bit indicates
-        * whether it's a repeat offset or an explicit offset.  */
-
-       bit = lzms_range_decode_bit(&ctx->lz_match_range_decoder);
-       if (bit == 0) {
-               /* Explicit offset.  */
-               offset = lzms_decode_value(&ctx->lz_offset_decoder);
-       } else {
-               /* Repeat offset.  */
-               int i;
-
-               for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
-                       if (!lzms_range_decode_bit(&ctx->lz_repeat_match_range_decoders[i]))
-                               break;
-
-               offset = ctx->lru.lz.recent_offsets[i];
-
-               for (; i < LZMS_NUM_RECENT_OFFSETS; i++)
-                       ctx->lru.lz.recent_offsets[i] = ctx->lru.lz.recent_offsets[i + 1];
-       }
-
-       /* Decode match length, which is always given explicitly (there is no
-        * LRU queue for repeat lengths).  */
-       length = lzms_decode_value(&ctx->length_decoder);
-
-       ctx->lru.lz.upcoming_offset = offset;
-
-       LZMS_DEBUG("Decoded %s LZ match: length=%u, offset=%u",
-                  (bit ? "repeat" : "explicit"), length, offset);
-
-       /* Validate the match and copy it to the output.  */
-       return lzms_copy_lz_match(ctx, length, offset);
+       return lzms_decode_huffman_symbol(&d->is,
+                                         d->delta_power_decode_table,
+                                         LZMS_DELTA_POWER_TABLEBITS,
+                                         &d->delta_power_rebuild_info);
 }
 
-/* Decodes a "delta" match from the input.  */
+/* Decode the series of literals and matches from the LZMS-compressed data.
+ * Return 0 if successful or -1 if the compressed data is invalid.  */
 static int
-lzms_decode_delta_match(struct lzms_decompressor *ctx)
+lzms_decode_items(struct lzms_decompressor * const restrict d,
+                 u8 * const restrict out, const size_t out_nbytes)
 {
-       int bit;
-       u32 length, power, raw_offset;
-
-       /* Decode the match power and raw offset.  The next range-encoded bit
-        * indicates whether these data are a repeat, or given explicitly.  */
-
-       bit = lzms_range_decode_bit(&ctx->delta_match_range_decoder);
-       if (bit == 0) {
-               power = lzms_huffman_decode_symbol(&ctx->delta_power_decoder);
-               raw_offset = lzms_decode_value(&ctx->delta_offset_decoder);
-       } else {
-               int i;
-
-               for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
-                       if (!lzms_range_decode_bit(&ctx->delta_repeat_match_range_decoders[i]))
-                               break;
-
-               power = ctx->lru.delta.recent_powers[i];
-               raw_offset = ctx->lru.delta.recent_offsets[i];
-
-               for (; i < LZMS_NUM_RECENT_OFFSETS; i++) {
-                       ctx->lru.delta.recent_powers[i] = ctx->lru.delta.recent_powers[i + 1];
-                       ctx->lru.delta.recent_offsets[i] = ctx->lru.delta.recent_offsets[i + 1];
+       u8 *out_next = out;
+       u8 * const out_end = out + out_nbytes;
+
+       while (out_next != out_end) {
+
+               if (!lzms_decode_main_bit(d)) {
+
+                       /* Literal  */
+                       *out_next++ = lzms_decode_literal(d);
+
+               } else if (!lzms_decode_match_bit(d)) {
+
+                       /* LZ match  */
+
+                       u32 offset;
+                       u32 length;
+
+                       if (d->pending_lz_offset != 0 &&
+                           out_next != d->lz_offset_still_pending)
+                       {
+                               BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+                               d->recent_lz_offsets[3] = d->recent_lz_offsets[2];
+                               d->recent_lz_offsets[2] = d->recent_lz_offsets[1];
+                               d->recent_lz_offsets[1] = d->recent_lz_offsets[0];
+                               d->recent_lz_offsets[0] = d->pending_lz_offset;
+                               d->pending_lz_offset = 0;
+                       }
+
+                       if (!lzms_decode_lz_match_bit(d)) {
+                               /* Explicit offset  */
+                               offset = lzms_decode_lz_offset(d);
+                       } else {
+                               /* Repeat offset  */
+
+                               BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+                               if (!lzms_decode_lz_repeat_match_bit(d, 0)) {
+                                       offset = d->recent_lz_offsets[0];
+                                       d->recent_lz_offsets[0] = d->recent_lz_offsets[1];
+                                       d->recent_lz_offsets[1] = d->recent_lz_offsets[2];
+                                       d->recent_lz_offsets[2] = d->recent_lz_offsets[3];
+                               } else if (!lzms_decode_lz_repeat_match_bit(d, 1)) {
+                                       offset = d->recent_lz_offsets[1];
+                                       d->recent_lz_offsets[1] = d->recent_lz_offsets[2];
+                                       d->recent_lz_offsets[2] = d->recent_lz_offsets[3];
+                               } else {
+                                       offset = d->recent_lz_offsets[2];
+                                       d->recent_lz_offsets[2] = d->recent_lz_offsets[3];
+                               }
+                       }
+
+                       if (d->pending_lz_offset != 0) {
+                               BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+                               d->recent_lz_offsets[3] = d->recent_lz_offsets[2];
+                               d->recent_lz_offsets[2] = d->recent_lz_offsets[1];
+                               d->recent_lz_offsets[1] = d->recent_lz_offsets[0];
+                               d->recent_lz_offsets[0] = d->pending_lz_offset;
+                       }
+                       d->pending_lz_offset = offset;
+
+                       length = lzms_decode_length(d);
+
+                       if (unlikely(length > out_end - out_next))
+                               return -1;
+                       if (unlikely(offset > out_next - out))
+                               return -1;
+
+                       lz_copy(out_next, length, offset, out_end, LZMS_MIN_MATCH_LEN);
+                       out_next += length;
+
+                       d->lz_offset_still_pending = out_next;
+               } else {
+                       /* Delta match  */
+
+                       u32 power;
+                       u32 raw_offset, offset1, offset2, offset;
+                       const u8 *matchptr1, *matchptr2, *matchptr;
+                       u32 length;
+
+                       if (d->pending_delta_offset != 0 &&
+                           out_next != d->delta_offset_still_pending)
+                       {
+                               BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+                               d->recent_delta_offsets[3] = d->recent_delta_offsets[2];
+                               d->recent_delta_offsets[2] = d->recent_delta_offsets[1];
+                               d->recent_delta_offsets[1] = d->recent_delta_offsets[0];
+                               d->recent_delta_offsets[0] = d->pending_delta_offset;
+                               d->pending_delta_offset = 0;
+                       }
+
+                       if (!lzms_decode_delta_match_bit(d)) {
+                               /* Explicit offset  */
+                               power = lzms_decode_delta_power(d);
+                               raw_offset = lzms_decode_delta_offset(d);
+                       } else {
+                               /* Repeat offset  */
+                               u64 val;
+
+                               BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+                               if (!lzms_decode_delta_repeat_match_bit(d, 0)) {
+                                       val = d->recent_delta_offsets[0];
+                                       d->recent_delta_offsets[0] = d->recent_delta_offsets[1];
+                                       d->recent_delta_offsets[1] = d->recent_delta_offsets[2];
+                                       d->recent_delta_offsets[2] = d->recent_delta_offsets[3];
+                               } else if (!lzms_decode_delta_repeat_match_bit(d, 1)) {
+                                       val = d->recent_delta_offsets[1];
+                                       d->recent_delta_offsets[1] = d->recent_delta_offsets[2];
+                                       d->recent_delta_offsets[2] = d->recent_delta_offsets[3];
+                               } else {
+                                       val = d->recent_delta_offsets[2];
+                                       d->recent_delta_offsets[2] = d->recent_delta_offsets[3];
+                               }
+                               power = val >> 32;
+                               raw_offset = (u32)val;
+                       }
+
+                       if (d->pending_delta_offset != 0) {
+                               BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+                               d->recent_delta_offsets[3] = d->recent_delta_offsets[2];
+                               d->recent_delta_offsets[2] = d->recent_delta_offsets[1];
+                               d->recent_delta_offsets[1] = d->recent_delta_offsets[0];
+                               d->recent_delta_offsets[0] = d->pending_delta_offset;
+                               d->pending_delta_offset = 0;
+                       }
+                       d->pending_delta_offset = raw_offset | ((u64)power << 32);
+
+                       length = lzms_decode_length(d);
+
+                       offset1 = (u32)1 << power;
+                       offset2 = raw_offset << power;
+                       offset = offset1 + offset2;
+
+                       /* raw_offset<<power overflowed?  */
+                       if (unlikely((offset2 >> power) != raw_offset))
+                               return -1;
+
+                       /* offset1+offset2 overflowed?  */
+                       if (unlikely(offset < offset2))
+                               return -1;
+
+                       if (unlikely(length > out_end - out_next))
+                               return -1;
+
+                       if (unlikely(offset > out_next - out))
+                               return -1;
+
+                       matchptr1 = out_next - offset1;
+                       matchptr2 = out_next - offset2;
+                       matchptr = out_next - offset;
+
+                       do {
+                               *out_next++ = *matchptr1++ + *matchptr2++ - *matchptr++;
+                       } while (--length);
+
+                       d->delta_offset_still_pending = out_next;
                }
        }
-
-       length = lzms_decode_value(&ctx->length_decoder);
-
-       ctx->lru.delta.upcoming_power = power;
-       ctx->lru.delta.upcoming_offset = raw_offset;
-
-       LZMS_DEBUG("Decoded %s delta match: length=%u, power=%u, raw_offset=%u",
-                  (bit ? "repeat" : "explicit"), length, power, raw_offset);
-
-       /* Validate the match and copy it to the output.  */
-       return lzms_copy_delta_match(ctx, length, power, raw_offset);
-}
-
-/* Decode an LZ or delta match.  */
-static int
-lzms_decode_match(struct lzms_decompressor *ctx)
-{
-       if (!lzms_range_decode_bit(&ctx->match_range_decoder))
-               return lzms_decode_lz_match(ctx);
-       else
-               return lzms_decode_delta_match(ctx);
-}
-
-/* Decode a literal byte encoded using the literal Huffman code.  */
-static int
-lzms_decode_literal(struct lzms_decompressor *ctx)
-{
-       u8 literal = lzms_huffman_decode_symbol(&ctx->literal_decoder);
-       LZMS_DEBUG("Decoded literal: 0x%02x", literal);
-       return lzms_copy_literal(ctx, literal);
-}
-
-/* Decode the next LZMS match or literal.  */
-static int
-lzms_decode_item(struct lzms_decompressor *ctx)
-{
-       int ret;
-
-       ctx->lru.lz.upcoming_offset = 0;
-       ctx->lru.delta.upcoming_power = 0;
-       ctx->lru.delta.upcoming_offset = 0;
-
-       if (lzms_range_decode_bit(&ctx->main_range_decoder))
-               ret = lzms_decode_match(ctx);
-       else
-               ret = lzms_decode_literal(ctx);
-
-       if (ret)
-               return ret;
-
-       lzms_update_lru_queues(&ctx->lru);
        return 0;
 }
 
 static void
-lzms_init_range_decoder(struct lzms_range_decoder *dec,
-                       struct lzms_range_decoder_raw *rd, u32 num_states)
+lzms_init_decompressor(struct lzms_decompressor *d, const void *in,
+                      size_t in_nbytes, unsigned num_offset_slots)
 {
-       dec->rd = rd;
-       dec->state = 0;
-       dec->mask = num_states - 1;
-       for (u32 i = 0; i < num_states; i++) {
-               dec->prob_entries[i].num_recent_zero_bits = LZMS_INITIAL_PROBABILITY;
-               dec->prob_entries[i].recent_bits = LZMS_INITIAL_RECENT_BITS;
+       /* Match offset LRU queues  */
+       for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) {
+               d->recent_lz_offsets[i] = i + 1;
+               d->recent_delta_offsets[i] = i + 1;
        }
-}
-
-static void
-lzms_init_huffman_decoder(struct lzms_huffman_decoder *dec,
-                         struct lzms_input_bitstream *is,
-                         const u32 *slot_base_tab,
-                         const u8 *extra_bits_tab,
-                         unsigned num_syms,
-                         unsigned rebuild_freq)
-{
-       dec->is = is;
-       dec->slot_base_tab = slot_base_tab;
-       dec->extra_bits_tab = extra_bits_tab;
-       dec->num_syms = num_syms;
-       dec->num_syms_read = rebuild_freq;
-       dec->rebuild_freq = rebuild_freq;
-       for (unsigned i = 0; i < num_syms; i++)
-               dec->sym_freqs[i] = 1;
-}
-
-/* Prepare to decode items from an LZMS-compressed block.  */
-static void
-lzms_init_decompressor(struct lzms_decompressor *ctx,
-                      const void *cdata, unsigned clen,
-                      void *ubuf, unsigned ulen)
-{
-       unsigned num_offset_slots;
-
-       LZMS_DEBUG("Initializing decompressor (clen=%u, ulen=%u)", clen, ulen);
+       d->pending_lz_offset = 0;
+       d->pending_delta_offset = 0;
 
-       /* Initialize output pointers.  */
-       ctx->out_begin = ubuf;
-       ctx->out_next = ubuf;
-       ctx->out_end = (u8*)ubuf + ulen;
+       /* Range decoding  */
 
-       /* Initialize the raw range decoder (reading forwards).  */
-       lzms_range_decoder_raw_init(&ctx->rd, cdata, clen / 2);
+       lzms_range_decoder_init(&d->rd, in, in_nbytes / sizeof(le16));
 
-       /* Initialize the input bitstream for Huffman symbols (reading
-        * backwards)  */
-       lzms_input_bitstream_init(&ctx->is, cdata, clen / 2);
+       d->main_state = 0;
+       lzms_init_probability_entries(d->main_prob_entries, LZMS_NUM_MAIN_STATES);
 
-       /* Calculate the number of offset slots needed for this compressed
-        * block.  */
-       num_offset_slots = lzms_get_offset_slot(ulen - 1) + 1;
+       d->match_state = 0;
+       lzms_init_probability_entries(d->match_prob_entries, LZMS_NUM_MATCH_STATES);
 
-       LZMS_DEBUG("Using %u offset slots", num_offset_slots);
+       d->lz_match_state = 0;
+       lzms_init_probability_entries(d->lz_match_prob_entries, LZMS_NUM_LZ_MATCH_STATES);
 
-       /* Initialize Huffman decoders for each alphabet used in the compressed
-        * representation.  */
-       lzms_init_huffman_decoder(&ctx->literal_decoder, &ctx->is,
-                                 NULL, NULL, LZMS_NUM_LITERAL_SYMS,
-                                 LZMS_LITERAL_CODE_REBUILD_FREQ);
+       d->delta_match_state = 0;
+       lzms_init_probability_entries(d->delta_match_prob_entries, LZMS_NUM_DELTA_MATCH_STATES);
 
-       lzms_init_huffman_decoder(&ctx->lz_offset_decoder, &ctx->is,
-                                 lzms_offset_slot_base,
-                                 lzms_extra_offset_bits,
-                                 num_offset_slots,
-                                 LZMS_LZ_OFFSET_CODE_REBUILD_FREQ);
+       for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++) {
+               d->lz_repeat_match_states[i] = 0;
+               lzms_init_probability_entries(d->lz_repeat_match_prob_entries[i],
+                                             LZMS_NUM_LZ_REPEAT_MATCH_STATES);
 
-       lzms_init_huffman_decoder(&ctx->length_decoder, &ctx->is,
-                                 lzms_length_slot_base,
-                                 lzms_extra_length_bits,
-                                 LZMS_NUM_LEN_SYMS,
-                                 LZMS_LENGTH_CODE_REBUILD_FREQ);
-
-       lzms_init_huffman_decoder(&ctx->delta_offset_decoder, &ctx->is,
-                                 lzms_offset_slot_base,
-                                 lzms_extra_offset_bits,
-                                 num_offset_slots,
-                                 LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ);
-
-       lzms_init_huffman_decoder(&ctx->delta_power_decoder, &ctx->is,
-                                 NULL, NULL, LZMS_NUM_DELTA_POWER_SYMS,
-                                 LZMS_DELTA_POWER_CODE_REBUILD_FREQ);
-
-
-       /* Initialize range decoders, all of which wrap around the same
-        * lzms_range_decoder_raw.  */
-       lzms_init_range_decoder(&ctx->main_range_decoder,
-                               &ctx->rd, LZMS_NUM_MAIN_STATES);
-
-       lzms_init_range_decoder(&ctx->match_range_decoder,
-                               &ctx->rd, LZMS_NUM_MATCH_STATES);
-
-       lzms_init_range_decoder(&ctx->lz_match_range_decoder,
-                               &ctx->rd, LZMS_NUM_LZ_MATCH_STATES);
-
-       for (size_t i = 0; i < ARRAY_LEN(ctx->lz_repeat_match_range_decoders); i++)
-               lzms_init_range_decoder(&ctx->lz_repeat_match_range_decoders[i],
-                                       &ctx->rd, LZMS_NUM_LZ_REPEAT_MATCH_STATES);
-
-       lzms_init_range_decoder(&ctx->delta_match_range_decoder,
-                               &ctx->rd, LZMS_NUM_DELTA_MATCH_STATES);
-
-       for (size_t i = 0; i < ARRAY_LEN(ctx->delta_repeat_match_range_decoders); i++)
-               lzms_init_range_decoder(&ctx->delta_repeat_match_range_decoders[i],
-                                       &ctx->rd, LZMS_NUM_DELTA_REPEAT_MATCH_STATES);
-
-       /* Initialize LRU match information.  */
-       lzms_init_lru_queues(&ctx->lru);
+               d->delta_repeat_match_states[i] = 0;
+               lzms_init_probability_entries(d->delta_repeat_match_prob_entries[i],
+                                             LZMS_NUM_DELTA_REPEAT_MATCH_STATES);
+       }
 
-       LZMS_DEBUG("Decompressor successfully initialized");
+       /* Huffman decoding  */
+
+       lzms_input_bitstream_init(&d->is, in, in_nbytes / sizeof(le16));
+
+       lzms_init_huffman_rebuild_info(&d->literal_rebuild_info,
+                                      LZMS_LITERAL_CODE_REBUILD_FREQ,
+                                      d->literal_decode_table,
+                                      LZMS_LITERAL_TABLEBITS,
+                                      d->literal_freqs,
+                                      d->codewords,
+                                      d->lens,
+                                      LZMS_NUM_LITERAL_SYMS);
+
+       lzms_init_huffman_rebuild_info(&d->length_rebuild_info,
+                                      LZMS_LENGTH_CODE_REBUILD_FREQ,
+                                      d->length_decode_table,
+                                      LZMS_LENGTH_TABLEBITS,
+                                      d->length_freqs,
+                                      d->codewords,
+                                      d->lens,
+                                      LZMS_NUM_LENGTH_SYMS);
+
+       lzms_init_huffman_rebuild_info(&d->lz_offset_rebuild_info,
+                                      LZMS_LZ_OFFSET_CODE_REBUILD_FREQ,
+                                      d->lz_offset_decode_table,
+                                      LZMS_LZ_OFFSET_TABLEBITS,
+                                      d->lz_offset_freqs,
+                                      d->codewords,
+                                      d->lens,
+                                      num_offset_slots);
+
+       lzms_init_huffman_rebuild_info(&d->delta_offset_rebuild_info,
+                                      LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ,
+                                      d->delta_offset_decode_table,
+                                      LZMS_DELTA_OFFSET_TABLEBITS,
+                                      d->delta_offset_freqs,
+                                      d->codewords,
+                                      d->lens,
+                                      num_offset_slots);
+
+       lzms_init_huffman_rebuild_info(&d->delta_power_rebuild_info,
+                                      LZMS_DELTA_POWER_CODE_REBUILD_FREQ,
+                                      d->delta_power_decode_table,
+                                      LZMS_DELTA_POWER_TABLEBITS,
+                                      d->delta_power_freqs,
+                                      d->codewords,
+                                      d->lens,
+                                      LZMS_NUM_DELTA_POWER_SYMS);
 }
 
-/* Decode the series of literals and matches from the LZMS-compressed data.
- * Returns 0 on success; nonzero if the compressed data is invalid.  */
 static int
-lzms_decode_items(const u8 *cdata, size_t clen, u8 *ubuf, size_t ulen,
-                 struct lzms_decompressor *ctx)
+lzms_create_decompressor(size_t max_bufsize, void **d_ret)
 {
-       /* Initialize the LZMS decompressor.  */
-       lzms_init_decompressor(ctx, cdata, clen, ubuf, ulen);
-
-       /* Decode the sequence of items.  */
-       while (ctx->out_next != ctx->out_end) {
-               LZMS_DEBUG("Position %u", ctx->out_next - ctx->out_begin);
-               if (lzms_decode_item(ctx))
-                       return -1;
-       }
+       struct lzms_decompressor *d;
+
+       if (max_bufsize > LZMS_MAX_BUFFER_SIZE)
+               return WIMLIB_ERR_INVALID_PARAM;
+
+       d = ALIGNED_MALLOC(sizeof(struct lzms_decompressor),
+                          DECODE_TABLE_ALIGNMENT);
+       if (!d)
+               return WIMLIB_ERR_NOMEM;
+
+       *d_ret = d;
        return 0;
 }
 
+/* Decompress @in_nbytes bytes of LZMS-compressed data at @in and write the
+ * uncompressed data, which had original size @out_nbytes, to @out.  Return 0 if
+ * successful or -1 if the compressed data is invalid.  */
 static int
-lzms_decompress(const void *compressed_data, size_t compressed_size,
-               void *uncompressed_data, size_t uncompressed_size, void *_ctx)
+lzms_decompress(const void *in, size_t in_nbytes, void *out, size_t out_nbytes,
+               void *_d)
 {
-       struct lzms_decompressor *ctx = _ctx;
+       struct lzms_decompressor *d = _d;
 
-       /* The range decoder requires that a minimum of 4 bytes of compressed
-        * data be initially available.  */
-       if (compressed_size < 4) {
-               LZMS_DEBUG("Compressed size too small (got %zu, expected >= 4)",
-                          compressed_size);
-               return -1;
-       }
-
-       /* An LZMS-compressed data block should be evenly divisible into 16-bit
-        * integers.  */
-       if (compressed_size % 2 != 0) {
-               LZMS_DEBUG("Compressed size not divisible by 2 (got %zu)",
-                          compressed_size);
+       /*
+        * Requirements on the compressed data:
+        *
+        * 1. LZMS-compressed data is a series of 16-bit integers, so the
+        *    compressed data buffer cannot take up an odd number of bytes.
+        * 2. To prevent poor performance on some architectures, we require that
+        *    the compressed data buffer is 2-byte aligned.
+        * 3. There must be at least 4 bytes of compressed data, since otherwise
+        *    we cannot even initialize the range decoder.
+        */
+       if ((in_nbytes & 1) || ((uintptr_t)in & 1) || (in_nbytes < 4))
                return -1;
-       }
 
-       /* Handle the trivial case where nothing needs to be decompressed.
-        * (Necessary because a window of size 0 does not have a valid offset
-        * slot.)  */
-       if (uncompressed_size == 0)
-               return 0;
+       lzms_init_decompressor(d, in, in_nbytes,
+                              lzms_get_num_offset_slots(out_nbytes));
 
-       /* Decode the literals and matches.  */
-       if (lzms_decode_items(compressed_data, compressed_size,
-                             uncompressed_data, uncompressed_size, ctx))
+       if (lzms_decode_items(d, out, out_nbytes))
                return -1;
 
-       /* Postprocess the data.  */
-       lzms_x86_filter(uncompressed_data, uncompressed_size,
-                       ctx->last_target_usages, true);
-
-       LZMS_DEBUG("Decompression successful.");
+       lzms_x86_filter(out, out_nbytes, d->last_target_usages, true);
        return 0;
 }
 
 static void
-lzms_free_decompressor(void *_ctx)
-{
-       struct lzms_decompressor *ctx = _ctx;
-
-       ALIGNED_FREE(ctx);
-}
-
-static int
-lzms_create_decompressor(size_t max_block_size, void **ctx_ret)
+lzms_free_decompressor(void *_d)
 {
-       struct lzms_decompressor *ctx;
+       struct lzms_decompressor *d = _d;
 
-       /* The x86 post-processor requires that the uncompressed length fit into
-        * a signed 32-bit integer.  Also, the offset slot table cannot be
-        * searched for an offset of INT32_MAX or greater.  */
-       if (max_block_size >= INT32_MAX)
-               return WIMLIB_ERR_INVALID_PARAM;
-
-       ctx = ALIGNED_MALLOC(sizeof(struct lzms_decompressor),
-                            DECODE_TABLE_ALIGNMENT);
-       if (ctx == NULL)
-               return WIMLIB_ERR_NOMEM;
-
-       /* Initialize offset and length slot data if not done already.  */
-       lzms_init_slots();
-
-       *ctx_ret = ctx;
-       return 0;
+       ALIGNED_FREE(d);
 }
 
 const struct decompressor_ops lzms_decompressor_ops = {