Tsugio Okamoto
tsugi****@muc*****
2003年 1月 6日 (月) 21:01:33 JST
Fork岡本です.
なんか申し訳ないです．少しコメントします．
あと，サンプルコードを送付します．
offは検索を早くするための名残です.lhaを誕生させる試行錯誤した結果です．
もとは，こんなに汚いソースではなかったのです．
> 何も予備知識がない状態で書けば
>
> 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 辞書法のキ
> モである。
はい．
text[i+0] text[i+1] text[i+2]
をハッシュ関数で変換して，ハッシュテーブルに登録します．
で，高速に検索できるようにするというのが工夫です．
lha v1.00を見るとまた違う構造になっていると思います.
> そういうわけで、この部分を読み解くことにする。なお、予備知識として 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
>
> .-----------.
> v |
> +----+-----+--------------------
> prev | |pppos| |ppos| . . .
> +----+-----+--------------------
> `- ppos `-pos
>
> * hash の取り得る値は pos その位置は hval
> * ppos は以前の pos を示す。pppos はさらに以前の 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) )
> & (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[] には、
> 以前のハッシュ値で求めた文字列の位置が入っている。つまり、prev[] はハッ
> シュが衝突したときのためのバッファだ。このハッシュはチェーン法だ。
>
> 例えば、insert() で、
> prev[pos] = hash[hval];
> hash[hval] = pos;
> っと処理をしているのだから
>
> hash[hval] = pos1
> |
> v
> prev[pos1] = pos2
> |
> v
> prev[pos2] = pos3
> ...
>
> といった値が入る事になる。ある文字列(のハッシュ値) hval に対して、その
> 辞書上の位置は pos1, pos2, pos3 という候補があるわけだ。実際にどの 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) )
> & (unsigned)(HSHSIZ - 1);
>
> であり、また、今度のハッシュ関数は、
>
> hval(pos+1) = ( hval(pos) << 5
> ^ x(pos+1 + 2) )
> & (unsigned)(HSHSIZ - 1);
>
> だ、繁雑なので & (HSHSIZE-1) を外すと、
>
> hval(pos+1) = (( x(pos+0) << 5
> ^ x(pos+1) ) << 5
> ^ x(pos+2) ) << 5
> ^ x(pos+3)
>
> っとなる。この次 get_next() が呼び出されれば、
>
> hval(pos+2) = ((( x(pos+0) << 5
> ^ x(pos+1) ) << 5
> ^ x(pos+2) ) << 5
> ^ x(pos+3) ) << 5
> ^ x(pos+4)
>
> である。順にハッシュ値を求める文字列長を増やしている。とにかく、
> get_next() は、pos を進め、remainder を縮め、新たな(以前より1文字長い)
> 文字列のハッシュ値 hval を求める関数のようだ。
>
> しかし、いつまでも hash 値の元となる文字列を伸ばしてもしょうがないだろ
> う。hval はどこかでまたリセットされるはずだ。っと思ってソースを探して
> みたがそのような箇所は見当たらない。なぜだろう？考えてみる・・・最初は
> わからなかったが数式をよく見てみたらわかった。<< 5 が鍵だ、hval(pos+2)
> の式を見ると x(pos+0) は、<< 5 が、4回も行われているつまり、20ビットの
> シフトだ。hval(pos+3) なら、25ビット、hval(pos+4) なら 30 ビットのシフ
> トだ。さすがにこれだけシフトすれば、x(pos+0)の情報は消えてもいいだろう。
>
> 実際、hval は何文字分の情報を持つのだろう？hval は、unsigned int で、
> 普通 32 bit であるから、6.4 文字分だろうか？いや、実際にはハッシュ値の
> 計算時にHSHSIZ (15bit) でマスクをかけているから 15 bit の情報しか持た
> ない。つまり、3文字だ。ビット計算は苦手なので図示して確認しよう。
>
> 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
> hval |--| | | | | | | | | | | | | | | |
> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
>
> 最初の hval(0) は、x(0), x(1), x(2) に対して、
>
> <--- 5 -----> <--- 5 -----> <--- 5 ----->
> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
> x(0) <<10 -- x x x x x
> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
> x(1) << 5 -- x x x x x x x x
> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
> x(2) -- x x x x x x x x
> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
>
> の排他的論理和である。hval(0) の時点で x(0) の情報は 5 ビット残ってい
> るが hval(1) になれば消えてしまうのは自明である。どうにも最初の文字に
> 関しては 5 ビットしか情報を使用しないと言うのが気持悪いのだが、15 bit
> サイズの変数 hval には、過去 3 文字分の情報しか保持されないのは間違い
> ない。get_next() の処理を見れば、位置 pos に対して、hval は常に pos,
> pos+1, pos+2 の情報しか持たないわけだ。これは重要だ。メモしよう
そうです．これは余り多く領域を取ってもあまり効果が
無いし，それよりも当初のMS-DOSでは都合のいい値だった
ためです．で，最小一致が3なのは？
> ----------------------------------------------------------------------------
> * hval hash[]のインデックス。現在位置 pos に対して、
> text[pos], text[pos+1], text[pos+2] のハッシュ値で、論理的には
> hval == text[pos] + text[pos+1] + text[pos+2]
> と同義
> ----------------------------------------------------------------------------
>
> ところで、前回、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() を詳細に解析する事にしよう。match_insert()
> をすべて再掲する。
>
> /* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */
>
> static void match_insert()
> {
> unsigned int scan_pos, scan_end, len;
> unsigned char *a, *b;
> unsigned int chain, off, h, max;
>
> max = maxmatch; /* MAXMATCH; */
> if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
> matchpos = pos;
>
> off = 0;
> for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
> h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
> }
> if (off == maxmatch - THRESHOLD) off = 0;
> for (;;) {
> chain = 0;
> scan_pos = hash[h];
> scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
> while (scan_pos > scan_end) {
> chain++;
>
> if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
> {
> a = text + scan_pos - off; b = text + pos;
> for (len = 0; len < max && *a++ == *b++; len++);
> }
>
> if (len > matchlen) {
> matchpos = scan_pos - off;
> if ((matchlen = len) == max) {
> break;
> }
> }
> }
> scan_pos = prev[scan_pos & (dicsiz - 1)];
> }
>
> if (chain >= LIMIT)
> too_flag[h] = 1;
>
> if (matchlen > off + 2 || off == 0)
> break;
> max = off + 2;
> off = 0;
> h = hval;
> }
> prev[pos & (dicsiz - 1)] = hash[hval];
> hash[hval] = pos;
> }
>
> まず、初期化部分の前半
>
> max = maxmatch; /* MAXMATCH; */
> if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
> matchpos = pos;
>
> off = 0;
>
> maxmatch は、固定値で 256 だ、だから max も 256
> 2行目の if 文は、これまでしつこいくらいに出て来た条件に似ているが、今
> 回は条件を満たすらしい。これまでは、
>
> if (matchlen > remainder) matchlen = remainder;
>
> という条件だった。そして今回は、
>
> if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
>
> だから、全体的に matchlen の値は、
>
> THRESHOLD-1 <= matchlen <= remainder
>
> つまり、
>
> 2 <= matchlen <= バッファに残ったテキスト長
>
> の範囲に納められるようだ。ここでは、matchlen は下限値を下回るので2 に
> 設定される。次に matchpos, off が初期化され。以下の図の状態になる。
> (pos, remainder は、get_next() で更新されていることに注意)
>
> ----------------------------------------------------------------------------
>
> dicsiz=2^dicbit 2*2^dicbit
> v v txtsiz
> +-------------+-------------+-------------+-------------+---+
> text | | | | | |
> +-------------+-------------+-------------+-------------+---+
> `-pos(=dicsiz+1) <--->
> matchpos(=pos) maxmatch{256}
> off(=0)
>
> <------ remainder ------------>
>
> |--- この位置に最初の ---------|
> データが読まれている
> ----------------------------------------------------------------------------
>
> 初期化部分の後半
>
> for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
> h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
> }
> if (off == maxmatch - THRESHOLD) off = 0;
>
> h は、too_flag[] が今のところすべて0だから hval だ。(too_flag は、h つ
> まり hval をインデックスに取るらしい。hash[] と同じだ。再掲はしないが
> メモに書き加えておこう)
>
> off は、pos の位置からのオフセットのようだ(h を更新する for 文の中身か
> ら)。図もその位置に書いた。最後の if 文は off が上限に達した場合に0 に
> 再初期化している。よくわからないので無視しよう。for 文の中身からh や
> off の用途はどうも先読みしたハッシュ値とその先読みの位置なのではないか
> と想像する。too_flag[] の状態によって先読みすべき値が変わるのだろうか？
>
> とにかく処理の本題に入る事にしよう。まず、この関数に現れる局所変数を列
> 挙しておこう
>
> unsigned int scan_pos, scan_end, len;
> unsigned char *a, *b;
> unsigned int chain, off, h, max;
>
> off, h, max はすでに出て来たので残りは
>
> scan_pos, scan_end, len, a, b, chain
>
> だ、これだけの変数の意味を解読しなくてはならない。変数は状態を表すから、
> その数が多いと言うのはそれだけ複雑な処理だということだ。めげる。
>
> この関数のメインとなるループの中をざっと眺めてみるさらに内部にループが
> ある。ひとまず、二重ループの中身を省略しよう。
>
> for (;;) {
> chain = 0;
> scan_pos = hash[h];
> scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
>
> while (scan_pos > scan_end) {
> chain++;
> ... 略 ...
> }
>
> if (chain >= LIMIT)
> too_flag[h] = 1;
>
> if (matchlen > off + 2 || off == 0)
> break;
> max = off + 2;
> off = 0;
> h = hval;
> }
>
> まず、前半部分から
>
> chain = 0;
> scan_pos = hash[h];
> scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
>
> chain, scan_pos, scan_end はすべて while ループに渡されるべき変数だ。
> さらに、while の後には、scan_pos, scan_end は現れないから(仮に while
> ループが1つの関数だったとすると)これらは while ループ部の引数(入力)だ。
> この2つの変数はどうやりくりしようとも、while ループ部内の状態しか表さ
> ないので、ここでは無視しよう。
>
> while ループの後を見てみると
>
> if (chain >= LIMIT)
> too_flag[h] = 1;
>
> if (matchlen > off + 2 || off == 0)
> break;
> max = off + 2;
> off = 0;
> h = hval;
>
> chain が LIMITを越えた場合、too_flag[h] = 1 としている。chain は、ざっ
> と見て、while ループのカウンタらしいが、LIMIT は 0x100 だ。どうにも例
> 外条件っぽい(LIMITという名前や数値がそう思わせる)のでここでは無視しよ
> う。while ループが 256以上回る可能性がある点だけ心にとどめておこう。
>
> 次の条件では、matchlen と off が条件判断されている。ということはこのど
> ちらか、あるいは両方は while ループの返り値(出力)だ。ざっと
> match_insert()全体を見てみると off は最初とこの直後でしか更新されない
> らしい。つまり、while ループ部の返り値はmatchlen の方だ。
> この条件は for () ループの脱出条件でもある。心にとどめて、次に進む。
>
> max = off + 2;
> off = 0;
> h = hval;
>
> ふむ。よくわからない。しかし注目すべき点はある。off はここで、0 になる
> がこれ以降は off の値は変わらない。つまり、off は最初は何らかの値で
> while ループ部に渡されるが、その次からは、0 だ。この for ループが何度
> 回ろうとも 0 だ。h も同じで最初は何らかの値を持つが、2回目のループ以降、
> h は hval だ。max は、off を 0 にする直前に更新しているから、h や off
> と事なり、3つの状態を持つ、すなわち。maxmatch, off+2, 2 だ。
>
> いや、脱出条件を見てみると off == 0 なら break とある。つまり、この
> for ループはどんなに頑張っても2回しか回らないらしい。やっぱり max も 2
> つの状態しか持たないようだ。
>
> これで、1 回目、2回目に while ループ部に入る直前の状態が書ける。この関
> 数 match_insert() は、while ループ部を1回か2回実行する処理と言うわけだ。
>
> ここで無視していた。while ループ部の入力となる scan_pos, scan_end
> もそれぞれどのような状態になるか書いておく
>
> ----------------------------------------------------------------------------
> < 1回目 >
> h = 何か
> off = 何か
> max = maxmatch
>
> scan_pos = hash[h]
> scan_end = pos + off - dicsiz (あるいは、off)
>
> matchlen = 2
> matchpos = pos
> < 2回目 >
> h = hval
> off = 0
> max = 前の off + 2
>
> scan_pos = hash[hval]
> scan_end = pos - dicsiz (あるいは、0)
>
> matchlen = ?
> matchpos = ?
> ----------------------------------------------------------------------------
>
> 上記は一般化した場合だが、今回(初回)の場合、h や off の値は、hval であ
> り、0 だった。2回目ループのときの状態と同じである。2回のループの違いは
> max の値がmatchpos であるか off+2 (すなわち2)であるかの違いしかないようだ。
>
> ここは、条件を少なくするためにこの場合だけにしぼって処理を考えよう。
> while ループの2回の呼び出しを行う際の状態は以下の通りに書き直せる。
>
> ----------------------------------------------------------------------------
> < 1回目 >
> h = hval
> off = 0
> max = maxmatch
>
> scan_pos = hash[hval]
> scan_end = pos - dicsiz (あるいは、0)
>
> matchlen = 2
> matchpos = pos
> < 2回目 >
> h = hval
> off = 0
> max = 2
>
> scan_pos = hash[hval]
> scan_end = pos - dicsiz (あるいは、0)
>
> matchlen = ?
> matchpos = ?
> ----------------------------------------------------------------------------
>
> うーん、まだ、すっきりしない。何がすっきりしないかというと scan_end の
> 値だ。これが何を意味するのかがよくわからない。scan_pos は、わかるのか？
> というと、わかる。hash[hval]だから現在の文字列と同じ文字列の辞書上の位
> 置だ。さらに、現時点では get_next() で、hval を更新してから insert()
> を行っていないので、hash[hval] には何も入っていない。すなわち 0 だ。
>
> scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
>
> を考えよう。off は、0 だから
>
> scan_end = (pos > dicsiz) ? pos - dicsiz : 0;
>
> なわけだ。さらに、posは現時点で dicbit+1 であるから、1 だ。図に書こう。
>
> ----------------------------------------------------------------------------
>
> dicsiz=2^dicbit 2*2^dicbit
> v v txtsiz
> +-------------+-------------+-------------+-------------+---+
> text | | | | | |
> +-------------+-------------+-------------+-------------+---+
> ^ ^ `-pos(=dicsiz+1)
> | |
> | scan_end はこの辺(1)
> scan_pos はこの辺(0)
>
> h = hval
> off = 0
> max = 2
>
> ----------------------------------------------------------------------------
>
> ついに、text[] バッファの左半分に指しかかる。これが何なのかは現時点で
> は明確に書いてなかったが予想するとこの左半分はズバリ辞書だ。言い切って
> やろう。今まで辞書らしい(dicsizのサイズを持つ)バッファは hash[] や
> prev[] があったが、hash[], prev[] の用途はもう明確である。辞書となり得
> るバッファはもうこの text[] しかないのだ。
>
> さらに、左半分に限らずこの text[] 全体が辞書であろうと予想する。これは
> ただの勘だが text[] は環状バッファなのではなかろうかと考えている。
>
> # 最初の方で prev[] が辞書だと予想したが間違った予想をしていたことにこ
> # の時点で気づいた。prev[] が辞書と同じサイズを持つ理由はまだよくわか
> # らない。
>
> この時点ではまだ scan_pos や scan_end の真の意味はわからない。off のこ
> とを無視しているから予想も立ちにくいが、ひとまず初期状態がどういったも
> のかはわかったのでこのまま、while ループ部を見てみたいと思う。
>
> while (scan_pos > scan_end) {
> chain++;
>
> if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
> {
> a = text + scan_pos - off; b = text + pos;
> for (len = 0; len < max && *a++ == *b++; len++);
> }
>
> if (len > matchlen) {
> matchpos = scan_pos - off;
> if ((matchlen = len) == max) {
> break;
> }
> }
> }
> scan_pos = prev[scan_pos & (dicsiz - 1)];
> }
>
> まず、if 文の条件を満たさない場合だけを考える。
>
> while (scan_pos > scan_end) {
> chain++;
>
> if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
> ...
> }
> scan_pos = prev[scan_pos & (dicsiz - 1)];
> }
>
>
> offは 0 なので、text[scan_pos + matchlen] != text[pos + matchlen] という条件の場合を想定するわけだが、
>
> text[scan_pos + matchlen]
>
> と
>
> text[pos + matchlen]
>
> を比べている
>
> text[scan_pos] 辞書上の文字列の*先頭*
> text[pos] 現在の文字列の*先頭*
>
> を比べないのは matchlen が前に予想した「最低限一致しなければならない長さ-1」
> だからであろう。現時点で、matchlen が 2 だから
>
> text[scan_pos + 0] == text[pos + 0]
> text[scan_pos + 1] == text[pos + 1]
>
> であったとしても、
>
> text[scan_pos + 2] != text[pos + 2]
>
> であれば、「最低限一致しなければならない長さ」という条件を満たさないの
> である。なので matchlen の位置から先に比較して無駄な比較をしないように
> している。後でちゃんとした比較の処理が出て来るだろう。このような処理は
> 処理としては効率が良いのだが、ことソース理解と言う点では冗長である。わ
> かりにくいのだ。仕方ないのだけど。
>
> # matchlen の意味の予想はどうやら当たっているようだ。matchlen は最短一
> # 致長で、minmatchlen っと名付けても良さそうな変数だ。
>
> そして、比較に失敗したら scan_pos を更新する。
>
> scan_pos = prev[scan_pos & (dicsiz - 1)];
>
> ハッシュのチェーンをたどっている、つまり次の候補を辞書から取り出してい
> るわけだ。ここまでで、while ループの処理内容の想像はついた。このループ
> は辞書から(最長)一致する文字列を探しているのだろう。
>
> 順番が前後したが、while ループの脱出条件を見てみる
>
> while (scan_pos > scan_end) {
>
> これはどういうことだろう？ scan_pos は、ハッシュのチェーンをたどって同
> じハッシュ値を持つ文字列の位置を探す、この値はだんだんと小さくなって行
> くものなのだろうか？
> その通りである。hash[] への格納はファイルから取って来た文字列を順に格
> 納して行くのでチェーンの奥には、より前の方の位置が書かれているはずだ。
> 逆にチェーンの浅い部分にはより現在位置に近い、位置が書かれているのだろ
> う。では、その境界 scan_end はどうやってわかるのだろうか？これは後でま
> た検証しよう。
>
> では、処理の本質 if 文の中を見る事にしよう
>
> if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
> {
> a = text + scan_pos - off; b = text + pos;
> for (len = 0; len < max && *a++ == *b++; len++);
> }
>
> if (len > matchlen) {
> matchpos = scan_pos - off;
> if ((matchlen = len) == max) {
> break;
> }
> }
> }
>
> 最初の意味もなくブロックになっている部分を見る、
>
> {
> a = text + scan_pos - off; b = text + pos;
> for (len = 0; len < max && *a++ == *b++; len++);
> }
>
> この処理では a, b といういかにも局所な名前の変数が使われている。これは、
> 本当にこのブロック内にで局所的なもののようだ。ならば定義位置もこのブロッ
> ク内にして本当に局所的にして欲しかった。
>
> さらに、この処理は単に文字列 a, b を比較しているだけのようだ。memcmp()
> ではまずいのかと言うとここで求めているものが「どこまで一致したか(len)」
> のようなので、memcmp() では役不足だ。仕方ないので関数をでっちあげて抽
> 象化をはかろう。memcmp_ret_len()(我ながら変な名前だ)という関数があった
> とするとこの部分は
> len = memcmp_ret_len(&text[scan_pos-off], &text[pos], max);
>
> っとなる。返り値は一致した文字列長だ。
>
> その次の処理、
>
> if (len > matchlen) {
> matchpos = scan_pos - off;
> if ((matchlen = len) == max) {
> break;
> }
> }
>
> で、matchlen (最低一致長)より大きい場合に条件を満たす。条件を満たさな
> ければ、scan_pos を更新し、次のループに移る。では、条件を満たす場合を
> 見てみよう。まず最短一致長の一致条件を満たした場合、matchpos と
> matchlen を更新する。
>
> matchpos はマッチした位置、
> matchlen はマッチした長さ
>
> で、matchlen が max なら最長一致長に達しているので、これ以上探索はしな
> い。matchlen は最短一致長でありながら、一致長でもある変数のようだ。
> (どうやら以前の2つの予想はどちらも当たっていた模様)
>
> とにかく while ループ部の出力は、この matchpos と matchlen のようだ。
> 前に書いた通りこのループは「最長一致文字列を求める処理」だ。
>
> match_insert() の全体をもう一度見てみよう。ただし、以下の書き換えを行う。
>
> o while ループ部は search_dict(pos, scan_pos, scan_end, max) という関数
> に置き換えたものとする。
>
> o 末尾の insert() と同等の処理を行っている部分も insert() の呼び出しに
> すり替えよう。(match_insert() 関数の中で insert() 処理を本当に行うべ
> きものなのかどうかが疑問だが)
>
> o chain という変数にかかわる処理も隠した(search_dict内で行う)
>
> o for ループは、2回しかまわらないので、2 度の search_dict() の呼び出し
> に書き換える
>
> static void match_insert()
> {
> unsigned int off, h, max;
> unsigned int scan_end;
>
> max = maxmatch; /* MAXMATCH; */
> if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
> matchpos = pos;
>
> off = 0;
> for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
> h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
> }
> if (off == maxmatch - THRESHOLD)
> off = 0;
>
> scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
> search_dict(pos, hash[h], scan_end, maxmatch);
>
> if (matchlen <= off + 2) {
> off = 0;
> h = hval;
>
> scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
> search_dict(pos, hash[h], scan_end, off+2);
> }
>
> insert();
> }
>
> だいぶすっきりした(が、まだ繁雑だ)。まだ、off にかかわる部分がよく分か
> らないが、ひとまず良いだろう。この関数の解析はこれで終って良いだろうか。
>
> いや、良くない。肝心の match_insert() の出力がよくわからない。この関数
> は「最長一致文字列を探し、hash を更新する処理」(くどいようだが、hashを
> 更新するは余計に思う)なのだろうが、最長一致文字列が見つからなかったと
> いうのはどう判断されるのだろう？
>
> まず、search_dict() で見つからなかった場合、matchlen, matchpos は更新
> されない。そして、おそらく 2 度目の search_dict() の呼び出しが行われる。
> が、too_flag[] というので、判断できそうな気もするがこれはむしろハッシュ
> のチェーンをたどりすぎるのを止めるためのフラグであるように思える。
>
> 2度目の search_dict()で、max の値が変わるのが鍵だろうか？。今回の場合、
> max は 256 から 2 になる。最長一致長として 2 が限界値になると、
> search_dict() の動作は変わるだろうか？いや、やはり変わらない。どうにも
> この関数だけでは見つかったか見つからなかったかという判断はできないよう
> だ。(本当はわかっているはずなのにその情報を直接外に持ち出していない)
>
> 気持悪いがやはりこの関数の解析を終え、次に移る事にしよう。
>
> (H) である。以前、
>
> (H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
>
> (H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
> (H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
>
> っと予想した部分だ。今や match_insert() は、解析済みだからこれの真偽が
> わかるか？というとやっぱり、わからない。ただ、
> matchlen > lastmatchlen
> というのは、辞書から文字列が見つかった場合の条件になりそうだから、やはり
> これは予想が逆だろうか？とにかく、比較的簡単そうな、(H.1) から見よう。
>
> if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
> /* (H.1) */
> encode_set.output(text[pos - 1], 0);
> count++;
> } else {
>
> どうも、文字 text[pos-1] を出力しているだけのように思える。文字の出力
> は、slide 辞書法では「辞書から見つからなかった場合」を意味するから、や
> はり最初の予想はあってそうなのだが・・・仕方ないので、output()の処理を
> 除いて見よう。これは、lh5, 6, 7 の場合、huf.c:output_st1(c, p) である。
> 現時点で処理の内容を見てもわけがわからないが、結論から言うと第一引数 c
> は、文字で、第二引数 p は、位置である。冒頭の decode 処理で、文字 c は
> 長さも兼ねていると説明済みなので、(そして、text[pos-1] には現時点で文
> 字そのものしか書かれていない)これはやはり文字を出力している処理だ。つ
> まり「見つからなかった場合」の処理だ。
>
> なぜ、pos-1 なのだろう？確かに Huffman coding に文字を渡すのはこれが初
> めてで、現在 pos の位置はバッファの1文字進んだ位置にある。pos-1 は出力
> しなければならないのは当然だ。ということは pos は常に「未出力文字の位
> 置 + 1」なのかもしれない。
辞書を検索してtext[pos-1]よりもtext[pos]から比較した方が長く
一致するケースがあったため，２回検索して長く一致したら，先に
text[pos-1]で辞書に一致したとしてもそれを使わずに長いほうを
選ぶということをしたらしいです．
> 次の count++ を見る。count はどうやらこの関数の変数ではないらしい、困っ
> た事に局所変数の名前っぽいがグローバル変数だ。これはよろしくない。ちょっ
> と grep しただけでは、他にどこでこの変数を使っているのかわからなかった。
> まあ、今 1 文字を渡した所なので、入力文字数なのだと仮定しておこう。こ
> の変数が大勢に影響を与える事はないだろうからこれ以上は見ないと言うのも
> アリだ。
>
> 次は (H.2) である。これがまた難解なのだがゆっくり片付けよう。
>
> } 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;
> }
>
> まず、output() に渡している引数は、それぞれ「長さ」と「位置」であろう
> ことは予想済みだ。さらに UCHAR_MAX{255} + 1 - THRESHOLD{3} だから
>
> 長さ lastmatchlen + 253
> 位置 lastmatchoffset & (dicsiz-1)
>
> となっている。冒頭の decode() の解析で、長さは 253 を足す事は確認済み
> だ(ふと -lhs- の場合 254 を足すという動作が、encoding 部分では考慮され
> ていないようだと気づく。いいのかそれで？)。ところで、一致長
> lastmatchlen は 3 以上で初めて 255 を越えることができる。以前予想した、
> THRESHOLD の意味「最低限一致しなければならない長さ」はあっているらしい。
>
> もう一点、注意しなくてはならないのは、出力しているのが lastmatchlen と
> lastmatchoffset である。これらは、match_insert() のときには更新してい
> ない(last〜の更新は次のループの先頭 (E) で行われる)。先程 (H.1) のとき
> も書き出していたのは、text[pos-1] であった。pos 位置は一歩先読みした位
> 置を指すらしい。このような処理を行う場合、最後に調整が必要なはずだ(で
> ないと最後の文字が出力されない)。その調整はどこで行われるのだろう？
>
> さて、後続の処理だが、<長さ、位置>のペアを出力した後は、
>
> --lastmatchlen;
>
> while (--lastmatchlen > 0) {
> get_next(); insert();
> count++;
> }
>
> という処理を行っている。get_next() は、pos を進める処理、insert() は辞
> 書に登録する処理だから、これは文字列を読み飛ばしている処理だ。確かに
> lastmatchlen 分の情報は出力済みだから、これは納得である。lastmatchlen
> を 1 余分に引いているのが謎だがこれは pos が一歩先に進んでいるからであ
> ろうと予想する。つまり、この後は pos の位置はまた「現在位置」に戻る。
> なるほど、先程調整が必要と書いたがここで行われているらしい。細部は不明
> だが少なくとも辞書に文字列が見つかった場合は最後まで出力されるようだ。
>
> 次に進もう
>
> get_next();
> matchlen = THRESHOLD - 1;
> match_insert();
> if (matchlen > remainder) matchlen = remainder;
>
> せっかく pos が現在の位置に戻ったのに、get_next() でまた先読みされた。
> うーむ。そして、matchlen は初期化される。一致情報はすでに出力済みだか
> らこれはうなずける。そして、match_insert() が呼ばれる。この時点で再度
> 辞書が検索される。pos はまた1文字進んでいるのだから、これは先程(初期状
> 態)のmatch_insert() と大差ない処理だ。(その直後のif文は境界条件なので
> 無視)
>
> そうして、また次のループに移る。このとき続けざま get_next(),
> match_insert() が行われる。どうやら pos は次のループからは、 2 文字文
> 先に進んでしまうようだ。なぜだろう？
>
> どうにもソースを見ただけで解読するには、このあたりが限界のようだ。どう
> しても細部がわからないし、事実が見えないから予想の積み重ねがたまって不
> 安になる。
>
> 実は、もう少しマメに図を起こして読み進んで行けばもっとわかることがあっ
> ただろうと思うのだが、それは面倒だし、間違える可能性がある(ここまでで
> 何度か痛い思いをした)。以降は、いくつかのデータを実際に圧縮させその動
> きをデバッガで追うことで、これまでの解析結果を検証してみよう。
>
> ・・・っと、その前に、ここまでですべての関数を網羅してしまったと思って
> たのだが、一つ忘れていたものがあった。update() だ。この関数は、
> get_next() で呼び出されていたのだが、以前は無視していた。先にここを見
> ておこう。
>
> まず、get_next() を再掲する。
>
> static void get_next()
> {
> remainder--;
> if (++pos >= txtsiz - maxmatch) {
> update();
> }
> hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
> }
>
> remainder と pos を進めた後、pos が txtsiz - maxmatch に達してしまった
> 場合(pos == 2 * 2^dicbit の場合)に呼び出されるようだ。つまり、以下の図
> の状態だ。これが、update() を呼び出す時の初期状態だ。
>
> ----------------------------------------------------------------------------
>
> dicsiz=2^dicbit 2*2^dicbit
> v v txtsiz
> +-------------+-------------+-------------+-------------+---+
> text | | | | | |
> +-------------+-------------+-------------+-------------+---+
> /<--->
> / maxmatch{256}
> pos
>
> <-->
> remainder
>
> ----------------------------------------------------------------------------
>
> では、update() に入る。
>
> static void update()
> {
> unsigned int i, j;
> unsigned int k;
> long n;
>
> #if 0
> memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
> #else
> {
> int m;
> i = 0; j = dicsiz; m = txtsiz-dicsiz;
> while (m-- > 0) {
> text[i++] = text[j++];
> }
> }
> #endif
> n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)],
> (unsigned)dicsiz, infile);
>
> remainder += n;
> encoded_origsize += n;
>
> pos -= dicsiz;
> for (i = 0; i < HSHSIZ; i++) {
> j = hash[i];
> hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
> too_flag[i] = 0;
> }
> for (i = 0; i < dicsiz; i++) {
> j = prev[i];
> prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
> }
> }
>
> 先頭で、なぜか memmove() を for ループで書き換えている。なぜこのような
> ことを行っているのだろう。for ループを見てみてもやっていることは変わら
> ない。謎だが、とにかく、text[] の右半分(maxmatch 部分も含む) を左に移
> している。
多分ここを触ったのは私です．
> 次に fread_crc() で、新たにファイルを読み込む。今度の読み込み位置は
> &text[txtsiz - dicsiz] で、長さは dicsiz である。当然、remainder も更
> 新している。encoded_origsize は以前と同様無視。pos は dicsiz 分減らさ
> れている。これはつまり図示すると、以下の状態になると言う事だ
>
> ----------------------------------------------------------------------------
>
> dicsiz=2^dicbit 2*2^dicbit
> v v txtsiz
> +-------------+-------------+---+---------+-------------+---+
> text | | | | | | |
> +-------------+-------------+---+---------+-------------+---+
> /<---> <--->
> / maxmatch{256} maxmatch{256}
> pos
>
> <------------------------------>
> remainder
> |------- 以前のデータ ---------|--- 新しいデータ ---------|
>
> ----------------------------------------------------------------------------
>
> 以降、ファイルの読み込みは常にこの update()でしか行われない。pos は、
> 初期状態と同じ位置なので、初期状態が再現されている。ここまでで、
> maxmatch の領域はなんだろうと思うが、おそらく先読みのためだろう。それ
> らしい処理は、match_insert() の冒頭にあった(が、現時点で詳細には触れて
> いない)。
>
> update() の残りを見る。
>
> for (i = 0; i < HSHSIZ; i++) {
> j = hash[i];
> hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
> too_flag[i] = 0;
> }
> for (i = 0; i < dicsiz; i++) {
> j = prev[i];
> prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
> }
>
> 内容は、想像がつくので詳細は省略しよう。単に以前のデータが移動したので、
> ハッシュ値を更新しているだけだ。しかし、これはなかなか無駄な処理だ。
>
> 以前、text[] は環状バッファだろうと予想したが予想がはずれたことがわかっ
> た。環状バッファにしていれば、このハッシュの書き換えは不要にできただろ
> うと思うのだが・・・
> # そのかわり、位置の大小比較が繁雑にならないので、これはこれで良いのか
> # もしれない。どちらが優れているかは実験してみなければわからないだろう。
これは辞書から消える文字列に該当するハッシュ値をハッシュリスト
から消すためと思いました.
無くても大丈夫ですか？
> これで、一応は slide.c を網羅する事ができた。まだ不明な点は多いが、デ
> バッガで実際の処理を追いかければまたわかることがあるだろう。
>
>
> # Local Variables:
> # mode : indented-text
> # indent-tabs-mode: nil
> # End:
>
On Mon, 06 Jan 2003 00:20:16 +0900 (JST)
Koji Arai <JCA02****@nifty*****> wrote:
> 新井です。
>
> 更新。この資料は、lha の CVS リポジトリに登録した。
>
> Index: Hackinf_of_LHa
-----------------------------------------------------
Tsugio Okamoto (E-Mail:tsugi****@muc*****)