Designing a JPEG Decoder & Source Code

Chroma Subsampling and the Huffman Scan data

Decoding the Scan Data segment (Marker: JFIF SOS, 0xFFDA) becomes a little more complicated when you need to deal with chroma subsampling. Since nearly all JPEG images are compressed with chroma subsampling, it is important that the decoder support the most common types of subsampling:

Subsampling HxV	Description	Comments
1x1	No Subsampling	Very few digital cameras (Sigma SD is a notable exception) output images without subsampling the color channel. Instead, you'll generally find these files generated from image editing applications when a high quality setting was used.
2x1	Horizontal subsampled	The majority of reasonable digital cameras produce JPEG images with 2x1.
1x2	Vertical subsampled	Typically from 2x1 subsampled images that have been rotated by 90 degrees.
2x2	Horizontal & Vertical subsampled	Cheaper digital cameras and image editors saving photos at low quality settings.
others		Not very common at all for digital photos. Other sources such as miniDV camcorders will use 4x1 chroma subsampling.

 

In each case, the encoding sequence is always to complete the luminance MCUs (1 or more) before going on to the chrominance components. Instead of observing a half or quarter as many color channel components, you'll find twice or four times as many luminance components encoded per block.

Coded Sequence for 1x1 (4:4:4)

The following 3 components make up one MCU, and are repeated in this sequence for every MCU. Note that the MCU represents a pixel area of 8x8 pixels.

[Y0(dc), Y0(ac)],
[Cb(dc), Cb(ac)],
[Cr(dc), Cr(ac)]

Coded Sequence for 2x1 (4:2:2)

The following 4 components make up one MCU. The MCU represents a pixel area of 16x8 pixels. Y0 and Y1 refer to two 8x8 pixel regions adjacent horizontally, while Cb and Cr refer to the single 16x8 pixel region that covers Y0 and Y1. To perform the encoding process, the Cb and Cr channels are first sub-sampled horizontally (this is usually done by averaging each pair of horizontal pixels into a single value). Then an MCU is made up of 8 averaged pixels horizontally by 8 original pixels veritically. The DC and AC coefficients are calculated on this new region.

[Y0(dc), Y0(ac)]
[Y1(dc), Y1(ac)],
[Cb(dc), Cb(ac)],
[Cr(dc), Cr(ac)]

Coded Sequence for 2x2 (4:2:0)

The following 6 components make up one MCU. The MCU represents a pixel area of 16x16 pixels. Y00 and Y10 refer to two 8x8 pixel regions adjacent horizontally, Y01 and Y11 refer to the two 8x8 pixel regions below Y00 and Y10. Cb and Cr refer to a single 16x16 pixel region that covers all four pixels (Y00, Y10, Y01 and Y11). To perform the encoding process, the Cb and Cr channels are first sub-sampled horizontally and vertically (this is usually done by averaging all four pixels into a single value). Then an MCU is made up of 8 averaged pixels horizontally by 8 averaged pixels veritically (which are based on the original region of 16x16 pixels). The DC and AC coefficients are calculated on this new region.

[Y00(dc), Y00(ac)]
[Y10(dc), Y10(ac)],
[Y01(dc), Y01(ac)],
[Y11(dc), Y11(ac)],
[Cb(dc), Cb(ac)],
[Cr(dc), Cr(ac)]

Variable-length Huffman Codes

Reading DHT Tables source code

Interpreting the DHT table in the JPEG JFIF file stream is not as intuitive as it may appear. It was designed to be stored in the most space-efficient manner, which makes reading it much harder. On paper, it is a fairly simple process to fill out the binary tree with the huffman codes as they appear in the DHT marker segment, but this doesn't translate well to the coded form.

The following example source code is completely un-optimized, as it is intended to show the basic mechanism of reading the DHT table and decoding the variable length JPEG huffman codes. It is based upon my experiences in developing the JPEGsnoop JPEG decoder from scratch.

Instead, one will observe that the codes that appear within the same bitlength will be incrementing by one. Going to the next bitlength requires the next code value to be doubled before continuing the count by one. This method is much more apparent when observing the resulting binary values that the codes correspond to.

Note that a two-dimensional array is used here to retain all of the variable-length codes. The first array index is used to reference the DHT table that we are processing (e.g. AC, DC, Luminance, Chrominance, etc.) The second index is simply to cover all of the possible code strings (max 162).

Locate the DHT Marker

repeat {
  class & dest_id = <Read Byte>

  table_set = dest_id*2 + class // Arbitrary mapping
  table_ind = 0

  Reset DhtCodeList[0..255] = 0xFFFF (dummy termination)
  DhtCodesLen[1..16] = <Read Bytes (x16)>

  for (ind_len=1; ind_len <= 16; ind_len++) {
    for (ind_code=0; ind_code < DhtCodesLen[ind_len]; ind_code++) {
    {
      DhtCodeList[dht_ind++] = <Read Byte>
    }
  }

  // Generate variable-length binary bit strings
  code_val = 0;
  dht_ind = 0;

  for (bit_len=1; bit_len <= 16; bit_len++) {
    for (code_ind=1; code_ind <= DhtCodesLen[bit_len]; code_ind++) {

      tmp_mask = ( (1 << (bit_len))-1 ) << (32-bit_len);
      tmp_bits = code_val << (32-bit_len);
      tmp_code = DhtCodeList[dht_ind];

      dht_lookup_bitlen [table_set][table_ind] = bit_len;
      dht_lookup_bits   [table_set][table_ind] = tmp_bits;
      dht_lookup_mask   [table_set][table_ind] = tmp_mask;
      dht_lookup_code   [table_set][table_ind] = tmp_code;

      table_ind++;
      code_val++;
      dht_ind++;
    }
    code_val <<= 1;
  }

  dht_lookup_size[table_set] = table_ind;

} until all DHT tables processed

Once you have stored the variable-length codes into structures that make it easy to search later, we can easily locate the codes in the bitstream.

dht_lookup_mask[][0..# codes] = Left-most bit mask for bitstring compare
dht_lookup_bits[][0..# codes] = Left-most bits for bitstring compare
dht_lookup_code[][0..# codes] = The 8-bit code value corresponding to this bitstring
dht_lookup_bitlen[][0..# codes] = The number of bits in the variable-length code

Searching the DHT Huffman Codes source code

The most simple way to locate a variable length code is to search linearly through the list of codes using the bitmask, looking for a match:

scan_buff = <Next 8 unused bits from file, shifted left align to bit 31>

// Slow search for variable-length huffman code
while (!done) {
  // Does the bit string match?
  if ((scan_buff & dht_lookup_mask[set][ind]) == dht_lookup_bits[set][ind]) {
    code = dht_lookup_code[set][ind];
    bits_used += dht_lookup_bitlen[set][ind];
    done = true;
  }
  ind++;

  // Just in case no match was found, check for end of array
  if (ind >= dht_lookup_size[set]) {
    done = true;
  }
}
					

After the above, bits_used indicates how long the variable-length code portion is, which can be used to shift the scan_buff for the next bit sequence.

JPEG Decoder Source Code

The following are some free resources that provide full source code implementations of other JPEG decoders. Several of these implementations take very different approaches, some simpler than others. Generally, the less refined / optimized versions are easier to understand.

• IJG 6b - The most widely-used JPEG Encoder / Decoder library, written in C. Fairly complex source code as it has been optimized heavily and is designed to work with a wide range of exception cases. Includes sample command-line applications (such as cjpeg, djpeg and jpegtran).
• Smaller Animals - Visual C++ code that demonstrates a simple application making use of the IJG 6a JPEG decoder libraries.
• Cristi Cuturicu - Very simple decoder source in C++. Some ASM optimization. Limited comments.
• Rich Geldreich - JPEG decoder. Includes MMX optimizations, progressive images. Limited comments.
• Cornell University - Lossless JPEG only
• Stanford University - Designed for research and experimentation (not optimized for production). Supports Lossless JPEG.
• JPEGsnoop (Calvin Hass) - JPEG decoder and Windows application. Fresh ground-up decoder library in Visual C++ with lots of comments :). Full source code not yet available.

Other Sections Coming soon:

JPEG JFIF Markers Parsing

Hex	Marker	Marker Name	Description
0x FFC0	SOF0	Start of Frame 0	Baseline DCT
0x FFC1	SOF1	Start of Frame 1	Extended Sequential DCT
0x FFC2	SOF2	Start of Frame 2	Progressive DCT
0x FFC3	SOF3	Start of Frame 3	Lossless (sequential)
0x FFC4	DHT	Define Huffman Table
0x FFC5	SOF5	Start of Frame 5	Differential sequential DCT
0x FFC6	SOF6	Start of Frame 6	Differential progressive DCT
0x FFC7	SOF7	Start of Frame 7	Differential lossless (sequential)
0x FFC8	JPG	JPEG Extensions
0x FFC9	SOF9	Start of Frame 9	Extended sequential DCT, Arithmetic coding
0x FFCA	SOF10	Start of Frame 10	Progressive DCT, Arithmetic coding
0x FFCB	SOF11	Start of Frame 11	Lossless (sequential), Arithmetic coding
0x FFCC	DAC	Define Arithmetic Coding
0x FFCD	SOF13	Start of Frame 13	Differential sequential DCT, Arithmetic coding
0x FFCE	SOF14	Start of Frame 14	Differential progressive DCT, Arithmetic coding
0x FFCF	SOF15	Start of Frame 15	Differential lossless (sequential), Arithmetic coding
0x FFD0	RST0	Restart Marker 0
0x FFD1	RST1	Restart Marker 1
0x FFD2	RST2	Restart Marker 2
0x FFD3	RST3	Restart Marker 3
0x FFD4	RST4	Restart Marker 4
0x FFD5	RST5	Restart Marker 5
0x FFD6	RST6	Restart Marker 6
0x FFD7	RST7	Restart Marker 7
0x FFD8	SOI	Start of Image
0x FFD9	EOI	End of Image
0x FFDA	SOS	Start of Scan
0x FFDB	DQT	Define Quantization Table
0x FFDC	DNL	Define Number of Lines	(Not common)
0x FFDD	DRI	Define Restart Interval
0x FFDE	DHP	Define Hierarchical Progression	(Not common)
0x FFDF	EXP	Expand Reference Component	(Not common)
0x FFE0	APP0	Application Segment 0	JFIF - JFIF JPEG image AVI1 - Motion JPEG (MJPG)
0x FFE1	APP1	Application Segment 1	EXIF Metadata, TIFF IFD format, JPEG Thumbnail (160x120) Adobe XMP
0x FFE2	APP2	Application Segment 2	ICC color profile, FlashPix
0x FFE3	APP3	Application Segment 3	(Not common) JPS Tag for Stereoscopic JPEG images
0x FFE4	APP4	Application Segment 4	(Not common)
0x FFE5	APP5	Application Segment 5	(Not common)
0x FFE6	APP6	Application Segment 6	(Not common) NITF Lossles profile
0x FFE7	APP7	Application Segment 7	(Not common)
0x FFE8	APP8	Application Segment 8	(Not common)
0x FFE9	APP9	Application Segment 9	(Not common)
0x FFEA	APP10	Application Segment 10 PhoTags	(Not common) ActiveObject (multimedia messages / captions)
0x FFEB	APP11	Application Segment 11	(Not common) HELIOS JPEG Resources (OPI Postscript)
0x FFEC	APP12	Application Segment 12	Picture Info (older digicams), Photoshop Save for Web: Ducky
0x FFED	APP13	Application Segment 13	Photoshop Save As: IRB, 8BIM, IPTC
0x FFEE	APP14	Application Segment 14	(Not common)
0x FFEF	APP15	Application Segment 15	(Not common)
0x FFF0 ... 0x FFF6	JPG6	JPEG Extension 0 ... JPEG Extension 6	(Not common)
0x FFF7	JPG7 SOF48	JPEG Extension 7 JPEG-LS	Lossless JPEG
0x FFF8	JPG8 LSE	JPEG Extension 8 JPEG-LS Extension	Lossless JPEG Extension Parameters
0x FFF9	JPG9	JPEG Extension 9	(Not common)
0x FFFA	JPG10	JPEG Extension 10	(Not common)
0x FFFB	JPG11	JPEG Extension 11	(Not common)
0x FFFC	JPG12	JPEG Extension 12	(Not common)
0x FFFD	JPG13	JPEG Extension 13	(Not common)
0x FFFE	COM	Comment

 

Counting AC Huffman Codes

Makernotes

YCC to RGB Color Conversion

Restart Markers

Variable Length Decode Optimization

 

for (i = 0; i < h; i += 2){
    for (j = 0; j < w; j += 2){
	CbBlocks[i/2][j/2] = CbBlocks[i][j] +
                                         CbBlocks[i] [j+1] +
                                         CbBlocks[i+1][j] +
                                         CbBlocks[i+1][j+1]) / 4;

        CrBlocks[i/2][j/2] = (CrBlocks[i][j] +
                                         CrBlocks[i][j+1] +
				         CrBlocks[i+1][j] +
                                         CrBlocks[i+1][j+1]) / 4;
	}
}

for (i = 0; i < h; i += 2){
    for (j = 0; j < w; j += 2){
	OutCbBlocks[i/2][j/2] = CbBlocks[i][j];
        OutCrBlocks[i/2][j/2] = CrBlocks[i][j];
    }
}

Y(:,:,1) =[...
 -471   -19     5     0   -15     1    -2     3
  -51    37   -41    -5    11     0     3    -5
  -25   -10    42     5    -8     5    -8     5
   11     8   -14     5     6   -12    11     1
   -9   -11    15     8    -1    13    -8     7
  -15     5   -21    -1     6    -4     3   -12
   12    -3    14     1     2     4     2    12
   -6     1   -14    -2     7     4    -4   -11]

Cb(:,:,2)=[ ...
 -165     6     2    -1     5    -2     1     0
   14   -10    11     5    -3    -1     0     2
   12     0   -13    -4     3    -1     1    -3
   -8     0     3    -2    -2     2    -2    -2
    6     2    -3    -2    -1    -3     2     1
    2     4     2    -2    -1    -1     0     2
   -1    -1    -2     1    -2    -4     0    -1
    3     1     2     0    -2     1     0     0]

Cr(:,:,3) =[ ...                   
  215    -2    -3     2    -4    -1     0    -1
  -13     7   -11    -5     3     1    -1     0
  -16     4    11     2    -2    -3     1     0
    5    -2    -1     2     3     0     1     3
   -5     0     2    -1     1     1     0    -1
   -3    -4    -1     3     2    -1    -1    -2
   -1     3    -2    -1     0     2     1     1
   -2    -2    -1     1     3    -1     0     0]

DCT Matrix=
[  992   -30   -30   -24   -24   -20     0     0]
[  -30   -42   -42   -40   -26   -29   -30     0]
[  -28   -42   -40   -36   -20   -29     0     0]
[  -28   -36   -33   -30   -26     0     0     0]
[  -18   -33   -38   -28   -34     0     0     0]
[  -12   -18   -28   -32     0     0     0     0]
[    0   -32     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0]

DCT Matrix=
[    0     9     0     0     0     0     0     0]
[    9    11    13     0     0     0     0     0]
[    0    13     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0]