High-speed software implementation of Huffman coding
Mikio Kawahara, Yi-Jen Chiu, Thomas Berger · 2002
Summary form only given. Huffman coding has been applied in many disciplines including text compression, still image compression, and video compression. In the case of video, several software-only codecs have been developed aiming at real-time performance. However, they fall well short of achieving full screen, high-quality, and full-motion. A key bottleneck in such software implementations occurs during writing and reading of the Huffman-coded bit stream. The reason is that the minimum unit for software operations is a byte rather than a bit. Therefore, the need to read/write data in bits necessitates devising means to bridge the bits-to-bytes and and bytes-to-bits gaps efficiently. We introduce new tables for software-only Huffman coding that enable us to write/read data in M-bit units, thereby virtually eliminating the need for inefficient software simulation of bit-based operations. We present an offset-based Huffman encoding table containing information for each number of bits by which the length of a Huffman word is offset from an integral number of bytes. The number of rows in the offset-based Huffman encoding table is M times that of the general Huffman table. The offset-based Huffman encoding table eliminates most of the bit operations, but it still requires some bit-based operations to update the offset and the condition of the current unit. In order to avoid bit operations entirely, we extend the offset-based table into a byte-based table by associating a unique subtable with each offset and unit condition. A byte-based Huffman decoding table has also been studied.