Koji Arai
JCA02****@nifty*****
2003年 1月 5日 (日) 13:05:11 JST
新井です。 突然ですが The Hacking of LHa for UNIX (1st draft) ------------------------------------------- 2003-01-05 Koji Arai <mailto:jca02****@nifty*****> 本書は、LHa for UNIX 1.14i のソースを解読し、その圧縮アルゴリズムの実 装を確認するためのものだ。この成果は別の形でまとめなおされ資料になるか もしれないし、このままの形で保管されるかもしれないし、新たにソースを書 き起こす元になるかもしれない。とにかく、暇な正月休みを潰すためにやって みただけのものだ。(休みが明けるとまた忙しくなるので、これ以上まったく 何もしないかもしれない) 現時点では、slide.c の解析だけである。huf.c も同時進行で解析中だが、文 体が異なる(読みものとしての体裁を整えていない)ので公開するとしても別文 書になるだろう(huf.c の解析文書は現時点でデバッガによるおっかけが中心 のメモでしかない) # 本当は、huf.c の解析を先に行っていた slide 辞書の encoding 部はなく # ても LHA 互換アーカイバは作れそうだったからだが、huf.c は slide.c # に比べて難解な部分が多そうだから、後回しにした。 本書は、まだ未完成である。にもかかわらず公開するのはこれ以上続かないか もしれないからである(気が向いたらまた続きを書くだろう。あるいは応援の お手紙がくればやる気が出るかもしれない)。 本書はフリーである。複製、改変、再配布は自由であるということだ。ただし 本書により生じたあらゆる損害、不利益に対しては一切の保証はない。本書に は嘘があるかもしれない。それに対して嘘を教えられたと著者を避難をしない で頂きたい。しかし間違いの指摘は構わない(ぜひお願いしたい)、著者は圧縮 処理に関しては無知である。用語の使い方等は適切でないかもしれないのでこ の方面でも御指導頂ければ幸いである。 =============================================================================== o 表記について * 関数は、その定義ソースfile.c と関数名 func() を示すのに file.c:func() という記述を使う * o 用語について * 符号 符号化、符号語、圧縮文 * 復号 復号化、復号語、復号文 =============================================================================== まず、構造について考える。 slide辞書法は、encoding にさまざまな工夫が凝らされるのでとても複雑だが、 普通 decoding は単純である。decoding を解析することでどのような圧縮文 を作っているのかを調べてみる。 decoding を行う処理は、slide.c の decode() である。この処理を見てみる と思った通り簡単に解読できた(以下) 1. huffman coding により復号した文字を環状バッファ dtext に書き込む 通常の文字 c は、c < 256 で表現されている(つまりそのまま) 2. 通常の文字でないものが現れたら、それは長さである。長さ len は、 len > 255 で表現されている。len から 0xfd(253) を引いた値が 実際の長さを表す(-lzs- method の場合は、0xfe(254)を引く) 「長さ」が、現れたらその直後には「位置」が書かれているのでそれを 読む。こうして、長さと位置のペア<len, pt>を得る dtext から pt+1 バイト前の len バイトを読み、dtext に追加で書き込む 3. dtext が一杯(dicsiz)になったらファイルに書き出す これの繰り返しである。つまり、slide 辞書法の圧縮文は、文字 c と<len, pt> の並びであることがわかる。例えば、文字列 c1 c2 c1 c2 は、以下のよ うに表現されているはずである。(本当は、長さが 2 以下では圧縮が起こらな いので平文のまま出力する。長さは最低でも 3 は必要) +----+----+--------+ | c1 | c2 | <2, 1> | +----+----+--------+ では、この構造を作成する圧縮処理について考える。slide 辞書法では、ファ イルから読み込んだ文字列 token が、以前に読み込んだ辞書に存在すれば <len, pt> のペアを出力し、存在しなければ token をそのまま出力する。読 み込んだ token は、辞書に追加し、辞書の語が溢れたら古い情報を捨てる。 何も予備知識がない状態で書けば while (read_file(&token, tokensiz)) { len = search_dict(dict, token, &pt); if (len == -1) { print_token(token); else print_pair(len, pt); update_dict(dict, token); } のようになるはず。ここで、tokensiz は token の最大サイズで、最長一致長 を表す。この値が大きければ大きい程、圧縮効率は良くなるはずで、lha では、 これは MAXMATCH{256}である。また、dict は辞書でこのサイズは lha の -lz5- メソッドでは、8192 となっている。この辞書も大きければ大きい程良 いはずだ。その方が一致文字列が見つかりやすい。(ただし、辞書が大きいと 一致位置を示す情報 <len, pt> の情報量が増えるはずだし、速度も遅くなる だろう。後で検証する) で、実際にソースを見てみると(slide.c:encode())・・・、まったくこのよう な構造にはなってないように見える。何やらややこしいことばかりでまったく わからない。なぜここまでややこしいのかと泣きたくなってくるが、それは速 度のためである(本当？)。上記のコードで、search_dict() は、単に dict か ら token に一致する位置を検索するだけで良さそう(実際にそれでも良い)だ が、これではまったく速度が出ない。このあたりの工夫が slide 辞書法のキ モである。 そういうわけで、この部分を読み解くことにする。なお、予備知識として lha では、辞書から token を探すのにハッシュが使われているらしいことを記し ておく。 ここでは実際にデバッガで動作させながら解読するのではなく、ソースを読む だけで理解できるかを試すことにする。また、本文は某書(謎)のノリをマネて いると指摘する方がいるかもしれない・・・がまったくその通りだ。 まず、そのものずばりの encode() (slide.c) を見る。以下がこの関数だが 処理の要点だけに着目するために不要そうな部分は(現時点で予測で)削った。 unsigned int encode() { int lastmatchlen; unsigned int lastmatchoffset; /* (A) */ init_slide(); /* (B) */ remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile); encoded_origsize = remainder; matchlen = THRESHOLD - 1; pos = dicsiz; if (matchlen > remainder) matchlen = remainder; /* (C) */ hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5) ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1); /* (D) */ insert(); while (remainder > 0 && ! unpackable) { /* (E) */ lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1; --matchlen; /* (F) */ /* (G) */ get_next(); match_insert(); if (matchlen > remainder) matchlen = remainder; /* (H) */ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) { /* (H.1) */ encode_set.output(text[pos - 1], 0); count++; } else { /* (H.2) */ encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD), (lastmatchoffset) & (dicsiz-1) ); --lastmatchlen; while (--lastmatchlen > 0) { get_next(); insert(); count++; } get_next(); matchlen = THRESHOLD - 1; match_insert(); if (matchlen > remainder) matchlen = remainder; } } } まず、この関数から概観を見てみると、ループの前に初期化処理として 以下が行われている。 (A) init_slide() 初期化する (B) ファイルを読み込み text[] に格納する。 (C) ハッシュ値 hval を計算する。 (D) insert() する (きっと辞書に token を追加しているのだろう) そして、ループ処理では以下の処理が行われている (E) lastmatchlen, lastmatchoffset, matchlen を更新する。 (F) get_next() (次の token を読む。たぶん) (G) match_insert() (辞書に追加する。たぶん) (H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら (H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん) (H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。 現時点で、(H.2) の部分はよく解読できなかった。何やら再度 get_next() が 呼ばれていたりして思った通りの処理フローにはなっていない。だが、ここで は焦らず放置することにして、ここまで予想で書いた部分の細部に触れること にする(単にここまでの予想が間違っているだけかもしれないのだから、わか らない部分を無理にわかるように頑張る必要はなかろう) 関数の細部に触れる前にデータ構造について調べておく。データ構造に対して の理解が深まればアルゴリズムの80%は分かったも同然だ(誇張)。slide.c で 使用されているデータ構造は以下の通りだ。(不要そうだと思うものは除いて ある) static unsigned int *hash; static unsigned int *prev; unsigned char *too_flag; static unsigned int txtsiz; static unsigned long dicsiz; static unsigned int hval; static int matchlen; static unsigned int matchpos; static unsigned int pos; static unsigned int remainder; too_flag だけ、static がついてないが、他のソースを grep してもこの変数 を使っている箇所はない、単に static の付け忘れだろう。 これらの変数は、encode() の冒頭 init_slide() で初期化されている・・の かと思ったら違った。slide.c:encode_alloc() で行われている。 int encode_alloc(method) int method; { if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */ encode_set = encode_define[0]; maxmatch = 60; dicbit = 12; /* 12 Changed N.Watazaki */ } else { /* method LH4(12),LH5(13),LH6(15) */ encode_set = encode_define[1]; maxmatch = MAXMATCH; if (method == LZHUFF7_METHOD_NUM) dicbit = MAX_DICBIT; /* 16 bits */ else if (method == LZHUFF6_METHOD_NUM) dicbit = MAX_DICBIT-1; /* 15 bits */ else /* LH5 LH4 is not used */ dicbit = MAX_DICBIT - 3; /* 13 bits */ } dicsiz = (((unsigned long)1) << dicbit); txtsiz = dicsiz*2+maxmatch; if (hash) return method; if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */ hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int)); prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int)); text = (unsigned char*)malloc(TXTSIZ); too_flag = (unsigned char*)malloc(HSHSIZ); if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL) exit(207); return method; } 引数に渡された method (これは、lh1, lh5, lh6, lh7 などを示す)によって、 初期化される内容が変わる(encode_alloc()前半部分)。このことから各変数の 用途もわかる。 method maxmatch dicbit ---------------------------- -lh1- 60 12 -lh5- 256 13 -lh6- 256 15 -lh7- 256 16 ということらしい。dicbit というのは辞書サイズのbitサイズで、辞書サイズ は 2^dicbit で表されている。lh5 が 8KB(2^13)、lh6 が 32KB(2^15)、lh7 が 64KB(2^16) の辞書サイズを利用すると言うのは予備知識である。maxmatch というのは、token の最長一致長である。このことも予備知識として詳細には 触れない。(ところで、本書では当面、lh5, 6, 7 のことしか言及しない) encode_set, encode_define というのがあるが、method によって、Huffman coding の方法を変えていることはちょっと見ればすぐにわかるし、大したこ とではない。以降無視する。 encode_alloc() の後半では、他の変数の初期化(バッファの割り当て)が行われる。 dicsiz = (((unsigned long)1) << dicbit); dicsiz はそのものずばり辞書サイズである。 txtsiz = dicsiz*2+maxmatch; 現時点で txtsiz が何なのかはわからない。 if (hash) return method; hash はこの直後で割り当てられる。つまり、一度割当を行ったら、 encode_alloc() は、以降メモリの割当を行わない。ただそれだけだ。 if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */ alloc_buf() は、huf.c で定義された関数。このことから Huffman coding の ためのバッファを割り当てているのだろう。ここでは無視。(しかし、207 と いうのは何なのだろう？) hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int)); prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int)); text = (unsigned char*)malloc(TXTSIZ); too_flag = (unsigned char*)malloc(HSHSIZ); if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL) exit(207); hash は、ハッシュ用の何か、HSHSIZ は、固定値で 2^15 である。 prev は、DICSIZから辞書だろう。要素の型が char でなく int であることに も注目しておく。DICSIZ は dicsiz でも構わないはず。単に「大は小を兼ね る」を実践しているだけであろう、TXTSIZ も同様である。おそらく、一度の 実行で複数の圧縮メソッドを使用した場合、そのメソッド毎に領域を割り当て るよりは最大の値をあらかじめ一度だけ割り当てた方が良いと考えたのだろう。 しかし、ソースを参照するときは繁雑になるので以降、 DICSIZ == dicsiz TXTSIZ == txtsiz であるとする。これ重要。 text は、現時点では不明 too_flag も不明 っとなる。まだ、良く分からないが、以下の図を書いておこう。後で何度も見 ることになるだろう。この図はスケールが lh7 の場合を想定しているが。こ のことは大したことではないはずだ。また、too_flag と hash のスケールが 一緒だがこれはサイズ(領域のバイト数)が一緒なのではなく、要素数が一緒で あることを示している。ほとんどの場合要素の型の違いというのは処理内容に とって重要なことではないはずだ。 ---------------------------------------------------------------------------- 0 2^15=32768 +-------------+ hash | | +-------------+ dicsiz=2^dicbit +-------------+-------------+ 2*2^dicbit prev | | | | +-------------+-------------+ v txtsiz +-------------+-------------+-------------+-------------+---+ text | | | | | | +-------------+-------------+-------------+-------------+---+ <---> maxmatch{256} too_flag 2^15 +-------------+ | | +-------------+ ---------------------------------------------------------------------------- 先に示した変数の中でまだ初期化には現れていないものがある。列挙すると static unsigned int hval; static int matchlen; static unsigned int matchpos; static unsigned int pos; static unsigned int remainder; だ、ざっとソースを眺めると slide.c:insert() という関数に hash[hval] = pos; というのが現れているから、hval は、hash[] の位置を指し、hash には、pos を格納すると推測される。同様に prev[pos & (dicsiz - 1)] = hash[hval]; というのも現れているから pos は、prev[] の位置を指し、prev には、 hash[hval] つまり、pos を格納しているようだ。これは少し謎な処理だが、 insert() の全貌は短い(というかこれだけ)なので、ちょっと横道にそれて詳 細に見てみよう。(現在の解析の趣旨は、変数の用途の概要を予想すること) /* 現在の文字列をチェーンに追加する */ static void insert() { prev[pos & (dicsiz - 1)] = hash[hval]; hash[hval] = pos; } コメントはまったく意味不明だが、無視して処理内容に着目する。prev[] の インデックス pos & (dicsiz - 1) は、dicsiz が 2^n であることからdicsiz はビットマスクであることがわかる。例えば仮に dicsiz が 2^8 だと dicsiz - 1 は、 8 7 6 5 4 3 2 1 0 bit -------------------------- dicsiz 1 0 0 0 0 0 0 0 0 dicsiz-1 1 1 1 1 1 1 1 1 である。このすべて 1 が立ったビットマスクと pos を & すると、どのよう な pos の値に対しても pos & (dicsiz - 1) は、prev[] のインデックスの範 囲に納まる。もう少し言うと pos が仮にインデックスの最大値+1だった場合、 pos & (dicsiz - 1) は、0 になる。これにより次の予想が立つ。 o pos が、prev[] の位置を指すのではなく、pos & (dicsiz - 1) が prev[]の位置を指す。(pos は、このインデックスの範囲を越える可能性がある) o それに反して、prev[] は環状バッファらしいという予想が立てばやはり pos は、prev のインデックスである。 prev が環状バッファであると予想が付けば話が早い。pos & (dicsiz-1) は、 pos と同義だと解釈可能だからである(prev が環状バッファでなく無限長のバッ ファであると想像しよう)そして、pos & (dicsiz-1) を pos に置き換えて、 再度処理内容に着目すると prev[pos] = hash[hval]; hash[hval] = pos; ということから、 1. (この関数に来る前に) pos が更新される。(予想) 2. prev[pos] に以前の hash[hval] (以前の pos)を格納する 3. hash[hval] に新しい pos を書く。 といった処理であることが予想される。コメントの「チェーン」もなんとなく 納得できる。新たな事実(まだ予想だが)が分かったので、図に書き記そう。 ---------------------------------------------------------------------------- 0 2^15=32768 +-+---+-------+ hash | |pos|... | +-+---+-------+ `-hval +----+----+-------------------- prev | |ppos| . . . +----+----+-------------------- `- pos * hash の取り得る値は pos その位置は hval * ppos は以前の pos を示す。prev は無限長のバッファ(本当は環状バッファ) ---------------------------------------------------------------------------- まだ、解析できてない変数が残っている。 static int matchlen; static unsigned int matchpos; static unsigned int remainder; しかしこれらはどうにもパッと見ではわからない。処理内容を追いかけないと だめそうだ。仕方ないので変数名で予想しよう。(幸い前の変数名と違って予 想しやすい)以下 ---------------------------------------------------------------------------- * matchlen 一致した文字列長 * matchpos 一致した辞書上の位置 * remainder token の残りサイズ ---------------------------------------------------------------------------- はたして、予想はあっているのか、今はまだ分からない。 slide.c を見る限りデータ構造は網羅できた。結局分かったのか分からないの か良く分からないが少しずつでも前進はしているはずだ。ここで、再度 encode() の処理を追いかけよう。今度は細部にも着目する。 前に、encode() のソースには (A) 〜 (H) までの記号を記した。この順番に 解析を進めよう。 /* (A) */ init_slide(); まあ、初期化である。内容を見てみると for (i = 0; i < HSHSIZ; i++) { hash[i] = NIL; too_flag[i] = 0; } だけである。NIL というのは、0 であると slide.c で定義されている。普通 このような初期値は、通常の値が取り得ない値を示している。NIL が 0 なら hash[] に格納される pos は 0 にならない可能性がある。まあ、予想ばかり 書いても仕方ないので、この関数は終ろう。余談だが、nil は null と同じで。 「ない」の意味だが、NULL がC言語ではポインタだから。別のマクロ名にした のかも知れない。いずれにしてもこの程度はマクロにする必要もなかろうとは 思うのは、余計なお世話かもしれない。 /* (B) */ remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile); encoded_origsize = remainder; matchlen = THRESHOLD - 1; pos = dicsiz; if (matchlen > remainder) matchlen = remainder; ファイルを読み込み、各変数の初期値を設定している。注目すべきはファイル を読み込んだバッファの位置である。fread_crc() は、crcio.c で定義された 汎用関数で、CRC値を計算したり漢字コード変換をしたりを除けば、fread() と同じである。つまり、ファイルは最初、 &text[dicsiz] の位置に、txtsiz-dicsiz 分だけ読まれる。 ことを示す。図示しよう。 ---------------------------------------------------------------------------- < 初期状態 > dicsiz=2^dicbit 2*2^dicbit v v txtsiz +-------------+-------------+-------------+-------------+---+ text | | | | | | +-------------+-------------+-------------+-------------+---+ `-pos <---> maxmatch{256} <------ remainder --------------> |--- この位置に最初の ---------| データが読まれている ---------------------------------------------------------------------------- ますます、text[] の用途が不明だが、slide 辞書法の典型的な読み込み処理 のことを考えるとある程度予想がつく(それを先に示した方が良いか？)。まあ、 ここではフーンっと鼻で納得して済まそう。 fread_crc() は、読み込んだバッファ長を返す。remainder がその値で、既に 図示してある。encoded_origsize は、ソースを見ると、元のファイルのサイ ズを表すためだけの変数のようだ。以降は無視しよう。 ところで、ファイルサイズが小さい場合図の通りにならないっと考えるかも知 れない。その通りなのだが、例外条件は少ない方がソースは理解しやすい。単 純な場合だけを考えた方が、あれこれ考えをめぐらす必要がないからだ。なに しろ既に動くソースを見ているのだから、細かいことに目をつぶってもエンバ グすることはないのである。そういうわけで、当面はこの図が唯一の初期状態 であると考える。 (B) の部分はもう少し注目すべき箇所がある。 matchlen = THRESHOLD - 1; matchlen は、「一致した文字列長」であると予想したが THRESHOLD の値は 3 (固定値)であるから、matchlen の初期値は 2 だ。いきなり予想がはずれた気 がする。予想を立て直そう。2 という謎な数値と match*len* について考える と、冒頭で <len, pt> のペアの len は 2 であることはないと説明した。無 意味だからであるが、matchlen の初期値はこの 2 と関連するかもしれない。 そこで、matchlen の用途を以下のように予想しなおすことにする。以下のよ うにメモを更新しよう。THRESHOLD(threshold は閾値の意)も一緒に予想した。 ---------------------------------------------------------------------------- * matchlen 最低限一致しなければならない長さ-1 * THRESHOLD 最低限一致しなければならない長さ ---------------------------------------------------------------------------- うーん、本当だろうか？ (B) の残りの部分を片付けよう pos = dicsiz; if (matchlen > remainder) matchlen = remainder; pos が dicsiz であることからどうやら、pos は、text[] のインデックスら しい。前の予想で pos は、prev[] のインデックスでもあり、hash[] の値で もあると予想したのだが(これはもちろん間違いではなかろうが)。どうやら 本当の意味は、処理するテキストの先頭を示しているのではないかとも思える。 まあ、ここでは無難に「text[] のインデックス(でもある)」とだけ理解しよう。 既に図には書き込んである。 次の if だが、remainder が matchlen よりも小さい場合の条件だ。また、 matchlen の予想が覆されそうな予感がしないでもないが、この if 文は*例外 条件*なので無視することにした。都合の悪いことは見ない方が良いのだ。 /* (C) */ hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5) ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1); (C) である。これは難解である。複雑な数式は苦手であるが、じっくり考えよ う。まず求める値は hval である。これは hash[] のインデックスなのだが、 このような複雑な式で求まるインデックスなんて想像もつかない。まず、最初 のインスピレーションを大事にすることにしよう。冒頭で、(C) の処理は「ハッ シュ値 hval を計算する。」っと苦もなく予想した。そしてこれは間違いでは ないだろう(きっと)。hash[] との関連をここで考えてもわからないから、こ のハッシュ値の計算だけを考えることにしよう。 式をじっくり見てみる。。。じっくり見てみると以下のことがわかる。 x(i) = text[dicsiz + i] とすると hval = ((x(0) << 5) ^ (x(1) << 5) ^ (x(2) << 0)) & (unsigned)(HSHSIZ - 1); である。最後の & (unsigned)(HSHSIZ - 1) は、前にも似たような式が出たが これはある範囲の数値(ここでは、0 〜 HSHSIZ{2^15}-1)を抽出するためのビッ トマスクである。ハッシュ関数と言うのはある符号をある集合の符号に写像す る関数であるからこのようなビットマスクは当然必要だし、良く行われる事だ (普通は mod 素数を行うんだけど)。また、hval は、hash[] のインデックス なのだから、写像する集合とは hash[] のインデックスだ。おっ、案外簡単に わかった。x(i) が text[dicsiz + i] で、ハッシュ関数の変数は x(0), x(1), x(2) だから、先頭の 3 バイトの文字列(平文)のハッシュ値を求めてい るわけだ。その他の計算(<< 5 とか ^ とか) は大したことではない。無視し よう。また、続けて (D) の処理も見るが、 /* (D) */ insert(); insert() は、幸い解読ずみである pos を hash[] に格納する処理だ。 予想の段階では、(C) と (D) を別個の処理と考えていたのだがこれは どうやらセットである。 (C) pos の位置の 3 文字のハッシュ値を計算し (D) hash[ハッシュ値] = pos を行う もう少し注意深く検討すると「posの位置の3文字」と、求めた「ハッシュ値」 は論理的には = である。 つまり、(C) (D) の処理は hash[文字列] = 位置 という処理を行っている。ハッシュ値の衝突はここでは考えない。slide 辞書 法では、ある文字列に対し以前その文字列が現れたかどうかを検索し、その位 置を求める必要があるのだが、この最初の 3 文字に関しては現時点でその用 件(位置を求める)を満たす事ができている。ここまでで自ずと encode() の全 体像も予想がつきそうな気がする。 # 衝突は考えないっとしたが prev[pos] に以前のハッシュ値が格納されてい # ることから簡単にわかる。チェーン法だ。謎は全て解けた。 # それにつけても、(C) と (D) の部分を見るだけでもこのソースがちょっと # 汚いことがわかる。もう少し、引数とか戻り値とか考えてくれても良かっ # たはずだ。ハッシュ関数にしても少なくともマクロぐらいにはしようよ。 (E) 〜 (H) に移ろうこれはループの中身で、処理の本題だ。まずループの脱 出条件を見てみると while (remainder > 0 && ! unpackable) { remainder は、バッファ上に読み込んだ平文の長さであるからこれがなくなる までループすることになる。さらに unpackable というのは、crcio.c の putcode() でその値を設定している箇所が出て来るのだが、符号化した出力サ イズが元のサイズを越えたときに真になる。つまり、これ以上処理しても圧縮 の意味がないとわかったらループを抜けるわけだ。 では、(E)を見よう。 /* (E) */ lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1; --matchlen; ちょっと見ただけではやはりわからない。これらの変数はまだ予想しかしてな いからである。が、わかるだけの情報は書きしるそう。 ---------------------------------------------------------------------------- lastmatchlen 以前の matchlen の値 (変数名から) lastmatchoffset 以前マッチした位置 (変数名から) ---------------------------------------------------------------------------- 以前の値をlast〜に退避し、新たな値を設定する準備をしているわけだ。そし て、「新たな値の設定」は、--matchlen で早速行われている。しかし、「マッ チした長さ」をまだ何もしてないのに -1 するというのはいったいどういうこ とだろう？ matchlen はループの頭で 2 に設定されている。これが 1 になっ た。本当の初期値は 1 なのか？ ---------------------------------------------------------------------------- < 各変数の初期値 > matchlen = 1 matchpos = 0 pos = dicsiz lastmatchlen = 2 lastmatchoffset = dicsiz - 1 (pos - matchpos - 1) ---------------------------------------------------------------------------- この (E) はまた後で見る事になるだろう。 (F) (G) である。また、その直後には以前にも見た境界条件がある。 /* (F) */ /* (G) */ get_next(); match_insert(); if (matchlen > remainder) matchlen = remainder; if 文 は無視して関数の中身だけを追いかけてみよう。まず、get_next() こ れは 次の token を取ってくる処理だと予想してある。はたしてどうだろうか？ static void get_next() { remainder--; if (++pos >= txtsiz - maxmatch) { update(); } hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1); } remainder を消費し、pos を進めている。予想通りだ。ひとまず if の条件は 無視すると直後で hash 値を求め直している。このハッシュ関数は、以前のハッ シュ値を利用しているが、これは pos が以前より + 1 されていることを考え ると関連が見えて来る。以前のhash関数を pos の関数として書き直すと x(pos+i) = text[pos + i] hval(pos) = (x(pos+0) << 5) ^ (x(pos+1) << 5) ^ (x(pos+2) << 0) & (unsigned)(HSHSIZ - 1); であり、また、今度のハッシュ関数は、 hval(pos+1) = (hval(pos) << 5) ^ (x(pos+1 + 2) << 0) & (unsigned)(HSHSIZ - 1); だ、繁雑なので & (HSHSIZE-1) を外すと、(気をきかして << 0 というのも書 いていたがどうやら意味がないので外した) hval(pos+1) = (x(pos+0) << 5) ^ (x(pos+1) << 5) ^ x(pos+2) ^ x(pos+3) っとなる。この次 get_next() が呼び出されれば、 hval(pos+2) = (x(pos+0) << 5) ^ (x(pos+1) << 5) ^ x(pos+2) ^ x(pos+3) ^ x(pos+4) である。順にハッシュ値を求める文字列長を増やしている。とにかく、 get_next() は、pos を進め、remainder を縮め、新たな(以前より1文字長い) 文字列のハッシュ値 hval を求める関数のようだ。 しかし、いつまでも hash 値の元となる文字列を伸ばしてもしょうがないだろ う。hval はどこかでまたリセットされるはずだ。っと思ってソースを探して みたがそのような箇所は見当たらない。なぜだろう？考えてみる・・・考えて みたがわからなかった。仕方ないので後にしよう。 ところで、前回、hval の計算とinsert() はセットだと言った。今回はどうだ ろう？次の match_insert() を見てみる。 /* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */ static void match_insert() { ... 省略 ... prev[pos & (dicsiz - 1)] = hash[hval]; hash[hval] = pos; } ・・・強敵であった。強敵すぎたので逃げて、最後の2 行だけに着目した。こ れは、insert()と同じだ。予想は当たっている。get_next() で hval を更新 した後は、この match_insert() で、prev[] と hash[] を更新するわけだ。 そして、match_insert() の省略した部分は、どうやら matchpos, matchlen, too_flag を更新しているだけのようだ。これが本当なら match_insert()で、 insert()の処理をせず、関数を分けるかした方が良さそうだ。(真偽の程は詳 細を見てからになる) おもむろに後続の処理 (H) を見ると、 /* (H) */ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) { これが真なら「見つからなかった状態」と予想した(なぜだろ？)。そして、 lastmatchlen は初期状態では 2 である。予想した条件は逆か？ matchlen ま わりは予想ばかりで進めすぎた。そしてどうやら match_insert() を読みとか なければこの先も分からずじまいになりそうだ。 このまま match_insert() を詳細に解析する事にしよう。 ...ひとまず休む。
Fork