-/*
- * 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.
- *
- * @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.
- *
- * @num_syms: Total number of symbols in the Huffman tree.
- *
- * @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.
- *
- * @lens: An array of length @num_syms, indexable by symbol, that
- * gives the length of the Huffman codeward 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.
- *
- * @max_codeword_len: The longest codeword length allowed in the compression
- * format.
- *
- * Returns 0 on success; returns -1 if the length values do not correspond to a
- * valid Huffman tree.
- *
- * 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.
- *
- * 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.
- *
- * 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.
- */
-int 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 sorted_syms[num_syms];
- unsigned offsets[max_codeword_len + 1];
- const unsigned table_num_entries = 1 << table_bits;