こんにちは。アプリケーション基盤チームのよやと申します。
バイナリの目利きや書き換えを主な業務フィールドとし、1% でも多くのユーザの皆様にサービスをお届けする為、より良質のバイナリを探し求める毎日です。
SWF の番外編として zlib 伸張について２回のブログに分けて解説します。(圧縮処理は対象外です)
前編の今回は概要についてお話し、具体的な実装は後編で扱う予定です。
はじめに
SWF フォーマットは zlib 圧縮を多用します。例えば、GIF/PNG 画像は独自画像形式(DefineBitsLossless の BitmapPixelData)に変換後 zlib 圧縮して格納します。
Flash6 以降では SWF を(先頭8byteを除いて)まるごと zlib 圧縮する事も出来ます。
SWF バイナリの中の zlib 圧縮されたデータが怪しい場合に、zlib 形式としてどの bit が誤っているかまで分かれば、より深く問題を追求できます。
SWF を扱うのに zlib の知識は必須とまでは言いませんが、持っていると嬉しい武器だと言えるでしょう。
尚、zlib フォーマットについて殆どの事柄は @7shi 氏から教わりました。この場を借りて御礼申し上げます。有難うございます。本当に助かりました！
当記事は @7shi 氏の資料と併せて読むと、より理解が深まります。ご参考までに。
zlib について
zlib はDeflate アルゴリズムを利用した圧縮フォーマットの一種で、Deflate ストリームの入れ物として機能します。
Deflate の他の入れ物では gzip や ZIP が有名です。gzip は UNIX の gzip コマンドで生成されるファイルの形式です。ZIP は Windows OS で広く利用されています。
zlib のヘッダは簡素ですが、gzip はファイル名や時刻等の情報が入りますし、ZIP は複数のファイルも扱える為、更に構造が複雑です。
-
これらのファイル形式は以下の文書で仕様が公開されています。
Deflate アルゴリズム
ハフマン符号(Huffman coding)と LZ77 を組み合わせてデータ圧縮を行います。
ハフマン符号 (Huffman coding)
データ中に頻繁に出現する値に短い bit 列を、滅多に出ない値に長い bit 列を割り当て、使われない値があれば bit 列を割り当てない事で、データ全体の長さを短くする手法です。
例えば、Hello World という文字列がある場合、文字毎の出現回数は各々、
- l が 3 文字
- o が 2 文字
- HWder と空白が1文字ずつ
ですので、以下のように bit 列を割り当てる事で、 11bytes のデータを 4bytes に圧縮できます。
- l : 00
- o: 01
- 空白,H: 100～101
- W,d,e,r: 1100～1111
尚、zlib はハフマン符号化で生成した bit を byte 内の下位 bit から詰めていく為、上記と違う byte になります。(次回のブログで解説します)
LZ77
データ中に同じパターンのデータ列を見つけた場合に、データそのものを記録せずに、同じパターンがある事を示すメタデータを置く事で、データ全体の長さを短くする手法です。
メタデータはどの位前(distance)に、どの位の長さ(length)のパターン(同じデータ列)があるといった情報を持ちます。
以下の図は Huffman と LZ77 を組み合わせた例です。Huffman で符号化する値(0～255 の1byte) を拡張し、distance も同列に扱います。
ADLER32
チェックサムアルゴリズムの一種です。信頼性に少し目をつむる代わりに比較的高速に計算出来ます。
PHP では以下のように実装できます。
define ('MOD_ADLER', 65521);
function adler32($data) {
$a = 1;
$b = 0;
$data_length = strlen($data);
for ($i = 0 ; $i < $data_length ; $i++) {
$a = ($a + ord($data[$i])) % MOD_ADLER;
$b = ($b + $a) % MOD_ADLER;
}
return ($b << 16) | $a;
}
尚、より高速なルーチンが Wikipedia で紹介されています。ご参考まで。(こちらは C 言語です)
zlib バイナリ形式
zlib のヘッダにはデータをどのように圧縮したかの情報が入ります。通常は 2bytes ですが、FDICT(1 bit)が 1 の場合には 6 bytes になります。
尚、(通常使われない DICTID を除いて) ヘッダの情報を見なくても伸長が可能です。
DICTID は(Deflate 仕様で定義された固定ハフマンの表が気に入らない場合)アプリケーション側でハフマン表を決め打ちにする時に、その送信側と受信側とで同じ表なのかのチェックに使われるようです。
Deflate ストリーム形式
Deflate ストリームはブロックのリスト構造です。
ブロックの頭に BFINAL (1 bit) のフィールドがあり、そのブロックの後ろに別のブロックが続くのか(BFINAL:0)、今のブロックで最後なのか(BFINAL:1)を示します。
BFINAL に続いて BTYPE(2 bits) のフィールドがあり、そのブロックの圧縮形式を示します。無圧縮(BTYPE:0)、固定ハフマン(BTYPE:1)、動的ハフマン(BTYPE:2)の三種類があり、データ列の性質によって使い分けます。
Deflate 形式
BTYPE:0 無圧縮
短いデータ列ではハフマン符号化は逆効果になりがちです。
その場合はあえてデータを圧縮せず、そのまま格納する形式を利用します。
LEN には格納するデータの長さを、NLEN には LEN の 1 の補数(全ビットの 0, 1 が逆)の値が入ります。
BTYPE:1 固定ハフマン
ハフマン符号表を圧縮データに付加してデータ長が膨らむのを避けるのに、決め打ちのハフマン符号表を使う方式が用意されています。
この符号表は、コードの出現頻度の偏りが少なく(US-ASCII 範囲内だと更に良し)、リピートが多い場合に圧縮がよく効きますが、そうでないデータ列では逆にデータ量が膨らむ性質を持ちます。
固定ハフマンで使われる決め打ちの符号表は RFC1951 の 3.2.6 章に載っています。
BTYPE:2 動的ハフマン
データ圧縮に適したハフマン符号表を作成し、圧縮データの先頭につける方式です。
そこそこのサイズのある画像データ等に適しています。多くの場合はこの形式が使われます。
実データに対するハフマン符号表は冗長になりがちな為か、そのハフマン符号表を更にハフマン符号化する形式を取ります。
さいごに
前編では zlib の概要を説明しました。
後編は、具体的な bit の並びと伸張の実装について解説する予定です。
それでは、失礼いたします。
参考資料
古い投稿