Dr. Dobb's Journal November 1997

A High-Speed Static Huffman Decoder

Huffman compression uses short codes for frequently appearing byte values and much longer codes for less common values. A simple Huffman decoder uses a binary tree. It reads one input bit at each step, using it to select the left (0) or right (1) path until a leaf node is reached. The decoder then outputs the symbol associated with the leaf node, and starts over from the root.

Stepping through the tree one node (and one bit) at a time is expensive. A table-driven decoder instead reads the next eight bits of input into a register and uses this register as an index into a decoding table. The table lookup classifies the input according to bit pattern. Each entry specifies how many bits are used to form the symbol, and the symbol value to be emitted. For example, if the three bits 101₂ encode a byte value of 27, you would store 3 (number of bits) and 27 (output value) in each table location matching 101xxxxx₂ (values 10100000₂ to 10111111₂).

If a symbol requires more than eight bits, the entry in the table for the first eight bits instructs the decoder to use a secondary table to continue interpreting the remainder of the code. For example, the code 10011010010₂ would be decoded by matching 10011010₂ in the first table, and then matching 010xxxxx₂ in an additional table.

To implement these ideas, I've defined the actions USE1, USE2, USE3, USE4, USE5, USE6, USE7, USE8 and USEGT8. Each action describes how many bits to consume. Actions USE1..USE8 emit a symbol, while USEGT8 chains to a lower-order table. Figure 5 illustrates how this works.

Decoders optimized to use table lookup spend most of their time arranging the input stream so that the next eight bits are presented as a byte for the table lookup. This cost can be slashed by cloning the decoder so that each possible bit alignment is handled by a tailored code page. The finite-state machine models its state space in two dimensions -- one state for the decode table, one for the input bit alignment.

On a Pentium, the optimized assembly-language decoder consumes just 14 cycles per decoded byte, not including the time to prepare the decoding tables. My implementation of this decoder (available electronically, see "Availability," page 3) uses Perl scripts to construct C or assembly source code for the decoder state machine.

-- B.K.