 Deflate Huffman coding

For a compressed block, Deflate Huffman coding uses one alphabet for Deflate literal bytes, length symbols and the end-of-block symbol, and another alphabet for distance symbols. Values 0 through 255 denote Deflate literal bytes, 256 ends the block, and 257 through 285 select lengths. A Deflate backreference is encoded as a length symbol, any length extra bits, a distance symbol, then any distance extra bits. Those extra bits select an offset within the symbol's prescribed range; they are not additional codewords.^[ref]

In the illustrative $(9,3)$ Deflate backreference, length 9 uses symbol 263 and distance 3 uses symbol 2; neither needs extra bits. Under the fixed Huffman codes, A, B and C each cost eight bits, symbol 263 costs seven, and distance symbol 2 costs five. Adding the seven-bit end-of-block symbol and three-bit block header gives $3+3\cdot 8+7+5+7=46$ bits, packed into six bytes for a single final block. This is a cost calculation for the explicitly chosen instructions, not a displayed compressed stream.^[ref]

Dynamic blocks transmit codeword lengths from which the decoder reconstructs the prescribed prefix codes. The code descriptions themselves use a smaller Huffman code and repeat instructions for successive codeword lengths, including runs of zero lengths. Here run-length encoding describes repeated code lengths, a separate role from copying repeated data bytes. Fixed blocks use predefined Huffman codes and avoid transmitting those descriptions.^[ref]