7shi さんのスライドを見ていたら、inflate(uncompress の方)だけ
なら簡単に作れそうだったので、pure PHP で実装してみました。
お仕事で SWF をいじる事が多いのですが、SWF は Zlib を多用しているので、
壊れたバイナリを調査する時に普通なら迷宮入りしそうな問題も Zlib を理解してると解決できたりしないかなと。
あと、SWF 編集で何か圧縮/伸長処理をサボれる場所があるかもしれませんし。
▼Zlib - Deflate:
Zlib (rfc1950)は単なる圧縮データのコンテナ((例えば、Zlib 以外のコンテナに GZIP (rfc1952)があります。))で、
圧縮自体は Deflate(rfc1951)という方式を使います。
Deflate はハフマン符号と LZ77 で圧縮を行います。
▼ハフマン符号と LZ77:
- ハフマン符号は、よく出てくる値を短いビットで、あまり出てこない値を長いビットで表現する事で、全体のビット数(つまりデータ量)を減らす方式です。
- LZ77 は、前の同じパターンがあれば、それと同じという事を示す符号だけ記録する事で、データ量を節約する方式です。
▼分かりにくかった所:
- Zlib は Big Endian です。Deflate は Little Endian です。ややこしいです。
- Deflate は bit 処理の際に 下位bitから順に切り出します。ややこしいです。
- しかも通常、上位bitが上位桁になりますが、ハフマン符号だけ下位bitが上位桁になります。ホントややこしいです。(実際処理すると合理的だと実感できますが)
- 固定ハフマン(BTYPE:1) ではLZ77の距離フィールドとして5bitを切り出しますが、これもハフマン符号同様下位bitを上位桁としたら、うまく処理できました。動的ハフマンでは、距離フィールドもハフマン符号なので、これはこれで合理的。(だけど仕様書からは読み取れないｗ)
- ハフマン符号で復元した時に出てくる値を 0〜255 でなく、0〜285 とする事で、256 を終端。257以上を LZ77 用として使えます。この 0〜255 を超えてマッピングされた値をアルファベットと呼ぶようです。(初め、わけ分からなかった)
- 固定ハフマンだと、アルファベットが287 まで範囲あるのに 285 までしか定義がなかったり、距離符号が5bitあるのに 30 までしか定義がなかったりと死に値があるので、理解になかなか自信が持てませんでした。(verify 的に)
- inflate が伸長です。(だってインフレだし)。deflate が圧縮です。(デフレね)。初め、語感から(de が戻す感じするので)逆だと勘違いしてました。
▼Deflate BTYPE:
Deflate の圧縮フォーマットは３種類あります。
- BTYPE:0 無圧縮 (圧縮するとむしろ膨らむようなデータや、Zlib の体裁を保つだけで圧縮しなくて良いデータはコレ)
- BTYPE:1 固定ハフマン (決まったハフマン符号表を用います。データが小さかったり、出てくる値に偏りがなく繰り返しが多く出てくるデータに適している)
- BTYPE:2 動的ハフマン (ハフマン符号表を自分で定義出来ます。データがある程度多い場合はコレが適している。画像とか)
BTYPE:2 はカスタムハフマンとも呼ばれます。
動的ハフマンは、一般的にはハフマン符号で変換しながら、その途中でテーブルの中身を切り替える適用ハフマンの意味で使われる事が多くて、紛らわしいからです。
▼BTYPE:2:
スライドには動的ハフマンの説明が無くて、
自分で解読しようとしましたが、やはり分からなくて、
困っていたら、7shi さんがその声を拾ってくれました。
僕でも分かった位なので、冒頭で紹介したスライドとこの記事を併せて読めば多分、猿でも Zlib inflate を実装出来ると思います！
▼記事を読んでつまづいた所:
- ハフマン符号長から符号テーブルを生成するのは、例題が示されていたので、すぐ法則が分かりましたが、3.2.2 に記述があると一言あると嬉しいかもしれません。
