+extern int read_huffsym_near_end_of_input(struct input_bitstream *istream,
+ const u16 decode_table[],
+ const u8 lens[],
+ unsigned num_syms,
+ unsigned table_bits,
+ unsigned *n);
+
+/*
+ * 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.
+ */
+static inline int read_huffsym(struct input_bitstream *istream,
+ const u16 decode_table[],
+ const u8 lens[],
+ unsigned num_syms,
+ unsigned table_bits,
+ unsigned *n,
+ unsigned max_codeword_len)
+{
+ int ret;
+
+ /* In the most common case, there are at least max_codeword_len bits
+ * remaining in the stream. */
+ if (bitstream_ensure_bits(istream, 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(istream, 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_syms) {
+ bitstream_remove_bits(istream, table_bits);
+ do {
+ key_bits = sym + bitstream_peek_bits(istream, 1);
+ bitstream_remove_bits(istream, 1);
+
+ wimlib_assert2(key_bits < num_syms * 2 +
+ (1 << table_bits));
+ } while ((sym = decode_table[key_bits]) >= num_syms);
+ } else {
+ wimlib_assert2(lens[sym] <= table_bits);
+ bitstream_remove_bits(istream, lens[sym]);
+ }
+ *n = sym;
+ ret = 0;
+ } else {
+ /* Otherwise, we must be careful to use only the bits that are
+ * actually remaining. */
+ ret = read_huffsym_near_end_of_input(istream, decode_table,
+ lens, num_syms,
+ table_bits, n);
+ }
+ return ret;
+}