DEFLATE と gzip の形式

DEFLATE は RFC 1951 で定義されたビットストリーム形式です。LZ77 の スライディングウィンドウとハフマン符号を組み合わせています。「zlib」と 「gzip」は DEFLATE を含むファイルを指すことが多いですが、それぞれ raw ビットストリームに対する異なるラッパーです。

ブロック境界と BTYPE #

DEFLATE ストリームは一連のブロックで構成されます。各ブロックは現在の ビット位置から BFINAL（1 ビット）と BTYPE（2 ビット）で始まります。

最後のブロックだけ BFINAL が 1 になります。圧縮ブロックは、その リテラル/長さストリームがブロック終端（EOB）であるシンボル 256 を出力 すると終了します。次のブロックヘッダーは次のビットから直ちに続くため、 圧縮ブロックはバイト境界までパディングされません。格納ブロックは例外 です。ヘッダーの後、デコーダーは現在のバイトに残っているビットを破棄し、 リトルエンディアンの LEN と NLEN（LEN の 1 の補数）を読み取り、 ちょうど LEN バイトをコピーします。LEN は 16 ビットなので、1 つの 格納ブロックに格納できるのは最大 65,535 バイトです。

LZ77 シンボルとハフマン符号 #

圧縮データのアルファベットには、リテラルバイト 0–255、EOB 256、および 長さシンボル 257–285 が含まれます。長さシンボルは基準長と追加ビット数を 選択します。続く距離シンボルは基準距離と追加ビット数を選択します。その 結果得られるペアは、生成済み出力から最大 32 KiB 後方、最大 258 バイトの 長さでバイトをコピーします。重複は有効です。

固定ブロックでは、RFC 1951 で規定された符号長を使用します。動的ブロック には HLIT（5 ビット）、HDIST（5 ビット）、HCLEN（4 ビット）が含まれ、 指定された順列で符号長アルファベットを伝送します。このアルファベットは、 ゼロの連続や繰り返される長さに対する繰り返し符号を含め、リテラル/長さ 符号と距離符号の符号長を記述します。正準的な再構成によって、これらの 長さから実際の符号が生成されます。

DEFLATE は各バイト内で最下位ビットから上位ビットへデータ要素を詰めます。 数値の追加ビットフィールドは最下位ビットから先に並びます。ハフマン符号は 正準値として割り当てられますが、形式で定められたビット反転規則に従って 出力されます。パーサーはすべてのフィールドをバイト境界にそろえた整数 として読み取るのではなく、ビットカーソルを保持する必要があります。

zlib と gzip のラッパー #

raw DEFLATE にはヘッダーもトレーラーもありません。zlib ラッパー （RFC 1950）は CMF と FLG で始まり、FCHECK によって 16 ビットの ヘッダーが 31 で割り切れるようになっています。FDICT が設定されている 場合は、4 バイトの Adler-32 辞書識別子が続きます。ストリームは、展開 されたデータのビッグエンディアン Adler-32 で終了します。

gzip ラッパー（RFC 1952）はメンバーのシーケンスです。各メンバーには、 マジックバイト 1f 8b、圧縮方式 8、フラグ、変更時刻、追加フラグ、および オペレーティングシステムの各フィールドがあります。フラグによって、追加 フィールド、元のファイル名、コメント、ヘッダー CRC を追加できます。 トレーラーには、展開されたメンバーのリトルエンディアン CRC-32 と、 サイズを 2³² で割った剰余である ISIZE が格納されます。メタデータは トレーラーの検証の代わりにはなりません。

プロトコルのドキュメントでは、表現形式を明示する必要があります。HTTP の Content-Encoding: gzip は gzip 形式を運びますが、method 8 を使用する ZIP エントリは通常 raw DEFLATE ストリームを運びます。ペイロードが 「compressed」と記述されているという理由だけで、zlib デコーダーを安全に 選択することはできません。

参考資料 #

• RFC 1951: DEFLATE
• RFC 1950: zlib Format
• RFC 1952: gzip Format