global variable unpackable, compsize and origsize was removed

[lha/olha.git] / encode.txt

#-*- indent-tabs-mode: nil -*-

まず、グローバル変数の洗い出し

text
childcount
pos
matchpos
avail
position
parent
prev
next
remainder
matchlen
level

これらをすべて理解すれば、ソース解析は完了と思ってよい。
この段階では、変数名とソースの概観から木を使ってるっぽい程度に認識する。
アルゴリズムの予想がある程度立っている場合は、変数名からその用途を予想しても
良い。私はわからなかったのでとっとと次に進むことにする。

次に、処理をトップダウンで解析する。

encode(void)
{
    int lastmatchlen;
    node lastmatchpos;

    (A)
    allocate_memory();
    (B)
    init_slide();

    (C)
    huf_encode_start(opts.method);

    (D)
    remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);

    (E)
    if (outfile != stdout && opts.quiet < 1) {
        putc('.', stdout);
    }

    (F)
    matchlen = 0;
    pos = DICSIZ;
    insert_node();

    (G)
    if (matchlen > remainder)
        matchlen = remainder;

    (H)
    while (remainder > 0 && !unpackable) {
        lastmatchlen = matchlen;
        lastmatchpos = matchpos;
        get_next_match();
        if (matchlen > remainder)
            matchlen = remainder;
        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
            output(text[pos - 1], 0);
        else {
            output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
                   (pos - lastmatchpos - 2) & (DICSIZ - 1));
            while (--lastmatchlen > 0)
                get_next_match();
            if (matchlen > remainder)
                matchlen = remainder;
        }
    }

    (I)
    huf_encode_end();
}

注目すべきところに適当に記号を割り振る。


(A) allocate_memory() を見ると以下のようなメモリ割り当てを行っている。
(B) の初期化に該当する部分もある程度（適当に）図示した。


                             dicsiz                dicsiz*2
                            /                     /
     +---------------------+---------------------+----+
text |                     |                     |    |
     +---------------------+---------------------+----+
                                                 |----|
                                                  maxmatch

                            dicsiz(8192)
                           /
     +---------------------+---+
level|                     |111|
     +---------------------+---+
                           |--|
                            UCHAR_MAX(255) + 1


                            dicsiz
                           '
position                   |
     +---------------------+---+
     |                     |NIL|
     +---------------------+---+
                           |---|
                            UCHAR_MAX(8) + 1

parent
     +---------------------+---------------------+
     |                     |   NIL               |
     +---------------------+---------------------+


     +---------------------+---------------------+
prev |                     |                     |
     +---------------------+---------------------+

                             DICSIZ                DICSIZ*2             max_hash_val + 1
                            /                     /                          /
     +---------------------+---------------------+---------------------+----+
next | 234...           NIL|                     | NIL                 |    |
     +---------------------+---------------------+---------------------+----+


なお、サイズは適当だ。ざっと上記のようにまとめて次に移る

(C) huf_encode_start() は、Huffman coding の初期化であることを
既にLHa for UNIXの解析で知っているので、次に進む。

(D) 圧縮対象のファイルを読み込んで text の右半分に書き込んでいる。

(E) 単に圧縮の進行状況を画面に出力する（ために、最初の "."を出力している）
だけ、無視する。

(F) matchlen, pos を初期化して insert_node() を呼んでいる。
insert_node() をざっと見ても内容はすぐにわからなさそうなので、
いったん無視して次に進む。

(G) if (matchlen > remainder) という判定を行っている。(F)の段階で、
matchlen = 0 の設定を行っているので、insert_node() にて、matchlen
が変更される場合があるのだろう程度に考える。おそらくは、insert_node()
実行後の例外条件に対応しているのではないかと予想しつつ次に進む。

(H) ちょっと長いが、LHa for UNIX の解析により以下の通り要約できるのでは
ないかと予想する。


    /* ファイルの残りがある間ループ */
    while (remainder > 0 && !unpackable) {

        /* 前回のマッチを記録 */
        lastmatchlen = matchlen;
        lastmatchpos = matchpos;

        /* 次のマッチを行う */
        get_next_match();


        /* 例外条件 */
        if (matchlen > remainder)
            matchlen = remainder;

        /* 次のマッチした長さが前回よりも大きいか、前回のマッチが
        THRESHOLDよりも小さい場合は、前回のマッチを出力する */
        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
            output(text[pos - 1], 0);
        else {
            /* 前回のマッチの方が最適であるなら、マッチ長と位置を出力する */
            output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
                   (pos - lastmatchpos - 2) & (DICSIZ - 1));

            /* 前回のマッチ長分のマッチを繰り返す。 */
            while (--lastmatchlen > 0)
                get_next_match();

            /* 例外条件 */
            if (matchlen > remainder)
                matchlen = remainder;
        }
    }

おおよそ、LHa for UNIX のスライド辞書のアルゴリズムと同様の処理が
見える。

(I) huf_encode_end() にて、Huffman coding の後処理を行う。

以上から、スライド法の出力ループは(H)が、単語のマッチをinsert_node()
と get_next_match() が実行していることがわかる。
また、insert_node() が最初のループの直前だけしか呼ばれていないことから
insert_node() と get_next_match() の処理は似ているのではないかと
勘で予想する。

とにかく、insert_node() および get_next_match() の解析を進める
べきであることがわかる。

前の予想があっているかどうか、insert_node() および get_next_match()
を並べて比べてみる。

・・・見たところ、insert_node() の処理は大きい、また get_next_match()
は予想以上に小さく、どうやら勘ははずれてこの二つの処理は違うことを行っ
ているらしい。

予想に反して get_next_match() の処理内容は短いので、こちらを先に
解析することにした。

static void
get_next_match(void)
{
    int n;

    (A)
    remainder--;

    (B)
    if (++pos == DICSIZ * 2) {
        memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
        n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
        remainder += n;
        pos = DICSIZ;
        if (outfile != stdout && opts.quiet < 1) {
            putc('.', stdout);
        }
    }

    (C)
    delete_node();
    (D)
    insert_node();
}

(A) 残りサイズを縮めている。一文字読み進んでいるということだろう。

(B) pos を一つ進めている。remainder と対応しているのだろう。
なお、if 分の中身は例外条件(pos が端に到達した場合)であるので、
無視することにする。（ざっと見ればファイルを読み込んで各変数を
再度初期化しているだけであることはわかる）

(C), (D) ここがこの処理のメインである。delete_node() して
insert_node() している。
結局、マッチ処理は処理の冒頭にて最初に insert_node() していることから
このinsert_node()の部分ではないか？また、delete_node() は「次」を
行うのに必要な処理なのではないかとなんとなく考える。

ここで、insert_node() と delete_node() のいずれを読むべきか？
insert_node() は処理が複雑なので、delete_node() の方を読み進めることと
した。

static void
delete_node(void)
{
#if PERCOLATE
    node q, r, s, t, u;
#else
    node r, s, t, u;
#endif

    if (parent[pos] == NIL)
        return;
    r = prev[pos];
    s = next[pos];
    next[r] = s;
    prev[s] = r;
    r = parent[pos];
    parent[pos] = NIL;
    if (r >= DICSIZ || --childcount[r] > 1)
        return;
#if PERCOLATE
    t = position[r] & ~PERC_FLAG;
#else
    t = position[r];
#endif
    if (t >= pos)
        t -= DICSIZ;
#if PERCOLATE
    s = t;
    q = parent[r];
    while ((u = position[q]) & PERC_FLAG) {
        u &= ~PERC_FLAG;
        if (u >= pos)
            u -= DICSIZ;
        if (u > s)
            s = u;
        position[q] = (s | DICSIZ);
        q = parent[q];
    }
    if (q < DICSIZ) {
        if (u >= pos)
            u -= DICSIZ;
        if (u > s)
            s = u;
        position[q] = s | DICSIZ | PERC_FLAG;
    }
#endif
    s = child(r, text[t + level[r]]);
    t = prev[s];
    u = next[s];
    next[t] = u;
    prev[u] = t;
    t = prev[r];
    next[t] = s;
    prev[s] = t;
    t = next[r];
    prev[t] = s;
    next[s] = t;
    parent[s] = parent[r];
    parent[r] = NIL;
    next[r] = avail;
    avail = r;
}


なかなか複雑である。が、このまま読み進める(insert_node()よりはマシだか
ら) ここまで、PERCOLATEの部分は無視してきたが、PERCOLATEは未定義である
として読み進めることにする。PERCOLATE の部分はアルゴリズムの改善を行っ
ている部分のように思えるので、より複雑である可能性が高いからまずは基本
部分の理解を優先するためである。


PERCOLATE を未定義であるとして、処理を再掲する。

static void
delete_node(void)
{
    node r, s, t, u;

    (A)
    if (parent[pos] == NIL)
        return;
    (B)
    r = prev[pos];
    s = next[pos];
    next[r] = s;
    prev[s] = r;

    (C)
    r = parent[pos];
    parent[pos] = NIL;

    (D)
    if (r >= DICSIZ || --childcount[r] > 1)
        return;

    (E)
    t = position[r];

    (F)
    if (t >= pos)
        t -= DICSIZ;

    (G)
    s = child(r, text[t + level[r]]);

    (H)
    t = prev[s];
    u = next[s];
    next[t] = u;
    prev[u] = t;

    (I)
    t = prev[r];
    next[t] = s;
    prev[s] = t;

    (J)
    t = next[r];
    prev[t] = s;
    next[s] = t;

    (K)
    parent[s] = parent[r];
    parent[r] = NIL;
    next[r] = avail;
    avail = r;
}

これだけ削るだけでも、なんとか解析できそうな気がしてくる。モチベーショ
ンを上げることは重要である。

まずは、(A)

    if (parent[pos] == NIL)
        return;

例外条件なので、無視する。ただし、変数pos（これは現在読んでいる位置であ
るようだ)を使用している。これはこの関数の入力であるらしいことは意識する。
（入力と出力が何であるかは常に意識すべき)

(B)

    r = prev[pos];
    s = next[pos];
    next[r] = s;
    prev[s] = r;

これはつまり

    next[r] = next[pos];
    prev[s] = prev[pos];

である。ただし、r と s はそれぞれ右辺値であることから

    next[prev[pos]] = next[pos];
    prev[next[pos]] = prev[pos];

である。なんとなくわかりそうな気がする。日本語に訳すと
    pos の prev の next は、pos の next である。
    pos の next の prev は、pos の prev である。
ということを書いている。図示してみる。


               prev<--+
                ^     next
                |     |
               pos    |
                |     |
                |     |
                v     prev
              next<---+

つまりは、双方向リンクリストで pos を中心に環状にリンクを作っている。
なんとなくわかったので、次に進む

    (C)
    r = parent[pos];
    parent[pos] = NIL;

pos の親を取得し、pos の親を NIL で上書きしている。
pos の親を「取り出している」と読めばよいのか？

(D)

    if (r >= DICSIZ || --childcount[r] > 1)
        return;

例外条件であろう。無視する。

(E)

    t = position[r];

r つまり、pos の親の position を取得している。変数名から pos の親のマッ
チ位置ではなかろうか？

(F)

    if (t >= pos)
        t -= DICSIZ;

例外条件であろうか？t つまり、posの親の position が pos より大きい
場合これは text バッファにおいて、posより右側の位置を t が指している
ことを示しているのだろう。このような場合があるのかどうかはわからないが
やはり例外条件である。無視する。

(G)

    s = child(r, text[t + level[r]]);

r つまり、pos の親と text[t + level[r]] つまり、pos の親の位置 t +　level[r]
を引数に child() 関数を呼んでいる。わかりそうなわからなさそうな・・・
次に進む

(H)

    t = prev[s];
    u = next[s];
    next[t] = u;
    prev[u] = t;

これは前に出てきたのと同じである。つまり、

    next[prev[s]] = next[s];
    prev[next[s]] = prev[s];

で、child()の戻り値についてリンクトリストを構築している。

(I)
    t = prev[r];
    next[t] = s;
    prev[s] = t;

r つまり、pos の親の prev について

    next[prev[parent[pos]]] = child()
    prev[child()] = prev[parent[pos]]

としている。親の前の次と子を、子の前を親の前と繋げている。

(J) (I) と同様である。
    t = next[r];
    prev[t] = s;
    next[s] = t;

(K)
    parent[s] = parent[r];
    parent[r] = NIL;
    next[r] = avail;
    avail = r;

parent[r] つまり、posの親の親とparent[child()]
を繋げている。

なんだかわかりそうなわからなさそうな・・・まだ情報が足りない。

キモとしては、next[], prev[], parent[] を理解すれば、データ構造が見えて
くるであろうことから、この辺りの操作をしている小さめの関数を探してみる
ことにする。

ざっと見て、child(), makechild(), split() が見つかる。これらは
ほとんど、insert_node() で呼ばれている。

get_next_match()
  delete_node()
    child()
  insert_node()
    child()
    split()
      makechild()
    makechild()

といったコールグラフとなっている。insert_node()が複雑であることから
やはり、これらの小さな関数群をまず調べるべきであろう。

ボトムアップ的にまずは、makechild() から

static void
makechild(node q, uchar c, node r)
        /* Let r be q's child for character c. */
{
    node h, t;

    h = HASH(q, c);
    t = next[h];
    next[h] = r;
    next[r] = t;
    prev[t] = r;
    prev[r] = h;
    parent[r] = q;
    childcount[q]++;
}

コメントから q の子を r につなげる処理らしい。

まず、q と文字 c からハッシュ値を求める。

    h = HASH(q, c);

そのハッシュ値の next を取得する

    t = next[h];

そして以下でリストに挿入している

    next[h] = r;
    next[r] = t;

つまり、

    h.next --> t

だったところに

    h.next --> r
               r.next --> t
と r を挿入している。


prev も同様である。

    prev[t] = r;
    prev[r] = h;

以下のようなイメージとなる。

    h <--- r.prev
           r <----- t.prev


r がちゃんと挿入されていることがわかる。
さらに、

    parent[r] = q;

r の parent として、q を設定している。
next[], prev[] が q と c のHASH値をさしているのに対し、
parent[] は、q そのものを指しているらしい。

    childcount[q]++;

q の子を繋げたので、q の子の数を足しているらしい。

次に child() を見てみる

static node
child(node q, uchar c)
        /* q's child for character c (NIL if not found) */
{
    node r;

    r = next[HASH(q, c)];
    parent[NIL] = q;            /* sentinel */
    while (parent[r] != q)
        r = next[r];
    return r;
}

q の子を返すらしい。

親は、直接 parent[] で取得できるが、子を取得するには、
リンクをたどる必要があることを示すようだ。

q の next を取得し、parent[] が q である r を探している。見つからなけれ
ば sentinel として設定してある NIL を返すようだ。

ここまでで言えることは、

・q と c のHASH値により、next[], prev[] が指す先は q の子の候補である。

というところか。

では、split()を見てみる

void
split(node old)
{
    node new, t;

    new = avail;
    avail = next[new];
    childcount[new] = 0;

    t = prev[old];
    prev[new] = t;

    next[t] = new;
    t = next[old];

    next[new] = t;
    prev[t] = new;

    parent[new] = parent[old];
    level[new] = matchlen;
    position[new] = pos;
    makechild(new, text[matchpos + matchlen], old);
    makechild(new, text[pos + matchlen], pos);
}

ここで、ようやく元々の処理目的であるマッチ位置、マッチ長を指す変数が
現れている。

・new に avail を退避し
・avail を新たに next[new] に設定
・new の childcount は 0

  どうやら avail は空きの位置を示しているらしく、新たな node の割り当て
  は、
     new = avail;
  で行い、
     avail = next[new]
  で次の空きをavailにセットしているようだ。avail, next[avail], next[next[avail]] は
  空き領域のリストとなるらしい。そういえば、初期化の処理で

        avail = 1;
        for (i = 1; i < DICSIZ - 1; i++)
            next[i] = i + 1;
        next[DICSIZ - 1] = NIL;

  というのがあったが、next の領域(下図)のうち、左、1/3 は、この空きリス
  トをさすらしい（そして、そのリンクは、next[DICSIZ-1]でNILとなる。
  なお、next[0] は使われておらず、next[1] -> 2 から始まるらしい。

-------------------------------------------------------------------------------------------

                             DICSIZ                DICSIZ*2             max_hash_val + 1
                            /                     /                          /
     +---------------------+---------------------+---------------------+----+
next | 234...           NIL|                     | NIL                 |    |
     +---------------------+---------------------+---------------------+----+

-------------------------------------------------------------------------------------------

・old の prev は、new の prev に設定(あわせて next も再設定)
・new の parent を old の parent に

これで、old は切り離された、

・newの level に matchlen を設定
・newの position に pos を設定
・new の子として old および pos を設定

注目すべきは、最後の makechild() 2連発である。
最初の makechild() により、matchpos + matchlen の文字を old として、
子に連結し、次の makechild() により、新たな pos + matchlen を
pos として、子に連結している。

ここで、matchpos, matchlen は前回のマッチを、pos, matchlen は
今回のマッチを指し、new の子の浅い方がより最近のマッチを指すことを
示すようだ。

ここまでで、どうやらおおよその構造の使い方はつかめて来たが、まだまだよ
くわからない。結局、 insert_node() を読み解くまでは全貌はつかめないよう
だ。

insert_node() を読み進めることにする。例によって、PERCOLATE は未定義として
見ることにする。

static void
insert_node(void)
{
    node q, r, j, t;
    uchar c, *t1, *t2;

    (A)

    if (matchlen >= 4) {
        matchlen--;
        r = (matchpos + 1) | DICSIZ;
        while ((q = parent[r]) == NIL)
            r = next[r];
        while (level[q] >= matchlen) {
            r = q;
            q = parent[q];
        }

        t = q;
        while (t < DICSIZ) {
            position[t] = pos;
            t = parent[t];
        }

    }
    (B)
    else {
        q = text[pos] + DICSIZ;
        c = text[pos + 1];
        if ((r = child(q, c)) == NIL) {
            makechild(q, c, pos);
            matchlen = 1;
            return;
        }
        matchlen = 2;
    }

    for (;;) {
    (C)
        if (r >= DICSIZ) {
            j = MAXMATCH;
            matchpos = r;
        }
    (D)
        else {
            j = level[r];
            matchpos = position[r] & ~PERC_FLAG;
        }
    (E)
        if (matchpos >= pos)
            matchpos -= DICSIZ;
    (F)
        t1 = &text[pos + matchlen];
        t2 = &text[matchpos + matchlen];
    (G)
        while (matchlen < j) {
            if (*t1 != *t2) {
                split(r);
                return;
            }
            matchlen++;
            t1++;
            t2++;
        }
    (H)
        if (matchlen >= MAXMATCH)
            break;
    (I)
        position[r] = pos;
    (J)
        q = r;
        if ((r = child(q, *t1)) == NIL) {
            makechild(q, *t1, pos);
            return;
        }
    (K)
        matchlen++;
    }
    (L)
    t = prev[r];
    prev[pos] = t;
    next[t] = pos;
    (M)
    t = next[r];
    next[pos] = t;
    prev[t] = pos;

    (N)
    parent[pos] = q;
    parent[r] = NIL;
    next[r] = pos;              /* special use of next[] */
}


最初に(A) matchlen >= 4 の場合を扱っている一旦無視することにする。

(B) matchlen < 4 の場合である。

        q = text[pos] + DICSIZ;
        c = text[pos + 1];

ここで、pos の位置の文字と pos + 1 の位置の文字を取得している。
pos には DICSIZ を足しているがそのことは一旦無視する。

        if ((r = child(q, c)) == NIL) {
            makechild(q, c, pos);
            matchlen = 1;
            return;
        }

1文字目の q と 2文字目の c を使って child() を呼び出している。つまり、
q の次に c が続く文字を木から探しているようだ。見つからない場合(NIL)は、
makechild() により、この2文字を木に登録し、matchlen = 1 としてこの関数
を抜けている。matchlen は実際のマッチ長が 1 の場合は、見つからなかった
場合を指しているらしい。

        matchlen = 2;

見つかった場合は、最低 2 文字はマッチしているということから
matchlen を 2 に設定して次の処理に進む。

    for (;;) {
    (C)
        if (r >= DICSIZ) {
            j = MAXMATCH;
            matchpos = r;
        }

r つまり、q の子が DICSIZ以上であれば、j を MAXMATCHに matchpos を r に
設定している。child() の戻り値 r は pos を示すようだ。

    (D)
        else {
            j = level[r];
            matchpos = position[r] & ~PERC_FLAG;
        }

DICSIZ より小さい場合は、j を level[r] に設定し、
matchpos を position[r] の位置にしている。position[r] も位置を示すらしい。

    (E)
        if (matchpos >= pos)
            matchpos -= DICSIZ;

matchpos が pos 以上を指す場合は、matchpos から DICSIZ を引いている。
スライド前の位置を差す場合を想定しているのか？

    (F)
        t1 = &text[pos + matchlen];
        t2 = &text[matchpos + matchlen];

t1 が現在の文字（の末尾）、t2がマッチ文字（の末尾）を指す。

    (G)
        while (matchlen < j) {
            if (*t1 != *t2) {
                split(r);
                return;
            }
            matchlen++;
            t1++;
            t2++;
        }

matchlen が j （最大マッチ長）となるまで、*t1 と *t2 を比較し、
一致する間先に進めている(matchlen++)そして、一致しない部分を
見つけたときに、split(r) により、木を分割している。
以前、split(r) を見たときに詳細は不明だが、新しいマッチを
木に登録する処理のように見えた。なんとなく理解できる。

    (H)
        if (matchlen >= MAXMATCH)
            break;

matchlen == j となったとき、matchlen が MAXMATCH より大きければ
break して for() ループを抜ける。

    (I)
        position[r] = pos;

matchlen が MAXMATCH に達しない間は、新しい pos を position[r] に
登録する。

    (J)
        q = r;
        if ((r = child(q, *t1)) == NIL) {
            makechild(q, *t1, pos);
            return;
        }

q を r にし、q と t1 について木を探索する
見つからなければ、新たな q, t1, pos について makechild() して
木に登録して、終了。

    (K)
        matchlen++;
    }

みつかるようなら matchlen を伸ばして、より長いマッチがあるか探索する。

    (L)
    t = prev[r];
    prev[pos] = t;
    next[t] = pos;
    (M)
    t = next[r];
    next[pos] = t;
    prev[t] = pos;

(L) 以降は for() を抜けた後の処理である。つまり、matchlen が MAXMATCH
以上となった場合。このとき、木を更新している。
r を取り除き、pos とすり替えている。

    (N)
    parent[pos] = q;
    parent[r] = NIL;
    next[r] = pos;              /* special use of next[] */

pos の親を q とし、r の親をNILに、r の next は pos としているが、
先ほど木から切り離していることおよび、コメントから木とは関係ない
用途に利用しているらしい。

nextやprev、parentに対して似たような処理が何度か現れていた
これを関数に切り出せるか考えてみる

。。。。

ここまで読み進めてもはっきり言ってよくわからない
なぜかというとデータ構造がまだよくわからないからである

そこで今度は各変数を中心に処理を追うことにする

なお現時点でわかった情報を変数の一覧に書き込んでおく

(1) 以下は本処理の入出力となる
text・・・読み込んだテキストのバッファ兼辞書　
remainder・・・読み込んでいるデータのバッファ上の残りサイズ
pos・・・現在読み込んでいる位置
matchpos・・・pos位置の文字とマッチした辞書上の位置
matchlen・・・pos位置の文字とマッチした辞書上のマッチ長

(2) 以下により木を現している。ざっと処理をみてトライ木なのではないかと予想
parent
prev
next

(3) 以下は上の木に格納されている補足情報らしい
level・・・マッチ長
position・・・文字に対する位置

(4) 以下は木に関するその他の情報
childcount・・・子の個数
avail・・・nextの空きを指すリストのトップ

ここで、不明確なのは(2)なので、この構造について追求してみる。

まず、型 next, prev, parent (ついでに、position) はいずれも node 型（の配列）である。
その添え字はというと、next を中心に利用している箇所を上から順に探してみると

child(node q, uchar c)
        /* q's child for character c (NIL if not found) */
{
    node r;

    r = next[HASH(q, c)];
    parent[NIL] = q;            /* sentinel */
    while (parent[r] != q)
        r = next[r];
    return r;
}

next の添え字は、HASH(q, c) である。その後の
parent[r], next[r] の記述を見るとどうやら添え字も node である。

node とは何を表すのかが重要である。

insert_node() の冒頭

        q = text[pos] + DICSIZ;
        c = text[pos + 1];
        if ((r = child(q, c)) == NIL) {
            makechild(q, c, pos);
            match->len = 1;
            return;
        }
        match->len = 2;

child() の第一引数は、pos 位置の文字 text[pos] に DICSIZ を足している。
第二引数は、pos の次の位置の文字である。

child() は、next[HASH(第一引数, 第二引数)] を実行するのであった。
ここで、HASH関数がどうなっているか見てみると

#define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)

つまり、
    p
  + ((c) << (DICBIT - 9))
  + DICSIZ * 2

である。HASH()の値はnext[]の添え字であり、常に DICSIZ * 2 以上である(c
はunsigned charなので、<< により、負になることはない)。
したがって、下図 *1 の部分の範囲がHASH()の値である。

さらに言うと、HASH(p, c) の p は、text[pos] + DICSIZ なので、
（この部分に関して言えば）、*2 の部分を返すことになる。

-------------------------------------------------------------------------------------------

                             DICSIZ                DICSIZ*2             max_hash_val + 1
                            /                     /                          /
     +---------------------+---------------------+---------------------+----+
next | 234...           NIL|                     | NIL                 |    |
     +---------------------+---------------------+---------------------+----+

                                                 |----------- *1 -----------|
                                                                       |-*2-|

-------------------------------------------------------------------------------------------

ざっと、HASH() を使用している箇所を探してみると、他に makechild() がある
これも、makechild()の第一、第二引数がそのままHASH()の引数となる。
では、child(), makechild() を使用している箇所を探すと

split() で、使用する new (avail で空きリストが割り当てられる箇所)がmakechild()
の第一引数となる場合がある、*1 の範囲がHASH()の戻りのようだ。

HASH() の ((c) << (DICBIT - 9)) の部分を考えてみる c は、text[] の値
（つまり、文字）を示すので、c の値は、0 〜 255 である。そうすると
DICBIT は、とりあえず13(-lh5)であるからビット列であらわすと


            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
           | 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                                               |-----------|
                                                (DICBIT-9)

と11ビット目から4ビット目までを使用した値の範囲となる。
ここでは、node 型(実体はunsigned short)の範囲を想定している。
なお、short が16bitであることも前提となっているように思う。

なお、2 * DICSIZ は、(DICSIZ は、1 << DICBITであるので) 以下である。

            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
           | 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

p はというと、今のところ 1 から 255 + DICSIZ の範囲なので、

            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
           | 0| 0| 1| 0| 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

これらを足すということは、

            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
p          | 0| 0| 1| 0| 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1|
c<<4       | 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| 0| 0| 0| 0|
2*DICSIZ   | 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
max          0  1  1  1  0  0  0  0  1  1  1  0  1  1  1  1

最大でも、max の値にしかならない、これは、next の領域サイズに使われている

#define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)

と照らし合わせると


MAX_HASH_VAL
            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
           | 0| 1| 1| 1| 0| 0| 0| 0| 1| 1| 1| 0| 1| 1| 1| 1|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
              `-----'  `-----------------------------------'
                /                       \
           3 * DICSIZ                    (DICSIZ / 512 + 1) * UCHAR_MAX{255}

DICSIZ は、2^13、512 は、2^9 であるから、DICSIZ / 512 は、2^4 である)

見事一致している。なにか納得いかない同じ値を示すのに、どうして違う計算式を
使うのだろう？もう一度、HASH()とMAX_HASH_VALを列挙してみよう。

#define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
#define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)

HASH() の式の最大値を考えると
p = DICSIZ + UCHAR_MAX
c = UCHAR_MAX
であるから

#define HASH(p, c) ((DICSIZ+UCHAR_MAX) + ((UCHAR_MAX) << (DICBIT - 9)) + DICSIZ * 2)

DICSIZを切り出すと

#define HASH(p, c) (3 * DICSIZ + UCHAR_MAX + ((UCHAR_MAX) << (DICBIT - 9)))

<< をべき乗(^ はここでは、べき乗)であらわすと(x << n)は、x * 2^(n)であるから

#define HASH(p, c) (3 * DICSIZ + UCHAR_MAX + ((UCHAR_MAX)* 2^(DICBIT - 9)))

UCHAR_MAX を切り出すと

#define HASH(p, c) (3 * DICSIZ + UCHAR_MAX * (1 + 2^(DICBIT - 9)))

x^(a-b) は、x^a / x^b であるから

#define HASH(p, c) (3 * DICSIZ + UCHAR_MAX * (1 + 2^DICBIT / 2^9))

これで、MAX_HASH_VALと同じになった。やはり、MAX_HASH_VALは基のHASH()関数の計算式を保存して、

#define MAX_HASH_VAL ((DICSIZ+UCHAR_MAX) + ((UCHAR_MAX) << (DICBIT - 9)) + DICSIZ * 2)

とするか、むしろ

#define MAX_HASH_VAL HASH(DICSIZ + UCHAR_MAX, UCHAR_MAX)

とした方がわかりやすい。どうせ定数の計算式だからコンパイラが計算してくれるのである。

横道にそれた、HASH()関数についてもう一度再考する。


            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
p          | 0| 0| 1| 0| 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1|
c<<4       | 0| 0| 0| 0| 1| 1| 1| 1| 1| 1| 1| 1| 0| 0| 0| 0|
2*DICSIZ   | 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

2*DICSIZ は、値の範囲をnext[]の領域下図（再掲）の*1の部分に押し上げるためのものである。

-------------------------------------------------------------------------------------------

                             DICSIZ                DICSIZ*2             max_hash_val + 1
                            /                     /                          /
     +---------------------+---------------------+---------------------+----+
next | 234...           NIL|                     | NIL                 |    |
     +---------------------+---------------------+---------------------+----+

                                                 |----------- *1 -----------|
                                                                       |-*2-|

-------------------------------------------------------------------------------------------

では、2*DICSIZ を除いて、13ビット目をx その他をyであらわすと

            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
p          | 0| 0| x| 0| 0| 0| 0| 0| y| y| y| y| y| y| y| y|
c<<4       | 0| 0| 0| 0| y| y| y| y| y| y| y| y| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                   x  y  y  y  y  y  y  y  y  y  y  y  y  y

13ビット目が立っている場合は、*2 の範囲を表しており、*2 の範囲はほぼDICSIZと同じであることが
わかる。(正確にはMAX_HASH_VAL+1であるから、yyyyyyyyyyyyy は、1000011110000 半分よりちょっと
多いサイズである。

そして、13ビット目が立っていない場合は、*1 の領域は、やはりyyyyyyyyyyyyyであるつまり、
DICSIZの領域をすべて使っているわけではないのである図を少し訂正しよう。

-------------------------------------------------------------------------------------------

                             DICSIZ                DICSIZ*2              DICSIZ*3
                            /                     /                     /         max_hash_val + 1
     +---------------------+---------------------+---------------------+----------+
next | 234...           NIL|                     |       NIL           |    NIL   |
     +---------------------+---------------------+---------------------+----------+

                                                 |--- *1 ---|          |--- *2 ---|


-------------------------------------------------------------------------------------------

*1 と *2 は同じである。max_hash_val + 1 - DICSIZ*3 は、*2 + 1 なので、
+ 1 の分だけ、図の通りではない。

*1 と *2 は、DICSIZ/2 より少し大きい

もう少し、HASH()について考える。13 bit目をとりあえず無視して
p ・・・text[]の１文字目
c ・・・text[]の２文字目
であるが、c<<4 としている理由は、


            15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
p          | 0| 0| x| 0| 0| 0| 0| 0| y| y| y| y| y| y| y| y|
c<<4       | 0| 0| 0| 0| y| y| y| y| y| y| y| y| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                   x  y  y  y  y  y  y  y  y  y  y  y  y  y


p, c の2文字(2*8bit)の情報を、12bitに写像(桁上がりも考慮)しており、p の
上位4bitとcの下位4bit を使っている。これを行う理由ははっきりとはまだわ
からないが、HASH()が指す node は、引数の組み合わせにより同じ値を持つ場
合があることがわかる。

c<<4 はc<<(DICBIT-9)であるが、DICBITが大きくなるとbitをずらす範囲が広がる。
c<<(DICBIT-9) は、2<<DICBIT つまり13bit目を上書きしない程度に2文字目の情報を
ずらしているためであるから、DICBIT-9の意味は、DICBIT-8-1(8 は1文字のbit数で、
DICBITから8bit+桁上がりの1bit引いて、何bit分左シフト可能かを表しているようだ。

必然的に、辞書サイズがたとえば、DICBIT{16} の場合(これは-lh7- の場合)、

DICSIZ は、2^16 であり、


            18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
p          | 0| 0| x| 0| 0| 0| 0| 0| 0| 0| 0| y| y| y| y| y| y| y| y|
c<<7       | 0| 0| 0| 0| y| y| y| y| y| y| y| y| 0| 0| 0| 0| 0| 0| 0|
           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                   x  y  y  y  y  y  y  y  y  y  y  y  y  y  y  y  y

1文字目と2文字目は1bitのみしか重ならないため、同じHASH値が衝突する確率
は減る。ただし、HASHの戻り値の型は 18bit (0〜17bit目まで)で、 16bit整数
では収まらないので32bit整数にする必要がある。

HASH()の戻り値については、next[]の添え字でしか使っていないので、まあ今時の
コンピュータなら大丈夫である。

node 型はというと、next[] が格納する値は、next[]の添え字である。

つまり、next[] は、常に以下の図の領域のいずれかの位置(NILはリンク先がな
いの意味)を指している。ということは、node型は MAX_HASH_VAL の値の範囲が
必要であり、これは 32bit 整数なのである。

下図で一つ一つの要素は32bitあるが、使うのは18bitだけとはちょっとさすがに
もったいない。

どのくらいもったいないかというと、DICBIT{16}のとき(辞書サイズ64K)の
MAX_HASH_VALは、229503 であり、その一要素が32bit とすると約896Kである。
next だけで、1M近い領域をmalloc()することになる。

しかし、HASH値は前にも述べたとおり、下図の *1 *2 の範囲しか使用しない。

-------------------------------------------------------------------------------------------
                             DICSIZ                DICSIZ*2              DICSIZ*3
                            /                     /                     /         max_hash_val + 1
     +---------------------+---------------------+---------------------+----------+
next | 234...           NIL|                     |       NIL           |    NIL   |
     +---------------------+---------------------+---------------------+----------+
                                                 |--- *1 ---|          |--- *2 ---|


-------------------------------------------------------------------------------------------

-lh7- 対応は考える必要がありそうだ。