-
-/*
- * Reads a Huffman-encoded symbol from a bitstream.
- *
- * This function may be called hundreds of millions of times when extracting a
- * large WIM file. I'm not sure it could be made much faster that it is,
- * especially since there isn't enough time to make a big table that allows
- * decoding multiple symbols per lookup. But if extracting files to a hard
- * disk, the IO will be the bottleneck anyway.
- *
- * @buf: The input buffer from which the symbol will be read.
- * @decode_table: The fast Huffman decoding table for the Huffman tree.
- * @lengths: The table that gives the length of the code for each
- * symbol.
- * @num_symbols: The number of symbols in the Huffman code.
- * @table_bits: Huffman codes this length or less can be looked up
- * directory in the decode_table, as the
- * decode_table contains 2**table_bits entries.
- */
-int read_huffsym(struct input_bitstream *stream,
- const u16 decode_table[],
- const u8 lengths[],
- unsigned num_symbols,
- unsigned table_bits,
- unsigned *n,
- unsigned max_codeword_len)
-{
- /* In the most common case, there are at least max_codeword_len bits
- * remaining in the stream. */
- if (bitstream_ensure_bits(stream, max_codeword_len) == 0) {
-
- /* Use the next table_bits of the input as an index into the
- * decode_table. */
- u16 key_bits = bitstream_peek_bits(stream, table_bits);
-
- u16 sym = decode_table[key_bits];
-
- /* If the entry in the decode table is not a valid symbol, it is
- * the offset of the root of its Huffman subtree. */
- if (sym >= num_symbols) {
- bitstream_remove_bits(stream, table_bits);
- do {
- key_bits = sym + bitstream_peek_bits(stream, 1);
- bitstream_remove_bits(stream, 1);
-
- wimlib_assert(key_bits < num_symbols * 2 +
- (1 << table_bits));
- } while ((sym = decode_table[key_bits]) >= num_symbols);
- } else {
- wimlib_assert(lengths[sym] <= table_bits);
- bitstream_remove_bits(stream, lengths[sym]);
- }
- *n = sym;
- return 0;
- } else {
- /* Otherwise, we must be careful to use only the bits that are
- * actually remaining. */
- return read_huffsym_near_end_of_input(stream, decode_table,
- lengths, num_symbols,
- table_bits, n);
- }
-}