シーケンスセクション

圧縮ブロックは、シーケンスの連続です。 シーケンスは、リテラルのコピー命令と、それに続くマッチのコピー命令からなります。 リテラルのコピー命令は長さを指定します。これはリテラルセクションからコピー（または取り出し）するバイト数です。 マッチのコピー命令は、オフセットと長さを指定します。

すべてのシーケンスを復号した後、リテラルセクションにリテラルが残っていれば、そのバイト列をブロックの末尾に追加します。

詳細はシーケンスの実行で説明します。

Sequences_Sectionには、命令の復号に必要なすべてのシンボルをまとめます。 シンボルには、リテラル長、オフセット、マッチ長の3種類があります。 これらは、単一のビットストリーム内で交互に組み合わせて符号化します。

Sequences_Sectionは、ヘッダー、各シンボル種別の省略可能な確率表、ビットストリームの順に並びます。

Sequences_Sectionの復号には、そのサイズを知る必要があります。 サイズはLiterals_Sectionのサイズから導きます: Sequences_Section_Size = Block_Size - Literals_Section_Size。

Sequences_Section_Header

次の2項目からなります:

• Number_of_Sequences
• シンボルの圧縮モード

Number_of_Sequences

1～3バイトを使う可変長フィールドです。最初のバイトをbyte0と呼びます。

• if (byte0 < 128) : Number_of_Sequences = byte0。1バイトを使います。
• if (byte0 < 255) : Number_of_Sequences = ((byte0 - 0x80) << 8) + byte1。2バイトを使います。 2バイト形式は1バイト形式と完全に重複する点に注意してください。
• if (byte0 == 255): Number_of_Sequences = byte1 + (byte2<<8) + 0x7F00。3バイトを使います。

if (Number_of_Sequences == 0) : シーケンスはありません。 シーケンスセクションは直ちに終了し、Repeat_Modeで使うFSE表は更新しません。 ブロックの伸長後の内容は、リテラルセクションの内容だけで定義します。

シンボルの圧縮モード

各シンボル種別の圧縮モードを定義する1バイトです。

最後のフィールドReservedは、すべてゼロでなければなりません。

Literals_Lengths_Mode、Offsets_Mode、Match_Lengths_Modeはそれぞれ、リテラル長、オフセット、マッチ長のシンボルのCompression_Modeを定義します。

同じ列挙値に従います:

• Predefined_Mode : 既定の分布で定義する事前定義FSE分布表を使います。分布表は格納しません。
• RLE_Mode : 表の記述は、シンボルの値を含む1バイトからなります。このシンボルをすべてのシーケンスに使います。
• FSE_Compressed_Mode : 標準のFSE圧縮です。分布表を格納します。 分布表の形式はFSE表の記述で説明します。 許されるaccuracy logの最大値は、リテラル長表とマッチ長表では9、オフセット表では8です。 シンボルが1つしか存在しない場合、FSE_Compressed_Modeを使ってはなりません。 代わりにRLE_Modeを使うことが望まれます（ただし、ほかのどのモードでも動作します）。
• Repeat_Mode : Number_of_Sequences > 0である直近のCompressed_Blockで使った表を再利用します。 最初のブロックであれば、辞書内の表を使います。 これにはRLE_modeも含まれるため、RLE_Modeの後にRepeat_Modeが続くと、同じシンボルを繰り返します。 Predefined_Modeも含まれ、その場合、Repeat_Modeの結果はPredefined_Modeと同じです。 分布表は格納しません。 フレーム内に再利用できる先行シーケンス表も辞書もない状態で使う場合は、破損として扱うことが望まれます。

リテラル長、マッチ長、オフセットのコード

各シンボルは、それぞれの文脈で、Baselineと追加するNumber_of_Bitsを指定するコードです。 コードはFSEで圧縮し、同じビットストリーム内で、未圧縮の追加ビットと交互に格納します。

リテラル長コード

リテラル長コードは、0から35まで（両端を含む）の値です。 0から131071バイトまでの長さを定義します。 リテラル長は、復号したBaselineに、ビットストリームからNumber_of_Bitsビットをリトルエンディアン値として読み取った結果を加えたものです。

マッチ長コード

マッチ長コードは、0から52まで（両端を含む）の値です。 3から131074バイトまでの長さを定義します。 マッチ長は、復号したBaselineに、ビットストリームからNumber_of_Bitsビットをリトルエンディアン値として読み取った結果を加えたものです。

オフセットコード

オフセットコードは、0からNまでの値です。

デコーダーは、対応するNの最大値を自由に制限できます。 少なくとも22までは対応することを推奨します。 参考として、原文の執筆時点で、参照デコーダーは最大31のNに対応しています。

オフセットコードは、リトルエンディアンで読む追加ビット数でもあります。 次の式を使って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までの後方参照距離に対応しますが、 最大後方参照距離による制限を受けます。

1から3のOffset_Valueは特殊で、「繰り返しコード」を定義します。 詳細は繰り返しオフセットで説明します。

シーケンスの復号

FSEビットストリームは、書き込んだ方向と逆に読みます。 zstdの圧縮器はビットを順方向にブロックへ書き込み、伸長器はビットストリームを逆方向に読む必要があります。

そのため、ビットストリームの読み始めを見つけるには、ブロックの最後のバイトのオフセットを知る必要があります。 これは、ブロックヘッダーの後からBlock_Sizeバイトを数えることで分かります。

圧縮器は、情報を含む最後のビットを書いた後に1ビットを1つ書き、0～7個の0ビットのパディングでバイトを埋めます。 このため、圧縮ビットストリームの最後のバイトは0にはなりません。

伸長時には、パディングを含む最後のバイトを最初に読みます。 伸長器は、先頭の0～7個の0ビットと、最初に現れる1ビットを飛ばす必要があります。 その後に、ビットストリームの有効部分が始まります。

FSEの復号には、シンボル間で引き継ぐ「状態」が必要です。 詳しくはFSEの節を参照してください。

シーケンスの復号では、リテラル長、オフセット、マッチ長の各シンボルを、別々の状態で追跡します。 FSEの基本操作もいくつか使います。 これらの操作の詳細はFSEの節を参照してください。

初期状態

ビットストリームは、FSEの初期状態値から始まります。 各値は、正規化分布から事前に復号したそれぞれのaccuracyに応じた必要ビット数を使います。

最初はLiterals_Length_State、次がOffset_State、最後がMatch_Length_Stateです。

すべての値を逆方向に読むことを、常に意識してください。 ビットストリームの「先頭」は、メモリ上の最も高い位置にあり、パディング用の最後の1ビットの直前です。

初期状態を復号した後は、1つのシーケンスを復号する処理をNumber_Of_Sequences回行います。 シーケンスは、最初から最後へ順番に復号します。 圧縮器はビットストリームを順方向に書くため、シーケンスを最後のものから最初のものへ符号化しなければなりません。

1シーケンスの復号

各シンボル種別について、FSE状態から適切なコードを決定できます。 そのコードが、各種別のBaselineと読み取るNumber_of_Bitsを定義します。 これらの値の決め方はコードの説明を参照してください。

復号は、Offsetの復号に必要なNumber_of_Bitsを読み取ることから始めます。 次にMatch_Length、最後にLiterals_Lengthについて同じ処理を行います。 得たシーケンスをシーケンスの実行に使います。

ブロックの最後のシーケンスでなければ、次に状態を更新します。 復号表で事前に計算した規則を使い、Literals_Length_State、Match_Length_State、Offset_Stateの順に更新します。 ビットストリームから状態を更新する詳細はFSEの節を参照してください。

この操作をNumber_of_Sequences回繰り返します。 終了時には、ビットストリームを完全に消費していなければなりません。そうでなければ、ビットストリームは破損していると見なします。

既定の分布

シンボル種別にPredefined_Modeを選択した場合、そのFSE復号表は、ここで定義する事前定義の分布表から生成します。 分布を復号表へ変換する詳細はFSEの節を参照してください。

リテラル長

復号表は、6ビットのaccuracy log（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 };

マッチ長

復号表は、6ビットのaccuracy log（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 };

オフセットコード

復号表は、5ビットのaccuracy log（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 };

シーケンスの実行

リテラルとシーケンスを復号したら、それらを組み合わせて、ブロックの復号内容を生成します。

各シーケンスは、シーケンスセクションで説明した方法で復号した、 （literals_length、offset_value、match_length）の組からなります。 実行時には、まず、復号したリテラルからliterals_lengthバイトを出力へコピーします。

次に、復号済みのデータからmatch_lengthバイトをコピーします。 コピー元のオフセットはoffset_valueで決まり、offset_value > 3ならoffset_value - 3です。 offset_valueが1～3なら、オフセットは特殊な繰り返しオフセット値です。 この場合の決め方は、繰り返しオフセットの節を参照してください。

オフセットは現在位置からの距離です。たとえば、オフセット6、マッチ長3は、6バイト前から3バイトをコピーすることを意味します。 復号済みデータへのすべてのオフセットは、Frame_Header_Descriptorで定義するWindow_Sizeより小さくなければなりません。

繰り返しオフセット

シーケンスの実行で示したとおり、最初の3つの値は繰り返しオフセットを定義します。 これらをRepeated_Offset1、Repeated_Offset2、Repeated_Offset3と呼びます。 使った時点が新しい順に並び、Repeated_Offset1は「最も最近使ったもの」を意味します。

offset_value == 1なら、使うオフセットはRepeated_Offset1です。ほかも同様です。

ただし、現在のシーケンスのliterals_length = 0の場合は例外です。 この場合、繰り返しオフセットを1つずらし、offset_valueが1ならRepeated_Offset2、2ならRepeated_Offset3、3ならRepeated_Offset1 - 1を意味します。

最後の場合に、Repeated_Offset1 - 1の評価結果が0になれば、データは破損していると見なします。

最初のブロックの初期オフセット履歴は、Repeated_Offset1=1、Repeated_Offset2=4、Repeated_Offset3=8です。 ただし、辞書を使う場合は、辞書からこれらの値を取得します。

以降の各ブロックは、直近のCompressed_Blockの終了時の値を、初期オフセット履歴に使います。 Compressed_Blockでないブロックは飛ばし、オフセット履歴には影響しません。

オフセットの更新規則

Compressed_Blockのシーケンスを実行する間は、Repeated_Offsetsの値を更新し、常に最近使った3つのオフセットを表すようにします。 そのため、各シーケンスの実行後に、次のように更新します:

シーケンスのoffset_valueがRepeated_Offsetsのいずれも参照しない場合、つまり値が3を超えるか、値が3でシーケンスのliterals_lengthがゼロの場合は、 Repeated_Offsetsを1つ後ろへずらし、Repeated_Offset1に、今使ったオフセットの値を設定します。

それ以外、つまりシーケンスのoffset_valueがRepeated_Offsetsのいずれかを参照する場合（値が1または2、または値が3でシーケンスのliterals_lengthがゼロでない場合）は、 使ったRepeated_Offsetの値がRepeated_Offset1になるように並べ替えます。 先頭のRepeated_Offsetからoffset_valueが選んだRepeated_Offsetまでの既存の値を、後ろへ押し出します。 これは、これらのオフセット値を1段階循環させる操作で、再び、使った時点が新しい順になります。

次の表は、シーケンスを順に適用したときのRepeated_Offsetsの値を示します: