### Optimizing JPEG entropy decoding

What

Entropy coding is the term used for lossless data compression . It refers to increasing the entropy of data by taking advantage of the differing probabilities of symbols to create a more compact representation of them. The size of the code used to represent each symbol is inversely proportional to its probability. In other words, the more probable symbols will be replaced with shorter codes, and the less probable with longer codes thereby reducing the total size of the data. A simple example of entropy coding is Morse code. The letters of the alphabet are replaced by a series of dots and dashes where the probability of the letter (in English) determines the length of the code. The way Morse code is defined, there must be a space between each code in order to uniquely recognize it or it could be confused with a different code. For example, the letter E is a single dot. If two E's are sent without a space between them, they would be interpreted as an I. David Huffman invented a different entropy coding system where the codes could be packed together without spaces. This 'minimum redundancy' code is what's used in many computing applications to compress data. This feature of having left-to-right uniqueness also means that Huffman codes will tend to grow in length relatively quickly as the number of symbols grows. Based on the probability of the symbols being encoded, a Huffman “tree” is created which produces a series of codes made up of a variable numbers of 1s and 0s, each representing a left and right branch on the tree.

Why

Most JPEG image files use Huffman compression (arithmetic coding is a less popular option) as the final step to shrink the size of the symbols used to encode the image. The goal of this article is to document techniques for decoding JPEG Huffman data more efficiently than the "standard" way employed in most software. JPEG images are so ubiquitous across the world that a significant amount of energy and time is spent working with them. Any improvement in decoding efficiency can translate into both improved usability and lower energy usage.

How

Part of the performance problem with decoding baseline JPEG data is that there can be markers inserted into the variable length codes. The markers are byte-aligned 8-bit values of 0xff followed by the 8-bit marker value. The only markers that should be found in the image data are 'stuffed zeros' and restart markers. The stuffed zero (FF 00) is just a way to store a data byte of FF since it would get interpreted as a marker otherwise. Typical JPEG decoders have to read the compressed data one byte at a time, always searching for the value FF and acting accordingly. I've found that it's faster to pre-filter out the markers from the compressed data before decoding. Obviously filtering out the stuffed zeros is not an issue, but what about the restart markers? If the image is not corrupted, then the restart markers occur at known intervals. If it is corrupted, then other action should be taken. So, in the interest of speed, it's ok to strip away the markers to speed up the decoder. It's faster because a dedicated loop removing markers is going to be faster than placing extra tests within the decoder. The dedicated "marker removal filter" can use SIMD to speed up the process of finding FF's within the data stream.

Now let's look at the actual variable length decoding. There are many ways to decode Huffman compressed data. The least efficient way would be to read a single bit at a time and walk through the binary tree until a terminal node is hit. The left-to-right unique property of Huffman codes can be used to accelerate this process. A practical example to use is the A/C coefficient encoding in JPEG image files. The Huffman codes defining the A/C coefficients vary from 2 to 16-bits in length. If the maximum length code is read from the compressed data stream, it can be used as an index into a lookup table of all permutations of 16-bits (65536). The table entries will each contain the symbol’s value along with its true length. In the example below, the bits that are not part of the current code are marked with an X.

Now let's look at the actual variable length decoding. There are many ways to decode Huffman compressed data. The least efficient way would be to read a single bit at a time and walk through the binary tree until a terminal node is hit. The left-to-right unique property of Huffman codes can be used to accelerate this process. A practical example to use is the A/C coefficient encoding in JPEG image files. The Huffman codes defining the A/C coefficients vary from 2 to 16-bits in length. If the maximum length code is read from the compressed data stream, it can be used as an index into a lookup table of all permutations of 16-bits (65536). The table entries will each contain the symbol’s value along with its true length. In the example below, the bits that are not part of the current code are marked with an X.

Huffman codes: 00
(length 2), 100 (length 3), 11010
(length 5), … up to 16-bits in length

|----- 16-bits ------|

00xxxxxxxxxxxxxx

100xxxxxxxxxxxxx

11010xxxxxxxxxxx

100xxxxxxxxxxxxx

11010xxxxxxxxxxx

In each case, the table will contain repeated entries for
each possible combination of the unused bits.
In the case of the shortest code (00), there will be 16384 entries in
the table which all contain the same uncompressed symbol for 00 along with its
true length (2). This method of decoding the compressed symbols is fast (a
single read), but the large table size makes this impractical for some
applications. In the case of JPEG A/C
coefficients, there can be up to 4 different AC tables per image and each would
require 2-bytes per entry for a total of 65536 x 2 x 4 = 512K bytes. Various techniques exist to reduce the table
size, but they usually involve creating a number of smaller tables which
require multiple reads in order to arrive at the correct code.

A Better Way

A property of Huffman codes can be exploited to reduce the
table size. In order to maintain the
left-to-right uniqueness, long Huffman codes have a number of leading ones (or
zeroes depending on how the codes are generated). Here are some examples of long codes for JPEG
AC coefficients:

111111110011

1111111111111110

1111111111111110

Each Huffman tree has a practical “split point” where there
are a certain number of leading 1s followed by the unique part of the
code. In the case of JPEG AC
coefficients, the useful split point is at 5 or 6 leading 1s followed by up to 10 or 11 other bits. Codes with 5/6 leading 1s will
be called “long” codes and codes without 5/6 leading 1s will be called “short”
codes. In this example, the short codes
can be up to 10/11 bits long and the long codes can also be up to 10/11 bits long
(not counting the 5/6 leading 1s). The short and
long tables are not always the same length, but in this case it works out that
way. In order to decode all short and
long codes, 2 tables with 1024 entries in each (10 unique bits) are needed. Compared to the single table approach, to
hold all 4 possible AC tables, 1024 x 2 x 2 x 4 = 16K bytes will be needed. If the tables are arranged with the long code
table following the short code table, decoding can be made even more
efficient. Here is sample C code which
demonstrates how to decode JPEG AC coefficients with a single table read.

uint32_t ulCompressedBits, ulCode;

uint8_t iCurrentBitNumber;

uint16_t *usACTable, usValue;

uint8_t iCurrentBitNumber;

uint16_t *usACTable, usValue;

// extract
16-bits (left justified) of compressed data

ulCode = (ulCompressedBits << iCurrentBitNumber) >> 16;

if (ulCode >= 0xfc00) // top 6 bits == 1 à long code

{

// use bit 10 (being 1) to point us to the long table

usValue = usACTable[ulCode & 0x7ff];

}

else

{

// use lower 10 bits

usValue = usACTable[ulCode >> 6];

}

// actual length in upper byte

iCurrentBitNumber += (usValue >> 8);

usValue &= 0xff; // symbol value

ulCode = (ulCompressedBits << iCurrentBitNumber) >> 16;

if (ulCode >= 0xfc00) // top 6 bits == 1 à long code

{

// use bit 10 (being 1) to point us to the long table

usValue = usACTable[ulCode & 0x7ff];

}

else

{

// use lower 10 bits

usValue = usACTable[ulCode >> 6];

}

// actual length in upper byte

iCurrentBitNumber += (usValue >> 8);

usValue &= 0xff; // symbol value

Conclusion

This technique is applicable to any Huffman code
applications such as digital audio, video, image and file archives (rar/zip
files). The small table sizes and
complete decode in a single read lend itself well to hardware
implementations. Mobile devices can
benefit from this since they tend to have small data caches and slow memory. Finding the ideal split point needs to be
determined on a case-by-case basis and can be done programmatically or by
visual inspection.

## Comments

## Post a Comment