Hacking_of_LHa

   1 $Id$
   2
   3                The Hacking of LHa for UNIX (3rd draft)
   4              -------------------------------------------
   5
   6                                 Koji Arai <arai@users.sourceforge.jp>
   7
   8 本書は、LHa for UNIX 1.14i のソースを解読し、その圧縮アルゴリズムの実
   9 装を確認するためのものだ。この成果は別の形でまとめなおされ資料になるか
  10 もしれないし、このままの形で保管されるかもしれないし、新たにソースを書
  11 き起こす元になるかもしれない。とにかく、暇な正月休みを潰すためにやって
  12 みただけのものだ。(休みが明けるとまた忙しくなるので、これ以上まったく
  13 何もしないかもしれない)
  14
  15 本書は、まだ未完成である。にもかかわらず公開するのはこれ以上続かないか
  16 もしれないからである(気が向いたらまた続きを書くだろう。あるいは応援の
  17 お手紙がくればやる気が出るかもしれない)。
  18
  19 本書はフリーである。複製、改変、再配布は自由であるということだ。ただし
  20 本書により生じたあらゆる損害、不利益に対しては一切の保証はない。本書に
  21 は嘘があるかもしれない。それに対して嘘を教えられたと著者を避難をしない
  22 で頂きたい。しかし間違いの指摘は構わない(ぜひお願いしたい)、著者は圧縮
  23 処理に関しては無知である。用語の使い方等は適切でないかもしれないのでこ
  24 の方面でも御指導頂ければ幸いである。
  25
  26 < 目次 >
  27
  28 表記について
  29 slide 辞書法 (slide.c)
  30 bit 入出力ルーチン (crcio.c)
  31 Huffman 法 (huf.c)
  32 LHA ファイルの構造(まとめ)
  33 セキュリティバグの考察
  34
  35 ===============================================================================
  36 表記について
  37
  38 * 関数は、その定義ソース file.c と関数名 func() を示すのに
  39      file.c:func()
  40   という記述を使う
  41
  42 * 配列の添字は、Python言語のスライス演算子の記法に準じた
  43
  44     a[m:n] は、m <= i < m+n の範囲の a[i] を意味する。
  45
  46 * 値の範囲は、Ruby言語の範囲演算子の記法に準じた。これを配列の
  47   添字に使用する場合もある。
  48
  49     m <= i <= n   -> i = m..n
  50     m <= i < n    -> i = m...n
  51
  52     a[m..n] は、m <= i <= n の範囲の a[i] を意味する。
  53
  54 * m の n 乗 は、m^n で表す。^ は、排他的論理和としても利用されるが
  55   文脈から判断してもらう。
  56
  57 * v{n} は、変数 v の値が n であることを表す。n は、サンプルの値であったり
  58   定数の値であったりする。
  59
  60   v=n は代入文
  61
  62   配列の内容は、
  63     ary[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }
  64   のように書く
  65
  66 o 用語について
  67
  68 * 符号
  69         符号化、符号語、圧縮文
  70
  71         符号語は、1つの文字を符号化した結果。圧縮文は符号語の並び。
  72
  73 * 復号
  74         復号化、復号語、復号文
  75
  76         復号語は、圧縮文から1つの文字を復号化した結果。復号文は復号語の並び。
  77
  78 * 平文
  79         圧縮前の文を示す。対して復号文は、復号した後の文を意味する。
  80
  81 * slide 辞書法
  82
  83 * Huffman 法
  84    動的 Huffman 法、静的 Huffman 法
  85
  86 ===============================================================================
  87
  88 \f
  89 slide 辞書法 (slide.c)
  90 ----------------------
  91
  92 まず、構造について考える。
  93
  94 slide辞書法は、encoding にさまざまな工夫が凝らされるのでとても複雑だが、
  95 普通 decoding は単純である。decoding を解析することでどのような圧縮文
  96 を作っているのかを調べてみる。
  97
  98 decoding を行う処理は、slide.c の decode() である。この処理を見てみる
  99 と思った通り簡単に解読できた(以下)
 100
 101   1. huffman coding により復号した文字を環状バッファ dtext に書き込む
 102      通常の文字 c は、c < 256 で表現されている(つまりそのまま)
 103
 104   2. 通常の文字でないものが現れたら、それは長さである。長さ len は、
 105      len > 255 で表現されている。len から 0xfd(253) を引いた値が
 106      実際の長さを表す(-lzs- method の場合は、0xfe(254)を引く)
 107     「長さ」が、現れたらその直後には「位置」が書かれているのでそれを
 108      読む。こうして、長さと位置のペア<len, pt>を得る
 109
 110      dtext から pt+1 バイト前の len バイトを読み、dtext に追加で書き込む
 111
 112    3. dtext が一杯(dicsiz)になったらファイルに書き出す
 113
 114 これの繰り返しである。つまり、slide 辞書法の圧縮文は、文字 c と<len,
 115 pt> の並びであることがわかる。例えば、文字列 c1 c2 c1 c2 は、以下のよ
 116 うに表現されているはずである。(本当は、長さが 2 以下では圧縮が起こらな
 117 いので平文のまま出力する。長さは最低でも 3 は必要)
 118
 119         +----+----+--------+
 120         | c1 | c2 | <2, 1> |
 121         +----+----+--------+
 122
 123 では、この構造を作成する圧縮処理について考える。slide 辞書法では、ファ
 124 イルから読み込んだ文字列 token が、以前に読み込んだ辞書に存在すれば
 125 <len, pt> のペアを出力し、存在しなければ token をそのまま出力する。読
 126 み込んだ token は、辞書に追加し、辞書の語が溢れたら古い情報を捨てる。
 127
 128 何も予備知識がない状態で書けば
 129
 130         while (read_file(&token, tokensiz)) {
 131           len = search_dict(dict, token, &pt);
 132           if (len == -1) {
 133             print_token(token);
 134           else
 135             print_pair(len, pt);
 136           update_dict(dict, token);
 137         }
 138
 139 のようになるはず。ここで、tokensiz は token の最大サイズで、最長一致長
 140 を表す。この値が大きければ大きい程、圧縮効率は良くなるはずで、lha では、
 141 これは MAXMATCH{256}である。また、dict は辞書でこのサイズは lha の
 142 -lh5- メソッドでは、8192 となっている。この辞書も大きければ大きい程良
 143 いはずだ。その方が一致文字列が見つかりやすい。(ただし、辞書が大きいと
 144 一致位置を示す情報 <len, pt> の情報量が増えるはずだし、速度も遅くなる
 145 だろう。後で検証する)
 146
 147 で、実際にソースを見てみると(slide.c:encode())・・・、まったくこのよう
 148 な構造にはなってないように見える。何やらややこしいことばかりでまったく
 149 わからない。なぜここまでややこしいのかと泣きたくなってくるが、それは速
 150 度のためである(本当？)。上記のコードで、search_dict() は、単に dict か
 151 ら token に一致する位置を検索するだけで良さそう(実際にそれでも良い)だ
 152 が、これではまったく速度が出ない。このあたりの工夫が slide 辞書法のキ
 153 モである。
 154
 155 そういうわけで、この部分を読み解くことにする。なお、予備知識として lha
 156 では、辞書から token を探すのにハッシュが使われているらしいことを記し
 157 ておく。
 158
 159 ここでは実際にデバッガで動作させながら解読するのではなく、ソースを読む
 160 だけで理解できるかを試すことにする。また、本文は某書(謎)のノリをマネて
 161 いると指摘する方がいるかもしれない・・・がまったくその通りだ。
 162
 163 まず、そのものずばりの encode() (slide.c) を見る。以下がこの関数だが
 164 処理の要点だけに着目するために不要そうな部分は(現時点で予測で)削った。
 165
 166 unsigned int
 167 encode()
 168 {
 169     int lastmatchlen;
 170     unsigned int lastmatchoffset;
 171
 172     /* (A) */
 173     init_slide();
 174
 175     /* (B) */
 176     remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
 177     encoded_origsize = remainder;
 178     matchlen = THRESHOLD - 1;
 179
 180     pos = dicsiz;
 181
 182     if (matchlen > remainder) matchlen = remainder;
 183
 184     /* (C) */
 185     hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
 186             ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
 187
 188     /* (D) */
 189     insert();
 190
 191     while (remainder > 0 && ! unpackable) {
 192         /* (E) */
 193         lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
 194         --matchlen;
 195
 196         /* (F) */    /* (G) */
 197         get_next();  match_insert();
 198         if (matchlen > remainder) matchlen = remainder;
 199
 200         /* (H) */
 201         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
 202             /* (H.1) */
 203             encode_set.output(text[pos - 1], 0);
 204             count++;
 205         } else {
 206             /* (H.2) */
 207             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
 208                (lastmatchoffset) & (dicsiz-1) );
 209             --lastmatchlen;
 210
 211             while (--lastmatchlen > 0) {
 212                 get_next();  insert();
 213                 count++;
 214             }
 215             get_next();
 216             matchlen = THRESHOLD - 1;
 217             match_insert();
 218             if (matchlen > remainder) matchlen = remainder;
 219         }
 220     }
 221 }
 222
 223 まず、この関数から概観を見てみると、ループの前に初期化処理として
 224 以下が行われている。
 225
 226 (A) init_slide() 初期化する
 227 (B) ファイルを読み込み text[] に格納する。
 228 (C) ハッシュ値 hval を計算する。
 229 (D) insert() する (きっと辞書に token を追加しているのだろう)
 230
 231 そして、ループ処理では以下の処理が行われている
 232
 233 (E) lastmatchlen, lastmatchoffset, matchlen を更新する。
 234 (F) get_next()  (次の token を読む。たぶん)
 235 (G) match_insert()  (辞書に追加する。たぶん)
 236
 237 (H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
 238
 239 (H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
 240 (H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
 241
 242 現時点で、(H.2) の部分はよく解読できなかった。何やら再度 get_next() が
 243 呼ばれていたりして思った通りの処理フローにはなっていない。だが、ここで
 244 は焦らず放置することにして、ここまで予想で書いた部分の細部に触れること
 245 にする(単にここまでの予想が間違っているだけかもしれないのだから、わか
 246 らない部分を無理にわかるように頑張る必要はなかろう)
 247
 248 関数の細部に触れる前にデータ構造について調べておく。データ構造に対して
 249 の理解が深まればアルゴリズムの80%は分かったも同然だ(誇張)。slide.c で
 250 使用されているデータ構造は以下の通りだ。(不要そうだと思うものは除いて
 251 ある)
 252
 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;
 259 static int matchlen;
 260 static unsigned int matchpos;
 261 static unsigned int pos;
 262 static unsigned int remainder;
 263
 264 too_flag だけ、static がついてないが、他のソースを grep してもこの変数
 265 を使っている箇所はない、単に static の付け忘れだろう。
 266
 267 これらの変数は、encode() の冒頭 init_slide() で初期化されている・・の
 268 かと思ったら違った。slide.c:encode_alloc() で行われている。
 269
 270 int
 271 encode_alloc(method)
 272     int method;
 273 {
 274     if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
 275         encode_set = encode_define[0];
 276         maxmatch = 60;
 277         dicbit = 12;   /* 12 Changed N.Watazaki */
 278     } else { /* method LH4(12),LH5(13),LH6(15) */
 279         encode_set = encode_define[1];
 280         maxmatch = MAXMATCH;
 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 */
 287     }
 288
 289     dicsiz = (((unsigned long)1) << dicbit);
 290     txtsiz = dicsiz*2+maxmatch;
 291
 292     if (hash) return method;
 293
 294     if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
 295
 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);
 300
 301     if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
 302         exit(207);
 303
 304     return method;
 305 }
 306
 307 引数に渡された method (これは、lh1, lh5, lh6, lh7 などを示す)によって、
 308 初期化される内容が変わる(encode_alloc()前半部分)。このことから各変数の
 309 用途もわかる。
 310
 311         method  maxmatch     dicbit
 312         ----------------------------
 313         -lh1-       60         12
 314         -lh5-      256         13
 315         -lh6-      256         15
 316         -lh7-      256         16
 317
 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 のことしか言及しない)
 323
 324 encode_set, encode_define というのがあるが、method によって、Huffman
 325 coding の方法を変えていることはちょっと見ればすぐにわかるし、大したこ
 326 とではない。以降無視する。
 327
 328 encode_alloc() の後半では、他の変数の初期化(バッファの割り当て)が行われる。
 329
 330     dicsiz = (((unsigned long)1) << dicbit);
 331
 332 dicsiz はそのものずばり辞書サイズである。
 333
 334     txtsiz = dicsiz*2+maxmatch;
 335
 336 現時点で txtsiz が何なのかはわからない。
 337
 338     if (hash) return method;
 339
 340 hash はこの直後で割り当てられる。つまり、一度割当を行ったら、
 341 encode_alloc() は、以降メモリの割当を行わない。ただそれだけだ。
 342
 343     if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
 344
 345 alloc_buf() は、huf.c で定義された関数。このことから Huffman coding の
 346 ためのバッファを割り当てているのだろう。ここでは無視。(しかし、207 と
 347 いうのは何なのだろう？)
 348
 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);
 353
 354     if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
 355         exit(207);
 356
 357 hash は、ハッシュ用の何か、HSHSIZ は、固定値で 2^15 である。
 358
 359 prev は、DICSIZから辞書だろう。要素の型が char でなく int であることに
 360 も注目しておく。DICSIZ は dicsiz でも構わないはず。単に「大は小を兼ね
 361 る」を実践しているだけであろう、TXTSIZ も同様である。おそらく、一度の
 362 実行で複数の圧縮メソッドを使用した場合、そのメソッド毎に領域を割り当て
 363 るよりは最大の値をあらかじめ一度だけ割り当てた方が良いと考えたのだろう。
 364 しかし、ソースを参照するときは繁雑になるので以降、
 365    DICSIZ == dicsiz
 366    TXTSIZ == txtsiz
 367 であるとする。これ重要。
 368
 369 text は、現時点では不明
 370
 371 too_flag も不明
 372
 373 っとなる。まだ、良く分からないが、以下の図を書いておこう。後で何度も見
 374 ることになるだろう。この図はスケールが lh7 の場合を想定しているが。こ
 375 のことは大したことではないはずだ。また、too_flag と hash のスケールが
 376 一緒だがこれはサイズ(領域のバイト数)が一緒なのではなく、要素数が一緒で
 377 あることを示している。ほとんどの場合要素の型の違いというのは処理内容に
 378 とって重要なことではないはずだ。
 379
 380 ----------------------------------------------------------------------------
 381
 382        0            2^15=32768
 383        +-------------+
 384   hash |             |
 385        +-------------+          dicsiz=2^dicbit
 386        +-------------+-------------+                          2*2^dicbit
 387   prev |             |             |                           |
 388        +-------------+-------------+                           v   txtsiz
 389        +-------------+-------------+-------------+-------------+---+
 390   text |             |             |             |             |   |
 391        +-------------+-------------+-------------+-------------+---+
 392                                                                <--->
 393                                                                 maxmatch{256}
 394   too_flag           2^15
 395        +-------------+
 396        |             |
 397        +-------------+
 398 ----------------------------------------------------------------------------
 399
 400
 401 先に示した変数の中でまだ初期化には現れていないものがある。列挙すると
 402
 403 static unsigned int hval;
 404 static int matchlen;
 405 static unsigned int matchpos;
 406 static unsigned int pos;
 407 static unsigned int remainder;
 408
 409 だ、ざっとソースを眺めると slide.c:insert() という関数に
 410         hash[hval] = pos;
 411 というのが現れているから、hval は、hash[] の位置を指し、hash には、pos
 412 を格納すると推測される。同様に
 413         prev[pos & (dicsiz - 1)] = hash[hval];
 414 というのも現れているから pos は、prev[] の位置を指し、prev には、
 415 hash[hval] つまり、pos を格納しているようだ。これは少し謎な処理だが、
 416 insert() の全貌は短い(というかこれだけ)なので、ちょっと横道にそれて詳
 417 細に見てみよう。(現在の解析の趣旨は、変数の用途の概要を予想すること)
 418
 419 /* 現在の文字列をチェーンに追加する */
 420
 421 static void insert()
 422 {
 423     prev[pos & (dicsiz - 1)] = hash[hval];
 424     hash[hval] = pos;
 425 }
 426
 427 コメントはまったく意味不明だが、無視して処理内容に着目する。prev[] の
 428 インデックス pos & (dicsiz - 1) は、dicsiz が 2^n であることからdicsiz
 429 はビットマスクであることがわかる。例えば仮に dicsiz が 2^8 だと
 430 dicsiz - 1 は、
 431
 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
 436
 437 である。このすべて 1 が立ったビットマスクと pos を & すると、どのよう
 438 な pos の値に対しても pos & (dicsiz - 1) は、prev[] のインデックスの範
 439 囲に納まる。もう少し言うと pos が仮にインデックスの最大値+1だった場合、
 440 pos & (dicsiz - 1) は、0 になる。これにより次の予想が立つ。
 441
 442   o pos が、prev[] の位置を指すのではなく、pos & (dicsiz - 1) が
 443     prev[]の位置を指す。(pos は、このインデックスの範囲を越える可能性がある)
 444   o それに反して、prev[] は環状バッファらしいという予想が立てばやはり
 445     pos は、prev のインデックスである。
 446
 447 prev が環状バッファであると予想が付けば話が早い。pos & (dicsiz-1) は、
 448 pos と同義だと解釈可能だからである(prev が環状バッファでなく無限長のバッ
 449 ファであると想像しよう)そして、pos & (dicsiz-1) を pos に置き換えて、
 450 再度処理内容に着目すると
 451
 452     prev[pos] = hash[hval];
 453     hash[hval] = pos;
 454
 455 ということから、
 456     1. (この関数に来る前に) pos が更新される。(予想)
 457     2. prev[pos] に以前の hash[hval] (以前の pos)を格納する
 458     3. hash[hval] に新しい pos を書く。
 459 といった処理であることが予想される。コメントの「チェーン」もなんとなく
 460 納得できる。新たな事実(まだ予想だが)が分かったので、図に書き記そう。
 461
 462 ----------------------------------------------------------------------------
 463        0            2^15=32768
 464        +-+---+-------+
 465   hash | |pos|...    |
 466        +-+---+-------+
 467          `-hval
 468
 469               .-----------.
 470              v            |
 471        +----+-----+--------------------
 472   prev |    |pppos|      |ppos|        . . .
 473        +----+-----+--------------------
 474             `- ppos      `-pos
 475
 476   * hash の取り得る値は pos その位置は hval
 477   * ppos は以前の pos を示す。pppos はさらに以前の pos を指す。
 478   * prev は無限長のバッファ(本当は環状バッファ)
 479 ----------------------------------------------------------------------------
 480
 481 まだ、解析できてない変数が残っている。
 482
 483 static int matchlen;
 484 static unsigned int matchpos;
 485 static unsigned int remainder;
 486
 487 しかしこれらはどうにもパッと見ではわからない。処理内容を追いかけないと
 488 だめそうだ。仕方ないので変数名で予想しよう。(幸い前の変数名と違って予
 489 想しやすい)以下
 490
 491 ----------------------------------------------------------------------------
 492  * matchlen     一致した文字列長
 493  * matchpos     一致した辞書上の位置
 494  * remainder    token の残りサイズ
 495 ----------------------------------------------------------------------------
 496
 497 はたして、予想はあっているのか、今はまだ分からない。
 498
 499 slide.c を見る限りデータ構造は網羅できた。結局分かったのか分からないの
 500 か良く分からないが少しずつでも前進はしているはずだ。ここで、再度
 501 encode() の処理を追いかけよう。今度は細部にも着目する。
 502
 503 前に、encode() のソースには (A) 〜 (H) までの記号を記した。この順番に
 504 解析を進めよう。
 505
 506     /* (A) */
 507     init_slide();
 508
 509 まあ、初期化である。内容を見てみると
 510
 511     for (i = 0; i < HSHSIZ; i++) {
 512         hash[i] = NIL;
 513         too_flag[i] = 0;
 514     }
 515
 516 だけである。NIL というのは、0 であると slide.c で定義されている。普通
 517 このような初期値は、通常の値が取り得ない値を示している。NIL が 0 なら
 518 hash[] に格納される pos は 0 にならない可能性がある。まあ、予想ばかり
 519 書いても仕方ないので、この関数は終ろう。余談だが、nil は null と同じで。
 520 「ない」の意味だが、NULL がC言語ではポインタだから。別のマクロ名にした
 521 のかも知れない。いずれにしてもこの程度はマクロにする必要もなかろうとは
 522 思うのは、余計なお世話かもしれない。
 523
 524     /* (B) */
 525     remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
 526     encoded_origsize = remainder;
 527     matchlen = THRESHOLD - 1;
 528
 529     pos = dicsiz;
 530
 531     if (matchlen > remainder) matchlen = remainder;
 532
 533 ファイルを読み込み、各変数の初期値を設定している。注目すべきはファイル
 534 を読み込んだバッファの位置である。fread_crc() は、crcio.c で定義された
 535 汎用関数で、CRC値を計算したり漢字コード変換をしたりを除けば、fread()
 536 と同じである。つまり、ファイルは最初、
 537
 538   &text[dicsiz] の位置に、txtsiz-dicsiz 分だけ読まれる。
 539
 540 ことを示す。図示しよう。
 541
 542 ----------------------------------------------------------------------------
 543 < 初期状態 >
 544
 545                                 dicsiz=2^dicbit               2*2^dicbit
 546                                    v                           v   txtsiz
 547        +-------------+-------------+-------------+-------------+---+
 548   text |             |             |             |             |   |
 549        +-------------+-------------+-------------+-------------+---+
 550                                    `-pos                       <--->
 551                                                                 maxmatch{256}
 552
 553                                    <------ remainder -------------->
 554
 555                                    |--- この位置に最初の  ---------|
 556                                         データが読まれている
 557 ----------------------------------------------------------------------------
 558
 559 ますます、text[] の用途が不明だが、slide 辞書法の典型的な読み込み処理
 560 のことを考えるとある程度予想がつく(それを先に示した方が良いか？)。まあ、
 561 ここではフーンっと鼻で納得して済まそう。
 562
 563 fread_crc() は、読み込んだバッファ長を返す。remainder がその値で、既に
 564 図示してある。encoded_origsize は、ソースを見ると、元のファイルのサイ
 565 ズを表すためだけの変数のようだ。以降は無視しよう。
 566
 567 ところで、ファイルサイズが小さい場合図の通りにならないっと考えるかも知
 568 れない。その通りなのだが、例外条件は少ない方がソースは理解しやすい。単
 569 純な場合だけを考えた方が、あれこれ考えをめぐらす必要がないからだ。なに
 570 しろ既に動くソースを見ているのだから、細かいことに目をつぶってもエンバ
 571 グすることはないのである。そういうわけで、当面はこの図が唯一の初期状態
 572 であると考える。
 573
 574 (B) の部分はもう少し注目すべき箇所がある。
 575
 576     matchlen = THRESHOLD - 1;
 577
 578 matchlen は、「一致した文字列長」であると予想したが THRESHOLD の値は 3
 579 (固定値)であるから、matchlen の初期値は 2 だ。いきなり予想がはずれた気
 580 がする。予想を立て直そう。2 という謎な数値と match*len* について考える
 581 と、冒頭で <len, pt> のペアの len は 2 であることはないと説明した。無
 582 意味だからであるが、matchlen の初期値はこの 2 と関連するかもしれない。
 583 そこで、matchlen の用途を以下のように予想しなおすことにする。以下のよ
 584 うにメモを更新しよう。THRESHOLD(threshold は閾値の意)も一緒に予想した。
 585
 586 ----------------------------------------------------------------------------
 587 * matchlen      最低限一致しなければならない長さ-1
 588 * THRESHOLD     最低限一致しなければならない長さ
 589 ----------------------------------------------------------------------------
 590
 591 うーん、本当だろうか？
 592
 593 (B) の残りの部分を片付けよう
 594
 595     pos = dicsiz;
 596
 597     if (matchlen > remainder) matchlen = remainder;
 598
 599 pos が dicsiz であることからどうやら、pos は、text[] のインデックスら
 600 しい。前の予想で pos は、prev[] のインデックスでもあり、hash[] の値で
 601 もあると予想したのだが(これはもちろん間違いではなかろうが)。どうやら
 602 本当の意味は、処理するテキストの先頭を示しているのではないかとも思える。
 603 まあ、ここでは無難に「text[] のインデックス(でもある)」とだけ理解しよう。
 604 既に図には書き込んである。
 605
 606 次の if だが、remainder が matchlen よりも小さい場合の条件だ。また、
 607 matchlen の予想が覆されそうな予感がしないでもないが、この if 文は*例外
 608 条件*なので無視することにした。都合の悪いことは見ない方が良いのだ。
 609
 610     /* (C) */
 611     hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
 612             ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
 613
 614 (C) である。これは難解である。複雑な数式は苦手であるが、じっくり考えよ
 615 う。まず求める値は hval である。これは hash[] のインデックスなのだが、
 616 このような複雑な式で求まるインデックスなんて想像もつかない。まず、最初
 617 のインスピレーションを大事にすることにしよう。冒頭で、(C) の処理は「ハッ
 618 シュ値 hval を計算する。」っと苦もなく予想した。そしてこれは間違いでは
 619 ないだろう(きっと)。hash[] との関連をここで考えてもわからないから、こ
 620 のハッシュ値の計算だけを考えることにしよう。
 621
 622 式をじっくり見てみる。。。じっくり見てみると以下のことがわかる。
 623
 624         x(i) = text[dicsiz + i]
 625 とすると
 626         hval = (( x(0) << 5
 627                 ^ x(1)      ) << 5
 628                 ^ x(2)             )
 629                & (unsigned)(HSHSIZ - 1);
 630
 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) の処理も見るが、
 642
 643     /* (D) */
 644     insert();
 645
 646 insert() は、幸い解読ずみである pos を hash[] に格納する処理だ。
 647 予想の段階では、(C) と (D) を別個の処理と考えていたのだがこれは
 648 どうやらセットである。
 649
 650    (C) pos の位置の 3 文字のハッシュ値を計算し
 651    (D) hash[ハッシュ値] = pos を行う
 652
 653 もう少し注意深く検討すると「posの位置の3文字」と、求めた「ハッシュ値」
 654 は論理的には = である。
 655
 656 つまり、(C) (D) の処理は
 657
 658   hash[文字列] = 位置
 659
 660 という処理を行っている。ハッシュ値の衝突はここでは考えない。slide 辞書
 661 法では、ある文字列に対し以前その文字列が現れたかどうかを検索し、その位
 662 置を求める必要があるのだが、この最初の 3 文字に関しては現時点でその用
 663 件(位置を求める)を満たす事ができている。ここまでで自ずと encode() の全
 664 体像も予想がつきそうな気がする。
 665
 666 衝突は考えないっとしたが、ちょっと考えたらすぐわかった。prev[] には、
 667 以前のハッシュ値で求めた文字列の位置が入っている。つまり、prev[] はハッ
 668 シュが衝突したときのためのバッファだ。このハッシュはチェーン法だ。
 669
 670 例えば、insert() で、
 671     prev[pos] = hash[hval];
 672     hash[hval] = pos;
 673 っと処理をしているのだから
 674
 675         hash[hval] = pos1
 676                       |
 677                       v
 678                 prev[pos1] = pos2
 679                               |
 680                               v
 681                          prev[pos2] = pos3
 682                                 ...
 683
 684 といった値が入る事になる。ある文字列(のハッシュ値) hval に対して、その
 685 辞書上の位置は pos1, pos2, pos3 という候補があるわけだ。実際にどの pos
 686 を選ぶかは比較によって行われるのだろう。
 687
 688 # それにつけても、(C) と (D) の部分を見るだけでもこのソースがちょっと
 689 # 汚いことがわかる。もう少し、引数とか戻り値とか考えてくれても良かっ
 690 # たはずだ。ハッシュ関数にしても少なくともマクロぐらいにはしようよ。
 691
 692 (E) 〜 (H) に移ろうこれはループの中身で、処理の本題だ。まずループの脱
 693 出条件を見てみると
 694
 695     while (remainder > 0 && ! unpackable) {
 696
 697 remainder は、バッファ上に読み込んだ平文の長さであるからこれがなくなる
 698 までループすることになる。さらに unpackable というのは、crcio.c の
 699 putcode() でその値を設定している箇所が出て来るのだが、符号化した出力サ
 700 イズが元のサイズを越えたときに真になる。つまり、これ以上処理しても圧縮
 701 の意味がないとわかったらループを抜けるわけだ。
 702
 703 では、(E)を見よう。
 704
 705         /* (E) */
 706         lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
 707         --matchlen;
 708
 709 ちょっと見ただけではやはりわからない。これらの変数はまだ予想しかしてな
 710 いからである。が、わかるだけの情報は書きしるそう。
 711
 712 ----------------------------------------------------------------------------
 713 * lastmatchlen    以前の matchlen の値 (変数名から)
 714 * lastmatchoffset 以前マッチした位置 (変数名から)
 715 ----------------------------------------------------------------------------
 716
 717 以前の値をlast〜に退避し、新たな値を設定する準備をしているわけだ。そし
 718 て、「新たな値の設定」は、--matchlen で早速行われている。しかし、「マッ
 719 チした長さ」をまだ何もしてないのに -1 するというのはいったいどういうこ
 720 とだろう？ matchlen はループの頭で 2 に設定されている。これが 1 になっ
 721 た。本当の初期値は 1 なのか？
 722
 723 ----------------------------------------------------------------------------
 724 < 各変数の初期値 >
 725
 726   matchlen = 1
 727   matchpos = 0
 728   pos = dicsiz
 729
 730   lastmatchlen = 2
 731   lastmatchoffset = dicsiz - 1  (pos - matchpos - 1)
 732 ----------------------------------------------------------------------------
 733
 734 この (E) はまた後で見る事になるだろう。
 735
 736 (F) (G) である。また、その直後には以前にも見た境界条件がある。
 737
 738         /* (F) */    /* (G) */
 739         get_next();  match_insert();
 740         if (matchlen > remainder) matchlen = remainder;
 741
 742 if 文 は無視して関数の中身だけを追いかけてみよう。まず、get_next() こ
 743 れは 次の token を取ってくる処理だと予想してある。はたしてどうだろうか？
 744
 745 static void get_next()
 746 {
 747     remainder--;
 748     if (++pos >= txtsiz - maxmatch) {
 749         update();
 750     }
 751     hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
 752 }
 753
 754 remainder を消費し、pos を進めている。予想通りだ。ひとまず if の条件は
 755 無視すると、直後で hash 値を求め直している。このハッシュ関数は、以前のハッ
 756 シュ値を利用しているが、これは pos が以前より + 1 されていることを考え
 757 ると関連が見えて来る。以前のhash関数を pos の関数として書き直すと
 758
 759         x(pos+i) = text[pos + i]
 760
 761         hval(pos) = (( x(pos+0) << 5
 762                      ^ x(pos+1)      ) << 5
 763                      ^ x(pos+2)             )
 764                     & (unsigned)(HSHSIZ - 1);
 765
 766 であり、また、今度のハッシュ関数は、
 767
 768         hval(pos+1) = ( hval(pos) << 5
 769                        ^ x(pos+1 + 2)  )
 770                       & (unsigned)(HSHSIZ - 1);
 771
 772 だ、繁雑なので & (HSHSIZE-1) を外すと、
 773
 774         hval(pos+1) = (( x(pos+0) << 5
 775                        ^ x(pos+1)      ) << 5
 776                        ^ x(pos+2)             ) << 5
 777                        ^ x(pos+3)
 778
 779 っとなる。この次 get_next() が呼び出されれば、
 780
 781         hval(pos+2) = ((( x(pos+0) << 5
 782                         ^ x(pos+1)      ) << 5
 783                         ^ x(pos+2)             ) << 5
 784                         ^ x(pos+3)                    ) << 5
 785                         ^ x(pos+4)
 786
 787 である。順にハッシュ値を求める文字列長を増やしている。とにかく、
 788 get_next() は、pos を進め、remainder を縮め、新たな(以前より1文字長い)
 789 文字列のハッシュ値 hval を求める関数のようだ。
 790
 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)の情報は消えてもいいだろう。
 798
 799 実際、hval は何文字分の情報を持つのだろう？hval は、unsigned int で、
 800 普通 32 bit であるから、6.4 文字分だろうか？いや、実際にはハッシュ値の
 801 計算時にHSHSIZ (15bit) でマスクをかけているから 15 bit の情報しか持た
 802 ない。つまり、3文字だ。ビット計算は苦手なので図示して確認しよう。
 803
 804                  15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
 805                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 806           hval  |--|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
 807                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 808
 809 最初の hval(0) は、x(0), x(1), x(2) に対して、
 810
 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                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 819
 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 の情報しか持たないわけだ。これは重要だ。メモしよう
 826
 827 ----------------------------------------------------------------------------
 828  * hval  hash[]のインデックス。現在位置 pos に対して、
 829          text[pos], text[pos+1], text[pos+2] のハッシュ値で、論理的には
 830              hval == text[pos] + text[pos+1] + text[pos+2]
 831          と同義
 832 ----------------------------------------------------------------------------
 833
 834 ところで、前回、hval の計算とinsert() はセットだと言った。今回はどうだ
 835 ろう？次の match_insert() を見てみる。
 836
 837 static void match_insert()
 838 {
 839     ... 省略 ...
 840
 841     prev[pos & (dicsiz - 1)] = hash[hval];
 842     hash[hval] = pos;
 843 }
 844
 845 ・・・強敵であった。強敵すぎたので逃げて、最後の2 行だけに着目した。こ
 846 れは、insert()と同じだ。予想は当たっている。get_next() で hval を更新
 847 した後は、この match_insert() で、prev[] と hash[] を更新するわけだ。
 848 そして、match_insert() の省略した部分は、どうやら matchpos, matchlen,
 849 too_flag を更新しているだけのようだ。これが本当なら match_insert()で、
 850 insert()の処理をせず、関数を分けるかした方が良さそうだ。(真偽の程は詳
 851 細を見てからになる)
 852
 853 おもむろに後続の処理 (H) を見ると、
 854
 855         /* (H) */
 856         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
 857
 858 これが真なら「見つからなかった状態」と予想した(なぜだろ？)。そして、
 859 lastmatchlen は初期状態では 2 である。予想した条件は逆か？ matchlen ま
 860 わりは予想ばかりで進めすぎた。そしてどうやら match_insert() を読みとか
 861 なければこの先も分からずじまいになりそうだ。
 862
 863 このまま match_insert() を詳細に解析する事にしよう。match_insert()
 864 をすべて再掲する。
 865
 866 /* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */
 867
 868 static void match_insert()
 869 {
 870     unsigned int scan_pos, scan_end, len;
 871     unsigned char *a, *b;
 872     unsigned int chain, off, h, max;
 873
 874     max = maxmatch; /* MAXMATCH; */
 875     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
 876     matchpos = pos;
 877
 878     off = 0;
 879     for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
 880         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
 881     }
 882     if (off == maxmatch - THRESHOLD) off = 0;
 883     for (;;) {
 884         chain = 0;
 885         scan_pos = hash[h];
 886         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
 887         while (scan_pos > scan_end) {
 888             chain++;
 889
 890             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
 891                 {
 892                     a = text + scan_pos - off;  b = text + pos;
 893                     for (len = 0; len < max && *a++ == *b++; len++);
 894                 }
 895
 896                 if (len > matchlen) {
 897                     matchpos = scan_pos - off;
 898                     if ((matchlen = len) == max) {
 899                         break;
 900                     }
 901                 }
 902             }
 903             scan_pos = prev[scan_pos & (dicsiz - 1)];
 904         }
 905
 906         if (chain >= LIMIT)
 907             too_flag[h] = 1;
 908
 909         if (matchlen > off + 2 || off == 0)
 910             break;
 911         max = off + 2;
 912         off = 0;
 913         h = hval;
 914     }
 915     prev[pos & (dicsiz - 1)] = hash[hval];
 916     hash[hval] = pos;
 917 }
 918
 919 まず、初期化部分の前半
 920
 921     max = maxmatch; /* MAXMATCH; */
 922     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
 923     matchpos = pos;
 924
 925     off = 0;
 926
 927 maxmatch は、固定値で 256 だ、だから max も 256
 928 2行目の if 文は、これまでしつこいくらいに出て来た条件に似ているが、今
 929 回は条件を満たすらしい。これまでは、
 930
 931     if (matchlen > remainder) matchlen = remainder;
 932
 933 という条件だった。そして今回は、
 934
 935     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
 936
 937 だから、全体的に matchlen の値は、
 938
 939     THRESHOLD-1 <= matchlen <= remainder
 940
 941 つまり、
 942
 943               2 <= matchlen <= バッファに残ったテキスト長
 944
 945 の範囲に納められるようだ。ここでは、matchlen は下限値を下回るので2 に
 946 設定される。次に matchpos, off が初期化され。以下の図の状態になる。
 947 (pos, remainder は、get_next() で更新されていることに注意)
 948
 949 ----------------------------------------------------------------------------
 950
 951                                 dicsiz=2^dicbit               2*2^dicbit
 952                                    v                           v   txtsiz
 953        +-------------+-------------+-------------+-------------+---+
 954   text |             |             |             |             |   |
 955        +-------------+-------------+-------------+-------------+---+
 956                                      `-pos(=dicsiz+1)          <--->
 957                                        matchpos(=pos)           maxmatch{256}
 958                                        off(=0)
 959
 960                                      <------ remainder ------------>
 961
 962                                    |--- この位置に最初の  ---------|
 963                                         データが読まれている
 964 ----------------------------------------------------------------------------
 965
 966 初期化部分の後半
 967
 968     for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
 969         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
 970     }
 971     if (off == maxmatch - THRESHOLD) off = 0;
 972
 973 h は、too_flag[] が今のところすべて0だから hval だ。(too_flag は、h つ
 974 まり hval をインデックスに取るらしい。hash[] と同じだ。再掲はしないが
 975 メモに書き加えておこう)
 976
 977 off は、pos の位置からのオフセットのようだ(h を更新する for 文の中身か
 978 ら)。図もその位置に書いた。最後の if 文は off が上限に達した場合に0 に
 979 再初期化している。よくわからないので無視しよう。for 文の中身からh や
 980 off の用途はどうも先読みしたハッシュ値とその先読みの位置なのではないか
 981 と想像する。too_flag[] の状態によって先読みすべき値が変わるのだろうか？
 982
 983 とにかく処理の本題に入る事にしよう。まず、この関数に現れる局所変数を列
 984 挙しておこう
 985
 986     unsigned int scan_pos, scan_end, len;
 987     unsigned char *a, *b;
 988     unsigned int chain, off, h, max;
 989
 990 off, h, max はすでに出て来たので残りは
 991
 992   scan_pos, scan_end, len, a, b, chain
 993
 994 だ、これだけの変数の意味を解読しなくてはならない。変数は状態を表すから、
 995 その数が多いと言うのはそれだけ複雑な処理だということだ。めげる。
 996
 997 この関数のメインとなるループの中をざっと眺めてみるさらに内部にループが
 998 ある。ひとまず、二重ループの中身を省略しよう。
 999
1000     for (;;) {
1001         chain = 0;
1002         scan_pos = hash[h];
1003         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1004
1005         while (scan_pos > scan_end) {
1006             chain++;
1007             ... 略 ...
1008         }
1009
1010         if (chain >= LIMIT)
1011             too_flag[h] = 1;
1012
1013         if (matchlen > off + 2 || off == 0)
1014             break;
1015         max = off + 2;
1016         off = 0;
1017         h = hval;
1018     }
1019
1020 まず、前半部分から
1021
1022         chain = 0;
1023         scan_pos = hash[h];
1024         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1025
1026 chain, scan_pos, scan_end はすべて while ループに渡されるべき変数だ。
1027 さらに、while の後には、scan_pos, scan_end は現れないから(仮に while
1028 ループが1つの関数だったとすると)これらは while ループ部の引数(入力)だ。
1029 この2つの変数はどうやりくりしようとも、while ループ部内の状態しか表さ
1030 ないので、ここでは無視しよう。
1031
1032 while ループの後を見てみると
1033
1034         if (chain >= LIMIT)
1035             too_flag[h] = 1;
1036
1037         if (matchlen > off + 2 || off == 0)
1038             break;
1039         max = off + 2;
1040         off = 0;
1041         h = hval;
1042
1043 chain が LIMITを越えた場合、too_flag[h] = 1 としている。chain は、ざっ
1044 と見て、while ループのカウンタらしいが、LIMIT は 0x100 だ。どうにも例
1045 外条件っぽい(LIMITという名前や数値がそう思わせる)のでここでは無視しよ
1046 う。while ループが 256以上回る可能性がある点だけ心にとどめておこう。
1047
1048 次の条件では、matchlen と off が条件判断されている。ということはこのど
1049 ちらか、あるいは両方は while ループの返り値(出力)だ。ざっと
1050 match_insert()全体を見てみると off は最初とこの直後でしか更新されない
1051 らしい。つまり、while ループ部の返り値はmatchlen の方だ。
1052 この条件は for () ループの脱出条件でもある。心にとどめて、次に進む。
1053
1054         max = off + 2;
1055         off = 0;
1056         h = hval;
1057
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 だ。
1064
1065 いや、脱出条件を見てみると off == 0 なら break とある。つまり、この
1066 for ループはどんなに頑張っても2回しか回らないらしい。やっぱり max も 2
1067 つの状態しか持たないようだ。
1068
1069 これで、1 回目、2回目に while ループ部に入る直前の状態が書ける。この関
1070 数 match_insert() は、while ループ部を1回か2回実行する処理と言うわけだ。
1071
1072 ここで無視していた。while ループ部の入力となる scan_pos, scan_end
1073 もそれぞれどのような状態になるか書いておく
1074
1075 ----------------------------------------------------------------------------
1076 < 1回目 >
1077    h = 何か
1078    off = 何か
1079    max = maxmatch
1080
1081    scan_pos = hash[h]
1082    scan_end = pos + off - dicsiz  (あるいは、off)
1083
1084    matchlen = 2
1085    matchpos = pos
1086 < 2回目 >
1087    h = hval
1088    off = 0
1089    max = 前の off + 2
1090
1091    scan_pos = hash[hval]
1092    scan_end = pos - dicsiz  (あるいは、0)
1093
1094    matchlen = ?
1095    matchpos = ?
1096 ----------------------------------------------------------------------------
1097
1098 上記は一般化した場合だが、今回(初回)の場合、h や off の値は、hval であ
1099 り、0 だった。2回目ループのときの状態と同じである。2回のループの違いは
1100 max の値がmatchpos であるか off+2 (すなわち2)であるかの違いしかないようだ。
1101
1102 ここは、条件を少なくするためにこの場合だけにしぼって処理を考えよう。
1103 while ループの2回の呼び出しを行う際の状態は以下の通りに書き直せる。
1104
1105 ----------------------------------------------------------------------------
1106 < 1回目 >
1107    h = hval
1108    off = 0
1109    max = maxmatch
1110
1111    scan_pos = hash[hval]
1112    scan_end = pos - dicsiz  (あるいは、0)
1113
1114    matchlen = 2
1115    matchpos = pos
1116 < 2回目 >
1117    h = hval
1118    off = 0
1119    max = 2
1120
1121    scan_pos = hash[hval]
1122    scan_end = pos - dicsiz  (あるいは、0)
1123
1124    matchlen = ?
1125    matchpos = ?
1126 ----------------------------------------------------------------------------
1127
1128 うーん、まだ、すっきりしない。何がすっきりしないかというと scan_end の
1129 値だ。これが何を意味するのかがよくわからない。scan_pos は、わかるのか？
1130 というと、わかる。hash[hval]だから現在の文字列と同じ文字列の辞書上の位
1131 置だ。さらに、現時点では get_next() で、hval を更新してから insert()
1132 を行っていないので、hash[hval] には何も入っていない。すなわち 0 だ。
1133
1134         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1135
1136 を考えよう。off は、0 だから
1137
1138         scan_end = (pos > dicsiz) ? pos - dicsiz : 0;
1139
1140 なわけだ。さらに、posは現時点で dicbit+1 であるから、1 だ。図に書こう。
1141
1142 ----------------------------------------------------------------------------
1143
1144                                 dicsiz=2^dicbit               2*2^dicbit
1145                                    v                           v   txtsiz
1146        +-------------+-------------+-------------+-------------+---+
1147   text |             |             |             |             |   |
1148        +-------------+-------------+-------------+-------------+---+
1149        ^ ^                           `-pos(=dicsiz+1)
1150        | |
1151        | scan_end はこの辺(1)
1152        scan_pos はこの辺(0)
1153
1154    h = hval
1155    off = 0
1156    max = 2
1157
1158 ----------------------------------------------------------------------------
1159
1160 ついに、text[] バッファの左半分に指しかかる。これが何なのかは現時点で
1161 は明確に書いてなかったが予想するとこの左半分はズバリ辞書だ。言い切って
1162 やろう。今まで辞書らしい(dicsizのサイズを持つ)バッファは hash[] や
1163 prev[] があったが、hash[], prev[] の用途はもう明確である。辞書となり得
1164 るバッファはもうこの text[] しかないのだ。
1165
1166 さらに、左半分に限らずこの text[] 全体が辞書であろうと予想する。これは
1167 ただの勘だが text[] は環状バッファなのではなかろうかと考えている。
1168
1169 # 最初の方で prev[] が辞書だと予想したが間違った予想をしていたことにこ
1170 # の時点で気づいた。prev[] が辞書と同じサイズを持つ理由はまだよくわか
1171 # らない。
1172
1173 この時点ではまだ scan_pos や scan_end の真の意味はわからない。off のこ
1174 とを無視しているから予想も立ちにくいが、ひとまず初期状態がどういったも
1175 のかはわかったのでこのまま、while ループ部を見てみたいと思う。
1176
1177         while (scan_pos > scan_end) {
1178             chain++;
1179
1180             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1181                 {
1182                     a = text + scan_pos - off;  b = text + pos;
1183                     for (len = 0; len < max && *a++ == *b++; len++);
1184                 }
1185
1186                 if (len > matchlen) {
1187                     matchpos = scan_pos - off;
1188                     if ((matchlen = len) == max) {
1189                         break;
1190                     }
1191                 }
1192             }
1193             scan_pos = prev[scan_pos & (dicsiz - 1)];
1194         }
1195
1196 まず、if 文の条件を満たさない場合だけを考える。
1197
1198         while (scan_pos > scan_end) {
1199             chain++;
1200
1201             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1202                 ...
1203             }
1204             scan_pos = prev[scan_pos & (dicsiz - 1)];
1205         }
1206
1207
1208 offは 0 なので、text[scan_pos + matchlen] != text[pos + matchlen] とい
1209 う条件の場合を想定するわけだが、
1210
1211 text[scan_pos + matchlen]
1212
1213 と
1214
1215 text[pos + matchlen]
1216
1217 を比べている
1218
1219 text[scan_pos]  辞書上の文字列の*先頭*
1220 text[pos]       現在の文字列の*先頭*
1221
1222 を比べないのは matchlen が前に予想した「最低限一致しなければならない長さ-1」
1223 だからであろう。現時点で、matchlen が 2 だから
1224
1225 text[scan_pos + 0] == text[pos + 0]
1226 text[scan_pos + 1] == text[pos + 1]
1227
1228 であったとしても、
1229
1230 text[scan_pos + 2] != text[pos + 2]
1231
1232 であれば、「最低限一致しなければならない長さ」という条件を満たさないの
1233 である。なので matchlen の位置から先に比較して無駄な比較をしないように
1234 している。後でちゃんとした比較の処理が出て来るだろう。このような処理は
1235 処理としては効率が良いのだが、ことソース理解と言う点では冗長である。わ
1236 かりにくいのだ。仕方ないのだけど。
1237
1238 # matchlen の意味の予想はどうやら当たっているようだ。matchlen は最短一
1239 # 致長で、minmatchlen っと名付けても良さそうな変数だ。
1240
1241 そして、比較に失敗したら scan_pos を更新する。
1242
1243             scan_pos = prev[scan_pos & (dicsiz - 1)];
1244
1245 ハッシュのチェーンをたどっている、つまり次の候補を辞書から取り出してい
1246 るわけだ。ここまでで、while ループの処理内容の想像はついた。このループ
1247 は辞書から(最長)一致する文字列を探しているのだろう。
1248
1249 順番が前後したが、while ループの脱出条件を見てみる
1250
1251         while (scan_pos > scan_end) {
1252
1253 これはどういうことだろう？ scan_pos は、ハッシュのチェーンをたどって同
1254 じハッシュ値を持つ文字列の位置を探す、この値はだんだんと小さくなって行
1255 くものなのだろうか？
1256 その通りである。hash[] への格納はファイルから取って来た文字列を順に格
1257 納して行くのでチェーンの奥には、より前の方の位置が書かれているはずだ。
1258 逆にチェーンの浅い部分にはより現在位置に近い位置が書かれているのだろ
1259 う。では、その境界 scan_end はどうやってわかるのだろうか？これは後でま
1260 た検証しよう。
1261
1262 では、処理の本質 if 文の中を見る事にしよう
1263
1264             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1265                 {
1266                     a = text + scan_pos - off;  b = text + pos;
1267                     for (len = 0; len < max && *a++ == *b++; len++);
1268                 }
1269
1270                 if (len > matchlen) {
1271                     matchpos = scan_pos - off;
1272                     if ((matchlen = len) == max) {
1273                         break;
1274                     }
1275                 }
1276             }
1277
1278 最初の意味もなくブロックになっている部分を見る、
1279
1280                 {
1281                     a = text + scan_pos - off;  b = text + pos;
1282                     for (len = 0; len < max && *a++ == *b++; len++);
1283                 }
1284
1285 この処理では a, b といういかにも局所な名前の変数が使われている。これは、
1286 本当にこのブロック内で局所的なもののようだ。ならば定義位置もこのブロッ
1287 ク内にして本当に局所的にして欲しかった。
1288
1289 さらに、この処理は単に文字列 a, b を比較しているだけのようだ。memcmp()
1290 ではまずいのかと言うとここで求めているものが「どこまで一致したか(len)」
1291 のようなので、memcmp() では役不足だ。
1292
1293 その次の処理、
1294
1295                 if (len > matchlen) {
1296                     matchpos = scan_pos - off;
1297                     if ((matchlen = len) == max) {
1298                         break;
1299                     }
1300                 }
1301
1302 で、matchlen (最低一致長)より大きい場合に条件を満たす。条件を満たさな
1303 ければ、scan_pos を更新し、次のループに移る。では、条件を満たす場合を
1304 見てみよう。まず最短一致長の一致条件を満たした場合、matchpos と
1305 matchlen を更新する。
1306
1307 matchpos はマッチした位置、
1308 matchlen はマッチした長さ
1309
1310 で、matchlen が max なら最長一致長に達しているので、これ以上探索はしな
1311 い。matchlen は最短一致長でありながら、一致長でもある変数のようだ。
1312 (どうやら以前の2つの予想はどちらも当たっていた模様)
1313
1314 とにかく while ループ部の出力は、この matchpos と matchlen のようだ。
1315 前に書いた通りこのループは「最長一致文字列を求める処理」だ。
1316
1317 match_insert() の全体をもう一度見てみよう。ただし、以下の書き換えを行う。
1318
1319 o while ループ部は search_dict(pos, scan_pos, scan_end, max) という関数
1320   に置き換えたものとする。
1321
1322 o 末尾の insert() と同等の処理を行っている部分も insert() の呼び出しに
1323   すり替えよう。(match_insert() 関数の中で insert() 処理を本当に行うべ
1324   きものなのかどうかが疑問だが)
1325
1326 o chain という変数にかかわる処理も隠した(search_dict内で行う)
1327
1328 o for ループは、2回しかまわらないので、2 度の search_dict() の呼び出し
1329   に書き換える
1330
1331 static void match_insert()
1332 {
1333     unsigned int off, h;
1334     unsigned int scan_end;
1335
1336     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
1337     matchpos = pos;
1338
1339     off = 0;
1340     for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
1341         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1342     }
1343     if (off == maxmatch - THRESHOLD)
1344         off = 0;
1345
1346     scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1347     search_dict(pos, hash[h], scan_end, maxmatch);
1348
1349     if (off > 0 && matchlen <= off + 2) {
1350       off = 0;
1351
1352       scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1353       search_dict(pos, hash[hval], scan_end, off+2);
1354     }
1355
1356     insert();
1357 }
1358
1359 だいぶすっきりした(が、まだ繁雑だ)。まだ、off にかかわる部分がよく分か
1360 らないが、ひとまず良いだろう。この関数の解析はこれで終って良いだろうか。
1361
1362 いや、良くない。肝心の match_insert() の出力がよくわからない。この関数
1363 は「最長一致文字列を探し、hash を更新する処理」(くどいようだが、hashを
1364 更新するは余計に思う)なのだろうが、最長一致文字列が見つからなかったと
1365 いうのはどう判断されるのだろう？
1366
1367 まず、search_dict() で見つからなかった場合、matchlen は更新されない
1368 (matchpos は、pos になる)。そして、おそらく 2 度目の search_dict() の
1369 呼び出しが行われる。が、too_flag[] というので、判断できそうな気もする
1370 がこれはむしろハッシュのチェーンをたどりすぎるのを止めるためのフラグで
1371 あるように思える。
1372
1373 2度目の search_dict()で、max の値が変わるのが鍵だろうか？。今回の場合、
1374 max は 256 から 2 になる。最長一致長として 2 が限界値になると、
1375 search_dict() の動作は変わるだろうか？いや、やはり変わらない。どうにも
1376 この関数だけでは見つかったか見つからなかったかという判断はできないよう
1377 だ。(本当はわかっているはずなのにその情報を直接外に持ち出していない)
1378
1379 気持悪いがやはりこの関数の解析を終え、次に移る事にしよう。
1380
1381 (H) である。以前、
1382
1383 (H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
1384
1385 (H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
1386 (H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
1387
1388 っと予想した部分だ。今や match_insert() は、解析済みだからこれの真偽が
1389 わかるか？というとやっぱり、わからない。ただ、
1390         matchlen > lastmatchlen
1391 というのは、辞書から文字列が見つかった場合の条件になりそうだから、やはり
1392 これは予想が逆だろうか？とにかく、比較的簡単そうな、(H.1) から見よう。
1393
1394         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
1395             /* (H.1) */
1396             encode_set.output(text[pos - 1], 0);
1397             count++;
1398         } else {
1399
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 字そのものしか書かれていない)これはやはり文字を出力している処理だ。つ
1408 まり「見つからなかった場合」の処理だ。
1409
1410 なぜ、pos-1 なのだろう？確かに Huffman coding に文字を渡すのはこれが初
1411 めてで、現在 pos の位置はバッファの1文字進んだ位置にある。pos-1 は出力
1412 しなければならないのは当然だ。ということは pos は常に「未出力文字の位
1413 置 + 1」なのかもしれない。
1414
1415 次の count++ を見る。count はどうやらこの関数の変数ではないらしい、困っ
1416 た事に局所変数の名前っぽいがグローバル変数だ。これはよろしくない。ちょっ
1417 と grep しただけでは、他にどこでこの変数を使っているのかわからなかった。
1418 まあ、今 1 文字を渡した所なので、入力文字数なのだと仮定しておこう。こ
1419 の変数が大勢に影響を与える事はないだろうからこれ以上は見ないと言うのも
1420 アリだ。
1421
1422 # その後、dhuf.c:decode_p_dyn() でのみ count を使用している事がわかった。
1423
1424 次は (H.2) である。これがまた難解なのだがゆっくり片付けよう。
1425
1426         } else {
1427             /* (H.2) */
1428             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
1429                (lastmatchoffset) & (dicsiz-1) );
1430             --lastmatchlen;
1431
1432             while (--lastmatchlen > 0) {
1433                 get_next();  insert();
1434                 count++;
1435             }
1436             get_next();
1437             matchlen = THRESHOLD - 1;
1438             match_insert();
1439             if (matchlen > remainder) matchlen = remainder;
1440         }
1441
1442 まず、output() に渡している引数は、それぞれ「長さ」と「位置」であろう
1443 ことは予想済みだ。さらに UCHAR_MAX{255} + 1 - THRESHOLD{3} だから
1444
1445  長さ  lastmatchlen + 253
1446  位置  lastmatchoffset & (dicsiz-1)
1447
1448 となっている。冒頭の decode() の解析で、長さは 253 を足す事は確認済み
1449 だ(-lhs- の場合 254 を足すという動作が、encoding 部分では考慮され
1450 てないのは、-lhs- の encoding 機能がないからだ)。ところで、一致長
1451 lastmatchlen は 3 以上で初めて 255 を越えることができる。以前予想した、
1452 THRESHOLD の意味「最低限一致しなければならない長さ」はあっているらしい。
1453
1454 もう一点、注意しなくてはならないのは、出力しているのが lastmatchlen と
1455 lastmatchoffset である。これらは、match_insert() のときには更新してい
1456 ない(last〜の更新は次のループの先頭 (E) で行われる)。先程 (H.1) のとき
1457 も書き出していたのは、text[pos-1] であった。pos 位置は一歩先読みした位
1458 置を指すらしい。このような処理を行う場合、最後に調整が必要なはずだ(で
1459 ないと最後の文字が出力されない)。その調整はどこで行われるのだろう？
1460
1461 さて、後続の処理だが、<長さ、位置>のペアを出力した後は、
1462
1463             --lastmatchlen;
1464
1465             while (--lastmatchlen > 0) {
1466                 get_next();  insert();
1467                 count++;
1468             }
1469
1470 という処理を行っている。get_next() は、pos を進める処理、insert() は辞
1471 書に登録する処理だから、これは文字列を読み飛ばしている処理だ。確かに
1472 lastmatchlen 分の情報は出力済みだから、これは納得である。lastmatchlen
1473 を 1 余分に引いているのが謎だがこれは pos が一歩先に進んでいるからであ
1474 ろうと予想する。つまり、この後は pos の位置はまた「現在位置」に戻る。
1475 なるほど、先程調整が必要と書いたがここで行われているらしい。細部は不明
1476 だが少なくとも辞書に文字列が見つかった場合は最後まで出力されるようだ。
1477
1478 次に進もう
1479
1480             get_next();
1481             matchlen = THRESHOLD - 1;
1482             match_insert();
1483             if (matchlen > remainder) matchlen = remainder;
1484
1485 せっかく pos が現在の位置に戻ったのに、get_next() でまた先読みされた。
1486 うーむ。そして、matchlen は初期化される。一致情報はすでに出力済みだか
1487 らこれはうなずける。そして、match_insert() が呼ばれる。この時点で再度
1488 辞書が検索される。pos はまた1文字進んでいるのだから、これは先程(初期状
1489 態)のmatch_insert() と大差ない処理だ。(その直後のif文は境界条件なので
1490 無視)
1491
1492 そうして、また次のループに移る。このとき続けざま get_next(),
1493 match_insert() が行われる。どうやら pos は次のループからは、 2 文字文
1494 先に進んでしまうようだ。なぜだろう？
1495
1496 # 後でわかった事だが、while (--lastmatchlen > 0) のループ回数を読み間
1497 # 違えた。例えば、lastmatchlen が 1 なら、この while ループ内では
1498 # get_next() は1回も呼ばれない。
1499
1500 どうにもソースを見ただけで解読するには、このあたりが限界のようだ。どう
1501 しても細部がわからないし、事実が見えないから予想の積み重ねがたまって不
1502 安になる。
1503
1504 実は、もう少しマメに図を起こして読み進んで行けばもっとわかることがあっ
1505 ただろうと思うのだが、それは面倒だし、間違える可能性がある(ここまでで
1506 何度か痛い思いをした)。以降は、いくつかのデータを実際に圧縮させその動
1507 きをデバッガで追うことで、これまでの解析結果を検証してみよう。
1508
1509 ・・・っと、その前に、ここまでですべての関数を網羅してしまったと思って
1510 いたのだが、一つ忘れていたものがあった。update() だ。この関数は、
1511 get_next() で呼び出されていたのだが、以前は無視していた。先にここを見
1512 ておこう。
1513
1514 まず、get_next() を再掲する。
1515
1516 static void get_next()
1517 {
1518     remainder--;
1519     if (++pos >= txtsiz - maxmatch) {
1520         update();
1521     }
1522     hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
1523 }
1524
1525 remainder と pos を進めた後、pos が txtsiz - maxmatch に達してしまった
1526 場合(pos == 2 * 2^dicbit の場合)に呼び出されるようだ。つまり、以下の図
1527 の状態だ。これが、update() を呼び出す時の初期状態だ。
1528
1529 ----------------------------------------------------------------------------
1530
1531                                 dicsiz=2^dicbit               2*2^dicbit
1532                                    v                           v   txtsiz
1533        +-------------+-------------+-------------+-------------+---+
1534   text |             |             |             |             |   |
1535        +-------------+-------------+-------------+-------------+---+
1536                                                               /<--->
1537                                                              /  maxmatch{256}
1538                                                            pos
1539
1540                                                                 <-->
1541                                                               remainder
1542
1543 ----------------------------------------------------------------------------
1544
1545 では、update() に入る。
1546
1547 static void update()
1548 {
1549     unsigned int i, j;
1550     unsigned int k;
1551     long n;
1552
1553 #if 0
1554     memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
1555 #else
1556     {
1557         int m;
1558         i = 0; j = dicsiz; m = txtsiz-dicsiz;
1559         while (m-- > 0) {
1560             text[i++] = text[j++];
1561         }
1562     }
1563 #endif
1564     n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)],
1565                                (unsigned)dicsiz, infile);
1566
1567     remainder += n;
1568     encoded_origsize += n;
1569
1570     pos -= dicsiz;
1571     for (i = 0; i < HSHSIZ; i++) {
1572         j = hash[i];
1573         hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
1574         too_flag[i] = 0;
1575     }
1576     for (i = 0; i < dicsiz; i++) {
1577         j = prev[i];
1578         prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
1579     }
1580 }
1581
1582 先頭で、なぜか memmove() を for ループで書き換えている。なぜこのような
1583 ことを行っているのだろう。for ループを見てみてもやっていることは変わら
1584 ない。謎だが、とにかく、text[] の右半分(maxmatch 部分も含む) を左に移
1585 している。
1586
1587 次に fread_crc() で、新たにファイルを読み込む。今度の読み込み位置は
1588 &text[txtsiz - dicsiz] で、長さは dicsiz である。当然、remainder も更
1589 新している。encoded_origsize は以前と同様無視。pos は dicsiz 分減らさ
1590 れている。これはつまり図示すると、以下の状態になると言う事だ
1591
1592 ----------------------------------------------------------------------------
1593
1594                                 dicsiz=2^dicbit               2*2^dicbit
1595                                    v                           v   txtsiz
1596        +-------------+-------------+---+---------+-------------+---+
1597   text |             |             |   |         |             |   |
1598        +-------------+-------------+---+---------+-------------+---+
1599                                   /<--->                       <--->
1600                                  / maxmatch{256}              maxmatch{256}
1601                                 pos
1602
1603                                    <------------------------------->
1604                                               remainder
1605
1606        |------- 以前のデータ  ---------|--- 新しいデータ  ---------|
1607
1608 ----------------------------------------------------------------------------
1609
1610 以降、ファイルの読み込みは常にこの update()でしか行われない。pos は、
1611 初期状態と同じ位置なので、初期状態が再現されている。ここまでで、
1612 maxmatch の領域はなんだろうと思うが、おそらく先読みのためだろう。それ
1613 らしい処理は、match_insert() の冒頭にあった(が、現時点で詳細には触れて
1614 いない)。
1615
1616 # maxmatch 分の余分な領域は、pos の位置から最大 maxmatch 長の文字列照
1617 # 合を行うために必要な領域。先読みとはまた見当外れなことを書いたものだ。
1618 # ちょっと考えればわかることなのに・・
1619
1620 update() の残りを見る。
1621
1622     for (i = 0; i < HSHSIZ; i++) {
1623         j = hash[i];
1624         hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
1625         too_flag[i] = 0;
1626     }
1627     for (i = 0; i < dicsiz; i++) {
1628         j = prev[i];
1629         prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
1630     }
1631
1632 内容は、想像がつくので詳細は省略しよう。単に以前のデータが移動したので、
1633 ハッシュ値を更新しているだけだ。しかし、これはなかなか無駄な処理だ。
1634
1635 以前、text[] は環状バッファだろうと予想したが予想がはずれたことがわかっ
1636 た。環状バッファにしていれば、このハッシュの書き換えは不要にできただろ
1637 うと思うのだが・・・
1638 # そのかわり、位置の大小比較が繁雑にならないので、これはこれで良いのか
1639 # もしれない。どちらが優れているかは実験してみなければわからないだろう。
1640
1641 これで、一応は slide.c を網羅する事ができた。まだ不明な点は多いが、デ
1642 バッガで実際の処理を追いかければまたわかることがあるだろう。
1643
1644 ・・・しばし、休息・・・
1645
1646 さて、デバッガでと以前は考えていたのだが、あきらめるのはまだ早い(元気
1647 が出たらしい)、そもそも最初に「デバッガを使わずにどこまで解読できるか」っ
1648 と冒頭に書いてたのにたった2回の通読でもうあきらめようとしていた。が、
1649 ここまで書いてきた本書を何度か読み返したが、まだまだ検討の余地はある。
1650
1651 まず、match_insert() の処理でわからなかった部分を解読しよう。実は、こ
1652 れに関してはどうしてもわからず悩んでいたところ、Lha for UNIX のメンテ
1653 ナである岡本さんに教えてもらうことができた(ありがとうございます)その内
1654 容を確認しつつ match_insert() を見ることにする。
1655
1656 まずは、復習だ。通常の状態に関しては match_insert() の解読は済んでいる。
1657 match_insert() は、text[pos] から始まる文字列を辞書から検索し、見つかっ
1658 た位置と一致長を matchpos, matchlen に設定する処理だ。そして、ついでに
1659 insert() で、text[pos] の位置をハッシュ配列に記録し、次回の検索に備え
1660 ることもしている。
1661
1662 では、不明な部分はなんだったかというと too_flag[] まわりである。
1663 too_flag のフラグが立っていると。辞書検索の頼りとなるハッシュ値を変更
1664 している。この部分がまったく皆目検討がつかなかったのだ。これに関してソー
1665 スを読み進めよう。以下ソースを再掲する。
1666
1667 static void match_insert()
1668 {
1669     unsigned int scan_pos, scan_end, len;
1670     unsigned char *a, *b;
1671     unsigned int chain, off, h, max;
1672
1673     max = maxmatch; /* MAXMATCH; */
1674     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
1675     matchpos = pos;
1676
1677     off = 0;
1678     for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
1679         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1680     }
1681     if (off == maxmatch - THRESHOLD) off = 0;
1682     for (;;) {
1683         chain = 0;
1684         scan_pos = hash[h];
1685         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1686         while (scan_pos > scan_end) {
1687             chain++;
1688
1689             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1690                 {
1691                     a = text + scan_pos - off;  b = text + pos;
1692                     for (len = 0; len < max && *a++ == *b++; len++);
1693                 }
1694
1695                 if (len > matchlen) {
1696                     matchpos = scan_pos - off;
1697                     if ((matchlen = len) == max) {
1698                         break;
1699                     }
1700                 }
1701             }
1702             scan_pos = prev[scan_pos & (dicsiz - 1)];
1703         }
1704
1705         if (chain >= LIMIT)
1706             too_flag[h] = 1;
1707
1708         if (matchlen > off + 2 || off == 0)
1709             break;
1710         max = off + 2;
1711         off = 0;
1712         h = hval;
1713     }
1714     prev[pos & (dicsiz - 1)] = hash[hval];
1715     hash[hval] = pos;
1716 }
1717
1718 まず、too_flag[] は、最初すべての要素が 0 である。そして、新たにファイ
1719 ルを読むとき(update())も 0 に再初期化されるのだった。このフラグが立つ
1720 条件はというと、この match_insert() の中だけである。その処理は
1721
1722         if (chain >= LIMIT)
1723             too_flag[h] = 1;
1724
1725 この部分だけだ。chain が LIMIT以上になったら h (これは検索対象のハッシュ
1726 値だ)に関して、フラグを立てる。chain は while ループ(これは文字列の照
1727 合を行う処理)のループ回数だ。h に関しての検索が LIMIT{256} 以上の場合
1728 に too_flag[h] のフラグが立っている。
1729
1730 while ループは一致文字列の一致長が最長一致長に達するか、辞書を最後まで
1731 探索するまでループする。つまり、あるハッシュ h に関してそのチェーンが
1732 256 以上のものに関しては、too_flag[h] が 1 になっている。
1733
1734 では、そのような h に関して、match_insert() がどのような処理になってい
1735 るかを見る。まず初期化部分
1736
1737     max = maxmatch; /* MAXMATCH; */
1738     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
1739     matchpos = pos;
1740
1741 これは、とりあえず無視。
1742
1743     off = 0;
1744     for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
1745         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1746     }
1747     if (off == maxmatch - THRESHOLD) off = 0;
1748
1749 通常 off は、0 なのだが、too_flag[h] が 1 であるものに関しては値が変わ
1750 る。検索対象となる文字列 text[pos](のハッシュ値) hval に関して、
1751 too_flag[h] が立っていれば、(このハッシュのチェーンが 256 以上であるこ
1752 とが事前にわかっていれば)
1753
1754         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
1755
1756 で、検索対象となるハッシュ値を変更している。このハッシュ値が示すのは元
1757 の検索対象文字列の 1 文字先だ。
1758
1759 ----------------------------------------------------------------------------
1760
1761                            |--- c --|
1762                         |--- b --|  |
1763                      |-- a ---|  |  |
1764        +-------------+--------+--------+
1765 text   |             |  |  |  |  |  |  |
1766        +-------------+--------+--------+
1767                       \  \
1768                       pos pos+1(off=1)
1769
1770 ----------------------------------------------------------------------------
1771
1772 元の検索対象文字列が図の a だとすると、これを図の b にしている。初期化
1773 部のループは、もしこの b のハッシュチェーンに関して too_flag[h] がさら
1774 に 1 であるならさらに 先の文字列をハッシュ値とするようになっている。
1775 (これは元の pos の 2 文字先を示す。図の c の部分だ) h は、pos+off から
1776 の3文字のハッシュ値を示すものと言う事だ。
1777
1778 ただし、h があまりにも先の方を見るようなハメになれば(off が maxmatch -
1779 THRESHOLD) off は 0 に再設定されるが、このとき h はそのままだ。この意
1780 味はまだわからないが、バグなのではないかと想像している(h = hval に再設
1781 定する必要があるだろう)
1782
1783 では off = 1 だとして本処理を見ることにしよう。外側の for ループに関し
1784 ては、while ループを2回実行するかどうかだけのものだった。なので、
1785 while ループ部だけを見てみよう。
1786
1787         chain = 0;
1788         scan_pos = hash[h];
1789         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
1790         while (scan_pos > scan_end) {
1791             chain++;
1792
1793             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1794                 {
1795                     a = text + scan_pos - off;  b = text + pos;
1796                     for (len = 0; len < max && *a++ == *b++; len++);
1797                 }
1798
1799                 if (len > matchlen) {
1800                     matchpos = scan_pos - off;
1801                     if ((matchlen = len) == max) {
1802                         break;
1803                     }
1804                 }
1805             }
1806             scan_pos = prev[scan_pos & (dicsiz - 1)];
1807         }
1808
1809         if (chain >= LIMIT)
1810             too_flag[h] = 1;
1811
1812 scan_pos, scan_end に関しては検索開始位置と終了位置と言う事でもう良い
1813 だろう。で、最初の if の条件に着目する。
1814
1815             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
1816
1817 これが真となる状態を図示しよう。
1818
1819 ----------------------------------------------------------------------------
1820
1821                                                         |-- c ---|
1822                     |-- a ---|                       |--- b --|
1823        +---------------+--------+--------------------+--------+--------+
1824 text   |               |  |x'|  |                    |  |  |x |  |  |  |
1825        +---------------+--------+--------------------+--------+--------+
1826                        ^                             \  \
1827                       scan_pos                       pos pos+1(off=1)
1828
1829 ----------------------------------------------------------------------------
1830
1831 まず、if 条件の左辺
1832
1833   text[scan_pos + matchlen - off]
1834
1835 matchlen は、match_insert() に入る直前に 2 に初期化されている(最初は)
1836 ので、照合するのは図の x' だ。
1837
1838 if 条件の右辺
1839
1840   text[pos + matchlen]
1841
1842 これは、図の x の位置だ。x' == x ならば本格的に照合を開始する。
1843
1844                 {
1845                     a = text + scan_pos - off;  b = text + pos;
1846                     for (len = 0; len < max && *a++ == *b++; len++);
1847                 }
1848
1849 ここで比較しているのは、図の a と b だ。b は、off がどのような場合でも
1850 変わらないが、a は、off が大きければ大きい程左側を指す。off が例えば
1851 3 であるときの場合も見てみよう。
1852
1853 ----------------------------------------------------------------------------
1854
1855               |-- a ---|                             |--- b --|-- c ---|
1856        +---------------+--------+--------------------+--------+--------+
1857 text   |             x'|  |  |  |                    |  |  |x |  |  |  |
1858        +---------------+--------+--------------------+--------+--------+
1859                        ^                              \        \
1860                       scan_pos                        pos      pos+3(off=3)
1861
1862 ----------------------------------------------------------------------------
1863
1864 結局比較しているのは、pos からの文字列のハッシュ値を求めた場合と何も変
1865 わらない。off でいくら先を見ようとも比較するのは pos の位置だ。なぜこ
1866 のようなことをするのだろうか？これは最初どうしてもわからなかったのだが、
1867 説明を受けて納得した。
1868
1869 これは単に効率(速度)のためということだ。もし、図の b に関して照合文字
1870 列の候補があまりにも多い場合(too_flag[h]=1)、ハッシュのチェーンを何度
1871 もたどる事になるので効率が悪い。しかし、辞書検索のキーを何文字か進める
1872 事で、この可能性を減らす事ができる。少なくとも最悪の 256 よりはマシに
1873 なるようなものを選んでいる。そうして、この while ループのループ回数を
1874 減らしているのだ。どうせ探したいのは最長一致文字列なので先の方の文字列
1875 が一致しないと話にならないのだからこれは合理的だ。
1876
1877 これで、外側の for ループも納得だ。これは while ループをある条件でやり
1878 直す処理だった。
1879
1880         if (matchlen > off + 2 || off == 0)
1881             break;
1882
1883 最長一致長が見つかるか、あるいは off が 0 であればさっさとこの処理は終
1884 るのだが、もし off を進めて照合を行っていたとして、最長一致文字列が見
1885 つからなかったとすると
1886
1887         max = off + 2;
1888         off = 0;
1889         h = hval;
1890
1891 という条件で照合をやり直す。これは元の文字列で照合をやり直すということ
1892 だからつまりは、最悪のハッシュチェーンを仕方ないから辿り直そうと言う事
1893 だ。さらに、pos から pos+off+3 までの文字列が、辞書から見つからなかっ
1894 たので、最大一致長を off + 2 として条件を緩めている(なぜこれが条件を緩
1895 める事になるかと言うと while ループは最大一致長の文字列が見つかったら
1896 すぐに抜けるからだ)。
1897
1898 ところで、match_insert() の先の処理は以下の書き換えを行うともう少し見
1899 やすくなる。(と思う)。
1900
1901 o scan_beg という変数を用意し、これを scan_pos - off にする。
1902 o scan_end は、pos - dicsiz にする。
1903 o while 条件を while (scan_pos != NIL && scan_beg > scan_end) にする。
1904
1905 以下
1906
1907         unsigned int scan_pos = hash[h];
1908         int scan_beg = scan_pos - off;
1909         int scan_end = pos - dicsiz;
1910
1911         chain = 0;
1912         while (scan_pos != NIL && scan_beg > scan_end) {
1913             chain++;
1914
1915             if (text[scan_beg + matchlen] == text[pos + matchlen]) {
1916                 {
1917                     unsigned char *a = &text[scan_beg];
1918                     unsigned char *b = &text[pos];
1919
1920                     for (len = 0; len < max && *a++ == *b++; len++);
1921                 }
1922
1923                 if (len > matchlen) {
1924                     matchpos = scan_beg;
1925                     if ((matchlen = len) == max) {
1926                         break;
1927                     }
1928                 }
1929             }
1930             scan_pos = prev[scan_pos & (dicsiz - 1)];
1931             scan_beg = scan_pos - off;
1932         }
1933
1934         if (chain >= LIMIT)
1935             too_flag[h] = 1;
1936
1937 ----------------------------------------------------------------------------
1938
1939               |-- a ---|                             |--- b --|
1940        +---------------+--------+--------------------+--------+--------+
1941 text   |      |      x'|  |  |  |                    |  |  |x |  |  |  |
1942        +---------------+--------+--------------------+--------+--------+
1943          ^     \        \                             \        \
1944          |    scan_beg  scan_pos                        pos      pos+off
1945      scan_end
1946
1947          |----|
1948            scan_beg の有効範囲
1949
1950          |----------------- dicsiz ------------------|
1951
1952 ----------------------------------------------------------------------------
1953
1954 scan_beg, scan_end の範囲もわかりやすいし、hash[h] が NIL の場合の処理
1955 も明示的だ。この書き換えを行う場合、scan_beg が負の値になる可能性があ
1956 る。元もとの処理では scan_end 等の変数を unsigned にしているので、これ
1957 らを int にして while 条件で負の scan_beg をはじかなければならないこと
1958 に注意。そうすると、scan_pos != NIL は必要なくなるのだがわかりやすさを
1959 追求した。
1960
1961 これで match_insert() の解読は終りだ。match_insert() の処理とは以下の
1962 通りだ。
1963
1964 ----------------------------------------------------------------------------
1965   match_insert() は、text[pos] から始まる文字列に一致する文字列を辞書
1966   から検索し、見つかった位置と一致長を matchpos, matchlen に設定する。
1967
1968   もし、最長一致文字列が見つからなければ matchpos は、pos に設定され、
1969   matchlen は更新されない。(実は、matchpos = pos の情報は特に使われてない)
1970
1971   見つかった場合、matchlen は呼び出し前の matchlen よりも大きくなる。
1972   (呼び出し前では matchlen の意味は最低限一致しなくてはならない文字列
1973   長で、照合条件の一つになっている)
1974
1975   この関数の入力は
1976
1977       matchlen
1978       pos
1979
1980   出力は
1981
1982       matchlen
1983       matchpos
1984
1985   といったところ。
1986
1987   さらに、insert() と同様の処理で、pos の位置をハッシュ配列に記録し、
1988   次回の検索に備える。これはついでの処理。
1989 ----------------------------------------------------------------------------
1990
1991 これを踏まえた上で処理内容を再読しよう。(E) 〜 (H) だ。
1992
1993         /* (E) */
1994         lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
1995         --matchlen;
1996
1997         /* (F) */    /* (G) */
1998         get_next();  match_insert();
1999         if (matchlen > remainder) matchlen = remainder;
2000
2001         /* (H) */
2002         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
2003             /* (H.1) */
2004             encode_set.output(text[pos - 1], 0);
2005             count++;
2006         } else {
2007
2008 (H) の条件とは何なのかを見る。この条件が真なら、文字列をそのまま出力す
2009 るのだが、素直に slide 辞書法の処理を考えればこの条件は「辞書から見つ
2010 からなかった場合」となる。が、実際にはもう少し複雑だ。
2011
2012         /* (H) */
2013         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
2014
2015 matchlen は、pos の位置の文字列が見つかった辞書上の長さ
2016 lastmatchlen は、pos-1 の位置の文字列が見つかった辞書上の長さ
2017
2018 であるとすると、この条件は、「pos の位置で見つかった長さが、pos-1 の位
2019 置で見つかった長さよりも長ければ」っとなる。
2020
2021 これはつまり、pos-1 と pos のニ箇所に関して辞書を検索して、より長くマッ
2022 チする方を選ぼうとしているわけだ。matchlen の方が長いなら 1 つ前
2023 (pos-1)の文字はそのまま出力し、次のループに移る(もし、次の文字が
2024 さらに長くマッチするなら。またそのまま出力される)
2025
2026 この条件で「見つからなかった場合」というのはどう表されているかを考える。
2027 もし、pos の文字列が辞書になければ pos - 1 の文字列は、どうすべきかと
2028 いうと「pos-1 の文字列が見つかってなければ。そのまま出力。辞書にあった
2029 なら <lastmatchlen, lastmatchoffset> のペアを出力」っとならなければな
2030 らない。
2031
2032 lastmatchlen は、初期状態では THRESHOLD - 1 であったので、見つからなかっ
2033 たという条件は (H) の右側の条件 lastmatchlen < THRESHOLD でまず表され
2034 ている。
2035
2036 では、例えば lastmatchlen が 5 であったとしよう。このとき (E) の処理で
2037 matchlen は lastmatchlen - 1 つまり、4 に設定される。そして、match_insert()
2038 で次の文字列がもし辞書から見つからなければ matchlen は更新されないので
2039   matchlen < lastmatchlen
2040 となる。このような条件(前回見つかり、今回見つからない)場合に限り、(H.2)
2041 の処理が実行されるようになっている。では、(H.2) の処理を追いかけよう。
2042
2043 まず、この状態を図示する。
2044
2045 ----------------------------------------------------------------------------
2046
2047                          lastmatchlen                  lastmatchlen
2048                        |--          --|              |--          --|
2049        +---------------+--------------+--------------+--------------+--+
2050 text   |               |  |  |  |  |  |              |  |  |  |  |  |  |
2051        +---------------+--------------+--------------+--------------+--+
2052                        ^                             |   \           \
2053                       matchpos                    pos-1  pos         pos2
2054
2055                        |--------------------------|
2056                              lastmatchoffset
2057
2058 ----------------------------------------------------------------------------
2059
2060
2061             /* (H.2) */
2062             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
2063                (lastmatchoffset) & (dicsiz-1) );
2064             --lastmatchlen;
2065
2066             while (--lastmatchlen > 0) {
2067                 get_next();  insert();
2068                 count++;
2069             }
2070             get_next();
2071             matchlen = THRESHOLD - 1;
2072             match_insert();
2073             if (matchlen > remainder) matchlen = remainder;
2074         }
2075
2076 まず、<長さ, 位置> のペアを出力する。これはいいだろう。出力する「位置」
2077 は0 なら 1 文字前を表すので、実際のオフセット pos - 1 - matchpos より
2078 も 1 小さい値になっていることに注意しておこう。
2079
2080 そして、lastmatchlen は 1 引かれる。この場合例えば 4 になる。したがっ
2081 て、次のループでは 3 文字 pos が先送りされる(4 ではない)。pos は既に 1
2082 文字先に進んでいるので、最初に 1 引くのはこのことを考慮している。while
2083 ループが終った後はpos の位置は実際に出力した文字列の最後の文字 pos2-1
2084 を指していることになる。
2085
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 の照合結果と比較されるのでこの処理も想像がつく。
2093
2094 最初、どうにもこの処理内容が理解できなかったのだが「現在の文字列と、次
2095 の文字列のそれぞれで辞書を検索し、より長く見つかった方を使う」という最
2096 適化を行っている事がわかってしまった後は解読は簡単だった。(実はこの事
2097 実も教えてもらった事だ。全然ダメじゃん)
2098
2099 さて、これで一通りの解析は済んだわけだが、ここまでの解析内容を読み直し
2100 てみると、以下の点がまだひっかかる。
2101
2102 1. ハッシュ関数は最適なのか？特に HSHSIZ{2^15} は最適なのか？
2103 2. too_flag[] は、実際に照合を行いループがLIMITを越えた場合に
2104    設定される。しかし、ハッシュのチェーンを作る際にチェーンの
2105    個数をあらかじめ数えておけば一度の探索すらも行われず。より
2106    早く処理されないだろうか？
2107
2108 現状、1, 2 とも実施してみたところ特に速度の改善は見られなかった。特に
2109 1 は、微妙なところがありほとんどの書き換えは性能を悪くするだけだった。
2110 なかなか興味深いものがある。
2111
2112 これは今後の課題としていずれまた検証しよう。そろそろ slide.c も飽きて
2113 きたのでひとまずはこれで終りにしたい。
2114
2115 \f
2116 bit 入出力ルーチン (crcio.c)
2117 ---------------------------
2118
2119 これから Huffman 法の解読に移るのだが、その前準備として bit 入出力ルー
2120 チンの解読を行う。Huffman 法の実装では必ず bit 入出力処理が必要になる。
2121 LHa for UNIX ももちろん例外ではなく、Huffman 法の実装を解読するにあた
2122 りこの部分の処理内容ははっきりさせておいた方が良いと考えたのだ。
2123
2124 LHa for UNIX version 1.14i では bit 入出力ルーチンは crcio.c で定義さ
2125 れている。(このようなファイル名に存在するのは意外な事だ。最近の LHa
2126 for UNIX では、私が bitio.c というファイルを設け、bit 入出力ルーチンは
2127 そこに切り出した)
2128
2129 crcio.c のうち bit 入出力ルーチンは fillbuf(), getbits(), putcode(),
2130 putbits(), init_getbits(), init_putbits() の 6 関数だ。
2131
2132 まず、初期化用の init_getbits(), init_putbits() を見よう。
2133
2134 void
2135 init_getbits( /* void */ )
2136 {
2137     bitbuf = 0;
2138     subbitbuf = 0;
2139     bitcount = 0;
2140     fillbuf(2 * CHAR_BIT);
2141 #ifdef EUC
2142     putc_euc_cache = EOF;
2143 #endif
2144 }
2145
2146 void
2147 init_putbits( /* void */ )
2148 {
2149     bitcount = CHAR_BIT;
2150     subbitbuf = 0;
2151     getc_euc_cache = EOF;
2152 }
2153
2154 それぞれ bit 入力、bit 出力を行うための初期化処理だ。CHAR_BIT というの
2155 は 8 で、char 型の bit サイズを表しているらしい。詳細はわからないが初期
2156 状態はとにかくこれだ。ここで使用されている変数は、
2157
2158 static unsigned char subbitbuf, bitcount;
2159
2160 が、crcio.c で定義されており、
2161
2162 EXTERN unsigned short bitbuf;
2163
2164 が、lha.h で定義されている(EUC なんたらは本質ではない無視しよう)。グロー
2165 バル変数と言うのは忌むべきものだが、とにかく使用されている変数と初期値
2166 を確認したので次に移ろう。init_getbits() で、早速 fillbuf() が呼ばれて
2167 いる。この処理内容を見る。
2168
2169 void
2170 fillbuf(n)          /* Shift bitbuf n bits left, read n bits */
2171     unsigned char   n;
2172 {
2173     /* (A) */
2174     while (n > bitcount) {
2175         n -= bitcount;
2176         /* (B) */
2177         bitbuf = (bitbuf << bitcount) + (subbitbuf >> (CHAR_BIT - bitcount));
2178         /* (C) */
2179         if (compsize != 0) {
2180             compsize--;
2181             subbitbuf = (unsigned char) getc(infile);
2182         }
2183         else
2184             subbitbuf = 0;
2185         bitcount = CHAR_BIT;
2186     }
2187     /* (D) */
2188     bitcount -= n;
2189     bitbuf = (bitbuf << n) + (subbitbuf >> (CHAR_BIT - n));
2190     subbitbuf <<= n;
2191 }
2192
2193 まず、初期状態として
2194
2195     bitbuf = 0;
2196     subbitbuf = 0;
2197     bitcount = 0;
2198
2199 であり、fillbuf の引数 n には 2 * CHAR_BIT が与えられたのだった。いき
2200 なり while 条件を満たすのでループ部の解析を行わなくてはならなくなるが、
2201 ひとまずこれを無視して最後の 3 行 (D) に着目する。条件は少ない方が良い
2202 のだ。
2203
2204     /* (D) */
2205     bitcount -= n;
2206     bitbuf = (bitbuf << n) + (subbitbuf >> (CHAR_BIT - n));
2207     subbitbuf <<= n;
2208
2209 bitbuf << n, subbitbuf << n されているので、bitbuf, subbitbuf を n ビッ
2210 ト左にずらす処理のようだ。さらに bitbuf には、subbitbuf を n ビットず
2211 らしたときに溢れた部分を bitbuf にセットしている。っと、
2212
2213    (subbitbuf >> (CHAR_BIT - n))
2214
2215 の部分を軽く説明したが、図示して確認しておこう。
2216
2217 subbitbuf は unsigned char なので 8 bit の変数だ。
2218
2219 ----------------------------------------------------------------------------
2220                7  6  5  4  3  2  1  0
2221               +--+--+--+--+--+--+--+--+
2222    subbitbuf  |                       |
2223               +--+--+--+--+--+--+--+--+
2224               <-- n -->
2225 ----------------------------------------------------------------------------
2226
2227 n が例えば 3 の場合、CHAR_BIT - n は、5 だから subbitbuf を 5 ビット右
2228 にずらした値を取っている。つまり、図の 7, 6, 5 ビット目が一番右に来る
2229 ようになっており、この値を bitbuf に足している。(C言語では、unsigned
2230 な変数を右にシフトすると上位ビットには 0 が入る)
2231
2232 fillbuf() の後半 3 行(いや、後半2行か)は。結局 bitbuf と subbitbuf を
2233 一つの bitbuf とみなして n ビット左にずらしていることがわかる。
2234
2235 ----------------------------------------------------------------------------
2236 <ビットバッファ全体図 (予想)>
2237
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           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2240   bitbuf  |                             |          x  y  z|
2241           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2242                                          \        <-- n  ->
2243                                          subbitbuf
2244            <-------------- bitcount ------------->
2245
2246 ----------------------------------------------------------------------------
2247
2248 このとき、当然図の x, y, z の部分(n = 3 は例としての値だ)が空く事になる。
2249 bitcount という変数が n 引かれていたが、これは bit バッファ全体の有効
2250 なビット数を表しているのではないかと予想しておく。すなわち図の状態なら
2251 21 だ。while ループは(関数名から)この空き部分を埋める処理なのではない
2252 かと適当に予想できる。では、while ループを見よう。もう一度初期値を確認
2253 し、最初に行われる処理内容を見よう。
2254
2255 最初、
2256
2257     bitbuf = 0;
2258     subbitbuf = 0;
2259     bitcount = 0;
2260
2261 であるから、bitバッファは空っぽだ。当然 fillbuf(2 * CHAR_BIT) されると
2262 while 条件を満たす。きっと 16 bit だけ bitバッファが補充されるはず(つ
2263 まり、bitbuf いっぱい、subbitbuf 空)だ。
2264
2265     /* (A) */
2266     while (n > bitcount) {
2267         n -= bitcount;
2268
2269 で、ビットバッファが保持する bit 数以上を要求されたので、ループに入る。
2270 n -= bitcount で、本当に足りない部分が何ビットなのかを得ている。ここで
2271 は 16 だ。次の行
2272
2273         /* (B) */
2274         bitbuf = (bitbuf << bitcount) + (subbitbuf >> (CHAR_BIT - bitcount));
2275
2276 これは先程も出て来た処理だ。ビットバッファ全体を bitcount 分左にずらし
2277 ている(ただし、まだ subbitbuf はずらされていない)。この時点で予想が少
2278 し覆された。8 - bitcount で subbitbuf をずらしているから bitcount は最
2279 大 8 の値しか持たないだろうということだ。どういうことか、考えてみる・・・
2280 考えてもわからなかったので次に進もう。
2281
2282         /* (C) */
2283         if (compsize != 0) {
2284             compsize--;
2285             subbitbuf = (unsigned char) getc(infile);
2286         }
2287         else
2288             subbitbuf = 0;
2289         bitcount = CHAR_BIT;
2290
2291 compsize というのが出て来たが、この値がどうあろうとも subbitbuf は8 ビッ
2292 ト埋められ。bitcount は 8 に設定されている。わかった bitcount は、
2293 subbitbuf に保持する bit 数だ。図を訂正しよう。
2294
2295 ----------------------------------------------------------------------------
2296 <ビットバッファ全体図>
2297
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           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2300   bitbuf  |                             |            x y z|
2301           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2302                                        /          <-- n  ->
2303                                    subbitbuf
2304                                         <-------->
2305                                          bitcount
2306
2307 ----------------------------------------------------------------------------
2308
2309 この図を踏まえてもう一度初期状態での処理内容を追いかける。
2310
2311 まず、(A) で、subbitbuf は空なので、bitcount は 0 だ。要求した bit 数
2312 n{16} より小さいのでループに入る。n は 16 のままだ。
2313
2314 (B) で、subbitbuf に残っている bit を bitbuf にずらしている。今はまだ
2315 空なのでbitbuf はここでもまだ空だ。
2316
2317 (C) で、ファイルからデータを8 ビット読む(compsize は常に0ではないと考え
2318 る)。bitcount は 8 になる。この時点で bitバッファ全体は subbitbuf だけ
2319 値が入った状態になる。
2320
2321 次のループに移ろう。(A) で、subbitbuf はいっぱいであるが要求した n{16}
2322 よりは小さいので、まだループは続く。n はここで 8 になる。
2323
2324 (B) で、subbitbuf に残っている bit (8 bit だ)を bitbuf にずらしている。
2325 今度は subbitbuf 全体が bitbuf に移っているのと同じだ。(つまり、bitbuf
2326 = subbitbuf)
2327
2328 (C) で、また subbitbuf は 8 bit 補充される。
2329
2330 (A) で、n{8} > bitcount{8} は偽なのでループが終る。
2331
2332 (D) で、subbitbuf に残っている bit はすべて bitbuf に移る。bitbuf は 16
2333 bit いっぱいになる。bitcount は 0 だ。
2334
2335 この処理結果から fillbuf(n) は、bitbuf に n ビット読み込む処理だと言え
2336 る。引数に指定できる n が最大 16 ビットであることにも気づいて良いだろ
2337 う。処理内容を確認してみればわかる。
2338
2339 ここで、subbitbuf の用途に気づいた。ファイルからの読み込みが 8 ビット
2340 単位でしかできないので、それを補うための保存用バッファであろう。例えば
2341 1 ビットだけ bitbuf を fill したければ subbitbuf に 7 bit 残し、1 bit
2342 だけ bitbuf に設定される(確認してみればわかる)
2343
2344 fillbuf() がわかったので、それを利用している getbits() の内容を確認し
2345 よう。
2346
2347 unsigned short
2348 getbits(n)
2349     unsigned char   n;
2350 {
2351     unsigned short  x;
2352
2353     x = bitbuf >> (2 * CHAR_BIT - n);
2354     fillbuf(n);
2355     return x;
2356 }
2357
2358     x = bitbuf >> (2 * CHAR_BIT - n);
2359
2360 は、3 度も出て来たので
2361
2362      buf >> (sizeof(buf)*8 - n)
2363
2364 を buf の上位 n ビットを得る式だとしてマクロにしても良いだろう。(が、
2365 良い名前が思い付かないのでそうはしない)。とにかく、bitbuf の上位 n ビット
2366 を下位 n ビットとして x に代入している。その後で、
2367
2368     fillbuf(n);
2369
2370 している。n bit を x に渡したので bitbuf から上位 n ビットを捨てて、n
2371 ビット補充する。ここで、bitbuf は常にいっぱいの状態になっていることが
2372 わかる。(ファイルの末尾付近の場合、正確に bitbuf に何ビット残っている
2373 かが判断できないが、種明かしをするとこのことは LHa の処理内容にとって
2374 はどうでもいいことだ。getbits() は decode 処理で使われるのだが、decode
2375 処理は何ビットの情報を decode する必要があるかを他の情報からあらかじめ
2376 得ている)
2377
2378 次に移ろう今度は putcode() だ。put の場合まずは、init_putbits() で
2379 初期化が行われている。その値は以下だ。
2380
2381     bitcount = CHAR_BIT;
2382     subbitbuf = 0;
2383     getc_euc_cache = EOF;
2384
2385 getc_euc_cache は無視だ。bitcount と subbitbuf の値が設定され、bitbuf
2386 は利用されない。先程とは違い subbitbuf が空なのにbitcount が 8 なので、
2387 bitcount の使われ方が多少異なるようだ。get の場合は、bitcount は、
2388 subbitbuf に保持する bit 数だったが今度は subbitbuf の空き bit 数だろ
2389 うと予想しておこう。
2390
2391 そして、putcode(n, x) を見る。実はソースを見るとわかるのだが、もう一つ
2392 の出力ルーチン putbits() は、putcode() の呼び出しに書き換え可能だ。
2393 putbits() は、
2394
2395 void
2396 putbits(n, x)           /* Write rightmost n bits of x */
2397     unsigned char   n;
2398     unsigned short  x;
2399 {
2400     x <<= USHRT_BIT - n;
2401     putcode(n, x);
2402 }
2403
2404 っと書き換えられるのだ。なので、putcode() の内容を先に確認するわけだ。
2405
2406 void
2407 putcode(n, x)           /* Write rightmost n bits of x */
2408     unsigned char   n;
2409     unsigned short  x;
2410 {
2411     /* (A) */
2412     while (n >= bitcount) {
2413         n -= bitcount;
2414         /* (B) */
2415         subbitbuf += x >> (USHRT_BIT - bitcount);
2416         x <<= bitcount;
2417         /* (C) */
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");
2422                 /* exit(errno); */
2423             }
2424             compsize++;
2425         }
2426         else
2427             unpackable = 1;
2428         subbitbuf = 0;
2429         bitcount = CHAR_BIT;
2430     }
2431     /* (D) */
2432     subbitbuf += x >> (USHRT_BIT - bitcount);
2433     bitcount -= n;
2434 }
2435
2436 処理内容が fillbuf() のときと似ている。まずは、先程と同様に while 条件
2437 を無視して考えてみる。(D) だ。
2438
2439     /* (D) */
2440     subbitbuf += x >> (USHRT_BIT - bitcount);
2441     bitcount -= n;
2442
2443 この式はもう 4 度目だ。まず、x の上位 bitcount ビットを得て、subbitbuf
2444 に足している。bitcount は、先程 subbitbuf の空きであろうと予想したが、
2445 n 引かれているので、埋めた分空きが減っているわけだ。予想は当たっている
2446 だろう。この時点でこの関数が x の上位ビットを利用することがわかる。コ
2447 メントに rightmost n bits of x と書かれているが惑わされてはいけない。
2448 多くの場合、コメントはせいぜいヒントとしての情報でしかない。信用しては
2449 いけないものなのだ。(コメントはあまりデバッグされない。コメントが詳し
2450 ければ詳しい程コメントはエンバグしやすい。疑ってかかろう。これは本書に
2451 も言える。すべてを鵜のみにしてはいけないのだ)
2452
2453 では、処理内容に移る。まずは (A)
2454
2455     /* (A) */
2456     while (n >= bitcount) {
2457         n -= bitcount;
2458
2459 subbitbuf の空きが n 以下であればループに入る。subbitbuf 一つではn ビッ
2460 ト全部は賄えないからループで小刻みに処理しようということだろう(もう全
2461 体の処理内容の予想はついている)
2462 n から bitcount 引いているので、n ビットのうちこれから bitcount 分は
2463 処理されることをここでさっさと記録して次のループに備えている。
2464
2465         /* (B) */
2466         subbitbuf += x >> (USHRT_BIT - bitcount);
2467         x <<= bitcount;
2468
2469 x の上位 bitcount ビットを subbitbuf に足している。subbitbuf の空きが
2470 これで埋まった。subbitbuf はもういっぱいだ。x を bitcount シフトするこ
2471 とで subbitbuf に渡した x の上位ビットを捨てている。
2472
2473         /* (C) */
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");
2478                 /* exit(errno); */
2479             }
2480             compsize++;
2481         }
2482         else
2483             unpackable = 1;
2484         subbitbuf = 0;
2485         bitcount = CHAR_BIT;
2486
2487 compsize は無視しても良い。処理の本質ではないからだが、すぐにわかるので
2488 一応説明すると、
2489         if (compsize < origsize) {
2490             ...
2491         else
2492             unpackable = 1;
2493 で、圧縮ファイルサイズが元のファイルサイズを上回ったときに
2494 処理を終るようになっている(unpackable = 1 して、他の箇所でこの変数を監視する。
2495 unpackable == 1 なら処理を中断する)
2496
2497 とにかく (C) の時点では必ず subbitbuf がいっぱいになるので 1 バイトを
2498 ファイルに書き出している。その後、subbitbuf = 0, bitcount = 8 として
2499 subbitbuf を空けて次のループに備えている。
2500
2501 もういいだろう。putcode() は、論理的には x のうち上位 n ビットを出力す
2502 る処理だ。引数 n の上限が x の最大ビットサイズ 16 になるのは説明するま
2503 でもないだろう。
2504
2505 putcode() は実装として、subbitbuf と x を一つに繋げて n bit 左にずらし
2506 ている処理だと考えても良い。そうして、subbitbuf がいっぱいになったらそ
2507 の都度(1 バイトずつ)ファイルに書き出すのだ。
2508
2509 ----------------------------------------------------------------------------
2510 <ビットバッファ全体図>
2511
2512                       <--- 左にずらす
2513
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           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2516           |* * *          |x y z                          |
2517           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2518          /               / <-n->
2519       subbitbuf         x
2520                  <-------->
2521                   bitcount
2522
2523 ----------------------------------------------------------------------------
2524
2525 putbits() も見よう。先程 putcode() の呼び出しに書き換えたコードを見ると
2526 すぐわかるが、
2527
2528     x <<= USHRT_BIT - n;
2529     putcode(n, x);
2530
2531 最初の式で、x の下位 n ビットを x の上位 n ビットにしている。
2532 そうして、putcode() を呼び出しているので、putbits(n, x) は、x
2533 の下位 n ビットを出力する処理だ。
2534
2535 以上でビット入出力ルーチンは終りだ。出力に関して一つ捕捉しておくと
2536 putcode(), putbits() では最後の最後で subbitbuf に情報が残ったままファ
2537 イルに書き出されない状態になる。これを吐き出すために利用者は
2538
2539   putcode(7, 0)
2540
2541 を行う必要がある。
2542
2543 まとめよう
2544
2545 ----------------------------------------------------------------------------
2546 fillbuf(n)
2547   bitbuf から上位 n ビットを捨てて、下位 n ビットをファイルから読み込
2548   み埋める。
2549
2550 getbits(n)
2551   bitbuf の上位 n ビットを下位 n ビットとして返す。bitbuf は n ビット
2552   補充される。
2553
2554 putcode(n, x)
2555   x の上位 n ビットをファイルに出力する。最後の出力時は putcode(7, 0)
2556   する必要がある。
2557
2558 putbits(n, x)
2559   x の下位 n ビットをファイルに出力する。最後の出力時は putcode(7, 0)
2560   する必要がある。
2561
2562 init_getbits()
2563   入力処理の初期化
2564
2565 init_putbits()
2566   出力処理の初期化
2567 ----------------------------------------------------------------------------
2568
2569 読み込みに関して、bitbuf のサイズが 16 ビットで常にその状態が保持され
2570 ているのは LHa にとって重要な事だ。decode 処理では直接 bitbuf を参照す
2571 る箇所がある。
2572
2573 \f
2574 Huffman 法 (huf.c)
2575 ------------------
2576
2577 LHa for UNIX では、静的 Huffman 法として、shuf.c、動的 Huffman 法とし
2578 て dhuf.c があるらしいが、これらに関しては触れない。LHa では、これらは
2579 過去の版のアーカイブを解凍できるように decode のみサポートしているよう
2580 だ。そこで、まずは -lh4-, -lh5-, -lh6-, -lh7- で利用されている huf.c
2581 の解析を中心に行うこととしたい。
2582
2583 ところで、本書では Huffman 法がどういったものかは予備知識として既に知っ
2584 ているものとするが、いちおう概要を簡単に説明しておこう。
2585
2586 以下の内容のテキストファイルがあったとする。
2587
2588         abcabcaba
2589
2590 このテキストは 9 バイトあるわけだが、このファイルで使われている文字は3
2591 種類しかない、a, b, c だ。だからこのファイルだけに関して言えば 1 文字
2592 は 2 ビットあれば表現可能である。例えば各文字に対して以下のビットを
2593 割り当てたとすると
2594
2595         文字   ビット表現
2596         a      00
2597         b      01
2598         c      10
2599
2600 先のテキストファイルの内容 abcabcaba は、18ビットあれば表現可能となる。
2601
2602 さらに、出現頻度の高い文字を少ないビット数で表現し、まれにしか現れない
2603 文字を長いビット数で表すようにすればよりビット数を少なくできる。例えば
2604
2605         文字   ビット表現
2606         a      0
2607         b      10
2608         c      11
2609
2610 であるとすると a は 4回、bは3回、cは2回現れるので、全体は 4 + 2*3 +
2611 2*2 = 14 ビットで表現できることになる。これが Huffman 法の圧縮原理であ
2612 る。このように Huffman 法では文字をビット単位で扱うためビット入出力ルー
2613 チンを先に解読したわけだ。また、符号化の際はあらかじめ各文字の出現頻度
2614 を求めておく必要があり、復号化の際はどのビット列がどの文字に対応するか
2615 をあらかじめ知る必要がある。
2616
2617 文字毎にビット長のばらつきがあるような可変長符号には以下の条件がある。
2618
2619    ある符号のビットパターンは、他の符号のビットパターンの開始にはなら
2620    ない。
2621
2622 というものだ。これを「語頭条件」と言うらしい。例えば、先の例では a に
2623 0 を割り当てたので他の文字は必ず 1 から始まるようになっている。この条
2624 件を満たさなければならない理由はちょっと考えればわかる。仮に以下の間違っ
2625 た割当を行ったとする。
2626
2627         文字   ビット表現
2628         a      0
2629         b      10
2630         c      01
2631
2632 これだと、ビットパターン 010 が ab なのか ca なのか曖昧になるのがわか
2633 るだろう。
2634
2635 文字に対応する語頭条件を満たす(最適な)ビット列を求める方法、それがハフ
2636 マン法だ。ハフマン法ではハフマン木という木構造を構築するのだが、そのア
2637 ルゴリズムは以下のとおりだ。
2638
2639 まず、圧縮対象であるテキストに関して各文字の出現回数を数える。例えば
2640 abcabcaba というテキストでは、a は 4回、bは3回、cは2回なので、
2641
2642         4    3    2
2643         |    |    |
2644         a    b    c
2645
2646 となる。次に、出現回数の低いもの同士を一つの節に束ねる。この節は 3+2=5
2647 という出現回数を持つものと考える。
2648
2649         4      5
2650         |     / \
2651         a    b   c
2652
2653 以降さらに出現回数の低いもの同士を一つの節に束ねる操作を繰り返す。この
2654 例では、もう一度束ねれば終りだ。
2655
2656            9
2657            /\
2658           /  \
2659          /  / \
2660         a  b   c
2661
2662 ここで、木の左側が 0 右側が 1 であるとすると。a は根から左に1つ進むだ
2663 けなので 0。b は、右(1)→左(0) なので、10。c は右(1)→右(1) なので、11
2664 となる。実際の符号化の際は文字からビット列を求めるので葉から根にむかっ
2665 て逆順に辿ることになる。また、復号の際は入力のビット列に沿ってこの木を
2666 根から辿ることで対応する文字を求める(なので圧縮文にはこの木構造が一緒
2667 に情報として格納されることになる)。
2668
2669 このようなハフマン木を作成する箇所があるかどうかを探してみたところ
2670 maketree.c:make_tree() が見つかった。これは「C言語による最新アルゴリズ
2671 ム辞典」(奥村晴彦著、技術評論社)に載っているものとほとんど同じだ。では、
2672 この関数の解読から始めよう(今回の解析はボトムアップ式に行うことにしよ
2673 うと思う。というのもデータ構造から攻めようにもグローバル変数がたくさん
2674 出て来るし、処理順に追っても正直よくわからなかったからだ)
2675
2676 この関数のあるファイル maketree.c で使用しているデータ構造は以下だ。
2677
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];
2682
2683 make_tree() は以下。
2684
2685 short
2686 make_tree(nparm, freqparm, lenparm, codeparm)
2687 /* make tree, calculate len[], return root */
2688     int             nparm;
2689     unsigned short  freqparm[];
2690     unsigned char   lenparm[];
2691     unsigned short  codeparm[];
2692 {
2693     short           i, j, k, avail;
2694
2695     /* (A) */
2696     n = nparm;
2697     freq = freqparm;
2698     len = lenparm;
2699     avail = n;
2700     /* (B) */
2701     heapsize = 0;
2702     heap[1] = 0;
2703     for (i = 0; i < n; i++) {
2704         len[i] = 0;
2705         if (freq[i])
2706             heap[++heapsize] = i;
2707     }
2708     /* (C) */
2709     if (heapsize < 2) {
2710         codeparm[heap[1]] = 0;
2711         return heap[1];
2712     }
2713     /* (D) */
2714     for (i = heapsize / 2; i >= 1; i--)
2715         downheap(i);    /* make priority queue */
2716     /* (E) */
2717     sort = codeparm;
2718     do {            /* while queue has at least two entries */
2719         i = heap[1];    /* take out least-freq entry */
2720         if (i < n)
2721             *sort++ = i;
2722         heap[1] = heap[heapsize--];
2723         downheap(1);
2724         j = heap[1];    /* next least-freq entry */
2725         if (j < n)
2726             *sort++ = j;
2727         k = avail++;    /* generate new node */
2728         freq[k] = freq[i] + freq[j];
2729         heap[1] = k;
2730         downheap(1);    /* put into queue */
2731         left[k] = i;
2732         right[k] = j;
2733     } while (heapsize > 1);
2734     /* (F) */
2735     sort = codeparm;
2736     make_len(k);
2737     make_code(nparm, lenparm, codeparm);
2738     return k;       /* return root */
2739 }
2740
2741 この関数の引数に、nparm, freqparm, lenparm, codeparm というのがある。
2742 これがなんなのかいきなりではわからないだろう。実は私にもわからない。今
2743 回の解析で特殊なのは、処理内容については私は(アルゴリズム辞典で)知って
2744 いることだ。強引に無視しても処理内容から想像がつくだろうことを期待して
2745 いる。
2746
2747 とりあえず、冒頭の初期化部分 (A) で
2748
2749     /* (A) */
2750     n = nparm;
2751     freq = freqparm;
2752     len = lenparm;
2753     avail = n;
2754
2755 としている。引数で受けた入力をこのファイルの static 変数にセットし、他
2756 のルーチンとデータ共有しているようだ。avail は後で説明しよう。
2757
2758     /* (B) */
2759     heapsize = 0;
2760     heap[1] = 0;
2761     for (i = 0; i < n; i++) {
2762         len[i] = 0;
2763         if (freq[i])
2764             heap[++heapsize] = i;
2765     }
2766
2767 ここで、heap[] を初期化している。heapsize は、heap の要素数となる。こ
2768 の処理は優先待ち行列 heap[] を作る部分なのだが、なぜ優先待ち行列が必要
2769 なのかというと先の説明で Huffman 法のアルゴリズムに出現回数の少ない順
2770 に葉を節に束ねるという部分があった。優先待ち行列はこのためのものだ。と
2771 りあえず、heap[] の要素は圧縮する文字であるということだけを書いておく。
2772 詳細はすぐ後で出るだろう。freq[i] (すなわち引数 freqparm) は、文字 i
2773 の出現回数を表している。だから、n (nparm)は、符号化するモデル上の文字
2774 の種類の数を表していることになる。たとえば通常のファイルなら nparm は
2775 256 だろう。まあ、結局は freq[] の要素数だ。
2776
2777     nparm               最大要素数
2778     freqparm[0:nparm]   添字が文字で、その要素が出現回数
2779
2780 注意すべきなのは heap[] の要素は 1 以降を使用していることだろう。
2781 heap[0] は使われない。
2782
2783     /* (C) */
2784     if (heapsize < 2) {
2785         codeparm[heap[1]] = 0;
2786         return heap[1];
2787     }
2788
2789 これは、heapsize が 0 か 1 の場合を表している。符号化する文字の種類が
2790 0 または 1 つしかない場合だ。heap[1] は、(B) で 0 に初期化していたので、
2791 codeparm[0] = 0 として、0 を返している。これは特殊な条件を示している。
2792 簡単に想像がつくことだが、出現する文字の種類が1種類しかない場合、ハフ
2793 マン木を作る必要がない。LHa ではこのような場合に特殊な構造あるいは方法
2794 を用いていることが想像できる。
2795
2796     /* (D) */
2797     for (i = heapsize / 2; i >= 1; i--)
2798         downheap(i);    /* make priority queue */
2799
2800 優先待ち行列 heap[] を構築する。downheap() がなんなのか、これがどういっ
2801 た処理なのかの詳細は省略しよう。アルゴリズム辞典の「ヒープソート」の項
2802 に詳しいが、heap[] は木構造を示しており、この木構造(2分木)には「親は子
2803 より優先順位が同じか高い」という規則だけがある。この木構造は、
2804
2805         1. heap[n] の左の子は heap[2*n]、右の子は heap[2*n + 1]
2806
2807 で、表現されており、このような半順序木 (partial ordered tree) には、以
2808 下の特徴がある
2809
2810         2. heap[n] の親は heap[n/2]
2811         3. heap[1.. heapsize/2] は節で、heap[heapsize/2 .. heapsize] は葉
2812
2813 この heap[] が最初ばらばらに要素が格納されているとき、葉に近い節から順
2814 に downheap() という操作を行う((D)の処理)と、ヒープを構築できるように
2815 なっている。downheap(i) は、節 heap[i] とその子 heap[2*i], heap[2*i+1]
2816 で要素を比較し、子の優先順位の方が高ければ位置を交換する、という処理を
2817 葉に向かって繰り返す関数だ。以下、参考までに maketree.c:downheap() の
2818 内容を示す。
2819
2820 static void
2821 downheap(i)
2822 /* priority queue; send i-th entry down heap */
2823     int             i;
2824 {
2825     short           j, k;
2826
2827     k = heap[i];
2828     while ((j = 2 * i) <= heapsize) {
2829         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
2830             j++;
2831         if (freq[k] <= freq[heap[j]])
2832             break;
2833         heap[i] = heap[j];
2834         i = j;
2835     }
2836     heap[i] = k;
2837 }
2838
2839 とにかく (D) により、最も優先順位の高い(出現回数の少ない)要素が
2840 heap[1] に来るようになる。この優先待ち行列はなかなか面白い(と私は思っ
2841 た)のでいろいろと調べてみるのもよいだろう。
2842
2843 さて、続けよう (E) だ。
2844
2845     /* (E) */
2846     sort = codeparm;
2847     do {            /* while queue has at least two entries */
2848         i = heap[1];    /* take out least-freq entry */
2849         if (i < n)
2850             *sort++ = i;
2851         heap[1] = heap[heapsize--];
2852         downheap(1);
2853         j = heap[1];    /* next least-freq entry */
2854         if (j < n)
2855             *sort++ = j;
2856         k = avail++;    /* generate new node */
2857         freq[k] = freq[i] + freq[j];
2858         heap[1] = k;
2859         downheap(1);    /* put into queue */
2860         left[k] = i;
2861         right[k] = j;
2862     } while (heapsize > 1);
2863
2864 最初に、
2865
2866         i = heap[1];    /* take out least-freq entry */
2867         if (i < n)
2868             *sort++ = i;
2869
2870 で、最も出現回数の少ない文字を取って来る。if の部分はひとまず無視しよう。
2871
2872         heap[1] = heap[heapsize--];
2873         downheap(1);
2874
2875 で、heap[] の最後尾の要素を先頭に持って来て downheap(1) を行っている。
2876 こうすると、ヒープが再構築され「親は子より優先順位が同じか高い」という
2877 条件をまた満たすようになる。heap[] の要素は1つ減っている。結局、ここま
2878 での処理は論理的には「優先待ち行列から優先度の高い要素を1つ取り出す」
2879 と言う処理だ。
2880
2881         j = heap[1];    /* next least-freq entry */
2882         if (j < n)
2883             *sort++ = j;
2884
2885 続けて、2番目に優先度の高い要素を取り出す。また、if は無視しておこう。
2886
2887         k = avail++;    /* generate new node */
2888         freq[k] = freq[i] + freq[j];
2889         heap[1] = k;
2890         downheap(1);    /* put into queue */
2891
2892 avail は最初 n (nparm)だった。freq[] は、文字の出現回数なので最初文字
2893 の種類数分(nparm)の要素しかないがハフマン木の節の出現回数(というか優先
2894 順位)を格納するために freq[] は、nparm * 2 - 1 の格納域が必要となるこ
2895 とがわかる。(葉が n 個ある 2 分木には、節が n - 1 個ある)
2896
2897 ----------------------------------------------------------------------------
2898
2899      +-----------------------+-----------------------+
2900 freq |                       |                       |
2901      +-----------------------+-----------------------+
2902      0                       nparm                   nparm * 2 - 1
2903
2904      |-----------------------|-----------------------|
2905       文字(ハフマン木の葉)    ハフマン木の節の優先順位
2906       の優先順位
2907
2908
2909       例:
2910                  .     ... freq[4]
2911                 / \
2912                .   \   ... freq[3]
2913               /\    \
2914              a  b    c ... freq[0 .. 2]
2915
2916 ----------------------------------------------------------------------------
2917
2918 ここまでで、出現回数の低い2つの要素を取り出しその出現回数の和を
2919 freq[k] に設定することになる。出現回数の和は heap[] に再設定され、
2920 downheap(1) で、優先待ち行列をまた再構築する。これは「葉を束ね節を作る」
2921 というハフマン木の構築アルゴリズムの実装だ。新しく作成した節が k でそ
2922 の最大値が最終的に avail-1 である。
2923
2924 最後に
2925
2926         left[k] = i;
2927         right[k] = j;
2928
2929 で、ハフマン木を構造 left[]、right[] で作成する。
2930
2931 この (E) を抽象度の高いコードで示してみよう。ハフマン木は
2932     struct huffman {
2933        ...
2934     } huff;
2935
2936 で表し、ハフマン木の1つの節は、
2937     make_huff(huff, node, left, right)
2938 で作成できるとする。また、優先順位つき待ち行列を heap とし、heap から
2939 要素を取り出す処理、要素を格納する処理をそれぞれ仮に
2940         n = delete_pqueue(heap)
2941         insert_pqueue(heap, n)
2942 とすると、
2943
2944     /* (E) */
2945     do {
2946         left = delete_pqueue(heap);
2947         right = delete_pqueue(heap);
2948
2949         node = avail++;
2950         freq[node] = freq[left] + freq[right];
2951
2952         insert_pqueue(heap, freq[node]);
2953
2954         make_huff(&huff, node, left, right);
2955     } while (heapsize > 1);
2956
2957 こんなところだろうか。元の処理ではヒープからの要素の取り出しと挿入で無
2958 駄な処理を無くすために少し複雑になっている。(そしてデータ構造に依存し
2959 た処理になっている)。どちらがよりすぐれているかは微妙な所だ。私は多少
2960 の処理の無駄も目をつぶってよりわかりやすい方を優先するのが好きなのだが。
2961 これはちょっと考えさせられるところだ。
2962
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] は使われないようだ。
2967
2968 ----------------------------------------------------------------------------
2969       例:
2970                  . -- k (= avail-1)
2971                 / \
2972    left[k] --  .   \
2973               /\    \
2974              a  b    c -- right[k]
2975              |   \
2976              |    right[left[k]]
2977           left[left[k]]
2978
2979 ----------------------------------------------------------------------------
2980
2981 これで、ハフマン木の構築は終りなのだが、ハフマン法の符号化ではハフマン
2982 木の葉から根に向かって木を辿る必要があるはずなのに、left[]、right[] の
2983 構造では根から葉に向かってしか木を辿ることができないはずだ。これはどう
2984 いうことだろう？make_tree() ではまだ処理が続いている。
2985
2986     /* (F) */
2987     sort = codeparm;
2988     make_len(k);
2989     make_code(nparm, lenparm, codeparm);
2990     return k;       /* return root */
2991
2992 どうやら、木構造の他にもなにやら構造を作成しているようだ。これは先程無
2993 視した if 文にも関連する。そしてこれは「アルゴリズム辞典」には載ってい
2994 ない部分だ。どうやら LHa なりの工夫があるようだ。
2995
2996 まず、maketree.c:make_len(root) から見てみようと思うが、その前にこの関
2997 数は maketree.c:count_len(root) という関数を呼び出している。こちらから
2998 先に見ることにした。
2999
3000 static void
3001 count_len(i)            /* call with i = root */
3002     int             i;
3003 {
3004     static unsigned char depth = 0;
3005
3006     if (i < n)
3007         len_cnt[depth < 16 ? depth : 16]++;
3008     else {
3009         depth++;
3010         count_len(left[i]);
3011         count_len(right[i]);
3012         depth--;
3013     }
3014 }
3015
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 先ほど構築したハフマン木に関して、ある深さの葉の数を数えているようだ。
3027
3028 len_cnt[1] は、深さ 1 (根の子)の葉の数で 0 〜 2 の値になる。len_cnt[2]
3029 は、深さ 2 (根の孫)の葉の数で 0 〜 4 の値を持つだろう。そして、深さ 16
3030 以上の層に関しては len_cnt[16] にすべて計上されるようだ。とにかくその
3031 ような処理だということでこの関数を終え、make_len() を見よう。
3032
3033 static void
3034 make_len(root)
3035     int             root;
3036 {
3037     int             i, k;
3038     unsigned int    cum;
3039
3040     /* (A) */
3041     for (i = 0; i <= 16; i++)
3042         len_cnt[i] = 0;
3043     count_len(root);
3044     /* (B) */
3045     cum = 0;
3046     for (i = 16; i > 0; i--) {
3047         cum += len_cnt[i] << (16 - i);
3048     }
3049 #if (UINT_MAX != 0xffff)
3050     cum &= 0xffff;
3051 #endif
3052     /* (C) */
3053     /* adjust len */
3054     if (cum) {
3055         fprintf(stderr, "17");
3056         len_cnt[16] -= cum; /* always len_cnt[16] > cum */
3057         do {
3058             for (i = 15; i > 0; i--) {
3059                 if (len_cnt[i]) {
3060                     len_cnt[i]--;
3061                     len_cnt[i + 1] += 2;
3062                     break;
3063                 }
3064             }
3065         } while (--cum);
3066     }
3067     /* (D) */
3068     /* make len */
3069     for (i = 16; i > 0; i--) {
3070         k = len_cnt[i];
3071         while (k > 0) {
3072             len[*sort++] = i;
3073             k--;
3074         }
3075     }
3076 }
3077
3078 ちょっと複雑だがゆっくり見ていこう。まず (A) の初期化部分は先ほどの
3079 count_len() を呼び出すだけのものなのでもうよいだろう。
3080
3081     /* (A) */
3082     for (i = 0; i <= 16; i++)
3083         len_cnt[i] = 0;
3084     count_len(root);
3085
3086 これで、len_cnt[1..16] にはハフマン木の各層の葉の数が計上される。続いて (B)
3087
3088     /* (B) */
3089     cum = 0;
3090     for (i = 16; i > 0; i--) {
3091         cum += len_cnt[i] << (16 - i);
3092     }
3093 #if (UINT_MAX != 0xffff)
3094     cum &= 0xffff;
3095 #endif
3096
3097 これは、どういうことだろう？len_cnt[] は short の配列だが、とにかく以
3098 下のような計算(len_cnt[] の要素を 1 ビットずらしながら足す)をしている。
3099 最後に int 型のサイズが 2 でない場合 0xffff で論理積をしているので 2バ
3100 イトの符号なし整数を結果として欲しいらしい。
3101
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ビット)
3107 +     :                                                   :
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 ----------------------------------------------------------------------------
3114
3115 ここで、len_cnt[] の各要素の値が各層の葉の数であることを考えると、各要
3116 素で使用するビット数との関連が見える。
3117
3118               取り得る
3119               値の範囲      使用ビット数
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ビット
3124      :
3125  len_cnt[ 3]  0.. 2^3        4 ビット
3126  len_cnt[ 2]  0.. 2^2        3 ビット
3127  len_cnt[ 1]  0.. 2^1        2 ビット
3128
3129 先の計算式では len_cnt[] の各要素で使用し得るビット数から 1 引いたビッ
3130 ト数が計算に使用されている。例えば根の子がすべて葉なら len_cnt[1] は、
3131 2 になり、2進で、00000000 00000010 だが、cum の計算にはこの下位 1 ビッ
3132 トしか使用されない。
3133
3134        /\
3135       a  b     .. len_cnt[1] = 00000000 00000010
3136                                                |
3137                                                v
3138                                          cum = x0000000 00000000
3139
3140 根の孫がすべて葉なら len_cnt[2] は、4 になり、2進で、00000000 00000100
3141 だが、cum の計算にはこの下位 2 ビットしか使用されない。
3142
3143        / \     .. len_cnt[1] = 00000000 00000000
3144       /\ /\
3145      a b c d   .. len_cnt[2] =  00000000 00000100
3146                                                ||
3147                                                vv
3148                                          cum = xx000000 00000000
3149
3150 このようにある層のすべてが葉であるようなバランスのよいハフマン木に
3151 対しては先の計算結果 cum は 0 になるらしい。
3152
3153 また、
3154        /\
3155       a /\     .. len_cnt[1] = 00000000 00000001
3156         b c    .. len_cnt[2] =  00000000 00000010
3157                                                ||
3158                                                vv
3159                                          cum = xx000000 00000000
3160
3161 のような木に対しても計算結果はオーバーフローされ cum は 0 になる。
3162
3163        /\
3164       a /\       .. len_cnt[1] = 00000000 00000001
3165        b /\      .. len_cnt[2] =  00000000 00000001
3166         c  d     .. len_cnt[3] =   00000000 00000010
3167                                                  |||
3168                                                  vvv
3169                                            cum = xxx00000 00000000
3170
3171 も同様に cum は 0 だ。結局 cum が 0 にならない木とはある節が 1 つの葉
3172 しかもたないような場合であるらしい。
3173
3174        /\
3175       a /\       .. len_cnt[1] = 00000000 00000001
3176        b  \      .. len_cnt[2] =  00000000 00000001
3177            d     .. len_cnt[3] =   00000000 00000001
3178                                                  |||
3179                                                  vvv
3180                                            cum = 11100000 00000000
3181
3182 そして、ハフマン木の作り方からこのようなことは起こりえないのではないか
3183 と思える。
3184
3185 (C) では、if (cum) で、この起こりえないハフマン木の場合になにか処理を
3186 行っている。まったく謎であるが、まず、この (C) を特殊条件とみなして先
3187 に (D) の方を見ることにしよう。
3188
3189     /* (D) */
3190     /* make len */
3191     for (i = 16; i > 0; i--) {
3192         k = len_cnt[i];
3193         while (k > 0) {
3194             len[*sort++] = i;
3195             k--;
3196         }
3197     }
3198
3199 sort は何かというと、make_tree() の引数に渡された codeparm を指してい
3200 る。この配列の中には(ハフマン木を構築する際に設定されていたのだが)、出
3201 現頻度の低い順で平文の文字コードが入っている。make_tree() で、sort に
3202 値を設定する際、
3203
3204         if (j < n)
3205             *sort++ = j;
3206
3207 のように条件判断があったので、sort[] にはハフマン木の節は入っていない。
3208 そしてハフマン木はその構築の仕方から出現頻度の低い文字は木のより深い場
3209 所に位置づけられている。これらのことから make_len()で求めようとしてい
3210 るものが何なのかがわかる。make_len() は、
3211     len[文字] = ハフマン木の深さ
3212 といった対応表を作成する処理だ。さらに言うとハフマン木の深さは文字を符
3213 号化した結果のビット数を表すことから
3214     lenparm[文字] = 符号語のビット数
3215 といった対応表を作成する処理であると言った方が正解だろう。
3216 len[] は、make_tree() の冒頭で、lenparm を指すように設定された変数なの
3217 で、そのように置き換えておいた。
3218
3219 では、謎の (C) を見よう。その前に cum != 0 は起こりえないと書いたがよ
3220 く考えたら len_cnt[16] だけは深さ16以上の葉すべての数を計上しているた
3221 め、どのような値もあり得る。つまり、この (C) の処理はハフマン木が深さ
3222 17 以上になったときに処理されるものだと言えそうだ。思い切って図示しよ
3223 う例えばこんな木は、(C)の処理対象となる。
3224
3225        /\
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                       ||||||||||||||||
3243                                                  vvvvvvvvvvvvvvvv
3244                                            cum = 0000000000000001
3245
3246 このような木は例えば各文字が以下の出現頻度となるファイルを作成すると起
3247 こる(実際には、LHA の場合、slide 辞書法の処理もあるのでこれほど単純で
3248 はない)。
3249
3250         文字    頻度        文字    頻度
3251         ------------        ------------
3252         r          1        i        256
3253         q          1        h        512
3254         p          2        g       1024
3255         o          4        f       2048
3256         n          8        e       4096
3257         m         16        d       8192
3258         l         32        c      16384
3259         k         64        b      32768
3260         j        128        a      65536
3261
3262 ところで、cum の値は何なのかというと、
3263
3264                                                         :
3265                                .. len_cnt[15] = 0000000000000001
3266                      p /\       .. len_cnt[16] = 0000000000000100
3267                       q /\                       ||||||||||||||||
3268                        r  s                      vvvvvvvvvvvvvvvv
3269                                            cum = 0000000000000010
3270
3271 この場合は cum = 2 だ。
3272                                                         :
3273                                .. len_cnt[15] = 0000000000000001
3274                      p /\       .. len_cnt[16] = 0000000000000101
3275                       q /\                       ||||||||||||||||
3276                        r /\                      vvvvvvvvvvvvvvvv
3277                         s  t               cum = 0000000000000011
3278
3279 この場合は cum = 3 だ。少なくともこの例では深さ 16 以上の葉の数 - 2に
3280 なるらしい(そうか、11111111 11111110 = -2 を足しているのだから当然だ)。
3281
3282 では、今度こそ (C) を見る。
3283
3284     /* (C) */
3285     /* adjust len */
3286     if (cum) {
3287         fprintf(stderr, "17");
3288         len_cnt[16] -= cum; /* always len_cnt[16] > cum */
3289         do {
3290             for (i = 15; i > 0; i--) {
3291                 if (len_cnt[i]) {
3292                     len_cnt[i]--;
3293                     len_cnt[i + 1] += 2;
3294                     break;
3295                 }
3296             }
3297         } while (--cum);
3298     }
3299
3300 である。いきなり fprintf() しているところがすごい。デバッグ用の出力が
3301 残っているのだろう。LHa for UNIX で 17 という出力を見たことがある人は
3302 教えて欲しい。
3303
3304 で・・・、結局この (C) の部分は見てもよくわからなかった。ここまで書い
3305 ておいてなんだが、気持ちよく無視することにした。
3306
3307 では、make_tree() から呼び出される最後の関数、maketree.c:make_code()
3308 を見よう。make_code() は、make_tree() の(F) の部分で以下のように呼ばれ
3309 ていた。
3310
3311     make_code(nparm, lenparm, codeparm);
3312
3313 この引数のうち、lenparm[] は先ほどの make_len[] で値が作られたものだが、
3314     lenparm[文字] = 符号語のビット数
3315 という対応表だった。codeparm[] は、先ほども出たが make_tree() の中で設
3316 定されているものだった。出現頻度の低い順で平文の文字コードが入った配列
3317 だ。
3318
3319 void
3320 make_code(n, len, code)
3321     int             n;
3322     unsigned char   len[];
3323     unsigned short  code[];
3324 {
3325     unsigned short  weight[17]; /* 0x10000ul >> bitlen */
3326     unsigned short  start[17];  /* start code */
3327     unsigned short  j, k;
3328     int             i;
3329
3330     j = 0;
3331     k = 1 << (16 - 1);
3332     for (i = 1; i <= 16; i++) {
3333         start[i] = j;
3334         j += (weight[i] = k) * len_cnt[i];
3335         k >>= 1;
3336     }
3337     for (i = 0; i < n; i++) {
3338         j = len[i];
3339         code[i] = start[j];
3340         start[j] += weight[j];
3341     }
3342 }
3343
3344 # 後で気がついたことだが、あらかじめ設定していた codeparm[] の内容はこ
3345 # こでは使用されない。つまり、codeparm[] は先程はワーク用のバッファと
3346 # して利用されていたが、ここでの codeparm[] は処理結果を表すという二つ
3347 # の役割がある。これは、領域を節約するための変数の使い回しだ。
3348
3349 最初の for 文では、変数 i に対して、weight[i] が下のように設定される
3350
3351   weight[i=1..16] = 2^(16-i)
3352
3353 そして、start[i] は、
3354
3355   start[1] = 0
3356   start[n] = start[n-1] + weight[n-1] * len_cnt[n-1]   (n > 1)
3357
3358 という漸化式だ。start[] の添字 i は、len_cnt[i](深さ i の葉の数)の添字
3359 でもあることから、ハフマン木の深さを表している。start が実際にどのよう
3360 な値を取るかと言うと、例えば len_cnt[i] の各要素が Li であった場合、
3361
3362      i     len_cnt[i]   weight[i]   start[i]
3363  --------------------------------------------
3364      1         L1        2^15       0
3365      2         L2        2^14      2^15 * L1
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
3368
3369 こんな感じだ。これはいったい何だろうか？続く for 文を見てみよう。
3370
3371     for (i = 0; i < n; i++) {
3372         j = len[i];
3373         code[i] = start[j];
3374         start[j] += weight[j];
3375     }
3376
3377 ここでの i は、0...n の範囲であることから平文の文字を示す。紛らわしい
3378 ので、i は、c に書き換え、j を i にしよう。(これで、i は前の for 文の
3379 i と同じ意味になる)
3380
3381     int c;
3382
3383     for (c = 0; c < n; c++) {
3384         i = len[c];
3385         code[c] = start[i];
3386         start[i] += weight[i];
3387     }
3388
3389 i = len[c] は文字 c のビット長で、ハフマン木の深さを示す。
3390 code[c] には、start[i] が設定されるが、一度 start[i] が参照されると
3391 start[i] は、weight[i] を足した値が次回使われる。例えば、ある文字
3392 a, b, c がそれぞれ以下のハフマン木で表現されたとする。
3393
3394        /\               a: 0
3395       a /\              b: 10
3396         b c             c: 11
3397
3398
3399               i     len_cnt[i]   weight[i]   start[i]
3400           --------------------------------------------
3401               1         1         2^15        0
3402               2         2         2^14       2^15
3403
3404   c  len[c]   i     len_cnt[i]   weight[i]   code[c]
3405  ---------------------------------------------------
3406   a     1     1         1            2^15       0
3407   b     2     2         2            2^14      2^15
3408   c     2     2         2            2^14      2^15 + 2^14
3409
3410 こんな感じになる。別のハフマン木の場合も見てみよう。
3411
3412         /\                a: 00
3413       /\  /\              b: 01
3414      a  b c d             c: 10
3415                           d: 11
3416
3417               i     len_cnt[i]   weight[i]   start[i]
3418           --------------------------------------------
3419               1         0         2^15        0
3420               2         4         2^14        0
3421               3         0         2^13       2^14 * 4
3422
3423   c  len[c]   i     len_cnt[i]   weight[i]   code[c]
3424  ---------------------------------------------------
3425   a     2     2         4            2^14      0
3426   b     2     2         4            2^14      2^14
3427   c     2     2         4            2^14      2^14 * 2
3428   d     2     2         4            2^14      2^14 * 3
3429
3430 これで、ピント来ると凄いのだが code[c] には文字 c に対応する符号化した
3431 ビット列が設定されるようになっていることに気づくだろうか？つまりは、
3432
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
3439                                            ^^ <- ハフマン符号
3440
3441 だ。以降、code[] (実際には codeparm) を利用することで表引きで文字 c に
3442 対応するハフマン符号を得ることができるようになっている(code[c]のうち上
3443 位 len[c] ビットだけを見る)。符号化の際に木を辿る必要はなく、高速な符号
3444 化が可能になる(と期待される。どの程度効果があるかはいずれ検証してみた
3445 い。そういえば、葉から根に向かって木を辿るための情報が必要なかったこと
3446 もこれでわかった)。
3447
3448 結局 make_tree(nparm, freqparm, lenparm, codeparm) は、lenparm[c] と
3449 codeparm[c] を作成する関数だったわけだ(ハフマン表とでも言うのだろう
3450 か？)。実は、このことは make_tree() を呼び出し、 codeparm を使用してい
3451 る箇所(huf.c)を見るまでまるでわからなかった。しかも、まだちゃんと理解
3452 したわけではない。
3453
3454 ふと思ったのだが、上記の表作成は文字コード順に依存している(コードの若
3455 い方が左の子になる)が、木を作成する場合はそのようなことはなかったはず
3456 だ。ハフマン木を辿った場合と表を参照した場合とでは得られる符号語は異な
3457 るのではないだろうか？ということは圧縮文に埋め込まれるのは木ではなくこ
3458 の表の方だということも想像がつく。木の構造を表す left[]、right[] はグ
3459 ローバル変数だが、実際には make_tree() 内でしか使われないのかも知れな
3460 い(少なくとも符号化に関してはそのようだ。huf.c を眺めるとどうやら復号
3461 時は left[]、right[]は使われるらしい)。
3462
3463 さらにふと思い付いた。謎の (C) のコードだが 深さ 17 以上の木が作成され
3464 た場合に木を再構築する処理だということがわかった。最初、len_cnt[] (あ
3465 る深さの葉の数) だけが、操作されていたからよくわからなかったのだ、
3466
3467     /* (C) */
3468     /* adjust len */
3469     if (cum) {
3470         fprintf(stderr, "17");
3471         len_cnt[16] -= cum; /* always len_cnt[16] > cum */
3472         do {
3473             for (i = 15; i > 0; i--) {
3474                 if (len_cnt[i]) {
3475                     len_cnt[i]--;
3476                     len_cnt[i + 1] += 2;
3477                     break;
3478                 }
3479             }
3480         } while (--cum);
3481     }
3482
3483 深さ i の葉の数を 1 つ減らして、その下の葉の数を 2 足している。
3484 これが、cum の数だけ繰り返される。例えば、前にも出た
3485
3486                                                      :
3487                    n /\       .. len_cnt[14] = 0000000000000001
3488                     o /\       .. len_cnt[15] = 0000000000000001
3489                      p /\       .. len_cnt[16] = 0000000000000011
3490                       q  r                       ||||||||||||||||
3491                                                  vvvvvvvvvvvvvvvv
3492                                            cum = 0000000000000001
3493
3494 の例では、最初に len_cnt[16] から cum {1} が引かれ、
3495
3496                                                      :
3497                    n /\       .. len_cnt[14] = 0000000000000001
3498                     o /\       .. len_cnt[15] = 0000000000000001
3499                      p /       .. len_cnt[16] = 0000000000000010
3500                       q
3501
3502 続いて、深さ 15 より上の葉のある節から 1 つ子を取り、
3503
3504                                                      :
3505                    n /\       .. len_cnt[14] = 0000000000000001
3506                       /\       .. len_cnt[15] = 0000000000000000
3507                      p /        .. len_cnt[16] = 0000000000000010
3508                       q
3509
3510 下の葉の数(この例では、len_cnt[16])を 2 足している。
3511
3512                 /   \
3513               n    /  \       .. len_cnt[14] = 0000000000000001
3514                  /\    /\      .. len_cnt[15] = 0000000000000000
3515                 o  r  p /       .. len_cnt[16] = 0000000000000100
3516                        q
3517
3518 cum は、この例では 0 になるので、これで木の平滑化は終る。テキストだと
3519 ちょっと見にくいが、そういう処理ということで間違いないだろう。
3520 lenparm[] の値はこの後の (D) で、この木を元に計算されている。
3521
3522 ところで、本当の所は以下のような文字の対応になる(表を作成するときに文
3523 字コード順になっているため)のだが、結果的に元の木から p を含む節を取り
3524 除き o の位置に挿入する処理になっている。なんだか面白い。
3525
3526                 /   \
3527               n    /  \       .. len_cnt[14] = 0000000000000001
3528                  /\    /\      .. len_cnt[15] = 0000000000000000
3529                 o  p  q  r      .. len_cnt[16] = 0000000000000100
3530
3531 文字から Huffman 符号が得られるようになったので、圧縮処理を行う道具は
3532 揃った。いよいよ Huffman 法による圧縮処理全般 (huf.c) を見ることにしよ
3533 う。
3534
3535 まず huf.c で定義されているデータ構造から確認しよう。データ構造がわかっ
3536 てしまえばアルゴリズムの 90% はわかったも同然だ(誇張)。
3537
3538 huf.c には以下の変数が定義されている。
3539
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];
3544
3545 static unsigned char *buf;
3546 static unsigned int bufsiz;
3547 static unsigned short blocksize;
3548 static unsigned short output_pos, output_mask;
3549 static          int   pbit;
3550 static          int   np;
3551
3552 使用されている定数も確認する lha_macro.h だ。
3553
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  */
3560 #define NPT         0x80
3561 #define CBIT                9   /* $\lfloor \log_2 NC \rfloor + 1$ */
3562
3563 たくさんある。たくさんありすぎてくじけそうだが(事実、くじけた)、現時点
3564 でわかる変数もある。left[] や right[] は Huffman 木を構築するのに使用
3565 した変数だった。そこから NC は文字種の最大数であることがわかる。NC に
3566 MAXMATCH{256} 等の値が使用されているのは謎だが、現時点では無視しておこ
3567 う。
3568
3569 c_freq[] や c_len[], p_freq[], pt_len[] も make_tree() で出て来た変数
3570 名に似ている。おそらく make_tree() に渡す変数だろう。確認してみたとこ
3571 ろ huf.c から make_tree() の呼び出しを行っている部分を抜き出すと、
3572
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);
3576
3577 の 3 箇所が出て来た。つまり、
3578
3579    文字種の数  文字の出現回数   符号化した文字  文字に対応する
3580                                 の bit 長       Huffman 符号表
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
3585
3586 という関係のようだ。どうやら c_code、pt_code という 2 種類の
3587 Huffman 符号表を使用するらしい。
3588
3589 # あとでわかることだが実際は 3 種類の Huffman 符号表を作っており
3590 # pt_code は変数が使い回しされている。変数の使用領域を減らし
3591 # たかったのだろう。
3592
3593 その他の変数に関しても予想を立てたい所だが、もうくじけたので、処理内容
3594 から攻めることにした。
3595
3596 slide 辞書法の解読で Huffman 法に関連した処理の呼び出しがいくつかあっ
3597 た。
3598
3599     /* initialize */
3600     alloc_buf()
3601
3602     /* encoder */
3603     encode_set.encode_start()
3604     encode_set.output(c, off)
3605     encode_set.encode_end()
3606
3607     /* decoder */
3608     decode_set.decode_start()
3609     decode_set.decode_c()
3610     decode_set.decode_p()
3611
3612 以上だ。lh4, 5, 6, 7 では、上記のそれぞれは、huf.c の以下の関数の呼び
3613 出しに対応している。これは、slide.c の冒頭部分で定義されている。
3614
3615     /* encoder */
3616     encode_start() -> encode_start_st1()
3617     output()       -> output_st1()
3618     encode_end()   -> encode_end_st1()
3619
3620     /* decoder */
3621     decode_start() -> decode_start_st1()
3622     decode_c()     -> decode_c_st1()
3623     decode_p()     -> decode_p_st1()
3624
3625 このうちの圧縮処理にあたる部分 encode_start_st1(), output_st1(),
3626 encode_end_st1() を見ていこう。まずは、初期化処理である
3627 encode_start_st1() から、
3628
3629 void
3630 encode_start_st1( /* void */ )
3631 {
3632     int             i;
3633
3634     if (dicbit <= 13) {
3635         pbit = 4;   /* lh4,5 etc. */
3636         np = 14;
3637     } else {
3638         pbit = 5;   /* lh6,7 */
3639         if (dicbit == 16)
3640             np = 17;
3641         else
3642             np = 16;
3643     }
3644
3645     for (i = 0; i < NC; i++)
3646         c_freq[i] = 0;
3647     for (i = 0; i < np; i++)
3648         p_freq[i] = 0;
3649     output_pos = output_mask = 0;
3650     init_putbits();
3651     buf[0] = 0;
3652 }
3653
3654 dicbit (これは辞書の bit サイズだった)によって、np, pbit の値が変わる。
3655 dicbit の違いというのは LHa の encoding メソッドの違いだ。それぞれ以下
3656 の対応になる。
3657
3658     method  dicbit  np  pbit
3659    --------------------------
3660     -lh4-   12      14  4
3661     -lh5-   13      14  4
3662     -lh6-   15      16  5
3663     -lh7-   16      17  5
3664
3665 np というのは、先程 make_tree() を呼び出している箇所の洗い出しで見かけ
3666 た変数だった。まだ、この関連はよくわからない。
3667
3668 処理の後半では、文字の出現頻度を表す c_freq[]、p_freq[] の初期化を
3669 行っている。さらに
3670
3671     output_pos
3672     output_mask
3673     buf[]
3674
3675 という初出の変数も 0 に初期化している。(buf は、buf[0] のみ初期化して
3676 いる) init_putbits() の呼び出しは bit 出力ルーチンの初期化処理だった。