LZ4フレーム形式の説明

通知

Copyright (c) 2013-2020 Yann Collet

Permission is granted to copy and distribute this document for any purpose and without charge, including translations into other languages and incorporation into compilations, provided that the copyright notice and this notice are preserved, and that any substantive changes or deletions from the original are clearly marked. Distribution of this document is unlimited.

バージョン

1.6.4 (28/12/2023)

はじめに

この文書の目的は、CPUの種類、オペレーティングシステム、ファイルシステム、文字集合に依存しない、可逆圧縮データ形式を定義することです。LZ4アルゴリズムによるファイル圧縮、パイプを使った圧縮、ストリーミング圧縮に適しています。

入力データストリームが逐次渡され、その長さに上限がない場合でも、あらかじめ上限の決まった量の中間記憶領域だけでデータを生成・消費できます。このため、データ通信にも利用できます。この形式ではLZ4圧縮方式を使い、データ破損の検出には任意でxxHash-32チェックサム方式を使います。

この仕様で定義するデータ形式は、圧縮データへのランダムアクセスを実現しようとするものではありません。

この仕様は、データをLZ4形式に圧縮するソフトウェア、またはLZ4形式から展開するソフトウェアの実装者を対象としています。本文は、ビットなどの基本的なデータ表現を扱うプログラミングの基礎知識を前提とします。

以下で特に示す場合を除き、準拠する圧縮器は、ここに示す仕様に従ったデータを生成しなければなりません。ただし、すべてのオプションをサポートする必要はありません。

準拠する展開器は、ここに示す仕様に従う、動作可能なパラメーターの組を少なくとも一つ展開できなければなりません。チェックサムを無視することもできます。圧縮ストリーム内の特定のパラメーターをサポートしない場合は、曖昧でないエラーコードと、どのパラメーターが非対応なのかを説明するエラーメッセージを出さなければなりません。

LZ4フレーム形式の全体構造

マジックナンバー

4バイト、リトルエンディアン形式。値: 0x184D2204。

フレーム記述子

3～15バイトです。仕様の最も重要な部分であるため、専用の項で詳しく説明します。

Magic_Number と Frame_Descriptor を合わせて、 LZ4フレームヘッダー と呼ぶことがあります。大きさは7～19バイトです。

データブロック

専用の項で詳しく説明します。ここに圧縮データを格納します。

EndMark

最後のデータブロックの後に32ビット値0x00000000が続くと、ブロックの流れは終わります。

コンテンツチェックサム

Content_Checksum は、内容全体が正しく展開されたことを検証します。元の（展開済みの）データを入力とし、シードをゼロとして、xxHash-32アルゴリズムで計算した値です。フレーム記述子の対応するフラグが設定されている場合にだけ存在します。すべてのブロックが正しい順序で、欠損や誤りなく送られたことに加え、符号化・展開処理自体によって内容が変化しなかったことも検証します。利用を推奨します。

EndMark と Content_Checksum を合わせて、 LZ4フレームフッター と呼ぶことがあります。大きさは4～8バイトです。

フレームの連結

既存の圧縮ファイルをフレームに組み直さずに新たなデータを追加する場合など、複数のフレームを連結する方がよいことがあります。

その場合、各フレームはそれぞれ独自の記述子フラグを持ち、独立したものとして扱います。フレーム間の唯一の関係は、逐次並ぶ順序です。

単一のストリームやファイル内で、連結された複数フレームを展開できるかどうかは、この仕様の対象外です。例として、参照実装のlz4コマンドラインユーティリティは、連結されたすべてのフレームを順に展開します。

フレーム記述子

記述子は最小3バイト、オプションのパラメーターに応じて最大15バイトです。

FLGバイト

BDバイト

表では、ビット7が最上位ビット、ビット0が最下位ビットです。

バージョン番号

2ビットのフィールドで、01に設定しなければなりません。それ以外の値は、このバージョンの仕様では展開できません。別のバージョン番号では、フラグの配置が異なります。

ブロック独立フラグ

このフラグが「1」の場合、ブロックは独立しています。「0」の場合、各ブロックは先行するブロックに依存します（LZ4のウィンドウサイズである64 KBまで）。その場合は、すべてのブロックを順に展開する必要があります。

ブロックの依存関係は、特に小さなブロックで圧縮率を改善します。一方、ランダムアクセスや複数スレッドでの展開はできなくなります。

ブロックチェックサムフラグ

このフラグが設定されている場合、各データブロックの後に4バイトのチェックサムが続きます。生の（圧縮された）データブロックに対してxxHash-32アルゴリズムを使って計算します。目的は、保存・転送の誤りによるデータ破損を、展開する前に直ちに検出することです。ブロックチェックサムの利用は任意です。

コンテンツサイズフラグ

このフラグが設定されている場合、フレームに含まれるデータの非圧縮サイズが、フラグの後に8バイトの符号なしリトルエンディアン値として存在します。コンテンツサイズの利用は任意です。

コンテンツチェックサムフラグ

このフラグが設定されている場合、EndMarkの後に32ビットのコンテンツチェックサムを付加します。

辞書IDフラグ

このフラグが設定されている場合、記述子のフラグとContent Sizeの後に4バイトのDict-IDフィールドが存在します。

ブロック最大サイズ

この情報は、展開器のメモリ確保に役立ちます。ここでのサイズは、元の（非圧縮の）データサイズです。ブロック最大サイズは、次の表のいずれかの値です。

展開器は、システム固有の上限を超えるブロックサイズのメモリ確保を拒否してもかまいません。未使用の値は、仕様の将来の改訂で使われる可能性があります。現行バージョンの仕様に準拠する展開器が展開できるのは、この仕様で定義したブロックサイズだけです。

予約ビット

予約ビットの値は、0（ゼロ）でなければなりません。予約ビットは、将来の仕様で、通常は新たな任意機能を有効にするために使われる可能性があります。その場合、現行の仕様バージョンに従う展開器は、そのようなフレームを展開できません。

コンテンツサイズ

元の（非圧縮の）サイズです。この情報は任意で、対応するフラグが設定されている場合だけ存在します。符号なし8バイト、最大16エクサバイトの値を、リトルエンディアン形式で格納します。情報提供用の値で、通常は表示やメモリ確保に使います。展開器はこの値を読み飛ばしても、内容の正しさの検証に使ってもかまいません。

辞書ID

辞書は短い入力列の圧縮に役立ちます。辞書がある場合、圧縮器はその内容を「既知の接頭部」のように使い、入力をよりコンパクトに符号化できます。

フレーム記述子が独立ブロックを指定する場合、各ブロックを同じ辞書で初期化します。連結ブロックを指定する場合、辞書を使うのはフレームの先頭で一度だけです。

データを展開できるようにするには、圧縮器と展開器が厳密に同じ辞書を使わなければなりません。

Dict-IDフィールドは、圧縮フレームの正しい展開に必要な辞書を展開器が判定するために用意されています。対応するフラグが設定されている場合だけ存在します。符号なし32ビット値で、リトルエンディアン形式で格納します。単一のフレーム内には、Dict-IDフィールドを一つだけ定義できます。

Dict-IDフィールドは任意です。どの辞書を使うかという情報は、例えばアプリケーションの文脈から暗黙に分かる場合など、別経路で伝えることもできます。

ヘッダーチェックサム

オプションのフィールドを含め、記述子の全フィールドをまとめたものに対する一バイトのチェックサムです。値はxxh32()の二番目のバイト、すなわち(xxh32()>>8) & 0xFFです。シードはゼロ、入力はフレーム記述子全体（存在するオプションのフィールドも含む）です。チェックサムが合わない場合、記述子に誤りがあることを示します。

データブロック

ブロックサイズ

このフィールドは4バイトで、リトルエンディアン形式です。

最上位ビットが設定されている（1）場合、ブロックは非圧縮です。

最上位ビットが設定されていない（0）場合、LZ4ブロック形式仕様に従ってLZ4圧縮されています。

それ以外のすべてのビットは、データ部分のバイト数を示します。ブロックチェックサムが存在する場合でも、このサイズには含みません。

Block_Size は Block_Maximum_Size を決して超えてはなりません。圧縮できない入力では、サイズがこの上限を超えそうになる場合があります。その場合、そのデータブロックは非圧縮形式で渡さなければなりません。

値0x00000000はブロックとしては無効で、代わりに EndMark を意味します。これは、最上位ビットが設定された値0x80000000とは異なります。後者はサイズ0の非圧縮ブロック（空ブロック）であり、有効なのでフレームを終了しません。 Block_checksum が有効な場合は、空ブロックの後にも32ビットのブロックチェックサムを付けなければなりません。

データ

実際に展開するデータを置く部分です。直前のフィールドの指定に応じて、圧縮されている場合も、非圧縮の場合もあります。

圧縮されている場合は、LZ4ブロック形式仕様に従わなければなりません。

ブロックは必ずしも一杯である必要はありません。データの非圧縮サイズは、 Block_Maximum_Size 以下の任意のサイズでよく、最大ブロックサイズより少ないデータを含んでもかまいません。

ブロックチェックサム

対応するフラグが設定されている場合だけ存在します。4バイトのリトルエンディアンのチェックサム値です。生の（未展開の）データブロックに対して、シードをゼロとしてxxHash-32アルゴリズムを使って計算します。目的は、保存・転送の誤りによるデータ破損を、展開する前に検出することです。

Block_checksum と Content_checksum は併用できます。

スキップ可能なフレーム

スキップ可能なフレームは、連結フレームの流れにユーザー定義のデータを組み込めるようにします。設計は単純で、展開器がユーザー定義データを素早く読み飛ばし、展開を続けられるようにすることだけを目的としています。

識別を容易にするため、連結フレームの流れをスキップ可能なフレームで始めることは推奨しません。スキップ可能なフレームに収めたユーザーデータを先頭に置く必要がある場合は、まずゼロバイトのLZ4フレームを置き、その後にスキップ可能なフレームを置くことを推奨します。これにより、ファイル形式を識別する処理が容易になります。

マジックナンバー

4バイト、リトルエンディアン形式。値: 0x184D2A5X。これは0x184D2A50から0x184D2A5Fまでのいずれかの値を意味します。16個の値は、すべてスキップ可能なフレームの識別に使えます。

フレームサイズ

後続のユーザーデータのバイト数です（マジックナンバーとサイズフィールド自体は含みません）。4バイト、リトルエンディアン形式の符号なし32ビット値です。したがって、ユーザーデータは(2^32-1)バイトを超えることができません。

ユーザーデータ

ユーザーデータの内容は任意です。展開器は単に読み飛ばします。

旧フレーム

旧フレーム形式は、「LZ4Demo」の初期バージョンで定義されました。制約が強すぎるため、新しい圧縮器ではこの形式を使うべきではありません。

旧形式の主な特徴:

• ブロックサイズは8 MB固定です。
• 最後のブロックを除き、すべてのブロックを完全に満たさなければなりません。
• 圧縮によってかえって大きくなる場合でも、すべてのブロックは常に圧縮されます。
• 最後のブロックは、後ろに「EOF」（ファイル終端）マークが続くか、既知のフレームマジックナンバーが続くことで検出します。
• チェックサムはありません。
• リトルエンディアンです。

マジックナンバー

4バイト、リトルエンディアン形式。値: 0x184C2102。

ブロック圧縮サイズ

後続の圧縮データブロックのバイト数です。4バイト、リトルエンディアン形式です。

データ

実際の圧縮データを置く部分です。圧縮によってかえって大きくなる場合でも、データは常に圧縮されます。

EndMark

旧フレームの終端は、暗黙に示されるだけです。ファイルでもストリームでも、標準のEOF（ファイル終端）信号が後に続かなければなりません。

別の方法として、フレームの後に有効なフレームマジックナンバーが続く場合は、完了したものと扱います。この規則により、旧フレームの連結が可能になります。

それ以外の値はブロックサイズと解釈し、許容範囲に収まらない場合はエラーになります。

バージョンの変更履歴

1.6.4: 辞書について軽微な説明の明確化。

1.6.3: 軽微な変更: データブロックの説明を明確化。

1.6.2: EndMark の仕様を明確化。

1.6.1: 「LZ4フレームヘッダー」「LZ4フレームフッター」という用語を導入。

1.6.0: フレームヘッダーに辞書IDフィールドを復活。

1.5.1: 文書形式をMarkDownに変更。

1.5: 仕様から辞書IDを削除。

1.4.1: 「ストリーム」から「フレーム」に表現を変更。

1.4: スキップ可能なストリームを追加し、ストリームチェックサムを復活。

1.3: ヘッダーチェックサムを変更。

1.2: 「BlockSizeフィールドのサイズを動的にする」判断を先送りするため、「ブロックサイズ」の選択肢を削減。

1.1: オプションのフィールドを記述子の一部に変更。

1.0: 「ブロックサイズ」の仕様を変更し、圧縮・非圧縮フラグを追加。

0.9: 「ブロック最大サイズ」表の尺度を縮小。

0.8: 高圧縮フラグを削除。

0.7: ストリームチェックサムを削除。

0.6: ストリームサイズを8バイト、リトルエンディアンとすることに確定。

0.5: 著作権通知を追加。

0.4: Google Docと互換性のあるOpenDocument形式に変更。