X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms-decompress.c;h=f8bfcdb17344b3055d343e7be7615897484d7bfc;hb=9ca5c20853d3be06378fb985aa75c75df280d1e2;hp=1516e364d842f72059332430c5177353b40fd963;hpb=2fdc3bd720f5bc49680dc2284ea42a537d1acc07;p=wimlib diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index 1516e364..f8bfcdb1 100644 --- a/src/lzms-decompress.c +++ b/src/lzms-decompress.c @@ -160,18 +160,28 @@ * have equal frequency. Following that, each code must be rebuilt whenever a * certain number of symbols has been decoded with it. * - * In general, multiple valid Huffman codes can be constructed from a set of - * symbol frequencies. Like other compression formats such as XPRESS, LZX, and - * DEFLATE, the LZMS format solves this ambiguity by requiring 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. + * 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. * - * Codewords in all the LZMS Huffman codes are limited to 15 bits. If the - * canonical code for a given set of symbol frequencies has any codewords longer - * than 15 bits, then all frequencies must be divided by 2, rounding up, and the - * code construction must be attempted again. + * 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. + * + * Codewords in LZMS are guaranteed to not exceed 15 bits. The format otherwise + * places no restrictions on codeword length. Therefore, the Huffman code + * construction algorithm that a correct LZMS decompressor uses need not + * implement length-limited code construction. But if it does (e.g. by virtue + * of being shared among multiple compression algorithms), the details of how it + * 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 @@ -190,10 +200,10 @@ # include "config.h" #endif -#include "wimlib.h" #include "wimlib/compress_common.h" #include "wimlib/decompressor_ops.h" #include "wimlib/decompress_common.h" +#include "wimlib/error.h" #include "wimlib/lzms.h" #include "wimlib/util.h" @@ -304,7 +314,7 @@ struct lzms_huffman_decoder { u8 lens[LZMS_MAX_NUM_SYMS]; /* The codeword of each symbol in the Huffman code. */ - u16 codewords[LZMS_MAX_NUM_SYMS]; + u32 codewords[LZMS_MAX_NUM_SYMS]; /* A table for quickly decoding symbols encoded using the Huffman code. */ @@ -568,9 +578,11 @@ lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec) static u32 lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec) { - const u8 *lens = dec->lens; 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 @@ -588,28 +600,31 @@ lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec) dec->num_syms_read = 0; } - /* In the following Huffman decoding implementation, the first - * LZMS_DECODE_TABLE_BITS of the input are used as an offset into a - * decode table. The entry will either provide the decoded symbol - * directly, or else a "real" Huffman binary tree will be searched to - * decode the symbol. */ - + /* 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); - u16 key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_TABLE_BITS); - u16 sym = decode_table[key_bits]; - - if (sym < dec->num_syms) { - /* Fast case: The decode table directly provided the symbol. */ - lzms_input_bitstream_remove_bits(is, lens[sym]); + /* 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); + 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); + sym = entry & 0x7FF; } else { - /* Slow case: The symbol took too many bits to include directly - * in the decode table, so search for it in a binary tree at the - * end of the decode table. */ + /* Slow case: The codeword for the symbol is longer than + * table_bits, so the symbol does not have an entry directly in + * 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); do { - key_bits = sym + lzms_input_bitstream_pop_bits(is, 1); - } while ((sym = decode_table[key_bits]) >= dec->num_syms); + key_bits = (entry & 0x3FFF) + lzms_input_bitstream_pop_bits(is, 1); + } while ((entry = decode_table[key_bits]) >= 0xC000); + sym = entry; } /* Tally and return the decoded symbol. */ @@ -659,7 +674,6 @@ static int lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset) { u8 *out_next; - u8 *matchptr; if (length > ctx->out_end - ctx->out_next) { LZMS_DEBUG("Match overrun!"); @@ -671,11 +685,10 @@ lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset) } out_next = ctx->out_next; - matchptr = out_next - offset; - while (length--) - *out_next++ = *matchptr++; - ctx->out_next = out_next; + lz_copy(out_next, length, offset, ctx->out_end); + ctx->out_next = out_next + length; + return 0; } @@ -1027,17 +1040,16 @@ lzms_free_decompressor(void *_ctx) { struct lzms_decompressor *ctx = _ctx; - FREE(ctx); + ALIGNED_FREE(ctx); } static int -lzms_create_decompressor(size_t max_block_size, - const struct wimlib_decompressor_params_header *params, - void **ctx_ret) +lzms_create_decompressor(size_t max_block_size, void **ctx_ret) { struct lzms_decompressor *ctx; - ctx = MALLOC(sizeof(struct lzms_decompressor)); + ctx = ALIGNED_MALLOC(sizeof(struct lzms_decompressor), + DECODE_TABLE_ALIGNMENT); if (ctx == NULL) return WIMLIB_ERR_NOMEM;