3.1.1.3.2. Sequences_Section (シーケンスセクション)
圧縮ブロックはシーケンスの連続体です。シーケンスはリテラルコピーコマンドに続いてマッチコピーコマンドです。リテラルコピーコマンドは長さを指定します。これは Literals_Section からコピー (または抽出) するバイト数です。マッチコピーコマンドはオフセットと長さを指定します。
すべてのシーケンスがデコードされ、Literals_Section にまだリテラルが残っている場合、これらのバイトはブロックの最後に追加されます。
これはセクション 3.1.1.4 でより詳細に説明されています。
Sequences_Section は、コマンドをデコードするために必要なすべてのシンボルをまとめます。3 つのシンボルタイプがあります: リテラル長コード、オフセットコード、マッチ長コード。これらは単一の「ビットストリーム」でインターリーブエンコードされます。
Sequences_Section はヘッダーで始まり、各シンボルタイプのオプションの確率テーブルが続き、その後にビットストリームが続きます。
Sequences_Section_Header
[Literals_Length_Table]
[Offset_Table]
[Match_Length_Table]
bitStream
Sequences_Section をデコードするには、そのサイズが知られている必要があります。このサイズは Literals_Section のサイズから導出されます:
Sequences_Section_Size = Block_Size - Literals_Section_Header
- Literals_Section_Content
3.1.1.3.2.1. Sequences_Section_Header (シーケンスセクションヘッダー)
このヘッダーは2つの要素で構成されます:
- Number_of_Sequences (シーケンス数)
- Symbol_Compression_Modes (シンボル圧縮モード)
Number_of_Sequences
Number_of_Sequences は 1 から 3 バイトを使用する可変サイズフィールドです。最初のバイトが "byte0" の場合:
-
if (byte0 == 0): シーケンスなし。シーケンス部分はここで停止します。解凍コンテンツは Literals_Section コンテンツとして完全に定義されます。Repeat_Mode で使用される FSE テーブルは更新されません。
-
if (byte0 < 128): Number_of_Sequences = byte0。1 バイトを使用します。
-
if (byte0 < 255): Number_of_Sequences =
((byte0 - 128) << 8) + byte1。2 バイトを使用します。 -
if (byte0 == 255): Number_of_Sequences =
byte1 + (byte2 << 8) + 0x7F00。3 バイトを使用します。
Symbol_Compression_Modes
Symbol_Compression_Modes は、各シンボルタイプの圧縮モードを定義する単一バイトです。
| ビット番号 (Bit Number) | フィールド名 (Field Name) |
|---|---|
| 7-6 | Literal_Lengths_Mode |
| 5-4 | Offsets_Mode |
| 3-2 | Match_Lengths_Mode |
| 1-0 | Reserved (予約済み) |
表 14: Symbol_Compression_Modes
最後のフィールド Reserved はすべてゼロである必要があります。
Literals_Lengths_Mode、Offsets_Mode、Match_Lengths_Mode は、それぞれリテラル長コード、オフセットコード、マッチ長コードの Compression_Mode を定義します。これらは同じ列挙に従います:
| Value (値) | Compression_Mode (圧縮モード) |
|---|---|
| 0 | Predefined_Mode (事前定義モード) |
| 1 | RLE_Mode (RLEモード) |
| 2 | FSE_Compressed_Mode (FSE圧縮モード) |
| 3 | Repeat_Mode (リピートモード) |
表 15: Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode
Predefined_Mode (事前定義モード) : セクション 3.1.1.3.2.2 で定義されているように、事前定義された FSE (セクション 4.1 を参照) 分布テーブルを使用します。分布テーブルは存在しません。
RLE_Mode (RLEモード) : テーブル記述は、シンボルの値を含む 1 バイトで構成されます。このシンボルはすべてのシーケンスに使用されます。
FSE_Compressed_Mode (FSE圧縮モード) : 標準 FSE 圧縮。分布テーブルが存在します。この分布テーブルの形式はセクション 4.1.1 で説明されています。リテラル長コードとマッチ長コードテーブルの最大許容精度は 9 で、オフセットコードテーブルの最大精度は 8 であることに注意してください。シンボルが 1 つだけ存在する場合、このモードは使用してはならず、代わりに RLE_Mode を使用する必要があります (他のモードも機能しますが)。
Repeat_Mode (リピートモード) : Number_Of_Sequences > 0 の前の Compressed_Block で使用されたテーブルが再利用されます。これが最初のブロックの場合は、辞書からのテーブルが使用されます。これには RLE_Mode が含まれることに注意してください。したがって、Repeat_Mode が RLE_Mode に続く場合、同じシンボルが繰り返されます。また、Predefined_Mode も含まれます。この場合、Repeat_Mode は Predefined_Mode と同じ結果になります。分布テーブルは存在しません。フレーム (またはセクション 5 による辞書) に繰り返すべき前のシーケンステーブルがない状態でこのモードが使用された場合、これは破損とみなされるべきです。
3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets (長さとオフセットのシーケンスコード)
各シンボルは独自のコンテキスト内のコードで、Baseline (ベースライン) と追加する Number_of_Bits (ビット数) を指定します。コードは FSE 圧縮され、元の追加ビットと同じビットストリームでインターリーブされます。
Literals Length Codes (リテラル長コード)
リテラル長コードは 0 から 35 (含む) の値です。これらは 0 から 131071 バイトの長さを定義します。リテラル長は、デコードされた Baseline にビットストリームから Number_of_Bits ビットを読み取った結果 (リトルエンディアン値として) を加えたものに等しくなります。
| Literals_Length_Code | Baseline | Number_of_Bits |
|---|---|---|
| 0-15 | length | 0 |
| 16 | 16 | 1 |
| 17 | 18 | 1 |
| 18 | 20 | 1 |
| 19 | 22 | 1 |
| 20 | 24 | 2 |
| 21 | 28 | 2 |
| 22 | 32 | 3 |
| 23 | 40 | 3 |
| 24 | 48 | 4 |
| 25 | 64 | 6 |
| 26 | 128 | 7 |
| 27 | 256 | 8 |
| 28 | 512 | 9 |
| 29 | 1024 | 10 |
| 30 | 2048 | 11 |
| 31 | 4096 | 12 |
| 32 | 8192 | 13 |
| 33 | 16384 | 14 |
| 34 | 32768 | 15 |
| 35 | 65536 | 16 |
表 16: リテラル長コード
Match Length Codes (マッチ長コード)
マッチ長コードは 0 から 52 (含む) の値です。これらは 3 から 131074 バイトの長さを定義します。マッチ長は、デコードされた Baseline にビットストリームから Number_of_Bits ビットを読み取った結果 (リトルエンディアン値として) を加えたものに等しくなります。
| Match_Length_Code | Baseline | Number_of_Bits |
|---|---|---|
| 0-31 | Match_Length_Code + 3 | 0 |
| 32 | 35 | 1 |
| 33 | 37 | 1 |
| 34 | 39 | 1 |
| 35 | 41 | 1 |
| 36 | 43 | 2 |
| 37 | 47 | 2 |
| 38 | 51 | 3 |
| 39 | 59 | 3 |
| 40 | 67 | 4 |
| 41 | 83 | 4 |
| 42 | 99 | 5 |
| 43 | 131 | 7 |
| 44 | 259 | 8 |
| 45 | 515 | 9 |
| 46 | 1027 | 10 |
| 47 | 2051 | 11 |
| 48 | 4099 | 12 |
| 49 | 8195 | 13 |
| 50 | 16387 | 14 |
| 51 | 32771 | 15 |
| 52 | 65539 | 16 |
表 17: マッチ長コード
Offset Codes (オフセットコード)
オフセットコードは 0 から N の値です。
デコーダーは、サポートする最大 N を自由に制限できます。少なくとも 22 の値をサポートすることが推奨されます。執筆時点で、リファレンスデコーダーがサポートする最大 N 値は 31 です。
オフセットコードは、リトルエンディアンで読み取られる追加ビットの数でもあり、次の式で Offset_Value に変換できます:
Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) Offset = Offset_Value - 3;
これは、最大 Offset_Value が (2^(N+1)) - 1 であり、最大 (2^(N+1)) - 4 の後方参照距離をサポートすることを意味しますが、最大後方参照距離によって制限されます (セクション 3.1.1.1.2 を参照)。
1 から 3 の Offset_Values は特別です: これらは「リピートコード」を定義します。これはセクション 3.1.1.5 でより詳細に説明されています。
3.1.1.3.2.2. Default Distributions (デフォルト分布)
シンボルタイプに対して Predefined_Mode が選択された場合、その FSE デコーディングテーブルは、ここで定義されている事前定義分布テーブルから生成されます。この分布をデコーディングテーブルに変換する方法の詳細については、セクション 4.1 を参照してください。
3.1.1.3.2.2.1. Literals Length Codes (リテラル長コード)
デコーディングテーブルは 6 ビットの精度ログ (64 状態) を使用します。
short literalsLength_defaultDistribution[36] =
{ 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
-1,-1,-1,-1
};
3.1.1.3.2.2.2. Match Length Codes (マッチ長コード)
デコーディングテーブルは 6 ビットの精度ログ (64 状態) を使用します。
short matchLengths_defaultDistribution[53] =
{ 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
-1,-1,-1,-1,-1
};
3.1.1.3.2.2.3. Offset Codes (オフセットコード)
デコーディングテーブルは 5 ビットの精度ログ (32 状態) を使用し、最大 N 値 28 をサポートし、最大 536,870,908 のオフセット値を許可します。
圧縮ブロック内のシーケンスがこれより大きいオフセットを必要とする場合、デフォルト分布では表現できません。
short offsetCodes_defaultDistribution[29] =
{ 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1
};