- 引言
在《nginx中的哈夫曼编解码算法[上]-编码》中，我们介绍了nginx采用查表的方法来实现的哈夫曼编码对http2 hpack进行压缩的功能，其编码的实现原理还是比较简单的。然而，上山容易下山难，nginx中实现的快速哈夫曼解码算法在理解上相对于编码算法有一些难度的。今天我们来聊一聊nginx是如何来实现快速哈夫曼解码的。
为什么要增加快速这个形容词呢？因为在学习哈夫曼原理的时候，书本上介绍的是采用构建哈夫曼树的方式，通过一边读取输入流中的比特，一边在哈夫曼树中不断游走的方式来实现的解码方式，虽然这种方式比较容易理解，但是其解码效率是不那么理想的。而nginx采用构建状态转移矩阵，在解码时不是每次读取一个比特，而是每次一次性读取输入流中的4个比特，通过跟随状态转移矩阵不断更新状态，来实现快速解码，解码效率得到大幅提升。
而且nginx在状态转移矩阵也进行了优化，能够在解码的过程中，对于多读取的比特不进行回退就能够正确解码，相比于需要回退的算法能够在性能上表现更加优秀。
本文分三部分进行讲解，首先介绍nginx实现的哈夫曼解码算法中的状态转移矩阵的构造及利用状态转移矩阵如何进行解码的原理；接着我们结合nginx的源码来详细分析nginx的解码源码的实现原理；最后，介绍快速哈夫曼解码算法的最核心的内容，就是如何来构造状态转移矩阵。
2. 哈夫曼解码状态转移矩阵
在nginx的哈夫曼解码的相关代码里面，首先它定义了一个状态转移矩阵，如下：
代码语言：javascript复制typedef struct {
u_char next;
u_char emit;
u_char sym;
u_char ending;
} ngx_http_huff_decode_code_t;
static ngx_http_huff_decode_code_t ngx_http_huff_decode_codes[256][16] = {
......
}先了解释一下ngx_http_huff_decode_code_t结构体的每个字段的含义。
- next: 下一个状态的状态id
- emit: 是否可以输出sym（被解码出来的字符）
- sym: 如果 emit=1，那么sym表示被解码出来的字符
- ending: 本状态是否可以进入解码完成状态
再看看ngx_http_huff_decode_codes，它是一个二维数组，第一维有256个记录，表示256个状态，第二维有16个元素，表示在当前的状态下面，后面读取到新的4个bit（总共16种排序方式，包括：0000,0001,0010,0011,0100,0101,0110,0111，1000,1001,1010,1011,1100,1101,1110,1111）后，如何进行处理，包括是输出解码得到的字符，还是只是进行状态转移，抑或是既要输出解码得到的字符又要进行状态转移。
所以这里第二维中的每个元素可以看成是状态转移图中的转移弧，并且每个状态都有16条状态转移弧。
在这个状态转移矩阵中，ngx_http_huff_decode_codes的第零条记录被规定为起始状态，解码的时候从状态零开始，不断重复读进4个bit，然后根据当前状态下对应的转移弧来进行处理，直到解码出所有的字符。
举个例子，譬如，0a0a9bcxf8的哈夫曼编码为 00 c0 37 e3 27 ff ff eb，按照nginx定义的状态转移矩阵，人工进行解码，将过程总结成一个表格，如下：
需要特别说明的是上述表格的”结束标记“，结束标记表示当前状态下遇到特定的4个比特的输入后，转移到新的状态时，这个新的状态可能是结束态。
如果输入流所有的比特都读取完毕了以后，但是当前的解码状态不是“结束状态”，那么认为当前的哈夫曼码流是有问题的，所以解码器根据这个条件来识别待解码的码流可能损坏。
在解码的过程中，还有一种是当前状态下面，输入的新的4个比特后，对应的转移弧还是转移到当前状态，在nginx中这种是用来表示当前状态不可能碰到这种组合的比特，也用来表示当前的输入码流可能已经损坏的标记。
3. 源码分析
通过上面的分析，下面我们对照nginx的源码，再来分析解码过程的实现原理。
3.1 状态转移矩阵的定义
首先，再详细看一下nginx的哈夫曼解码代码中定义的状态转移矩阵的定义：
代码语言：javascript复制static ngx_http_huff_decode_code_t ngx_http_huff_decode_codes[256][16] =
{
/* 0 */
{
{0x04, 0x00, 0x00, 0x00}, {0x05, 0x00, 0x00, 0x00},
{0x07, 0x00, 0x00, 0x00}, {0x08, 0x00, 0x00, 0x00},
{0x0b, 0x00, 0x00, 0x00}, {0x0c, 0x00, 0x00, 0x00},
{0x10, 0x00, 0x00, 0x00}, {0x13, 0x00, 0x00, 0x00},
{0x19, 0x00, 0x00, 0x00}, {0x1c, 0x00, 0x00, 0x00},
{0x20, 0x00, 0x00, 0x00}, {0x23, 0x00, 0x00, 0x00},
{0x2a, 0x00, 0x00, 0x00}, {0x31, 0x00, 0x00, 0x00},
{0x39, 0x00, 0x00, 0x00}, {0x40, 0x00, 0x00, 0x01}
},
{
{0x00, 0x01, 0x30, 0x01}, {0x00, 0x01, 0x31, 0x01},
{0x00, 0x01, 0x32, 0x01}, {0x00, 0x01, 0x61, 0x01},
{0x00, 0x01, 0x63, 0x01}, {0x00, 0x01, 0x65, 0x01},
{0x00, 0x01, 0x69, 0x01}, {0x00, 0x01, 0x6f, 0x01},
{0x00, 0x01, 0x73, 0x01}, {0x00, 0x01, 0x74, 0x01},
{0x0d, 0x00, 0x00, 0x00}, {0x0e, 0x00, 0x00, 0x00},
{0x11, 0x00, 0x00, 0x00}, {0x12, 0x00, 0x00, 0x00},
{0x14, 0x00, 0x00, 0x00}, {0x15, 0x00, 0x00, 0x00}
},
......
}关于对应的各个元素定义已经在第2节中介绍，不再赘述。
3.2 解码函数
解码函数是ngx_http_huff_decode，因为有了经过特别优化的状态转移矩阵的加持，解码逻辑实现得相当短小精悍。源码如下：
ngx_int_t
ngx_http_huff_decode(u_char *state, u_char *src, size_t len, u_char **dst,
ngx_uint_t last, ngx_log_t *log)
{
u_char *end, ch, ending;
ch = 0; /* 当前读入的待解码的一个byte */
ending = 1; /* 表示是否可以进入解码完成状态 */
end = src len; /* 待解码的内容缓冲区的结束位置 */
while (src != end) {
ch = *src ; /* 从待解吗内容缓冲区读取一个字节 */
/* 对当前读取的字节的高4位进行处理 */
if (ngx_http_huff_decode_bits(state, &ending, ch >> 4, dst)
!= NGX_OK)
{
ngx_log_debug2(NGX_LOG_DEBUG_HTTP, log, 0,
"http2 huffman decoding error at state %d: "
"bad code 0x%Xd", *state, ch >> 4);
return NGX_ERROR;
}
/* 对当前读取的字节的低4位进行处理 */
if (ngx_http_huff_decode_bits(state, &ending, ch & 0xf, dst)
!= NGX_OK)
{
ngx_log_debug2(NGX_LOG_DEBUG_HTTP, log, 0,
"http2 huffman decoding error at state %d: "
"bad code 0x%Xd", *state, ch & 0xf);
return NGX_ERROR;
}
}
if (last) {
if (!ending) { /* 如果输入码流已经结束了，
但是我们的解码状态认为码流还没有结束，
则说明输入的码流可能已经损坏，
这里输出此物日志并返回NGX_ERROR */
ngx_log_debug1(NGX_LOG_DEBUG_HTTP, log, 0,
"http2 huffman decoding error: "
"incomplete code 0x%Xd", ch);
return NGX_ERROR;
}
*state = 0;
}
return NGX_OK;
}这里再解释一下解码函数的入口参数。
- state: 当前的解码状态，如果将待解码内容分片解码的话，那么第一个分片进行调用的时候设置
*state=0，否则*state沿用上次调用返回时候的状态。 - src: 本次待解码内容的缓冲区。
- len: 本次待解码内容的缓冲区大小。
- dst: 解码后内容的存储地址，当解码完成后，指向解码后内容的结尾处。
- last: 如果调用者传入的当前缓冲区是最后一个缓冲区，那么last设置为1。
所以，我们需要知道，解码程序是可以支持分块解压的，一个完整内容的分块解压过程是有上下文的，即*state参数中保存的解码状态。
每次调用解码，如果解码成功，dst参数会指向解码后内容的结尾处，所以解码后内容的长度需要通过dst调用前和调用后之间的差值来计算得到。
因为不像编码逻辑每次调用一定会成功，解码过程可能会发现输入的内容不是合法的哈夫曼编码码流，所以解码可能会失败，调用者需要处理失败的情况。
下面再分析一下解码函数ngx_http_huff_decode调用的ngx_http_huff_decode_bits。这个函数的任务就是根据读取的4个bit，查找状态转移矩阵中定义的规则，进行解码输出和状态转移处理。源码如下：
代码语言：javascript复制static ngx_inline ngx_int_t
ngx_http_huff_decode_bits(u_char *state, u_char *ending, ngx_uint_t bits,
u_char **dst)
{
ngx_http_huff_decode_code_t code; /* 状态转移弧 */
/* 根据当前的状态*state和读入的4个bit，得到状态转移弧 */
code = ngx_http_huff_decode_codes[*state][bits];
/* 如果状态转移弧中定义的目标状态和当前的状态是一样的，
这个是故意设置的错误状态，解码失败，所以直接返回NGX_ERROR */
if (code.next == *state) {
return NGX_ERROR;
}
/* 如果状态转移弧中emit字段标记为1，那么在输出缓冲区中输出sym字段 */
if (code.emit) {
*(*dst) = code.sym;
}
/* 更新当前的ending状态和state状态为状态转移弧中定义值，使得解码逻辑进入下一个状态 */
*ending = code.ending;
*state = code.next;
return NGX_OK;
}4. 如何构造状态转移矩阵
看了nginx的代码，实现得非常简练，之所以这样，是因为它的状态转移表构建得好，如果按照我在[[《采用状态转移矩阵方式的快速哈夫曼解码算法》]]https://blog.csdn.net/bluestn/article/details/138191031中描述的算法那样构造状态转移表，会产生一次读入的4个bit只被使用了部分bit，而剩下的几位比特需要再和新读取的比特合成新的4个比特重新回到初始状态去匹配新的输入，导致逻辑会有一些复杂，同时效率也会相对比较低，这个实现代码大家也可以参考《Huffman Codec in netty HPACK》http://kapsterio.github.io/test/2021/07/31/huffman-codec-in-netty-hpack.html中的介绍，比起nginx的实现的确会略显麻烦。
那么nginx采用的状态转移表也不是完全没有代价的，它相对于《Huffman Codec in netty HPACK》中给出的算法所使用的状态转移表大了近5倍，用空间换取了算法上的高效和实现的简洁性，对nginx这种以高性能著称的web服务器来说是我觉得是非常划算的。
所以，说一千道一万，解码算法的实现最核心的地方还是状态转移表的构建，有了状态转移表的构建算法，那么只要知道了哈夫曼编码表，我们就可以自己来重新构建一个新的解码用的状态转移表，而直接复用nginx给出的解码代码就可以实现新的哈夫曼编码的解码功能。那么如何来构造状态转移表呢？
4.1 主要过程
- 创建第一个状态，该状态表示初始状态，即什么都没有输入，或者每次读取的4个比特正好解码完毕（没有待解码的比特多余），我们设置初始状态的编码为“”。
- 为每种不足4比特的组合情况都创建一个状态，一共14个状态，即多余1比特的2种状态，多余2比特的4种状态，多余3比特的8种状态，设置每个状态的编码为对应的比特，如多余1比特的状态0，对应的状态编码为“0”，犹如多余3个比特的状为111，那么对应的状态编码为“111”。
- 将当前的状态设置为初始状态0，开始进入循环。3.1. 针对当前状态下的每一种4比特输入（即总共16种），和当前状态的编码一起组成新状态的编码，譬如当前状态编码为"1"，转移弧对应的比特为"1010"，那么新状态的编码为11010，然后用这个新的状态编码去查询已知的哈夫曼编码表。3.2. 如果哈夫曼编码表中能够查找到有哈夫曼编码是待查找的编码的前缀，那么将当前的编码去掉前缀，只留下<4比特的后缀，然后将当前的状态转移弧的下一状态设置为步骤2中设置的同编码的状态；如果去掉前缀后，没有剩余的比特，也就是当前正在查找的编码正好和哈夫曼表中的某个编码完全匹配，则下一状态设置为0，即初始状态。当然，无论是有剩余还是没有剩余比特，都需要设置输出编码为查到的哈夫曼编码表中对应的字符，并设置emit为1。3.3. 如果哈夫曼编码表中能够查找不到有哈夫曼编码是待查找的编码的前缀的记录，但是当前待查找的编码是某个哈夫曼编码表中的编码的前缀，那么创建一个新的状态（其编码即为当前待查找编码），并将当前状态转移弧设置为新创建的状态。3.4 否则，设置当前状态该转移弧为状态自己，表示编码错误。
- 将当前状态 1，如果当前状态没有超出状态表的末尾，则跳转到步骤3.1继续执行。
- 循环输出构建的转移状态表。
- 结束。
4.2 关于结束状态的补充说明
在《nginx中的哈夫曼编解码算法[上]-编码》中，我们看到，如果待编码的字符串读取完毕，但是产生的哈夫曼编码码流的比特数不是正好8的倍数（即不能正好凑成整数个字节），那么编码器需要在末尾添加PADDING位为“1”的比特，使得输出的码流正好是整数个字节，以便进行存储或者发送。
所以，我们需要在解码器中有检测的能力，在解码带有PADDING位的码流的时候能够忽略这些比特位（最多7个比特），而不会误认为是码流不完整。
因此，在生成状态转移矩阵的时候，对于每个转移弧我们增加了一个ending字段属性，用来标记在目前的状态下读取到转移弧对应的4个比特后，是否可以进入到结束状态。
那么什么情况下可以定义为结束状态呢？
- 一种是带有emit的转移弧，如果剩下的比特都是1，那么可以设置为结束状态。
- 一种是带有emit的转移弧，如果没有剩余的比特，那么也可以设置为结束状态。
- 一种是步骤3.3中待查找的编码所有的比特都是“1”，那么也可以设置为结束状态。
以上就是构建状态转移矩阵的完整过程。
