原创 JPEG的Haffman编码（1）

最近移植一些JPEG算法的代码，其中最令我困惑的就是Haffman编码部分。在网上搜索得到的资料要么只讲原理，没有具体的实例和步骤，要么语焉不详。最后我自己读了一遍代码，才搞清楚。现在写下来，希望给后来者提供些帮助。

本文假定读者已经非常了解JPEG和Haffman编码的原理。通过一个实例来讲解其具体的实现。关于JPEG和Haffman编码的原理，可以参考下面的网站：http://www.impulseadventure.com/photo/

假定MCU（Minimum Coded Unit）中的一个8X8 Block，经过DCT，Quantization和Zigzag编码得到如下的64字节的数据流。

FE 00 FF 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 FF 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00

现在，就来看看如何对其进行编码。

1 对DC（直流）分量Vd进行编码，就是数据中的第一个字节。

1.1 对于DC分量Vd，JPEG首先要进行DPCM编码。具体含义就是求当前Block的DC值与上一个Block的DC值的差值。假定上一个Block（必须是同一个color space）中的DC值Vd为03，而当前的DC值Vd为－2（0xFE为－2的补码），则DPCM编码Vdpcm等于FB（－5的补码）。

1.2 对DPCM的结果Vdpcm进行编码。

首先求Vdpcm（FB）得绝对值，为05。然后求Vdpcm的对应的编码长度（Magnitude）和编码值（Bits）。

Magnitude可以利用Vdpcm得绝对值通过查表法获得，其Lookup Table如下：

const UNS_8 getMagnitude[256] = {
 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};

看到其中得规律了吗？所以Magnitude也可以通过计算得来，只是需要计算时间，但可以节省一些存储空间。查表得Magnitue为3。

如果Vdpcm大于等于0，则其编码值（Bits）为Vdpcm的低Magnitude位。如果Vdpcm小于零，则其编码值（Bits）为Vdpcm绝对值取反的低Magnitude位。本例中Vdpcm小于零，所以先对其绝对值05取反，得FA，再取其低3位得Bits等于“010”。

1.3 对Magnitude进行Haffman编码

首先根据Lookup Table（convertDCMagnitudeLengthTable）查表得编码的长度为03。再根据Lookup Table（convertDCMagnitudeOutTable）查表得编码为0x0004。最终取0x0004得低3位为Magnitude的编码100。

const UNS_8 convertDCMagnitudeLengthTable[16] = {
 0x02, 0x03, 0x03, 0x03, 0x03, 0x03, 0x04, 0x05,
 0x06, 0x07, 0x08, 0x09, 0x00, 0x00, 0x00, 0x00};

const UNS_16 convertDCMagnitudeOutTable[16] = {
 0x0000, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x000e, 0x001e,
 0x003e, 0x007e, 0x00fe, 0x01fe, 0x0000, 0x0000, 0x0000, 0x0000};

1.4 连接Magnitude的编码和Vdpcm的编码的到DC分量的编码
连接100（Magnitude的编码）和010（Vdpcm）的编码，的到100010，就是DC分量的编码。