.JPG File Format – Huffman tables

JPEG image (JFIF and Exif)

The quantised coefficients are coded with Huffman codes: short codes for the things that happen most often. A DHT segment holds the tables. The tables say how many codes there are of each length and which symbol each code stands for; the bit patterns themselves follow from those.

DHT segment

A segment (marker FF C4, section B.2.4.2 of T.81) can define several tables in a row.

  1. 0Marker FF C42 bytes
  2. 2Lh segment length2 bytes
  3. 4Tc, Th class and table number1 byte
  4. 5L1 … L16 codes of each length16 bytes
  5. 21V the symbols, shortest codes firstsum of L bytes
  6. …Further tables the same againvaries
A DHT segment, with its first table
FieldSizeDescription
Tc (high 4 bits)½0: a DC table. 1: an AC table.
Th (low 4 bits)½Table number, 0 to 3 (0 or 1 in baseline). A later table of the same class and number replaces this one.
Li1 eachHow many codes are i bits long, for i from 1 to 16.
V1 eachOne symbol for each code, in order of code. The sum of the L values is how many there are, at most 256.

A table takes 17 bytes and one more for each symbol. Scans choose their tables in the scan header.

How the codes are assigned

The codes are canonical. Start with the code 0, one bit long. Give each code in turn the next number, and every time the length grows, double the number:

code = 0
for length = 1 to 16:
    for each of the L(length) symbols of this length, in order:
        give the symbol this code, written in length bits
        code = code + 1
    code = code × 2

A table with one 2-bit code, then one 3-bit code, and one 4-bit code gives the codes 00, 010 and 0110. Lengths cannot go past 16 bits, and the tables Annex K describes leave the code of all 1 bits unused.

Decoding reads bits one at a time, keeping the code so far, until the code matches one of that length. The codes of one length are consecutive numbers, so the count of codes at each length is enough to tell where the code falls, and the place of a code in its length gives its symbol.

DC symbols

A DC table codes the size of the difference between this block's DC coefficient and the previous block's in the same component. The symbol is that size, called SSSS, in bits, and the bits follow immediately after the code.

Size (SSSS)Differences it can hold
00 (no bits follow)
1−1, 1
2−3 … −2, 2 … 3
3−7 … −4, 4 … 7
4−15 … −8, 8 … 15
5−31 … −16, 16 … 31
6−63 … −32, 32 … 63
7−127 … −64, 64 … 127
8−255 … −128, 128 … 255
9−511 … −256, 256 … 511
10−1,023 … −512, 512 … 1,023
11−2,047 … −1,024, 1,024 … 2,047

In a 12-bit image, sizes above 11 are also used.

AC symbols

An AC table's symbols combine two numbers: RRRR (high 4 bits), the count of zero coefficients to skip, and SSSS (low 4 bits), the size of the next non-zero coefficient.

SymbolNameMeaning
00EOBEnd of block: the rest of the coefficients are zero.
F0ZRLZero run length: 16 zero coefficients, and the coding carries on.
R S (S not 0)R zero coefficients, then a coefficient of S bits, whose bits follow the code.
n0 (n from 1 to E, in hex)EOBnOnly in progressive scans: an end-of-band run of 2n blocks or more; n further bits follow the code.

In a baseline 8-bit image an AC coefficient takes at most 10 bits. The bits after the code give the coefficient's value in the same way as a DC difference: How the coding works shows how.