* 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
* 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.
*
- * A LZMS-compressed block seemingly cannot have a compressed size greater than
+ * 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
* 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. */
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!");
}
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;
}
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