9. 圧縮データ形式 (Compressed Data Format)
9. 圧縮データ形式 (Compressed Data Format)
このセクションでは、前のセクションで説明した個々のデータ項目の形式の観点から、圧縮データセットの形式について説明します。
9.1. ストリームヘッダーの形式 (Format of the Stream Header)
ストリームヘッダー (Stream Header) には、次の 1 つのフィールドのみがあります:
1..7 bits: WBITS、10..24 の範囲の値で、次の可変長コードでエンコードされます
(圧縮データに表示される際、ビットは右から左に解析されます):
Value Bit Pattern
----- -----------
10 0100001
11 0110001
12 1000001
13 1010001
14 1100001
15 1110001
16 0
17 0000001
18 0011
19 0101
20 0111
21 1001
22 1011
23 1101
24 1111
ビットパターン 0010001 は無効であり、使用してはなりません。
スライディングウィンドウ (Sliding Window) のサイズは、任意の非辞書参照後方距離 (Non-Dictionary Reference Backward Distance) の最大値であり、次の式で与えられます:
window size = (1 << WBITS) - 16
9.2. メタブロックヘッダーの形式 (Format of the Meta-Block Header)
準拠した圧縮データセットには、少なくとも 1 つのメタブロック (Meta-Block) があります。各メタブロックには、メタブロックの非圧縮長に関する情報を含むヘッダーと、メタブロックが最後であることを示すビットが含まれています。メタブロックヘッダーの形式は次のとおりです:
1 bit: ISLAST、これが最後のメタブロックの場合は 1 に設定
1 bit: ISLASTEMPTY、1 に設定されている場合、メタブロックは空です。
このフィールドは ISLAST ビットが設定されている場合にのみ存在します。
1 の場合、メタブロックと brotli ストリームはそのビットで終了し、
圧縮ストリームの最後のバイトの残りのビットはゼロで埋められます
(埋めビットがゼロでない場合、ストリームは無効として拒否されるべきです)
2 bits: MNIBBLES、非圧縮長を表すニブル数で、次の固定長コードで
エンコードされます:
Value Bit Pattern
----- -----------
0 11
4 00
5 01
6 10
MNIBBLES が 0 の場合、メタブロックは空、つまり非圧縮データを
生成しません。この場合、メタブロックの残りの部分は次の形式を
持ちます:
1 bit: 予約済み、ゼロでなければなりません
2 bits: MSKIPBYTES、メタデータ長を表すバイト数
MSKIPBYTES * 8 bits: MSKIPLEN - 1、ここで MSKIPLEN は
メタデータバイト数です。このフィールドは MSKIPBYTES が
正の場合にのみ存在します。そうでない場合、MSKIPLEN は 0 です
(MSKIPBYTES が 1 より大きく、最後のバイトがすべてゼロの
場合、ストリームは無効として拒否されるべきです)
0..7 bits: 次のバイト境界までの埋めビット、すべてゼロで
なければなりません
MSKIPLEN バイトのメタデータ、非圧縮データまたはスライディング
ウィンドウの一部ではありません
MNIBBLES * 4 bits: MLEN - 1、ここで MLEN はメタブロックの非圧縮データの
長さ（バイト単位）です (MNIBBLES が 4 より大きく、最後のニブルが
すべてゼロの場合、ストリームは無効として拒否されるべきです)
1 bit: ISUNCOMPRESSED、1 に設定されている場合、次のバイト境界までの
圧縮データの任意のビットは無視され、メタブロックの残りの部分には
MLEN バイトのリテラルデータが含まれます。このフィールドは ISLAST
ビットが設定されていない場合にのみ存在します (無視されたビットが
すべてゼロでない場合、ストリームは無効として拒否されるべきです)
1..11 bits: NBLTYPESL、リテラルブロックタイプ (Literal Block Types) の数で、
次の可変長コードでエンコードされます (圧縮データに表示される際、
ビットは右から左に解析されるため、0110111 は値 12 を持ちます):
Value Bit Pattern
----- -----------
1 0
2 0001
3..4 x0011
5..8 xx0101
9..16 xxx0111
17..32 xxxx1001
33..64 xxxxx1011
65..128 xxxxxx1101
129..256 xxxxxxx1111
リテラルブロックタイプのブロックタイプコードアルファベット上の
プレフィックスコード、NBLTYPESL >= 2 の場合にのみ表示
リテラルブロックカウントのブロックカウントコードアルファベット上の
プレフィックスコード、NBLTYPESL >= 2 の場合にのみ表示
最初のリテラルブロックカウントのブロックカウントコード + 追加ビット、
NBLTYPESL >= 2 の場合にのみ表示
1..11 bits: NBLTYPESI、挿入コピーブロックタイプ (Insert-and-Copy Block Types)
の数、上記と同じ可変長コードでエンコード
挿入コピーブロックタイプのブロックタイプコードアルファベット上の
プレフィックスコード、NBLTYPESI >= 2 の場合にのみ表示
挿入コピーブロックカウントのブロックカウントコードアルファベット上の
プレフィックスコード、NBLTYPESI >= 2 の場合にのみ表示
最初の挿入コピーブロックカウントのブロックカウントコード + 追加ビット、
NBLTYPESI >= 2 の場合にのみ表示
1..11 bits: NBLTYPESD、距離ブロックタイプ (Distance Block Types) の数、
上記と同じ可変長コードでエンコード
距離ブロックタイプのブロックタイプコードアルファベット上の
プレフィックスコード、NBLTYPESD >= 2 の場合にのみ表示
距離ブロックカウントのブロックカウントコードアルファベット上の
プレフィックスコード、NBLTYPESD >= 2 の場合にのみ表示
最初の距離ブロックカウントのブロックカウントコード + 追加ビット、
NBLTYPESD >= 2 の場合にのみ表示
2 bits: NPOSTFIX、距離符号化で使用されるパラメータ
4 bits: NDIRECT の 4 最上位ビット、パラメータ NDIRECT の実際の値を取得するには、
この 4 ビット数を NPOSTFIX ビット分左シフトします
NBLTYPESL * 2 bits: 各リテラルブロックタイプのコンテキストモード
1..11 bits: NTREESL、リテラルプレフィックスツリーの数、NBLTYPESL と同じ
可変長コードでエンコード
セクション 7.3 で説明されているようにエンコードされたリテラル
コンテキストマップ、NTREESL >= 2 の場合にのみ表示。そうでない場合、
コンテキストマップはゼロ値のみを持ちます
1..11 bits: NTREESD、距離プレフィックスツリーの数、NBLTYPESD と同じ
可変長コードでエンコード
セクション 7.3 で説明されているようにエンコードされた距離
コンテキストマップ、NTREESD >= 2 の場合にのみ表示。そうでない場合、
コンテキストマップはゼロ値のみを持ちます
NTREESL 個のリテラル用プレフィックスコード
NBLTYPESI 個の挿入コピー長用プレフィックスコード
NTREESD 個の距離用プレフィックスコード
9.3. メタブロックデータの形式 (Format of the Meta-Block Data)
メタブロックの圧縮データ部分は、一連のコマンド (Commands) で構成されます。各コマンドには次の形式があります:
次の挿入コピーブロックタイプのブロックタイプコード、NBLTYPESI >= 2 で
前の挿入コピーブロックカウントがゼロの場合にのみ表示
次の挿入コピーブロックカウントのブロックカウントコード + 追加ビット、
NBLTYPESI >= 2 で前の挿入コピーブロックカウントがゼロの場合にのみ表示
セクション 5 でエンコードされた挿入コピー長、現在の挿入コピーブロック
タイプインデックスの挿入コピー長プレフィックスコードを使用
挿入長の数のリテラル、次の形式:
次のリテラルブロックタイプのブロックタイプコード、NBLTYPESL >= 2 で
前のリテラルブロックカウントがゼロの場合にのみ表示
次のリテラルブロックカウントのブロックカウントコード + 追加ビット、
NBLTYPESL >= 2 で前のリテラルブロックカウントがゼロの場合にのみ表示
非圧縮データの次のバイト、非圧縮データの前の 2 バイト、現在の
リテラルブロックタイプ、およびセクション 7.3 で説明されている
コンテキストマップによって決定されるインデックスを持つリテラル
プレフィックスコードでエンコード
次の距離ブロックタイプのブロックタイプコード、NBLTYPESD >= 2 で前の
距離ブロックカウントがゼロの場合にのみ表示
次の距離ブロックカウントのブロックカウントコード + 追加ビット、
NBLTYPESD >= 2 で前の距離ブロックカウントがゼロの場合にのみ表示
セクション 4 でエンコードされた距離コード、コピー長、現在の距離ブロック
タイプ、およびセクション 7.3 で説明されている距離コンテキストマップ
によって決定されるインデックスを持つ距離プレフィックスコードを使用。
挿入コピー長コードによって示されるように、距離コードが暗黙の 0 でない
場合にのみ表示
メタブロック内のコマンド数は、すべてのコマンドにわたって生成された非圧縮バイトの合計（つまり、挿入されたリテラルの数と過去のデータからコピーされたバイト数または静的辞書から生成されたバイト数）が、メタブロックヘッダーにエンコードされた非圧縮長 MLEN を与えるようなものです。
最後のコマンドの挿入部分の後に生成された非圧縮バイトの総数が MLEN に等しい場合、最後のコマンドのコピー長は無視され、非圧縮出力を生成しません。この場合、最後のコマンドのコピー長は任意の値を持つことができます。それ以外の場合、挿入するリテラルの数、コピー長、または結果の辞書単語長が MLEN を超える場合、ストリームは無効として拒否されるべきです。
最後の非空メタブロックの最後のコマンドがバイト境界で終了しない場合、最後のバイトの未使用ビットはゼロでなければなりません。
出典 (Source): RFC 7932, Section 9
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt