SWFバイナリ編集のススメ番外編 (zlib 伸張) 中編

よやと申します。こんにちわ。

今回は zlib 解説の中編です。前編はこちら ↓

前回、zlib ヘッダのバイナリを解説しました。今回はその後ろに続く Deflateストリームのバイナリ構造についてです。
尚、固定ハフマンまでの説明で長くなり過ぎたので、動的ハフマン(カスタムハフマン)は次回の後編で改めて解説いたします。

前回の復習

  • zlib は「zlib ヘッダ + Deflate ストリーム + ADLER32」のデータ形式です。尚、通常、zlib ヘッダ無しでも Deflate ストリームだけで圧縮元のデータを復元出来ます。(DICTID が存在すると話が少し厄介ですが、通常見かける事はないでしょう)

zlibInflate-zlib

Deflate はデータを任意の長さのブロックで分けて収納出来ます。続きのブロックがあるかは BFINAL で表し、各ブロック毎に任意の圧縮タイプ(BTYPE)を付けられます。

  • ブロックの連結イメージ


zlibInflate-Deflate

  • 圧縮タイプには三種類存在します。データのサイズや性質に応じて使い分けます。(前回、大まかに解説しました)


zlibInflate-Deflate-BTYPE0zlibInflate-Deflate-BTYPE1zlibInflate-Deflate-BTYPE2

テストデータの作り方

PHP には gzcompress という関数がありまして、gz と頭に付いていますが (gzip でなく) zlib のデータを生成します。

  • 無圧縮(BTYPE:0)

  • 固定ハフマン(BTYPE:1)

  • 動的ハフマン(BTYPE:2)

小さなデータに対して動的ハフマンを適用する方法は http://d.hatena.ne.jp/n7shi/20110719 を参考に .NET の DeflateStream を使おうとしたのですが、環境を作るのが面倒なのでデータの方だけ拝借させて頂きます。(zlib ヘッダとして頭に 9c 78 の 2byte を追加)

BTYPE 別詳細解説

BTYPE:0 無圧縮

この方式は実際には圧縮しません。初めにデータ長があり、その後ろに何も変換しない生のデータが続きます。
但し、データ長フィールドは 2 bytes の為、65535 を超えられない事に注意が必要です。


zlibInflate-Deflate-BTYPE0

先程、生成したテストデータ(btype0.zlib)で確認しましょう。

先頭 2 bytes は zlib ヘッダなので無視するとして、その後ろに BTYPE とデータ長が続きます。

  • zlib のビットの読み出しは分かりにくいですが、下位ビットから読みだします。
  • 0x01 は2進数で 00000001、最後1ビットの 1(最後のブロック)とその手前2ビットの 00 (BTYPE)だけ意味があります。頭の 00000 は読み捨てます。

DeflateBTYPE0_70per

  • LittleEndian なので 0c 00 => 0x000c => データ長が 12 byte である事を示します。
  • データ長の次には足すと 0xffff になるような値(*2)が入ります。(verify チェックでしょうか)

12 bytes データが続く事が分かっているので、”This is TEST” を取り出して、復元成功です。
最後の 4 bytes は ADLER32 のチェックサムです。データが化けてないか確認するのに使います。

BTYPE:1 固定ハフマン

とある決まったハフマン表を使って伸長します。


zlibInflate-Deflate-BTYPE1

BTYPE=1(固定ハフマン)のハフマン表は RFC1951 の Page12 に載っています。

これをビット数の少ない順に並べて図にするとこうです。

固定ハフマン変換表_70per

  • 終端や繰り返しを表すメタデータに短いビット(7bits)を割り当て、
  • その次に短いビット(8bits)を ASCII の前方のコードや距離の長い繰り返しのメタデータに割り当て、
  • 最後にASCIIの後ろの方の文字を割り当てる。

US-ASCII のテキスト文字で短い間隔での繰り返しが多く出る、普通の英語の文章にそこそこ合った(でも、文字頻度での最適化まではしていない)ハフマン表と言えます。

さて、この表を元に先程作成した、テストデータ(btype1.zlib)を解釈してみます。

  • 0x0b は2進数で 00001011、最後1ビットの 1(最後のブロック)とその手前2ビットの 01 (BTYPE)で始まります。
  • btype:0 と違って、残りの 00001 にも意味があります。そこからデータの始まりです。

まずは BFINAL と BTYPE の 3bit を見て固定ハフマンのブロックが始まるのを確認します。

DeflateBTYPE1_LIT_1_70per

元データの復元 (リテラル)

まず 7 bits 読みだします。

DeflateBTYPE1_LIT_2_70per

7bits のエントリで定義された符号の範囲に収まらないので、更にもう 1 bit 読みだします。

DeflateBTYPE1_LIT_3_70per

これで、1文字目の “T” が取り出せた事になります

元データの復元 (繰り返し)

“This is TEST” の “is “の3文字が繰り返しなので、長さ3、距離3の繰り返しを表すメタデータをハミング符号で指定する事で、圧縮率を上げられます。

DeflateBTYPE1_LEN_1_70per

繰り返しメタデータに関する符号は RFC1951 の Page12 に定義されています。

  • ハフマン符号に応じて、繰り返しの長さが定義されます。
  • 繰り返しの長さが長い(11以上の)場合は、その長さに応じて追加の長さを入れるフィールド(Extra Bits)を用意します。
  • 続く5bits に繰り返し開始までの距離が入ります。
  • 繰り返しの距離が遠い(11以上の)場合は、その距離に応じて追加の距離を入れるフィールド(Extra Bits)を用意します。

バイナリ構成としては以下のようになります。

  • Huffman Code (Length)

DeflateBTYPE1_LEN_2_70per

  • Distance Code

DeflateBTYPE1_LEN_3_70per

では、実際のデータ(“is ” の繰り返し)を見てみましょう。

繰り返しのある場所まで調べるのが面倒なので、ツールに頼ります。

これは pure PHP で Zlib を解釈するツールですが、これの dump スクリプトを使うと、各ハフマン符号が Zlib バイナリ中の何処のオフセットに存在するのか分かります。

これを信じて (0オリジンの) 7 bytes 目の 3bits 目から分解します。

  • ハフマン符号が 0x257 なので繰り返しの長さが 3 だと分かります。

DeflateBTYPE1_LEN_4_70per

  • 続く 5 bits を見ると、距離が 3 だと分かります。

DeflateBTYPE1_LEN_5_70per

この例では、Extra Bits を使いませんでしたが、より長い長さ、遠い距離だと必要になり、上の方で説明したように Extra Bits に入っている値を足して補正します。

BTYPE1 のまとめ
  • ハフマン符号を解釈して以下の3つに分別します。

    • リテラル(0~255) => 元データそのもの
    • 終端記号(256) => Deflate ブロックの終端
    • 長さ(257~285) => 繰り返しパターンの長さ
  • ハフマン符号が長さを表す場合

    • 長さが 3~10(ハフマン符号は 257~264)の場合は、その値をそのまま長さとして使う
    • 長さが 11以上(ハフマン符号は 265~285)の場合は、更に後ろを数bits読みだして、それを足した値を長さにします
  • 距離フィールド(5bits)

    • 距離が 0~3 の場合は、その値をそのまま距離として使う
    • 距離が 4以上の場合は、更に後ろを数bits読みだして、それを足した値を距離にします
  • ビットをそのままの並びで値として解釈する時と、逆さにして解釈する時があります。規則は正直分かりません。ハフマン符号が逆順なのは妥当ですが、5 bits 固定の長さフィールドも逆順で、その拡張ビットは正順。整理すると以下のようになります。

    • ビット正順 => BTYPE の 2 bits、長さ拡張フィールド、距離拡張フィールド。
    • ビット逆順 => ハフマン符号、距離フィールド(5 bits)

次回予告

BTYPE:2 動的ハフマン

より高いデータの圧縮率を求めるならば、そのデータに応じた適切なハフマン表が必要です。
この動的ハフマン方式では、元データを解析して適切なハフマン表で圧縮を行い、そのハフマン表を先頭につけるデータ構造となります。

こちらは最終回に当たる Zlib 伸長解説の後編で解説いたします。

以上です。

*1: gzip ヘッダも込みで欲しい場合は gzencode 、zlib のヘッダ無しで deflate ストリームだけ欲しい場合は gzdeflate が対応しています

*2: いわゆる 1の補数です。一般に負の表現でよく使われる 2の補数ではないです。

Author: よや