HPACK の Integer Representation の仕組み

intro

この内容は、 HPACK draft-03 を元に書かれています。
http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-03

将来のドラフトでは変わる可能性があるためバージョンにはご注意下さい。

(以下の内容は、自分がアルゴリズムから読み解いたものなので、間違ってたら教えて下さい。)

HPACK

HPACK のフレーム表現の中に、以下のような表記が出てくる。

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

この Index(7+) は、ここに数値が 7 bit もしくは、それに続く数 byte を用いて、
表現されていることを示している。

この表現は、 7 bit で収まる数値は 7bit で表現し
収まらない大きな数値は、後続の byte を必要なだけ用いて表現することで
任意の大きさの数値を表現できる仕組みになっている。

この Index(N+) の部分の表現を Integer Representation という。

Encode アルゴリズム

ドラフトを見ると、 Encode 方法として以下のアルゴリズムが示されている。

If I < 2^N - 1, encode I on N bits
Else
    encode 2^N - 1 on N bits
    I = I - (2^N - 1)
    While I >= 128
         Encode (I % 128 + 128) on 8 bits
         I = I / 128
    encode (I) on 8 bits

この通りやればエンコードできるのだが、最初は意図がよくわからなかった。
また、デコードの方法は記されてないので、 Decode するためには逆算するのだが、
その導出過程で仕組みを解いてみたら面白かったので紹介する。

以下 I が表現したい値、 N が Prefix (+N の部分) とする。

仕組み

ここでは、簡素化のために N＝５で固定する。

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

I=10

まず、小さい数値 I＝１０で導出過程を見てみる。
10 を表現するには 5 bit あれば十分である。
なぜなら N<2^5-1(31) よりも小さいから。

xxx0 1010

つまり 2^N - 1 より小さい値については、普通に 2 進数にすれば良いことがわかる。
(If I < 2^N - 1, encode I on N bits の部分)

I=3,000,000

I を大きめにしてみる。
(ドラフトのサンプルでは 1337 があるが、ターン数が少ないので、より大きな数字を選んだ)

まず、 N bit は使えるので、そこで表せる最も大きい値をそこで表すことにする。
2^N-1 = 2^5-1 = 31
つまり、以下のようにすればとりあえず 31 は表せる。
(encode 2^N - 1 on N bits の部分)

xxx1 1111 (31)

そこで、元の I から表せた分だけ引いたものを算出すると。

3,000,000 - 31 = 2,999,969

この値は、後続の byte を用いて表す必要がある。
(I = I - (2^N - 1) の部分)

そこで、現在の値を 2 進数で表してみると。

0010 1101  1100 0110  1010 0001 (2,999,969)

全てが 8 bit には収まらないので、後続のバイト列で表現せざるをえない。
それをどう表現するか。

表現不足な例

下位から 8 bit ごとに区切っていけばいいと考えると。。

こうなる。
これで表現できた気もするが、問題がある。
それは、この後も別のバイト列が続いた場合に、
どこまでが I を表しているのかがわからないからだ。

終端を自己表現するために

I を表すのに何byte 使ったのかを別途持つ方法もあるが、
Integer Representation は、表現自身からどこまでが
I を表しているかわかるようにしている。

8bit ではなく、 7bit ごとに区切って、後続がある場合は
必ず先頭 bit を 1 にし、最後のバイトの場合は先頭 bit が
0 になるようにしているのである。

もう一度もとのバイト列

0010 1101  1100 0110  1010 0001 (2,999,969)
xxxx xxxx  xxxx xxxx  xooo oooo

下位 7bit を切り出して、8bit 目を 1 にして後続の 1byte とする。
現在の表現に加える。(o の部分)

xxx1 1111
1010 0001

I からはその分削る。
次は、以下になる。

0101 1011  1000 1101 (23,437)
xxxx xxxx  xooo oooo

xxx1 1111
1010 0001
1000 1101

同様に。

1011 0111 (183)
xooo oooo

で、最後は 1 になるが、これはそのまま 1 としてエンコードすれば良い。
結果は以下になる。

つまり、先頭ビットを 0 にしたまま表現できるサイズまで縮めば、
それを最後の byte とすることができる。
その値は最大で 127 である。

0111 1111 (127)

アルゴリズムで言うと

While I >= 128

この部分は、先頭ビットを 0 にしたまま表現できない値を意味している。
その間は、

Encode (I % 128 + 128) on 8 bits

128 は 2^7 であるので、 128 で割るのは、 7 bit 右シフトすることと等価である。
つまり、 128 で割ったあまりは、 7bit 右シフトしたら消えてしまう部分にあたるので、
(I % 128) は下位 7 bit をさす。
128 加えるのは、 1000 0000 を加えることなので 7bit の値に対して先頭 bit に 1 を加えることを意味する。

I = I / 128

これは、単純に今処理した 7bit を消すために 7bit 右シフトしていることと等化である。

これを繰り返し、 I < 127 (7bit で表現できる値) になったら

encode (I) on 8 bits

8 bit で表現するということは先頭がかならず 0 になるので、これを終端とみなせる。

デコード

結果をもう一度見てみよう。

この値を上から見た場合。

1, I=5 で、 5bit 読んだら全て 1 なので 5bit では表せず後続 byte を使っていることがわかる。

                        0001 1111

2, 次の byte を見ると、先頭が 1 なので、それを除いた 7 bit が最下位になり、まだ続くことがわかる
3, 最後の 0 で始まる byte が最後になり、そこまでをシフトしながら繋いで行けば良い。

これを図持すると以下のイメージに成る。

                        0010 0001
                0000 1101
        0011 0111
0000 0001
------------------------------------
        1011 0111000 1101010 0001 (2,999,969)

1 と 2-3 の結果を加える。

                  0001 1111        (31)
10 1101 1100 0110 1010 0001 (2,999,969)
---------------------------------------
10 1101 1100 0110 1100 0000 (3,000,000)

よって、デコードは上記を行うアルゴリズムを構築すれば良い。

Block Rockin’ Codes

back with another one of those block rockin' codes