* decompress_common.c
*
* Code for decompression shared among multiple compression formats.
- */
-
-/*
- * Copyright (C) 2012, 2013 Eric Biggers
*
- * This file is part of wimlib, a library for working with WIM files.
+ * The following copying information applies to this specific source code file:
+ *
+ * Written in 2012-2016 by Eric Biggers <ebiggers3@gmail.com>
*
- * wimlib is free software; you can redistribute it and/or modify it under the
- * terms of the GNU General Public License as published by the Free
- * Software Foundation; either version 3 of the License, or (at your option)
- * any later version.
+ * To the extent possible under law, the author(s) have dedicated all copyright
+ * and related and neighboring rights to this software to the public domain
+ * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
+ * Dedication (the "CC0").
*
- * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
- * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
- * A PARTICULAR PURPOSE. See the GNU General Public License for more
- * details.
+ * This software is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
*
- * You should have received a copy of the GNU General Public License
- * along with wimlib; if not, see http://www.gnu.org/licenses/.
+ * You should have received a copy of the CC0 along with this software; if not
+ * see <http://creativecommons.org/publicdomain/zero/1.0/>.
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
-#include "wimlib/decompress_common.h"
-#include "wimlib/error.h"
-#include "wimlib/util.h"
-
#include <string.h>
-#ifdef __GNUC__
-# ifdef __SSE2__
-# define USE_SSE2_FILL
-# include <emmintrin.h>
-# else
-# define USE_LONG_FILL
-# endif
+#ifdef __SSE2__
+# include <emmintrin.h>
#endif
+#include "wimlib/decompress_common.h"
+
/*
- * make_huffman_decode_table: - Builds a fast huffman decoding table from an
- * array that gives the length of the codeword for each symbol in the alphabet.
- * Originally based on code written by David Tritscher (taken the original LZX
- * decompression code); also heavily modified to add some optimizations used in
- * the zlib code, as well as more comments; also added some optimizations to
- * make filling in the decode table entries faster (may not help significantly
- * though).
+ * make_huffman_decode_table() -
+ *
+ * Given an alphabet of symbols and the length of each symbol's codeword in a
+ * canonical prefix code, build a table for quickly decoding symbols that were
+ * encoded with that code.
+ *
+ * A _prefix code_ is an assignment of bitstrings called _codewords_ to symbols
+ * such that no whole codeword is a prefix of any other. A prefix code might be
+ * a _Huffman code_, which means that it is an optimum prefix code for a given
+ * list of symbol frequencies and was generated by the Huffman algorithm.
+ * Although the prefix codes processed here will ordinarily be "Huffman codes",
+ * strictly speaking the decoder cannot know whether a given code was actually
+ * generated by the Huffman algorithm or not.
+ *
+ * A prefix code is _canonical_ if and only if a longer codeword never
+ * lexicographically precedes a shorter codeword, and the lexicographic ordering
+ * of codewords of equal length is the same as the lexicographic ordering of the
+ * corresponding symbols. The advantage of using a canonical prefix code is
+ * that the codewords can be reconstructed from only the symbol => codeword
+ * length mapping. This eliminates the need to transmit the codewords
+ * explicitly. Instead, they can be enumerated in lexicographic order after
+ * sorting the symbols primarily by increasing codeword length and secondarily
+ * by increasing symbol value.
*
- * @decode_table: The array in which to create the fast huffman decoding
- * table. It must have a length of at least
- * (2**table_bits) + 2 * num_syms to guarantee
- * that there is enough space. Also must be 16-byte
- * aligned (at least when USE_SSE2_FILL gets defined).
+ * However, the decoder's real goal is to decode symbols with the code, not just
+ * generate the list of codewords. Consequently, this function directly builds
+ * a table for efficiently decoding symbols using the code. The basic idea is
+ * that given the next 'max_codeword_len' bits of input, the decoder can look up
+ * the next decoded symbol by indexing a table containing '2^max_codeword_len'
+ * entries. A codeword with length 'max_codeword_len' will have exactly one
+ * entry in this table, whereas a codeword shorter than 'max_codeword_len' will
+ * have multiple entries in this table. Precisely, a codeword of length 'n'
+ * will have '2^(max_codeword_len - n)' entries. The index of each such entry,
+ * considered as a bitstring of length 'max_codeword_len', will contain the
+ * corresponding codeword as a prefix.
*
- * @num_syms: Number of symbols in the alphabet, including symbols
- * that do not appear in this particular input chunk.
+ * That's the basic idea, but we extend it in two ways:
*
- * @table_bits: Any symbols with a code length of table_bits or less can
- * be decoded in one lookup of the table. 2**table_bits
- * must be greater than or equal to @num_syms if there are
- * any Huffman codes longer than @table_bits.
+ * - Often the maximum codeword length is too long for it to be efficient to
+ * build the full decode table whenever a new code is used. Instead, we build
+ * a "root" table using only '2^table_bits' entries, where 'table_bits <=
+ * max_codeword_len'. Then, a lookup of 'table_bits' bits produces either a
+ * symbol directly (for codewords not longer than 'table_bits'), or the index
+ * of a subtable which must be indexed with additional bits of input to fully
+ * decode the symbol (for codewords longer than 'table_bits').
*
- * @lens: An array of length @num_syms, indexable by symbol, that
- * gives the length of the Huffman codeword for that
- * symbol. Because the Huffman tree is in canonical form,
- * it can be reconstructed by only knowing the length of
- * the codeword for each symbol. It is assumed, but not
- * checked, that every length is less than
- * @max_codeword_len.
+ * - Whenever the decoder decodes a symbol, it needs to know the codeword length
+ * so that it can remove the appropriate number of input bits. The obvious
+ * solution would be to simply retain the codeword lengths array and use the
+ * decoded symbol as an index into it. However, that would require two array
+ * accesses when decoding each symbol. Our strategy is to instead store the
+ * codeword length directly in the decode table entry along with the symbol.
*
- * @max_codeword_len: The longest codeword length allowed in the compression
- * format.
+ * See MAKE_DECODE_TABLE_ENTRY() for full details on the format of decode table
+ * entries, and see read_huffsym() for full details on how symbols are decoded.
*
- * Returns 0 on success; returns -1 if the length values do not correspond to a
- * valid Huffman tree.
+ * @decode_table:
+ * The array in which to build the decode table. This must have been
+ * declared by the DECODE_TABLE() macro. This may alias @lens, since all
+ * @lens are consumed before the decode table is written to.
*
- * The format of the Huffamn decoding table is as follows. The first (1 <<
- * table_bits) entries of the table are indexed by chunks of the input of size
- * @table_bits. If the next Huffman codeword in the input happens to have a
- * length of exactly @table_bits, the symbol is simply read directly from the
- * decoding table. Alternatively, if the next Huffman codeword has length _less
- * than_ @table_bits, the symbol is also read directly from the decode table;
- * this is possible because every entry in the table that is indexed by an
- * integer that has the shorter codeword as a binary prefix is filled in with
- * the appropriate symbol. If a codeword has length n <= table_bits, it will
- * have 2**(table_bits - n) possible suffixes, and thus that many entries in the
- * decoding table.
+ * @num_syms:
+ * The number of symbols in the alphabet.
*
- * It's a bit more complicated if the next Huffman codeword has length of more
- * than @table_bits. The table entry indexed by the first @table_bits of that
- * codeword cannot give the appropriate symbol directly, because that entry is
- * guaranteed to be referenced by the Huffman codewords of multiple symbols.
- * And while the LZX compression format does not allow codes longer than 16
- * bits, a table of size (2 ** 16) = 65536 entries would be too slow to create.
+ * @table_bits:
+ * The log base 2 of the number of entries in the root table.
*
- * There are several different ways to make it possible to look up the symbols
- * for codewords longer than @table_bits. One way is to make the entries for
- * the prefixes of length @table_bits of those entries be pointers to additional
- * decoding tables that are indexed by some number of additional bits of the
- * codeword. The technique used here is a bit simpler, however: just store the
- * needed subtrees of the Huffman tree in the decoding table after the lookup
- * entries, beginning at index (2**table_bits). Real pointers are replaced by
- * indices into the decoding table, and symbol entries are distinguished from
- * pointers by the fact that values less than @num_syms must be symbol values.
+ * @lens:
+ * An array of length @num_syms, indexed by symbol, that gives the length
+ * of the codeword, in bits, for each symbol. The length can be 0, which
+ * means that the symbol does not have a codeword assigned. In addition,
+ * @lens may alias @decode_table, as noted above.
+ *
+ * @max_codeword_len:
+ * The maximum codeword length permitted for this code. All entries in
+ * 'lens' must be less than or equal to this value.
+ *
+ * Returns 0 on success, or -1 if the lengths do not form a valid prefix code.
*/
int
-make_huffman_decode_table(u16 *decode_table, unsigned num_syms,
- unsigned table_bits, const u8 *lens,
+make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
+ unsigned table_bits, const u8 lens[],
unsigned max_codeword_len)
{
- unsigned len_counts[max_codeword_len + 1];
+ u16 len_counts[max_codeword_len + 1];
+ u16 offsets[max_codeword_len + 1];
u16 sorted_syms[num_syms];
- unsigned offsets[max_codeword_len + 1];
- const unsigned table_num_entries = 1 << table_bits;
- int left;
- unsigned decode_table_pos;
- void *decode_table_ptr;
+ s32 remainder = 1;
+ void *entry_ptr = decode_table;
+ unsigned codeword_len = 1;
unsigned sym_idx;
- unsigned codeword_len;
- unsigned stores_per_loop;
-
-#ifdef USE_LONG_FILL
- const unsigned entries_per_long = sizeof(unsigned long) / sizeof(decode_table[0]);
-#endif
-
-#ifdef USE_SSE2_FILL
- const unsigned entries_per_xmm = sizeof(__m128i) / sizeof(decode_table[0]);
-#endif
-
- wimlib_assert2((uintptr_t)decode_table % DECODE_TABLE_ALIGNMENT == 0);
-
- /* accumulate lengths for codes */
- for (unsigned i = 0; i <= max_codeword_len; i++)
- len_counts[i] = 0;
-
- for (unsigned sym = 0; sym < num_syms; sym++) {
- wimlib_assert2(lens[sym] <= max_codeword_len);
+ unsigned codeword;
+ unsigned subtable_pos;
+ unsigned subtable_bits;
+ unsigned subtable_prefix;
+
+ /* Count how many codewords have each length, including 0. */
+ for (unsigned len = 0; len <= max_codeword_len; len++)
+ len_counts[len] = 0;
+ for (unsigned sym = 0; sym < num_syms; sym++)
len_counts[lens[sym]]++;
- }
- /* check for an over-subscribed or incomplete set of lengths */
- left = 1;
+ /* It is already guaranteed that all lengths are <= max_codeword_len,
+ * but it cannot be assumed they form a complete prefix code. A
+ * codeword of length n should require a proportion of the codespace
+ * equaling (1/2)^n. The code is complete if and only if, by this
+ * measure, the codespace is exactly filled by the lengths. */
for (unsigned len = 1; len <= max_codeword_len; len++) {
- left <<= 1;
- left -= len_counts[len];
- if (unlikely(left < 0)) { /* over-subscribed */
- DEBUG("Invalid Huffman code (over-subscribed)");
+ remainder = (remainder << 1) - len_counts[len];
+ /* Do the lengths overflow the codespace? */
+ if (unlikely(remainder < 0))
return -1;
- }
}
- if (unlikely(left != 0)) /* incomplete set */{
- if (left == 1 << max_codeword_len) {
- /* Empty code--- okay in XPRESS and LZX */
- memset(decode_table, 0,
- table_num_entries * sizeof(decode_table[0]));
- return 0;
- } else {
- DEBUG("Invalid Huffman code (incomplete set)");
+ if (remainder != 0) {
+ /* The lengths do not fill the codespace; that is, they form an
+ * incomplete code. This is permitted only if the code is empty
+ * (contains no symbols). */
+
+ if (unlikely(remainder != 1U << max_codeword_len))
return -1;
- }
+
+ /* The code is empty. When processing a well-formed stream, the
+ * decode table need not be initialized in this case. However,
+ * we cannot assume the stream is well-formed, so we must
+ * initialize the decode table anyway. Setting all entries to 0
+ * makes the decode table always produce symbol '0' without
+ * consuming any bits, which is good enough. */
+ memset(decode_table, 0, sizeof(decode_table[0]) << table_bits);
+ return 0;
}
- /* Generate offsets into symbol table for each length for sorting */
- offsets[1] = 0;
- for (unsigned len = 1; len < max_codeword_len; len++)
+ /* Sort the symbols primarily by increasing codeword length and
+ * secondarily by increasing symbol value. */
+
+ /* Initialize 'offsets' so that 'offsets[len]' is the number of
+ * codewords shorter than 'len' bits, including length 0. */
+ offsets[0] = 0;
+ for (unsigned len = 0; len < max_codeword_len; len++)
offsets[len + 1] = offsets[len] + len_counts[len];
- /* Sort symbols primarily by length and secondarily by symbol order.
- * This is basically a count-sort over the codeword lengths. */
+ /* Use the 'offsets' array to sort the symbols. */
for (unsigned sym = 0; sym < num_syms; sym++)
- if (lens[sym] != 0)
- sorted_syms[offsets[lens[sym]]++] = sym;
-
- /* Fill entries for codewords short enough for a direct mapping. We can
- * take advantage of the ordering of the codewords, since the Huffman
- * code is canonical. It must be the case that all the codewords of
- * some length L numerically precede all the codewords of length L + 1.
- * Furthermore, if we have 2 symbols A and B with the same codeword
- * length but symbol A is sorted before symbol B, then then we know that
- * the codeword for A numerically precedes the codeword for B. */
- decode_table_ptr = decode_table;
- sym_idx = 0;
- codeword_len = 1;
-#ifdef USE_SSE2_FILL
- /* Fill in the Huffman decode table entries one 128-bit vector at a
- * time. This is 8 entries per store. */
- stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_xmm;
- for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
+ sorted_syms[offsets[lens[sym]]++] = sym;
+
+ /*
+ * Fill the root table entries for codewords no longer than table_bits.
+ *
+ * The table will start with entries for the shortest codeword(s), which
+ * will have the most entries. From there, the number of entries per
+ * codeword will decrease. As an optimization, we may begin filling
+ * entries with SSE2 vector accesses (8 entries/store), then change to
+ * word accesses (2 or 4 entries/store), then change to 16-bit accesses
+ * (1 entry/store).
+ */
+ sym_idx = offsets[0];
+
+#ifdef __SSE2__
+ /* Fill entries one 128-bit vector (8 entries) at a time. */
+ for (unsigned stores_per_loop = (1U << (table_bits - codeword_len)) /
+ (sizeof(__m128i) / sizeof(decode_table[0]));
+ stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1)
+ {
unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
for (; sym_idx < end_sym_idx; sym_idx++) {
- /* Note: unlike in the 'long' version below, the __m128i
+ /* Note: unlike in the "word" version below, the __m128i
* type already has __attribute__((may_alias)), so using
- * it to access the decode table, which is an array of
- * unsigned shorts, will not violate strict aliasing. */
- u16 sym;
- __m128i v;
- __m128i *p;
- unsigned n;
-
- sym = sorted_syms[sym_idx];
-
- v = _mm_set1_epi16(sym);
- p = (__m128i*)decode_table_ptr;
- n = stores_per_loop;
+ * it to access an array of u16 will not violate strict
+ * aliasing. */
+ __m128i v = _mm_set1_epi16(
+ MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx],
+ codeword_len));
+ unsigned n = stores_per_loop;
do {
- *p++ = v;
+ *(__m128i *)entry_ptr = v;
+ entry_ptr += sizeof(v);
} while (--n);
- decode_table_ptr = p;
}
}
-#endif /* USE_SSE2_FILL */
+#endif /* __SSE2__ */
-#ifdef USE_LONG_FILL
- /* Fill in the Huffman decode table entries one 'unsigned long' at a
- * time. On 32-bit systems this is 2 entries per store, while on 64-bit
- * systems this is 4 entries per store. */
- stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_long;
- for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
+#ifdef __GNUC__
+ /* Fill entries one word (2 or 4 entries) at a time. */
+ for (unsigned stores_per_loop = (1U << (table_bits - codeword_len)) /
+ (WORDBYTES / sizeof(decode_table[0]));
+ stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1)
+ {
unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
for (; sym_idx < end_sym_idx; sym_idx++) {
- /* Accessing the array of unsigned shorts as unsigned
- * longs would violate strict aliasing and would require
- * compiling the code with -fno-strict-aliasing to
- * guarantee correctness. To work around this problem,
- * use the gcc 'may_alias' extension to define a special
- * unsigned long type that may alias any other in-memory
- * variable. */
- typedef unsigned long __attribute__((may_alias)) aliased_long_t;
-
- u16 sym;
- aliased_long_t *p;
- aliased_long_t v;
- unsigned n;
-
- sym = sorted_syms[sym_idx];
-
- BUILD_BUG_ON(sizeof(aliased_long_t) != 4 &&
- sizeof(aliased_long_t) != 8);
-
- v = sym;
- if (sizeof(aliased_long_t) >= 4)
- v |= v << 16;
- if (sizeof(aliased_long_t) >= 8) {
- /* This may produce a compiler warning if an
- * aliased_long_t is 32 bits, but this won't be
- * executed unless an aliased_long_t is at least
- * 64 bits anyway. */
- v |= v << 32;
- }
-
- p = (aliased_long_t *)decode_table_ptr;
- n = stores_per_loop;
-
+ /* Accessing the array of u16 as u32 or u64 would
+ * violate strict aliasing and would require compiling
+ * the code with -fno-strict-aliasing to guarantee
+ * correctness. To work around this problem, use the
+ * gcc 'may_alias' extension. */
+ typedef machine_word_t
+ __attribute__((may_alias)) aliased_word_t;
+ aliased_word_t v = repeat_u16(
+ MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx],
+ codeword_len));
+ unsigned n = stores_per_loop;
do {
- *p++ = v;
+ *(aliased_word_t *)entry_ptr = v;
+ entry_ptr += sizeof(v);
} while (--n);
- decode_table_ptr = p;
}
}
-#endif /* USE_LONG_FILL */
+#endif /* __GNUC__ */
- /* Fill in the Huffman decode table entries one 16-bit integer at a
- * time. */
- stores_per_loop = (1 << (table_bits - codeword_len));
- for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
+ /* Fill entries one at a time. */
+ for (unsigned stores_per_loop = (1U << (table_bits - codeword_len));
+ stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1)
+ {
unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
for (; sym_idx < end_sym_idx; sym_idx++) {
- u16 sym;
- u16 *p;
- unsigned n;
-
- sym = sorted_syms[sym_idx];
-
- p = (u16*)decode_table_ptr;
- n = stores_per_loop;
-
+ u16 v = MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx],
+ codeword_len);
+ unsigned n = stores_per_loop;
do {
- *p++ = sym;
+ *(u16 *)entry_ptr = v;
+ entry_ptr += sizeof(v);
} while (--n);
-
- decode_table_ptr = p;
}
}
- /* If we've filled in the entire table, we are done. Otherwise, there
- * are codes longer than table bits that we need to store in the
- * tree-like structure at the end of the table rather than directly in
- * the main decode table itself. */
+ /* If all symbols were processed, then no subtables are required. */
+ if (sym_idx == num_syms)
+ return 0;
+
+ /* At least one subtable is required. Process the remaining symbols. */
+ codeword = ((u16 *)entry_ptr - decode_table) << 1;
+ subtable_pos = 1U << table_bits;
+ subtable_bits = table_bits;
+ subtable_prefix = -1;
+ do {
+ while (len_counts[codeword_len] == 0) {
+ codeword_len++;
+ codeword <<= 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;
+ unsigned prefix = codeword >> (codeword_len - table_bits);
+
+ /* 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 != subtable_prefix) {
+
+ subtable_prefix = prefix;
+
+ /*
+ * Calculate the subtable length. If the codeword
+ * length exceeds 'table_bits' by n, then 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 it was previously verified that the
+ * code is complete.
+ */
+ subtable_bits = codeword_len - table_bits;
+ remainder = (s32)1 << subtable_bits;
+ for (;;) {
+ remainder -= len_counts[table_bits +
+ subtable_bits];
+ if (remainder <= 0)
+ break;
+ subtable_bits++;
+ remainder <<= 1;
+ }
- wimlib_assert2(decode_table_pos < table_num_entries);
+ /* Create the entry that points from the root 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[subtable_prefix] =
+ MAKE_DECODE_TABLE_ENTRY(subtable_pos,
+ subtable_bits);
+ }
- /* Fill in the remaining entries, which correspond to codes
- * longer than @table_bits.
- *
- * First, zero out the rest of the entries. This is necessary
- * so that the entries appear as "unallocated" in the next part.
- * */
- j = decode_table_pos;
+ /* Fill the subtable entries for this symbol. */
+ u16 entry = MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx],
+ codeword_len - table_bits);
+ unsigned n = 1U << (subtable_bits - (codeword_len -
+ table_bits));
do {
- decode_table[j] = 0;
- } while (++j != table_num_entries);
-
- /* Assert that 2**table_bits is at least num_syms. If this
- * wasn't the case, we wouldn't be able to distinguish pointer
- * entries from symbol entries. */
- wimlib_assert2(table_num_entries >= num_syms);
-
-
- /* The tree nodes are allocated starting at decode_table[1 <<
- * table_bits]. Remember that the full size of the table,
- * including the extra space for the tree nodes, is actually
- * 2**table_bits + 2 * num_syms slots, while table_num_entries
- * is only 2**table_bits. */
- next_free_tree_slot = table_num_entries;
-
- /* The current Huffman codeword */
- cur_codeword = decode_table_pos << 1;
-
- /* Go through every codeword of length greater than @table_bits,
- * primarily in order of codeword length and secondarily in
- * order of symbol. */
- wimlib_assert2(codeword_len == table_bits + 1);
- for (; 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++) {
- unsigned sym = sorted_syms[sym_idx];
- unsigned extra_bits = codeword_len - table_bits;
-
- /* index of the current node; find it from the
- * prefix of the current Huffman codeword. */
- unsigned node_idx = cur_codeword >> extra_bits;
- wimlib_assert2(node_idx < table_num_entries);
+ decode_table[subtable_pos++] = entry;
+ } while (--n);
- /* Go through each bit of the current Huffman
- * codeword beyond the prefix of length
- * @table_bits and walk the tree, allocating any
- * slots that have not yet been allocated. */
- do {
+ len_counts[codeword_len]--;
+ codeword++;
+ } while (++sym_idx < num_syms);
- /* If the current tree node points to
- * nowhere but we need to follow it,
- * allocate a new node for it to point
- * to. */
- if (decode_table[node_idx] == 0) {
- decode_table[node_idx] = next_free_tree_slot;
- decode_table[next_free_tree_slot++] = 0;
- decode_table[next_free_tree_slot++] = 0;
- wimlib_assert2(next_free_tree_slot <=
- table_num_entries + 2 * num_syms);
- }
-
- /* Set node_idx to left child */
- node_idx = decode_table[node_idx];
-
- /* Is the next bit 0 or 1? If 0, go left
- * (already done). If 1, go right by
- * incrementing node_idx. */
- --extra_bits;
- node_idx += (cur_codeword >> extra_bits) & 1;
- } while (extra_bits != 0);
-
- /* node_idx is now the index of the leaf entry
- * into which the actual symbol will go. */
- decode_table[node_idx] = sym;
-
- /* Note: cur_codeword is always incremented at
- * the end of this loop because this is how
- * canonical Huffman codes are generated (add 1
- * for each code, then left shift whenever the
- * code length increases) */
- }
- }
- }
return 0;
}
git://wimlib.net / wimlib / blobdiff