* XXX: This is mostly duplicated in lzms_decode_huffman_symbol() in
* lzms_decompress.c. */
static inline unsigned
-read_huffsym(struct input_bitstream *istream, const u16 decode_table[],
+read_huffsym(struct input_bitstream *is, const u16 decode_table[],
unsigned table_bits, unsigned max_codeword_len)
{
unsigned entry;
- unsigned key_bits;
- bitstream_ensure_bits(istream, max_codeword_len);
+ bitstream_ensure_bits(is, max_codeword_len);
/* Index the decode table by the next table_bits bits of the input. */
- key_bits = bitstream_peek_bits(istream, table_bits);
- entry = decode_table[key_bits];
- if (likely(table_bits >= max_codeword_len || 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. */
- bitstream_remove_bits(istream, entry >> 11);
- return entry & 0x7FF;
- } else {
- /* 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 to decode the symbol. */
- bitstream_remove_bits(istream, table_bits);
- do {
- key_bits = (entry & 0x3FFF) + bitstream_pop_bits(istream, 1);
- } while ((entry = decode_table[key_bits]) >= 0xC000);
- return entry;
+ entry = decode_table[bitstream_peek_bits(is, table_bits)];
+ if (max_codeword_len > table_bits && (entry & 0x8000)) {
+ /* Subtable required */
+ unsigned subtable_start = (entry & 0xFFF);
+ unsigned subtable_bits = (entry >> 12) & 0x7;
+ bitstream_remove_bits(is, table_bits);
+ entry = decode_table[(1U << table_bits) + subtable_start +
+ bitstream_peek_bits(is, subtable_bits)];
}
+ bitstream_remove_bits(is, entry >> 11);
+ return entry & 0x7FF;
}
extern int
void *decode_table_ptr;
unsigned sym_idx;
unsigned codeword_len;
- unsigned decode_table_pos;
/* Count how many symbols have each codeword length, including 0. */
for (unsigned len = 0; len <= max_codeword_len; len++)
}
}
- /* If we've filled in the entire table, we are done. Otherwise,
- * there are codewords longer than table_bits for which we must
- * generate binary trees. */
+ unsigned codeword = ((u16 *)decode_table_ptr - decode_table) << 1;
+ unsigned cur_subtable_pos = table_num_entries;
+ unsigned cur_subtable_bits = table_bits;
+ unsigned cur_subtable_prefix = -1;
- decode_table_pos = (u16 *)decode_table_ptr - decode_table;
- if (decode_table_pos != table_num_entries) {
- unsigned j;
- unsigned next_free_tree_slot;
- unsigned cur_codeword;
+ /* Fill in the remaining entries if any. These entries will require
+ * subtables. */
+ while (sym_idx < num_syms) {
- /* First, zero out the remaining entries. This is
- * necessary so that these entries appear as
- * "unallocated" in the next part. Each of these entries
- * will eventually be filled with the representation of
- * the root node of a binary tree. */
- j = decode_table_pos;
- do {
- decode_table[j] = 0;
- } while (++j != table_num_entries);
+ while (len_counts[codeword_len] == 0) {
+ codeword_len++;
+ codeword <<= 1;
+ }
- /* We allocate child nodes starting at the end of the
- * direct lookup table. Note that there should be
- * 2*num_syms extra entries for this purpose, although
- * fewer than this may actually be needed. */
- next_free_tree_slot = table_num_entries;
+ unsigned prefix = codeword >> (codeword_len - table_bits);
- /* Iterate through each codeword with length greater than
- * 'table_bits', primarily in order of codeword length
- * and secondarily in order of symbol. */
- for (cur_codeword = decode_table_pos << 1;
- codeword_len <= max_codeword_len;
- codeword_len++, cur_codeword <<= 1)
- {
- unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
- for (; sym_idx < end_sym_idx; sym_idx++, cur_codeword++)
- {
- /* 'sym' is the symbol represented by the
- * codeword. */
- unsigned sym = sorted_syms[sym_idx];
+ /* Start a new subtable if the first 'table_bits' bits of the
+ * codeword don't match the prefix for the previous subtable, or
+ * if this will be the first subtable. */
+ if (prefix != cur_subtable_prefix) {
- unsigned extra_bits = codeword_len - table_bits;
+ cur_subtable_prefix = prefix;
- unsigned node_idx = cur_codeword >> extra_bits;
+ /* Calculate the subtable length. If the codeword
+ * length exceeds 'table_bits' by n, the subtable needs
+ * at least 2**n entries. But it may need more; if
+ * there are fewer than 2**n codewords of length
+ * 'table_bits + n' remaining, then n will need to be
+ * incremented to bring in longer codewords until the
+ * subtable can be filled completely. Note that it
+ * always will, eventually, be possible to fill the
+ * subtable, since the only case where we may have an
+ * incomplete code is a single codeword of length 1,
+ * and that never requires any subtables. */
+ cur_subtable_bits = codeword_len - table_bits;
+ remainder = (s32)1 << cur_subtable_bits;
+ for (;;) {
+ remainder -= len_counts[table_bits +
+ cur_subtable_bits];
+ if (remainder <= 0)
+ break;
+ cur_subtable_bits++;
+ remainder <<= 1;
+ }
- /* Go through each bit of the current codeword
- * beyond the prefix of length @table_bits and
- * walk the appropriate binary tree, allocating
- * any slots that have not yet been allocated.
- *
- * Note that the 'pointer' entry to the binary
- * tree, which is stored in the direct lookup
- * portion of the table, is represented
- * identically to other internal (non-leaf)
- * nodes of the binary tree; it can be thought
- * of as simply the root of the tree. The
- * representation of these internal nodes is
- * simply the index of the left child combined
- * with the special bits 0xC000 to distinguish
- * the entry from direct mapping and leaf node
- * entries. */
- do {
+ /* Create the entry that points from the main table to
+ * the subtable. This entry contains the index of the
+ * start of the subtable and the number of bits with
+ * which the subtable is indexed (the log base 2 of the
+ * number of entries it contains). */
+ decode_table[cur_subtable_prefix] =
+ 0x8000 | (cur_subtable_bits << 12) |
+ (cur_subtable_pos - table_num_entries);
+ }
- /* At least one bit remains in the
- * codeword, but the current node is an
- * unallocated leaf. Change it to an
- * internal node. */
- if (decode_table[node_idx] == 0) {
- decode_table[node_idx] =
- next_free_tree_slot | 0xC000;
- decode_table[next_free_tree_slot++] = 0;
- decode_table[next_free_tree_slot++] = 0;
- }
+ u16 entry = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx],
+ codeword_len - table_bits);
+ unsigned n = 1 << (cur_subtable_bits - (codeword_len - table_bits));
- /* Go to the left child if the next bit
- * in the codeword is 0; otherwise go to
- * the right child. */
- node_idx = decode_table[node_idx] & 0x3FFF;
- --extra_bits;
- node_idx += (cur_codeword >> extra_bits) & 1;
- } while (extra_bits != 0);
+ do {
+ decode_table[cur_subtable_pos++] = entry;
+ } while (--n);
- /* We've traversed the tree using the entire
- * codeword, and we're now at the entry where
- * the actual symbol will be stored. This is
- * distinguished from internal nodes by not
- * having its high two bits set. */
- decode_table[node_idx] = sym;
- }
- }
+ /* Advance to the next symbol. This will either increase the
+ * codeword length, or keep the same codeword length but
+ * increase the symbol value. Note: since we are using
+ * bit-reversed codewords, we don't need to explicitly append
+ * zeroes to the codeword when the codeword length increases. */
+ ++sym_idx;
+ len_counts[codeword_len]--;
+ codeword++;
}
+
return 0;
}
unsigned table_bits;
};
+static void _unused_attribute
+check_enough_values(void)
+{
+/* ./enough 256 10 15 */
+#define LZMS_LITERAL_ENOUGH 1302
+ STATIC_ASSERT(LZMS_NUM_LITERAL_SYMS == 256);
+ STATIC_ASSERT(LZMS_LITERAL_TABLEBITS == 10);
+ STATIC_ASSERT(LZMS_MAX_CODEWORD_LENGTH == 15);
+
+/* ./enough 54 10 15 */
+#define LZMS_LENGTH_ENOUGH 1098
+ STATIC_ASSERT(LZMS_NUM_LENGTH_SYMS == 54);
+ STATIC_ASSERT(LZMS_LENGTH_TABLEBITS == 10);
+ STATIC_ASSERT(LZMS_MAX_CODEWORD_LENGTH == 15);
+
+/* ./enough 799 10 15 */
+#define LZMS_LZ_OFFSET_ENOUGH 1846
+ STATIC_ASSERT(LZMS_MAX_NUM_OFFSET_SYMS == 799);
+ STATIC_ASSERT(LZMS_LZ_OFFSET_TABLEBITS == 10);
+ STATIC_ASSERT(LZMS_MAX_CODEWORD_LENGTH == 15);
+
+/* ./enough 799 10 15 */
+#define LZMS_DELTA_OFFSET_ENOUGH 1846
+ STATIC_ASSERT(LZMS_MAX_NUM_OFFSET_SYMS == 799);
+ STATIC_ASSERT(LZMS_DELTA_OFFSET_TABLEBITS == 10);
+ STATIC_ASSERT(LZMS_MAX_CODEWORD_LENGTH == 15);
+
+/* ./enough 8 7 15 */
+#define LZMS_DELTA_POWER_ENOUGH 128
+ STATIC_ASSERT(LZMS_NUM_DELTA_POWER_SYMS == 8);
+ STATIC_ASSERT(LZMS_DELTA_POWER_TABLEBITS == 7);
+ STATIC_ASSERT(LZMS_MAX_CODEWORD_LENGTH == 15);
+}
+
struct lzms_decompressor {
/* 'last_target_usages' is in union with everything else because it is
struct lzms_probabilites probs;
- u16 literal_decode_table[(1 << LZMS_LITERAL_TABLEBITS) +
- (2 * LZMS_NUM_LITERAL_SYMS)]
+ u16 literal_decode_table[LZMS_LITERAL_ENOUGH]
_aligned_attribute(DECODE_TABLE_ALIGNMENT);
u32 literal_freqs[LZMS_NUM_LITERAL_SYMS];
struct lzms_huffman_rebuild_info literal_rebuild_info;
- u16 lz_offset_decode_table[(1 << LZMS_LZ_OFFSET_TABLEBITS) +
- ( 2 * LZMS_MAX_NUM_OFFSET_SYMS)]
+ u16 lz_offset_decode_table[LZMS_LZ_OFFSET_ENOUGH]
_aligned_attribute(DECODE_TABLE_ALIGNMENT);
u32 lz_offset_freqs[LZMS_MAX_NUM_OFFSET_SYMS];
struct lzms_huffman_rebuild_info lz_offset_rebuild_info;
- u16 length_decode_table[(1 << LZMS_LENGTH_TABLEBITS) +
- (2 * LZMS_NUM_LENGTH_SYMS)]
+ u16 length_decode_table[LZMS_LENGTH_ENOUGH]
_aligned_attribute(DECODE_TABLE_ALIGNMENT);
u32 length_freqs[LZMS_NUM_LENGTH_SYMS];
struct lzms_huffman_rebuild_info length_rebuild_info;
- u16 delta_offset_decode_table[(1 << LZMS_DELTA_OFFSET_TABLEBITS) +
- (2 * LZMS_MAX_NUM_OFFSET_SYMS)]
+ u16 delta_offset_decode_table[LZMS_DELTA_OFFSET_ENOUGH]
_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)]
+ u16 delta_power_decode_table[LZMS_DELTA_POWER_ENOUGH]
_aligned_attribute(DECODE_TABLE_ALIGNMENT);
u32 delta_power_freqs[LZMS_NUM_DELTA_POWER_SYMS];
struct lzms_huffman_rebuild_info delta_power_rebuild_info;
unsigned table_bits, u32 freqs[],
struct lzms_huffman_rebuild_info *rebuild_info)
{
- unsigned key_bits;
unsigned entry;
unsigned sym;
lzms_ensure_bits(is, LZMS_MAX_CODEWORD_LENGTH);
/* Index the decode table by the next table_bits bits of the input. */
- 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_remove_bits(is, entry >> 11);
- sym = entry & 0x7FF;
- } else {
- /* 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. */
+ entry = decode_table[lzms_peek_bits(is, table_bits)];
+ if (entry & 0x8000) {
+ /* Subtable required */
+ unsigned subtable_start = (entry & 0xFFF);
+ unsigned subtable_bits = (entry >> 12) & 0x7;
lzms_remove_bits(is, table_bits);
- do {
- key_bits = (entry & 0x3FFF) + lzms_pop_bits(is, 1);
- } while ((entry = decode_table[key_bits]) >= 0xC000);
- sym = entry;
+ entry = decode_table[(1U << table_bits) + subtable_start +
+ lzms_peek_bits(is, subtable_bits)];
}
+ lzms_remove_bits(is, entry >> 11);
+ sym = entry & 0x7FF;
freqs[sym]++;
if (--rebuild_info->num_syms_until_rebuild == 0)
#define LZX_PRECODE_TABLEBITS 6
#define LZX_ALIGNEDCODE_TABLEBITS 7
+static void _unused_attribute
+check_enough_values(void)
+{
+/* ./enough 656 11 16 */
+#define LZX_MAINCODE_ENOUGH 2726
+ STATIC_ASSERT(LZX_MAINCODE_MAX_NUM_SYMBOLS == 656);
+ STATIC_ASSERT(LZX_MAINCODE_TABLEBITS == 11);
+ STATIC_ASSERT(LZX_MAX_MAIN_CODEWORD_LEN == 16);
+
+/* ./enough 249 10 16 */
+#define LZX_LENCODE_ENOUGH 1326
+ STATIC_ASSERT(LZX_LENCODE_NUM_SYMBOLS == 249);
+ STATIC_ASSERT(LZX_LENCODE_TABLEBITS == 10);
+ STATIC_ASSERT(LZX_MAX_LEN_CODEWORD_LEN == 16);
+
+/* ./enough 20 6 15 */
+#define LZX_PRECODE_ENOUGH 582
+ STATIC_ASSERT(LZX_PRECODE_NUM_SYMBOLS == 20);
+ STATIC_ASSERT(LZX_PRECODE_TABLEBITS == 6);
+ STATIC_ASSERT(LZX_MAX_PRE_CODEWORD_LEN == 15);
+
+/* ./enough 8 7 7 */
+#define LZX_ALIGNEDCODE_ENOUGH 128
+ STATIC_ASSERT(LZX_ALIGNEDCODE_NUM_SYMBOLS == 8);
+ STATIC_ASSERT(LZX_ALIGNEDCODE_TABLEBITS == 7);
+ STATIC_ASSERT(LZX_MAX_ALIGNED_CODEWORD_LEN == 7);
+}
+
+
#define LZX_READ_LENS_MAX_OVERRUN 50
/* Reusable heap-allocated memory for LZX decompression */
struct lzx_decompressor {
- /* Huffman decoding tables, and arrays that map symbols to codeword
- * lengths */
+ /* Huffman decoding tables and codeword lengths */
- u16 maincode_decode_table[(1 << LZX_MAINCODE_TABLEBITS) +
- (LZX_MAINCODE_MAX_NUM_SYMBOLS * 2)]
- _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+ u16 maincode_decode_table[LZX_MAINCODE_ENOUGH]
+ _aligned_attribute(DECODE_TABLE_ALIGNMENT);
u8 maincode_lens[LZX_MAINCODE_MAX_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
-
- u16 lencode_decode_table[(1 << LZX_LENCODE_TABLEBITS) +
- (LZX_LENCODE_NUM_SYMBOLS * 2)]
- _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+ u16 lencode_decode_table[LZX_LENCODE_ENOUGH]
+ _aligned_attribute(DECODE_TABLE_ALIGNMENT);
u8 lencode_lens[LZX_LENCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
union {
- u16 alignedcode_decode_table[(1 << LZX_ALIGNEDCODE_TABLEBITS) +
- (LZX_ALIGNEDCODE_NUM_SYMBOLS * 2)]
- _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+ u16 alignedcode_decode_table[LZX_ALIGNEDCODE_ENOUGH]
+ _aligned_attribute(DECODE_TABLE_ALIGNMENT);
u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS];
};
union {
- u16 precode_decode_table[(1 << LZX_PRECODE_TABLEBITS) +
- (LZX_PRECODE_NUM_SYMBOLS * 2)]
- _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+ u16 precode_decode_table[LZX_PRECODE_ENOUGH]
+ _aligned_attribute(DECODE_TABLE_ALIGNMENT);
u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
};
/* This value is chosen for fast decompression. */
#define XPRESS_TABLEBITS 12
+static void _unused_attribute
+check_enough_values(void)
+{
+/* ./enough 512 12 15 */
+#define XPRESS_ENOUGH 4606
+ STATIC_ASSERT(XPRESS_NUM_SYMBOLS == 512);
+ STATIC_ASSERT(XPRESS_TABLEBITS == 12);
+ STATIC_ASSERT(XPRESS_MAX_CODEWORD_LEN == 15);
+}
+
static int
xpress_decompress(const void *restrict compressed_data, size_t compressed_size,
void *restrict uncompressed_data, size_t uncompressed_size,
u8 *out_next = out_begin;
u8 * const out_end = out_begin + uncompressed_size;
union {
- u16 decode_table[(1 << XPRESS_TABLEBITS) + 2 * XPRESS_NUM_SYMBOLS]
- _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+ u16 decode_table[XPRESS_ENOUGH];
u8 lens[XPRESS_NUM_SYMBOLS];
} u;
struct input_bitstream is;
git://wimlib.net / wimlib / commitdiff