From: Eric Biggers Date: Fri, 26 Dec 2014 16:56:16 +0000 (-0600) Subject: LZMS: decompression optimizations X-Git-Tag: v1.7.4~9 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=855b49ef85d274588a2848d9c69974f9b88d343a LZMS: decompression optimizations --- diff --git a/NEWS b/NEWS index ff832a57..b5f7be59 100644 --- 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. diff --git a/include/wimlib/compiler-gcc.h b/include/wimlib/compiler-gcc.h index db6e3249..46983308 100644 --- a/include/wimlib/compiler-gcc.h +++ b/include/wimlib/compiler-gcc.h @@ -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__) diff --git a/include/wimlib/compiler.h b/include/wimlib/compiler.h index a1f513f5..11eaa239 100644 --- a/include/wimlib/compiler.h +++ b/include/wimlib/compiler.h @@ -54,6 +54,10 @@ # 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 diff --git a/include/wimlib/lzms.h b/include/wimlib/lzms.h index 94bcba82..91a0e1ba 100644 --- a/include/wimlib/lzms.h +++ b/include/wimlib/lzms.h @@ -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 diff --git a/include/wimlib/lzms_constants.h b/include/wimlib/lzms_constants.h index 7f872901..aa22aaf2 100644 --- a/include/wimlib/lzms_constants.h +++ b/include/wimlib/lzms_constants.h @@ -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 diff --git a/src/lzms-common.c b/src/lzms-common.c index ee479903..eaa237fa 100644 --- a/src/lzms-common.c +++ b/src/lzms-common.c @@ -23,29 +23,300 @@ # 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 - -/*************************************************************** - * 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); -} diff --git a/src/lzms-compress.c b/src/lzms-compress.c index 3686db0a..5f5e3741 100644 --- a/src/lzms-compress.c +++ b/src/lzms-compress.c @@ -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); diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index 96c501aa..b56c4ffa 100644 --- a/src/lzms-decompress.c +++ b/src/lzms-decompress.c @@ -29,18 +29,18 @@ * 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 @@ -51,14 +51,14 @@ * 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. * @@ -81,27 +81,27 @@ * 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 @@ -159,25 +159,24 @@ * 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 @@ -187,10 +186,6 @@ * 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. @@ -209,16 +204,17 @@ #include "wimlib/decompress_common.h" #include "wimlib/error.h" #include "wimlib/lzms.h" -#include "wimlib/unaligned.h" #include "wimlib/util.h" -#include +/* 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) != 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 = {