080 余談になります（２）
●080 余談になります（２）
ZIP ファイルを特定するためのスクリプトを走らせて部屋に戻ってきた。
ご飯を食べて、夜になるも、なかなか寝付けない。
それで、適当に［ビット列］を作って、手動でデコードをしてみることにする。ちょっとだけなら良いだろう。
適当なデータを zlib で圧縮して［ビット列］にすればよいはず。zlib の出力にはヘッダ 2 バイトとフッター 4 バイトが付いているので取り除く。［ビット列］に変換する際には各バイトの最下位ビットを先にする。
s = "ABABABABAB"
x = zlib.compress(s)[2:-4]
r = cnv_b(x)
［ビット列］から切り出したビットは、ハフマン符号にはそのまま、それ以外はビットの順を反転させる必要があることに注意しよう。
［ビット列］の先頭 3 ビットはデータブロックのヘッダーで、後続ブロックの有無などの情報である。4 ビット目以降がデコードの対象だ。末尾に 0 を追加しているのは番兵的な保険で、デコードが少し気楽になる。固定ハフマン符号の符号語のビット数は最大 9、動的ハフマン符号は最大 15 である。
print "BFIN",r[0],"BTYP",rev(r[1:3])
r = r[3:] + "000000000" + "000000"
あとは［ビット列］には、［ＬＩＴ｜ＥＯＢ｜ＬＥＮ、ＥＸ１、ＤＩＳ、ＥＸ２］という構造があり、ＬＩＴとＥＯＢとＬＥＮはハフマン符号Ａでデコードし、ＤＩＳはハフマン符号Ｂでデコード、ＥＸ１とＥＸ２は生の二進数だ。この構造は固定ハフマン符号と動的ハフマン符号とで共通だ。
＊＊＊
データブロックの［ビット列］を［バイト列］に変換する処理を復習しよう。
［ビット列］の先頭から所要のビット（固定ハフマン符号では 7〜9 ビット）を切り出してハフマン符号Ａにより［記号Ａ］（0〜285）に変換する（ここで 286 や 287 が出現したらエラーだ）。なお、固定ハフマン符号の場合は RFC1951 で定義されたハフマン符号を使う。動的ハフマン符号の場合はデータブロックにあるデータでハフマン符号を作る。
そして［記号Ａ］により、次の 1）、2）、3）のどれかを行う。
1）［記号Ａ］が 0〜255 の場合は、［リテラル］として出力する。
2）［記号Ａ］が 256 の場合は、［終端］として出力して、処理終了する。
3）［記号Ａ］が 257〜285 の場合は、次の 4）〜7）を行う。
4）［記号Ａ］に応じて決まるビット数を［ビット列］から切り出して［補助１］とし、［記号Ａ］と［補助１］を変換して、［長さ］とする。
5）［ビット列］から所要のビット（固定ハフマン符号では 5 ビット）を切り出してハフマン符号Ｂにより［記号Ｂ］（0〜29）に変換する（30 か 31 の場合はエラーだ）。
6）［記号Ｂ］に応じて決まるビット数を［ビット列］から切り出して［補助２］とし、［記号Ｂ］と［補助２］を変換して、［距離］とする。
7）［長さと距離］を出力する。
以上を処理終了するまで繰り返す。これにより［リテラル｜終端｜長さと距離］の列が出力されるので、ＬＺ７７で［バイト列］に変換する。
＊＊＊
具体的に、固定ハフマン符号の場合で説明しよう。
デコードしたデータは変数 dec に格納する。
dec = []
［ビット列］（変数 r）の先頭 9 ビットを変換して数値（変数 c）にし、その値により［記号Ａ］（変数 s）を定める。ここで、range(0x0,0x60) は 0h 〜 5Fh までという意味です。そしてこれがハフマン符号Ａです。
c = cnv_n(r[:9])
if c in range( 0x0, 0x60): s = (c- 0x0)/4 + 256; r = r[7:]
elif c in range( 0x60, 0x180): s = (c- 0x60)/2 + 0; r = r[8:]
elif c in range(0x180, 0x190): s = (c-0x180)/2 + 280; r = r[8:]
elif c in range(0x190, 0x200): s = (c-0x190)/1 + 144; r = r[9:]
RFC1951 ではハミング符号Ａは次のように定義されています。「：」の左側が［記号Ａ］で、右側がそれに対応する符号語です（...正確には、符号語のビット数を定義していて、符号語自体は参考表記ですけれど、これについては後述します）。
000〜143 ： 00110000_ 〜 10111111_
144〜255 ： 110001000 〜 111111111
256〜279 ： 0000000__ 〜 0010111__
280〜287 ： 11000000_ 〜 11000111_
符号語から記号を求める場合には「 _ 」の部分を 0 または 1 に置き換えて、数値の範囲を判定すればよいのです。あるいは 2 の 9 乗（= 512）個のテーブルを用意して、変数 c から変数 s をルックアップすることもできます。しかし、Deflate ではビット数毎に上限と下限の数値を用意して判定することもできます。ビット数が同じ符号語は連続しているからです。これが Deflate のハフマン符号の良い点です。固定ハフマン符号ではあまり違いが分かりませんが、動的ハフマン符号では有用です。Deflate が少し理解できた気がしますね。
変数 s が 255 以下なら［リテラル］で、256 なら［終端］だ。どちらも場合も変数 dec に追加すればよい。
if s<=256:
dec += [s];
else:
変数 s が 257 以上なら［長さ］である。まず RFC1951 で定義されている長さと距離の表を変数にしておく（...えー、辞書なんですか、処理速度は良いの？、そもそもビット列って 32K*8 で 256K。そのコピーをボコボコ作ってガベージコレクションに迷惑だよ、とても遅いし、止めなよ。これだから最近の若者は）。
length_codes = {
257:(0, 3), 265:(1,11), 273:(3, 35), 281:(5,131),
258:(0, 4), 266:(1,13), 274:(3, 43), 282:(5,163),
259:(0, 5), 267:(1,15), 275:(3, 51), 283:(5,195),
260:(0, 6), 268:(1,17), 276:(3, 59), 284:(5,227),
261:(0, 7), 269:(2,19), 277:(4, 67), 285:(0,258),
262:(0, 8), 270:(2,23), 278:(4, 83),
263:(0, 9), 271:(2,27), 279:(4, 99),
264:(0,10), 272:(2,31), 280:(4,115) }
distance_codes = {
0:(0, 1), 8:(3, 17), 16:( 7, 257), 24:(11, 4097),
1:(0, 2), 9:(3, 25), 17:( 7, 385), 25:(11, 6145),
2:(0, 3), 10:(4, 33), 18:( 8, 513), 26:(12, 8193),
3:(0, 4), 11:(4, 49), 19:( 8, 769), 27:(12,12289),
4:(1, 5), 12:(5, 65), 20:( 9,1025), 28:(13,16385),
5:(1, 7), 13:(5, 97), 21:( 9,1537), 29:(13,24577),
6:(2, 9), 14:(6,129), 22:(10,2049),
7:(2,13), 15:(6,193), 23:(10,3073) }
そして、［記号Ａ］（変数 s）毎に定義されている［補助１］のビット数を変数 b として、［補助１］を［ビット列］から取り出して、反転して、数値に変換して、［記号Ａ］毎に定義されているオフセットに加算して［長さ］（変数 l）を求める。
b = length_codes[s][0]
l = length_codes[s][1] + cnv_n(rev(r[:b])); r = r[b:]
さらに、ビット列の次の５ビットを変換して、［記号Ｂ］（変数 t）にする。単に数値にしているだけに見えますが、これがハフマン符号Ｂです。ビットの順を反転していないのはハフマン符号だからです。
t = cnv_n(r[:5]); r = r[5:]
そして、［記号Ｂ］（変数 t）毎に定義されている［補助２］のビット数を変数 b として、［補助２］を［ビット列］から取り出して、反転して、数値に変換して、［記号Ｂ］毎に定義されているオフセットに加算して［距離］（変数 d）を求める。
b = distance_codes[t][0]
d = distance_codes[t][1] + cnv_n(rev(r[:b])); r = r[b:]
［長さ］と［距離］はペアにして変数 dec に追加する。
dec += [(l,d)]
以上を［終端］が出るまで繰り返す、というか［終端］が出たら処理終了する。
if s == 256: break
＊＊＊
［長さ］と［距離］は、参照してる表が違うだけで、同じ処理ですね。表の説明をしていなかったので、ここで補足します。［距離］の distance_codes は、［記号Ｂ］の 0〜29 に対応して２個の数値があり、１個目が［補助２］のビット数、２個目がオフセットです。29 の場合なら、［ビット列］から 13 ビットを切り出して数値にして、オフセットの 24577 に加算すると［距離］となるのです。
(b,ofs) = distance_codes[t]
d = ofs + cnv_n(rev(r[:b])); r = r[b:]
と、このように書いた方が分りやすいでしょうか。
ところで、［長さ］の length_codes で、［記号Ａ］の 284 は (5, 227) となっています。5 ビットの補助１とオフセット 227 なので、227〜258 (=227+31) までの［長さ］と対応します。ところが［記号Ａ］の 285 は (0, 258) で、補助１は無し、オフセットは 258 です。つまり、［長さ］の「258」は［記号Ａ］284 でも［記号Ａ］285 でも表現できることになります。補助１が要らない［記号Ａ］285 で表現した方がお得です（...と zlib が指摘しています）。RFC1951 では length_codes の表で［記号Ａ］284 は［長さ］の 277〜257 に対応すると定義していますけれども、本文中では特に言及はありません。どういうことなのか不思議ですね。
［記号Ａ］の 286 や 287 は、符号語を定義したけれど使用しないのはもったいない気がします。使用しないことに積極的なメリットはあるのでしょうか。これも謎ですね。気になります。
＊＊＊
ハフマン符号のデコード結果を格納した変数 dec は、次のようにしてＬＺ７７のデコードができる。デコード結果は変数 rc に文字列として格納する（...文字列はバイト列のようなものですね）。
rc = ""
for c in dec:
if type(c)==int:
if c <= 255: rc += chr(c)
if c == 256: break
elif type(c)==tuple:
for x in range(c[0]): rc += rc[-c[1]]
変数 dec には［リテラル｜終端｜長さと距離］が格納されている。［リテラル］と［終端］は１個の数値で、［長さと距離］は２個の数値のペアです。変数 dec の先頭から順番に変数 c に取り出して、それの型が「int」なら［リテラル］か［終端］なので、数値を確認して［リテラル］なら変数 rc に追加、［終端］なら処理終了。変数 c の型が「tuple」なら［長さと距離］なので、rc の後ろから［距離］の位置にある文字を、［長さ］の回数だけコピーする。これでおｋ。
＊＊＊
それはさておき、zlib の圧縮データを手動でデコードしようという話だったはず（...手動とは？）。
10 バイトのデータ "ABABABABAB" を zlib で圧縮すると、6 バイトの 0x737472844200 となる。これを最下位ビットを先にビット列にすると（...1 バイト目の 73h は 01110011 で、これを逆順にしています。2 バイト目以降も同様に）、
11001110 00101110 01001110 00100001 01000010 00000000
となる。8 ビット毎にスペースを入れています。
最初のビットは BFINAL で、「1」はこのブロックが最終ブロックであることを意味する。次の２ビットは BTYPE で、「10」をビット順を反転して 01 にして、固定ハフマン符号による圧縮であることを示す。なお、00 は非圧縮で、10 は動的ハフマン符号による圧縮だ。11 だったらエラーですね。
4 ビット目以降がデータブロックの本体となる。これらをデコードすると、
1(BFIN,1) 10(BTYP,01) 01110001(LIT,41h) 01110010(LIT,42h) 01110001(LIT,41h) 0000101(LEN,7) 00001(DIS,2) 0000000(EOB) 00
となって、「41h, 42h, 41h, (7, 2), 256」であることが分かる（...41h がＡで、42h がＢですよ）。
4 ビット目からの 8 ビット「01110001」は、01110001 - 00110000 = 01000001 なので、［ＬＩＴ］の 41h になります。
［ＬＥＮ］の 7 と、［ＤＩＳ］の 2 は、［記号Ａ］の 261 と［記号Ｂ］の 1 と対応するもので、length_codes の 261 と distance_codes の 1 を見ると、どちらも補助のビットは 0 なので、補助１と補助２はここにはない。
これをＬＺ７７で変換すれば元の文字列が得られるはずだ。
ＬＺ７７は［リテラル］を「ＡＢＡ」と出力した後、距離 2 からのコピーを 7 回繰り返す。距離 2 とは後ろから 2 個目のことで、「ＡＢＡ」の場合は「Ｂ」を指す。
1 回目「ＡＢＡ」＋「Ｂ」
2 回目「ＡＢＡＢ」＋「Ａ」
3 回目「ＡＢＡＢＡ」＋「Ｂ」
4 回目「ＡＢＡＢＡＢ」＋「Ａ」
5 回目「ＡＢＡＢＡＢＡ」＋「Ｂ」
6 回目「ＡＢＡＢＡＢＡＢ」＋「Ａ」
7 回目「ＡＢＡＢＡＢＡＢＡ」＋「Ｂ」
その後、ＥＯＢが来て終端となる。
ＬＺ７７の変換で「ＡＢＡＢＡＢＡＢＡＢ」が得られましたね。ちゃんとデコードできましたね。
＊＊＊
ＬＺ７７「アバババ、バブー」
私「なんかしゃべった！」
冬の夜はまだ長く、春は遠い。
＊＊＊
