ZLIBフォーマット - しんのすけWiki

ZLIB

データ圧縮フォーマット. ZLIB 3.3がRFC1950として公開. 最新バージョンが何かは知らない.
WikipediaによるとUNIX系OSでcompressが使えなくなったことへの対応として, gzipで使用されるフォーマットとして採用された. 本来zlibという名前にあるとおり, ライブラリの名前である.
RFCの日本語訳を発見. こちら

Javaライブラリ

• JDK1.1以降には組み込みのライブラリが存在する. (java.util.zip)
• 上記は機能が制限されているとしてフル機能を実装している人もいる. (JZlib 1.0.7: こちら)

アルゴリズム/実装面から見た特徴

• 実際の圧縮アルゴリズムとしてはDeflate圧縮を使っている (他の圧縮方法にも容易に対応できると書いてある. 意味するところはZLIBは単なる圧縮フォーマットに何らかのメタデータを加えた, より上位のフォーマットで, その中で圧縮に用いるアルゴリズムを指定できるということだろう)
  • LZ77とシャノン符号を用いている
  • 入力長は無制限
  • ワーキングメモリは事前に決めた固定長で動作する
• チェックサムとしてAdler-32も使用する
• 圧縮データへのランダムアクセスを提供しない

その他の特徴

• 特許に抵触しない (これは結構大事)

仕様

記法など

• バイト内のビットは下から順にビット0,1,…,7と数える
• 複数バイトの数値を表現するときは上位バイトが先頭 (アドレスの低いほう, 配列の前のほう) に来る. 例えば2バイト (16ビット) の数520は [0x02, 0x08] の順で格納される.
• バイトやバイト列には大文字のシンボルが割り当てられている. ビットまたはビット列にもシンボルが割り当てられる. バイト内のビットまたはビット列を表現するにはドット記法を用いる. 例: FLG.FDICT

データフォーマット

• 1バイト: CMF (Compression Method and flags)
  • ビット0～3: CM (Compression method)
    • 圧縮アルゴリズムを表す
    • CM=8: windowサイズが32K以下のdeflateアルゴリズム (gzipやPNGで使用)
    • CM=15: 予約
  • ビット4～7: CINFO (Compression info)
    • CMの値に依存
    • CM=8の場合, LZ77のwindowサイズ (バイト単位) の対数をとって8を引いたもの (サイズが32Kの場合CINFO=7. つまり128bytesから2倍になるごとに1増える). この仕様では7より大きいCINFOは認められない
    • CM=8以外の場合, この仕様ではCINFOの値は定義されない
• 1バイト: FLG (FLaGs)
  • ビット0～4: FCHECK (Check bits for CMF and FLG)
    • チェックサム: CMF*256+FLGが31の倍数になるようにこれをセットする
  • ビット5: FDICT (Preset dictionary)
    • 1ならDEFLATEのプリセット辞書が存在する (辞書とは圧縮器に与えられる初期入力バイト列. 出力は生成しない). DICTID参照のこと
  • ビット6～7: FLEVEL (Compression level)
    • 圧縮レベルを表す
    • CM=8の場合, 0=最も速いアルゴリズム, 1=速いアルゴリズム, 2=デフォルトのアルゴリズム, 3=圧縮率最大で最も遅いアルゴリズム
• 4バイト: DICTID (FLG.FDICTが1なら)
  • 圧縮器に与えられる辞書のAdler-32チェックサムの値がここに入る
• xバイト: 圧縮されたデータ
• 4バイト: ADLER32
  • 辞書データを除く, 元データのAdler-32チェックサム. Alder-32の計算方法は以下の通り. 変数s1が全てのバイトの和を保持, 変数s2はすべてのs1値の和を保持する (つまりs2は, 1バイト読むごとに更新されるs1の値を足していく?). どちらの和も65521を法として計算する. 初期値はそれぞれ1, 0とする. Alder-32チェックサムはs2*65536+s1で計算される. バイトオーダーを考慮するとこれはs2, s1の順でデータを配置すればよい. アルゴリズムのコーディング例はRFCに載っている.
• この後ろは無視される (そもそもどこからチェックサムかわかるのか?)

実装

ビルトインライブラリがあるが, あえて実装してみた. アーカイブフォーマットではないのでテストがしにくいが, Deflaterで作ったデータを読んでみれば良いだろうか.

実験結果

• DeflaterOutputStreamクラスで作成したデータを読んでみた. FLEVELは2 (デフォルト) になる.
• 次にDeflaterクラスを用いてオプションを設定してみる.

---