X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms-decompress.c;h=2bc1c754cd69e49b86c17cce9e934ed888392cd4;hb=394751ae13025edab605cd61c8e32819e3fb33a1;hp=32ce082c29b1ebb6a5940a60619d74c7bbfe3d74;hpb=abe65b1f2f12bcedec1103cc7924897720f919be;p=wimlib diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index 32ce082c..2bc1c754 100644 --- a/src/lzms-decompress.c +++ b/src/lzms-decompress.c @@ -35,7 +35,7 @@ * is a container format from which the locations and sizes (both compressed and * uncompressed) of the constituent blocks can be determined. * - * A LZMS-compressed block must be read in 16-bit little endian units from both + * 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 @@ -65,7 +65,7 @@ * offset is 1, regardless of match length. * * For LZ matches, up to 3 repeat offsets are allowed, similar to some other - * LZ-based formats such as LZX and LZMA. They must updated in a LRU fashion, + * LZ-based formats such as LZX and LZMA. They must updated in an LRU fashion, * except for a quirk: updates to the queue must be delayed by one LZMS item, * except for the removal of a repeat match. As a result, 4 entries are * actually needed in the queue, even though it is only possible to decode @@ -173,7 +173,7 @@ * than 15 bits, then all frequencies must be divided by 2, rounding up, and the * code construction must be attempted again. * - * A LZMS-compressed block seemingly cannot have a compressed size greater than + * 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. * @@ -232,7 +232,7 @@ struct lzms_input_bitstream { * at a time, this needs to be 64 bits rather than 32 bits. */ u64 bitbuf; - /* Number of bits in @bitbuf that are are used. */ + /* Number of bits in @bitbuf that are used. */ unsigned num_filled_bits; /* Pointer to the one past the next little-endian 16-bit integer in the @@ -304,7 +304,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. */ @@ -347,8 +347,8 @@ struct lzms_decompressor { 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; + /* LRU (least-recently-used) queues for match information. */ + struct lzms_lru_queues lru; /* Used for postprocessing. */ s32 last_target_usages[65536]; @@ -568,9 +568,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 +590,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. */ @@ -796,7 +801,7 @@ lzms_decode_delta_match(struct lzms_decompressor *ctx) return lzms_copy_delta_match(ctx, length, power, raw_offset); } -/* Decode a LZ or delta match. */ +/* Decode an LZ or delta match. */ static int lzms_decode_match(struct lzms_decompressor *ctx) { @@ -833,7 +838,7 @@ lzms_decode_item(struct lzms_decompressor *ctx) if (ret) return ret; - lzms_update_lru_queues(&ctx->lru); + lzms_update_lru_queues(&ctx->lru); return 0; } @@ -948,7 +953,7 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, &ctx->rd, LZMS_NUM_DELTA_REPEAT_MATCH_STATES); /* Initialize LRU match information. */ - lzms_init_lru_queues(&ctx->lru); + lzms_init_lru_queues(&ctx->lru); LZMS_DEBUG("Decompressor successfully initialized"); } @@ -985,7 +990,7 @@ lzms_decompress(const void *compressed_data, size_t compressed_size, return -1; } - /* A LZMS-compressed data block should be evenly divisible into 16-bit + /* 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)",