メインコンテンツまでスキップ

4. 距離のエンコーディング (Encoding of Distances)

4. 距離のエンコーディング (Encoding of Distances)​

セクション 2 で説明したように、圧縮メタブロック (Compressed Meta-block) の 1 つのコンポーネントは、後方距離 (Backward Distances) のシーケンスです。このセクションでは、距離のエンコーディングの詳細を提供します。

メタブロックの圧縮データ部分の各距離は、ペア <distance code, extra bits> で表されます。距離コード (Distance Code) と追加ビット (Extra Bits) は連続してエンコードされ、距離コードは距離アルファベット上のプレフィックスコードを使用してエンコードされ、追加ビット値は固定幅整数値としてエンコードされます。追加ビットの数は 0..24 であり、距離コードに依存します。

距離コードと関連する追加ビットを後方距離に変換するには、過去の距離のシーケンスと 2 つの追加パラメータが必要です: "postfix bits" の数、NPOSTFIX (0..3) で示され、直接距離コード (Direct Distance Codes) の数、NDIRECT (0..120) で示されます。これらのパラメータは両方ともメタブロックヘッダーにエンコードされます。次の派生パラメータも使用します:

POSTFIX_MASK = (1 << NPOSTFIX) - 1

最初の 16 個の距離シンボルは、次のように過去の距離を参照する特別なシンボルです:

 0: last distance (最後の距離)
 1: second-to-last distance (最後から 2 番目の距離)
 2: third-to-last distance (最後から 3 番目の距離)
 3: fourth-to-last distance (最後から 4 番目の距離)
 4: last distance - 1
 5: last distance + 1
 6: last distance - 2
 7: last distance + 2
 8: last distance - 3
 9: last distance + 3
10: second-to-last distance - 1
11: second-to-last distance + 1
12: second-to-last distance - 2
13: second-to-last distance + 2
14: second-to-last distance - 3
15: second-to-last distance + 3

4 つの最後の距離のリングバッファ (Ring Buffer) は、ストリームの開始時（メタブロックの開始時ではなく）に値 16, 15, 11, 4 によって初期化されます（つまり、最後から 4 番目は 16 に設定され、最後から 3 番目は 15、最後から 2 番目は 11、最後の距離は 4 に設定されます）。メタブロック境界ではリセットされません。距離シンボル 0 が現れると、それが表す距離（つまり、距離シーケンス内の最後の距離）は最後の距離のリングバッファにプッシュされません。言い換えれば、「最後から 2 番目の距離」という表現は、0 距離シンボルで表されなかった最後から 2 番目の距離を意味します（「最後から 3 番目の距離」と「最後から 4 番目の距離」についても同様です）。同様に、静的辞書ワード (Static Dictionary Words) を表す距離（セクション 8 を参照）は、最後の距離のリングバッファにプッシュされません。

特別な距離シンボルがゼロまたは負の値に解決される場合、ストリームは無効として拒否されるべきです。

NDIRECT がゼロより大きい場合、次の NDIRECT 個の距離シンボル（16 から 15 + NDIRECT）は、1 から NDIRECT までの距離を表します。特別な距離シンボルも NDIRECT 個の直接距離シンボルも、追加ビットが続きません。

距離シンボル 16 + NDIRECT 以上のすべてに追加ビットがあり、距離シンボル "dcode" の追加ビット数は次の式で与えられます:

ndistbits = 1 + ((dcode - NDIRECT - 16) >> (NPOSTFIX + 1))

追加ビットの最大数は 24 です。したがって、距離シンボルアルファベットのサイズは (16 + NDIRECT + (48 << NPOSTFIX)) です。

距離シンボル "dcode" (>= 16 + NDIRECT) と追加ビット "dextra" が与えられた場合、後方距離は次の式で与えられます:

hcode = (dcode - NDIRECT - 16) >> NPOSTFIX
lcode = (dcode - NDIRECT - 16) & POSTFIX_MASK
offset = ((2 + (hcode & 1)) << ndistbits) - 4
distance = ((offset + dextra) << NPOSTFIX) + lcode + NDIRECT + 1

出典 (Source): RFC 7932, Section 4
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

に最終更新