* 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
* 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
* 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.
*
* 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
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.
*/
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
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. */
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)
{
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)",
{
struct lzms_decompressor *ctx = _ctx;
- FREE(ctx);
+ ALIGNED_FREE(ctx);
}
static int
{
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;
git://wimlib.net / wimlib / blobdiff