LZ4 ブロック形式の説明

最終改訂日: 2022-07-31。著者: Yann Collet

この仕様は、任意のプログラミング言語を使って LZ4 圧縮データブロックを生成したり読み取ったりしたい開発者を対象としています。

LZ4 は、固定のバイト指向符号化形式を持つ LZ77 型の圧縮器です。エントロピー符号化のバックエンドも、フレーム化レイヤーもありません。後者はシステムの他の部分で処理することを想定しています（LZ4 フレーム形式を参照）。この設計は、単純さと速度を重視するものです。

この文書はブロック形式だけを説明し、圧縮器や展開器の実際の動作方法は説明しません。そのような話題については、後の「実装上の注意」節を参照してください。

圧縮ブロック形式

LZ4 圧縮ブロックは、シーケンスで構成されます。シーケンスは、リテラル（圧縮されていないバイト）の並びと、その後に続くマッチコピー操作からなります。

各シーケンスは token で始まります。token は、二つの4ビットフィールドに分かれた1バイトの値です。したがって、各フィールドの値は0から15の範囲になります。

最初のフィールドはトークンの上位4ビットを使い、後に続くリテラルの長さを示します。

フィールドの値が15より小さい場合、その値はシーケンス中のリテラルの総数を表します。0も含まれ、その場合はリテラルがありません。

15は特別な値で、長さ全体を示すために追加のバイトが必要になります。各追加バイトは0から255の値を表し、それまでの値に加算して全体の長さを求めます。バイトの値が255の場合は、さらに別のバイトを読み取って加算する必要があり、これを繰り返します。token の後に、値が 255 のバイトがいくつ続いてもかまいません。ブロック形式は「サイズ上限」を定義していません。ただし、実際の実装には実用上の上限がある場合があります（後の「実装上の注意」の詳しい説明を参照）。

注: 圧縮できない入力ブロックが0.4%大きくなる理由は、この形式にあります。

例1: リテラル長48は、次のように表します。

15: 4ビットの上位フィールドの値
33: （=48-15）48に達するための残りの長さ

例2: リテラル長280は、次のように表します。

15: 4ビットの上位フィールドの値
255: 280-15 >= 255 なので、後続バイトは最大値になる
10: （=280 - 15 - 255）280に達するための残りの長さ

例3: リテラル長15は、次のように表します。

15: 4ビットの上位フィールドの値
0: （=15-15）このゼロは必ず出力しなければならない

token と、必要な場合に置かれる長さバイトの後には、リテラル本体が続きます。そのバイト数は、直前に復号したリテラル長と正確に一致します。補足: リテラルがない場合もあります。

リテラルの後には、マッチコピー操作が続きます。

これは offset 値で始まります。リトルエンディアン形式の2バイト値です（1バイト目が「下位」バイト、2バイト目が「上位」バイトです）。

offset は、過去のデータからコピーするマッチの位置を表します。たとえば、1は「現在位置 - 1バイト」を意味します。offset の最大値は65535で、65536以上は符号化できません。0は無効な offset 値であることに注意してください。値が0の offset がある場合、そのブロックは無効（破損）です。

次に matchlength を取り出せます。これには、token の後半のフィールドである下位4ビットを使います。この値も0から15の範囲ですが、ここでの0はコピー操作が最小であることを意味します。minmatch と呼ばれるマッチの最小長は4です。したがって、値が0なら4バイトを意味します。

リテラル長と同様に、15より小さい値には4（minmatch）を加えて長さとするので、長さは4から18の範囲になります。15は特別な値で、19バイト以上を意味します。この場合は、0から255の値を持つ追加バイトを一つずつ読み取る必要があります。それぞれを合計に加算し、最終的なマッチ長を求めます。値が255なら、さらに別のバイトを読み取って加算する必要があります。追加の 255 バイトの個数に上限はなく、したがって表現可能なマッチ長にも上限はありません。ただし、実際の実装は実用上の理由で上限を設けることが多いでしょう（後の「実装上の注意」を参照）。

注: この形式で達成可能な最大圧縮比は約250です。

matchlength の復号が終わると、現在のシーケンスは終了します。次のバイトは別のシーケンスの開始、つまり新しい token になります。

ブロック終端の条件

LZ4 ブロックを終端するために必要な制約があります。

最後のシーケンスはリテラルだけを含みます。ブロックはリテラルの直後で終わります（offset フィールドはありません）。
入力の最後の5バイトは常にリテラルです。したがって、最後のシーケンスは少なくとも5バイトを含みます。
- 特別な場合: 入力が5バイトより小さい場合は、シーケンスは一つだけで、入力全体をリテラルとして含みます。空の入力も、ゼロ値のバイトを使って表現できます。このバイトは、リテラルもマッチもない最終トークンと解釈されます。
最後のマッチは、ブロック末尾から少なくとも12バイト手前で始まらなければなりません。最後のマッチは 最後から二番目 のシーケンスに属します。その後に、リテラルだけを含む最後のシーケンスが続きます。
- その結果、12バイト未満のブロックは圧縮できません。さらに、独立した ブロックでは13バイト未満の場合に圧縮できません。少なくとも一つのリテラルで始まり、そのリテラルを後からマッチがコピーできるようにする必要があるためです。

これらの終端条件に従わないブロックは、仕様に適合するデコーダーが不正なブロックとして拒否してかまいません。

これらの規則は、速度重視の設計でこの条件に依存している、幅広い旧来のデコーダーとの互換性を確保するために設けられています。

実装上の注意

LZ4 ブロック形式は圧縮形式だけを定義し、デコーダーやエンコーダーの作り方は定めていません。その設計は、実装者の自由な発想に委ねられています。

ただし、経験から、ほとんどの実装で考慮する必要がある典型的な事項がいくつかあります。この節では、そのための指針を示します。

メタデータ

LZ4 圧縮ブロックを正しく展開するには、追加のメタデータが必要です。通常、デコーダーには圧縮ブロックのサイズと、展開後サイズの上限が必要になります。展開後サイズが既知で、入力サイズの上限が与えられる形など、他の方法もあります。

ブロック形式は、この情報をどう伝えるかを定めておらず、別経路で伝える情報と見なしています。多くの場合、この情報は周囲の環境に存在するためです。たとえば、データベースは索引のために圧縮ブロックのサイズを保存する必要があり、展開後のブロックが一定のしきい値を超えないことも分かっています。

自己完結した形式が必要で、どのプラットフォームでも正しく展開するために必要なメタデータを運びたい場合は、代わりに LZ4 フレーム形式の使用を検討してください。

大きな長さ値

ブロック形式は長さフィールドの最大値を定義しませんが、実際のほとんどの実装には何らかの上限があります。値を固定ビット幅のレジスターに格納することを想定しているためです。

長さフィールドに64ビットのレジスターを使う場合、実用上の上限はないと考えられます。上限に達するには、単一の連続したブロックが数ペタバイト必要となり、現在の基準では現実的でないためです。

長さフィールドに32ビットのレジスターを使う場合は、オーバーフローする可能性がありますが、16 MBを超えるサイズの圧縮ブロックが必要です。したがって、16 MBを超える圧縮ブロックを扱わない実装は、このオーバーフローに対して安全です。ただし、そのようなブロックを扱う場合は、大きな長さ値がレジスターをオーバーフローしないことを確認することを推奨します。

長さフィールドに16ビットのレジスターを使う場合、300バイト未満の圧縮データでも、このレジスターをオーバーフローさせることが確実に可能です。

仕様に適合するデコーダーは、長さのオーバーフローが起こり得る場合にはそれを検出し、発生した場合は単にエラーとして終了できるようにするべきです。入力ブロック自体が無効とは限らず、ローカルのデコーダー実装では展開できないだけの場合もあります。

より広い LZ4 エコシステムとの互換性を保つために、最大4 MBの長さを読み取って表現でき、最大4 MBのサイズのブロックを受け付けられるようにすることを推奨します。この上限は32ビットの長さレジスターと両立し、32ビットのレジスターのオーバーフローを防ぎます。

安全な展開

外部のソースから圧縮データを受け取るデコーダーでは、破損した入力に耐え、バッファオーバーフローを狙う操作に対して安全であることを確認することを推奨します。読み取りと書き込みの操作が、提供されたバッファの範囲内に収まることを必ず確認してください。

特に、コピーするよう指示されたバイト数が、入力バッファと出力バッファのどちらからもはみ出さないことを確認してください。また、オフセット値を読み取る際に、コピー元となる位置がバッファの先頭より前に達しないことも確認してください。この状況は、展開されたデータの最初の64 KBで起こり得ます。

安全性をさらに高めるため、ファザーを使ってデコーダーをテストし、起こりにくい条件の並びにも耐えられることを確認してください。サニタイザーを組み合わせ、オーバーフロー（asan）や初期化の問題（msan）を検出します。

無効なオフセット0の場合にも注意してください。この値を無条件に展開してはなりません。素朴な実装では、宛先バッファの内容をそのまま残してしまうことがあります。そのバッファが未初期化で、機密データをまだ含んでいる場合、情報漏えいにつながる可能性があります。参考として、この場合、参照実装の LZ4 デコーダーはマッチ領域を、値が 0 のバイトでクリアします。ただし、他の解決方法も考えられます。

最後に、matchlength が offset より大きい「重なりのあるマッチ」の場合にも注意してください。この場合、match_pos + matchlength > current_pos なので、後でコピーする一部のバイトはまだ存在せず、マッチコピー操作の初期段階で生成されます。この状況は特に注意して扱わなければなりません。よくある例は、オフセットが1の場合で、直前のバイトが matchlength 回繰り返されることを意味します。

圧縮手法

LZ4 圧縮器の中核は、過去64 KBにわたる重複データを検出することです。この形式は、圧縮器が入力データブロック内でマッチを検索して選ぶ方法について、前提も制限も設けていません。たとえば、「full optimal parsing」と呼ばれる手法を使い、高い CPU・メモリコストをかければ、圧縮の上限に到達できます。ただし、時間と性能のトレードオフがそれぞれ異なる、他のさまざまな手法も考えられます。指定された形式に従っている限り、結果は仕様に適合するどのデコーダーとも互換性があり、展開できます。