HTTP/2 HPACK 实际应用举例

在上篇文章中，具体说明了 HPACK 算法中的 8 种场景(7 种 Name-value 的场景 + 1 种动态表更新场景)。

动态表大小更新有两种方式，一种是在 HEADERS 帧中直接修改(“001” 3 位模式开始)，另外一种方式是通过 SETTINGS 帧中的 SETTINGS_HEADER_TABLE_SIZE 中设置的。

在介绍 HPACK 实际应用之前，需要先来看看静态表的定义和 HTTP/2 中霍夫曼编码的定义。

一. 静态表定义

静态表（请参阅第 2.3.1 节）包含一个预定义且不可更改的 header 字段列表。

静态表是根据流行网站使用的最频繁的 header 字段创建的，并添加了 HTTP/2 特定的伪 header 字段（请参见 [HTTP2]的 8.1.2.1 节）。对于具有一些频繁值的 header 字段，为每个这些频繁值添加了一个条目。对于其他标题字段，添加了带有空值的条目。

表 1 列出了构成静态表的预定义 header 字段，并提供了每个条目的索引。

Index Header Name Header Value
1 :authority
2 :method GET
3 :method POST
4 :path /
5 :path /index.html
6 :scheme http
7 :scheme https
8 :status 200
9 :status 204
10 :status 206
11 :status 304
12 :status 400
13 :status 404
14 :status 500
15 accept-charset
16 accept-encoding gzip, deflate
17 accept-language
18 accept-ranges
19 accept
20 access-control-allow-origin
21 age
22 allow
23 authorization
24 cache-control
25 content-disposition
26 content-encoding
27 content-language
28 content-length
29 content-location
30 content-range
31 content-type
32 cookie
33 date
34 etag
35 expect
36 expires
37 from
38 host
39 if-match
40 if-modified-since
41 if-none-match
42 if-range
43 if-unmodified-since
44 last-modified
45 link
46 location
47 max-forwards
48 proxy-authenticate
49 proxy-authorization
50 range
51 referer
52 refresh
53 retry-after
54 server
55 set-cookie
56 strict-transport-security
57 transfer-encoding
58 user-agent
59 vary
60 via
61 www-authenticate

二. 霍夫曼编码

1. 霍夫曼算法

如果每个字符都是等长的编码形式，是否有一种算法能保证大幅压缩这些数据？等长的编码形式首先面临的一个问题是如何避免解压的时候出现歧义误读。

霍夫曼在 1952 年发现了最优前缀码的算法，算法的核心思想是：出现概率比较大的符号采用较短的编码，概率较小的符号采用较长的编码。

举个例子，一篇文章中有很多单词，我们讲所有字母出现的频率都统计出来，以 a、b、c、d、e、f 这 6 个字母为例，它们的出现频率分别如下：

HTTP/2 HPACK 实际应用举例

第一步先从这些频率中选取频率最小的 2 个，进行合并。左子树小，右子树大。合并成新的节点以后，再放回原有的节点中。

HTTP/2 HPACK 实际应用举例

重复第一步，直到所有节点都合并到一棵树上。

HTTP/2 HPACK 实际应用举例

最后给每个左子树的指针上编码为 0，右子树的指针上编码为 1。以上 6 个字母的最终编码是 a = 0, b = 101, c = 100, d = 111, e = 1101, f = 1100 。

2. 霍夫曼编码在 HTTP/2 中的定义

当使用霍夫曼编码对字符串字面进行编码时，使用以下霍夫曼代码（请参见第 5.2 节）。

此霍夫曼代码是从大量 HTTP header 样本获得的统计信息中生成的。这是规范的霍夫曼代码（请参见 [CANONICAL]），需要进行一些调整以确保没有符号具有唯一的代码长度。

表中的每一行均定义用于表示符号的代码：

sym：要表示的符号。它是八位字节的十进制值，可能以ASCII表示形式为前缀。特定的符号 “EOS” 用于指示字符串字面的结尾。

code as bits：符号的霍夫曼编码，表示为以2为基的整数，在最高有效位（MSB）上对齐。

code as hex：符号的霍夫曼编码，以十六进制整数表示，在最低有效位（LSB）上对齐。

len：代表符号的代码的位数。

例如，符号 47 的代码（对应于 ASCII 字符 “/”）由 6 位 “0”，“1”，“1”，“0”，“0”，“0”组成。这对应于以 6 位编码的值 0x18（以十六进制表示）。

原文：https://halfrost.com/http2-hpack-example/
我的收藏
上一篇HPACK: Header Compression for HTTP/2下一篇详解 HTTP/2 头压缩算法 —— HPACK

相关文章

小鼠研究显示阉割有助于长寿

小鼠研究显示阉割有助于长寿

Solidot 奇客
鳄鱼为何免受毁灭恐龙的小行星的影响？

鳄鱼为何免受毁灭恐龙的小行星的影响？

Solidot 奇客
5000名“洋景漂”引发的蝴蝶效应

5000名“洋景漂”引发的蝴蝶效应

虎嗅
【美国中期选举】罕见承认中期选举告急 特朗普誓当“否决先生”

【美国中期选举】罕见承认中期选举告急 特朗普誓当“否决先生”

联合早报》-国际-即时
【美国中期选举】阿拉斯加“真假沙利文”之争 联邦法官驳回诉讼司法部将上诉

【美国中期选举】阿拉斯加“真假沙利文”之争 联邦法官驳回诉讼司法部将上诉

联合早报》-国际-即时
韩国医疗旅游需求激增 首尔指定19家外国患者友善酒店

韩国医疗旅游需求激增 首尔指定19家外国患者友善酒店

联合早报》-国际-即时
sym code as bits
aligned to MSB		 code as hex
aligned to LSB		 len in 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
'}' (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)