3 The Hacking of LHa for UNIX (3rd draft)
4 -------------------------------------------
6 Koji Arai <arai@users.sourceforge.jp>
8 本書は、LHa for UNIX 1.14i のソースを解読し、その圧縮アルゴリズムの実
9 装を確認するためのものだ。この成果は別の形でまとめなおされ資料になるか
10 もしれないし、このままの形で保管されるかもしれないし、新たにソースを書
11 き起こす元になるかもしれない。とにかく、暇な正月休みを潰すためにやって
12 みただけのものだ。(休みが明けるとまた忙しくなるので、これ以上まったく
15 本書は、まだ未完成である。にもかかわらず公開するのはこれ以上続かないか
16 もしれないからである(気が向いたらまた続きを書くだろう。あるいは応援の
19 本書はフリーである。複製、改変、再配布は自由であるということだ。ただし
20 本書により生じたあらゆる損害、不利益に対しては一切の保証はない。本書に
21 は嘘があるかもしれない。それに対して嘘を教えられたと著者を避難をしない
22 で頂きたい。しかし間違いの指摘は構わない(ぜひお願いしたい)、著者は圧縮
23 処理に関しては無知である。用語の使い方等は適切でないかもしれないのでこ
35 ===============================================================================
38 * 関数は、その定義ソース file.c と関数名 func() を示すのに
42 * 配列の添字は、Python言語のスライス演算子の記法に準じた
44 a[m:n] は、m <= i < m+n の範囲の a[i] を意味する。
46 * 値の範囲は、Ruby言語の範囲演算子の記法に準じた。これを配列の
49 m <= i <= n -> i = m..n
50 m <= i < n -> i = m...n
52 a[m..n] は、m <= i <= n の範囲の a[i] を意味する。
54 * m の n 乗 は、m^n で表す。^ は、排他的論理和としても利用されるが
57 * v{n} は、変数 v の値が n であることを表す。n は、サンプルの値であったり
63 ary[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }
71 符号語は、1つの文字を符号化した結果。圧縮文は符号語の並び。
76 復号語は、圧縮文から1つの文字を復号化した結果。復号文は復号語の並び。
79 圧縮前の文を示す。対して復号文は、復号した後の文を意味する。
84 動的 Huffman 法、静的 Huffman 法
86 ===============================================================================
90 ----------------------
94 slide辞書法は、encoding にさまざまな工夫が凝らされるのでとても複雑だが、
95 普通 decoding は単純である。decoding を解析することでどのような圧縮文
98 decoding を行う処理は、slide.c の decode() である。この処理を見てみる
101 1. huffman coding により復号した文字を環状バッファ dtext に書き込む
102 通常の文字 c は、c < 256 で表現されている(つまりそのまま)
104 2. 通常の文字でないものが現れたら、それは長さである。長さ len は、
105 len > 255 で表現されている。len から 0xfd(253) を引いた値が
106 実際の長さを表す(-lzs- method の場合は、0xfe(254)を引く)
107 「長さ」が、現れたらその直後には「位置」が書かれているのでそれを
108 読む。こうして、長さと位置のペア<len, pt>を得る
110 dtext から pt+1 バイト前の len バイトを読み、dtext に追加で書き込む
112 3. dtext が一杯(dicsiz)になったらファイルに書き出す
114 これの繰り返しである。つまり、slide 辞書法の圧縮文は、文字 c と<len,
115 pt> の並びであることがわかる。例えば、文字列 c1 c2 c1 c2 は、以下のよ
116 うに表現されているはずである。(本当は、長さが 2 以下では圧縮が起こらな
117 いので平文のまま出力する。長さは最低でも 3 は必要)
123 では、この構造を作成する圧縮処理について考える。slide 辞書法では、ファ
124 イルから読み込んだ文字列 token が、以前に読み込んだ辞書に存在すれば
125 <len, pt> のペアを出力し、存在しなければ token をそのまま出力する。読
126 み込んだ token は、辞書に追加し、辞書の語が溢れたら古い情報を捨てる。
130 while (read_file(&token, tokensiz)) {
131 len = search_dict(dict, token, &pt);
136 update_dict(dict, token);
139 のようになるはず。ここで、tokensiz は token の最大サイズで、最長一致長
140 を表す。この値が大きければ大きい程、圧縮効率は良くなるはずで、lha では、
141 これは MAXMATCH{256}である。また、dict は辞書でこのサイズは lha の
142 -lh5- メソッドでは、8192 となっている。この辞書も大きければ大きい程良
143 いはずだ。その方が一致文字列が見つかりやすい。(ただし、辞書が大きいと
144 一致位置を示す情報 <len, pt> の情報量が増えるはずだし、速度も遅くなる
147 で、実際にソースを見てみると(slide.c:encode())・・・、まったくこのよう
148 な構造にはなってないように見える。何やらややこしいことばかりでまったく
149 わからない。なぜここまでややこしいのかと泣きたくなってくるが、それは速
150 度のためである(本当？)。上記のコードで、search_dict() は、単に dict か
151 ら token に一致する位置を検索するだけで良さそう(実際にそれでも良い)だ
152 が、これではまったく速度が出ない。このあたりの工夫が slide 辞書法のキ
155 そういうわけで、この部分を読み解くことにする。なお、予備知識として lha
156 では、辞書から token を探すのにハッシュが使われているらしいことを記し
159 ここでは実際にデバッガで動作させながら解読するのではなく、ソースを読む
160 だけで理解できるかを試すことにする。また、本文は某書(謎)のノリをマネて
161 いると指摘する方がいるかもしれない・・・がまったくその通りだ。
163 まず、そのものずばりの encode() (slide.c) を見る。以下がこの関数だが
164 処理の要点だけに着目するために不要そうな部分は(現時点で予測で)削った。
170 unsigned int lastmatchoffset;
176 remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
177 encoded_origsize = remainder;
178 matchlen = THRESHOLD - 1;
182 if (matchlen > remainder) matchlen = remainder;
185 hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
186 ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
191 while (remainder > 0 && ! unpackable) {
193 lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
197 get_next(); match_insert();
198 if (matchlen > remainder) matchlen = remainder;
201 if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
203 encode_set.output(text[pos - 1], 0);
207 encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
208 (lastmatchoffset) & (dicsiz-1) );
211 while (--lastmatchlen > 0) {
212 get_next(); insert();
216 matchlen = THRESHOLD - 1;
218 if (matchlen > remainder) matchlen = remainder;
223 まず、この関数から概観を見てみると、ループの前に初期化処理として
226 (A) init_slide() 初期化する
227 (B) ファイルを読み込み text[] に格納する。
228 (C) ハッシュ値 hval を計算する。
229 (D) insert() する (きっと辞書に token を追加しているのだろう)
231 そして、ループ処理では以下の処理が行われている
233 (E) lastmatchlen, lastmatchoffset, matchlen を更新する。
234 (F) get_next() (次の token を読む。たぶん)
235 (G) match_insert() (辞書に追加する。たぶん)
237 (H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
239 (H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
240 (H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
242 現時点で、(H.2) の部分はよく解読できなかった。何やら再度 get_next() が
243 呼ばれていたりして思った通りの処理フローにはなっていない。だが、ここで
244 は焦らず放置することにして、ここまで予想で書いた部分の細部に触れること
245 にする(単にここまでの予想が間違っているだけかもしれないのだから、わか
246 らない部分を無理にわかるように頑張る必要はなかろう)
248 関数の細部に触れる前にデータ構造について調べておく。データ構造に対して
249 の理解が深まればアルゴリズムの80%は分かったも同然だ(誇張)。slide.c で
250 使用されているデータ構造は以下の通りだ。(不要そうだと思うものは除いて
253 static unsigned int *hash;
254 static unsigned int *prev;
255 unsigned char *too_flag;
256 static unsigned int txtsiz;
257 static unsigned long dicsiz;
258 static unsigned int hval;
260 static unsigned int matchpos;
261 static unsigned int pos;
262 static unsigned int remainder;
264 too_flag だけ、static がついてないが、他のソースを grep してもこの変数
265 を使っている箇所はない、単に static の付け忘れだろう。
267 これらの変数は、encode() の冒頭 init_slide() で初期化されている・・の
268 かと思ったら違った。slide.c:encode_alloc() で行われている。
274 if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
275 encode_set = encode_define[0];
277 dicbit = 12; /* 12 Changed N.Watazaki */
278 } else { /* method LH4(12),LH5(13),LH6(15) */
279 encode_set = encode_define[1];
281 if (method == LZHUFF7_METHOD_NUM)
282 dicbit = MAX_DICBIT; /* 16 bits */
283 else if (method == LZHUFF6_METHOD_NUM)
284 dicbit = MAX_DICBIT-1; /* 15 bits */
285 else /* LH5 LH4 is not used */
286 dicbit = MAX_DICBIT - 3; /* 13 bits */
289 dicsiz = (((unsigned long)1) << dicbit);
290 txtsiz = dicsiz*2+maxmatch;
292 if (hash) return method;
294 if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
296 hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
297 prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
298 text = (unsigned char*)malloc(TXTSIZ);
299 too_flag = (unsigned char*)malloc(HSHSIZ);
301 if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
307 引数に渡された method (これは、lh1, lh5, lh6, lh7 などを示す)によって、
308 初期化される内容が変わる(encode_alloc()前半部分)。このことから各変数の
311 method maxmatch dicbit
312 ----------------------------
318 ということらしい。dicbit というのは辞書サイズのbitサイズで、辞書サイズ
319 は 2^dicbit で表されている。lh5 が 8KB(2^13)、lh6 が 32KB(2^15)、lh7
320 が 64KB(2^16) の辞書サイズを利用すると言うのは予備知識である。maxmatch
321 というのは、token の最長一致長である。このことも予備知識として詳細には
322 触れない。(ところで、本書では当面、lh5, 6, 7 のことしか言及しない)
324 encode_set, encode_define というのがあるが、method によって、Huffman
325 coding の方法を変えていることはちょっと見ればすぐにわかるし、大したこ
328 encode_alloc() の後半では、他の変数の初期化(バッファの割り当て)が行われる。
330 dicsiz = (((unsigned long)1) << dicbit);
332 dicsiz はそのものずばり辞書サイズである。
334 txtsiz = dicsiz*2+maxmatch;
336 現時点で txtsiz が何なのかはわからない。
338 if (hash) return method;
340 hash はこの直後で割り当てられる。つまり、一度割当を行ったら、
341 encode_alloc() は、以降メモリの割当を行わない。ただそれだけだ。
343 if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
345 alloc_buf() は、huf.c で定義された関数。このことから Huffman coding の
346 ためのバッファを割り当てているのだろう。ここでは無視。(しかし、207 と
349 hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
350 prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
351 text = (unsigned char*)malloc(TXTSIZ);
352 too_flag = (unsigned char*)malloc(HSHSIZ);
354 if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
357 hash は、ハッシュ用の何か、HSHSIZ は、固定値で 2^15 である。
359 prev は、DICSIZから辞書だろう。要素の型が char でなく int であることに
360 も注目しておく。DICSIZ は dicsiz でも構わないはず。単に「大は小を兼ね
361 る」を実践しているだけであろう、TXTSIZ も同様である。おそらく、一度の
362 実行で複数の圧縮メソッドを使用した場合、そのメソッド毎に領域を割り当て
363 るよりは最大の値をあらかじめ一度だけ割り当てた方が良いと考えたのだろう。
364 しかし、ソースを参照するときは繁雑になるので以降、
373 っとなる。まだ、良く分からないが、以下の図を書いておこう。後で何度も見
374 ることになるだろう。この図はスケールが lh7 の場合を想定しているが。こ
375 のことは大したことではないはずだ。また、too_flag と hash のスケールが
376 一緒だがこれはサイズ(領域のバイト数)が一緒なのではなく、要素数が一緒で
377 あることを示している。ほとんどの場合要素の型の違いというのは処理内容に
380 ----------------------------------------------------------------------------
385 +-------------+ dicsiz=2^dicbit
386 +-------------+-------------+ 2*2^dicbit
388 +-------------+-------------+ v txtsiz
389 +-------------+-------------+-------------+-------------+---+
391 +-------------+-------------+-------------+-------------+---+
398 ----------------------------------------------------------------------------
401 先に示した変数の中でまだ初期化には現れていないものがある。列挙すると
403 static unsigned int hval;
405 static unsigned int matchpos;
406 static unsigned int pos;
407 static unsigned int remainder;
409 だ、ざっとソースを眺めると slide.c:insert() という関数に
411 というのが現れているから、hval は、hash[] の位置を指し、hash には、pos
413 prev[pos & (dicsiz - 1)] = hash[hval];
414 というのも現れているから pos は、prev[] の位置を指し、prev には、
415 hash[hval] つまり、pos を格納しているようだ。これは少し謎な処理だが、
416 insert() の全貌は短い(というかこれだけ)なので、ちょっと横道にそれて詳
417 細に見てみよう。(現在の解析の趣旨は、変数の用途の概要を予想すること)
419 /* 現在の文字列をチェーンに追加する */
423 prev[pos & (dicsiz - 1)] = hash[hval];
427 コメントはまったく意味不明だが、無視して処理内容に着目する。prev[] の
428 インデックス pos & (dicsiz - 1) は、dicsiz が 2^n であることからdicsiz
429 はビットマスクであることがわかる。例えば仮に dicsiz が 2^8 だと
432 8 7 6 5 4 3 2 1 0 bit
433 --------------------------
434 dicsiz 1 0 0 0 0 0 0 0 0
435 dicsiz-1 1 1 1 1 1 1 1 1
437 である。このすべて 1 が立ったビットマスクと pos を & すると、どのよう
438 な pos の値に対しても pos & (dicsiz - 1) は、prev[] のインデックスの範
439 囲に納まる。もう少し言うと pos が仮にインデックスの最大値+1だった場合、
440 pos & (dicsiz - 1) は、0 になる。これにより次の予想が立つ。
442 o pos が、prev[] の位置を指すのではなく、pos & (dicsiz - 1) が
443 prev[]の位置を指す。(pos は、このインデックスの範囲を越える可能性がある)
444 o それに反して、prev[] は環状バッファらしいという予想が立てばやはり
445 pos は、prev のインデックスである。
447 prev が環状バッファであると予想が付けば話が早い。pos & (dicsiz-1) は、
448 pos と同義だと解釈可能だからである(prev が環状バッファでなく無限長のバッ
449 ファであると想像しよう)そして、pos & (dicsiz-1) を pos に置き換えて、
452 prev[pos] = hash[hval];
456 1. (この関数に来る前に) pos が更新される。(予想)
457 2. prev[pos] に以前の hash[hval] (以前の pos)を格納する
458 3. hash[hval] に新しい pos を書く。
459 といった処理であることが予想される。コメントの「チェーン」もなんとなく
460 納得できる。新たな事実(まだ予想だが)が分かったので、図に書き記そう。
462 ----------------------------------------------------------------------------
471 +----+-----+--------------------
472 prev | |pppos| |ppos| . . .
473 +----+-----+--------------------
476 * hash の取り得る値は pos その位置は hval
477 * ppos は以前の pos を示す。pppos はさらに以前の pos を指す。
478 * prev は無限長のバッファ(本当は環状バッファ)
479 ----------------------------------------------------------------------------
484 static unsigned int matchpos;
485 static unsigned int remainder;
487 しかしこれらはどうにもパッと見ではわからない。処理内容を追いかけないと
488 だめそうだ。仕方ないので変数名で予想しよう。(幸い前の変数名と違って予
491 ----------------------------------------------------------------------------
493 * matchpos 一致した辞書上の位置
494 * remainder token の残りサイズ
495 ----------------------------------------------------------------------------
497 はたして、予想はあっているのか、今はまだ分からない。
499 slide.c を見る限りデータ構造は網羅できた。結局分かったのか分からないの
500 か良く分からないが少しずつでも前進はしているはずだ。ここで、再度
501 encode() の処理を追いかけよう。今度は細部にも着目する。
503 前に、encode() のソースには (A) 〜 (H) までの記号を記した。この順番に
511 for (i = 0; i < HSHSIZ; i++) {
516 だけである。NIL というのは、0 であると slide.c で定義されている。普通
517 このような初期値は、通常の値が取り得ない値を示している。NIL が 0 なら
518 hash[] に格納される pos は 0 にならない可能性がある。まあ、予想ばかり
519 書いても仕方ないので、この関数は終ろう。余談だが、nil は null と同じで。
520 「ない」の意味だが、NULL がC言語ではポインタだから。別のマクロ名にした
521 のかも知れない。いずれにしてもこの程度はマクロにする必要もなかろうとは
525 remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
526 encoded_origsize = remainder;
527 matchlen = THRESHOLD - 1;
531 if (matchlen > remainder) matchlen = remainder;
533 ファイルを読み込み、各変数の初期値を設定している。注目すべきはファイル
534 を読み込んだバッファの位置である。fread_crc() は、crcio.c で定義された
535 汎用関数で、CRC値を計算したり漢字コード変換をしたりを除けば、fread()
538 &text[dicsiz] の位置に、txtsiz-dicsiz 分だけ読まれる。
542 ----------------------------------------------------------------------------
545 dicsiz=2^dicbit 2*2^dicbit
547 +-------------+-------------+-------------+-------------+---+
549 +-------------+-------------+-------------+-------------+---+
553 <------ remainder -------------->
555 |--- この位置に最初の ---------|
557 ----------------------------------------------------------------------------
559 ますます、text[] の用途が不明だが、slide 辞書法の典型的な読み込み処理
560 のことを考えるとある程度予想がつく(それを先に示した方が良いか？)。まあ、
563 fread_crc() は、読み込んだバッファ長を返す。remainder がその値で、既に
564 図示してある。encoded_origsize は、ソースを見ると、元のファイルのサイ
565 ズを表すためだけの変数のようだ。以降は無視しよう。
567 ところで、ファイルサイズが小さい場合図の通りにならないっと考えるかも知
568 れない。その通りなのだが、例外条件は少ない方がソースは理解しやすい。単
569 純な場合だけを考えた方が、あれこれ考えをめぐらす必要がないからだ。なに
570 しろ既に動くソースを見ているのだから、細かいことに目をつぶってもエンバ
571 グすることはないのである。そういうわけで、当面はこの図が唯一の初期状態
574 (B) の部分はもう少し注目すべき箇所がある。
576 matchlen = THRESHOLD - 1;
578 matchlen は、「一致した文字列長」であると予想したが THRESHOLD の値は 3
579 (固定値)であるから、matchlen の初期値は 2 だ。いきなり予想がはずれた気
580 がする。予想を立て直そう。2 という謎な数値と match*len* について考える
581 と、冒頭で <len, pt> のペアの len は 2 であることはないと説明した。無
582 意味だからであるが、matchlen の初期値はこの 2 と関連するかもしれない。
583 そこで、matchlen の用途を以下のように予想しなおすことにする。以下のよ
584 うにメモを更新しよう。THRESHOLD(threshold は閾値の意)も一緒に予想した。
586 ----------------------------------------------------------------------------
587 * matchlen 最低限一致しなければならない長さ-1
588 * THRESHOLD 最低限一致しなければならない長さ
589 ----------------------------------------------------------------------------
597 if (matchlen > remainder) matchlen = remainder;
599 pos が dicsiz であることからどうやら、pos は、text[] のインデックスら
600 しい。前の予想で pos は、prev[] のインデックスでもあり、hash[] の値で
601 もあると予想したのだが(これはもちろん間違いではなかろうが)。どうやら
602 本当の意味は、処理するテキストの先頭を示しているのではないかとも思える。
603 まあ、ここでは無難に「text[] のインデックス(でもある)」とだけ理解しよう。
606 次の if だが、remainder が matchlen よりも小さい場合の条件だ。また、
607 matchlen の予想が覆されそうな予感がしないでもないが、この if 文は*例外
608 条件*なので無視することにした。都合の悪いことは見ない方が良いのだ。
611 hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
612 ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
614 (C) である。これは難解である。複雑な数式は苦手であるが、じっくり考えよ
615 う。まず求める値は hval である。これは hash[] のインデックスなのだが、
616 このような複雑な式で求まるインデックスなんて想像もつかない。まず、最初
617 のインスピレーションを大事にすることにしよう。冒頭で、(C) の処理は「ハッ
618 シュ値 hval を計算する。」っと苦もなく予想した。そしてこれは間違いでは
619 ないだろう(きっと)。hash[] との関連をここで考えてもわからないから、こ
620 のハッシュ値の計算だけを考えることにしよう。
622 式をじっくり見てみる。。。じっくり見てみると以下のことがわかる。
624 x(i) = text[dicsiz + i]
629 & (unsigned)(HSHSIZ - 1);
631 である。演算子 << は、演算子 ^ よりも優先順位が低いので余計な括弧は省
632 略した。最後の & (unsigned)(HSHSIZ - 1) は、前にも似たような式が出たが
633 これはある範囲の数値(ここでは、0 〜 HSHSIZ{2^15}-1)を抽出するためのビッ
634 トマスクである。ハッシュ関数と言うのはある符号をある集合の符号に写像す
635 る関数であるからこのようなビットマスクは当然必要だし、良く行われる事だ
636 (普通は mod 素数を行うんだけど)。また、hval は、hash[] のインデックス
637 なのだから、写像する集合とは hash[] のインデックスだ。おっ、案外簡単に
638 わかった。x(i) が text[dicsiz + i] で、ハッシュ関数の変数は x(0),
639 x(1), x(2) だから、先頭の 3 バイトの文字列(平文)のハッシュ値を求めてい
640 るわけだ。その他の計算(<< 5 とか ^ とか) は大したことではない。無視し
641 よう。また、続けて (D) の処理も見るが、
646 insert() は、幸い解読ずみである pos を hash[] に格納する処理だ。
647 予想の段階では、(C) と (D) を別個の処理と考えていたのだがこれは
650 (C) pos の位置の 3 文字のハッシュ値を計算し
651 (D) hash[ハッシュ値] = pos を行う
653 もう少し注意深く検討すると「posの位置の3文字」と、求めた「ハッシュ値」
660 という処理を行っている。ハッシュ値の衝突はここでは考えない。slide 辞書
661 法では、ある文字列に対し以前その文字列が現れたかどうかを検索し、その位
662 置を求める必要があるのだが、この最初の 3 文字に関しては現時点でその用
663 件(位置を求める)を満たす事ができている。ここまでで自ずと encode() の全
666 衝突は考えないっとしたが、ちょっと考えたらすぐわかった。prev[] には、
667 以前のハッシュ値で求めた文字列の位置が入っている。つまり、prev[] はハッ
668 シュが衝突したときのためのバッファだ。このハッシュはチェーン法だ。
671 prev[pos] = hash[hval];
684 といった値が入る事になる。ある文字列(のハッシュ値) hval に対して、その
685 辞書上の位置は pos1, pos2, pos3 という候補があるわけだ。実際にどの pos
688 # それにつけても、(C) と (D) の部分を見るだけでもこのソースがちょっと
689 # 汚いことがわかる。もう少し、引数とか戻り値とか考えてくれても良かっ
690 # たはずだ。ハッシュ関数にしても少なくともマクロぐらいにはしようよ。
692 (E) 〜 (H) に移ろうこれはループの中身で、処理の本題だ。まずループの脱
695 while (remainder > 0 && ! unpackable) {
697 remainder は、バッファ上に読み込んだ平文の長さであるからこれがなくなる
698 までループすることになる。さらに unpackable というのは、crcio.c の
699 putcode() でその値を設定している箇所が出て来るのだが、符号化した出力サ
700 イズが元のサイズを越えたときに真になる。つまり、これ以上処理しても圧縮
701 の意味がないとわかったらループを抜けるわけだ。
706 lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
709 ちょっと見ただけではやはりわからない。これらの変数はまだ予想しかしてな
710 いからである。が、わかるだけの情報は書きしるそう。
712 ----------------------------------------------------------------------------
713 * lastmatchlen 以前の matchlen の値 (変数名から)
714 * lastmatchoffset 以前マッチした位置 (変数名から)
715 ----------------------------------------------------------------------------
717 以前の値をlast〜に退避し、新たな値を設定する準備をしているわけだ。そし
718 て、「新たな値の設定」は、--matchlen で早速行われている。しかし、「マッ
719 チした長さ」をまだ何もしてないのに -1 するというのはいったいどういうこ
720 とだろう？ matchlen はループの頭で 2 に設定されている。これが 1 になっ
723 ----------------------------------------------------------------------------
731 lastmatchoffset = dicsiz - 1 (pos - matchpos - 1)
732 ----------------------------------------------------------------------------
734 この (E) はまた後で見る事になるだろう。
736 (F) (G) である。また、その直後には以前にも見た境界条件がある。
739 get_next(); match_insert();
740 if (matchlen > remainder) matchlen = remainder;
742 if 文 は無視して関数の中身だけを追いかけてみよう。まず、get_next() こ
743 れは 次の token を取ってくる処理だと予想してある。はたしてどうだろうか？
745 static void get_next()
748 if (++pos >= txtsiz - maxmatch) {
751 hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
754 remainder を消費し、pos を進めている。予想通りだ。ひとまず if の条件は
755 無視すると、直後で hash 値を求め直している。このハッシュ関数は、以前のハッ
756 シュ値を利用しているが、これは pos が以前より + 1 されていることを考え
757 ると関連が見えて来る。以前のhash関数を pos の関数として書き直すと
759 x(pos+i) = text[pos + i]
761 hval(pos) = (( x(pos+0) << 5
764 & (unsigned)(HSHSIZ - 1);
768 hval(pos+1) = ( hval(pos) << 5
770 & (unsigned)(HSHSIZ - 1);
772 だ、繁雑なので & (HSHSIZE-1) を外すと、
774 hval(pos+1) = (( x(pos+0) << 5
779 っとなる。この次 get_next() が呼び出されれば、
781 hval(pos+2) = ((( x(pos+0) << 5
787 である。順にハッシュ値を求める文字列長を増やしている。とにかく、
788 get_next() は、pos を進め、remainder を縮め、新たな(以前より1文字長い)
789 文字列のハッシュ値 hval を求める関数のようだ。
791 しかし、いつまでも hash 値の元となる文字列を伸ばしてもしょうがないだろ
792 う。hval はどこかでまたリセットされるはずだ。っと思ってソースを探して
793 みたがそのような箇所は見当たらない。なぜだろう？考えてみる・・・最初は
794 わからなかったが数式をよく見てみたらわかった。<< 5 が鍵だ、hval(pos+2)
795 の式を見ると x(pos+0) は、<< 5 が、4回も行われているつまり、20ビットの
796 シフトだ。hval(pos+3) なら、25ビット、hval(pos+4) なら 30 ビットのシフ
797 トだ。さすがにこれだけシフトすれば、x(pos+0)の情報は消えてもいいだろう。
799 実際、hval は何文字分の情報を持つのだろう？hval は、unsigned int で、
800 普通 32 bit であるから、6.4 文字分だろうか？いや、実際にはハッシュ値の
801 計算時にHSHSIZ (15bit) でマスクをかけているから 15 bit の情報しか持た
802 ない。つまり、3文字だ。ビット計算は苦手なので図示して確認しよう。
804 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
805 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
806 hval |--| | | | | | | | | | | | | | | |
807 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
809 最初の hval(0) は、x(0), x(1), x(2) に対して、
811 <--- 5 -----> <--- 5 -----> <--- 5 ----->
812 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
813 x(0) <<10 -- x x x x x
814 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
815 x(1) << 5 -- x x x x x x x x
816 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
817 x(2) -- x x x x x x x x
818 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
820 の排他的論理和である。hval(0) の時点で x(0) の情報は 5 ビット残ってい
821 るが hval(1) になれば消えてしまうのは自明である。どうにも最初の文字に
822 関しては 5 ビットしか情報を使用しないと言うのが気持悪いのだが、15 bit
823 サイズの変数 hval には、過去 3 文字分の情報しか保持されないのは間違い
824 ない。get_next() の処理を見れば、位置 pos に対して、hval は常に pos,
825 pos+1, pos+2 の情報しか持たないわけだ。これは重要だ。メモしよう
827 ----------------------------------------------------------------------------
828 * hval hash[]のインデックス。現在位置 pos に対して、
829 text[pos], text[pos+1], text[pos+2] のハッシュ値で、論理的には
830 hval == text[pos] + text[pos+1] + text[pos+2]
832 ----------------------------------------------------------------------------
834 ところで、前回、hval の計算とinsert() はセットだと言った。今回はどうだ
835 ろう？次の match_insert() を見てみる。
837 static void match_insert()
841 prev[pos & (dicsiz - 1)] = hash[hval];
845 ・・・強敵であった。強敵すぎたので逃げて、最後の2 行だけに着目した。こ
846 れは、insert()と同じだ。予想は当たっている。get_next() で hval を更新
847 した後は、この match_insert() で、prev[] と hash[] を更新するわけだ。
848 そして、match_insert() の省略した部分は、どうやら matchpos, matchlen,
849 too_flag を更新しているだけのようだ。これが本当なら match_insert()で、
850 insert()の処理をせず、関数を分けるかした方が良さそうだ。(真偽の程は詳
856 if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
858 これが真なら「見つからなかった状態」と予想した(なぜだろ？)。そして、
859 lastmatchlen は初期状態では 2 である。予想した条件は逆か？ matchlen ま
860 わりは予想ばかりで進めすぎた。そしてどうやら match_insert() を読みとか
861 なければこの先も分からずじまいになりそうだ。
863 このまま match_insert() を詳細に解析する事にしよう。match_insert()
866 /* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */
868 static void match_insert()
870 unsigned int scan_pos, scan_end, len;
871 unsigned char *a, *b;
872 unsigned int chain, off, h, max;
874 max = maxmatch; /* MAXMATCH; */
875 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
879 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
880 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
882 if (off == maxmatch - THRESHOLD) off = 0;
886 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
887 while (scan_pos > scan_end) {
890 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
892 a = text + scan_pos - off; b = text + pos;
893 for (len = 0; len < max && *a++ == *b++; len++);
896 if (len > matchlen) {
897 matchpos = scan_pos - off;
898 if ((matchlen = len) == max) {
903 scan_pos = prev[scan_pos & (dicsiz - 1)];
909 if (matchlen > off + 2 || off == 0)
915 prev[pos & (dicsiz - 1)] = hash[hval];
921 max = maxmatch; /* MAXMATCH; */
922 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
927 maxmatch は、固定値で 256 だ、だから max も 256
928 2行目の if 文は、これまでしつこいくらいに出て来た条件に似ているが、今
931 if (matchlen > remainder) matchlen = remainder;
935 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
937 だから、全体的に matchlen の値は、
939 THRESHOLD-1 <= matchlen <= remainder
943 2 <= matchlen <= バッファに残ったテキスト長
945 の範囲に納められるようだ。ここでは、matchlen は下限値を下回るので2 に
946 設定される。次に matchpos, off が初期化され。以下の図の状態になる。
947 (pos, remainder は、get_next() で更新されていることに注意)
949 ----------------------------------------------------------------------------
951 dicsiz=2^dicbit 2*2^dicbit
953 +-------------+-------------+-------------+-------------+---+
955 +-------------+-------------+-------------+-------------+---+
956 `-pos(=dicsiz+1) <--->
957 matchpos(=pos) maxmatch{256}
960 <------ remainder ------------>
962 |--- この位置に最初の ---------|
964 ----------------------------------------------------------------------------
968 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
969 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
971 if (off == maxmatch - THRESHOLD) off = 0;
973 h は、too_flag[] が今のところすべて0だから hval だ。(too_flag は、h つ
974 まり hval をインデックスに取るらしい。hash[] と同じだ。再掲はしないが
977 off は、pos の位置からのオフセットのようだ(h を更新する for 文の中身か
978 ら)。図もその位置に書いた。最後の if 文は off が上限に達した場合に0 に
979 再初期化している。よくわからないので無視しよう。for 文の中身からh や
980 off の用途はどうも先読みしたハッシュ値とその先読みの位置なのではないか
981 と想像する。too_flag[] の状態によって先読みすべき値が変わるのだろうか？
983 とにかく処理の本題に入る事にしよう。まず、この関数に現れる局所変数を列
986 unsigned int scan_pos, scan_end, len;
987 unsigned char *a, *b;
988 unsigned int chain, off, h, max;
990 off, h, max はすでに出て来たので残りは
992 scan_pos, scan_end, len, a, b, chain
994 だ、これだけの変数の意味を解読しなくてはならない。変数は状態を表すから、
995 その数が多いと言うのはそれだけ複雑な処理だということだ。めげる。
997 この関数のメインとなるループの中をざっと眺めてみるさらに内部にループが
998 ある。ひとまず、二重ループの中身を省略しよう。
1003 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1005 while (scan_pos > scan_end) {
1013 if (matchlen > off + 2 || off == 0)
1024 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1026 chain, scan_pos, scan_end はすべて while ループに渡されるべき変数だ。
1027 さらに、while の後には、scan_pos, scan_end は現れないから(仮に while
1028 ループが1つの関数だったとすると)これらは while ループ部の引数(入力)だ。
1029 この2つの変数はどうやりくりしようとも、while ループ部内の状態しか表さ
1037 if (matchlen > off + 2 || off == 0)
1043 chain が LIMITを越えた場合、too_flag[h] = 1 としている。chain は、ざっ
1044 と見て、while ループのカウンタらしいが、LIMIT は 0x100 だ。どうにも例
1045 外条件っぽい(LIMITという名前や数値がそう思わせる)のでここでは無視しよ
1046 う。while ループが 256以上回る可能性がある点だけ心にとどめておこう。
1048 次の条件では、matchlen と off が条件判断されている。ということはこのど
1049 ちらか、あるいは両方は while ループの返り値(出力)だ。ざっと
1050 match_insert()全体を見てみると off は最初とこの直後でしか更新されない
1051 らしい。つまり、while ループ部の返り値はmatchlen の方だ。
1052 この条件は for () ループの脱出条件でもある。心にとどめて、次に進む。
1058 ふむ。よくわからない。しかし注目すべき点はある。off はここで、0 になる
1059 がこれ以降は off の値は変わらない。つまり、off は最初は何らかの値で
1060 while ループ部に渡されるが、その次からは、0 だ。この for ループが何度
1061 回ろうとも 0 だ。h も同じで最初は何らかの値を持つが、2回目のループ以降、
1062 h は hval だ。max は、off を 0 にする直前に更新しているから、h や off
1063 と事なり、3つの状態を持つ、すなわち。maxmatch, off+2, 2 だ。
1065 いや、脱出条件を見てみると off == 0 なら break とある。つまり、この
1066 for ループはどんなに頑張っても2回しか回らないらしい。やっぱり max も 2
1069 これで、1 回目、2回目に while ループ部に入る直前の状態が書ける。この関
1070 数 match_insert() は、while ループ部を1回か2回実行する処理と言うわけだ。
1072 ここで無視していた。while ループ部の入力となる scan_pos, scan_end
1073 もそれぞれどのような状態になるか書いておく
1075 ----------------------------------------------------------------------------
1082 scan_end = pos + off - dicsiz (あるいは、off)
1091 scan_pos = hash[hval]
1092 scan_end = pos - dicsiz (あるいは、0)
1096 ----------------------------------------------------------------------------
1098 上記は一般化した場合だが、今回(初回)の場合、h や off の値は、hval であ
1099 り、0 だった。2回目ループのときの状態と同じである。2回のループの違いは
1100 max の値がmatchpos であるか off+2 (すなわち2)であるかの違いしかないようだ。
1102 ここは、条件を少なくするためにこの場合だけにしぼって処理を考えよう。
1103 while ループの2回の呼び出しを行う際の状態は以下の通りに書き直せる。
1105 ----------------------------------------------------------------------------
1111 scan_pos = hash[hval]
1112 scan_end = pos - dicsiz (あるいは、0)
1121 scan_pos = hash[hval]
1122 scan_end = pos - dicsiz (あるいは、0)
1126 ----------------------------------------------------------------------------
1128 うーん、まだ、すっきりしない。何がすっきりしないかというと scan_end の
1129 値だ。これが何を意味するのかがよくわからない。scan_pos は、わかるのか？
1130 というと、わかる。hash[hval]だから現在の文字列と同じ文字列の辞書上の位
1131 置だ。さらに、現時点では get_next() で、hval を更新してから insert()
1132 を行っていないので、hash[hval] には何も入っていない。すなわち 0 だ。
1134 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1138 scan_end = (pos > dicsiz) ? pos - dicsiz : 0;
1140 なわけだ。さらに、posは現時点で dicbit+1 であるから、1 だ。図に書こう。
1142 ----------------------------------------------------------------------------
1144 dicsiz=2^dicbit 2*2^dicbit
1146 +-------------+-------------+-------------+-------------+---+
1148 +-------------+-------------+-------------+-------------+---+
1149 ^ ^ `-pos(=dicsiz+1)
1158 ----------------------------------------------------------------------------
1160 ついに、text[] バッファの左半分に指しかかる。これが何なのかは現時点で
1161 は明確に書いてなかったが予想するとこの左半分はズバリ辞書だ。言い切って
1162 やろう。今まで辞書らしい(dicsizのサイズを持つ)バッファは hash[] や
1163 prev[] があったが、hash[], prev[] の用途はもう明確である。辞書となり得
1164 るバッファはもうこの text[] しかないのだ。
1166 さらに、左半分に限らずこの text[] 全体が辞書であろうと予想する。これは
1167 ただの勘だが text[] は環状バッファなのではなかろうかと考えている。
1169 # 最初の方で prev[] が辞書だと予想したが間違った予想をしていたことにこ
1170 # の時点で気づいた。prev[] が辞書と同じサイズを持つ理由はまだよくわか
1173 この時点ではまだ scan_pos や scan_end の真の意味はわからない。off のこ
1174 とを無視しているから予想も立ちにくいが、ひとまず初期状態がどういったも
1175 のかはわかったのでこのまま、while ループ部を見てみたいと思う。
1177 while (scan_pos > scan_end) {
1180 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1182 a = text + scan_pos - off; b = text + pos;
1183 for (len = 0; len < max && *a++ == *b++; len++);
1186 if (len > matchlen) {
1187 matchpos = scan_pos - off;
1188 if ((matchlen = len) == max) {
1193 scan_pos = prev[scan_pos & (dicsiz - 1)];
1196 まず、if 文の条件を満たさない場合だけを考える。
1198 while (scan_pos > scan_end) {
1201 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1204 scan_pos = prev[scan_pos & (dicsiz - 1)];
1208 offは 0 なので、text[scan_pos + matchlen] != text[pos + matchlen] とい
1211 text[scan_pos + matchlen]
1215 text[pos + matchlen]
1219 text[scan_pos] 辞書上の文字列の*先頭*
1220 text[pos] 現在の文字列の*先頭*
1222 を比べないのは matchlen が前に予想した「最低限一致しなければならない長さ-1」
1223 だからであろう。現時点で、matchlen が 2 だから
1225 text[scan_pos + 0] == text[pos + 0]
1226 text[scan_pos + 1] == text[pos + 1]
1230 text[scan_pos + 2] != text[pos + 2]
1232 であれば、「最低限一致しなければならない長さ」という条件を満たさないの
1233 である。なので matchlen の位置から先に比較して無駄な比較をしないように
1234 している。後でちゃんとした比較の処理が出て来るだろう。このような処理は
1235 処理としては効率が良いのだが、ことソース理解と言う点では冗長である。わ
1238 # matchlen の意味の予想はどうやら当たっているようだ。matchlen は最短一
1239 # 致長で、minmatchlen っと名付けても良さそうな変数だ。
1241 そして、比較に失敗したら scan_pos を更新する。
1243 scan_pos = prev[scan_pos & (dicsiz - 1)];
1245 ハッシュのチェーンをたどっている、つまり次の候補を辞書から取り出してい
1246 るわけだ。ここまでで、while ループの処理内容の想像はついた。このループ
1247 は辞書から(最長)一致する文字列を探しているのだろう。
1249 順番が前後したが、while ループの脱出条件を見てみる
1251 while (scan_pos > scan_end) {
1253 これはどういうことだろう？ scan_pos は、ハッシュのチェーンをたどって同
1254 じハッシュ値を持つ文字列の位置を探す、この値はだんだんと小さくなって行
1256 その通りである。hash[] への格納はファイルから取って来た文字列を順に格
1257 納して行くのでチェーンの奥には、より前の方の位置が書かれているはずだ。
1258 逆にチェーンの浅い部分にはより現在位置に近い位置が書かれているのだろ
1259 う。では、その境界 scan_end はどうやってわかるのだろうか？これは後でま
1262 では、処理の本質 if 文の中を見る事にしよう
1264 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1266 a = text + scan_pos - off; b = text + pos;
1267 for (len = 0; len < max && *a++ == *b++; len++);
1270 if (len > matchlen) {
1271 matchpos = scan_pos - off;
1272 if ((matchlen = len) == max) {
1278 最初の意味もなくブロックになっている部分を見る、
1281 a = text + scan_pos - off; b = text + pos;
1282 for (len = 0; len < max && *a++ == *b++; len++);
1285 この処理では a, b といういかにも局所な名前の変数が使われている。これは、
1286 本当にこのブロック内で局所的なもののようだ。ならば定義位置もこのブロッ
1287 ク内にして本当に局所的にして欲しかった。
1289 さらに、この処理は単に文字列 a, b を比較しているだけのようだ。memcmp()
1290 ではまずいのかと言うとここで求めているものが「どこまで一致したか(len)」
1291 のようなので、memcmp() では役不足だ。
1295 if (len > matchlen) {
1296 matchpos = scan_pos - off;
1297 if ((matchlen = len) == max) {
1302 で、matchlen (最低一致長)より大きい場合に条件を満たす。条件を満たさな
1303 ければ、scan_pos を更新し、次のループに移る。では、条件を満たす場合を
1304 見てみよう。まず最短一致長の一致条件を満たした場合、matchpos と
1310 で、matchlen が max なら最長一致長に達しているので、これ以上探索はしな
1311 い。matchlen は最短一致長でありながら、一致長でもある変数のようだ。
1312 (どうやら以前の2つの予想はどちらも当たっていた模様)
1314 とにかく while ループ部の出力は、この matchpos と matchlen のようだ。
1315 前に書いた通りこのループは「最長一致文字列を求める処理」だ。
1317 match_insert() の全体をもう一度見てみよう。ただし、以下の書き換えを行う。
1319 o while ループ部は search_dict(pos, scan_pos, scan_end, max) という関数
1322 o 末尾の insert() と同等の処理を行っている部分も insert() の呼び出しに
1323 すり替えよう。(match_insert() 関数の中で insert() 処理を本当に行うべ
1326 o chain という変数にかかわる処理も隠した(search_dict内で行う)
1328 o for ループは、2回しかまわらないので、2 度の search_dict() の呼び出し
1331 static void match_insert()
1333 unsigned int off, h;
1334 unsigned int scan_end;
1336 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
1340 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
1341 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1343 if (off == maxmatch - THRESHOLD)
1346 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1347 search_dict(pos, hash[h], scan_end, maxmatch);
1349 if (off > 0 && matchlen <= off + 2) {
1352 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1353 search_dict(pos, hash[hval], scan_end, off+2);
1359 だいぶすっきりした(が、まだ繁雑だ)。まだ、off にかかわる部分がよく分か
1360 らないが、ひとまず良いだろう。この関数の解析はこれで終って良いだろうか。
1362 いや、良くない。肝心の match_insert() の出力がよくわからない。この関数
1363 は「最長一致文字列を探し、hash を更新する処理」(くどいようだが、hashを
1364 更新するは余計に思う)なのだろうが、最長一致文字列が見つからなかったと
1367 まず、search_dict() で見つからなかった場合、matchlen は更新されない
1368 (matchpos は、pos になる)。そして、おそらく 2 度目の search_dict() の
1369 呼び出しが行われる。が、too_flag[] というので、判断できそうな気もする
1370 がこれはむしろハッシュのチェーンをたどりすぎるのを止めるためのフラグで
1373 2度目の search_dict()で、max の値が変わるのが鍵だろうか？。今回の場合、
1374 max は 256 から 2 になる。最長一致長として 2 が限界値になると、
1375 search_dict() の動作は変わるだろうか？いや、やはり変わらない。どうにも
1376 この関数だけでは見つかったか見つからなかったかという判断はできないよう
1377 だ。(本当はわかっているはずなのにその情報を直接外に持ち出していない)
1379 気持悪いがやはりこの関数の解析を終え、次に移る事にしよう。
1383 (H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
1385 (H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
1386 (H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
1388 っと予想した部分だ。今や match_insert() は、解析済みだからこれの真偽が
1389 わかるか？というとやっぱり、わからない。ただ、
1390 matchlen > lastmatchlen
1391 というのは、辞書から文字列が見つかった場合の条件になりそうだから、やはり
1392 これは予想が逆だろうか？とにかく、比較的簡単そうな、(H.1) から見よう。
1394 if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
1396 encode_set.output(text[pos - 1], 0);
1400 どうも、文字 text[pos-1] を出力しているだけのように思える。文字の出力
1401 は、slide 辞書法では「辞書から見つからなかった場合」を意味するから、や
1402 はり最初の予想はあってそうなのだが・・・仕方ないので、output()の処理を
1403 覗いて見よう。これは、lh5, 6, 7 の場合、huf.c:output_st1(c, p) である。
1404 現時点で処理の内容を見てもわけがわからないが、結論から言うと第一引数 c
1405 は、文字で、第二引数 p は、位置である。冒頭の decode 処理で、文字 c は
1406 長さも兼ねていると説明済みなので、(そして、text[pos-1] には現時点で文
1407 字そのものしか書かれていない)これはやはり文字を出力している処理だ。つ
1410 なぜ、pos-1 なのだろう？確かに Huffman coding に文字を渡すのはこれが初
1411 めてで、現在 pos の位置はバッファの1文字進んだ位置にある。pos-1 は出力
1412 しなければならないのは当然だ。ということは pos は常に「未出力文字の位
1415 次の count++ を見る。count はどうやらこの関数の変数ではないらしい、困っ
1416 た事に局所変数の名前っぽいがグローバル変数だ。これはよろしくない。ちょっ
1417 と grep しただけでは、他にどこでこの変数を使っているのかわからなかった。
1418 まあ、今 1 文字を渡した所なので、入力文字数なのだと仮定しておこう。こ
1419 の変数が大勢に影響を与える事はないだろうからこれ以上は見ないと言うのも
1422 # その後、dhuf.c:decode_p_dyn() でのみ count を使用している事がわかった。
1424 次は (H.2) である。これがまた難解なのだがゆっくり片付けよう。
1428 encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
1429 (lastmatchoffset) & (dicsiz-1) );
1432 while (--lastmatchlen > 0) {
1433 get_next(); insert();
1437 matchlen = THRESHOLD - 1;
1439 if (matchlen > remainder) matchlen = remainder;
1442 まず、output() に渡している引数は、それぞれ「長さ」と「位置」であろう
1443 ことは予想済みだ。さらに UCHAR_MAX{255} + 1 - THRESHOLD{3} だから
1445 長さ lastmatchlen + 253
1446 位置 lastmatchoffset & (dicsiz-1)
1448 となっている。冒頭の decode() の解析で、長さは 253 を足す事は確認済み
1449 だ(-lhs- の場合 254 を足すという動作が、encoding 部分では考慮され
1450 てないのは、-lhs- の encoding 機能がないからだ)。ところで、一致長
1451 lastmatchlen は 3 以上で初めて 255 を越えることができる。以前予想した、
1452 THRESHOLD の意味「最低限一致しなければならない長さ」はあっているらしい。
1454 もう一点、注意しなくてはならないのは、出力しているのが lastmatchlen と
1455 lastmatchoffset である。これらは、match_insert() のときには更新してい
1456 ない(last〜の更新は次のループの先頭 (E) で行われる)。先程 (H.1) のとき
1457 も書き出していたのは、text[pos-1] であった。pos 位置は一歩先読みした位
1458 置を指すらしい。このような処理を行う場合、最後に調整が必要なはずだ(で
1459 ないと最後の文字が出力されない)。その調整はどこで行われるのだろう？
1461 さて、後続の処理だが、<長さ、位置>のペアを出力した後は、
1465 while (--lastmatchlen > 0) {
1466 get_next(); insert();
1470 という処理を行っている。get_next() は、pos を進める処理、insert() は辞
1471 書に登録する処理だから、これは文字列を読み飛ばしている処理だ。確かに
1472 lastmatchlen 分の情報は出力済みだから、これは納得である。lastmatchlen
1473 を 1 余分に引いているのが謎だがこれは pos が一歩先に進んでいるからであ
1474 ろうと予想する。つまり、この後は pos の位置はまた「現在位置」に戻る。
1475 なるほど、先程調整が必要と書いたがここで行われているらしい。細部は不明
1476 だが少なくとも辞書に文字列が見つかった場合は最後まで出力されるようだ。
1481 matchlen = THRESHOLD - 1;
1483 if (matchlen > remainder) matchlen = remainder;
1485 せっかく pos が現在の位置に戻ったのに、get_next() でまた先読みされた。
1486 うーむ。そして、matchlen は初期化される。一致情報はすでに出力済みだか
1487 らこれはうなずける。そして、match_insert() が呼ばれる。この時点で再度
1488 辞書が検索される。pos はまた1文字進んでいるのだから、これは先程(初期状
1489 態)のmatch_insert() と大差ない処理だ。(その直後のif文は境界条件なので
1492 そうして、また次のループに移る。このとき続けざま get_next(),
1493 match_insert() が行われる。どうやら pos は次のループからは、 2 文字文
1496 # 後でわかった事だが、while (--lastmatchlen > 0) のループ回数を読み間
1497 # 違えた。例えば、lastmatchlen が 1 なら、この while ループ内では
1498 # get_next() は1回も呼ばれない。
1500 どうにもソースを見ただけで解読するには、このあたりが限界のようだ。どう
1501 しても細部がわからないし、事実が見えないから予想の積み重ねがたまって不
1504 実は、もう少しマメに図を起こして読み進んで行けばもっとわかることがあっ
1505 ただろうと思うのだが、それは面倒だし、間違える可能性がある(ここまでで
1506 何度か痛い思いをした)。以降は、いくつかのデータを実際に圧縮させその動
1507 きをデバッガで追うことで、これまでの解析結果を検証してみよう。
1509 ・・・っと、その前に、ここまでですべての関数を網羅してしまったと思って
1510 いたのだが、一つ忘れていたものがあった。update() だ。この関数は、
1511 get_next() で呼び出されていたのだが、以前は無視していた。先にここを見
1514 まず、get_next() を再掲する。
1516 static void get_next()
1519 if (++pos >= txtsiz - maxmatch) {
1522 hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
1525 remainder と pos を進めた後、pos が txtsiz - maxmatch に達してしまった
1526 場合(pos == 2 * 2^dicbit の場合)に呼び出されるようだ。つまり、以下の図
1527 の状態だ。これが、update() を呼び出す時の初期状態だ。
1529 ----------------------------------------------------------------------------
1531 dicsiz=2^dicbit 2*2^dicbit
1533 +-------------+-------------+-------------+-------------+---+
1535 +-------------+-------------+-------------+-------------+---+
1543 ----------------------------------------------------------------------------
1547 static void update()
1554 memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
1558 i = 0; j = dicsiz; m = txtsiz-dicsiz;
1560 text[i++] = text[j++];
1564 n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)],
1565 (unsigned)dicsiz, infile);
1568 encoded_origsize += n;
1571 for (i = 0; i < HSHSIZ; i++) {
1573 hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
1576 for (i = 0; i < dicsiz; i++) {
1578 prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
1582 先頭で、なぜか memmove() を for ループで書き換えている。なぜこのような
1583 ことを行っているのだろう。for ループを見てみてもやっていることは変わら
1584 ない。謎だが、とにかく、text[] の右半分(maxmatch 部分も含む) を左に移
1587 次に fread_crc() で、新たにファイルを読み込む。今度の読み込み位置は
1588 &text[txtsiz - dicsiz] で、長さは dicsiz である。当然、remainder も更
1589 新している。encoded_origsize は以前と同様無視。pos は dicsiz 分減らさ
1590 れている。これはつまり図示すると、以下の状態になると言う事だ
1592 ----------------------------------------------------------------------------
1594 dicsiz=2^dicbit 2*2^dicbit
1596 +-------------+-------------+---+---------+-------------+---+
1598 +-------------+-------------+---+---------+-------------+---+
1600 / maxmatch{256} maxmatch{256}
1603 <------------------------------->
1606 |------- 以前のデータ ---------|--- 新しいデータ ---------|
1608 ----------------------------------------------------------------------------
1610 以降、ファイルの読み込みは常にこの update()でしか行われない。pos は、
1611 初期状態と同じ位置なので、初期状態が再現されている。ここまでで、
1612 maxmatch の領域はなんだろうと思うが、おそらく先読みのためだろう。それ
1613 らしい処理は、match_insert() の冒頭にあった(が、現時点で詳細には触れて
1616 # maxmatch 分の余分な領域は、pos の位置から最大 maxmatch 長の文字列照
1617 # 合を行うために必要な領域。先読みとはまた見当外れなことを書いたものだ。
1618 # ちょっと考えればわかることなのに・・
1622 for (i = 0; i < HSHSIZ; i++) {
1624 hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
1627 for (i = 0; i < dicsiz; i++) {
1629 prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
1632 内容は、想像がつくので詳細は省略しよう。単に以前のデータが移動したので、
1633 ハッシュ値を更新しているだけだ。しかし、これはなかなか無駄な処理だ。
1635 以前、text[] は環状バッファだろうと予想したが予想がはずれたことがわかっ
1636 た。環状バッファにしていれば、このハッシュの書き換えは不要にできただろ
1638 # そのかわり、位置の大小比較が繁雑にならないので、これはこれで良いのか
1639 # もしれない。どちらが優れているかは実験してみなければわからないだろう。
1641 これで、一応は slide.c を網羅する事ができた。まだ不明な点は多いが、デ
1642 バッガで実際の処理を追いかければまたわかることがあるだろう。
1646 さて、デバッガでと以前は考えていたのだが、あきらめるのはまだ早い(元気
1647 が出たらしい)、そもそも最初に「デバッガを使わずにどこまで解読できるか」っ
1648 と冒頭に書いてたのにたった2回の通読でもうあきらめようとしていた。が、
1649 ここまで書いてきた本書を何度か読み返したが、まだまだ検討の余地はある。
1651 まず、match_insert() の処理でわからなかった部分を解読しよう。実は、こ
1652 れに関してはどうしてもわからず悩んでいたところ、Lha for UNIX のメンテ
1653 ナである岡本さんに教えてもらうことができた(ありがとうございます)その内
1654 容を確認しつつ match_insert() を見ることにする。
1656 まずは、復習だ。通常の状態に関しては match_insert() の解読は済んでいる。
1657 match_insert() は、text[pos] から始まる文字列を辞書から検索し、見つかっ
1658 た位置と一致長を matchpos, matchlen に設定する処理だ。そして、ついでに
1659 insert() で、text[pos] の位置をハッシュ配列に記録し、次回の検索に備え
1662 では、不明な部分はなんだったかというと too_flag[] まわりである。
1663 too_flag のフラグが立っていると。辞書検索の頼りとなるハッシュ値を変更
1664 している。この部分がまったく皆目検討がつかなかったのだ。これに関してソー
1665 スを読み進めよう。以下ソースを再掲する。
1667 static void match_insert()
1669 unsigned int scan_pos, scan_end, len;
1670 unsigned char *a, *b;
1671 unsigned int chain, off, h, max;
1673 max = maxmatch; /* MAXMATCH; */
1674 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
1678 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
1679 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1681 if (off == maxmatch - THRESHOLD) off = 0;
1685 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1686 while (scan_pos > scan_end) {
1689 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1691 a = text + scan_pos - off; b = text + pos;
1692 for (len = 0; len < max && *a++ == *b++; len++);
1695 if (len > matchlen) {
1696 matchpos = scan_pos - off;
1697 if ((matchlen = len) == max) {
1702 scan_pos = prev[scan_pos & (dicsiz - 1)];
1708 if (matchlen > off + 2 || off == 0)
1714 prev[pos & (dicsiz - 1)] = hash[hval];
1718 まず、too_flag[] は、最初すべての要素が 0 である。そして、新たにファイ
1719 ルを読むとき(update())も 0 に再初期化されるのだった。このフラグが立つ
1720 条件はというと、この match_insert() の中だけである。その処理は
1725 この部分だけだ。chain が LIMIT以上になったら h (これは検索対象のハッシュ
1726 値だ)に関して、フラグを立てる。chain は while ループ(これは文字列の照
1727 合を行う処理)のループ回数だ。h に関しての検索が LIMIT{256} 以上の場合
1728 に too_flag[h] のフラグが立っている。
1730 while ループは一致文字列の一致長が最長一致長に達するか、辞書を最後まで
1731 探索するまでループする。つまり、あるハッシュ h に関してそのチェーンが
1732 256 以上のものに関しては、too_flag[h] が 1 になっている。
1734 では、そのような h に関して、match_insert() がどのような処理になってい
1737 max = maxmatch; /* MAXMATCH; */
1738 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
1744 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
1745 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1747 if (off == maxmatch - THRESHOLD) off = 0;
1749 通常 off は、0 なのだが、too_flag[h] が 1 であるものに関しては値が変わ
1750 る。検索対象となる文字列 text[pos](のハッシュ値) hval に関して、
1751 too_flag[h] が立っていれば、(このハッシュのチェーンが 256 以上であるこ
1754 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1756 で、検索対象となるハッシュ値を変更している。このハッシュ値が示すのは元
1759 ----------------------------------------------------------------------------
1764 +-------------+--------+--------+
1765 text | | | | | | | |
1766 +-------------+--------+--------+
1770 ----------------------------------------------------------------------------
1772 元の検索対象文字列が図の a だとすると、これを図の b にしている。初期化
1773 部のループは、もしこの b のハッシュチェーンに関して too_flag[h] がさら
1774 に 1 であるならさらに 先の文字列をハッシュ値とするようになっている。
1775 (これは元の pos の 2 文字先を示す。図の c の部分だ) h は、pos+off から
1776 の3文字のハッシュ値を示すものと言う事だ。
1778 ただし、h があまりにも先の方を見るようなハメになれば(off が maxmatch -
1779 THRESHOLD) off は 0 に再設定されるが、このとき h はそのままだ。この意
1780 味はまだわからないが、バグなのではないかと想像している(h = hval に再設
1783 では off = 1 だとして本処理を見ることにしよう。外側の for ループに関し
1784 ては、while ループを2回実行するかどうかだけのものだった。なので、
1789 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1790 while (scan_pos > scan_end) {
1793 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1795 a = text + scan_pos - off; b = text + pos;
1796 for (len = 0; len < max && *a++ == *b++; len++);
1799 if (len > matchlen) {
1800 matchpos = scan_pos - off;
1801 if ((matchlen = len) == max) {
1806 scan_pos = prev[scan_pos & (dicsiz - 1)];
1812 scan_pos, scan_end に関しては検索開始位置と終了位置と言う事でもう良い
1813 だろう。で、最初の if の条件に着目する。
1815 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1819 ----------------------------------------------------------------------------
1822 |-- a ---| |--- b --|
1823 +---------------+--------+--------------------+--------+--------+
1824 text | | |x'| | | | |x | | | |
1825 +---------------+--------+--------------------+--------+--------+
1827 scan_pos pos pos+1(off=1)
1829 ----------------------------------------------------------------------------
1833 text[scan_pos + matchlen - off]
1835 matchlen は、match_insert() に入る直前に 2 に初期化されている(最初は)
1840 text[pos + matchlen]
1842 これは、図の x の位置だ。x' == x ならば本格的に照合を開始する。
1845 a = text + scan_pos - off; b = text + pos;
1846 for (len = 0; len < max && *a++ == *b++; len++);
1849 ここで比較しているのは、図の a と b だ。b は、off がどのような場合でも
1850 変わらないが、a は、off が大きければ大きい程左側を指す。off が例えば
1853 ----------------------------------------------------------------------------
1855 |-- a ---| |--- b --|-- c ---|
1856 +---------------+--------+--------------------+--------+--------+
1857 text | x'| | | | | | |x | | | |
1858 +---------------+--------+--------------------+--------+--------+
1860 scan_pos pos pos+3(off=3)
1862 ----------------------------------------------------------------------------
1864 結局比較しているのは、pos からの文字列のハッシュ値を求めた場合と何も変
1865 わらない。off でいくら先を見ようとも比較するのは pos の位置だ。なぜこ
1866 のようなことをするのだろうか？これは最初どうしてもわからなかったのだが、
1869 これは単に効率(速度)のためということだ。もし、図の b に関して照合文字
1870 列の候補があまりにも多い場合(too_flag[h]=1)、ハッシュのチェーンを何度
1871 もたどる事になるので効率が悪い。しかし、辞書検索のキーを何文字か進める
1872 事で、この可能性を減らす事ができる。少なくとも最悪の 256 よりはマシに
1873 なるようなものを選んでいる。そうして、この while ループのループ回数を
1874 減らしているのだ。どうせ探したいのは最長一致文字列なので先の方の文字列
1875 が一致しないと話にならないのだからこれは合理的だ。
1877 これで、外側の for ループも納得だ。これは while ループをある条件でやり
1880 if (matchlen > off + 2 || off == 0)
1883 最長一致長が見つかるか、あるいは off が 0 であればさっさとこの処理は終
1884 るのだが、もし off を進めて照合を行っていたとして、最長一致文字列が見
1891 という条件で照合をやり直す。これは元の文字列で照合をやり直すということ
1892 だからつまりは、最悪のハッシュチェーンを仕方ないから辿り直そうと言う事
1893 だ。さらに、pos から pos+off+3 までの文字列が、辞書から見つからなかっ
1894 たので、最大一致長を off + 2 として条件を緩めている(なぜこれが条件を緩
1895 める事になるかと言うと while ループは最大一致長の文字列が見つかったら
1898 ところで、match_insert() の先の処理は以下の書き換えを行うともう少し見
1901 o scan_beg という変数を用意し、これを scan_pos - off にする。
1902 o scan_end は、pos - dicsiz にする。
1903 o while 条件を while (scan_pos != NIL && scan_beg > scan_end) にする。
1907 unsigned int scan_pos = hash[h];
1908 int scan_beg = scan_pos - off;
1909 int scan_end = pos - dicsiz;
1912 while (scan_pos != NIL && scan_beg > scan_end) {
1915 if (text[scan_beg + matchlen] == text[pos + matchlen]) {
1917 unsigned char *a = &text[scan_beg];
1918 unsigned char *b = &text[pos];
1920 for (len = 0; len < max && *a++ == *b++; len++);
1923 if (len > matchlen) {
1924 matchpos = scan_beg;
1925 if ((matchlen = len) == max) {
1930 scan_pos = prev[scan_pos & (dicsiz - 1)];
1931 scan_beg = scan_pos - off;
1937 ----------------------------------------------------------------------------
1939 |-- a ---| |--- b --|
1940 +---------------+--------+--------------------+--------+--------+
1941 text | | x'| | | | | | |x | | | |
1942 +---------------+--------+--------------------+--------+--------+
1944 | scan_beg scan_pos pos pos+off
1950 |----------------- dicsiz ------------------|
1952 ----------------------------------------------------------------------------
1954 scan_beg, scan_end の範囲もわかりやすいし、hash[h] が NIL の場合の処理
1955 も明示的だ。この書き換えを行う場合、scan_beg が負の値になる可能性があ
1956 る。元もとの処理では scan_end 等の変数を unsigned にしているので、これ
1957 らを int にして while 条件で負の scan_beg をはじかなければならないこと
1958 に注意。そうすると、scan_pos != NIL は必要なくなるのだがわかりやすさを
1961 これで match_insert() の解読は終りだ。match_insert() の処理とは以下の
1964 ----------------------------------------------------------------------------
1965 match_insert() は、text[pos] から始まる文字列に一致する文字列を辞書
1966 から検索し、見つかった位置と一致長を matchpos, matchlen に設定する。
1968 もし、最長一致文字列が見つからなければ matchpos は、pos に設定され、
1969 matchlen は更新されない。(実は、matchpos = pos の情報は特に使われてない)
1971 見つかった場合、matchlen は呼び出し前の matchlen よりも大きくなる。
1972 (呼び出し前では matchlen の意味は最低限一致しなくてはならない文字列
1987 さらに、insert() と同様の処理で、pos の位置をハッシュ配列に記録し、
1988 次回の検索に備える。これはついでの処理。
1989 ----------------------------------------------------------------------------
1991 これを踏まえた上で処理内容を再読しよう。(E) 〜 (H) だ。
1994 lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
1998 get_next(); match_insert();
1999 if (matchlen > remainder) matchlen = remainder;
2002 if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
2004 encode_set.output(text[pos - 1], 0);
2008 (H) の条件とは何なのかを見る。この条件が真なら、文字列をそのまま出力す
2009 るのだが、素直に slide 辞書法の処理を考えればこの条件は「辞書から見つ
2010 からなかった場合」となる。が、実際にはもう少し複雑だ。
2013 if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
2015 matchlen は、pos の位置の文字列が見つかった辞書上の長さ
2016 lastmatchlen は、pos-1 の位置の文字列が見つかった辞書上の長さ
2018 であるとすると、この条件は、「pos の位置で見つかった長さが、pos-1 の位
2019 置で見つかった長さよりも長ければ」っとなる。
2021 これはつまり、pos-1 と pos のニ箇所に関して辞書を検索して、より長くマッ
2022 チする方を選ぼうとしているわけだ。matchlen の方が長いなら 1 つ前
2023 (pos-1)の文字はそのまま出力し、次のループに移る(もし、次の文字が
2024 さらに長くマッチするなら。またそのまま出力される)
2026 この条件で「見つからなかった場合」というのはどう表されているかを考える。
2027 もし、pos の文字列が辞書になければ pos - 1 の文字列は、どうすべきかと
2028 いうと「pos-1 の文字列が見つかってなければ。そのまま出力。辞書にあった
2029 なら <lastmatchlen, lastmatchoffset> のペアを出力」っとならなければな
2032 lastmatchlen は、初期状態では THRESHOLD - 1 であったので、見つからなかっ
2033 たという条件は (H) の右側の条件 lastmatchlen < THRESHOLD でまず表され
2036 では、例えば lastmatchlen が 5 であったとしよう。このとき (E) の処理で
2037 matchlen は lastmatchlen - 1 つまり、4 に設定される。そして、match_insert()
2038 で次の文字列がもし辞書から見つからなければ matchlen は更新されないので
2039 matchlen < lastmatchlen
2040 となる。このような条件(前回見つかり、今回見つからない)場合に限り、(H.2)
2041 の処理が実行されるようになっている。では、(H.2) の処理を追いかけよう。
2045 ----------------------------------------------------------------------------
2047 lastmatchlen lastmatchlen
2049 +---------------+--------------+--------------+--------------+--+
2050 text | | | | | | | | | | | | | |
2051 +---------------+--------------+--------------+--------------+--+
2053 matchpos pos-1 pos pos2
2055 |--------------------------|
2058 ----------------------------------------------------------------------------
2062 encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
2063 (lastmatchoffset) & (dicsiz-1) );
2066 while (--lastmatchlen > 0) {
2067 get_next(); insert();
2071 matchlen = THRESHOLD - 1;
2073 if (matchlen > remainder) matchlen = remainder;
2076 まず、<長さ, 位置> のペアを出力する。これはいいだろう。出力する「位置」
2077 は0 なら 1 文字前を表すので、実際のオフセット pos - 1 - matchpos より
2078 も 1 小さい値になっていることに注意しておこう。
2080 そして、lastmatchlen は 1 引かれる。この場合例えば 4 になる。したがっ
2081 て、次のループでは 3 文字 pos が先送りされる(4 ではない)。pos は既に 1
2082 文字先に進んでいるので、最初に 1 引くのはこのことを考慮している。while
2083 ループが終った後はpos の位置は実際に出力した文字列の最後の文字 pos2-1
2086 そして、get_next() でまた 1 文字先に送る。pos は図の pos2 の位置になる。
2087 そして、match_insert() で、この位置の文字列を照合する。matchlen は、
2088 THRESHOLD - 1 に初期化されるので pos2 の位置の文字列が辞書から見つから
2089 なければ matchlen は、THRESHOLD-1 だ。これは初期状態と同じ状態を示すの
2090 で、次のループの処理も想像がつく((H) の条件の右側 lastmatchlen < THRESHOLD
2091 が有効になる)。では、見つかった場合はというと、次のループでさらに先
2092 pos2+1 の照合結果と比較されるのでこの処理も想像がつく。
2094 最初、どうにもこの処理内容が理解できなかったのだが「現在の文字列と、次
2095 の文字列のそれぞれで辞書を検索し、より長く見つかった方を使う」という最
2096 適化を行っている事がわかってしまった後は解読は簡単だった。(実はこの事
2097 実も教えてもらった事だ。全然ダメじゃん)
2099 さて、これで一通りの解析は済んだわけだが、ここまでの解析内容を読み直し
2102 1. ハッシュ関数は最適なのか？特に HSHSIZ{2^15} は最適なのか？
2103 2. too_flag[] は、実際に照合を行いループがLIMITを越えた場合に
2104 設定される。しかし、ハッシュのチェーンを作る際にチェーンの
2105 個数をあらかじめ数えておけば一度の探索すらも行われず。より
2108 現状、1, 2 とも実施してみたところ特に速度の改善は見られなかった。特に
2109 1 は、微妙なところがありほとんどの書き換えは性能を悪くするだけだった。
2112 これは今後の課題としていずれまた検証しよう。そろそろ slide.c も飽きて
2116 bit 入出力ルーチン (crcio.c)
2117 ---------------------------
2119 これから Huffman 法の解読に移るのだが、その前準備として bit 入出力ルー
2120 チンの解読を行う。Huffman 法の実装では必ず bit 入出力処理が必要になる。
2121 LHa for UNIX ももちろん例外ではなく、Huffman 法の実装を解読するにあた
2122 りこの部分の処理内容ははっきりさせておいた方が良いと考えたのだ。
2124 LHa for UNIX version 1.14i では bit 入出力ルーチンは crcio.c で定義さ
2125 れている。(このようなファイル名に存在するのは意外な事だ。最近の LHa
2126 for UNIX では、私が bitio.c というファイルを設け、bit 入出力ルーチンは
2129 crcio.c のうち bit 入出力ルーチンは fillbuf(), getbits(), putcode(),
2130 putbits(), init_getbits(), init_putbits() の 6 関数だ。
2132 まず、初期化用の init_getbits(), init_putbits() を見よう。
2135 init_getbits( /* void */ )
2140 fillbuf(2 * CHAR_BIT);
2142 putc_euc_cache = EOF;
2147 init_putbits( /* void */ )
2149 bitcount = CHAR_BIT;
2151 getc_euc_cache = EOF;
2154 それぞれ bit 入力、bit 出力を行うための初期化処理だ。CHAR_BIT というの
2155 は 8 で、char 型の bit サイズを表しているらしい。詳細はわからないが初期
2156 状態はとにかくこれだ。ここで使用されている変数は、
2158 static unsigned char subbitbuf, bitcount;
2162 EXTERN unsigned short bitbuf;
2164 が、lha.h で定義されている(EUC なんたらは本質ではない無視しよう)。グロー
2165 バル変数と言うのは忌むべきものだが、とにかく使用されている変数と初期値
2166 を確認したので次に移ろう。init_getbits() で、早速 fillbuf() が呼ばれて
2170 fillbuf(n) /* Shift bitbuf n bits left, read n bits */
2174 while (n > bitcount) {
2177 bitbuf = (bitbuf << bitcount) + (subbitbuf >> (CHAR_BIT - bitcount));
2179 if (compsize != 0) {
2181 subbitbuf = (unsigned char) getc(infile);
2185 bitcount = CHAR_BIT;
2189 bitbuf = (bitbuf << n) + (subbitbuf >> (CHAR_BIT - n));
2199 であり、fillbuf の引数 n には 2 * CHAR_BIT が与えられたのだった。いき
2200 なり while 条件を満たすのでループ部の解析を行わなくてはならなくなるが、
2201 ひとまずこれを無視して最後の 3 行 (D) に着目する。条件は少ない方が良い
2206 bitbuf = (bitbuf << n) + (subbitbuf >> (CHAR_BIT - n));
2209 bitbuf << n, subbitbuf << n されているので、bitbuf, subbitbuf を n ビッ
2210 ト左にずらす処理のようだ。さらに bitbuf には、subbitbuf を n ビットず
2211 らしたときに溢れた部分を bitbuf にセットしている。っと、
2213 (subbitbuf >> (CHAR_BIT - n))
2215 の部分を軽く説明したが、図示して確認しておこう。
2217 subbitbuf は unsigned char なので 8 bit の変数だ。
2219 ----------------------------------------------------------------------------
2221 +--+--+--+--+--+--+--+--+
2223 +--+--+--+--+--+--+--+--+
2225 ----------------------------------------------------------------------------
2227 n が例えば 3 の場合、CHAR_BIT - n は、5 だから subbitbuf を 5 ビット右
2228 にずらした値を取っている。つまり、図の 7, 6, 5 ビット目が一番右に来る
2229 ようになっており、この値を bitbuf に足している。(C言語では、unsigned
2230 な変数を右にシフトすると上位ビットには 0 が入る)
2232 fillbuf() の後半 3 行(いや、後半2行か)は。結局 bitbuf と subbitbuf を
2233 一つの bitbuf とみなして n ビット左にずらしていることがわかる。
2235 ----------------------------------------------------------------------------
2238 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
2239 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2241 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2244 <-------------- bitcount ------------->
2246 ----------------------------------------------------------------------------
2248 このとき、当然図の x, y, z の部分(n = 3 は例としての値だ)が空く事になる。
2249 bitcount という変数が n 引かれていたが、これは bit バッファ全体の有効
2250 なビット数を表しているのではないかと予想しておく。すなわち図の状態なら
2251 21 だ。while ループは(関数名から)この空き部分を埋める処理なのではない
2252 かと適当に予想できる。では、while ループを見よう。もう一度初期値を確認
2261 であるから、bitバッファは空っぽだ。当然 fillbuf(2 * CHAR_BIT) されると
2262 while 条件を満たす。きっと 16 bit だけ bitバッファが補充されるはず(つ
2263 まり、bitbuf いっぱい、subbitbuf 空)だ。
2266 while (n > bitcount) {
2269 で、ビットバッファが保持する bit 数以上を要求されたので、ループに入る。
2270 n -= bitcount で、本当に足りない部分が何ビットなのかを得ている。ここで
2274 bitbuf = (bitbuf << bitcount) + (subbitbuf >> (CHAR_BIT - bitcount));
2276 これは先程も出て来た処理だ。ビットバッファ全体を bitcount 分左にずらし
2277 ている(ただし、まだ subbitbuf はずらされていない)。この時点で予想が少
2278 し覆された。8 - bitcount で subbitbuf をずらしているから bitcount は最
2279 大 8 の値しか持たないだろうということだ。どういうことか、考えてみる・・・
2283 if (compsize != 0) {
2285 subbitbuf = (unsigned char) getc(infile);
2289 bitcount = CHAR_BIT;
2291 compsize というのが出て来たが、この値がどうあろうとも subbitbuf は8 ビッ
2292 ト埋められ。bitcount は 8 に設定されている。わかった bitcount は、
2293 subbitbuf に保持する bit 数だ。図を訂正しよう。
2295 ----------------------------------------------------------------------------
2298 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
2299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2301 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2307 ----------------------------------------------------------------------------
2309 この図を踏まえてもう一度初期状態での処理内容を追いかける。
2311 まず、(A) で、subbitbuf は空なので、bitcount は 0 だ。要求した bit 数
2312 n{16} より小さいのでループに入る。n は 16 のままだ。
2314 (B) で、subbitbuf に残っている bit を bitbuf にずらしている。今はまだ
2315 空なのでbitbuf はここでもまだ空だ。
2317 (C) で、ファイルからデータを8 ビット読む(compsize は常に0ではないと考え
2318 る)。bitcount は 8 になる。この時点で bitバッファ全体は subbitbuf だけ
2321 次のループに移ろう。(A) で、subbitbuf はいっぱいであるが要求した n{16}
2322 よりは小さいので、まだループは続く。n はここで 8 になる。
2324 (B) で、subbitbuf に残っている bit (8 bit だ)を bitbuf にずらしている。
2325 今度は subbitbuf 全体が bitbuf に移っているのと同じだ。(つまり、bitbuf
2328 (C) で、また subbitbuf は 8 bit 補充される。
2330 (A) で、n{8} > bitcount{8} は偽なのでループが終る。
2332 (D) で、subbitbuf に残っている bit はすべて bitbuf に移る。bitbuf は 16
2333 bit いっぱいになる。bitcount は 0 だ。
2335 この処理結果から fillbuf(n) は、bitbuf に n ビット読み込む処理だと言え
2336 る。引数に指定できる n が最大 16 ビットであることにも気づいて良いだろ
2339 ここで、subbitbuf の用途に気づいた。ファイルからの読み込みが 8 ビット
2340 単位でしかできないので、それを補うための保存用バッファであろう。例えば
2341 1 ビットだけ bitbuf を fill したければ subbitbuf に 7 bit 残し、1 bit
2342 だけ bitbuf に設定される(確認してみればわかる)
2344 fillbuf() がわかったので、それを利用している getbits() の内容を確認し
2353 x = bitbuf >> (2 * CHAR_BIT - n);
2358 x = bitbuf >> (2 * CHAR_BIT - n);
2362 buf >> (sizeof(buf)*8 - n)
2364 を buf の上位 n ビットを得る式だとしてマクロにしても良いだろう。(が、
2365 良い名前が思い付かないのでそうはしない)。とにかく、bitbuf の上位 n ビット
2366 を下位 n ビットとして x に代入している。その後で、
2370 している。n bit を x に渡したので bitbuf から上位 n ビットを捨てて、n
2371 ビット補充する。ここで、bitbuf は常にいっぱいの状態になっていることが
2372 わかる。(ファイルの末尾付近の場合、正確に bitbuf に何ビット残っている
2373 かが判断できないが、種明かしをするとこのことは LHa の処理内容にとって
2374 はどうでもいいことだ。getbits() は decode 処理で使われるのだが、decode
2375 処理は何ビットの情報を decode する必要があるかを他の情報からあらかじめ
2378 次に移ろう今度は putcode() だ。put の場合まずは、init_putbits() で
2381 bitcount = CHAR_BIT;
2383 getc_euc_cache = EOF;
2385 getc_euc_cache は無視だ。bitcount と subbitbuf の値が設定され、bitbuf
2386 は利用されない。先程とは違い subbitbuf が空なのにbitcount が 8 なので、
2387 bitcount の使われ方が多少異なるようだ。get の場合は、bitcount は、
2388 subbitbuf に保持する bit 数だったが今度は subbitbuf の空き bit 数だろ
2391 そして、putcode(n, x) を見る。実はソースを見るとわかるのだが、もう一つ
2392 の出力ルーチン putbits() は、putcode() の呼び出しに書き換え可能だ。
2396 putbits(n, x) /* Write rightmost n bits of x */
2400 x <<= USHRT_BIT - n;
2404 っと書き換えられるのだ。なので、putcode() の内容を先に確認するわけだ。
2407 putcode(n, x) /* Write rightmost n bits of x */
2412 while (n >= bitcount) {
2415 subbitbuf += x >> (USHRT_BIT - bitcount);
2418 if (compsize < origsize) {
2419 if (fwrite(&subbitbuf, 1, 1, outfile) == 0) {
2420 /* fileerror(WTERR, outfile); */
2421 fatal_error("Write error in crcio.c(putcode)\n");
2429 bitcount = CHAR_BIT;
2432 subbitbuf += x >> (USHRT_BIT - bitcount);
2436 処理内容が fillbuf() のときと似ている。まずは、先程と同様に while 条件
2440 subbitbuf += x >> (USHRT_BIT - bitcount);
2443 この式はもう 4 度目だ。まず、x の上位 bitcount ビットを得て、subbitbuf
2444 に足している。bitcount は、先程 subbitbuf の空きであろうと予想したが、
2445 n 引かれているので、埋めた分空きが減っているわけだ。予想は当たっている
2446 だろう。この時点でこの関数が x の上位ビットを利用することがわかる。コ
2447 メントに rightmost n bits of x と書かれているが惑わされてはいけない。
2448 多くの場合、コメントはせいぜいヒントとしての情報でしかない。信用しては
2449 いけないものなのだ。(コメントはあまりデバッグされない。コメントが詳し
2450 ければ詳しい程コメントはエンバグしやすい。疑ってかかろう。これは本書に
2451 も言える。すべてを鵜のみにしてはいけないのだ)
2456 while (n >= bitcount) {
2459 subbitbuf の空きが n 以下であればループに入る。subbitbuf 一つではn ビッ
2460 ト全部は賄えないからループで小刻みに処理しようということだろう(もう全
2462 n から bitcount 引いているので、n ビットのうちこれから bitcount 分は
2463 処理されることをここでさっさと記録して次のループに備えている。
2466 subbitbuf += x >> (USHRT_BIT - bitcount);
2469 x の上位 bitcount ビットを subbitbuf に足している。subbitbuf の空きが
2470 これで埋まった。subbitbuf はもういっぱいだ。x を bitcount シフトするこ
2471 とで subbitbuf に渡した x の上位ビットを捨てている。
2474 if (compsize < origsize) {
2475 if (fwrite(&subbitbuf, 1, 1, outfile) == 0) {
2476 /* fileerror(WTERR, outfile); */
2477 fatal_error("Write error in crcio.c(putcode)\n");
2485 bitcount = CHAR_BIT;
2487 compsize は無視しても良い。処理の本質ではないからだが、すぐにわかるので
2489 if (compsize < origsize) {
2493 で、圧縮ファイルサイズが元のファイルサイズを上回ったときに
2494 処理を終るようになっている(unpackable = 1 して、他の箇所でこの変数を監視する。
2495 unpackable == 1 なら処理を中断する)
2497 とにかく (C) の時点では必ず subbitbuf がいっぱいになるので 1 バイトを
2498 ファイルに書き出している。その後、subbitbuf = 0, bitcount = 8 として
2499 subbitbuf を空けて次のループに備えている。
2501 もういいだろう。putcode() は、論理的には x のうち上位 n ビットを出力す
2502 る処理だ。引数 n の上限が x の最大ビットサイズ 16 になるのは説明するま
2505 putcode() は実装として、subbitbuf と x を一つに繋げて n bit 左にずらし
2506 ている処理だと考えても良い。そうして、subbitbuf がいっぱいになったらそ
2507 の都度(1 バイトずつ)ファイルに書き出すのだ。
2509 ----------------------------------------------------------------------------
2514 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
2515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2523 ----------------------------------------------------------------------------
2525 putbits() も見よう。先程 putcode() の呼び出しに書き換えたコードを見ると
2528 x <<= USHRT_BIT - n;
2531 最初の式で、x の下位 n ビットを x の上位 n ビットにしている。
2532 そうして、putcode() を呼び出しているので、putbits(n, x) は、x
2535 以上でビット入出力ルーチンは終りだ。出力に関して一つ捕捉しておくと
2536 putcode(), putbits() では最後の最後で subbitbuf に情報が残ったままファ
2537 イルに書き出されない状態になる。これを吐き出すために利用者は
2545 ----------------------------------------------------------------------------
2547 bitbuf から上位 n ビットを捨てて、下位 n ビットをファイルから読み込
2551 bitbuf の上位 n ビットを下位 n ビットとして返す。bitbuf は n ビット
2555 x の上位 n ビットをファイルに出力する。最後の出力時は putcode(7, 0)
2559 x の下位 n ビットをファイルに出力する。最後の出力時は putcode(7, 0)
2567 ----------------------------------------------------------------------------
2569 読み込みに関して、bitbuf のサイズが 16 ビットで常にその状態が保持され
2570 ているのは LHa にとって重要な事だ。decode 処理では直接 bitbuf を参照す
2577 LHa for UNIX では、静的 Huffman 法として、shuf.c、動的 Huffman 法とし
2578 て dhuf.c があるらしいが、これらに関しては触れない。LHa では、これらは
2579 過去の版のアーカイブを解凍できるように decode のみサポートしているよう
2580 だ。そこで、まずは -lh4-, -lh5-, -lh6-, -lh7- で利用されている huf.c
2583 ところで、本書では Huffman 法がどういったものかは予備知識として既に知っ
2584 ているものとするが、いちおう概要を簡単に説明しておこう。
2586 以下の内容のテキストファイルがあったとする。
2590 このテキストは 9 バイトあるわけだが、このファイルで使われている文字は3
2591 種類しかない、a, b, c だ。だからこのファイルだけに関して言えば 1 文字
2592 は 2 ビットあれば表現可能である。例えば各文字に対して以下のビットを
2600 先のテキストファイルの内容 abcabcaba は、18ビットあれば表現可能となる。
2602 さらに、出現頻度の高い文字を少ないビット数で表現し、まれにしか現れない
2603 文字を長いビット数で表すようにすればよりビット数を少なくできる。例えば
2610 であるとすると a は 4回、bは3回、cは2回現れるので、全体は 4 + 2*3 +
2611 2*2 = 14 ビットで表現できることになる。これが Huffman 法の圧縮原理であ
2612 る。このように Huffman 法では文字をビット単位で扱うためビット入出力ルー
2613 チンを先に解読したわけだ。また、符号化の際はあらかじめ各文字の出現頻度
2614 を求めておく必要があり、復号化の際はどのビット列がどの文字に対応するか
2617 文字毎にビット長のばらつきがあるような可変長符号には以下の条件がある。
2619 ある符号のビットパターンは、他の符号のビットパターンの開始にはなら
2622 というものだ。これを「語頭条件」と言うらしい。例えば、先の例では a に
2623 0 を割り当てたので他の文字は必ず 1 から始まるようになっている。この条
2624 件を満たさなければならない理由はちょっと考えればわかる。仮に以下の間違っ
2632 これだと、ビットパターン 010 が ab なのか ca なのか曖昧になるのがわか
2635 文字に対応する語頭条件を満たす(最適な)ビット列を求める方法、それがハフ
2636 マン法だ。ハフマン法ではハフマン木という木構造を構築するのだが、そのア
2639 まず、圧縮対象であるテキストに関して各文字の出現回数を数える。例えば
2640 abcabcaba というテキストでは、a は 4回、bは3回、cは2回なので、
2646 となる。次に、出現回数の低いもの同士を一つの節に束ねる。この節は 3+2=5
2653 以降さらに出現回数の低いもの同士を一つの節に束ねる操作を繰り返す。この
2662 ここで、木の左側が 0 右側が 1 であるとすると。a は根から左に1つ進むだ
2663 けなので 0。b は、右(1)→左(0) なので、10。c は右(1)→右(1) なので、11
2664 となる。実際の符号化の際は文字からビット列を求めるので葉から根にむかっ
2665 て逆順に辿ることになる。また、復号の際は入力のビット列に沿ってこの木を
2666 根から辿ることで対応する文字を求める(なので圧縮文にはこの木構造が一緒
2669 このようなハフマン木を作成する箇所があるかどうかを探してみたところ
2670 maketree.c:make_tree() が見つかった。これは「C言語による最新アルゴリズ
2671 ム辞典」(奥村晴彦著、技術評論社)に載っているものとほとんど同じだ。では、
2672 この関数の解読から始めよう(今回の解析はボトムアップ式に行うことにしよ
2673 うと思う。というのもデータ構造から攻めようにもグローバル変数がたくさん
2674 出て来るし、処理順に追っても正直よくわからなかったからだ)
2676 この関数のあるファイル maketree.c で使用しているデータ構造は以下だ。
2678 static short n, heapsize, heap[NC + 1];
2679 static unsigned short *freq, *sort;
2680 static unsigned char *len;
2681 static unsigned short len_cnt[17];
2686 make_tree(nparm, freqparm, lenparm, codeparm)
2687 /* make tree, calculate len[], return root */
2689 unsigned short freqparm[];
2690 unsigned char lenparm[];
2691 unsigned short codeparm[];
2693 short i, j, k, avail;
2703 for (i = 0; i < n; i++) {
2706 heap[++heapsize] = i;
2710 codeparm[heap[1]] = 0;
2714 for (i = heapsize / 2; i >= 1; i--)
2715 downheap(i); /* make priority queue */
2718 do { /* while queue has at least two entries */
2719 i = heap[1]; /* take out least-freq entry */
2722 heap[1] = heap[heapsize--];
2724 j = heap[1]; /* next least-freq entry */
2727 k = avail++; /* generate new node */
2728 freq[k] = freq[i] + freq[j];
2730 downheap(1); /* put into queue */
2733 } while (heapsize > 1);
2737 make_code(nparm, lenparm, codeparm);
2738 return k; /* return root */
2741 この関数の引数に、nparm, freqparm, lenparm, codeparm というのがある。
2742 これがなんなのかいきなりではわからないだろう。実は私にもわからない。今
2743 回の解析で特殊なのは、処理内容については私は(アルゴリズム辞典で)知って
2744 いることだ。強引に無視しても処理内容から想像がつくだろうことを期待して
2747 とりあえず、冒頭の初期化部分 (A) で
2755 としている。引数で受けた入力をこのファイルの static 変数にセットし、他
2756 のルーチンとデータ共有しているようだ。avail は後で説明しよう。
2761 for (i = 0; i < n; i++) {
2764 heap[++heapsize] = i;
2767 ここで、heap[] を初期化している。heapsize は、heap の要素数となる。こ
2768 の処理は優先待ち行列 heap[] を作る部分なのだが、なぜ優先待ち行列が必要
2769 なのかというと先の説明で Huffman 法のアルゴリズムに出現回数の少ない順
2770 に葉を節に束ねるという部分があった。優先待ち行列はこのためのものだ。と
2771 りあえず、heap[] の要素は圧縮する文字であるということだけを書いておく。
2772 詳細はすぐ後で出るだろう。freq[i] (すなわち引数 freqparm) は、文字 i
2773 の出現回数を表している。だから、n (nparm)は、符号化するモデル上の文字
2774 の種類の数を表していることになる。たとえば通常のファイルなら nparm は
2775 256 だろう。まあ、結局は freq[] の要素数だ。
2778 freqparm[0:nparm] 添字が文字で、その要素が出現回数
2780 注意すべきなのは heap[] の要素は 1 以降を使用していることだろう。
2785 codeparm[heap[1]] = 0;
2789 これは、heapsize が 0 か 1 の場合を表している。符号化する文字の種類が
2790 0 または 1 つしかない場合だ。heap[1] は、(B) で 0 に初期化していたので、
2791 codeparm[0] = 0 として、0 を返している。これは特殊な条件を示している。
2792 簡単に想像がつくことだが、出現する文字の種類が1種類しかない場合、ハフ
2793 マン木を作る必要がない。LHa ではこのような場合に特殊な構造あるいは方法
2797 for (i = heapsize / 2; i >= 1; i--)
2798 downheap(i); /* make priority queue */
2800 優先待ち行列 heap[] を構築する。downheap() がなんなのか、これがどういっ
2801 た処理なのかの詳細は省略しよう。アルゴリズム辞典の「ヒープソート」の項
2802 に詳しいが、heap[] は木構造を示しており、この木構造(2分木)には「親は子
2803 より優先順位が同じか高い」という規則だけがある。この木構造は、
2805 1. heap[n] の左の子は heap[2*n]、右の子は heap[2*n + 1]
2807 で、表現されており、このような半順序木 (partial ordered tree) には、以
2810 2. heap[n] の親は heap[n/2]
2811 3. heap[1.. heapsize/2] は節で、heap[heapsize/2 .. heapsize] は葉
2813 この heap[] が最初ばらばらに要素が格納されているとき、葉に近い節から順
2814 に downheap() という操作を行う((D)の処理)と、ヒープを構築できるように
2815 なっている。downheap(i) は、節 heap[i] とその子 heap[2*i], heap[2*i+1]
2816 で要素を比較し、子の優先順位の方が高ければ位置を交換する、という処理を
2817 葉に向かって繰り返す関数だ。以下、参考までに maketree.c:downheap() の
2822 /* priority queue; send i-th entry down heap */
2828 while ((j = 2 * i) <= heapsize) {
2829 if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
2831 if (freq[k] <= freq[heap[j]])
2839 とにかく (D) により、最も優先順位の高い(出現回数の少ない)要素が
2840 heap[1] に来るようになる。この優先待ち行列はなかなか面白い(と私は思っ
2841 た)のでいろいろと調べてみるのもよいだろう。
2847 do { /* while queue has at least two entries */
2848 i = heap[1]; /* take out least-freq entry */
2851 heap[1] = heap[heapsize--];
2853 j = heap[1]; /* next least-freq entry */
2856 k = avail++; /* generate new node */
2857 freq[k] = freq[i] + freq[j];
2859 downheap(1); /* put into queue */
2862 } while (heapsize > 1);
2866 i = heap[1]; /* take out least-freq entry */
2870 で、最も出現回数の少ない文字を取って来る。if の部分はひとまず無視しよう。
2872 heap[1] = heap[heapsize--];
2875 で、heap[] の最後尾の要素を先頭に持って来て downheap(1) を行っている。
2876 こうすると、ヒープが再構築され「親は子より優先順位が同じか高い」という
2877 条件をまた満たすようになる。heap[] の要素は1つ減っている。結局、ここま
2878 での処理は論理的には「優先待ち行列から優先度の高い要素を1つ取り出す」
2881 j = heap[1]; /* next least-freq entry */
2885 続けて、2番目に優先度の高い要素を取り出す。また、if は無視しておこう。
2887 k = avail++; /* generate new node */
2888 freq[k] = freq[i] + freq[j];
2890 downheap(1); /* put into queue */
2892 avail は最初 n (nparm)だった。freq[] は、文字の出現回数なので最初文字
2893 の種類数分(nparm)の要素しかないがハフマン木の節の出現回数(というか優先
2894 順位)を格納するために freq[] は、nparm * 2 - 1 の格納域が必要となるこ
2895 とがわかる。(葉が n 個ある 2 分木には、節が n - 1 個ある)
2897 ----------------------------------------------------------------------------
2899 +-----------------------+-----------------------+
2901 +-----------------------+-----------------------+
2902 0 nparm nparm * 2 - 1
2904 |-----------------------|-----------------------|
2905 文字(ハフマン木の葉) ハフマン木の節の優先順位
2914 a b c ... freq[0 .. 2]
2916 ----------------------------------------------------------------------------
2918 ここまでで、出現回数の低い2つの要素を取り出しその出現回数の和を
2919 freq[k] に設定することになる。出現回数の和は heap[] に再設定され、
2920 downheap(1) で、優先待ち行列をまた再構築する。これは「葉を束ね節を作る」
2921 というハフマン木の構築アルゴリズムの実装だ。新しく作成した節が k でそ
2922 の最大値が最終的に avail-1 である。
2929 で、ハフマン木を構造 left[]、right[] で作成する。
2931 この (E) を抽象度の高いコードで示してみよう。ハフマン木は
2937 make_huff(huff, node, left, right)
2938 で作成できるとする。また、優先順位つき待ち行列を heap とし、heap から
2939 要素を取り出す処理、要素を格納する処理をそれぞれ仮に
2940 n = delete_pqueue(heap)
2941 insert_pqueue(heap, n)
2946 left = delete_pqueue(heap);
2947 right = delete_pqueue(heap);
2950 freq[node] = freq[left] + freq[right];
2952 insert_pqueue(heap, freq[node]);
2954 make_huff(&huff, node, left, right);
2955 } while (heapsize > 1);
2957 こんなところだろうか。元の処理ではヒープからの要素の取り出しと挿入で無
2958 駄な処理を無くすために少し複雑になっている。(そしてデータ構造に依存し
2959 た処理になっている)。どちらがよりすぐれているかは微妙な所だ。私は多少
2960 の処理の無駄も目をつぶってよりわかりやすい方を優先するのが好きなのだが。
2963 ループを抜けた所で k (avail - 1) は、ハフマン木の根を表している。
2964 left[0:avail], right[0:avail] でハフマン木を表し、そのうち
2965 left[nparm...avail], right[nparm...avail] が節の子を示している。
2966 left[0...nparm], right[0...nparm] は使われないようだ。
2968 ----------------------------------------------------------------------------
2979 ----------------------------------------------------------------------------
2981 これで、ハフマン木の構築は終りなのだが、ハフマン法の符号化ではハフマン
2982 木の葉から根に向かって木を辿る必要があるはずなのに、left[]、right[] の
2983 構造では根から葉に向かってしか木を辿ることができないはずだ。これはどう
2984 いうことだろう？make_tree() ではまだ処理が続いている。
2989 make_code(nparm, lenparm, codeparm);
2990 return k; /* return root */
2992 どうやら、木構造の他にもなにやら構造を作成しているようだ。これは先程無
2993 視した if 文にも関連する。そしてこれは「アルゴリズム辞典」には載ってい
2994 ない部分だ。どうやら LHa なりの工夫があるようだ。
2996 まず、maketree.c:make_len(root) から見てみようと思うが、その前にこの関
2997 数は maketree.c:count_len(root) という関数を呼び出している。こちらから
3001 count_len(i) /* call with i = root */
3004 static unsigned char depth = 0;
3007 len_cnt[depth < 16 ? depth : 16]++;
3011 count_len(right[i]);
3016 この関数に渡される i は、最初ハフマン木の根を指す値だ。この関数の全体
3017 を見れば、i が節や葉を示すことはすぐわかる。最初の if 文に出てくる n
3018 は何かというとなんとこのファイル内の static 変数で、make_tree() の冒頭
3019 で nparm で初期化していた。先程は気にもとめなかったのだが、変数名の選
3020 び方がどうにもよろしくない。とにかく n は、nparm で、freqparm の最初の
3021 要素数で、文字の種類の数を表していたものだ。ここではハフマン木の節や葉
3022 となる i と比較していることから、i がハフマン木の節を示すか葉を示すか
3023 の判断に使用しているらしい。if 文の条件が真の場合(i < n)、i は葉である。
3024 偽の場合 i は節である。偽の場合は、depth を足して二つの子に対して再帰
3025 的にこの関数を呼び出している。で、結局この関数が何をしているかというと、
3026 先ほど構築したハフマン木に関して、ある深さの葉の数を数えているようだ。
3028 len_cnt[1] は、深さ 1 (根の子)の葉の数で 0 〜 2 の値になる。len_cnt[2]
3029 は、深さ 2 (根の孫)の葉の数で 0 〜 4 の値を持つだろう。そして、深さ 16
3030 以上の層に関しては len_cnt[16] にすべて計上されるようだ。とにかくその
3031 ような処理だということでこの関数を終え、make_len() を見よう。
3041 for (i = 0; i <= 16; i++)
3046 for (i = 16; i > 0; i--) {
3047 cum += len_cnt[i] << (16 - i);
3049 #if (UINT_MAX != 0xffff)
3055 fprintf(stderr, "17");
3056 len_cnt[16] -= cum; /* always len_cnt[16] > cum */
3058 for (i = 15; i > 0; i--) {
3061 len_cnt[i + 1] += 2;
3069 for (i = 16; i > 0; i--) {
3078 ちょっと複雑だがゆっくり見ていこう。まず (A) の初期化部分は先ほどの
3079 count_len() を呼び出すだけのものなのでもうよいだろう。
3082 for (i = 0; i <= 16; i++)
3086 これで、len_cnt[1..16] にはハフマン木の各層の葉の数が計上される。続いて (B)
3090 for (i = 16; i > 0; i--) {
3091 cum += len_cnt[i] << (16 - i);
3093 #if (UINT_MAX != 0xffff)
3097 これは、どういうことだろう？len_cnt[] は short の配列だが、とにかく以
3098 下のような計算(len_cnt[] の要素を 1 ビットずらしながら足す)をしている。
3099 最後に int 型のサイズが 2 でない場合 0xffff で論理積をしているので 2バ
3100 イトの符号なし整数を結果として欲しいらしい。
3102 ----------------------------------------------------------------------------
3103 f e d c b a 9 8 7 6 5 4 3 2 1 0 bit
3104 len_cnt[16] |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x| (下位 16ビット)
3105 + len_cnt[15] |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|0| (下位 15ビット)
3106 + len_cnt[14] |x|x|x|x|x|x|x|x|x|x|x|x|x|x|0|0| (下位 14ビット)
3108 + len_cnt[ 2] |x|x|0|0|0|0|0|0|0|0|0|0|0|0|0|0| (下位 2 ビット)
3109 + len_cnt[ 1] |x|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0| (下位 1 ビット)
3110 & 0xffff |1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|
3111 ------------------------------------------------
3112 = cum x x x x x x x x x x x x x x x x
3113 ----------------------------------------------------------------------------
3115 ここで、len_cnt[] の各要素の値が各層の葉の数であることを考えると、各要
3120 -----------------------------------------
3121 len_cnt[16] 0.. 2^16以上 17ビット以上
3122 len_cnt[15] 0.. 2^15 16ビット
3123 len_cnt[14] 0.. 2^14 15ビット
3125 len_cnt[ 3] 0.. 2^3 4 ビット
3126 len_cnt[ 2] 0.. 2^2 3 ビット
3127 len_cnt[ 1] 0.. 2^1 2 ビット
3129 先の計算式では len_cnt[] の各要素で使用し得るビット数から 1 引いたビッ
3130 ト数が計算に使用されている。例えば根の子がすべて葉なら len_cnt[1] は、
3131 2 になり、2進で、00000000 00000010 だが、cum の計算にはこの下位 1 ビッ
3135 a b .. len_cnt[1] = 00000000 00000010
3138 cum = x0000000 00000000
3140 根の孫がすべて葉なら len_cnt[2] は、4 になり、2進で、00000000 00000100
3141 だが、cum の計算にはこの下位 2 ビットしか使用されない。
3143 / \ .. len_cnt[1] = 00000000 00000000
3145 a b c d .. len_cnt[2] = 00000000 00000100
3148 cum = xx000000 00000000
3150 このようにある層のすべてが葉であるようなバランスのよいハフマン木に
3151 対しては先の計算結果 cum は 0 になるらしい。
3155 a /\ .. len_cnt[1] = 00000000 00000001
3156 b c .. len_cnt[2] = 00000000 00000010
3159 cum = xx000000 00000000
3161 のような木に対しても計算結果はオーバーフローされ cum は 0 になる。
3164 a /\ .. len_cnt[1] = 00000000 00000001
3165 b /\ .. len_cnt[2] = 00000000 00000001
3166 c d .. len_cnt[3] = 00000000 00000010
3169 cum = xxx00000 00000000
3171 も同様に cum は 0 だ。結局 cum が 0 にならない木とはある節が 1 つの葉
3175 a /\ .. len_cnt[1] = 00000000 00000001
3176 b \ .. len_cnt[2] = 00000000 00000001
3177 d .. len_cnt[3] = 00000000 00000001
3180 cum = 11100000 00000000
3182 そして、ハフマン木の作り方からこのようなことは起こりえないのではないか
3185 (C) では、if (cum) で、この起こりえないハフマン木の場合になにか処理を
3186 行っている。まったく謎であるが、まず、この (C) を特殊条件とみなして先
3191 for (i = 16; i > 0; i--) {
3199 sort は何かというと、make_tree() の引数に渡された codeparm を指してい
3200 る。この配列の中には(ハフマン木を構築する際に設定されていたのだが)、出
3201 現頻度の低い順で平文の文字コードが入っている。make_tree() で、sort に
3207 のように条件判断があったので、sort[] にはハフマン木の節は入っていない。
3208 そしてハフマン木はその構築の仕方から出現頻度の低い文字は木のより深い場
3209 所に位置づけられている。これらのことから make_len()で求めようとしてい
3210 るものが何なのかがわかる。make_len() は、
3212 といった対応表を作成する処理だ。さらに言うとハフマン木の深さは文字を符
3214 lenparm[文字] = 符号語のビット数
3215 といった対応表を作成する処理であると言った方が正解だろう。
3216 len[] は、make_tree() の冒頭で、lenparm を指すように設定された変数なの
3219 では、謎の (C) を見よう。その前に cum != 0 は起こりえないと書いたがよ
3220 く考えたら len_cnt[16] だけは深さ16以上の葉すべての数を計上しているた
3221 め、どのような値もあり得る。つまり、この (C) の処理はハフマン木が深さ
3222 17 以上になったときに処理されるものだと言えそうだ。思い切って図示しよ
3223 う例えばこんな木は、(C)の処理対象となる。
3226 a /\ .. len_cnt[ 1] = 0000000000000001
3227 b /\ .. len_cnt[ 2] = 0000000000000001
3228 c /\ .. len_cnt[ 3] = 0000000000000001
3229 d /\ .. len_cnt[ 4] = 0000000000000001
3230 e /\ .. len_cnt[ 5] = 0000000000000001
3231 f /\ .. len_cnt[ 6] = 0000000000000001
3232 g /\ .. len_cnt[ 7] = 0000000000000001
3233 h /\ .. len_cnt[ 8] = 0000000000000001
3234 i /\ .. len_cnt[ 9] = 0000000000000001
3235 j /\ .. len_cnt[10] = 0000000000000001
3236 k /\ .. len_cnt[11] = 0000000000000001
3237 l /\ .. len_cnt[12] = 0000000000000001
3238 m /\ .. len_cnt[13] = 0000000000000001
3239 n /\ .. len_cnt[14] = 0000000000000001
3240 o /\ .. len_cnt[15] = 0000000000000001
3241 p /\ .. len_cnt[16] = 0000000000000011
3242 q r ||||||||||||||||
3244 cum = 0000000000000001
3246 このような木は例えば各文字が以下の出現頻度となるファイルを作成すると起
3247 こる(実際には、LHA の場合、slide 辞書法の処理もあるのでこれほど単純で
3251 ------------ ------------
3262 ところで、cum の値は何なのかというと、
3265 .. len_cnt[15] = 0000000000000001
3266 p /\ .. len_cnt[16] = 0000000000000100
3267 q /\ ||||||||||||||||
3268 r s vvvvvvvvvvvvvvvv
3269 cum = 0000000000000010
3273 .. len_cnt[15] = 0000000000000001
3274 p /\ .. len_cnt[16] = 0000000000000101
3275 q /\ ||||||||||||||||
3276 r /\ vvvvvvvvvvvvvvvv
3277 s t cum = 0000000000000011
3279 この場合は cum = 3 だ。少なくともこの例では深さ 16 以上の葉の数 - 2に
3280 なるらしい(そうか、11111111 11111110 = -2 を足しているのだから当然だ)。
3287 fprintf(stderr, "17");
3288 len_cnt[16] -= cum; /* always len_cnt[16] > cum */
3290 for (i = 15; i > 0; i--) {
3293 len_cnt[i + 1] += 2;
3300 である。いきなり fprintf() しているところがすごい。デバッグ用の出力が
3301 残っているのだろう。LHa for UNIX で 17 という出力を見たことがある人は
3304 で・・・、結局この (C) の部分は見てもよくわからなかった。ここまで書い
3305 ておいてなんだが、気持ちよく無視することにした。
3307 では、make_tree() から呼び出される最後の関数、maketree.c:make_code()
3308 を見よう。make_code() は、make_tree() の(F) の部分で以下のように呼ばれ
3311 make_code(nparm, lenparm, codeparm);
3313 この引数のうち、lenparm[] は先ほどの make_len[] で値が作られたものだが、
3314 lenparm[文字] = 符号語のビット数
3315 という対応表だった。codeparm[] は、先ほども出たが make_tree() の中で設
3316 定されているものだった。出現頻度の低い順で平文の文字コードが入った配列
3320 make_code(n, len, code)
3322 unsigned char len[];
3323 unsigned short code[];
3325 unsigned short weight[17]; /* 0x10000ul >> bitlen */
3326 unsigned short start[17]; /* start code */
3327 unsigned short j, k;
3332 for (i = 1; i <= 16; i++) {
3334 j += (weight[i] = k) * len_cnt[i];
3337 for (i = 0; i < n; i++) {
3340 start[j] += weight[j];
3344 # 後で気がついたことだが、あらかじめ設定していた codeparm[] の内容はこ
3345 # こでは使用されない。つまり、codeparm[] は先程はワーク用のバッファと
3346 # して利用されていたが、ここでの codeparm[] は処理結果を表すという二つ
3347 # の役割がある。これは、領域を節約するための変数の使い回しだ。
3349 最初の for 文では、変数 i に対して、weight[i] が下のように設定される
3351 weight[i=1..16] = 2^(16-i)
3356 start[n] = start[n-1] + weight[n-1] * len_cnt[n-1] (n > 1)
3358 という漸化式だ。start[] の添字 i は、len_cnt[i](深さ i の葉の数)の添字
3359 でもあることから、ハフマン木の深さを表している。start が実際にどのよう
3360 な値を取るかと言うと、例えば len_cnt[i] の各要素が Li であった場合、
3362 i len_cnt[i] weight[i] start[i]
3363 --------------------------------------------
3366 3 L3 2^13 2^15 * L1 + 2^14 * L2
3367 4 L4 2^12 2^15 * L1 + 2^14 * L2 + 2^13 * L3
3369 こんな感じだ。これはいったい何だろうか？続く for 文を見てみよう。
3371 for (i = 0; i < n; i++) {
3374 start[j] += weight[j];
3377 ここでの i は、0...n の範囲であることから平文の文字を示す。紛らわしい
3378 ので、i は、c に書き換え、j を i にしよう。(これで、i は前の for 文の
3383 for (c = 0; c < n; c++) {
3386 start[i] += weight[i];
3389 i = len[c] は文字 c のビット長で、ハフマン木の深さを示す。
3390 code[c] には、start[i] が設定されるが、一度 start[i] が参照されると
3391 start[i] は、weight[i] を足した値が次回使われる。例えば、ある文字
3392 a, b, c がそれぞれ以下のハフマン木で表現されたとする。
3399 i len_cnt[i] weight[i] start[i]
3400 --------------------------------------------
3404 c len[c] i len_cnt[i] weight[i] code[c]
3405 ---------------------------------------------------
3408 c 2 2 2 2^14 2^15 + 2^14
3410 こんな感じになる。別のハフマン木の場合も見てみよう。
3417 i len_cnt[i] weight[i] start[i]
3418 --------------------------------------------
3423 c len[c] i len_cnt[i] weight[i] code[c]
3424 ---------------------------------------------------
3427 c 2 2 4 2^14 2^14 * 2
3428 d 2 2 4 2^14 2^14 * 3
3430 これで、ピント来ると凄いのだが code[c] には文字 c に対応する符号化した
3431 ビット列が設定されるようになっていることに気づくだろうか？つまりは、
3433 c len[c] i len_cnt[i] weight[i] code[c]
3434 -----------------------------------------------------------
3435 a 2 2 4 2^14 00000000 00000000
3436 b 2 2 4 2^14 01000000 00000000
3437 c 2 2 4 2^14 10000000 00000000
3438 d 2 2 4 2^14 11000000 00000000
3441 だ。以降、code[] (実際には codeparm) を利用することで表引きで文字 c に
3442 対応するハフマン符号を得ることができるようになっている(code[c]のうち上
3443 位 len[c] ビットだけを見る)。符号化の際に木を辿る必要はなく、高速な符号
3444 化が可能になる(と期待される。どの程度効果があるかはいずれ検証してみた
3445 い。そういえば、葉から根に向かって木を辿るための情報が必要なかったこと
3448 結局 make_tree(nparm, freqparm, lenparm, codeparm) は、lenparm[c] と
3449 codeparm[c] を作成する関数だったわけだ(ハフマン表とでも言うのだろう
3450 か？)。実は、このことは make_tree() を呼び出し、 codeparm を使用してい
3451 る箇所(huf.c)を見るまでまるでわからなかった。しかも、まだちゃんと理解
3454 ふと思ったのだが、上記の表作成は文字コード順に依存している(コードの若
3455 い方が左の子になる)が、木を作成する場合はそのようなことはなかったはず
3456 だ。ハフマン木を辿った場合と表を参照した場合とでは得られる符号語は異な
3457 るのではないだろうか？ということは圧縮文に埋め込まれるのは木ではなくこ
3458 の表の方だということも想像がつく。木の構造を表す left[]、right[] はグ
3459 ローバル変数だが、実際には make_tree() 内でしか使われないのかも知れな
3460 い(少なくとも符号化に関してはそのようだ。huf.c を眺めるとどうやら復号
3461 時は left[]、right[]は使われるらしい)。
3463 さらにふと思い付いた。謎の (C) のコードだが 深さ 17 以上の木が作成され
3464 た場合に木を再構築する処理だということがわかった。最初、len_cnt[] (あ
3465 る深さの葉の数) だけが、操作されていたからよくわからなかったのだ、
3470 fprintf(stderr, "17");
3471 len_cnt[16] -= cum; /* always len_cnt[16] > cum */
3473 for (i = 15; i > 0; i--) {
3476 len_cnt[i + 1] += 2;
3483 深さ i の葉の数を 1 つ減らして、その下の葉の数を 2 足している。
3484 これが、cum の数だけ繰り返される。例えば、前にも出た
3487 n /\ .. len_cnt[14] = 0000000000000001
3488 o /\ .. len_cnt[15] = 0000000000000001
3489 p /\ .. len_cnt[16] = 0000000000000011
3490 q r ||||||||||||||||
3492 cum = 0000000000000001
3494 の例では、最初に len_cnt[16] から cum {1} が引かれ、
3497 n /\ .. len_cnt[14] = 0000000000000001
3498 o /\ .. len_cnt[15] = 0000000000000001
3499 p / .. len_cnt[16] = 0000000000000010
3502 続いて、深さ 15 より上の葉のある節から 1 つ子を取り、
3505 n /\ .. len_cnt[14] = 0000000000000001
3506 /\ .. len_cnt[15] = 0000000000000000
3507 p / .. len_cnt[16] = 0000000000000010
3510 下の葉の数(この例では、len_cnt[16])を 2 足している。
3513 n / \ .. len_cnt[14] = 0000000000000001
3514 /\ /\ .. len_cnt[15] = 0000000000000000
3515 o r p / .. len_cnt[16] = 0000000000000100
3518 cum は、この例では 0 になるので、これで木の平滑化は終る。テキストだと
3519 ちょっと見にくいが、そういう処理ということで間違いないだろう。
3520 lenparm[] の値はこの後の (D) で、この木を元に計算されている。
3522 ところで、本当の所は以下のような文字の対応になる(表を作成するときに文
3523 字コード順になっているため)のだが、結果的に元の木から p を含む節を取り
3524 除き o の位置に挿入する処理になっている。なんだか面白い。
3527 n / \ .. len_cnt[14] = 0000000000000001
3528 /\ /\ .. len_cnt[15] = 0000000000000000
3529 o p q r .. len_cnt[16] = 0000000000000100
3531 文字から Huffman 符号が得られるようになったので、圧縮処理を行う道具は
3532 揃った。いよいよ Huffman 法による圧縮処理全般 (huf.c) を見ることにしよ
3535 まず huf.c で定義されているデータ構造から確認しよう。データ構造がわかっ
3536 てしまえばアルゴリズムの 90% はわかったも同然だ(誇張)。
3538 huf.c には以下の変数が定義されている。
3540 unsigned short left[2 * NC - 1], right[2 * NC - 1];
3541 unsigned char c_len[NC], pt_len[NPT];
3542 unsigned short c_freq[2 * NC - 1], c_table[4096], c_code[NC], p_freq[2 * NP - 1],
3543 pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
3545 static unsigned char *buf;
3546 static unsigned int bufsiz;
3547 static unsigned short blocksize;
3548 static unsigned short output_pos, output_mask;
3552 使用されている定数も確認する lha_macro.h だ。
3554 #define NP (MAX_DICBIT + 1)
3555 #define NT (USHRT_BIT + 3)
3556 #define PBIT 5 /* smallest integer such that (1 << PBIT) > * NP */
3557 #define TBIT 5 /* smallest integer such that (1 << TBIT) > * NT */
3558 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
3559 /* #if NT > NP #define NPT NT #else #define NPT NP #endif */
3561 #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */
3563 たくさんある。たくさんありすぎてくじけそうだが(事実、くじけた)、現時点
3564 でわかる変数もある。left[] や right[] は Huffman 木を構築するのに使用
3565 した変数だった。そこから NC は文字種の最大数であることがわかる。NC に
3566 MAXMATCH{256} 等の値が使用されているのは謎だが、現時点では無視しておこ
3569 c_freq[] や c_len[], p_freq[], pt_len[] も make_tree() で出て来た変数
3570 名に似ている。おそらく make_tree() に渡す変数だろう。確認してみたとこ
3571 ろ huf.c から make_tree() の呼び出しを行っている部分を抜き出すと、
3573 root = make_tree(NC, c_freq, c_len, c_code);
3574 root = make_tree(NT, t_freq, pt_len, pt_code);
3575 root = make_tree(np, p_freq, pt_len, pt_code);
3579 文字種の数 文字の出現回数 符号化した文字 文字に対応する
3581 -----------------------------------------------------------
3582 NC c_freq c_len c_code
3583 NT t_freq pt_len pt_code
3584 np p_freq pt_len pt_code
3586 という関係のようだ。どうやら c_code、pt_code という 2 種類の
3587 Huffman 符号表を使用するらしい。
3589 # あとでわかることだが実際は 3 種類の Huffman 符号表を作っており
3590 # pt_code は変数が使い回しされている。変数の使用領域を減らし
3593 その他の変数に関しても予想を立てたい所だが、もうくじけたので、処理内容
3596 slide 辞書法の解読で Huffman 法に関連した処理の呼び出しがいくつかあっ
3603 encode_set.encode_start()
3604 encode_set.output(c, off)
3605 encode_set.encode_end()
3608 decode_set.decode_start()
3609 decode_set.decode_c()
3610 decode_set.decode_p()
3612 以上だ。lh4, 5, 6, 7 では、上記のそれぞれは、huf.c の以下の関数の呼び
3613 出しに対応している。これは、slide.c の冒頭部分で定義されている。
3616 encode_start() -> encode_start_st1()
3617 output() -> output_st1()
3618 encode_end() -> encode_end_st1()
3621 decode_start() -> decode_start_st1()
3622 decode_c() -> decode_c_st1()
3623 decode_p() -> decode_p_st1()
3625 このうちの圧縮処理にあたる部分 encode_start_st1(), output_st1(),
3626 encode_end_st1() を見ていこう。まずは、初期化処理である
3627 encode_start_st1() から、
3630 encode_start_st1( /* void */ )
3635 pbit = 4; /* lh4,5 etc. */
3638 pbit = 5; /* lh6,7 */
3645 for (i = 0; i < NC; i++)
3647 for (i = 0; i < np; i++)
3649 output_pos = output_mask = 0;
3654 dicbit (これは辞書の bit サイズだった)によって、np, pbit の値が変わる。
3655 dicbit の違いというのは LHa の encoding メソッドの違いだ。それぞれ以下
3658 method dicbit np pbit
3659 --------------------------
3665 np というのは、先程 make_tree() を呼び出している箇所の洗い出しで見かけ
3666 た変数だった。まだ、この関連はよくわからない。
3668 処理の後半では、文字の出現頻度を表す c_freq[]、p_freq[] の初期化を
3675 という初出の変数も 0 に初期化している。(buf は、buf[0] のみ初期化して
3676 いる) init_putbits() の呼び出しは bit 出力ルーチンの初期化処理だった。
3677 以降、putbits(), putcode() を使用できる。
3679 次に output_st1(c, p) を見る。slide.c でこの関数は以下のように使用され
3682 output_st1(c, 0) 文字 c を出力
3683 output_st1(len, off) <len, off> のペアを出力
3685 このことを踏まえた上で、処理内容を見てみよう。
3692 static unsigned short cpos;
3696 if (output_mask == 0) {
3697 output_mask = 1 << (CHAR_BIT - 1);
3698 if (output_pos >= bufsiz - 3 * CHAR_BIT) {
3704 cpos = output_pos++;
3708 buf[output_pos++] = (unsigned char) c;
3711 if (c >= (1 << CHAR_BIT)) {
3712 buf[cpos] |= output_mask;
3713 buf[output_pos++] = (unsigned char) (p >> CHAR_BIT);
3714 buf[output_pos++] = (unsigned char) p;
3724 (A) は、output_mask の値に応じて処理を行うようだ。初期化で output_mask
3725 は 0 だから (A) の処理は最初から実行されるが、ひとまず無視しよう。
3727 (B) は、buf に引数で渡された文字 c を格納し、c_freq[c] の値(文字の出現
3728 頻度)を足している。どうやら基本は渡された文字 c を延々と buf に格納し、
3729 後で圧縮を行う(おそらく (A) だろう)ようだ。
3731 この buf のサイズはと言うと、これは alloc_buf() で割り当てられていた。
3734 alloc_buf( /* void */ )
3736 bufsiz = 16 * 1024 *2; /* 65408U; */ /* t.okamoto */
3737 while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) {
3738 bufsiz = (bufsiz / 10) * 9;
3739 if (bufsiz < 4 * 1024)
3745 bufsiz が buf のサイズらしい。これはできるだけ大きく取るようにしている
3746 が、大きく取れなければそれはそれで良いようだ。
3748 さらに、(C) の処理を行うかどうかは、c >= (1 << CHAR_BIT) という条件で
3749 判断されている。この条件が真となる場合は何かと言うと c が「長さ」を表
3750 す場合だ。このとき引数 p で「位置」が渡されているのでこれも buf にセッ
3751 トしている。その具体的内容はというと、何やら cpos というこの関数内で
3752 static な変数が使用されている。よくわからないが文字 c や <len,off> の
3753 ペアは、buf 上で以下のように表されるらしい。
3755 ----------------------------------------------------------------------------
3759 output_st1(len, off)
3763 +-----+-----+-----+-----+-----+
3764 buf | c1 | c2 | len | off |
3765 +-----+-----+-----+-----+-----+
3767 ----------------------------------------------------------------------------
3778 は、出現頻度 p_freq[] を求める処理だが、p_freq は、off 値の出現頻度を
3779 表しているらしい。ここでの c は、p (off) の bit 長になっている。off の
3780 値は大きい(辞書サイズだから最大(lh7)で、64KB)ので、代わりに bit 長を利
3781 用しているといったところか。そういえば、np という変数があり、
3782 make_tree() の第一引数に渡されることから、これは、p_freq[] の要素数を
3783 表す。p_freq[] の要素数とは、<off> の bit 長の最大値+1なので、lh7 で、
3784 64KB。つまり 16 bit + 1 が np になる。
3786 ついでに言うと、「長さ」はそのまま c_freq[] で頻度が計上されていた。同
3787 じく make_tree() の第一引数に渡される NC の値が
3789 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
3791 なのは、そういうことだ(長さを考えなければ文字の最大値{255}+1となるとこ
3792 ろだが、長さの最大値が、256 + MAXMATCH - THRESHOLD だから上の式になっ
3793 ているのだろうと思う。ちょっとわかりにくいが)
3795 ここまでで、圧縮を行う処理は現われなかった。やはり (A) の部分が圧縮処
3800 if (output_mask == 0) {
3801 output_mask = 1 << (CHAR_BIT - 1);
3802 if (output_pos >= bufsiz - 3 * CHAR_BIT) {
3808 cpos = output_pos++;
3812 最初、output_mask は、0 なので if 条件を満たす。そして、output_mask は、
3813 (1 << (CHAR_BIT - 1)) つまり、128 になる。(A) の冒頭で、>>= 1 している
3814 ので、output_mask は、128, 64, 32, ..., 1, 128 という値を取るらしい。そ
3819 output_pos >= bufsiz - 3 * CHAR_BIT
3821 というのは、buf が bufsiz - 24 よりも大きくなったときの値だ。ひとまず
3822 無視しよう。そして、cpos = output_pos++ として、buf[cpos] = 0 にセット
3823 されている。どうやら、先にこちらを見るべきだったようだ。cpos の値
3824 と output_pos++ が (A) で行われていることを踏まえてもう一度 (B)、(C)
3825 の処理を見ると、buf は以下のように使用されているらしい。
3827 ----------------------------------------------------------------------------
3831 output_st1(len, off)
3836 +-----+-----+-----+-----+-----+-----+--
3837 buf | 32 | c1 | c2 | len | off | ...
3838 +-----+-----+-----+-----+-----+-----+--
3841 ----------------------------------------------------------------------------
3843 <len, off> のペアを出力するとき buf[cpos] には以下のような値が設定され
3846 buf[cpos] |= output_mask;
3848 もう少し注意深くこのあたりを考えよう。output_mask は、この関数が呼ばれ
3849 るたびに 128, 64, 32, ..., 1, 128, 64, ... という値になる。そして、buf
3850 は、呼ばれるたびに c (1バイト)、あるいは <len, off> (3バイト)の値が設
3851 定されるが、output_mask が 128 になったときは、余分に 1 バイト空きがで
3852 きる(これは、buf[cpos]で示される)。この空きには <len,off> が設定される
3853 たびにその時点の output_mask 値が設定されるようだ。(A) が呼ばれるとき
3854 と言うのは、一番最初の output_mask = 0 の場合を除けば、
3856 ----------------------------------------------------------------------------
3858 output_mask 128 64 32 16 8 4 2 1
3859 +----+----+----+----+----+----+----+----+----+----+----+----+----+
3860 buf | 40 | c1 | c2 |len | off | c4 |len | off | c6 | c7 | c8 |
3861 +----+----+----+----+----+----+----+----+----+----+----+----+----+
3867 ----------------------------------------------------------------------------
3869 このような状態になったときということだ。さらに、buf[cpos] には、
3870 <len,off> が格納されている位置を表している。この状態を 1 セグメントと呼
3871 ぶことにしよう。そしてこのセグメント単位に情報が buf に格納され、buf が
3872 いっぱいになったらこのセグメントの集まりを 1 ブロックとして (A) の処理
3875 if (output_pos >= bufsiz - 3 * CHAR_BIT) {
3882 のように send_block() が呼ばれるようになっているようだ。この if の条件
3883 で、3 * CHAR_BIT というのは <len, off> の格納バイト数を示している。
3884 (と思ったが、3 * CHAR_BIT ではビット数だ。一方、bufsiz はバイト数だ。
3885 計算に使用している単位が違う。何やらバグっぽい雰囲気があるが、バグだと
3886 してもバッファをちょっとだけ無駄にしているだけなので大したことはないの
3889 # どうやらバグではないらしい。3 * CHAR_BIT というのは、1 セグメントが
3890 # CHAR_BIT のスロット(8 つのスロット)を持ち、1 セグメント内のスロットが
3891 # すべて <len,off> (3 bytes)の場合、最大 3 bytes * 8 となることを示して
3893 # CHAR_BIT は、buf[cpos] のビット数を表している。
3895 # 実際のところ 1 セグメントは、buf[cpos] の領域 1 byte が先頭に必要なの
3899 # if (buf の残りサイズ < 最大サイズ) {
3901 # if (bufsiz - output_pos < 3 * CHAR_BIT + 1) {
3904 output_pos = 0 としていることからこの時点の buf の中身(セグメントの集ま
3905 り=1 ブロック)がすべて send_block() で圧縮されファイルに出力されるだろ
3908 この 1 ブロックに満たない状態でファイルの終りが来た場合、後処理
3909 encode_end_st1() で send_block() が呼ばれるであろうことも想像できる。
3911 encode_end_st1( /* void */ )
3915 putbits(CHAR_BIT - 1, 0); /* flush remaining bits */
3919 思った通りである。putbits(7, 0) というは、bitbuf に残った bit を吐き出す
3920 ためであることは、bit 入出力ルーチンの解読で確認済みだ。
3922 そういうわけで、send_block() が圧縮のメインルーチンである。
3923 send_block() の入力とは先に示した図の状態の buf だ。huf.c:send_block()
3927 send_block( /* void */ )
3929 unsigned char flags;
3930 unsigned short i, k, root, pos, size;
3933 root = make_tree(NC, c_freq, c_len, c_code);
3934 size = c_freq[root];
3939 root = make_tree(NT, t_freq, pt_len, pt_code);
3941 write_pt_len(NT, TBIT, 3);
3944 putbits(TBIT, root);
3951 putbits(CBIT, root);
3954 root = make_tree(np, p_freq, pt_len, pt_code);
3956 write_pt_len(np, pbit, -1);
3960 putbits(pbit, root);
3964 for (i = 0; i < size; i++) {
3965 if (i % CHAR_BIT == 0)
3969 if (flags & (1 << (CHAR_BIT - 1))) {
3970 encode_c(buf[pos++] + (1 << CHAR_BIT));
3971 k = buf[pos++] << CHAR_BIT;
3975 encode_c(buf[pos++]);
3980 for (i = 0; i < NC; i++)
3982 for (i = 0; i < np; i++)
3986 なかなか大きな関数であるが、それほど難しいことはない。まず、(A)
3989 root = make_tree(NC, c_freq, c_len, c_code);
3990 size = c_freq[root];
3993 make_tree() で Huffman 表 c_len[], c_code[] を構築する。戻り値の root
3994 は、Huffman 木の根を示し、c_freq[root] は、文字の出現回数の総和である
3995 から、size は、平文の総バイト数だ(size に <off> の分のサイズは含まれな
3996 い。c_freq[] が、<off> の出現頻度を数えなかったから)。ファイルには、こ
3997 の size がまず書き出されている(そういえば、この bit 入出力ルーチンを使
3998 用するとバイトオーダーに関して考慮する必要がなくなる)。
4000 ----------------------------------------------------------------------------
4008 ----------------------------------------------------------------------------
4014 root = make_tree(NT, t_freq, pt_len, pt_code);
4016 write_pt_len(NT, TBIT, 3);
4019 putbits(TBIT, root);
4026 putbits(CBIT, root);
4029 root が NC よりも大きい場合を判断しているが、ハフマン木の根は必ず NC よ
4030 りも大きい(make_tree() の avail の初期値を確認しよう)。では、この
4031 条件を満たさない場合と言うのは何かと言うと、同じく make_tree() を確認すると、
4034 codeparm[heap[1]] = 0;
4038 という例外条件があった。これは、圧縮する文字がない、あるいは 1 種類しか
4039 ない場合の処理だ。圧縮する文字がない場合に send_block() が呼ばれること
4040 はないだろうから、(B) の処理の else は 1 ブロック中に圧縮する文字が 1
4041 種類しかない場合の処理である(この 1 種類の文字とは、make_tree() の戻り
4042 値 root だ)。このとき以下のような出力になる。(TBIT{5}, CBIT{9} である)
4044 ----------------------------------------------------------------------------
4047 |--|--|----|----| TBIT: 5
4048 +--+--+----+----+ CBIT: 9
4052 ----------------------------------------------------------------------------
4054 これが、1 ブロックに 1 種類しか文字がない場合の出力だ(off の情報はまだ
4055 含まない)。(B)の if が真のときがどうなるかは複雑そうなので後で見ること
4060 root = make_tree(np, p_freq, pt_len, pt_code);
4062 write_pt_len(np, pbit, -1);
4066 putbits(pbit, root);
4069 p_freq[] を見ていることから今度は <off> の情報の Huffman 木を構築して
4070 いることがわかる。先程と同様に、<off> の値がすべて同じ場合は、else の
4071 条件になり、以下の出力が行われる。(pbit の値は、-lh7- の場合で、5 だ)
4073 ----------------------------------------------------------------------------
4075 pbit pbit method pbit
4076 |---------|---------| ----------
4077 +----+----+---------+ -lh4- 4
4078 | 0 | root | -lh5- 4
4079 +----+----+---------+ -lh6- 5
4082 ----------------------------------------------------------------------------
4084 ここまでに出力した情報が何を示すかわかるだろうか？Huffman 法の符号化処
4085 理は文字を bit 列に変換する。これを復号する場合は bit 列に対応する文字
4086 を知る必要がある。すなわち Huffman 木である(実際には Huffman 表)。図示
4087 したのは、Huffman 木を構築する必要がない(構築できない)場合の情報になる
4088 が、現在解読を飛ばしている処理は Huffman 表をファイルに出力している箇
4089 所であることは容易に想像がつく。ということは残りの (D) が本当の圧縮文
4094 for (i = 0; i < size; i++) {
4095 if (i % CHAR_BIT == 0)
4099 if (flags & (1 << (CHAR_BIT - 1))) {
4100 encode_c(buf[pos++] + (1 << CHAR_BIT));
4101 k = buf[pos++] << CHAR_BIT;
4105 encode_c(buf[pos++]);
4110 size 数分ループしている。size は、<off> を除いた buf の文字数を示して
4111 いると前に書いたが、どうやら <len, off> を 1 文字と数えたときの buf の
4112 文字数を示していると考えた方が良さそうだ。
4116 if (i % CHAR_BIT == 0)
4121 これが真になる条件は buf[pos] が buf[cpos] である場合だ(output_mask が
4122 128, 64, ..., 1 と 8 つの値を巡回していたことを思い出そう)。
4123 flags は、<len, off> の buf 上の位置を示す bit マスクになる。
4125 if (flags & (1 << (CHAR_BIT - 1))) {
4126 encode_c(buf[pos++] + (1 << CHAR_BIT));
4127 k = buf[pos++] << CHAR_BIT;
4131 encode_c(buf[pos++]);
4133 flags の 7 ビット目(128)が立っているとき buf[pos] は、<len, off> を指し、
4138 で、圧縮を行うようだ。len に 256 を足しているのは、buf[] に len を格納
4139 するとき(output_st1() の (B) の処理)に
4141 buf[output_pos++] = (unsigned char) c;
4143 のように最上位 bit を捨てていたからだ。len は常に 256 以上なので、256
4144 を足すことで元の len の値を圧縮ルーチンに渡している。
4150 で圧縮されている。encode_c() の処理内容は簡単なので見てみよう。
4156 putcode(c_len[c], c_code[c]);
4159 c_len[], c_code[] が文字 c に対応する Huffman 符号の bit 長と符号を示
4160 しているので、それをそのまま出力している。簡単だ。
4162 encode_p() はもう少し複雑だ。
4168 unsigned short c, q;
4176 putcode(pt_len[c], pt_code[c]);
4181 最初の while 文で、<off> の bit 長を求め、その bit 長の情報を
4182 Huffman 符号化している。その後、putbits() で、必要 bit 数だけ
4183 出力する。つまり、<off> は以下のように符号化される。
4185 ----------------------------------------------------------------------------
4188 |---- 16 bit -------|
4189 +----+----+----+----+
4190 off |0000 0000 0100 0000|
4191 +----+----+----+----+
4194 この圧縮文は以下(長さが 7 bit であるという情報(Huffman符号化)と値のペア)
4197 +-----------------+-------+
4198 | 7 のHuffman符号 |00 0000|
4199 +-----------------+-------+
4201 ----------------------------------------------------------------------------
4203 ここで、値を 6 bit しか出力しない(putbits() で c-1 を渡している)のは、
4204 7 bit 目が 1 であることが自明だからである。最初にビット長を出力している
4205 ので、値の情報は1 bit 削減できるわけだ。したがって、off=1 のときは bit
4208 最後の (E) は頻度表をクリアしているだけだ。
4211 for (i = 0; i < NC; i++)
4213 for (i = 0; i < np; i++)
4216 ここで、頻度表をクリアしているということは文字や位置の出現回数は 1 ブロック
4219 # 一方、c_freq や p_freq は unsigned short であるから(16 bit だとし
4220 # て)65535 までしか数えられない。さらに、{c,p}_freq には Huffman 木の構
4221 # 築の過程で出現回数の総和がセットされる場合があることから 1 ブロックに
4222 # は 65535 文字 + 65535 個の位置までしか格納できない。
4223 # いや、位置は必ず長さとセットであることから。位置の出現回数は文字の出
4224 # 現回数(これは長さの出現回数を含む)に含まれるため 65535 スロットまでし
4225 # か buf を持てないことになる。これは blocksize (16 bit)とも一致する。
4227 # buf の領域確保は以下のようになっていた。
4230 # alloc_buf( /* void */ )
4232 # bufsiz = 16 * 1024 *2; /* 65408U; */ /* t.okamoto */
4233 # while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) {
4234 # bufsiz = (bufsiz / 10) * 9;
4235 # if (bufsiz < 4 * 1024)
4241 # これから、bufsiz は、16 * 1024 *2 = 2^4 * 2^10 * 2 = 2^15 である。
4242 # 1 セグメントの最小サイズがバイト数で(1*CHAR_BIT+1)であるから
4243 # この領域に格納できる最大セグメント数は、
4244 # 2^15 / (1*CHAR_BIT+1)
4245 # であり、1 セグメントは 8 スロットあるから、最大スロット数は
4246 # 8 * 2^15 / (1*CHAR_BIT+1)
4248 # = 29127.1111111111
4249 # となる。これは、頻度表の上限(スロット数の上限)
4251 # よりも小さいので問題はないことになる。
4253 # なお、1 ブロックのサイズはこのバッファサイズにより決まるわけだが 1 ブ
4254 # ロックのサイズが大きければ大きいほどよいというわけではない。むしろ、
4255 # 文字の出現確率の変動に追随するためには小さい方がよいのだがそうすると
4256 # Huffman 木の格納回数が増えるので簡単には最適値は決まらない。
4258 以上で、圧縮処理全体の概要がわかった。後は無視していた Huffman 表を出
4264 root = make_tree(NT, t_freq, pt_len, pt_code);
4266 write_pt_len(NT, TBIT, 3);
4269 putbits(TBIT, root);
4273 ここでは、c_len[], c_code[] という Huffman 表を出力するだけのはずだが、
4274 さらに Huffman 表 pt_len[], pt_code[] の構築を行っている。これは、
4275 <off> の bit 長の Huffman 符号表でもあった変数だが、単に変数を使い回し
4276 ているだけだ。ここでの pt_len[], pt_code[] が何の符号表かは、
4277 count_t_freq() を見る必要がある。
4280 count_t_freq(/*void*/)
4282 short i, k, n, count;
4284 for (i = 0; i < NT; i++)
4287 while (n > 0 && c_len[n - 1] == 0)
4294 while (i < n && c_len[i] == 0) {
4300 else if (count <= 18)
4302 else if (count == 19) {
4313 最初に頻度表 t_freq[] を初期化する。続いて、
4316 while (n > 0 && c_len[n - 1] == 0)
4319 で、c_len[n] != 0 である最大の n を求めている。
4326 while (i < n && c_len[i] == 0) {
4332 else if (count <= 18)
4334 else if (count == 19) {
4344 c_len[i] は、文字 i の Huffman 符号での bit 長であった。この
4345 c_len[i] の値を以下の場合分けで t_freq[] に頻度計算している。
4346 count は、c_len[i] が連続で何回 0 であるかの数だ。
4348 c_len[i] count t_freq[]
4349 -------------------------------------------
4350 0 1 .. 2 t_freq[0] += count
4351 0 3 ..18 t_freq[1]++
4352 0 19 t_freq[0]++, t_freq[1]++
4354 0以外 t_freq[c_len[i]+2]++;
4356 これがどういう理屈であるかはよくわからないが、とにかく頻度計算を行う場
4357 合に t_freq[0], t_freq[1], t_freq[2] を特別扱いしている。そして、頻度
4358 計算の対象が c_len[] であることから (B) の処理は、c_len[] に関して
4359 Huffman 符号化を行う処理のようだ。
4361 そうして、make_tree() で、t_freq[] に関して Huffman 符号表を作成し、
4362 write_pt_len() で、この符号表(文字の Huffman 符号のビット長 c_len の
4363 Huffman 符号のビット長) pt_len[] を出力する。
4366 write_pt_len(n, nbit, i_special)
4373 while (n > 0 && pt_len[n - 1] == 0)
4382 putbits(k - 3, USHRT_MAX << 1);
4383 if (i == i_special) {
4384 while (i < 6 && pt_len[i] == 0)
4391 最初に pt_len[] の要素数を nbit 出力し、続けて符号 bit 長 pt_len[] の
4392 要素を出力している。nbit は、n を格納するのに必要な bit 数を表している
4393 ようだ。ここでは、n (NT{19}) を出力するのに TBIT{5} bit 必要であるとい
4396 pt_len[] を出力するときは、その値が 6 より大きいかどうかで形式を変えて
4397 出力している。6 以下であればそのまま 3 bit で出力し、7 bit 以上であれ
4398 ば、bit 数で表現するらしい。例えば pt_len[i] == 7 なら、1110 となる。
4399 最初の 3 bit は必ず 1 になり、最初の形式と区別がつくようになっている。
4401 さらに、i_special 番目の pt_len[i] を出力した後は、i_special ... 6 の範
4402 囲で pt_len[i] == 0 が続くことを 2 bit で、表現している。i_special は
4403 write_pt_len() の 3 番目の引数で、今回の場合は 3 だ。例えば
4404 pt_len[3..5] がすべて 0 なら pt_len[3..5] を出力せずに、i - 3 (= 3) を
4405 2 bit 出力する。つまり、11 が出力される。このようなことをしている意味は
4406 これまたよくわからない。ちょっと複雑なので図示してみた。
4408 ----------------------------------------------------------------------------
4409 < pt_len[] の出力フォーマット >
4412 +-------+-----------+-----------+-- --+-----------+
4413 | n | pt_len[0] | pt_len[1] | ... pt_len[n-1]|
4414 +-------+-----------+-----------+-- --+-----------+
4427 pt_len[i] |1 1 1 1 ... 1 0 |
4430 pt_len[i_special-1] の直後は 2 bit の情報が付加される。この値を x とする
4431 と、pt_len[i_special .. x + 2] の範囲で 0 が続くことを意味する。x が 0
4432 なら pt_len[i_special] は 0 ではない。
4434 ----------------------------------------------------------------------------
4436 最後に、write_c_len() で、Huffman 符号のビット長 c_len[] (の Huffman 符
4437 号表 pt_code[]) を出力する。
4440 write_c_len(/*void*/)
4442 short i, k, n, count;
4445 while (n > 0 && c_len[n - 1] == 0)
4453 while (i < n && c_len[i] == 0) {
4458 for (k = 0; k < count; k++)
4459 putcode(pt_len[0], pt_code[0]);
4461 else if (count <= 18) {
4462 putcode(pt_len[1], pt_code[1]);
4463 putbits(4, count - 3);
4465 else if (count == 19) {
4466 putcode(pt_len[0], pt_code[0]);
4467 putcode(pt_len[1], pt_code[1]);
4471 putcode(pt_len[2], pt_code[2]);
4472 putbits(CBIT, count - 20);
4476 putcode(pt_len[k + 2], pt_code[k + 2]);
4480 前に、頻度を数えたときと同様の条件で出力形式が変わっている。処理内容は
4481 簡単なので、以下の図を示すだけにする(理屈はよくわからない)。
4483 ----------------------------------------------------------------------------
4484 < c_len[] の出力フォーマット >
4487 +-------+-----------+-----------+-- --+-----------+
4488 | n | c_len[0] | c_len[1] | ... c_len[n-1]|
4489 +-------+-----------+-----------+-- --+-----------+
4506 <----------> <------>
4507 +------------+-------+
4508 | pt_code[1] |count-3|
4509 +------------+-------+
4513 pt_len[0] pt_len[1] 4 bit
4514 <----------> <----------> <------>
4515 +------------+------------+-------+
4516 | pt_code[0] | pt_code[1] |count-3|
4517 +------------+------------+-------+
4522 <----------> <------>
4523 +------------+--------+
4524 | pt_code[2] |count-20|
4525 +------------+--------+
4530 +-------------------+
4531 |pt_code[c_len[i]+2]|
4532 +-------------------+
4534 ----------------------------------------------------------------------------
4536 こうして、文字の Huffman 符号表は、pt_len[] と pt_code[](pt_code[] は
4537 つまり c_len[] の Huffman 符号)を出力することで表現される。c_code[] が
4538 出力されてないと思うかもしれないが、おそらく、decode 処理が c_len[] の値
4539 から計算して求めているのではないかと思われる。これは decode 処理の解読
4542 # 少し変なことを書いている。pt_code[] の出力は、c_len[] の Huffman 符号
4543 # を出力しているのであり、Huffman 木の情報として出力しているわけではな
4544 # い。つまり、c_code[] が出力されていないのと同様に pt_code[] も出力は
4547 この後、send_block() は、(C) で、<off> の Huffman 符号表を出力するのだ
4550 write_pt_len(np, pbit, -1);
4552 これは、先の pt_len[] の出力フォーマットと同じなので詳細ははしょろう。
4553 ただし、今度の pt_len[] の出力では write_pt_len() の第三引数 i_special
4554 が -1 で指定されていて、i_special 番目の pt_len[i_special..5] に関して
4555 特別扱いがなくなっているところが異なる。
4557 np や pbit の意味もこの時点でわかるので一応説明しておく。np, pbit そし
4558 て、LHA の圧縮 method との関係は以下の表の通りなのだが、np は、<off> の
4559 最大 bit 長 + 1 だ。<off> の最大 bit 長はすなわち dicbit なので、np は、
4560 dicbit + 1 である。-lh4- のときに dicbit + 2 なのが不思議だが、これは歴
4561 史的な理由だろうと思われる。pbit は、値 np を出力するのに必要な bit 数
4564 method dicbit np pbit
4565 --------------------------
4571 まとめると LHA における圧縮ファイルの構造は以下の連続であると言えるよ
4574 ----------------------------------------------------------------------------
4575 < LHA ファイルの構造(1 ブロック分) >
4582 +-----+--------------------+
4583 | len | pt_len | c_lenのハフマン符号表
4584 +-----+--------------------+
4588 +-------+------------------+
4589 | len | c_len | 文字と長さのハフマン符号表
4590 +-------+------------------+
4594 +---------+--------------------+
4595 | len | pt_len | 位置のハフマン符号表
4596 +---------+--------------------+
4598 (pbit=4bit(lh4,5) or 5bit(lh6,7))
4600 +---------------------+
4602 +---------------------+
4604 ----------------------------------------------------------------------------
4606 ここまでの解読では細部をかなりはしょったが、decode 処理を見ればわかる
4607 こともあるであろうことを期待している。以降、decode 処理の内容を処理の
4610 では、いよいよ decode 処理の解読に入る。これが終れば LHA の処理の全貌
4611 を一応は網羅したことになるので、気合いを入れて進めよう。
4613 decode 処理は以下の関数から成っている。これらは、slide.c の decode 関
4616 huf.c:decode_c_st1() /* 文字、長さの decode 処理 */
4617 huf.c:decode_p_st1() /* 位置の decode 処理 */
4618 huf.c:decode_start_st1() /* decode 処理の初期化 */
4620 (実際には、struct decode_option の decode_c,
4621 decode_p, decode_start を介して呼ばれる)
4623 decode_start_st1() は、以下の通りだ。これは encode_start_st1() のとき
4624 と特別変わる所はない。特に説明の必要はないだろう。
4627 decode_start_st1( /* void */ )
4634 np = 17; /* for -lh7- */
4645 では、decode_c_st1() を見よう。
4648 decode_c_st1( /*void*/ )
4650 unsigned short j, mask;
4652 if (blocksize == 0) {
4653 blocksize = getbits(16);
4654 read_pt_len(NT, TBIT, 3);
4656 read_pt_len(np, pbit, -1);
4659 j = c_table[bitbuf >> 4];
4664 mask = 1 << (16 - 1);
4672 fillbuf(c_len[j] - 12);
4679 if (blocksize == 0) {
4680 blocksize = getbits(16);
4681 read_pt_len(NT, TBIT, 3);
4683 read_pt_len(np, pbit, -1);
4686 と、いろいろとやっているがこの部分はすぐ想像がつく。< LHA ファイルの構
4687 造 > のハフマン符号表を読み込んでいるのだろう。そうして、一度読み込んだ
4688 後は後続の処理で blocksize 分読み込むまで decode を行うだけだ。
4691 j = c_table[bitbuf >> 4];
4693 decode 処理はハフマン符号表を表引きするだけなので単純だ。bitbuf >> 4
4694 は、bitbuf >> (16 - 12) と読み変えた方がわかりやすい。これは以前何度も
4695 出た形だが bitbuf の上位 12 bit を取り出している。そうしてその値(ハフ
4696 マン符号)を元に表引きした結果 j が復号した文字となる。なぜ 12 bit なのか
4697 はよくわからない後で考えよう。この後の部分で、
4703 mask = 1 << (16 - 1);
4711 fillbuf(c_len[j] - 12);
4715 j < NC の場合は c_len[j] でハフマン符号のビット長分を fillbuf() してい
4716 る。つまり先程表引きした 12 bit のうち c_len[j] bit が本当のハフマン符
4717 号なのだが、表引きの際に実際のビット長を気にする必要がないのが特徴的だ。
4719 else の部分は、j を求め直していることから、どうやら符号表からの表引き
4720 では復号できない場合を表しているらしい。この場合、表引きに使用した 12
4721 bit を捨て(fillbuf(12))、ハフマン木(left[], right[])を辿る事で、復号を
4722 行っている。この後、fillbuf(c_len[j] - 12) していることから、符号長は
4725 decode_c_st1() が decode する圧縮文の構造は図で表すと以下のようになる
4727 ----------------------------------------------------------------------------
4729 j < NC の場合 (c_len[j] < 12 の場合)
4733 +--------------+----------
4735 +--------------+----------
4737 j >= NC の場合 (c_len[j] > 12 の場合)
4739 <------------ c_len[j] --------->
4741 +------------------+--------------+--------
4742 圧縮文 | root | ハフマン符号 |
4743 +------------------+--------------+--------
4747 ----------------------------------------------------------------------------
4749 はたして、圧縮処理のときにこのような構造を作った覚えはないのだがどうい
4750 うことだろう？課題を残しつつ今度は decode_p_st1() (位置の復号処理)を見
4754 decode_p_st1( /* void */ )
4756 unsigned short j, mask;
4758 j = pt_table[bitbuf >> (16 - 8)];
4763 mask = 1 << (16 - 1);
4771 fillbuf(pt_len[j] - 8);
4774 j = (1 << (j - 1)) + getbits(j - 1);
4778 先程と同じだ。今度は、bitbuf のうち 8 bit を使用して表引きを行い、
4779 j < np なら pt_len[j] を詰め、そうでなければハフマン木を辿っている。
4780 復号した j は位置を表す値の bit 長なので最後に
4782 j = (1 << (j - 1)) + getbits(j - 1);
4784 で、本当の位置の値を読んでいる(encode_p() がそういう処理だった事を思い
4787 decode_p_st1() が decode する圧縮文の構造は図で表すと以下のようになる
4789 ----------------------------------------------------------------------------
4791 j < np の場合 (pt_len[j] < 8 の場合)
4795 +--------------+----------
4797 +--------------+----------
4799 j >= np の場合 (pt_len[j] > 8 の場合)
4801 <----------- pt_len[j] --------->
4803 +------------------+--------------+----------+----------
4804 圧縮文 | root | ハフマン符号 | 位置の値 |
4805 +------------------+--------------+----------+----------
4809 ----------------------------------------------------------------------------
4811 以上が、decode 処理の概要だ。ここまでの処理は別にどうという事もないだ
4812 ろう。decode 処理のキモは、圧縮文に埋め込んだハフマン符号表の読み込み
4813 にある。blocksize == 0 のときに、decode_c_st1() で呼ばれる
4814 read_pt_len(), read_c_len() だ。これにより、decode 処理で使用するテーブル
4816 c_table[] ハフマン符号 -> 文字の変換テーブル
4817 c_len[] ハフマン符号 -> ハフマン符号のビット長の対応
4818 pt_table[] ハフマン符号 -> 位置のビット長の変換テーブル
4819 pt_len[] ハフマン符号 -> ハフマン符号のビット長の対応
4821 right[] ハフマン木(右のノード)
4823 が構築される。この部分の方が decode 処理本体よりややこしそうだ。
4826 if (blocksize == 0) {
4827 blocksize = getbits(16);
4828 read_pt_len(NT, TBIT, 3);
4830 read_pt_len(np, pbit, -1);
4833 最初は、read_pt_len(NT, TBIT, 3) から
4836 read_pt_len(nn, nbit, i_special)
4846 for (i = 0; i < nn; i++)
4848 for (i = 0; i < 256; i++)
4854 c = bitbuf >> (16 - 3);
4856 unsigned short mask = 1 << (16 - 4);
4857 while (mask & bitbuf) {
4862 fillbuf((c < 7) ? 3 : c - 3);
4864 if (i == i_special) {
4872 make_table(nn, pt_len, 8, pt_table);
4876 実際、大した事はない。< pt_len[] の出力フォーマット > にしたがって、
4877 pt_len[] を読み直しているだけだ。read_c_len() も見よう。
4880 read_c_len( /* void */ )
4887 for (i = 0; i < NC; i++)
4889 for (i = 0; i < 4096; i++)
4894 c = pt_table[bitbuf >> (16 - 8)];
4896 unsigned short mask = 1 << (16 - 9);
4912 c = getbits(CBIT) + 20;
4921 make_table(NC, c_len, 12, c_table);
4925 こちらも、< c_len[] の出力フォーマット > にしたがって、c_len[] を読み
4927 # このあたりになると解析がかなり雑になっている(当時疲れていたのだろう)。
4928 # 最終的には後述の「LHA ファイルの構造(まとめ)」にて、再度検討しなおし
4929 # ているのでそちらを見て欲しい。不明だった部分もここですべて明らかにし
4931 結局キモとなるのは、make_table() にあるらしい。この関数により、読み込ん
4932 だ pt_len[], c_len[] から pt_table[], c_table[] (そして、ハフマン木
4933 left[], right[])を構築しているのだろう。
4935 結局、decode 処理 read_c_len(), read_pt_len() を読んでもなぜこのような
4936 符号化を行っているのかよくわからなかった。何か統計的な根拠でもあるのだ
4937 ろうか？それとも LHA にとって歴史的な事情でもあるのか？これに関しては
4940 では、最後の関数 make_table() を解読しよう。これは、maketbl.c で定義さ
4944 make_table(nchar, bitlen, tablebits, table)
4946 unsigned char bitlen[];
4948 unsigned short table[];
4950 unsigned short count[17]; /* count of bitlen */
4951 unsigned short weight[17]; /* 0x10000ul >> bitlen */
4952 unsigned short start[17]; /* first code of bitlen */
4953 unsigned short total;
4955 int j, k, m, n, avail;
4962 for (i = 1; i <= 16; i++) {
4964 weight[i] = 1 << (16 - i);
4969 for (i = 0; i < nchar; i++)
4973 /* calculate first code */
4975 for (i = 1; i <= 16; i++) {
4977 total += weight[i] * count[i];
4979 if ((total & 0xffff) != 0)
4980 error("make_table()", "Bad table (5)\n");
4983 /* shift data for make table. */
4985 for (i = 1; i <= tablebits; i++) {
4992 j = start[tablebits + 1] >> m;
4995 for (i = j; i < k; i++)
4999 /* create table and tree */
5000 for (j = 0; j < nchar; j++) {
5004 l = start[k] + weight[k];
5005 if (k <= tablebits) {
5007 for (i = start[k]; i < l; i++)
5011 /* code not in table */
5012 p = &table[(i = start[k]) >> m];
5015 /* make tree (n length) */
5018 right[avail] = left[avail] = 0;
5039 for (i = 1; i <= 16; i++) {
5041 weight[i] = 1 << (16 - i);
5044 avail はおそらく maketree.c:make_tree() でそうであったように、木の節の
5045 初期値だろうと予想しておく。count[], weight[] も、maketree.c での
5046 len_cnt[] weight[] と同義だろう(すなわち、count[i] は、木の深さ i 番目
5051 for (i = 0; i < nchar; i++)
5054 count[] を求めている。bitlen[i] は、文字 i のハフマン符号での bit 長で
5055 あった。やはり count[] は予想通りだ。
5058 /* calculate first code */
5060 for (i = 1; i <= 16; i++) {
5062 total += weight[i] * count[i];
5064 if ((total & 0xffff) != 0)
5065 error("make_table()", "Bad table (5)\n");
5067 これは、maketree.c:make_code() の前半部分とまったく同じだ。これにより、
5068 深さ i に対して、以下の対応表ができる(これは前にも書いた。Li は、
5071 i count[i] weight[i] start[i]
5072 --------------------------------------------
5075 3 L3 2^13 2^15 * L1 + 2^14 * L2
5076 4 L4 2^12 2^15 * L1 + 2^14 * L2 + 2^13 * L3
5078 これが何を表すかと言うと深さ i の符号(つまり bit 長 i の符号)は、
5079 start[i] から start[i+1]-1 の範囲の値を持つと言う事を意味する。再度、
5086 i count[i] weight[i] start[i]
5087 --------------------------------------------
5090 3 0 2^13 2^15 + 2^14 * 2
5092 これより、深さ 1 の葉 a は、start[1] .. start[2]-1 つまり、
5093 00000000 00000000 .. 01111111 11111111 の範囲の符号となる。
5094 深さ 2 の葉 b, c は、start[2] .. start[3]-1 つまり、
5095 10000000 00000000 ... 11111111 11111111 となる。
5098 /* shift data for make table. */
5100 for (i = 1; i <= tablebits; i++) {
5105 理由はわからないが、作成するテーブルを引数で渡された bit 数のテーブル
5106 になるよう写像している。つまり、値の範囲の初期値 start[] と weight[]
5107 を 16 - tablebits でシフトすることで、
5111 というテーブルの値は(tablebits が 12 であるとすると)、
5114 <--> (16 - tablebits{12}) = 4 bit シフト
5116 の値にする。encode するときは、16 bit のテーブルをそのまま使用していた
5117 にも関わらず decode のときにはテーブルの bit 数を減らしているのだ。まっ
5120 当然、encode で使用していたときのテーブルより情報量が減っているので、
5121 すべてをテーブル参照で decode することはできない。そこで、足りない部分
5122 は後の処理で木を作ることで補っているようだ。
5124 bit 数を減らす理由を考えてみる。まず表引きの考え方は、
5139 c_table[Huffman符号]=復号語
5141 を作成することで Huffman 符号化したビット列から復号語を得られるようにす
5142 る。そして、Huffman 符号から文字を得る必要があるので、c_table[] のイン
5143 デックスには、Huffman 符号が取りうる最大値を指定できなければならない。
5144 16 bit のHuffman 符号の最大値は 65535 であるから表引きに必要な変数は、
5146 unsigned short c_table[65535+1]; (unsigned short >= NC-1)
5148 となる。おそらく表の bit 数を減らしているのはこの大きなテーブルを作りた
5149 くないからではないかと思われる。c_table[] の要素数を最低限必要な数に抑
5152 0: c_table[ 0=0] = a
5153 10: c_table[10=2] = b
5154 11: c_table[11=3] = c
5156 この例の場合、c_table[1] が空であるようなテーブルを作成しなければならな
5157 い。ハッシュ表を作れば可能だがそうはせず、c_table[] の要素数を減らし、
5158 表引きで表せない部分は木で補っているということだ。
5162 unsigned short c_table[4095+1];
5164 となっており、12 ビット(2^12=4096)の Huffman 符号について表引きが可能と
5165 なっている。そして、復号語は、0...NC の範囲であるから、
5169 の場合は、木のルートノードを示し、その値から木を辿って復号できるように
5172 ----------------------------------------------------------------------------
5182 x y ... 階層:12 .' <- 表引きの結果 y が(>=NC)の場合、
5186 : > left[]/right[]で表現 (階層12がroot)
5188 ----------------------------------------------------------------------------
5190 階層 12 より下(13 以上の bit 数の Huffman 符号)の Huffman 木について
5191 left[], right[] で表しているようだ。
5193 上の例で、13 ビットの Huffman 符号で符号化される復号語 z については、
5194 y にその木のルートノードの値(y > NC)が割り当てられる。
5196 図から明らかだが、復号語そのものを指す 12 bit の符号(たとえば x)と、木
5197 のルートノードを指す 12 bit の符号(たとえば y)が同じ符号となることはな
5198 い。これは Huffman 符号が語頭条件を満たすからである。
5200 では、y に割り当てる値はどのように決まるかというとおそらく NC 以上の数
5201 値を連番か何かで割り当てているのではないかと思われる。これについてはこ
5204 なお、階層が深い Huffman 木とは、bit 長が長い符号であり、bit 長が長いと
5205 いうことは出現頻度が低いはずであるから、left[], right[] で木を辿る回数
5206 は少ないはずである。これは理にかなっている。
5208 あと、この木に必要なサイズはいくつであるかという点が気になる。これは、
5209 階層 13 以上のノードの数となるが、階層 n の二分木のノード(ここでは、葉
5210 および節をノードと呼ぶことにしている。「ノード」と「節」は本来同じ意味
5211 なのだがもう書いてしまったので仕方ない)の数が 2^(n+1) - 1 である(階層
5212 n の葉の数は 2^n で、節の数は 2^n-1)から、
5214 階層 12 のノードの数は、(2^(12+1)-1) = 8191
5215 階層 16 のノードの数は、(2^(16+1)-1) = 131071
5217 となり、その差は 131071 - 8191 = 122880 となる。単純に考えると、最悪の
5218 場合を想定して left[], right[] 合計で 122880 個の領域が必要であることに
5219 なる。そうすると領域を節約するという目的からは元も子もないこととなる。
5221 しかしよくよく考えるとその心配はないようだ。実際のところはハフマン木全
5222 体の葉の数は文字種の数 NC しか存在しないため(ハフマン木構築アルゴリズム
5223 及びエンコード処理を確認) 2*NC-1がハフマン木全体のノード数である。そし
5228 であることから、階層13以下のノード数は
5232 となり木のノード数の最大値は 2*(NC-12)-1 となる。さらに、この木の葉は
5233 left right の添え字にならないのでその分の領域は厳密には不要である。
5235 # 後の解析でわかることだが、left, right の添え字は NC 以上であるため
5236 # 0...NC の範囲の領域は(c_len については)使われない。また、変数 left
5237 # right はエンコード処理でハフマン木を作る際に使用した変数を流用してい
5238 # るため領域が足りないということはない。
5240 # 表引きを行わずに Huffman 木を完全に読み込むことを考えると、left,
5241 # right は、c_len については、
5243 # が使用され、位置(p_len)に対する Huffman 木の構築時には
5247 # c_len, p_len の Huffman 木は同時に存在するので、left, right ともに
5248 # 下図の領域が同時に使用されることになる。
5249 # (t_len は c_len の読み込みが完了した時点で不要となるため、この図には
5252 # 0 np 2*np-1 NC 2*NC-1
5253 # +---------+-------+----------+------------------------------+
5254 # |未使用域 |使用域 | 未使用域 | 使用域 |
5255 # +---------+-------+----------+------------------------------+
5260 # ソースを見てみても、このことはなかなか気がつきにくい。やはり、left,
5261 # right は各 Huffman 符号用に領域を割り当てた方がわかりやすいだろう。
5267 j = start[tablebits + 1] >> m;
5270 for (i = j; i < k; i++)
5273 table[] の初期値として 0 を設定している。
5275 Huffman 符号である j には、start[tablebits + 1] つまり、ビット長
5276 tablebits の最大の Huffman 符号+1が設定される。(繰り返しになるが、ビッ
5277 ト長 i の Huffman 符号は、start[i] から start[i+1]-1の範囲の符号である)
5278 m で右シフトしているのは、(D) では、tablebits までの start[i] しか 右
5281 k は、1 << tablebits から tablebits + 1 番目のビットが立った数値となる。
5282 この値はつまりは tablebits ビットの Huffman 符号の最大値 + 1 である。
5284 そして、start[j...k] の範囲について 0 を設定している。結局 tablebits の
5285 ビット長の範囲で割り当てられることがない Huffman 符号に対して 0 で初期
5287 割り当てられることがない Huffman 符号ということは 0 で初期化しているの
5288 はこの後の処理で木のノードになる予定の領域だと思われる。
5290 ちょっと疑問なのだが、if (j != 0) は必要なのだろうか？つまり、j = 0 と
5291 して、table[] の全要素について 0 で初期化しても何も問題はないのではない
5292 か？そしてそれなら make_table() に table[] のサイズ(sizeof)を渡し
5293 memset() にて 0 で初期化した方が(機械語の命令数が少なくなるので)速いの
5294 ではないだろうか？まあ、速さは良いとしても memset() の方がよりわかりや
5297 次に (F) の処理。少し大きいので下記の通り (F.1), (F.2) と細分化してみた。
5300 /* create table and tree */
5301 for (j = 0; j < nchar; j++) {
5306 l = start[k] + weight[k];
5307 if (k <= tablebits) {
5309 for (i = start[k]; i < l; i++)
5315 /* code not in table */
5316 p = &table[(i = start[k]) >> m];
5319 /* make tree (n length) */
5322 right[avail] = left[avail] = 0;
5336 この部分は一時変数の量が多い、i,j,k,l,m,n,p まで使われている。
5337 (しかも、前の処理までと変数の用途が違ってたりするので、複雑になっている)
5339 一旦、以下に整理してみた。(どの変数の添え字に使われているかなどからひと
5340 めで判断してみた結果である。そして、n, p についてはひとめではわからなかっ
5345 k: j の Huffman 符号のビット長(i のビット長)
5346 l: ビット長 k に対するHuffman 符号の終値 (start[k] <= Huffman(k) < l)
5347 m: Huffman 符号表をshiftするビット数
5351 これを踏まえて処理内容を見てみよう。まず、(F)全体について
5354 /* create table and tree */
5355 for (j = 0; j < nchar; j++) {
5365 復号文字 j = 0 ... nchar をループしている(j が復号文字であることは、
5366 bitlen[] の添え字であることからわかる)。
5368 そして、k = bitlen[j] が 0 であれば、(Huffman 符号化されていなければ)そ
5369 の文字はスキップしている。ここは、良いだろう。
5371 (F.1), (F.2) は、Huffman符号化されている文字 j について
5372 の処理となる。(最後の start[k] = l は後で考えよう)
5376 (F.1) k <= tablebits の場合、表引き可能な範囲なので、
5379 (F.2) k > tablebits の場合、表引き不可能な範囲なので、
5380 left[],right[]に復号文字をセット。
5382 といった処理をしていることが予想できる。では、(F.1) を見てみる。
5385 l = start[k] + weight[k];
5386 if (k <= tablebits) {
5388 for (i = start[k]; i < l; i++)
5392 ビット長 k <= tablebits の場合、ビット長 k が取りうる範囲の Huffman 符号
5394 ビット長 k が取りうる範囲の Huffman 符号とは
5396 start[k] <= Huffman符号 i < l
5398 である。例で示すと(簡便化のために、最大の Huffman 符号長を 2 とする)
5404 文字 a は、1 ビットで、00...10 の範囲(つまり、00 と 01)
5405 文字 b は、2 ビットで、10...11 の範囲(つまり、10)
5407 となる。ここで、文字 c については文字 b と同じ符号が割り当てられるかのように
5408 見えるが、実際は(F) のループの末尾に出てきた
5412 によって、ビット長 k に対する初期値 start[k] が変更されるため、その心配
5419 /* code not in table */
5420 p = &table[(i = start[k]) >> m];
5423 /* make tree (n length) */
5426 right[avail] = left[avail] = 0;
5438 ちょっと複雑だが難しいことはない。まず、
5440 p = &table[(i = start[k]) >> m];
5447 であり、i は Huffman 符号の初期値である。i が m で右シフトされているが、
5448 初期化部分の (D) では、tablebits までのインデックスに対する値
5449 (start[1..tablebits])しかシフトしておらず、この (F.2) の部分は k >
5450 tablebits であるから start[k] は m でシフトされていない Huffman 符号と
5453 p は、Huffman符号 i の table 上の位置を指す。後で、*p には木のルート位
5460 i を tablebits でシフトすることで、Huffman 符号 i は最上位の tablebits
5461 を除いた残りのビット部分になる。この残りのビット部分を木で表す。
5467 n は、書き換えた i のビット長を示す。木には深さ n の階層が作成されるの
5470 ----------------------------------------------------------------------------
5471 k: Huffman 符号 i のビット長
5474 tablebits (表引きで復号する部分)
5477 Huffman 符号 i| |xxxx|
5482 tablebits ビットシフトにより、書き換えた i は、xxxx の部分が最上位ビッ
5486 Huffman 符号 i|xxxx| |
5491 ----------------------------------------------------------------------------
5493 そうして、書き換えた i について、木を構築する。
5495 /* make tree (n length) */
5499 right[avail] = left[avail] = 0;
5512 (F.2.1) *p が 0 であれば、*p に avail として、新たな根を割り当てその右
5515 (F.2.2) Huffman 符号(の tablebits 以降のビット) i について最上位ビット
5516 が立っていれば右の子 right、ビットが立っていなければ左の子 left を作成
5519 ループによってビットパターンに沿って *p には、avail++ が順に割り当てられる。
5521 avail の初期値は nchar なので、*p >= nchar (c_table[] なら NC)である。
5523 この while ループを抜けた後に(F.2.3)にて
5527 が設定され、木の葉には、*p < nchar である値が設定されている。(そしてこ
5530 (F.2.1) で、if (*p == 0) としている理由は、
5537 と p が既に割り当てられており、その節に
5544 と右の子が追加される場合を想定している。この時点で (E) にて table を 0
5545 で初期化している理由がわかった。木の根が割り当てられているかどうかの判
5546 定が必要だから初期化で未割り当てにしておく必要があるということだ。もち
5547 ろん (E) で書いた通り table 全体を 0 で初期化しても問題はないしその方が
5550 ここまで、c_table[] を作成する場合だけを見てきたが、pt_table の場合も考
5551 え方は同じなので解析の必要はないだろう。
5553 ただ、この段階で表引きのビット数が c_table については 12 が p_table につ
5554 いては 8 が選ばれている理由が不明である。これは、想像だが pt_table が符号化する
5555 文字種は少ないので pt_table については 8 bit のテーブルを使っても表引きの確率が
5556 高いのではないだろうか。つまり、領域(pt_table のサイズ)の節約を優先しているので
5561 --------------------------
5563 以上で LHa for UNIX についての一通りの処理を見たことになる。ここからは
5564 実装については極力触れずに LHA ファイルの構造(圧縮形式)についてまとめて
5565 みよう。また、ここまで細部についてなぞのままとしていた部分があるのでこ
5568 ----------------------------------------------------------------------------
5569 < LHA ファイルの構造(1 ブロック分) >
5576 t_len: c_len のハフマン木 |
5577 +-----+--------------------+ | +-----+-----+
5578 | len | t_len | | | 0 |root |
5579 +-----+--------------------+ | +-----+-----+
5580 TBIT ?? bit | TBIT TBIT
5582 c_len: 文字と長さのハフマン木 |
5583 +-------+------------------+ | +-------+-------+
5584 | len | c_len | | | 0 | root |
5585 +-------+------------------+ | +-------+-------+
5586 CBIT ?? bit | CBIT CBIT
5588 p_len: 位置の(ビット長の)ハフマン木 |
5589 +-----+--------------------+ | +-----+-----+
5590 | len | p_len | | | 0 |root |
5591 +-----+--------------------+ | +-----+-----+
5594 圧縮文(文字と長さ、位置のビット長のハフマン符号と位置の値)
5595 +---------------------+
5597 +---------------------+
5600 method maxmatch dicsiz dicbit np(dicbit+1) pbit(np <= 2^pbit)
5601 ------------------------------------------------------------------
5602 -lh4- 256 2^12 12 14 (or 13?) 4 (14 <= 2^4)
5603 -lh5- 256 2^13 13 14 4 (14 <= 2^4)
5604 -lh6- 256 2^15 15 16 5 (16 <= 2^5)
5605 -lh7- 256 2^16 16 17 5 (17 <= 2^5)
5608 NC 256+maxmatch-threshold+1{510}
5614 ----------------------------------------------------------------------------
5616 # ソース上 pt_len と書いていた部分は、以降の説明のために p_len, t_len
5617 # と名前を変更している。変数 pt_len は単に領域の節約のために使い回され
5618 # ていただけでありいわば実装の都合であるからだ。
5620 上記は、LHA ファイルの構造(ヘッダを除く)を表したものである。LHA ファイ
5621 ルはヘッダと上記ファイル構造の集まりで 1 ファイルの圧縮ファイルとなり、
5622 それが複数集まってアーカイブを構成する。また、約束事としてアーカイブの
5623 最後は 1 バイトの 0 が付加されることとなっている。
5625 圧縮形式は method によってパラメータが変化する。ここでは、method
5626 lh4,5,6,7 の形式しか触れないので method の違いは slide 辞書の辞書サイズ
5627 の違いしかない。ただし、辞書のサイズの違いに連動して圧縮形式に影響を与
5628 える変数があるのでこれも上記にまとめている。(小文字はその変数、大文字は
5631 図中 t_len, c_len, p_len は、Huffman 木の情報を格納した領域を表し、「圧
5634 また、3 つのハフマン木の出力形式についてハフマン木が構築できない場合の
5635 形式を右側に併記した。これは、復号語が 1 種類しかない場合を示しており
5636 root がその復号語となる。例えば、c_len がこの形式で書かれていた場合は圧
5637 縮文を見ずに blocksize 分 root を出力すれば復号となる。なお、c_len がこ
5638 の形式の場合 c_len のハフマン木を示す t_len も右側の形式になるが、この
5639 ときの t_len の root の値は 0 にする事になっているようだ(ただ、復号処理
5642 圧縮文は、文字 c(0 .. 255)と <長さ len, 位置 off> を Huffman 木で符号化
5643 した Huffman 符号の並び(と位置の値)で表される。
5645 <len, off> は、slide 辞書法での圧縮結果であり、辞書上の off 位置の len
5646 文字をこの形式で表している。辞書とは、現在復号を開始している位置から辞
5649 位置 off は、0 が「1文字前」を現す。従って辞書サイズ dicsiz が 2^3 の場
5650 合を例に考えると位置の値が 2^3-1 の場合では、2^3 文字前を示すことになる。
5660 従って、off の値の範囲は 0 ... 2^dicbit である。
5662 長さ len の値は 256 の場合に文字列長 3 バイトを示す。つまり、len に対し
5663 て len-256+3 が実際の長さを示す。(ただし、-lzs- の場合は len-256+2 が実
5666 len の値が 256 から始まるのは、1 バイトの文字 c の範囲 0..255 と重なら
5667 ないようにするためである。(長さは、文字と同じ Huffman 木で符号化される)
5669 実際の長さが 3 から始まるのは、<len,off> の組が 4 バイトで表されるため、
5670 マッチ長として 2 文字以下を <len,off> の形式で表すと圧縮ではなく伸長に
5673 # 長さが 3 の場合も同じように思えるがなぜだろうか？
5674 # <len,off> はより正確には 3 バイトと 1 ビットである。というのも len が
5675 # 256 から始まるから len の情報は 9 ビット必要である。len が 256...510
5676 # の範囲なので 8 ビットのようにも思えるが文字 c との判別のための情報と
5677 # して 1 ビット余計に必要なのである。これは予想だが、当時 -lh5- の辞書
5678 # サイズであれば位置は 13 ビットしか使用しないため、<len,off> は 22 ビッ
5679 # トと見なせる。従って 3 バイトは <len,off> の形式にした方が良いと判断
5680 # したのではないだろうか？では、-lh7- の場合は、長さの最小値は 4 にした
5681 # 方が良いのだろうか？おそらく位置の値に 16 ビットすべて使用する確率が
5682 # 低く多くの場合は効果がないのではないかと思う。
5684 また、maxmatch{256}が最大マッチ長であり、このときの len の値は
5685 256+maxmatch-3{509=NC-1} である。
5688 ----------------------------------
5689 256..256+maxmatch-3 3..maxmatch
5691 これらを圧縮した形式「圧縮文」は Huffman 符号の連続(および位置の値。後
5692 述)である。圧縮文のサイズは上図の blocksize で表され、blocksize 数の文
5693 字数の情報が出力されている。ここで、「文字数」は <長さ, 位置> の組も 1
5694 文字としてカウントされる。文字なのか、<長さ, 位置> の組なのかの判別は、
5697 長さを示す。(そしてその直後に位置の Huffman 符号がある)
5702 となっている。そして、文字と長さの Huffman 符号は、Huffman 木の情報を示
5703 す c_len により復号され、位置の Huffman 符号は、p_len により復号される。
5705 位置の Huffman 符号は位置の情報の上位ビットが 0 である部分を除いたビッ
5706 ト長を符号化したものであり位置そのものの符号ではない。従って位置の符号
5709 +------------------------------+----------+
5710 | 位置のビット長の Huffman 符号| 位置の値 |
5712 +------------------------------+----------+
5714 と Huffman 符号に続いて実際の値を示すビット列が出力されている。例で示す
5717 ----------------------------------------------------------------------------
5722 |---- 16 bit -------|
5723 +----+----+----+----+
5724 off |0000 0000 0100 0000|
5725 +----+----+----+----+
5728 この圧縮文は以下(長さが 7 bit であるという情報(Huffman符号化)と値のペア)
5731 +-----------------+-------+
5732 | 7 のHuffman符号 |00 0000|
5733 +-----------------+-------+
5735 この例で 必要ビットである 7 bit 目は必ず 1 であるため値の部分は 6 bit
5740 |---- 16 bit -------|
5741 +----+----+----+----+
5742 off |0000 0000 0000 0001|
5743 +----+----+----+----+
5747 この圧縮文は以下(長さが 1 bit であるという情報のみ)
5755 |---- 16 bit -------|
5756 +----+----+----+----+
5757 off |0000 0000 0000 0000|
5758 +----+----+----+----+
5762 この圧縮文は以下(長さが 0 bit であるという情報は値が 0 と見なされる)
5767 ----------------------------------------------------------------------------
5769 # 位置を直接 Huffman 符号化しない理由は位置を指す値は slide 辞書上の任
5770 # 意の位置を指すためデータの範囲が広く(-lh7- の場合で 0 ... 2^16)
5771 # Huffman 符号化による圧縮の効果が期待できないためだと思われる。一方、
5772 # 位置情報は辞書上の比較的近い位置にマッチしやすいはずであるから Huffman
5773 # 符号化の対象であるビット長は小さい値に偏りやすいはずだ。(偏りがある
5774 # と Huffman 符号化の効果が高い)
5776 Huffman 木の情報をファイルに出力する際 p_len, c_len は、それぞれに適し
5777 た形式で圧縮して出力される。特に c_len は、さらに、t_len により
5778 Huffman 符号化することで圧縮を行う。
5780 ハフマン木 {p,c,t}_len はどの復号語がハフマン木のどの階層にあるかの情報
5781 により表されている。これだけの情報だと木を一意に表すことができないよう
5784 Huffman 木1 Huffman 木2
5791 Huffman 木1 と Huffman 木2 は枝の伸び方と葉に文字を振る順番の違いでしか
5792 ない。そこで、LHA では、以下の規則を設けることで、{p,c,t}_len の情報だ
5795 o 右の木を優先して作成する。(右の枝をビット 1 とする)
5796 o 同じ階層の復号語の割り当てはコード順に左から割り当てる。
5807 階層 1 に 1 個の葉(値が 1 である c_len[] が 1 個)
5808 階層 2 に 1 個の葉(値が 2 である c_len[] が 1 個)
5809 階層 3 に 2 個の葉(値が 3 である c_len[] が 2 個)
5811 があるので以下の Huffman 木の形に決まる(右の木を優先して作成する)。
5821 そして各階層毎に文字をコード順に割り当てると
5832 と一意に定まることとなる。(「階層毎のコード順」の意味が正確に伝わるよう
5835 なお、{p,c,t}_len の値はある文字の階層の位置を示すが、これはつまりある
5836 文字を Huffman 符号化したときの符号長(bit 長)を示していることになる。以
5837 降、{p,c,t}_len は添え字が復号語、値が符号長を表す配列であるものとして
5838 説明を行う。この配列のサイズは圧縮対象の文字集合の要素数であり、各要素
5839 は 0..16 の値を持つ。(LHA の Huffman 木のルールで木の階層は 16 までとなっ
5840 ている)そして、値 0 はその文字が平文に現れないことを示す。
5842 ----------------------------------------------------------------------------
5843 Huffman 木 要素数 値の範囲 要素数のビット長
5850 c_len[x]=0 の場合、文字 x は複合した結果に現れない
5851 要素数のビット長は要素数を表現するのに必要なビット
5853 ----------------------------------------------------------------------------
5855 では、Huffman 木の情報の出力形式について整理しよう。
5857 まず、p_len[] の出力フォーマットを下記に示す。
5859 ----------------------------------------------------------------------------
5860 < p_len[] の出力フォーマット >
5863 +-------+-----------+-----------+-- --+-----------+
5864 | n | p_len[0] | p_len[1] | ... p_len[n-1]|
5865 +-------+-----------+-----------+-- --+-----------+
5878 p_len[i] |1 1 1 1 ... 1 0 |
5881 p_len[n...np] は、0 となる。
5883 ----------------------------------------------------------------------------
5885 先にも書いた通り p_len は位置の値の必要ビット長を Huffman 符号化したと
5886 きの木の情報である。スライド辞書のサイズは dicsiz であり -lh7- の場合で
5887 16 bit で位置を指すことができるから、p_len は位置のビット長 0 .. 16 の
5888 17個(np個)の値を Huffman 符号化した結果(の符号長)である。
5890 そして p_len 自体の出力については、0 .. 6 の値(Huffman 符号長)について
5891 は 3 bit で、それ以上の値については 0 が現れるまでのビット数で表すよう
5894 なお p_len は np 個の固定長配列だが、出力形式としては先頭に pbit 幅
5895 の p_len の要素数を出力している。これはなぜかというと p_len の後方の値
5896 (p_len[n...np])が 0 である場合にその要素を出力しないで済むようにするた
5897 めである。これは他の Huffman 符号についても同様である。
5899 # なぜ、このような形式になっているか考えてみた。
5901 # p_len の値の範囲は、0 .. 16 であるから 1 要素は 6 bit で表現可能であり、
5902 # 単純に出力した場合を考えると 6 * 17 = 102 bit で表現可能である。
5904 # 一方、p_len の出力形式の場合、LHA の Huffman 木の階層は最大 16 階層であ
5905 # ることから、最悪すべての p_len[] についてビット数の形式(p_len[] >= 7)
5906 # が使われた場合 1 つの p_len[] に 16-3 bit * 17 = 221 bit 使うことにな
5907 # り最悪の使用領域は大きくなってしまうように思えてしまう。
5909 # しかし、実際にはそうはならない。というのも np が 17 であるから
5910 # Huffman 木の葉の数は最大でも 17 にしかならない。そして葉の数が np で
5911 # 最も Huffman 木が深くなるのは
5925 # となる場合で、この場合の p_len の出力ビット長は
5927 # 2*(16-3) + (15-3) + ... (7-3) + 6*3
5928 # = 2*13 + 12 + ... 4 + 18
5931 # である。単純に出力する場合に比べると 65 bit 増える。また、1 階層減ら
5949 # 4*(15-3) + (13-3) + ... (7-3) + 6*3
5950 # = 4*12 + 10 + ... 4 + 18
5953 # である。なお、この木の場合も葉は np 個ある。もう 1 階層減らしてみよう。
5971 # 4*(14-3) + 2*(13-3) + (11-3) + ... + (7-3) + 6*3
5972 # = 4*11 + 2*10 + 8 + ... 4 + 18
5978 # 4*(13-3) + 2*(12-3) + (10-3) + ... + (7-3) + 6*3
5979 # = 4*10 + 2*9 + 7 + ... + 4 + 18
5982 # 13 階層目で単純に出力するよりも小さくなった。感覚的には、あまり効果は
5983 # 期待できないように見える。これは恐らくは p_len については符号長が 6
5984 # 以下になる場合が多いのであろう(すべてが 6 以下であれば、3 * 17 = 51
5985 # bit であり 51 bit 削減できる)。階層が 6 である Huffman 木の葉の数は最
5986 # 大 2^6 {64} であるから NP{17} 種類の平文を格納する率が高いのであろう。
5988 続いて c_len[] の出力フォーマットを示す。
5990 ----------------------------------------------------------------------------
5991 < c_len[] の出力フォーマット >
5994 +-------+-----------+-----------+-- --+-----------+
5995 | n | c_len[0] | c_len[1] | ... c_len[n-1]|
5996 +-------+-----------+-----------+-- --+-----------+
6013 <----------> <---------->
6014 +------------+------------+
6015 | t_code[0] | t_code[0] |
6016 +------------+------------+
6021 <----------> <------>
6022 +------------+-------+
6023 | t_code[1] |count-3|
6024 +------------+-------+
6028 t_len[0] t_len[1] 4 bit
6029 <----------> <----------> <------>
6030 +------------+------------+-------+
6031 | t_code[0] | t_code[1] |count-3|
6032 +------------+------------+-------+
6037 <----------> <------>
6038 +------------+--------+
6039 | t_code[2] |count-20|
6040 +------------+--------+
6046 +-------------------+
6047 | t_code[c_len[i]+2]|
6048 +-------------------+
6050 c_len[n...NC] は、0 となる。
6052 ----------------------------------------------------------------------------
6054 c_len[] の値はある程度 0 が連続する場合が多いことが期待できる。
6055 c_len[i]=0 の場合というのはその文字(i)が平文に現れない場合を示す。
6056 ASCII テキストファイルの圧縮なら 0..127 の範囲のコードしか使われないた
6057 めそれ以外は 0 になるなどである。そして c_len を単純に出力することを考
6058 えたとき c_len[i]=0 である情報を多数出力することになり領域が無駄である
6059 (c_len は NC{255+256+2-3=510} 個の要素を持ちその中で未使用文字や未使用
6060 長が多数あることを想定している)。そこで 0 が連続して現れる特徴を生かし
6064 o c_len が連続で20個以上(20〜NC{510})
6066 をそれぞれ一つの文字と見なして Huffman 符号化することで c_len 自体の出
6067 力サイズを小さくしている。これは 0 の出現頻度を単純に Huffman 符号化す
6070 上図で t_code は c_len を Huffman 符号化したときの符号表を示しており
6072 o t_code[0] ... c_len[i] は 0 が 1 個
6073 o t_code[1] ... c_len[i] は 0 が 3〜18 個(続く4 ビットのビット列で
6075 o t_code[2] ... c_len[i] は 0 が 20〜NC-1個(続く CBIT ビットのビット
6077 o t_code[x] ... c_len[i]=x-2 (x>2)
6079 と復号することになる。c_len[i] = 0 が 2 個あるいは 19 個続く場合は
6082 t_code[0] と t_code[1] が 1 個ずつ
6086 最後に、t_len[] の出力フォーマットを示す。
6088 ----------------------------------------------------------------------------
6089 < t_len[] の出力フォーマット >
6093 +-------+----------+----------+----------+--+----------+- -+-----------+
6094 | n | t_len[0] | t_len[1] | t_len[2] | x|t_len[x+3]| ... | t_len[n-1]|
6095 +-------+----------+----------+----------+--+----------+- -+-----------+
6108 t_len[i] |1 1 1 1 ... 1 0 |
6111 t_len[2] の直後は 2 bit の情報が付加される。この値を x{0..3} とすると、
6112 t_len[3 .. x+2] の範囲で 0 が続くことを意味し、この 2 bit 以降は、
6113 t_len[x+3] が続くことになる。x が 0 の場合は、t_len[3] は 0 ではない。
6115 t_len[n...NT] は、0 となる。
6117 ----------------------------------------------------------------------------
6119 基本的な考えは p_len[] の場合と同じである(t_len[] の要素数 NT は 19)。
6120 ただし t_len[3..5] について特別扱いされている。
6122 まず、t_len[] と c_len[x] の値の対応を以下に整理し直す。
6124 t_len[0] c_len[x]=0 1 つを 1 文字とみなす
6125 t_len[1] c_len[x]=0 が 3〜18 個連続している塊を 1 文字とみなす
6126 t_len[2] c_len[x]=0 が 20〜NC{510} 個連続している塊を 1 文字とみなす
6132 t_len[18] c_len[x]=16
6134 t_len[3..5] の特別扱いについて考えると t_len[3..5] の範囲で 0 が連続す
6135 る場合に、2 ビットでそのことを表している。これはつまりこのような場合が
6136 多いのであろう。上で対応関係を示したとおり、t_len[3..5] が 0 である場合
6137 というのは、つまりビット長 c_len[x] が 1..3 の範囲の値を持たない場合を
6140 # c_len[x] が 1..3 の値を持つ場合というのは Huffman 木においてある 3 文字
6141 # の出現頻度が極端に多い場合を示す。このような場合はあまりないであると想
6155 以上で LHA ファイルの構造についてひととおり説明したことになる。ただし、
6156 復号処理を考える場合に注意事項がある。これはこの後で説明しよう。
6160 ----------------------
6162 2006年8月 LHA の復号処理にセキュリティバグ(CVE-2006-4335,4337,4338)が発
6163 見された。この問題は LHA の実装において符号化については当然あらゆる入力
6164 ファイルを想定した処理となっているが復号については圧縮ファイルが正しい
6165 構造、値で作成されていることしか想定せずに処理が作られていたためである。
6166 つまり、不正な圧縮ファイルが与えられた場合の動作が不定だったのだ。
6168 ここでは、LHA の復号において注意すべき点について考察する。また、ここま
6169 でに解読した LHa for UNIX ver.1.14i のソースはこのセキュリティバグが
6170 残っていたものなので、セキュリティバグの対策を行ったソースについても後
6173 以下、LHA の構造を再掲し、各復号処理で注意すべき点を確認しよう。
6174 以降の説明では注意点毎に (1) (2) のように番号を振っている。最終的に
6175 全チェックポイントをチェックするように修正したソースを載せ、この番号で
6178 ----------------------------------------------------------------------------
6179 < LHA ファイルの構造(1 ブロック分) >
6187 +-----------+-----------+-----------+
6188 | t_len | c_len | p_len |
6189 +-----------+-----------+-----------+
6191 圧縮文(文字と長さ、位置のビット長のハフマン符号と位置の値)
6192 +---------------------+
6194 +---------------------+
6196 ----------------------------------------------------------------------------
6199 blocksize の読み込みについてこの値は 1〜0xffff については正しいが 0 に
6200 なることはあり得ないので 0 の場合に不正と判断してもよいと思われる。
6203 「圧縮文」自体については、blocksize 数を頼りに読み込むので blocksize を
6204 越えて圧縮文が存在しても次の block として読まれるだけである。blocksize
6205 に満たない場合は、EOF を検知して早期に不正と判断するように処理した方が
6211 長さを示す。(そしてその直後に位置の Huffman 符号がある)
6216 であり、文字としては 0 .. 255 すべてについて正しい値なので問題はない。
6219 長さは 256 ... NC{256+maxmatch-3+1} の範囲の値を取るのでこれを超える値
6220 を返す場合は不正と判断してもよい。ただし、この判定自体は c_len を読み込
6221 み Huffman 木を構築するときに行うこともできる。(実際、実装では
6222 Huffman 木にこの範囲内の復号語しか割り当てないのでバグでない限りは発生
6225 位置については下図の通り位置のビット長の Huffman 符号と位置の値が書かれ
6228 +------------------------------+----------+
6229 | 位置のビット長の Huffman 符号| 位置の値 |
6230 +------------------------------+----------+
6233 位置の値としては 0 ... 2^dicbit の範囲の値を持つので Huffman 符号の復号
6234 結果が 0 ... np{dicbit+1} の範囲であれば位置の値部分についてチェックす
6235 る必要はない。従って、c_len と同じくハフマン木の構築の段階で不正な復号
6240 ----------------------------------------------------------------------------
6241 < t_len[] の出力フォーマット >
6245 +-------+----------+----------+----------+--+----------+- -+-----------+
6246 | n | t_len[0] | t_len[1] | t_len[2] | x|t_len[x+3]| ... | t_len[n-1]|
6247 +-------+----------+----------+----------+--+----------+- -+-----------+
6260 t_len[i] |1 1 1 1 ... 1 0 |
6263 t_len[2] の直後は 2 bit の情報が付加される。この値を x{0..3} とすると、
6264 t_len[3 .. x+2] の範囲で 0 が続くことを意味し、この 2 bit 以降は、
6265 t_len[x+3] が続くことになる。x が 0 の場合は、t_len[3] は 0 ではない。
6267 t_len[n...NT] は、0 となる。
6269 ----------------------------------------------------------------------------
6272 t_len の出力フォーマットの先頭 TBIT{5} は 0 ... 2^5{32} の範囲の値を格
6273 納できるが t_len の領域サイズは NT{19} なので 0..19 の範囲を超える場合
6277 また、t_len[i] >= 7 の場合の形式は bit 0 を検出するまでのビット長が値と
6278 なるが t_len[i] の値はハフマン符号長なので 0 .. 16 の範囲でなければなら
6279 ない。t_len[i] >= 7 の形式の具体的な値の対応は
6285 16: 1111 1111 1111 0
6287 となっているので、16 の場合のビット長(1 が 12 bit 続く)よりビット長が長
6288 い場合は不正である。(最大 12 ビットまでしか見ないとすることも考えられるが、
6289 LHA の圧縮処理は上の例のように 16 の場合でもビット 0 を出力するので、そ
6290 のような読み方をすると正常な圧縮文を復号できなくなる。)
6293 さらに、t_len を読み込んだ後に構築した Huffman 木は Huffman 木として整合
6295 たとえば、LHA における Huffman 木は以下の性質が守られなければならないは
6298 o t_len[x] <= 16 (LHA の Huffman 木の階層は 16 までである)
6300 o 各階層の葉の数は整合性が保たれなければならない。例えば、1 階層目の
6301 葉の数は最大 2 であり、このとき下位の階層の葉の数は 0 である。各節
6304 後で処理を解析する際にこの辺りを確認しよう。
6305 なお、1 点目については前述の通り t_len の読み込み時にチェックできる。
6306 2 点目については実装では非常にうまい方法でチェックしている。
6308 続いて c_len[] の出力フォーマットについて考える。
6310 ----------------------------------------------------------------------------
6311 < c_len[] の出力フォーマット >
6314 +-------+-----------+-----------+-- --+-----------+
6315 | n | c_len[0] | c_len[1] | ... c_len[n-1]|
6316 +-------+-----------+-----------+-- --+-----------+
6333 <----------> <---------->
6334 +------------+------------+
6335 | t_code[0] | t_code[0] |
6336 +------------+------------+
6341 <----------> <------>
6342 +------------+-------+
6343 | t_code[1] |count-3|
6344 +------------+-------+
6348 t_len[0] t_len[1] 4 bit
6349 <----------> <----------> <------>
6350 +------------+------------+-------+
6351 | t_code[0] | t_code[1] |count-3|
6352 +------------+------------+-------+
6357 <----------> <------>
6358 +------------+--------+
6359 | t_code[2] |count-20|
6360 +------------+--------+
6366 +-------------------+
6367 | t_code[c_len[i]+2]|
6368 +-------------------+
6370 c_len[n...NC] は、0 となる。
6372 ----------------------------------------------------------------------------
6375 c_len の出力フォーマットの先頭 CBIT{9} は 0 ... 2^9(512) の範囲の値を
6376 格納できるが c_len の領域サイズは NC{510} なので 0..510 の範囲を超える
6384 のそれぞれの形式において count の数だけ c_len[i] は 0 が続くがこれが
6385 c_len の*残り*サイズを越える場合も不正である。
6388 さらに、c_len[i] > 0 の場合の形式において、t_len[x] を復号した結果が
6389 c_len[i]{x}+2 の値でありc_len[i] の値はハフマン符号長なので 0 .. 16 の
6390 範囲でなければならない。これは、c_len, p_len と同じく t_len のハフマン
6391 木の構築の段階で不正な復号語を返さないようにしていればよい。
6394 もちろん、t_len のときと同様 c_len を読み込んだ後に構築した Huffman 木
6395 は Huffman 木として整合性が保たれなければならない。
6397 続いて p_len[] の出力フォーマットについて考える。
6399 ----------------------------------------------------------------------------
6400 < p_len[] の出力フォーマット >
6403 +-------+-----------+-----------+-- --+-----------+
6404 | n | p_len[0] | p_len[1] | ... p_len[n-1]|
6405 +-------+-----------+-----------+-- --+-----------+
6418 p_len[i] |1 1 1 1 ... 1 0 |
6421 p_len[n...np] は、0 となる。
6423 ----------------------------------------------------------------------------
6426 p_len の出力フォーマットの先頭 pbit{4 or 5} は 0 ... 2^4{16} or
6427 2^5{32} の範囲の値を格納できるが p_len の領域サイズは np{14..17} なので
6428 0..np の範囲を超える場合は不正と判断しなければならない。
6430 ところで復習になるが np は、各圧縮メソッドの辞書のサイズで決まる。対応
6431 を以下に再掲するので確認してほしい。(-lh4- の場合の np はなぜか 13 では
6432 なく14 となっている。おそらく、LHA が実装された当時 -lh6-, -lh7- は存在
6433 せず np や pbit は固定値(定数 NP, PBIT)であったため、-lh4-, -lh5- の両
6434 方に対応できるよう変数の領域サイズを合わせただけであると思う。つまり、
6435 圧縮処理においては、-lh4- の np を 13 と想定しても問題は発生しないと思
6436 われる。逆に復号処理においては、(gzip のように)圧縮 method の情報が渡さ
6437 れない場合は np を 14 とするしかない。なお、このような(gzip のような)
6438 場合 -lh6,7- への対応はできない。最初の pbit 分の要素数の読み込みで 4
6439 ビット読めばよいのか 5 ビット読めばよいのかがわからないからである)
6441 method maxmatch dicsiz dicbit np(dicbit+1) pbit
6442 -----------------------------------------------------------
6443 -lh4- 256 2^12 12 14 (or 13?) 4 (14<2^4)
6444 -lh5- 256 2^13 13 14 4 (14<2^4)
6445 -lh6- 256 2^15 15 16 5 (16<2^5)
6446 -lh7- 256 2^16 16 17 5 (17<2^5)
6449 また、t_len と同様に、p_len[i] >= 7 の形式では、1 が 12 bit より多く連
6453 もちろん、p_len[] を読み込んだ後に構築した Huffman 木の整合性が保たれな
6454 ければならない点は他の Huffman 木と同じだ。
6456 では、実際に復号処理のセキュリティ対応を行ったソースを基に実装を確認しよう。
6461 https://bugzilla.redhat.com/show_bug.cgi?id=204676
6463 にて掲載されたパッチある。このパッチは gzip 用のパッチであったが内容は
6464 ほとんど同じである。(gzip は LHA とほとんど同じ復号処理のソースを含んで
6465 おり、LHA の圧縮形式を復号することができる。ただ、LHA ヘッダを読むこと
6466 はできないため lzh ファイルを展開できるわけではない。見たところ
6467 -lh4,lh5- にのみ対応している。)
6469 diff -ru gzip-1.3.5.orig/unlzh.c gzip-1.3.5/unlzh.c
6470 --- gzip-1.3.5.orig/unlzh.c 1999-10-06 06:00:00.000000000 +0100
6471 +++ gzip-1.3.5/unlzh.c 2006-08-18 22:56:19.446997000 +0100
6472 @@ -149,13 +149,17 @@
6473 unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
6475 for (i = 1; i <= 16; i++) count[i] = 0;
6476 - for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
6477 + for (i = 0; i < (unsigned)nchar; i++) {
6478 + if (bitlen[i] > 16)
6479 + error("Bad table (case a)\n");
6480 + else count[bitlen[i]]++;
6483 bitlen は、c_len, p_len, t_len であり、いずれの Huffman 木も最大の階層
6484 は 16 までであるからその範囲を超えたものがないかチェックしている。これ
6485 は、セキュリティバグの重要な改修点の１点目である。
6488 for (i = 1; i <= 16; i++)
6489 start[i + 1] = start[i] + (count[i] << (16 - i));
6490 - if ((start[17] & 0xffff) != 0)
6491 - error("Bad table\n");
6492 + if ((start[17] & 0xffff) != 0 || tablebits > 16) /* 16 for weight below */
6493 + error("Bad table (case b)\n");
6495 jutbits = 16 - tablebits;
6496 for (i = 1; i <= (unsigned)tablebits; i++) {
6498 tablebits は、make_table() を呼び出すときに指定する引数で以下の通り固定
6499 値(8 or 12)である。従って必ずしも必要ではない。(あえてチェックするなら
6500 Bad table でなく Bug と表示するべきだろう)
6502 make_table(nn, pt_len, 8, pt_table);
6503 make_table(NC, c_len, 12, c_table);
6505 total & 0xffff はどの程度の不正テーブルを検出するのだろうか？
6508 for (i = 1; i <= 16; i++) count[i] = 0;
6509 for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
6512 for (i = 1; i <= 16; i++)
6513 start[i + 1] = start[i] + (count[i] << (16 - i));
6514 if ((start[17] & 0xffff) != 0)
6515 error("Bad table\n");
6517 これは、LHa for UNIX で以下のように書かれていた部分であり、ロジックとし
6524 for (i = 1; i <= 16; i++) {
6526 weight[i] = 1 << (16 - i);
6531 for (i = 0; i < nchar; i++)
6535 /* calculate first code */
6537 for (i = 1; i <= 16; i++) {
6539 total += weight[i] * count[i];
6541 if ((total & 0xffff) != 0)
6542 error("make_table()", "Bad table (5)\n");
6544 例えば、以下の Huffman 木では各階層の重み weight の値(gzip のソースで、
6548 a /\ weight[1] = 0x8000
6549 b c weight[2] = 0x4000
6555 となる。これは正しい Huffman 木について必ず成り立たなければならない必要
6558 しかし、既存の処理では例えば 1 階層目の葉の数が 4 である場合に total が
6559 0x20000 となり 0xffff との論理積では異常を検知できない。
6561 ここは、以下のようにするべきであろう(以下は、LHa for UNIXのソース)。
6564 /* calculate first code */
6566 for (i = 1; i <= 16; i++) {
6568 total += weight[i] * count[i];
6569 if (total > 0x10000)
6570 error("make_table()", "Bad table\n");
6572 if (total != 0x10000)
6573 error("make_table()", "Bad table (5)\n");
6575 ループの中に total のチェックを入れているのは念のためである。もちろん、
6576 total の変数のサイズは 16 bit では足りないので 32 bit 整数にする必要が
6577 ある。(gzip のソースでは、total 変数の代わりに start[17] が使われている
6578 ので、LHa for UNIX のように total 変数にするか、start[] 自体を 32 bit
6581 なお、32 bit 整数にした場合でも、count[1] が 0x20000 の値以上であるとき
6582 total がオーバーフローする恐れがあるが以下の処理より count[] がnchar よ
6587 for (i = 0; i < nchar; i++)
6590 そして、要素数が最も大きい c_len の場合で nchar は NC{510} であるから
6591 32 bit 整数の範囲をオーバーすることはないだろう。このことがはっきりして
6594 if (total > 0x10000)
6595 error("make_table()", "Bad table (5)\n");
6597 は必ずしも必要ではない。あるいは、階層 n の葉の数が 2^n を越えないことの
6601 /* calculate first code */
6603 for (i = 1; i <= 16; i++) {
6604 if (count[i] > (1<<i))
6605 error("make_table()", "Bad table\n");
6607 total += weight[i] * count[i];
6609 if (total != 0x10000)
6610 error("make_table()", "Bad table (5)\n");
6612 これならば、total は最大でも 16 * 0x10000 = 0x100000 にしかならないこと
6615 @@ -169,15 +173,15 @@
6617 i = start[tablebits + 1] >> jutbits;
6619 - k = 1 << tablebits;
6620 - while (i != k) table[i++] = 0;
6621 + k = MIN(1 << tablebits, DIST_BUFSIZE);
6622 + while (i < k) table[i++] = 0;
6625 tablebits は固定値なので、必ずしもこのチェックは必要ではない。
6628 mask = (unsigned) 1 << (15 - tablebits);
6629 for (ch = 0; ch < (unsigned)nchar; ch++) {
6630 if ((len = bitlen[ch]) == 0) continue;
6631 - nextcode = start[len] + weight[len];
6632 + nextcode = MIN(start[len] + weight[len], DIST_BUFSIZE);
6633 if (len <= (unsigned)tablebits) {
6634 for (i = start[len]; i < nextcode; i++) table[i] = ch;
6637 DIST_BUFSIZE は、c_table[] のバッファサイズで 1<<12 である。nextcode は、
6638 LHa for UNIX での該当変数は l で、Huffman 符号の(先頭 tablebits ビット
6639 の)取り得る最大値である。これは、理論上
6641 tablebits 最大の Huffman 符号 m
6642 c_len 12 1111 1111 1111{4095} 4
6643 p_len 8 1111 1111{255} 8
6644 t_len 8 1111 1111{255} 8
6646 であり、ループ脱出条件が不正でない限り、このチェックは不要であると思わ
6647 れる。(そもそも、念のためという意味でチェックしているのなら c_len の場
6650 ただし、先ほどの total チェックが不完全なままだと start[] の値が
6652 そういうわけで、これはセキュリティバグの重要な改修点の２点目となるが、
6653 本当は total のチェックの方が重要である。
6659 である場合、葉に値が割り当てられない枝が発生してしまう。これもチェック
6660 しておいた方が良いだろう。復号語の数は nchar で葉の数は count[] の総和
6665 for (i = 0; i < nchar; i++)
6668 より、このことは保証されているようだ(i >= nchar である bitlen[i] が設定
6669 されていても使われない。もちろん設定された時点で、エラーを検出する方が
6673 for (i = 0; i < 256; i++) pt_table[i] = c;
6677 + while (i < MIN(n,NPT)) {
6678 c = bitbuf >> (BITBUFSIZ - 3);
6680 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
6682 n が t_len、p_len の領域の範囲内の値とは限らないのでそのチェックを行っ
6683 ている。これは、セキュリティバグの重要な改修点の３点目である。
6687 ・p_len, t_len の論理的な領域サイズでなく実装上の pt_len の領域サイズで
6688 チェックしている。そのため、バッファオーバーフローのセキュリティ対策
6689 としては十分だがエラーチェックとしては不完全である(エラーの検出が遅延
6692 ・不正な値をエラーとせず。処理を最大値で継続している。そのため、以下同文。
6696 if (i == i_special) {
6698 - while (--c >= 0) pt_len[i++] = 0;
6699 + while (--c >= 0 && i < NPT) pt_len[i++] = 0;
6702 while (i < nn) pt_len[i++] = 0;
6704 i_special は 3 固定なので、このチェックは必ずしも必要というわけではない。
6705 (厳密には、実装上 i_special が -1 である場合があるが i が -1 になった時
6709 for (i = 0; i < 4096; i++) c_table[i] = c;
6713 + while (i < MIN(n,NC)) {
6714 c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
6716 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
6718 n が c_len の領域の範囲内の値とは限らないので、同上。
6720 @@ -256,14 +260,14 @@
6721 if (bitbuf & mask) c = right[c];
6724 - } while (c >= NT);
6725 + } while (c >= NT && (mask || c != left[c]));
6730 c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
6732 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
6734 if (bitbuf & mask) c = right[c];
6739 fillbuf((int) pt_len[c]);
6743 mask == 0 && c == left[c]
6745 の条件を満たしてしまうような不正な木が構築されていると c の値は変化せず
6746 いつまでもループし続けることになってしまう。そこで、この条件が発生した
6747 ときにすぐにループを脱出するようその条件の否定である
6749 !(mask == 0 && c == left[c])
6753 (mask || c != left[c])
6755 をループ継続の while 条件に加えているようだ。しかし、mask の初期値は
6757 1 << (BITBUFSIZ{16} - 1 - 8) {0000 0000 1000 0000}
6763 しているのだから、mask == 0 になった時点で、8 bit(最初の表引きと合わせ
6764 て 16 bit)の Huffman 符号を読み込んでおり(くどいかも知れないが LHA にお
6765 ける Huffman 木の階層は最大 16)、mask == 0 を脱出条件に加えるだけで良い
6768 もちろん、17 bit の符号を読み込んだ時点で不正なのだから
6770 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
6772 if (mask == 0) error("....");
6774 if (bitbuf & mask) c = right[c];
6779 と異常終了しても問題ないと思う。以下のように for で書くこともできるがま
6780 あ結局は同じことだ。(こうすると見やすいだろうか？と考えてみただけである
6783 for (mask = 1 <<(BITBUFSIZ-1-8); mask != 0; mask >>= 1) {
6784 if (bitbuf & mask) c = right[c];
6789 if (mask == 0) error(...);
6791 しかし c の値と left[], right[] の領域サイズとの比較は良いのだろうか？
6792 （理論上は Huffman 木の構築時にチェックされていれば問題ないので、私は問
6793 題ないと思うのだが、それを言うとそもそも無限ループのチェックも不要であ
6796 fillbuf((int) pt_len[c]);
6799 else if (c == 1) c = getbits(4) + 3;
6800 else c = getbits(CBIT) + 20;
6801 - while (--c >= 0) c_len[i++] = 0;
6802 + while (--c >= 0 && i < NC) c_len[i++] = 0;
6803 } else c_len[i++] = c - 2;
6805 while (i < NC) c_len[i++] = 0;
6807 c_len[] の範囲外の領域に値が設定されないようチェックしている。しかし、
6808 やはりエラーとして検出せずに処理を続行している。
6811 if (bitbuf & mask) j = right[j];
6814 - } while (j >= NC);
6815 + } while (j >= NC && (mask || j != left[j]));
6817 fillbuf((int) c_len[j]);
6823 if (bitbuf & mask) j = right[j];
6826 - } while (j >= NP);
6827 + } while (j >= NP && (mask || j != left[j]));
6829 fillbuf((int) pt_len[j]);
6830 if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
6836 buffer[r] = buffer[i];
6837 i = (i + 1) & (DICSIZ - 1);
6838 - if (++r == count) return r;
6839 + if (++r >= count) return r;
6843 @@ -366,14 +370,14 @@
6845 if (c <= UCHAR_MAX) {
6847 - if (++r == count) return r;
6848 + if (++r >= count) return r;
6850 j = c - (UCHAR_MAX + 1 - THRESHOLD);
6851 i = (r - decode_p() - 1) & (DICSIZ - 1);
6853 buffer[r] = buffer[i];
6854 i = (i + 1) & (DICSIZ - 1);
6855 - if (++r == count) return r;
6856 + if (++r >= count) return r;
6862 さて、これらセキュリティ対策は具体的にどのような場合を想定しているのだ
6865 https://bugzilla.redhat.com/show_bug.cgi?id=204676
6867 には、木の構築が不正になるシナリオとして以下が書かれている。
6869 > * Construct a pt_len[] such that pt_len[n] is 0.
6870 > * Construct a pt_table[] such that pt_table[(code buffer) >> 16 - 8]
6872 > * Now c_len[] is filled with (n-2), generating exceptionally high values in
6875 しかし、これを読んでもよくわからなかったので一緒に掲載されていたサンプ
6878 > perl -e 'print "\x1f\xa0","\xab\xcd","\xf6\x40\x01\xc2\xcc\x36\x0c\x92\x00\x00\x00\x00","\xc8","\x00"x"2048"' | gzip -d
6880 \x1f\xa0 はマジックナンバーで、gzip における LHA の圧縮形式を示す。そし
6881 て、LHA フォーマットは、\xab\xcd から始まる。これは、blocksize である。
6885 そして、t_len の出力形式が続く。2 進数と合わせて下記に示す。
6888 1111 0110 0100 0000 0000 0001 1100 0010 1100 1100 0011 0110
6893 0000 1100 1001 0010 0000 0000 0000 0000 0000 0000 0000 0000,
6896 1100 1000, 0000 * 2048
6898 いきなり、t_len のサイズが不正(1111 0=0x1e(30) > NT{19})である。そして、各
6899 t_len[] を読み込むと以下のようになる
6931 t_len[29] = 00, 1 :1
6933 この t_len から Huffman 木の階層の葉の数は、以下の通りとなり
6942 以下のような木の形になるので、不正である(図中 X は、count の値が不正な
6959 結果的に、c_len[] はというとこちらは gzip のソースを修正して実際に値を
6960 出力させてみたところ以下の通りすべての値が 5 になった。これはやはり不正
6961 である。(階層 5 の葉の数が 288 個ある)
6963 size of c_len: 100 1000, 0 0x120(288)
6971 ところで、本当はこうしたかったのではないだろうか？
6973 perl -e 'print "\x1f\xa0","\xab\xcd","\x9e\x40\x01\xc2\xcc\x36\x0c\x92","\xc8","\x00"x"2048"' | gzip -d
6975 これならば、t_len[] の領域サイズは超えないので、このチェックにはかから
6980 size of t_len: 0x13(19)
7002 そして、先ほどと同じ count[] の結果となり不正な木ができる。
7013 size of c_len: 0x190 (400)
7019 結局、この問題は木の形の不正を検出できてないために発生している。調べて
7020 みたところ、この例では total が 0x30000 になるために、
7022 (total & 0xffff) != 0
7024 で検出できていないようである。従って、先に示したとおり total を 32 bit
7031 # ちなみに、この条件は「クラフトの不等式」を整数に変形したものであるらしい。
7032 # 階層 16 以下のハフマン木であれば、
7034 # total == 2^16(0x10000)
7040 # であれば、この木は冗長な符号を割り当てていることを示すそうだ。そして、
7044 # は、一意な復号ができないことを示す。
7046 念を押しておくが、セキュリティパッチが間違っているわけではない。セキュ
7047 リティパッチとしてはバッファオーバフローを防げば良いので単にそのための
7048 チェックを入れただけである。ただし、プログラマの立場としてはセキュリティ
7049 パッチは対症療法な修正でしかなく、根本的な問題点を解決していない場合が
7050 あるということを覚えておく必要がある。と思う。
7053 このセキュリティバグの報告を受けて、gzip としてどのように修正しているか
7054 を確認してみた。以下は、問題が発見された gzip-1.3.5 とその修正が行われ
7055 た gzip-1.3.6 との差分(unlzh.c のみ)である。
7057 --- gzip-1.3.5/unlzh.c 1999-10-06 14:00:00.000000000 +0900
7058 +++ gzip-1.3.6/unlzh.c 2006-11-20 17:40:34.000000000 +0900
7063 -static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";
7064 +static char rcsid[] = "$Id: unlzh.c,v 1.4 2006/11/20 08:40:34 eggert Exp $";
7068 @@ -69,11 +69,7 @@ local void make_table OF((int nchar, uch
7069 #define NT (CODE_BIT + 3)
7070 #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */
7071 #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */
7077 +#define NPT (1 << TBIT)
7080 恐らく、NT を超える値が圧縮文に埋め込まれてもバッファオーバーフローしな
7081 いようにするために pt_len のバッファサイズを大きくしたのだろう(重要な改
7082 修点の３点目を別な方法で解決している。個人的にはこのような対処は好みで
7085 c_len の領域サイズ(NC)はというと、gzip では元々 c_len のバッファサイズ
7086 は NC よりも大きい(8192 or 16384)。どうやら他の変数を使い回ししているた
7089 /* local ush left[2 * NC - 1]; */
7090 /* local ush right[2 * NC - 1]; */
7091 @@ -155,7 +151,7 @@ local void make_table(nchar, bitlen, tab
7092 for (i = 1; i <= 16; i++)
7093 start[i + 1] = start[i] + (count[i] << (16 - i));
7094 if ((start[17] & 0xffff) != 0)
7095 - error("Bad table\n");
7096 + gzip_error ("Bad table\n");
7098 ここの判定(木の構築が正しいかどうか)は変えなかったようだ。
7100 jutbits = 16 - tablebits;
7101 for (i = 1; i <= (unsigned)tablebits; i++) {
7102 @@ -179,6 +175,8 @@ local void make_table(nchar, bitlen, tab
7103 if ((len = bitlen[ch]) == 0) continue;
7104 nextcode = start[len] + weight[len];
7105 if (len <= (unsigned)tablebits) {
7106 + if ((unsigned) 1 << tablebits < nextcode)
7107 + gzip_error ("Bad table\n");
7108 for (i = start[len]; i < nextcode; i++) table[i] = ch;
7112 代わりに、table[] の領域範囲を超える符号が現れた場合にエラーになるよう
7113 にしている(重要な改修点の２点目。ちゃんと、c_len だけでなく、pt_len の
7116 @@ -223,6 +221,8 @@ local void read_pt_len(nn, nbit, i_speci
7118 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
7119 while (mask & bitbuf) { mask >>= 1; c++; }
7121 + gzip_error ("Bad table\n");
7123 fillbuf((c < 7) ? 3 : c - 3);
7126 p_len, t_len について Huffman 符号長より大きい値が復号語となる場合にエ
7127 ラーとしている。(重要な改修点の１点目)
7129 パッチでは、make_table() 内でチェックしていたところを実際に値を読み込む
7130 箇所に移したのだろう。そして、c_len の場合は、t_len の復号で木の構築
7131 チェックにてエラーが検出されなければ問題ないとみなしているのだろうと思
7134 どうやら方針としては最低限のチェックで済ませているらしい。さすがにアル
7135 ゴリズムを熟知した上での修正のように見えるが、これで良いのかいまひとつ
7136 確信が持てない。まあ、gzip についてはこれ以上は触れないでおこう。
7140 # mode : indented-text
7141 # indent-tabs-mode: nil
OSDN Git Service
