用Rust手把手編寫一個wmproxy(代理，內網穿透等), HTTP改造篇之HPACK原理項目 ++wmproxy++ gite: https://gitee.com/tickbh/wmproxy github: https://github.com/tickbh/wmproxy HTTP/2的 ...

用Rust手把手編寫一個wmproxy(代理，內網穿透等), HTTP改造篇之HPACK原理

項目 ++wmproxy++

gite: https://gitee.com/tickbh/wmproxy

github: https://github.com/tickbh/wmproxy

HTTP/2的簡介

HTTP/1.1發表於1999年，該協議持續被使用到了至今
HTTP/2標準於2015年5月以RFC7540正式發表。由於HTTP2對1.1協議保持有高度的相容，並且主要以位元組傳輸，相比於1.1有更好的傳輸效率和更強大的傳輸能力，所以他快速流行起來

在2017年5月，全球排名前1000萬的網站中，有13.7%支持了HTTP/2。
在2019年6月，全球有36.5%的網站支持了HTTP/2

而http/3的標準基於UDP協議的制定，而UDP在很多場合受限相對嚴重，由此可以得出http/1.1和http/2將會並存非常長的一段時間。所以我們需要對兩種協議進行完全支持

庫的選擇

在這裡我們選擇自研的解析庫 webparse和HTTP服務框架wenmeng，可以將服務轉化成可以支持多協議的結構。此過程可能涉及到重寫頭信息，也可能添加頭信息，會涉及到HTTP2的頭部編碼問題，所以必須將HTTP2的代碼做完整的解析。

HTTP2的定義

HTTP2的RFC主要由7540和補充的7541，因為少量數據的請求如GET請求頭占比100%，頭部流量的優化變成了極為重要的性能提升點，所以很大的一部分把重點放在頭部（7541）的優化。

HPACK: HTTP2的頭部壓縮

頭部信息主要以下部分組成:
Header Field: 一個名稱-值對。無論是名稱還是值都由8位的位元組組成，但名稱限定為常見的編碼（可解析成String），值可以為純二進位。
Dynamic Table: 動態表是一個將存儲的頭部欄位與索引值相關聯的表。這個表是動態的，特定於一個編碼或解碼上下文。
Static Table: 靜態表是一個靜態地將頻繁出現的頭部欄位與索引值相關聯的表。這個表是有序的、只讀的、始終可訪問的，並且可以在所有編碼或解碼上下文之間共用。定義了一個常用的鍵值對以更好的壓縮如(:method, GET)可由一個位元組0x82表示
Header List: 一個頭部列表是有序的頭欄位集合，這些頭欄位被聯合編碼並可以包含重覆的頭欄位。一個完整的HTTP/2頭部塊中的頭欄位列表就是一個頭部列表。如返回:status必須在其它的頭前面，請求:method必須在其它前面，另一個因為需要動態添加到動態表裡，如果前後順序不一致的話，可能會導致動態表的映射值不一致，所以必須用列表的形式保證順序。
Header Field Representation: 一個頭欄位可以在編碼形式中表示為字面量或索引
Header Block: 一個有序的頭欄位表示列表，當解碼時，會產生一個完整的頭部列表。

動態表索引值

靜態表和動態表如何結合成一個單獨的索引地址空間。
在HPACK中，靜態表和動態表都被結合到一個單獨的索引地址空間中。
索引值在1和靜態表長度之間（包括兩端）指的是靜態表中的元素。
索引值嚴格大於靜態表長度指的是動態表中的元素。需要從索引中減去靜態表的長度以找到動態表中的索引。
嚴格大於兩個表長度之和的索引值必須被視為解碼錯誤。
對於一個大小為s的靜態表和大小為k的動態表，下麵的圖表展示了整個有效的索引地址空間。

<----------  索引地址空間 ---------->
<--      靜態表   -->  <--    動態表     -->
+---+-----------+---+  +---+-----------+---+
| 1 |    ...    | s |  |s+1|    ...    |s+k|
+---+-----------+---+  +---+-----------+---+
                       ^                   |
                       |                   V
                新值插入位置      超出大小刪除位置

如何索引

編碼的頭部欄位可以表示為索引或文字。
索引表示將頭部欄位定義為靜態表或動態表中的條目的引用。
文字表示通過指定其名稱和值來定義頭部欄位。頭部欄位名稱可以文字地表示或作為靜態表或動態表中的條目的引用。頭部欄位值以文字形式表示。
定義了三種不同的文字表示：
將頭部欄位作為新條目添加到動態表開頭的文字表示，如(custom-key, custom-value)。
不將頭部欄位添加到動態表的文字表示，如(:path, /wmproxy)。
不將頭部欄位添加到動態表，同時附加規定，此頭部欄位始終使用文字表示，尤其是當由中間人重新編碼時。此表示旨在保護不因壓縮而處於危險之中的頭部欄位值這些文字表示的選擇可以通過安全考慮來指導，以保護敏感的頭部欄位值(如Authorization: xxxx)，不能做任何的數據索引緩存。

頭部欄位名稱或頭部欄位值的文字表示可以直接或使用靜態Huffman編碼對八位位元組序列進行編碼。

長度編碼

整數被用於表示名稱索引、頭部欄位索引或字元串長度。整數的表示可以在一個八位位元組內的任何位置開始。為了允許優化的處理，整數的表示始終在八位位元組的末尾完成。
整數由兩部分表示：一個首碼，該首碼填充當前八位位元組，以及一個可選的八位位元組列表，當整數值不適合首碼時使用。首碼的位數（稱為N）是整數表示的參數。

如果整數值足夠小，即嚴格小於2^N-1，則在首碼的N位中對其進行編碼。
可表示0-31的值，前面三位被用來做別的用途，如string的長度首碼為1，如索引頭首碼為2

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? |       Value       |
+---+---+---+-------------------+

圖：首碼中編碼的整數值（以N=5為例），動態表長度更新即N=5

否則，首碼的所有位均設置為1，並且使用一個或多個八位位元組列表對值進行編碼，該值減去2^N-1。每個八位位元組的最高有效位用作續表標記：其值設置為1，列表中的最後一個八位位元組除外。八位位元組的其餘位用於編碼減小後的值。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? | 1   1   1   1   1 |
+---+---+---+-------------------+
| 1 |    Value-(2^N-1) LSB      |
+---+---------------------------+
               ...
+---+---------------------------+
| 0 |    Value-(2^N-1) MSB      |
+---+---------------------------+

圖：首碼後編碼的整數值（以N=5為例）

從八位位元組列表解碼整數值首先從列表中反轉八位位元組的順序。然後，對於每個八位位元組，刪除其最高有效位。將八位位元組的剩餘位連接起來，並增加2N-1以獲得整數值。

首碼大小N始終介於1和8位之間。以八位位元組邊界開始的整數具有8位首碼。

表示整數I的偽代碼如下：

if I < 2^N - 1, encode I on N bits
else
    encode (2^N - 1) on N bits #即N位的1
    I = I - (2^N - 1)
    while I >= 128
         encode (I % 128 + 128) on 8 bits
         I = I / 128
    encode I on 8 bits

解碼整數I的偽代碼如下：

decode I from the next N bits
if I < 2^N - 1, return I
else
    M = 0
    repeat
        B = next octet
        I = I + (B & 127) * 2^M
        M = M + 7
    while B & 128 == 128
    return I

在HPACK中跟長度相關的編解碼都用如上方式

字元串的表示

標題欄位名稱和標題欄位值可以表示為字元串文字。字元串文字編碼為一系列八進位數字，通過直接編碼字元串文字的八進位數字或使用霍夫曼編碼（參見［HUFFMAN］）。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| H |    String Length (7+)     |
+---+---------------------------+
|  String Data (Length octets)  |
+-------------------------------+

圖：字元串文字表示

字元串文字表示包含以下欄位：

H：一個1位的標記H，指示字元串的八進位數字是否使用霍夫曼編碼。如果1則表示用HUFFMAN編碼，如果為0則普通編碼
字元串長度：用於編碼字元串文字的八進位數字的數量，編碼為具有7位首碼的整數。
字元串數據：字元串文字的編碼數據。如果H為“0”，則編碼數據是字元串文字的原始八進位數字。如果H為“1”，則編碼數據是字元串文字的霍夫曼編碼。

霍夫曼編碼的優勢：
在頭信息中，可讀信息出現的頻率遠大於不可讀位元組出現的概率，也就是把0-255位元組按照頻率出現在概率進行數據的重編碼，如‘0’則編碼成‘00000’，按照ASCII的方式如果表示0需要8位的編碼，這裡就可以節省(8-5)/8=37.5%的數據大小。

頭信息索引

因為HTTP2是多次復用同一個連接，頭基本上會相同，如Cookie，HTTP2會將常用的（靜態編碼）和常用的（動態編碼）將其緩存下來，在下次發送的時候，只要發送一個位元組接收方就可以知道對方發送的頭文件信息。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |
+---+---------------------------+

圖: 頭信息索引，Index為長度編碼，遵循首碼1的長度編碼

增量索引的文字頭部欄位

增量索引文字頭部欄位表示法將一個頭部欄位附加到解碼後的頭部列表，並將其作為新條目插入到動態表中。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

表示名字是索引，即Name命中，如:path命中，值為新的值，添加到動態表裡

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |           0           |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

表示名字和值均沒有在原有的表裡，現將name和value添加到動態表裡。

索引的兩個首碼必須為01，如01000010十六進位寫法則是0x82，<61，查靜態表可得(:method, GET)，即我們通過一位元組表示請求方法為GET。

以下兩種情況首碼為0001開頭的則表示不添加到動態表中。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

不進行索引，但是從表中查Name，如authorization。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

從不進行索引

更新動態表的長度

動態表大小更新表示動態表大小發生了變化。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 |   Max size (5+)   |
+---+---------------------------+

可以設置新的最大的動態表長度。

至此HTTP2的頭部壓縮協議已基本瞭解完成，下一章將進行具體示例的分析。

8. 用Rust手把手編寫一個wmproxy(代理，內網穿透等), HTTP改造篇之HPACK原理