339.txt

* 仕様書

[REFS[
- [1] [CITE@en[RFC 7541 - HPACK: Header Compression for HTTP/2]] ([TIME[2015-05-15 10:13:02 +09:00]] 版) <https://tools.ietf.org/html/rfc7541>
]REFS]

* データ構造

[11] [RUBYB[[[符号化器]]]@en[encoder]]が[[符号化]]を行い、
[RUBYB[[[復号器]]]@en[decoder]]が[[復号]]を行います。

[49] [RUBYB[[[初等型]]]@en[primitive type]]として符号無し可変長整数とオクテット列があります。
[SRC[>>1]]

* ヘッダーブロック

[5] [DFN[[RUBYB[ヘッダーリスト]@en[header list]]]]は、
[[ヘッダー欄表現]]を連結したものです。 [SRC[>>1]]

[28] 重複する[[ヘッダー欄]]を含むことができます。
[[HTTP/2]] [[header block]] に含まれる[[ヘッダー欄]]の完全なリストは、
[[ヘッダーリスト]]です。 [SRC[>>1]]

[7] [DFN[[RUBYB[ヘッダーブロック]@en[header block]]]]は、
[[ヘッダー欄表現]]の順序付きリストで、[[復号]]すると完全な[[ヘッダーリスト]]が得られるものです。
[SRC[>>1]]

[37] [[ヘッダーブロック]]の先頭には[[動的表サイズ更新]]があるかもしれません。

[FIG(railroad)[
= ?
== [[動的表サイズ更新]]
= *
== [[ヘッダー欄表現]]
]FIG]

[8] [[符号化器]]は、[[ヘッダーブロック]]中の[[ヘッダー欄]]の順序を元の[[ヘッダーリスト]]中の[[ヘッダー欄]]の順序のままとしなければ[['''なりません''']]。 [SRC[>>1]]

[9] [[復号器]]は、[[復号]]した[[ヘッダーリスト]]中の[[ヘッダー欄]]の順序を[[ヘッダーブロック]]中の順序のままとしなければ[['''なりません''']]。 [SRC[>>1]]

[27] [[復号器]]は、[[ヘッダーブロック]]内の[[ヘッダー欄表現]]を順に処理し、
元の[[ヘッダーリスト]]を再構築します。 [SRC[>>1]]

* ヘッダー欄

[2] [DFN[[RUBYB[ヘッダー欄]@en[header field]]]]は、名前と値の組です。
いずれも不透明な[[オクテット列]]として扱います。 [SRC[>>1]]

[6] [DFN[[RUBYB[ヘッダー欄表現]@en[header field representation]]]]は、
[[ヘッダー欄]]を索引表現またはリテラル表現によって[[符号化]]したものです。 [SRC[>>1]]

[FIG(railroad)[
= |
== [[索引表現]]
== [[リテラル表現]] (索引付けする)
== [[リテラル表現]] (索引付けしない)
== [[リテラル表現]] (決して索引付けしない)
]FIG]

[29] [[復号器]]は、[[ヘッダー欄表現]]を次のようにしなければ[['''なりません''']]
[SRC[>>1]]。
[FIG(steps)[
= [30] [[索引]]表現なら、
== [[索引]]で参照されている項目の[[ヘッダー欄]]を、[[ヘッダーリスト]]の末尾に追加します。
= [31] リテラル表現なら、
== [32] [[ヘッダー欄]]を、[[ヘッダーリスト]]の末尾に追加します。
== [33] [[動的表]]に追加するものなら、
=== [[ヘッダー欄]]を[[動的表]]の先頭に追加します。
(これに伴い [[eviction]] が発生することがあります。)
]FIG]

** 索引表現

[19] [RUBYB[[[索引]]表現]@en[indexed representation]]は、[[静的表]]または[[動的表]]上の項目を参照する形で[[ヘッダー欄]]を表しています。 [SRC[>>1]]

[64] 索引表現は、最初の1ビットが [CODE[1]] でその後の7ビットを[[接頭辞]]とする[[整数]]で構成され、この[[整数]]が[[索引]]を表します。 [SRC[>>1]]

[FIG(packet)[
:width:8

=1 [CODE[1]]
=7 [[整数]]
]FIG]

** リテラル表現

[20] [RUBYB[[[リテラル]]]@en[literal]]表現は、名前と値を指定する形で[[ヘッダー欄]]を表しています。
名前は、[[リテラル]]により、または[[静的表]]または[[動的表]]上の項目を参照する形で表します。
値は、[[リテラル]]により表します。 [SRC[>>1]]

[21] [RUBYB[[[リテラル]]表現]@en[literal representation]]には、次の3通りがあります [SRC[>>1]]。 
[FIG(list)[
- [22] [[動的表]]の最初に新しい項目として[[ヘッダー欄]]を追加する (索引付けする) もの
- [23] [[動的表]]に[[ヘッダー欄]]を追加しない (索引付けしない) もの
- [24] [[動的表]]に[[ヘッダー欄]]を追加しないもので、しかも常にリテラル表現とする
(絶対に索引付けしない) もの
]FIG]

[26] 索引付けを行うリテラル表現では、次のようにします [SRC[>>1]]。
[FIG(list)[
= [69] 最初の2ビットは [CODE[01]] とします。
= [66] [[ヘッダー欄]]の名前を[[索引]]によって表現するなら、
== [70] 次の6ビットを[[接頭辞]]とする[[整数]]によってその[[索引]]を示します。
= [67] [[ヘッダー欄]]の名前を文字列リテラルによって表現するなら、
== [72] 次の6ビットをすべて 0 とし、その後に名前を文字列リテラルとして指定します。
= [68] その後に[[ヘッダー欄]]の値を文字列リテラルとして指定します。
]FIG]

[FIG(packet)[
:width:16:

= 1 [CODE[0]]
= 1 [CODE[1]]
= 6 索引
= 24... 値
]FIG]

[FIG(packet)[
:width:16:

= 1 [CODE[0]]
= 1 [CODE[1]]
= 6 [CODE[0]]
= 8 名前
= 16... 値
]FIG]

[71] 索引付けを行わないリテラル表現では、次のようにします [SRC[>>1]]。
[FIG(list)[
= [74] 最初の3ビットは [CODE[000]] とします。
= [87] 次の1ビットは[[転送]]時に索引付けしても構わないなら [CODE[0]]、
絶対に索引付けしてはならないなら [CODE[1]] とします。
= [75] [[ヘッダー欄]]の名前を[[索引]]によって表現するなら、
== [76] 次の4ビットを[[接頭辞]]とする[[整数]]によってその[[索引]]を示します。
= [77] [[ヘッダー欄]]の名前を文字列リテラルによって表現するなら、
== [78] 次の4ビットをすべて 0 とし、その後に名前を文字列リテラルとして指定します。
= [79] その後に[[ヘッダー欄]]の値を文字列リテラルとして指定します。
]FIG]

[FIG(packet)[
:width:16:

= 1 [CODE[0]]
= 1 [CODE[0]]
= 1 [CODE[0]]
= 1 絶対
= 4 索引
= 24... 値
]FIG]

[FIG(packet)[
:width:16:

= 1 [CODE[0]]
= 1 [CODE[0]]
= 1 [CODE[0]]
= 1 絶対
= 4 [CODE[0]]
= 8 名前
= 16... 値
]FIG]

[86] [[中間器]]は、[[転送]]時に絶対に索引付けしない ([CODE[0001]]) 
表現で符号化された[[ヘッダー欄]]は、
同じ表現のまま符号化しなければ[['''なりません''']] [SRC[>>1]]。

;; [25] これは[[圧縮]]することで危険になる[[ヘッダー欄]]を保護するためのものです。 [SRC[>>1]]

;; [73] [[ヘッダー名]]を索引により表現するかリテラルにより表現するかを変えて良いのかは定かではありません。

* 表

[10] [[復号器]]は、[DFN[[RUBYB[復号文脈]@en[decoding context]]]]として[[動的表]]を維持する必要があります。
動的な状態として必要なのは[[動的表]]のみです。 [SRC[>>1]]

[12] [[エンドポイント]]は、双方向通信のため、
[[符号化]]用と[[復号]]用で別の[[動的表]]を維持する必要があります。 [SRC[>>1]]

[4] [DFN[[RUBYB[静的表]@en[static table]]]]は、頻出[[ヘッダー欄]]を索引値に関連付ける表です。
本表は順序があり、読み取り専用で、常にアクセス可能で、
すべての[[符号化]]や[[復号]]の文脈で共有できます。
本表は予め定義された共通の[[ヘッダー欄]]を含んでいます。 [SRC[>>1]]

[3] [DFN[[RUBYB[動的表]@en[dynamic table]]]]は、
蓄積された[[ヘッダー欄]]を[RUBYB[索引値]@en[index value]]に関連付ける表です。 
本表は動的であり、[[符号化]]や[[復号]]の文脈に固有のものです。
[[FIFO]] で、最初の最新の[RUBYB[項目]@en[entry]]が最小の索引を持ち、
最古の項目が最高の索引を持ちます。
[[符号化器]]は、[[符号化]]対象の[[ヘッダーリスト]]で繰り返し登場する[[ヘッダー欄]]を[RUBYB[索引付け]@en[index]]するために使うことができます。 [SRC[>>1]]

[14] [[動的表]]の初期状態は、空です。 [SRC[>>1]]

[15] [[動的表]]は、重複する (同名同値の) 項目を含むことがあります。
[[復号器]]はこれをエラーとしては[['''なりません''']]。 [SRC[>>1]]

[16] [[符号化器]]は、[[動的表]]をどう使うか決めることができ、
従ってどれだけ[[メモリー]]を消費するかを決めることができます。
[[復号器]]のメモリー要件の制限のために[[動的表]]のサイズは厳密に上界が設けられています。
[SRC[>>1]]

** 索引

[17] 表上の項目は、[DFN[[RUBYB[索引]@en[index]]]]により参照されます。

[13] [[動的表]]と[[静的表]]は、どちらも共通の[RUBYB[索引番地空間]@en[index address space]]上にあります。
[CODE[[[1]]]] [[以上]]、[[静的表]]の大きさ[[以下]]の[[索引]]は、
[[静的表]]上の項目を表しています。それよりも大きな[[索引]]は、
[[動的表]]上の項目を表しています。 [SRC[>>1]]

[18] 両[[表]]の長さの[[和]]よりも大きな[[索引]]は、
復号エラーとしなければ[['''なりません''']] [SRC[>>1]]。

[65] [[索引]]表現における値 0 は、復号エラーとしなければ[['''なりません''']] [SRC[>>1]]。

** サイズ制限

[34] [[動的表]]の[DFN[[RUBYB[サイズ]@en[size]]]]は、各項目のサイズの[[和]]です。 [SRC[>>1]]

[35] 項目の[DFN[[RUBYB[サイズ]@en[size]]]]は、名前のオクテット長と値のオクテット長と
32 の[[和]]です。 [SRC[>>1]]

;; [36] [[Huffman符号化]]は適用しない状態の長さです。 [SRC[>>1]]

[39] [[符号化器]]は、[[動的表]]サイズを最大サイズ[[以下]]としなければ[['''なりません''']]。
[SRC[>>1]]

[40] [[動的表]]の最大サイズの変更は、[DFN[[RUBYB[動的表サイズ更新]@en[dynamic table size update]]]]により通知されます。
[[動的表サイズ更新]]は、変更の後の最初の[[ヘッダーブロック]]の最初になければ[['''なりません''']]。 [SRC[>>1]]

[41] [[HTTP/2]] では、[[設定]]の [[acknowledgment]] の後に当たります。 [SRC[>>1]]

[42] 2つの[[ヘッダーブロック]]の転送の間に最大サイズの変更が複数回行われた時は、
最小サイズを[[動的表サイズ更新]]で通知しなければ[['''なりません''']]。
最後のサイズも通知しなければなりません。 [SRC[>>1]]

;; [43] 0 を設定し、元に戻すことで、[[動的表]]の内容を消去できます。 [SRC[>>1]]

[80] [[動的表サイズ更新]]は、先頭の3ビットが [CODE[001]] で、
その後5ビットを[[接頭辞]]とする[[整数]]によって新しい最大サイズを表します [SRC[>>1]]。

[FIG(packet)[
:width:16

= 1 [CODE[0]]
= 1 [CODE[0]]
= 0 [CODE[1]]
= 5 最大サイズ
]FIG]

[81] 新しい最大サイズは、プロトコルによる上限[[以下]]でなければ[['''なりません''']] [SRC[>>1]]。

[82] [[HTTP/2]] では、復号側から受信し、符号化側が [[acknowledge]] した最新の[[設定]] 
[CODE[[[SETTINGS_HEADER_TABLE_SIZE]]]] の値がこの上限です。 [SRC[>>1]]

[83] 上限を超える値は、復号エラーとしなければ[['''なりません''']]。 [SRC[>>1]]

[44] 最大サイズが減少した時は、[[動的表]]のサイズが最大サイズ[[以下]]となるまで、
末尾から順に削除 ([[eviction]]) します。 [SRC[>>1]]

[45] 新しい項目を追加する前には、[[動的表]]に新しい項目のサイズを足しても最大サイズ[[以下]]となるか、
[[表]]が空となるまで、末尾から順に削除 ([[eviction]]) します。 [SRC[>>1]]

[46] 新しい項目が最大サイズ[[以下]]なら、[[動的表]]に追加します。 [SRC[>>1]]

;; [47] 最大サイズを超えるなら、[[動的表]]が空になります。これはエラーではありません。
[SRC[>>1]]

[48] なお、新しい項目は、それによって[[動的表]]から削除される項目の名前を参照していることがありますから、
注意が必要です。 [SRC[>>1]]

* 文字列リテラル (オクテット列)

[56] [RUBYB[オクテット列]@en[string of octets]]は、[[ヘッダー欄]]の名前や値に使います。
[SRC[>>1]]

[57] 文字列リテラルは、オクテット列として直接、
または[[Huffman符号]]により符号化します。 [SRC[>>1]]

[58] 文字列リテラルは、次の欄で構成されます。 [SRC[>>1]]

[59] H は、[[Huffman符号化]]されているかどうかを示す1ビットのフラグです。
[CODE[0]] は、[[Huffman符号化]]されていない生のオクテット列を表します。
[CODE[1]] は、[[Huffman符号化]]されたオクテット列を表します。 [SRC[>>1]]

[60] [RUBYB[文字列長]@en[String Length]]は、文字列リテラルを符号化するために使ったオクテット数を7ビット[[接頭辞]]の[[整数]]として[[符号化]]したものです。 [SRC[>>1]]

[61] [RUBYB[文字列データ]@en[String Data]]は、
文字列リテラルの符号化されたデータです。生のオクテット列または [[Huffman符号化]]されたオクテット列です。 [SRC[>>1]]

[62] [[Huffman符号化]]の場合、[[Huffman符号]]によって[[符号化]]し、
各オクテットに対応する[[符号]]をビット単位で順に連結したものです。
[[オクテット]]境界でちょうど終わらない場合、次の[[オクテット]]境界まで[RUBYB[詰め]@en[padding]]を挿入します。
文字列リテラルの一部と誤解されないよう、 [[EOS]] (end-of-string)
記号に対応する[[符号]]の最上位ビット群を使います。 [SRC[>>1]]

[63] [[Huffman符号化]]の[[復号]]時には、末尾の不完全な[[符号]]は、
詰めとみなして捨てます。8ビット[[以上]]の詰めは、復号エラーとしなければ[['''なりません''']]。
[[EOS]] 記号に対応する[[符号]]の最上位ビット群でない詰めも、
復号エラーとしなければ[['''なりません''']]。
[[EOS]] 記号を含む文字列リテラルは、[[復号エラー]]としなければ[['''なりません''']]。 [SRC[>>1]]

[FIG(packet)[
:width:16

=1 H
=7 文字列長
=24... 文字列データ
]FIG]

* 整数

[50] [RUBYB[[[整数]]]@en[integer]]は、[[索引]]と文字列長に使います。 [SRC[>>1]]

[51] 整数は、[[オクテット]]中のどこからでもはじめられますが、
必ず[[オクテット]]の最後で終わります。 [SRC[>>1]]

[52] 整数は、開始[[オクテット]]のうちの開始以後の部分である[RUBYB[接頭辞]@en[prefix]]と、
その後の0個[[以上]]の[[オクテット]]の列で構成されます。
[[接頭辞]]のビット数 [VAR[N]] は、文脈によります。
[[接頭辞]]の後に続く[[オクテット]]は、 [[MSB]] が1のものが続いた後、
[[MSB]] が0のもので終わります。 [SRC[>>1]]

[FIG(railroad)[
= |
== [[接頭辞]] (0 を含む)
== =
=== [[接頭辞]] (すべて1)
=== *
==== [[MSB]]=1
=== [[MSB]]=0
]FIG]

[55] [[整数]]の[[符号化]]は、次のように行います [SRC[>>1]]。
[FIG(steps)[
= 値が 2[SUP[[VAR[N]]]]-1 [[未満]]なら、
== [VAR[N]] ビットで表現したものを、[[接頭辞]]として出力します。
= それ以外なら、
== [VAR[N]] ビット分の 1 の列を、[[接頭辞]]として出力します。
== 値から 2[SUP[[VAR[N]]]]-1 を引きます。
== 値が 128 [[以上]]である間、繰り返し実行します。
=== 値を128で割った[[余り]]を下位7ビットで符号化し、
[[MSB]] を1とした[[オクテット]]を出力します。
=== 値を128で割ります。
== 値を符号化した[[オクテット]]を出力します。
]FIG]

[53] [[整数]]の[[復号]]は、次のように行います [SRC[>>1]]。
[FIG(steps)[
= [VAR[結果]]を、[[接頭辞]] [VAR[N]] ビットを復号した値に設定します。
= [VAR[結果]]が 2[SUP[[VAR[N]]]]-1 なら、
== [VAR[M]] を、0に設定します。
== 次の処理を実行します。
=== [VAR[B]] を、次の[[オクテット]]に設定します。
=== [VAR[結果]]に、 [VAR[B]] の下位7ビットの値に 2[SUP[[VAR[M]]]] を掛けた値を足します。
=== [VAR[M]] に、7 を足します。
=== [VAR[B]] の [[MSB]] が 1 なら、繰り返します。そうでなければ、次に進みます。
= [VAR[結果]]を返します。
]FIG]

[54] 本方式の[[整数]]は無限に大きな値を表現できますし、
無駄に多くの[[オクテット]]を消費したり、[[桁溢れ]]させたりするかもしれません。
実装は (使われる文脈毎に適当な) 値やオクテット長の制限を超えたら、
復号エラーとしなければ[['''なりません''']]。 [SRC[>>1]]