nginx中的哈夫曼编解码算法[上]-编码
1. 引言
在http2以前的http头部报文都是文本形式发送，http2为了优化网络对头部报文进行压缩编码使其内容更精简，发送更少的数据加快网络传输，采用压缩算法就是hpack。其中hpack算法在进行http header名字和值的压缩的使用使用了静态哈夫曼编码算法，因此nginx为了支持http2，实现了哈夫曼压缩的编解码来对http2进行支持。
本文通过对nginx的源码 进行分析，来深入理解nginx实现哈夫曼压缩编解码算法的精髓，借此深入领会nginx为了优化编解码算法所做的性能优化，从而为我们将来在编写类似编解码算法优化的时候提供借鉴思路。
本文不会从头分析哈夫曼编码算法的原理，因为关于哈夫曼算法的底层原理的介绍，在互联网上是一捞一大把，大家可以提前查找相关资料进行学习。本文重点是着眼于nginx的实现，本文的上篇介绍nginx如何来实现快速编码算法，本文的中篇介绍解码算法，本文的下篇将介绍如何来制作为实现解码算法的所需要的哈夫曼解码表。
2. 哈夫曼编码算法
http2的哈夫曼算法采用静态哈夫曼码表的方式来实现。而哈夫曼码表已经在RFC7541规范文档《 [Appendix B](https://httpwg.org/specs/rfc7541.html#rfc.section.B)》部分进行了明确规定，编码表是完全静态的，不会因为站点的不同或者http2请求的不同采用不同的哈夫曼表。因此nginx在实现算法的时候不需要自己生成哈夫曼码表，而是直接采用RFC7541规范中定义的哈夫曼表，通过一边读入待编码字符一边查找编码表中的压缩编码，并不断输出的方式来进行编码。
以下摘录了RFC7541中定义的码表，如下：
code
code as bits as hex len
sym aligned to MSB aligned in
to LSB bits
( 0) |11111111|11000 1ff8 [13]
( 1) |11111111|11111111|1011000 7fffd8 [23]
( 2) |11111111|11111111|11111110|0010 fffffe2 [28]
( 3) |11111111|11111111|11111110|0011 fffffe3 [28]
( 4) |11111111|11111111|11111110|0100 fffffe4 [28]
( 5) |11111111|11111111|11111110|0101 fffffe5 [28]
( 6) |11111111|11111111|11111110|0110 fffffe6 [28]
( 7) |11111111|11111111|11111110|0111 fffffe7 [28]
( 8) |11111111|11111111|11111110|1000 fffffe8 [28]
( 9) |11111111|11111111|11101010 ffffea [24]
( 10) |11111111|11111111|11111111|111100 3ffffffc [30]
( 11) |11111111|11111111|11111110|1001 fffffe9 [28]
( 12) |11111111|11111111|11111110|1010 fffffea [28]
( 13) |11111111|11111111|11111111|111101 3ffffffd [30]
( 14) |11111111|11111111|11111110|1011 fffffeb [28]
( 15) |11111111|11111111|11111110|1100 fffffec [28]
( 16) |11111111|11111111|11111110|1101 fffffed [28]
( 17) |11111111|11111111|11111110|1110 fffffee [28]
( 18) |11111111|11111111|11111110|1111 fffffef [28]
( 19) |11111111|11111111|11111111|0000 ffffff0 [28]
( 20) |11111111|11111111|11111111|0001 ffffff1 [28]
( 21) |11111111|11111111|11111111|0010 ffffff2 [28]
( 22) |11111111|11111111|11111111|111110 3ffffffe [30]
( 23) |11111111|11111111|11111111|0011 ffffff3 [28]
( 24) |11111111|11111111|11111111|0100 ffffff4 [28]
( 25) |11111111|11111111|11111111|0101 ffffff5 [28]
( 26) |11111111|11111111|11111111|0110 ffffff6 [28]
( 27) |11111111|11111111|11111111|0111 ffffff7 [28]
( 28) |11111111|11111111|11111111|1000 ffffff8 [28]
( 29) |11111111|11111111|11111111|1001 ffffff9 [28]
( 30) |11111111|11111111|11111111|1010 ffffffa [28]
( 31) |11111111|11111111|11111111|1011 ffffffb [28]
' ' ( 32) |010100 14 [ 6]
'!' ( 33) |11111110|00 3f8 [10]
'"' ( 34) |11111110|01 3f9 [10]
'#' ( 35) |11111111|1010 ffa [12]
'$' ( 36) |11111111|11001 1ff9 [13]
'%' ( 37) |010101 15 [ 6]
'&' ( 38) |11111000 f8 [ 8]
''' ( 39) |11111111|010 7fa [11]
'(' ( 40) |11111110|10 3fa [10]
')' ( 41) |11111110|11 3fb [10]
'*' ( 42) |11111001 f9 [ 8]
'+' ( 43) |11111111|011 7fb [11]
',' ( 44) |11111010 fa [ 8]
'-' ( 45) |010110 16 [ 6]
'.' ( 46) |010111 17 [ 6]
'/' ( 47) |011000 18 [ 6]
'0' ( 48) |00000 0 [ 5]
'1' ( 49) |00001 1 [ 5]
'2' ( 50) |00010 2 [ 5]
'3' ( 51) |011001 19 [ 6]
'4' ( 52) |011010 1a [ 6]
'5' ( 53) |011011 1b [ 6]
'6' ( 54) |011100 1c [ 6]
'7' ( 55) |011101 1d [ 6]
'8' ( 56) |011110 1e [ 6]
'9' ( 57) |011111 1f [ 6]
':' ( 58) |1011100 5c [ 7]
';' ( 59) |11111011 fb [ 8]
'<' ( 60) |11111111|1111100 7ffc [15]
'=' ( 61) |100000 20 [ 6]
'>' ( 62) |11111111|1011 ffb [12]
'?' ( 63) |11111111|00 3fc [10]
'@' ( 64) |11111111|11010 1ffa [13]
'A' ( 65) |100001 21 [ 6]
'B' ( 66) |1011101 5d [ 7]
'C' ( 67) |1011110 5e [ 7]
'D' ( 68) |1011111 5f [ 7]
'E' ( 69) |1100000 60 [ 7]
'F' ( 70) |1100001 61 [ 7]
'G' ( 71) |1100010 62 [ 7]
'H' ( 72) |1100011 63 [ 7]
'I' ( 73) |1100100 64 [ 7]
'J' ( 74) |1100101 65 [ 7]
'K' ( 75) |1100110 66 [ 7]
'L' ( 76) |1100111 67 [ 7]
'M' ( 77) |1101000 68 [ 7]
'N' ( 78) |1101001 69 [ 7]
'O' ( 79) |1101010 6a [ 7]
'P' ( 80) |1101011 6b [ 7]
'Q' ( 81) |1101100 6c [ 7]
'R' ( 82) |1101101 6d [ 7]
'S' ( 83) |1101110 6e [ 7]
'T' ( 84) |1101111 6f [ 7]
'U' ( 85) |1110000 70 [ 7]
'V' ( 86) |1110001 71 [ 7]
'W' ( 87) |1110010 72 [ 7]
'X' ( 88) |11111100 fc [ 8]
'Y' ( 89) |1110011 73 [ 7]
'Z' ( 90) |11111101 fd [ 8]
'[' ( 91) |11111111|11011 1ffb [13]
'\' ( 92) |11111111|11111110|000 7fff0 [19]
']' ( 93) |11111111|11100 1ffc [13]
'^' ( 94) |11111111|111100 3ffc [14]
'_' ( 95) |100010 22 [ 6]
'`' ( 96) |11111111|1111101 7ffd [15]
'a' ( 97) |00011 3 [ 5]
'b' ( 98) |100011 23 [ 6]
'c' ( 99) |00100 4 [ 5]
'd' (100) |100100 24 [ 6]
'e' (101) |00101 5 [ 5]
'f' (102) |100101 25 [ 6]
'g' (103) |100110 26 [ 6]
'h' (104) |100111 27 [ 6]
'i' (105) |00110 6 [ 5]
'j' (106) |1110100 74 [ 7]
'k' (107) |1110101 75 [ 7]
'l' (108) |101000 28 [ 6]
'm' (109) |101001 29 [ 6]
'n' (110) |101010 2a [ 6]
'o' (111) |00111 7 [ 5]
'p' (112) |101011 2b [ 6]
'q' (113) |1110110 76 [ 7]
'r' (114) |101100 2c [ 6]
's' (115) |01000 8 [ 5]
't' (116) |01001 9 [ 5]
'u' (117) |101101 2d [ 6]
'v' (118) |1110111 77 [ 7]
'w' (119) |1111000 78 [ 7]
'x' (120) |1111001 79 [ 7]
'y' (121) |1111010 7a [ 7]
'z' (122) |1111011 7b [ 7]
'{' (123) |11111111|1111110 7ffe [15]
'|' (124) |11111111|100 7fc [11]
'}' (125) |11111111|111101 3ffd [14]
'~' (126) |11111111|11101 1ffd [13]
(127) |11111111|11111111|11111111|1100 ffffffc [28]
(128) |11111111|11111110|0110 fffe6 [20]
(129) |11111111|11111111|010010 3fffd2 [22]
(130) |11111111|11111110|0111 fffe7 [20]
(131) |11111111|11111110|1000 fffe8 [20]
(132) |11111111|11111111|010011 3fffd3 [22]
(133) |11111111|11111111|010100 3fffd4 [22]
(134) |11111111|11111111|010101 3fffd5 [22]
(135) |11111111|11111111|1011001 7fffd9 [23]
(136) |11111111|11111111|010110 3fffd6 [22]
(137) |11111111|11111111|1011010 7fffda [23]
(138) |11111111|11111111|1011011 7fffdb [23]
(139) |11111111|11111111|1011100 7fffdc [23]
(140) |11111111|11111111|1011101 7fffdd [23]
(141) |11111111|11111111|1011110 7fffde [23]
(142) |11111111|11111111|11101011 ffffeb [24]
(143) |11111111|11111111|1011111 7fffdf [23]
(144) |11111111|11111111|11101100 ffffec [24]
(145) |11111111|11111111|11101101 ffffed [24]
(146) |11111111|11111111|010111 3fffd7 [22]
(147) |11111111|11111111|1100000 7fffe0 [23]
(148) |11111111|11111111|11101110 ffffee [24]
(149) |11111111|11111111|1100001 7fffe1 [23]
(150) |11111111|11111111|1100010 7fffe2 [23]
(151) |11111111|11111111|1100011 7fffe3 [23]
(152) |11111111|11111111|1100100 7fffe4 [23]
(153) |11111111|11111110|11100 1fffdc [21]
(154) |11111111|11111111|011000 3fffd8 [22]
(155) |11111111|11111111|1100101 7fffe5 [23]
(156) |11111111|11111111|011001 3fffd9 [22]
(157) |11111111|11111111|1100110 7fffe6 [23]
(158) |11111111|11111111|1100111 7fffe7 [23]
(159) |11111111|11111111|11101111 ffffef [24]
(160) |11111111|11111111|011010 3fffda [22]
(161) |11111111|11111110|11101 1fffdd [21]
(162) |11111111|11111110|1001 fffe9 [20]
(163) |11111111|11111111|011011 3fffdb [22]
(164) |11111111|11111111|011100 3fffdc [22]
(165) |11111111|11111111|1101000 7fffe8 [23]
(166) |11111111|11111111|1101001 7fffe9 [23]
(167) |11111111|11111110|11110 1fffde [21]
(168) |11111111|11111111|1101010 7fffea [23]
(169) |11111111|11111111|011101 3fffdd [22]
(170) |11111111|11111111|011110 3fffde [22]
(171) |11111111|11111111|11110000 fffff0 [24]
(172) |11111111|11111110|11111 1fffdf [21]
(173) |11111111|11111111|011111 3fffdf [22]
(174) |11111111|11111111|1101011 7fffeb [23]
(175) |11111111|11111111|1101100 7fffec [23]
(176) |11111111|11111111|00000 1fffe0 [21]
(177) |11111111|11111111|00001 1fffe1 [21]
(178) |11111111|11111111|100000 3fffe0 [22]
(179) |11111111|11111111|00010 1fffe2 [21]
(180) |11111111|11111111|1101101 7fffed [23]
(181) |11111111|11111111|100001 3fffe1 [22]
(182) |11111111|11111111|1101110 7fffee [23]
(183) |11111111|11111111|1101111 7fffef [23]
(184) |11111111|11111110|1010 fffea [20]
(185) |11111111|11111111|100010 3fffe2 [22]
(186) |11111111|11111111|100011 3fffe3 [22]
(187) |11111111|11111111|100100 3fffe4 [22]
(188) |11111111|11111111|1110000 7ffff0 [23]
(189) |11111111|11111111|100101 3fffe5 [22]
(190) |11111111|11111111|100110 3fffe6 [22]
(191) |11111111|11111111|1110001 7ffff1 [23]
(192) |11111111|11111111|11111000|00 3ffffe0 [26]
(193) |11111111|11111111|11111000|01 3ffffe1 [26]
(194) |11111111|11111110|1011 fffeb [20]
(195) |11111111|11111110|001 7fff1 [19]
(196) |11111111|11111111|100111 3fffe7 [22]
(197) |11111111|11111111|1110010 7ffff2 [23]
(198) |11111111|11111111|101000 3fffe8 [22]
(199) |11111111|11111111|11110110|0 1ffffec [25]
(200) |11111111|11111111|11111000|10 3ffffe2 [26]
(201) |11111111|11111111|11111000|11 3ffffe3 [26]
(202) |11111111|11111111|11111001|00 3ffffe4 [26]
(203) |11111111|11111111|11111011|110 7ffffde [27]
(204) |11111111|11111111|11111011|111 7ffffdf [27]
(205) |11111111|11111111|11111001|01 3ffffe5 [26]
(206) |11111111|11111111|11110001 fffff1 [24]
(207) |11111111|11111111|11110110|1 1ffffed [25]
(208) |11111111|11111110|010 7fff2 [19]
(209) |11111111|11111111|00011 1fffe3 [21]
(210) |11111111|11111111|11111001|10 3ffffe6 [26]
(211) |11111111|11111111|11111100|000 7ffffe0 [27]
(212) |11111111|11111111|11111100|001 7ffffe1 [27]
(213) |11111111|11111111|11111001|11 3ffffe7 [26]
(214) |11111111|11111111|11111100|010 7ffffe2 [27]
(215) |11111111|11111111|11110010 fffff2 [24]
(216) |11111111|11111111|00100 1fffe4 [21]
(217) |11111111|11111111|00101 1fffe5 [21]
(218) |11111111|11111111|11111010|00 3ffffe8 [26]
(219) |11111111|11111111|11111010|01 3ffffe9 [26]
(220) |11111111|11111111|11111111|1101 ffffffd [28]
(221) |11111111|11111111|11111100|011 7ffffe3 [27]
(222) |11111111|11111111|11111100|100 7ffffe4 [27]
(223) |11111111|11111111|11111100|101 7ffffe5 [27]
(224) |11111111|11111110|1100 fffec [20]
(225) |11111111|11111111|11110011 fffff3 [24]
(226) |11111111|11111110|1101 fffed [20]
(227) |11111111|11111111|00110 1fffe6 [21]
(228) |11111111|11111111|101001 3fffe9 [22]
(229) |11111111|11111111|00111 1fffe7 [21]
(230) |11111111|11111111|01000 1fffe8 [21]
(231) |11111111|11111111|1110011 7ffff3 [23]
(232) |11111111|11111111|101010 3fffea [22]
(233) |11111111|11111111|101011 3fffeb [22]
(234) |11111111|11111111|11110111|0 1ffffee [25]
(235) |11111111|11111111|11110111|1 1ffffef [25]
(236) |11111111|11111111|11110100 fffff4 [24]
(237) |11111111|11111111|11110101 fffff5 [24]
(238) |11111111|11111111|11111010|10 3ffffea [26]
(239) |11111111|11111111|1110100 7ffff4 [23]
(240) |11111111|11111111|11111010|11 3ffffeb [26]
(241) |11111111|11111111|11111100|110 7ffffe6 [27]
(242) |11111111|11111111|11111011|00 3ffffec [26]
(243) |11111111|11111111|11111011|01 3ffffed [26]
(244) |11111111|11111111|11111100|111 7ffffe7 [27]
(245) |11111111|11111111|11111101|000 7ffffe8 [27]
(246) |11111111|11111111|11111101|001 7ffffe9 [27]
(247) |11111111|11111111|11111101|010 7ffffea [27]
(248) |11111111|11111111|11111101|011 7ffffeb [27]
(249) |11111111|11111111|11111111|1110 ffffffe [28]
(250) |11111111|11111111|11111101|100 7ffffec [27]
(251) |11111111|11111111|11111101|101 7ffffed [27]
(252) |11111111|11111111|11111101|110 7ffffee [27]
(253) |11111111|11111111|11111101|111 7ffffef [27]
(254) |11111111|11111111|11111110|000 7fffff0 [27]
(255) |11111111|11111111|11111011|10 3ffffee [26]
EOS (256) |11111111|11111111|11111111|111111 3fffffff [30]如字母A，对应的ASCII码为65，在表中对应的哈夫曼编码为100001，占6个bit；再比如，字母B，对应的ASCII码为66，在表中对应的哈夫曼编码为1011101，占7个bit。HTTP2利用哈夫曼编码将HTTP头中ASCII字母出现频率高的字母分配相对较短的编码来达到压缩的目的。由于其采用的是静态哈夫曼码表，基于的是对大量HTTP请求和响应头中的字母出现概率的先验统计得到的哈夫曼码表，因此，HTTP2中采用的码表一般不建议应用用于其他领域，否则可能导致压缩后的数据反而变得更大。
为了在压缩编码的时候，同时执行HTTP头的大写到小写的转换，因此nginx定义了两个哈夫曼码表。码表的名字分别为：ngx_http_huff_encode_table 和 ngx_http_huff_encode_table_lc。
在 ngx_http_huff_encode_table_lc表中定义的A-Z,a-z大写字母对应的小写字母的码字是相同的。如下：
这样就能够在进行编码的时候顺便将字符统一转变成了小写字母，一定程度上提升了性能。
下面来分析一下nginx的哈夫曼编码算法的实现源码：
size_t
ngx_http_huff_encode(u_char *src, size_t len, u_char *dst, ngx_uint_t lower)
{
u_char *end;
size_t hlen;
ngx_uint_t buf, pending, code;
ngx_http_huff_encode_code_t *table, *next;
/* 根据lower标记选择不同的码表 */
table = lower ? ngx_http_huff_encode_table_lc
: ngx_http_huff_encode_table;
hlen = 0; /* 实际输出到dst的字节数 */
buf = 0; /* 输出内容的临时4字节缓存 */
pending = 0;
end = src + len; /* end为待编码内容的结束位置 */
while (src != end) {
next = &table[*src++]; /* next为当前字符对应的码表元素 */
code = next->code; /* code为当前字符对应的哈夫曼编码 */
pending += next->len; /* next->len为当前code哈夫曼编码的比特数 */
/* pending:尚未输出到dst的已经编码的比特 */
/* accumulate bits */
if (pending < sizeof(buf) * 8) { /* buf缓存的比特还没有满，则继续缓存到buf中*/
buf |= code << (sizeof(buf) * 8 - pending);
continue;
}
if (hlen + sizeof(buf) >= len) {
return 0; /* 输出到dst的字节数超过输入的字节数，
直接返回0，表示压缩失败 */
}
/* 将当前的字符对应的编码比特拆分成2部分存入，
先存入左边的部分，并且正好使buf存满，buf存满后就输出到dst
再存入右边的部分到buf
*/
pending -= sizeof(buf) * 8;
buf |= code >> pending;
/* 按照网络字节顺序输出到dst */
ngx_http_huff_encode_buf(&dst[hlen], buf);
hlen += sizeof(buf); /* 变更输出到dst的内容长度 */
buf = pending ? code << (sizeof(buf) * 8 - pending) : 0;
}
/* pending=0表示正好buf中的内容已经都输出到了dst，所以可以直接返回hlen */
if (pending == 0) {
return hlen;
}
/* 因为编码输出可能不是正好整数个字节，这里buf后面未满的比特位都填充1 */
buf |= (ngx_uint_t) -1 >> pending;
pending = ngx_align(pending, 8); /* 将pending向上进整对齐到8 */
if (hlen + pending / 8 >= len) { /* 如果超过了src的长度，返回压缩失败 */
return 0;
}
buf >>= sizeof(buf) * 8 - pending;
/* 将pending在buf中的编码比特按照网络字节顺序(即先输出高位)输出到dst中 */
do {
pending -= 8;
dst[hlen++] = (u_char) (buf >> pending);
} while (pending);
return hlen;
}
在这里，需要特别提一下的是，为了提升编码性能，nginx对输出的编码采用了buf缓存，等到输出的bit存满一个ngx_uint_t才会用网络字节序的方式输出到目标缓冲区dst中。
那么添加buf缓存，后面还不是要存入目标缓冲区吗？不是步骤变多了，怎么会反而能够提升性能呢？我们要记得，buf变量在编译器优化的时候是可以将其分配在寄存器中的，这样子多次的编码输出只要保存到性能高出内存至少一个数量级的寄存器，而不需要频繁操作内存了。下面的第一个图显示的是没有经过编译器优化的汇编代码，第二个图是经过编译器优化后的汇编代码：
[没有经过编译器优化的汇编代码]
[经过编译器优化的汇编代码]
第二张图是在gcc 7.1命令行添加了-O2后的效果，可以明显看到已经被优化到%r10d寄存器了（%r10d 表示的是 r10 寄存器的低 32 位部分）。
退一步讲，如果即使没有进行编译器优化，buf变量仍然是被分配在内存中的话，由于变量buf对应的内存地址是一个固定的地址，在编码运算的过程中非常有可能是在CPU的高速缓存中的，而不像dst那样，可能长长不能在CPU高速缓存中被命中。
因此，通过buf缓存的输出优化，从一定程度上提升了哈夫曼编码的性能。
3. 小结
以上介绍了nginx的哈夫曼编码算法的编码实现原理。nginx采用查表的方法，加上buf输出缓冲区，对编码算法的性能进行了很好地优化，其优化思想非常值得我们学习借鉴。
中篇将介绍nginx的哈夫曼解码算法的实现原理。
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2024-05-06，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读