the autoconfig-version of lha

maintained as seperate project

Suggested by:	Shigekazu Kimura

7 files changed, 5064 insertions, 0 deletions

diff --git a/archivers/lha-ac/Makefile b/archivers/lha-ac/Makefile
new file mode 100644
index 000000000000..6974631eb359
--- /dev/null
+++ b/archivers/lha-ac/Makefile
@@ -0,0 +1,42 @@
+# New ports collection makefile for:    lha-autoconf
+# Date created:         24 Sep 2004
+# Whom:                 dirk.meyer@dinoex.sub.org
+#
+# $FreeBSD$
+#
+
+PORTNAME=	lha
+PORTVERSION=	1.14i
+PORTREVISION=	7
+CATEGORIES=	archivers
+MASTER_SITES=	${MASTER_SITE_SOURCEFORGE_JP} \
+		http://qgpop.dl.sourceforge.jp/%SUBDIR%/ \
+		http://osdn.dl.sourceforge.jp/%SUBDIR%/
+MASTER_SITE_SUBDIR=	lha/6052
+PKGNAMESUFFIX=	-ac${PKGNAMESUFFIX2}
+DISTNAME=	${PORTNAME}-${PORTVERSION}-ac20030921
+
+MAINTAINER=	dinoex@FreeBSD.org
+COMMENT=	Archive files using LZSS and Huffman compression (.lzh files)
+
+MAN1=		lha.1
+MANLANG=	ja
+PLIST_FILES=	bin/lha
+PLIST_DIRS=	man/ja/man1
+GNU_CONFIGURE=	yes
+
+RESTRICTED=	"no permission to redistribute"
+NO_PACKAGE=	${RESTRICTED}
+
+.if !defined(WITHOUT_NLS)
+CONFIGURE_ARGGS+=	--disable-multibyte-filename
+.else
+CONFIGURE_ARGGS+=	--enable-multibyte-filename=auto
+.endif
+
+do-install:
+	-${MKDIR} ${MANPREFIX}/man/ja/man1
+	${INSTALL_PROGRAM} ${WRKSRC}/src/lha ${PREFIX}/bin/lha
+	${INSTALL_MAN} ${WRKSRC}/man/lha.n ${MANPREFIX}/man/ja/man1/lha.1
+
+.include <bsd.port.mk>
diff --git a/archivers/lha-ac/distinfo b/archivers/lha-ac/distinfo
new file mode 100644
index 000000000000..ade3b41489b8
--- /dev/null
+++ b/archivers/lha-ac/distinfo
@@ -0,0 +1,3 @@
+MD5 (lha-1.14i-ac20030921.tar.gz) = 7cbf0599683547b64f44076def988c55
+SHA256 (lha-1.14i-ac20030921.tar.gz) = c81ba351411dd935ec6be0e051dc1558a41d68e0180ae2ae90f06c09c43ed9e1
+SIZE (lha-1.14i-ac20030921.tar.gz) = 216238
diff --git a/archivers/lha-ac/files/patch-2004-09-23 b/archivers/lha-ac/files/patch-2004-09-23
new file mode 100644
index 000000000000..ab7ff611b554
--- /dev/null
+++ b/archivers/lha-ac/files/patch-2004-09-23
@@ -0,0 +1,4930 @@
+diff -urN lha-1.14i-ac20030921/00readme.autoconf 00readme.autoconf
+--- lha-1.14i-ac20030921/00readme.autoconf	Sun Aug 17 17:16:46 2003
++++ 00readme.autoconf	Fri Sep 17 21:20:57 2004
+@@ -1,4 +1,4 @@
+-# $Id: 00readme.autoconf,v 1.24 2003/08/17 15:15:12 arai Exp $
++# $Id: 00readme.autoconf,v 1.25 2004/09/17 19:20:57 arai Exp $
+ # -*- Mode: text ; Coding: euc-japan -*-
+ 
+ autoconfiscated for LHa for UNIX version 1.14i
+@@ -330,6 +330,28 @@
+ 
+   なお、level 0, 1, 2 ヘッダの仕様上 4G 未満のファイルしか書庫に格納で
+   きません。
++
++・壊れたアーカイブの展開 (--extract-broken-archive)
++
++  LHa for UNIX (autoconf版)は、バージョン 1.14i-ac20030713 (slide.c
++  revision 1.20) より壊れたアーカイブを作成してしまう致命的なバグがあ
++  りました。(このようなアーカイブが作成される現象に遭遇することはほと
++  んどないかも知れません。ただ、バグのある LHa for UNIX では正常に展開
++  できてしまうので、壊れたアーカイブであることに気が付いてないだけかも
++  しれません)
++
++  この壊れたアーカイブは他の正常な LHA (あるいは現在の LHa for UNIX) 
++  では展開時に CRC エラーが発生してしまいます。
++
++  現在のバージョンでは、
++
++  	lha x --extract-broken-archive broken.lzh
++
++  とオプション --extract-broken-archive を指定することで、このバグによ
++  り作成された壊れたアーカイブを強制的に展開することができます。CRC エ
++  ラーが発生するアーカイブを見付けたときには(そして、それが過去の LHa
++  for UNIX (autoconf版)で作成されたものである場合には)このオプションを
++  試してみてください。
+ 
+ ・再配布について
+ 
+diff -urN lha-1.14i-ac20030921/ChangeLog ChangeLog
+--- lha-1.14i-ac20030921/ChangeLog	Sun Sep 21 16:14:55 2003
++++ ChangeLog	Fri Sep 17 21:25:19 2004
+@@ -1,3 +1,49 @@
++2004-09-18  Koji Arai  <jca02266@nifty.ne.jp>
++
++	* configure.ac: updated version.
++
++	* 00readme.autoconf: added a description about
++	`--extract-broken-archive' option.
++
++	* src/lharc.c (init_variable, parse_option): added an option
++	`--extract-broken-archive' to extract broken archive.
++
++	* src/lha.h (extract_broken_archive): ditto.
++
++	* src/slide.c (encode, decode): fixed a *FATAL* bug which make a
++	broken archive.
++
++2004-05-08  Koji Arai  <jca02266@nifty.ne.jp>
++
++	* configure.ac: updated version.
++
++	* src/prototypes.h: updated.
++
++	* src/lhext.c (extract_one, is_directory_traversal): applied a
++	security patch (CAN-2004-0235: directory traversal problems)
++
++	* src/lharc.c (print_usage): updated.
++
++2003-12-18  Koji Arai  <jca02266@nifty.ne.jp>
++
++	* src/header.c (wintime_to_unix_stamp): no use 64bit constant to
++	avoid the warning `integer constant is too large for "long" type'
++	on GCC. however, for portability, no use the unsigned long long
++	suffix "ULL".
++
++2003-12-13  Koji Arai  <jca02266@nifty.ne.jp>
++
++	* configure.ac: updated version.
++
++	* src/lhext.c (extract_one, cmd_extract): preserve directory
++	timestamp. Thanks Akihiro Iriyama.
++
++	* src/lhext.c (add_dirinfo, adjust_dirinfo): newly added.
++
++2003-09-28  Koji Arai  <jca02266@nifty.ne.jp>
++
++	* Makefile.am (SUBDIRS): reordered to avoid useless re-compilation.
++
+ 2003-09-21  Koji Arai  <jca02266@nifty.ne.jp>
+ 
+ 	* released.
+diff -urN lha-1.14i-ac20030921/Hackinf_of_LHa Hackinf_of_LHa
+--- lha-1.14i-ac20030921/Hackinf_of_LHa	Thu Jan  1 01:00:00 1970
++++ Hackinf_of_LHa	Mon Feb 24 00:23:56 2003
+@@ -0,0 +1,4494 @@
++$Id: Hackinf_of_LHa,v 1.14 2003/02/23 23:23:56 arai Exp $
++
++               The Hacking of LHa for UNIX (2nd draft)
++             -------------------------------------------
++
++                                Koji Arai <mailto:jca02266@nifty.ne.jp>
++
++本書は、LHa for UNIX 1.14i のソースを解読し、その圧縮アルゴリズムの実
++装を確認するためのものだ。この成果は別の形でまとめなおされ資料になるか
++もしれないし、このままの形で保管されるかもしれないし、新たにソースを書
++き起こす元になるかもしれない。とにかく、暇な正月休みを潰すためにやって
++みただけのものだ。(休みが明けるとまた忙しくなるので、これ以上まったく
++何もしないかもしれない)
++
++本書は、まだ未完成である。にもかかわらず公開するのはこれ以上続かないか
++もしれないからである(気が向いたらまた続きを書くだろう。あるいは応援の
++お手紙がくればやる気が出るかもしれない)。
++
++本書はフリーである。複製、改変、再配布は自由であるということだ。ただし
++本書により生じたあらゆる損害、不利益に対しては一切の保証はない。本書に
++は嘘があるかもしれない。それに対して嘘を教えられたと著者を避難をしない
++で頂きたい。しかし間違いの指摘は構わない(ぜひお願いしたい)、著者は圧縮
++処理に関しては無知である。用語の使い方等は適切でないかもしれないのでこ
++の方面でも御指導頂ければ幸いである。
++
++===============================================================================
++o 表記について
++
++* 関数は、その定義ソース file.c と関数名 func() を示すのに
++     file.c:func()
++  という記述を使う
++
++* 配列の添字は、Python言語のスライス演算子の記法に準じた
++
++    a[m:n] は、m <= i < m+n の範囲の a[i] を意味する。
++
++* 値の範囲は、Ruby言語の範囲演算子の記法に準じた。これを配列の
++  添字に使用する場合もある。
++
++    m <= i <= n   -> i = m..n
++    m <= i < n    -> i = m...n
++
++    a[m..n] は、m <= i <= n の範囲の a[i] を意味する。
++
++* m の n 乗 は、m^n で表す。^ は、排他的論理和としても利用されるが
++  文脈から判断してもらう。
++
++* v{n} は、変数 v の値が n であることを表す。n は、サンプルの値であったり
++  定数の値であったりする。
++
++  v=n は代入文
++
++  配列の内容は、
++    ary[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }
++  のように書く
++
++o 用語について
++
++* 符号
++        符号化、符号語、圧縮文
++
++        符号語は、1つの文字を符号化した結果。圧縮文は符号語の並び。
++
++* 復号
++        復号化、復号語、復号文
++
++        復号語は、圧縮文から1つの文字を復号化した結果。復号文は復号語の並び。
++
++* 平文
++        圧縮前の文を示す。対して復号文は、復号した後の文を意味する。
++
++* slide 辞書法
++
++* Huffman 法
++   動的 Huffman 法、静的 Huffman 法
++
++===============================================================================
++
++
++slide 辞書法 (slide.c)
++----------------------
++
++まず、構造について考える。
++
++slide辞書法は、encoding にさまざまな工夫が凝らされるのでとても複雑だが、
++普通 decoding は単純である。decoding を解析することでどのような圧縮文
++を作っているのかを調べてみる。
++
++decoding を行う処理は、slide.c の decode() である。この処理を見てみる
++と思った通り簡単に解読できた(以下)
++
++  1. huffman coding により復号した文字を環状バッファ dtext に書き込む
++     通常の文字 c は、c < 256 で表現されている(つまりそのまま)
++
++  2. 通常の文字でないものが現れたら、それは長さである。長さ len は、
++     len > 255 で表現されている。len から 0xfd(253) を引いた値が
++     実際の長さを表す(-lzs- method の場合は、0xfe(254)を引く)
++    「長さ」が、現れたらその直後には「位置」が書かれているのでそれを
++     読む。こうして、長さと位置のペア<len, pt>を得る
++
++     dtext から pt+1 バイト前の len バイトを読み、dtext に追加で書き込む
++
++   3. dtext が一杯(dicsiz)になったらファイルに書き出す
++
++これの繰り返しである。つまり、slide 辞書法の圧縮文は、文字 c と<len,
++pt> の並びであることがわかる。例えば、文字列 c1 c2 c1 c2 は、以下のよ
++うに表現されているはずである。(本当は、長さが 2 以下では圧縮が起こらな
++いので平文のまま出力する。長さは最低でも 3 は必要)
++
++        +----+----+--------+
++        | c1 | c2 | <2, 1> |
++        +----+----+--------+
++
++では、この構造を作成する圧縮処理について考える。slide 辞書法では、ファ
++イルから読み込んだ文字列 token が、以前に読み込んだ辞書に存在すれば
++<len, pt> のペアを出力し、存在しなければ token をそのまま出力する。読
++み込んだ token は、辞書に追加し、辞書の語が溢れたら古い情報を捨てる。
++
++何も予備知識がない状態で書けば
++
++        while (read_file(&token, tokensiz)) {
++          len = search_dict(dict, token, &pt);
++          if (len == -1) {
++            print_token(token);
++          else
++            print_pair(len, pt);
++          update_dict(dict, token);
++        }
++
++のようになるはず。ここで、tokensiz は token の最大サイズで、最長一致長
++を表す。この値が大きければ大きい程、圧縮効率は良くなるはずで、lha では、
++これは MAXMATCH{256}である。また、dict は辞書でこのサイズは lha の 
++-lh5- メソッドでは、8192 となっている。この辞書も大きければ大きい程良
++いはずだ。その方が一致文字列が見つかりやすい。(ただし、辞書が大きいと
++一致位置を示す情報 <len, pt> の情報量が増えるはずだし、速度も遅くなる
++だろう。後で検証する)
++
++で、実際にソースを見てみると(slide.c:encode())・・・、まったくこのよう
++な構造にはなってないように見える。何やらややこしいことばかりでまったく
++わからない。なぜここまでややこしいのかと泣きたくなってくるが、それは速
++度のためである(本当？)。上記のコードで、search_dict() は、単に dict か
++ら token に一致する位置を検索するだけで良さそう(実際にそれでも良い)だ
++が、これではまったく速度が出ない。このあたりの工夫が slide 辞書法のキ
++モである。
++
++そういうわけで、この部分を読み解くことにする。なお、予備知識として lha 
++では、辞書から token を探すのにハッシュが使われているらしいことを記し
++ておく。
++
++ここでは実際にデバッガで動作させながら解読するのではなく、ソースを読む
++だけで理解できるかを試すことにする。また、本文は某書(謎)のノリをマネて
++いると指摘する方がいるかもしれない・・・がまったくその通りだ。
++
++まず、そのものずばりの encode() (slide.c) を見る。以下がこの関数だが
++処理の要点だけに着目するために不要そうな部分は(現時点で予測で)削った。
++
++unsigned int
++encode()
++{
++    int lastmatchlen;
++    unsigned int lastmatchoffset;
++
++    /* (A) */
++    init_slide();  
++
++    /* (B) */
++    remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
++    encoded_origsize = remainder;
++    matchlen = THRESHOLD - 1;
++
++    pos = dicsiz;
++
++    if (matchlen > remainder) matchlen = remainder;
++
++    /* (C) */
++    hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5) 
++            ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
++
++    /* (D) */
++    insert();
++
++    while (remainder > 0 && ! unpackable) {
++        /* (E) */
++        lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
++        --matchlen;
++
++        /* (F) */    /* (G) */
++        get_next();  match_insert();
++        if (matchlen > remainder) matchlen = remainder;
++
++        /* (H) */
++        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
++            /* (H.1) */
++            encode_set.output(text[pos - 1], 0);
++            count++;
++        } else {
++            /* (H.2) */
++            encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
++               (lastmatchoffset) & (dicsiz-1) );
++            --lastmatchlen;
++
++            while (--lastmatchlen > 0) {
++                get_next();  insert();
++                count++;
++            }
++            get_next();
++            matchlen = THRESHOLD - 1;
++            match_insert();
++            if (matchlen > remainder) matchlen = remainder;
++        }
++    }
++}
++
++まず、この関数から概観を見てみると、ループの前に初期化処理として
++以下が行われている。
++
++(A) init_slide() 初期化する
++(B) ファイルを読み込み text[] に格納する。
++(C) ハッシュ値 hval を計算する。
++(D) insert() する (きっと辞書に token を追加しているのだろう)
++
++そして、ループ処理では以下の処理が行われている
++
++(E) lastmatchlen, lastmatchoffset, matchlen を更新する。
++(F) get_next()  (次の token を読む。たぶん)
++(G) match_insert()  (辞書に追加する。たぶん)
++
++(H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
++
++(H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
++(H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
++
++現時点で、(H.2) の部分はよく解読できなかった。何やら再度 get_next() が
++呼ばれていたりして思った通りの処理フローにはなっていない。だが、ここで
++は焦らず放置することにして、ここまで予想で書いた部分の細部に触れること
++にする(単にここまでの予想が間違っているだけかもしれないのだから、わか
++らない部分を無理にわかるように頑張る必要はなかろう)
++
++関数の細部に触れる前にデータ構造について調べておく。データ構造に対して
++の理解が深まればアルゴリズムの80%は分かったも同然だ(誇張)。slide.c で
++使用されているデータ構造は以下の通りだ。(不要そうだと思うものは除いて
++ある)
++
++static unsigned int *hash;
++static unsigned int *prev;
++unsigned char *too_flag;
++static unsigned int txtsiz;
++static unsigned long dicsiz;
++static unsigned int hval;
++static int matchlen;
++static unsigned int matchpos;
++static unsigned int pos;
++static unsigned int remainder;
++
++too_flag だけ、static がついてないが、他のソースを grep してもこの変数
++を使っている箇所はない、単に static の付け忘れだろう。
++
++これらの変数は、encode() の冒頭 init_slide() で初期化されている・・の
++かと思ったら違った。slide.c:encode_alloc() で行われている。
++
++int
++encode_alloc(method)
++    int method;
++{
++    if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
++        encode_set = encode_define[0];
++        maxmatch = 60;
++        dicbit = 12;   /* 12 Changed N.Watazaki */
++    } else { /* method LH4(12),LH5(13),LH6(15) */
++        encode_set = encode_define[1];
++        maxmatch = MAXMATCH;
++        if (method == LZHUFF7_METHOD_NUM)
++            dicbit = MAX_DICBIT; /* 16 bits */
++        else if (method == LZHUFF6_METHOD_NUM)
++            dicbit = MAX_DICBIT-1;      /* 15 bits */
++        else /* LH5  LH4 is not used */
++            dicbit = MAX_DICBIT - 3;    /* 13 bits */
++    }
++
++    dicsiz = (((unsigned long)1) << dicbit);
++    txtsiz = dicsiz*2+maxmatch;
++
++    if (hash) return method;
++
++    if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
++
++    hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
++    prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
++    text = (unsigned char*)malloc(TXTSIZ);
++    too_flag = (unsigned char*)malloc(HSHSIZ);
++
++    if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
++        exit(207);
++
++    return method;
++}
++
++引数に渡された method (これは、lh1, lh5, lh6, lh7 などを示す)によって、
++初期化される内容が変わる(encode_alloc()前半部分)。このことから各変数の
++用途もわかる。
++
++        method  maxmatch     dicbit
++        ----------------------------
++        -lh1-       60         12
++        -lh5-      256         13
++        -lh6-      256         15
++        -lh7-      256         16
++
++ということらしい。dicbit というのは辞書サイズのbitサイズで、辞書サイズ
++は 2^dicbit で表されている。lh5 が 8KB(2^13)、lh6 が 32KB(2^15)、lh7 
++が 64KB(2^16) の辞書サイズを利用すると言うのは予備知識である。maxmatch 
++というのは、token の最長一致長である。このことも予備知識として詳細には
++触れない。(ところで、本書では当面、lh5, 6, 7 のことしか言及しない)
++
++encode_set, encode_define というのがあるが、method によって、Huffman
++coding の方法を変えていることはちょっと見ればすぐにわかるし、大したこ
++とではない。以降無視する。
++
++encode_alloc() の後半では、他の変数の初期化(バッファの割り当て)が行われる。
++
++    dicsiz = (((unsigned long)1) << dicbit);
++
++dicsiz はそのものずばり辞書サイズである。
++
++    txtsiz = dicsiz*2+maxmatch;
++
++現時点で txtsiz が何なのかはわからない。
++
++    if (hash) return method;
++
++hash はこの直後で割り当てられる。つまり、一度割当を行ったら、
++encode_alloc() は、以降メモリの割当を行わない。ただそれだけだ。
++
++    if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
++
++alloc_buf() は、huf.c で定義された関数。このことから Huffman coding の
++ためのバッファを割り当てているのだろう。ここでは無視。(しかし、207 と
++いうのは何なのだろう？)
++
++    hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
++    prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
++    text = (unsigned char*)malloc(TXTSIZ);
++    too_flag = (unsigned char*)malloc(HSHSIZ);
++
++    if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
++        exit(207);
++
++hash は、ハッシュ用の何か、HSHSIZ は、固定値で 2^15 である。
++
++prev は、DICSIZから辞書だろう。要素の型が char でなく int であることに
++も注目しておく。DICSIZ は dicsiz でも構わないはず。単に「大は小を兼ね
++る」を実践しているだけであろう、TXTSIZ も同様である。おそらく、一度の
++実行で複数の圧縮メソッドを使用した場合、そのメソッド毎に領域を割り当て
++るよりは最大の値をあらかじめ一度だけ割り当てた方が良いと考えたのだろう。
++しかし、ソースを参照するときは繁雑になるので以降、
++   DICSIZ == dicsiz
++   TXTSIZ == txtsiz
++であるとする。これ重要。
++
++text は、現時点では不明
++
++too_flag も不明
++
++っとなる。まだ、良く分からないが、以下の図を書いておこう。後で何度も見
++ることになるだろう。この図はスケールが lh7 の場合を想定しているが。こ
++のことは大したことではないはずだ。また、too_flag と hash のスケールが
++一緒だがこれはサイズ(領域のバイト数)が一緒なのではなく、要素数が一緒で
++あることを示している。ほとんどの場合要素の型の違いというのは処理内容に
++とって重要なことではないはずだ。
++
++----------------------------------------------------------------------------
++
++       0            2^15=32768
++       +-------------+
++  hash |             |
++       +-------------+          dicsiz=2^dicbit
++       +-------------+-------------+                          2*2^dicbit
++  prev |             |             |                           |
++       +-------------+-------------+                           v   txtsiz
++       +-------------+-------------+-------------+-------------+---+
++  text |             |             |             |             |   |
++       +-------------+-------------+-------------+-------------+---+
++                                                               <--->
++                                                                maxmatch{256}
++  too_flag           2^15
++       +-------------+
++       |             |
++       +-------------+
++----------------------------------------------------------------------------
++
++
++先に示した変数の中でまだ初期化には現れていないものがある。列挙すると
++
++static unsigned int hval;
++static int matchlen;
++static unsigned int matchpos;
++static unsigned int pos;
++static unsigned int remainder;
++
++だ、ざっとソースを眺めると slide.c:insert() という関数に
++        hash[hval] = pos;
++というのが現れているから、hval は、hash[] の位置を指し、hash には、pos 
++を格納すると推測される。同様に
++        prev[pos & (dicsiz - 1)] = hash[hval];
++というのも現れているから pos は、prev[] の位置を指し、prev には、
++hash[hval] つまり、pos を格納しているようだ。これは少し謎な処理だが、
++insert() の全貌は短い(というかこれだけ)なので、ちょっと横道にそれて詳
++細に見てみよう。(現在の解析の趣旨は、変数の用途の概要を予想すること)
++
++/* 現在の文字列をチェーンに追加する */
++
++static void insert()
++{
++    prev[pos & (dicsiz - 1)] = hash[hval];
++    hash[hval] = pos;
++}
++
++コメントはまったく意味不明だが、無視して処理内容に着目する。prev[] の
++インデックス pos & (dicsiz - 1) は、dicsiz が 2^n であることからdicsiz 
++はビットマスクであることがわかる。例えば仮に dicsiz が 2^8 だと
++dicsiz - 1 は、
++
++               8 7 6 5 4 3 2 1 0 bit
++      --------------------------
++      dicsiz   1 0 0 0 0 0 0 0 0
++      dicsiz-1   1 1 1 1 1 1 1 1
++
++である。このすべて 1 が立ったビットマスクと pos を & すると、どのよう
++な pos の値に対しても pos & (dicsiz - 1) は、prev[] のインデックスの範
++囲に納まる。もう少し言うと pos が仮にインデックスの最大値+1だった場合、
++pos & (dicsiz - 1) は、0 になる。これにより次の予想が立つ。
++
++  o pos が、prev[] の位置を指すのではなく、pos & (dicsiz - 1) が
++    prev[]の位置を指す。(pos は、このインデックスの範囲を越える可能性がある)
++  o それに反して、prev[] は環状バッファらしいという予想が立てばやはり
++    pos は、prev のインデックスである。
++
++prev が環状バッファであると予想が付けば話が早い。pos & (dicsiz-1) は、
++pos と同義だと解釈可能だからである(prev が環状バッファでなく無限長のバッ
++ファであると想像しよう)そして、pos & (dicsiz-1) を pos に置き換えて、
++再度処理内容に着目すると
++
++    prev[pos] = hash[hval];
++    hash[hval] = pos;
++
++ということから、
++    1. (この関数に来る前に) pos が更新される。(予想)
++    2. prev[pos] に以前の hash[hval] (以前の pos)を格納する
++    3. hash[hval] に新しい pos を書く。
++といった処理であることが予想される。コメントの「チェーン」もなんとなく
++納得できる。新たな事実(まだ予想だが)が分かったので、図に書き記そう。
++
++----------------------------------------------------------------------------
++       0            2^15=32768
++       +-+---+-------+
++  hash | |pos|...    |
++       +-+---+-------+
++         `-hval
++
++              .-----------.
++             v            |
++       +----+-----+--------------------
++  prev |    |pppos|      |ppos|        . . .
++       +----+-----+--------------------
++            `- ppos      `-pos
++
++  * hash の取り得る値は pos その位置は hval
++  * ppos は以前の pos を示す。pppos はさらに以前の pos を指す。
++  * prev は無限長のバッファ(本当は環状バッファ)
++----------------------------------------------------------------------------
++
++まだ、解析できてない変数が残っている。
++
++static int matchlen;
++static unsigned int matchpos;
++static unsigned int remainder;
++
++しかしこれらはどうにもパッと見ではわからない。処理内容を追いかけないと
++だめそうだ。仕方ないので変数名で予想しよう。(幸い前の変数名と違って予
++想しやすい)以下
++
++----------------------------------------------------------------------------
++ * matchlen     一致した文字列長
++ * matchpos     一致した辞書上の位置
++ * remainder    token の残りサイズ
++----------------------------------------------------------------------------
++
++はたして、予想はあっているのか、今はまだ分からない。
++
++slide.c を見る限りデータ構造は網羅できた。結局分かったのか分からないの
++か良く分からないが少しずつでも前進はしているはずだ。ここで、再度 
++encode() の処理を追いかけよう。今度は細部にも着目する。
++
++前に、encode() のソースには (A) 〜 (H) までの記号を記した。この順番に
++解析を進めよう。
++
++    /* (A) */
++    init_slide();  
++
++まあ、初期化である。内容を見てみると
++
++    for (i = 0; i < HSHSIZ; i++) {
++        hash[i] = NIL;
++        too_flag[i] = 0;
++    }
++
++だけである。NIL というのは、0 であると slide.c で定義されている。普通
++このような初期値は、通常の値が取り得ない値を示している。NIL が 0 なら 
++hash[] に格納される pos は 0 にならない可能性がある。まあ、予想ばかり
++書いても仕方ないので、この関数は終ろう。余談だが、nil は null と同じで。
++「ない」の意味だが、NULL がC言語ではポインタだから。別のマクロ名にした
++のかも知れない。いずれにしてもこの程度はマクロにする必要もなかろうとは
++思うのは、余計なお世話かもしれない。
++
++    /* (B) */
++    remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
++    encoded_origsize = remainder;
++    matchlen = THRESHOLD - 1;
++
++    pos = dicsiz;
++
++    if (matchlen > remainder) matchlen = remainder;
++
++ファイルを読み込み、各変数の初期値を設定している。注目すべきはファイル
++を読み込んだバッファの位置である。fread_crc() は、crcio.c で定義された
++汎用関数で、CRC値を計算したり漢字コード変換をしたりを除けば、fread() 
++と同じである。つまり、ファイルは最初、
++
++  &text[dicsiz] の位置に、txtsiz-dicsiz 分だけ読まれる。
++
++ことを示す。図示しよう。
++
++----------------------------------------------------------------------------
++< 初期状態 >
++                                
++                                dicsiz=2^dicbit               2*2^dicbit
++                                   v                           v   txtsiz
++       +-------------+-------------+-------------+-------------+---+
++  text |             |             |             |             |   |
++       +-------------+-------------+-------------+-------------+---+
++                                   `-pos                       <--->
++                                                                maxmatch{256}
++
++                                   <------ remainder -------------->
++
++                                   |--- この位置に最初の  ---------|
++                                        データが読まれている
++----------------------------------------------------------------------------
++
++ますます、text[] の用途が不明だが、slide 辞書法の典型的な読み込み処理
++のことを考えるとある程度予想がつく(それを先に示した方が良いか？)。まあ、
++ここではフーンっと鼻で納得して済まそう。
++
++fread_crc() は、読み込んだバッファ長を返す。remainder がその値で、既に
++図示してある。encoded_origsize は、ソースを見ると、元のファイルのサイ
++ズを表すためだけの変数のようだ。以降は無視しよう。
++
++ところで、ファイルサイズが小さい場合図の通りにならないっと考えるかも知
++れない。その通りなのだが、例外条件は少ない方がソースは理解しやすい。単
++純な場合だけを考えた方が、あれこれ考えをめぐらす必要がないからだ。なに
++しろ既に動くソースを見ているのだから、細かいことに目をつぶってもエンバ
++グすることはないのである。そういうわけで、当面はこの図が唯一の初期状態
++であると考える。
++
++(B) の部分はもう少し注目すべき箇所がある。
++
++    matchlen = THRESHOLD - 1;
++
++matchlen は、「一致した文字列長」であると予想したが THRESHOLD の値は 3
++(固定値)であるから、matchlen の初期値は 2 だ。いきなり予想がはずれた気
++がする。予想を立て直そう。2 という謎な数値と match*len* について考える
++と、冒頭で <len, pt> のペアの len は 2 であることはないと説明した。無
++意味だからであるが、matchlen の初期値はこの 2 と関連するかもしれない。
++そこで、matchlen の用途を以下のように予想しなおすことにする。以下のよ
++うにメモを更新しよう。THRESHOLD(threshold は閾値の意)も一緒に予想した。
++
++----------------------------------------------------------------------------
++* matchlen      最低限一致しなければならない長さ-1
++* THRESHOLD     最低限一致しなければならない長さ
++----------------------------------------------------------------------------
++
++うーん、本当だろうか？
++
++(B) の残りの部分を片付けよう
++
++    pos = dicsiz;
++
++    if (matchlen > remainder) matchlen = remainder;
++
++pos が dicsiz であることからどうやら、pos は、text[] のインデックスら
++しい。前の予想で pos は、prev[] のインデックスでもあり、hash[] の値で
++もあると予想したのだが(これはもちろん間違いではなかろうが)。どうやら
++本当の意味は、処理するテキストの先頭を示しているのではないかとも思える。
++まあ、ここでは無難に「text[] のインデックス(でもある)」とだけ理解しよう。
++既に図には書き込んである。
++
++次の if だが、remainder が matchlen よりも小さい場合の条件だ。また、
++matchlen の予想が覆されそうな予感がしないでもないが、この if 文は*例外
++条件*なので無視することにした。都合の悪いことは見ない方が良いのだ。
++
++    /* (C) */
++    hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5) 
++            ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
++
++(C) である。これは難解である。複雑な数式は苦手であるが、じっくり考えよ
++う。まず求める値は hval である。これは hash[] のインデックスなのだが、
++このような複雑な式で求まるインデックスなんて想像もつかない。まず、最初
++のインスピレーションを大事にすることにしよう。冒頭で、(C) の処理は「ハッ
++シュ値 hval を計算する。」っと苦もなく予想した。そしてこれは間違いでは
++ないだろう(きっと)。hash[] との関連をここで考えてもわからないから、こ
++のハッシュ値の計算だけを考えることにしよう。
++
++式をじっくり見てみる。。。じっくり見てみると以下のことがわかる。
++
++        x(i) = text[dicsiz + i]
++とすると
++        hval = (( x(0) << 5
++                ^ x(1)      ) << 5
++                ^ x(2)             )
++               & (unsigned)(HSHSIZ - 1);
++
++である。演算子 << は、演算子 ^ よりも優先順位が低いので余計な括弧は省
++略した。最後の & (unsigned)(HSHSIZ - 1) は、前にも似たような式が出たが
++これはある範囲の数値(ここでは、0 〜 HSHSIZ{2^15}-1)を抽出するためのビッ
++トマスクである。ハッシュ関数と言うのはある符号をある集合の符号に写像す
++る関数であるからこのようなビットマスクは当然必要だし、良く行われる事だ
++(普通は mod 素数を行うんだけど)。また、hval は、hash[] のインデックス
++なのだから、写像する集合とは hash[] のインデックスだ。おっ、案外簡単に
++わかった。x(i) が text[dicsiz + i] で、ハッシュ関数の変数は x(0),
++x(1), x(2) だから、先頭の 3 バイトの文字列(平文)のハッシュ値を求めてい
++るわけだ。その他の計算(<< 5 とか ^ とか) は大したことではない。無視し
++よう。また、続けて (D) の処理も見るが、
++
++    /* (D) */
++    insert();
++
++insert() は、幸い解読ずみである pos を hash[] に格納する処理だ。
++予想の段階では、(C) と (D) を別個の処理と考えていたのだがこれは
++どうやらセットである。
++
++   (C) pos の位置の 3 文字のハッシュ値を計算し
++   (D) hash[ハッシュ値] = pos を行う
++
++もう少し注意深く検討すると「posの位置の3文字」と、求めた「ハッシュ値」
++は論理的には = である。
++
++つまり、(C) (D) の処理は
++
++  hash[文字列] = 位置
++
++という処理を行っている。ハッシュ値の衝突はここでは考えない。slide 辞書
++法では、ある文字列に対し以前その文字列が現れたかどうかを検索し、その位
++置を求める必要があるのだが、この最初の 3 文字に関しては現時点でその用
++件(位置を求める)を満たす事ができている。ここまでで自ずと encode() の全
++体像も予想がつきそうな気がする。
++
++衝突は考えないっとしたが、ちょっと考えたらすぐわかった。prev[] には、
++以前のハッシュ値で求めた文字列の位置が入っている。つまり、prev[] はハッ
++シュが衝突したときのためのバッファだ。このハッシュはチェーン法だ。
++
++例えば、insert() で、
++    prev[pos] = hash[hval];
++    hash[hval] = pos;
++っと処理をしているのだから
++
++        hash[hval] = pos1
++                      |
++                      v
++                prev[pos1] = pos2
++                              |
++                              v
++                         prev[pos2] = pos3
++                                ...
++
++といった値が入る事になる。ある文字列(のハッシュ値) hval に対して、その
++辞書上の位置は pos1, pos2, pos3 という候補があるわけだ。実際にどの pos
++を選ぶかは比較によって行われるのだろう。
++
++# それにつけても、(C) と (D) の部分を見るだけでもこのソースがちょっと
++# 汚いことがわかる。もう少し、引数とか戻り値とか考えてくれても良かっ
++# たはずだ。ハッシュ関数にしても少なくともマクロぐらいにはしようよ。
++
++(E) 〜 (H) に移ろうこれはループの中身で、処理の本題だ。まずループの脱
++出条件を見てみると
++
++    while (remainder > 0 && ! unpackable) {
++
++remainder は、バッファ上に読み込んだ平文の長さであるからこれがなくなる
++までループすることになる。さらに unpackable というのは、crcio.c の 
++putcode() でその値を設定している箇所が出て来るのだが、符号化した出力サ
++イズが元のサイズを越えたときに真になる。つまり、これ以上処理しても圧縮
++の意味がないとわかったらループを抜けるわけだ。
++
++では、(E)を見よう。
++
++        /* (E) */
++        lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
++        --matchlen;
++
++ちょっと見ただけではやはりわからない。これらの変数はまだ予想しかしてな
++いからである。が、わかるだけの情報は書きしるそう。
++
++----------------------------------------------------------------------------
++* lastmatchlen    以前の matchlen の値 (変数名から)
++* lastmatchoffset 以前マッチした位置 (変数名から)
++----------------------------------------------------------------------------
++
++以前の値をlast〜に退避し、新たな値を設定する準備をしているわけだ。そし
++て、「新たな値の設定」は、--matchlen で早速行われている。しかし、「マッ
++チした長さ」をまだ何もしてないのに -1 するというのはいったいどういうこ
++とだろう？ matchlen はループの頭で 2 に設定されている。これが 1 になっ
++た。本当の初期値は 1 なのか？
++
++----------------------------------------------------------------------------
++< 各変数の初期値 >
++
++  matchlen = 1
++  matchpos = 0
++  pos = dicsiz
++
++  lastmatchlen = 2
++  lastmatchoffset = dicsiz - 1  (pos - matchpos - 1)
++----------------------------------------------------------------------------
++
++この (E) はまた後で見る事になるだろう。
++
++(F) (G) である。また、その直後には以前にも見た境界条件がある。
++
++        /* (F) */    /* (G) */
++        get_next();  match_insert();
++        if (matchlen > remainder) matchlen = remainder;
++
++if 文 は無視して関数の中身だけを追いかけてみよう。まず、get_next() こ
++れは 次の token を取ってくる処理だと予想してある。はたしてどうだろうか？
++
++static void get_next()
++{
++    remainder--;
++    if (++pos >= txtsiz - maxmatch) {
++        update();
++    }
++    hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
++}
++
++remainder を消費し、pos を進めている。予想通りだ。ひとまず if の条件は
++無視すると、直後で hash 値を求め直している。このハッシュ関数は、以前のハッ
++シュ値を利用しているが、これは pos が以前より + 1 されていることを考え
++ると関連が見えて来る。以前のhash関数を pos の関数として書き直すと
++
++        x(pos+i) = text[pos + i]
++
++        hval(pos) = (( x(pos+0) << 5
++                     ^ x(pos+1)      ) << 5
++                     ^ x(pos+2)             )
++                    & (unsigned)(HSHSIZ - 1);
++
++であり、また、今度のハッシュ関数は、
++
++        hval(pos+1) = ( hval(pos) << 5
++                       ^ x(pos+1 + 2)  )
++                      & (unsigned)(HSHSIZ - 1);
++
++だ、繁雑なので & (HSHSIZE-1) を外すと、
++
++        hval(pos+1) = (( x(pos+0) << 5
++                       ^ x(pos+1)      ) << 5
++                       ^ x(pos+2)             ) << 5
++                       ^ x(pos+3)
++
++っとなる。この次 get_next() が呼び出されれば、
++
++        hval(pos+2) = ((( x(pos+0) << 5
++                        ^ x(pos+1)      ) << 5
++                        ^ x(pos+2)             ) << 5
++                        ^ x(pos+3)                    ) << 5
++                        ^ x(pos+4)
++
++である。順にハッシュ値を求める文字列長を増やしている。とにかく、
++get_next() は、pos を進め、remainder を縮め、新たな(以前より1文字長い) 
++文字列のハッシュ値 hval を求める関数のようだ。
++
++しかし、いつまでも hash 値の元となる文字列を伸ばしてもしょうがないだろ
++う。hval はどこかでまたリセットされるはずだ。っと思ってソースを探して
++みたがそのような箇所は見当たらない。なぜだろう？考えてみる・・・最初は
++わからなかったが数式をよく見てみたらわかった。<< 5 が鍵だ、hval(pos+2) 
++の式を見ると x(pos+0) は、<< 5 が、4回も行われているつまり、20ビットの
++シフトだ。hval(pos+3) なら、25ビット、hval(pos+4) なら 30 ビットのシフ
++トだ。さすがにこれだけシフトすれば、x(pos+0)の情報は消えてもいいだろう。
++
++実際、hval は何文字分の情報を持つのだろう？hval は、unsigned int で、
++普通 32 bit であるから、6.4 文字分だろうか？いや、実際にはハッシュ値の
++計算時にHSHSIZ (15bit) でマスクをかけているから 15 bit の情報しか持た
++ない。つまり、3文字だ。ビット計算は苦手なので図示して確認しよう。
++
++                 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
++                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
++          hval  |--|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
++                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
++
++最初の hval(0) は、x(0), x(1), x(2) に対して、
++
++                    <---  5 -----> <---  5 -----> <---  5 ----->
++                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
++    x(0) <<10    --  x  x  x  x  x
++                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
++    x(1) << 5    --        x  x  x  x  x  x  x  x
++                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
++    x(2)         --                       x  x  x  x  x  x  x  x
++                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
++
++の排他的論理和である。hval(0) の時点で x(0) の情報は 5 ビット残ってい
++るが hval(1) になれば消えてしまうのは自明である。どうにも最初の文字に
++関しては 5 ビットしか情報を使用しないと言うのが気持悪いのだが、15 bit 
++サイズの変数 hval には、過去 3 文字分の情報しか保持されないのは間違い
++ない。get_next() の処理を見れば、位置 pos に対して、hval は常に pos,
++pos+1, pos+2 の情報しか持たないわけだ。これは重要だ。メモしよう
++
++----------------------------------------------------------------------------
++ * hval  hash[]のインデックス。現在位置 pos に対して、
++         text[pos], text[pos+1], text[pos+2] のハッシュ値で、論理的には
++             hval == text[pos] + text[pos+1] + text[pos+2]
++         と同義
++----------------------------------------------------------------------------
++
++ところで、前回、hval の計算とinsert() はセットだと言った。今回はどうだ
++ろう？次の match_insert() を見てみる。
++
++static void match_insert()
++{
++    ... 省略 ...
++
++    prev[pos & (dicsiz - 1)] = hash[hval];
++    hash[hval] = pos;
++}
++
++・・・強敵であった。強敵すぎたので逃げて、最後の2 行だけに着目した。こ
++れは、insert()と同じだ。予想は当たっている。get_next() で hval を更新
++した後は、この match_insert() で、prev[] と hash[] を更新するわけだ。
++そして、match_insert() の省略した部分は、どうやら matchpos, matchlen,
++too_flag を更新しているだけのようだ。これが本当なら match_insert()で、
++insert()の処理をせず、関数を分けるかした方が良さそうだ。(真偽の程は詳
++細を見てからになる)
++
++おもむろに後続の処理 (H) を見ると、
++
++        /* (H) */
++        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
++
++これが真なら「見つからなかった状態」と予想した(なぜだろ？)。そして、
++lastmatchlen は初期状態では 2 である。予想した条件は逆か？ matchlen ま
++わりは予想ばかりで進めすぎた。そしてどうやら match_insert() を読みとか
++なければこの先も分からずじまいになりそうだ。
++
++このまま match_insert() を詳細に解析する事にしよう。match_insert()
++をすべて再掲する。
++
++/* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */
++
++static void match_insert()
++{
++    unsigned int scan_pos, scan_end, len;
++    unsigned char *a, *b;
++    unsigned int chain, off, h, max;
++
++    max = maxmatch; /* MAXMATCH; */
++    if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
++    matchpos = pos;
++
++    off = 0;
++    for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
++        h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
++    }
++    if (off == maxmatch - THRESHOLD) off = 0;
++    for (;;) {
++        chain = 0;
++        scan_pos = hash[h];
++        scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++        while (scan_pos > scan_end) {
++            chain++;
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++                if (len > matchlen) {
++                    matchpos = scan_pos - off;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++            }
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++        }
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++        if (matchlen > off + 2 || off == 0)
++            break;
++        max = off + 2;
++        off = 0;
++        h = hval;
++    }
++    prev[pos & (dicsiz - 1)] = hash[hval];
++    hash[hval] = pos;
++}
++
++まず、初期化部分の前半
++
++    max = maxmatch; /* MAXMATCH; */
++    if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
++    matchpos = pos;
++
++    off = 0;
++
++maxmatch は、固定値で 256 だ、だから max も 256
++2行目の if 文は、これまでしつこいくらいに出て来た条件に似ているが、今
++回は条件を満たすらしい。これまでは、
++
++    if (matchlen > remainder) matchlen = remainder;
++
++という条件だった。そして今回は、
++
++    if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
++
++だから、全体的に matchlen の値は、
++
++    THRESHOLD-1 <= matchlen <= remainder
++
++つまり、
++
++              2 <= matchlen <= バッファに残ったテキスト長
++
++の範囲に納められるようだ。ここでは、matchlen は下限値を下回るので2 に
++設定される。次に matchpos, off が初期化され。以下の図の状態になる。
++(pos, remainder は、get_next() で更新されていることに注意)
++
++----------------------------------------------------------------------------
++                                
++                                dicsiz=2^dicbit               2*2^dicbit
++                                   v                           v   txtsiz
++       +-------------+-------------+-------------+-------------+---+
++  text |             |             |             |             |   |
++       +-------------+-------------+-------------+-------------+---+
++                                     `-pos(=dicsiz+1)          <--->
++                                       matchpos(=pos)           maxmatch{256}
++                                       off(=0)
++
++                                     <------ remainder ------------>
++
++                                   |--- この位置に最初の  ---------|
++                                        データが読まれている
++----------------------------------------------------------------------------
++
++初期化部分の後半
++
++    for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
++        h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
++    }
++    if (off == maxmatch - THRESHOLD) off = 0;
++
++h は、too_flag[] が今のところすべて0だから hval だ。(too_flag は、h つ
++まり hval をインデックスに取るらしい。hash[] と同じだ。再掲はしないが
++メモに書き加えておこう)
++
++off は、pos の位置からのオフセットのようだ(h を更新する for 文の中身か
++ら)。図もその位置に書いた。最後の if 文は off が上限に達した場合に0 に
++再初期化している。よくわからないので無視しよう。for 文の中身からh や 
++off の用途はどうも先読みしたハッシュ値とその先読みの位置なのではないか
++と想像する。too_flag[] の状態によって先読みすべき値が変わるのだろうか？
++
++とにかく処理の本題に入る事にしよう。まず、この関数に現れる局所変数を列
++挙しておこう
++
++    unsigned int scan_pos, scan_end, len;
++    unsigned char *a, *b;
++    unsigned int chain, off, h, max;
++
++off, h, max はすでに出て来たので残りは
++
++  scan_pos, scan_end, len, a, b, chain
++
++だ、これだけの変数の意味を解読しなくてはならない。変数は状態を表すから、
++その数が多いと言うのはそれだけ複雑な処理だということだ。めげる。
++
++この関数のメインとなるループの中をざっと眺めてみるさらに内部にループが
++ある。ひとまず、二重ループの中身を省略しよう。
++
++    for (;;) {
++        chain = 0;
++        scan_pos = hash[h];
++        scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++
++        while (scan_pos > scan_end) {
++            chain++;
++            ... 略 ...
++        }
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++        if (matchlen > off + 2 || off == 0)
++            break;
++        max = off + 2;
++        off = 0;
++        h = hval;
++    }
++
++まず、前半部分から
++
++        chain = 0;
++        scan_pos = hash[h];
++        scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++
++chain, scan_pos, scan_end はすべて while ループに渡されるべき変数だ。
++さらに、while の後には、scan_pos, scan_end は現れないから(仮に while 
++ループが1つの関数だったとすると)これらは while ループ部の引数(入力)だ。
++この2つの変数はどうやりくりしようとも、while ループ部内の状態しか表さ
++ないので、ここでは無視しよう。
++
++while ループの後を見てみると
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++        if (matchlen > off + 2 || off == 0)
++            break;
++        max = off + 2;
++        off = 0;
++        h = hval;
++
++chain が LIMITを越えた場合、too_flag[h] = 1 としている。chain は、ざっ
++と見て、while ループのカウンタらしいが、LIMIT は 0x100 だ。どうにも例
++外条件っぽい(LIMITという名前や数値がそう思わせる)のでここでは無視しよ
++う。while ループが 256以上回る可能性がある点だけ心にとどめておこう。
++
++次の条件では、matchlen と off が条件判断されている。ということはこのど
++ちらか、あるいは両方は while ループの返り値(出力)だ。ざっと 
++match_insert()全体を見てみると off は最初とこの直後でしか更新されない
++らしい。つまり、while ループ部の返り値はmatchlen の方だ。
++この条件は for () ループの脱出条件でもある。心にとどめて、次に進む。
++
++        max = off + 2;
++        off = 0;
++        h = hval;
++
++ふむ。よくわからない。しかし注目すべき点はある。off はここで、0 になる
++がこれ以降は off の値は変わらない。つまり、off は最初は何らかの値で 
++while ループ部に渡されるが、その次からは、0 だ。この for ループが何度
++回ろうとも 0 だ。h も同じで最初は何らかの値を持つが、2回目のループ以降、
++h は hval だ。max は、off を 0 にする直前に更新しているから、h や off 
++と事なり、3つの状態を持つ、すなわち。maxmatch, off+2, 2 だ。
++
++いや、脱出条件を見てみると off == 0 なら break とある。つまり、この 
++for ループはどんなに頑張っても2回しか回らないらしい。やっぱり max も 2 
++つの状態しか持たないようだ。
++
++これで、1 回目、2回目に while ループ部に入る直前の状態が書ける。この関
++数 match_insert() は、while ループ部を1回か2回実行する処理と言うわけだ。
++
++ここで無視していた。while ループ部の入力となる scan_pos, scan_end
++もそれぞれどのような状態になるか書いておく
++
++----------------------------------------------------------------------------
++< 1回目 >
++   h = 何か
++   off = 何か
++   max = maxmatch
++
++   scan_pos = hash[h]
++   scan_end = pos + off - dicsiz  (あるいは、off)
++
++   matchlen = 2
++   matchpos = pos
++< 2回目 >
++   h = hval
++   off = 0
++   max = 前の off + 2
++
++   scan_pos = hash[hval]
++   scan_end = pos - dicsiz  (あるいは、0)
++
++   matchlen = ?
++   matchpos = ?
++----------------------------------------------------------------------------
++
++上記は一般化した場合だが、今回(初回)の場合、h や off の値は、hval であ
++り、0 だった。2回目ループのときの状態と同じである。2回のループの違いは 
++max の値がmatchpos であるか off+2 (すなわち2)であるかの違いしかないようだ。
++
++ここは、条件を少なくするためにこの場合だけにしぼって処理を考えよう。
++while ループの2回の呼び出しを行う際の状態は以下の通りに書き直せる。
++
++----------------------------------------------------------------------------
++< 1回目 >
++   h = hval
++   off = 0
++   max = maxmatch
++
++   scan_pos = hash[hval]
++   scan_end = pos - dicsiz  (あるいは、0)
++
++   matchlen = 2
++   matchpos = pos
++< 2回目 >
++   h = hval
++   off = 0
++   max = 2
++
++   scan_pos = hash[hval]
++   scan_end = pos - dicsiz  (あるいは、0)
++
++   matchlen = ?
++   matchpos = ?
++----------------------------------------------------------------------------
++
++うーん、まだ、すっきりしない。何がすっきりしないかというと scan_end の
++値だ。これが何を意味するのかがよくわからない。scan_pos は、わかるのか？
++というと、わかる。hash[hval]だから現在の文字列と同じ文字列の辞書上の位
++置だ。さらに、現時点では get_next() で、hval を更新してから insert() 
++を行っていないので、hash[hval] には何も入っていない。すなわち 0 だ。
++
++        scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++
++を考えよう。off は、0 だから
++
++        scan_end = (pos > dicsiz) ? pos - dicsiz : 0;
++
++なわけだ。さらに、posは現時点で dicbit+1 であるから、1 だ。図に書こう。
++
++----------------------------------------------------------------------------
++                                
++                                dicsiz=2^dicbit               2*2^dicbit
++                                   v                           v   txtsiz
++       +-------------+-------------+-------------+-------------+---+
++  text |             |             |             |             |   |
++       +-------------+-------------+-------------+-------------+---+
++       ^ ^                           `-pos(=dicsiz+1)
++       | |
++       | scan_end はこの辺(1)
++       scan_pos はこの辺(0)
++
++   h = hval
++   off = 0
++   max = 2
++
++----------------------------------------------------------------------------
++
++ついに、text[] バッファの左半分に指しかかる。これが何なのかは現時点で
++は明確に書いてなかったが予想するとこの左半分はズバリ辞書だ。言い切って
++やろう。今まで辞書らしい(dicsizのサイズを持つ)バッファは hash[] や 
++prev[] があったが、hash[], prev[] の用途はもう明確である。辞書となり得
++るバッファはもうこの text[] しかないのだ。
++
++さらに、左半分に限らずこの text[] 全体が辞書であろうと予想する。これは
++ただの勘だが text[] は環状バッファなのではなかろうかと考えている。
++
++# 最初の方で prev[] が辞書だと予想したが間違った予想をしていたことにこ
++# の時点で気づいた。prev[] が辞書と同じサイズを持つ理由はまだよくわか
++# らない。
++
++この時点ではまだ scan_pos や scan_end の真の意味はわからない。off のこ
++とを無視しているから予想も立ちにくいが、ひとまず初期状態がどういったも
++のかはわかったのでこのまま、while ループ部を見てみたいと思う。
++
++        while (scan_pos > scan_end) {
++            chain++;
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++                if (len > matchlen) {
++                    matchpos = scan_pos - off;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++            }
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++        }
++
++まず、if 文の条件を満たさない場合だけを考える。
++
++        while (scan_pos > scan_end) {
++            chain++;
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++                ...
++            }
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++        }
++
++
++offは 0 なので、text[scan_pos + matchlen] != text[pos + matchlen] とい
++う条件の場合を想定するわけだが、
++
++text[scan_pos + matchlen]
++
++と
++
++text[pos + matchlen]
++
++を比べている
++
++text[scan_pos]  辞書上の文字列の*先頭*
++text[pos]       現在の文字列の*先頭*
++
++を比べないのは matchlen が前に予想した「最低限一致しなければならない長さ-1」
++だからであろう。現時点で、matchlen が 2 だから
++
++text[scan_pos + 0] == text[pos + 0]
++text[scan_pos + 1] == text[pos + 1]
++
++であったとしても、
++
++text[scan_pos + 2] != text[pos + 2]
++
++であれば、「最低限一致しなければならない長さ」という条件を満たさないの
++である。なので matchlen の位置から先に比較して無駄な比較をしないように
++している。後でちゃんとした比較の処理が出て来るだろう。このような処理は
++処理としては効率が良いのだが、ことソース理解と言う点では冗長である。わ
++かりにくいのだ。仕方ないのだけど。
++
++# matchlen の意味の予想はどうやら当たっているようだ。matchlen は最短一
++# 致長で、minmatchlen っと名付けても良さそうな変数だ。
++
++そして、比較に失敗したら scan_pos を更新する。
++
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++
++ハッシュのチェーンをたどっている、つまり次の候補を辞書から取り出してい
++るわけだ。ここまでで、while ループの処理内容の想像はついた。このループ
++は辞書から(最長)一致する文字列を探しているのだろう。
++
++順番が前後したが、while ループの脱出条件を見てみる
++
++        while (scan_pos > scan_end) {
++
++これはどういうことだろう？ scan_pos は、ハッシュのチェーンをたどって同
++じハッシュ値を持つ文字列の位置を探す、この値はだんだんと小さくなって行
++くものなのだろうか？
++その通りである。hash[] への格納はファイルから取って来た文字列を順に格
++納して行くのでチェーンの奥には、より前の方の位置が書かれているはずだ。
++逆にチェーンの浅い部分にはより現在位置に近い位置が書かれているのだろ
++う。では、その境界 scan_end はどうやってわかるのだろうか？これは後でま
++た検証しよう。
++
++では、処理の本質 if 文の中を見る事にしよう
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++                if (len > matchlen) {
++                    matchpos = scan_pos - off;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++            }
++
++最初の意味もなくブロックになっている部分を見る、
++
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++この処理では a, b といういかにも局所な名前の変数が使われている。これは、
++本当にこのブロック内で局所的なもののようだ。ならば定義位置もこのブロッ
++ク内にして本当に局所的にして欲しかった。
++
++さらに、この処理は単に文字列 a, b を比較しているだけのようだ。memcmp() 
++ではまずいのかと言うとここで求めているものが「どこまで一致したか(len)」
++のようなので、memcmp() では役不足だ。
++
++その次の処理、
++
++                if (len > matchlen) {
++                    matchpos = scan_pos - off;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++
++で、matchlen (最低一致長)より大きい場合に条件を満たす。条件を満たさな
++ければ、scan_pos を更新し、次のループに移る。では、条件を満たす場合を
++見てみよう。まず最短一致長の一致条件を満たした場合、matchpos と 
++matchlen を更新する。
++
++matchpos はマッチした位置、
++matchlen はマッチした長さ
++
++で、matchlen が max なら最長一致長に達しているので、これ以上探索はしな
++い。matchlen は最短一致長でありながら、一致長でもある変数のようだ。
++(どうやら以前の2つの予想はどちらも当たっていた模様)
++
++とにかく while ループ部の出力は、この matchpos と matchlen のようだ。
++前に書いた通りこのループは「最長一致文字列を求める処理」だ。
++
++match_insert() の全体をもう一度見てみよう。ただし、以下の書き換えを行う。
++
++o while ループ部は search_dict(pos, scan_pos, scan_end, max) という関数
++  に置き換えたものとする。
++
++o 末尾の insert() と同等の処理を行っている部分も insert() の呼び出しに
++  すり替えよう。(match_insert() 関数の中で insert() 処理を本当に行うべ
++  きものなのかどうかが疑問だが)
++
++o chain という変数にかかわる処理も隠した(search_dict内で行う)
++
++o for ループは、2回しかまわらないので、2 度の search_dict() の呼び出し
++  に書き換える
++
++static void match_insert()
++{
++    unsigned int off, h;
++    unsigned int scan_end;
++
++    if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
++    matchpos = pos;
++
++    off = 0;
++    for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
++        h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
++    }
++    if (off == maxmatch - THRESHOLD)
++        off = 0;
++
++    scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++    search_dict(pos, hash[h], scan_end, maxmatch);
++
++    if (off > 0 && matchlen <= off + 2) {
++      off = 0;
++
++      scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++      search_dict(pos, hash[hval], scan_end, off+2);
++    }
++
++    insert();
++}
++
++だいぶすっきりした(が、まだ繁雑だ)。まだ、off にかかわる部分がよく分か
++らないが、ひとまず良いだろう。この関数の解析はこれで終って良いだろうか。
++
++いや、良くない。肝心の match_insert() の出力がよくわからない。この関数
++は「最長一致文字列を探し、hash を更新する処理」(くどいようだが、hashを
++更新するは余計に思う)なのだろうが、最長一致文字列が見つからなかったと
++いうのはどう判断されるのだろう？
++
++まず、search_dict() で見つからなかった場合、matchlen は更新されない
++(matchpos は、pos になる)。そして、おそらく 2 度目の search_dict() の
++呼び出しが行われる。が、too_flag[] というので、判断できそうな気もする
++がこれはむしろハッシュのチェーンをたどりすぎるのを止めるためのフラグで
++あるように思える。
++
++2度目の search_dict()で、max の値が変わるのが鍵だろうか？。今回の場合、
++max は 256 から 2 になる。最長一致長として 2 が限界値になると、
++search_dict() の動作は変わるだろうか？いや、やはり変わらない。どうにも
++この関数だけでは見つかったか見つからなかったかという判断はできないよう
++だ。(本当はわかっているはずなのにその情報を直接外に持ち出していない)
++
++気持悪いがやはりこの関数の解析を終え、次に移る事にしよう。
++
++(H) である。以前、
++
++(H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD なら
++
++(H.1) output() する。(マッチしなかったらそのまま出力しているのだろう。たぶん)
++(H.2) そうでなければ(マッチしたなら)、output()し、何かいろいろする。
++
++っと予想した部分だ。今や match_insert() は、解析済みだからこれの真偽が
++わかるか？というとやっぱり、わからない。ただ、
++        matchlen > lastmatchlen
++というのは、辞書から文字列が見つかった場合の条件になりそうだから、やはり
++これは予想が逆だろうか？とにかく、比較的簡単そうな、(H.1) から見よう。
++
++        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
++            /* (H.1) */
++            encode_set.output(text[pos - 1], 0);
++            count++;
++        } else {
++
++どうも、文字 text[pos-1] を出力しているだけのように思える。文字の出力
++は、slide 辞書法では「辞書から見つからなかった場合」を意味するから、や
++はり最初の予想はあってそうなのだが・・・仕方ないので、output()の処理を
++覗いて見よう。これは、lh5, 6, 7 の場合、huf.c:output_st1(c, p) である。
++現時点で処理の内容を見てもわけがわからないが、結論から言うと第一引数 c 
++は、文字で、第二引数 p は、位置である。冒頭の decode 処理で、文字 c は
++長さも兼ねていると説明済みなので、(そして、text[pos-1] には現時点で文
++字そのものしか書かれていない)これはやはり文字を出力している処理だ。つ
++まり「見つからなかった場合」の処理だ。
++
++なぜ、pos-1 なのだろう？確かに Huffman coding に文字を渡すのはこれが初
++めてで、現在 pos の位置はバッファの1文字進んだ位置にある。pos-1 は出力
++しなければならないのは当然だ。ということは pos は常に「未出力文字の位
++置 + 1」なのかもしれない。
++
++次の count++ を見る。count はどうやらこの関数の変数ではないらしい、困っ
++た事に局所変数の名前っぽいがグローバル変数だ。これはよろしくない。ちょっ
++と grep しただけでは、他にどこでこの変数を使っているのかわからなかった。
++まあ、今 1 文字を渡した所なので、入力文字数なのだと仮定しておこう。こ
++の変数が大勢に影響を与える事はないだろうからこれ以上は見ないと言うのも
++アリだ。
++
++# その後、dhuf.c:decode_p_dyn() でのみ count を使用している事がわかった。
++
++次は (H.2) である。これがまた難解なのだがゆっくり片付けよう。
++
++        } else {
++            /* (H.2) */
++            encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
++               (lastmatchoffset) & (dicsiz-1) );
++            --lastmatchlen;
++
++            while (--lastmatchlen > 0) {
++                get_next();  insert();
++                count++;
++            }
++            get_next();
++            matchlen = THRESHOLD - 1;
++            match_insert();
++            if (matchlen > remainder) matchlen = remainder;
++        }
++
++まず、output() に渡している引数は、それぞれ「長さ」と「位置」であろう
++ことは予想済みだ。さらに UCHAR_MAX{255} + 1 - THRESHOLD{3} だから
++
++ 長さ  lastmatchlen + 253
++ 位置  lastmatchoffset & (dicsiz-1)
++
++となっている。冒頭の decode() の解析で、長さは 253 を足す事は確認済み
++だ(-lhs- の場合 254 を足すという動作が、encoding 部分では考慮され
++てないのは、-lhs- の encoding 機能がないからだ)。ところで、一致長 
++lastmatchlen は 3 以上で初めて 255 を越えることができる。以前予想した、
++THRESHOLD の意味「最低限一致しなければならない長さ」はあっているらしい。
++
++もう一点、注意しなくてはならないのは、出力しているのが lastmatchlen と 
++lastmatchoffset である。これらは、match_insert() のときには更新してい
++ない(last〜の更新は次のループの先頭 (E) で行われる)。先程 (H.1) のとき
++も書き出していたのは、text[pos-1] であった。pos 位置は一歩先読みした位
++置を指すらしい。このような処理を行う場合、最後に調整が必要なはずだ(で
++ないと最後の文字が出力されない)。その調整はどこで行われるのだろう？
++
++さて、後続の処理だが、<長さ、位置>のペアを出力した後は、
++
++            --lastmatchlen;
++
++            while (--lastmatchlen > 0) {
++                get_next();  insert();
++                count++;
++            }
++
++という処理を行っている。get_next() は、pos を進める処理、insert() は辞
++書に登録する処理だから、これは文字列を読み飛ばしている処理だ。確かに 
++lastmatchlen 分の情報は出力済みだから、これは納得である。lastmatchlen 
++を 1 余分に引いているのが謎だがこれは pos が一歩先に進んでいるからであ
++ろうと予想する。つまり、この後は pos の位置はまた「現在位置」に戻る。
++なるほど、先程調整が必要と書いたがここで行われているらしい。細部は不明
++だが少なくとも辞書に文字列が見つかった場合は最後まで出力されるようだ。
++
++次に進もう
++
++            get_next();
++            matchlen = THRESHOLD - 1;
++            match_insert();
++            if (matchlen > remainder) matchlen = remainder;
++
++せっかく pos が現在の位置に戻ったのに、get_next() でまた先読みされた。
++うーむ。そして、matchlen は初期化される。一致情報はすでに出力済みだか
++らこれはうなずける。そして、match_insert() が呼ばれる。この時点で再度
++辞書が検索される。pos はまた1文字進んでいるのだから、これは先程(初期状
++態)のmatch_insert() と大差ない処理だ。(その直後のif文は境界条件なので
++無視)
++
++そうして、また次のループに移る。このとき続けざま get_next(),
++match_insert() が行われる。どうやら pos は次のループからは、 2 文字文
++先に進んでしまうようだ。なぜだろう？
++
++# 後でわかった事だが、while (--lastmatchlen > 0) のループ回数を読み間
++# 違えた。例えば、lastmatchlen が 1 なら、この while ループ内では 
++# get_next() は1回も呼ばれない。
++
++どうにもソースを見ただけで解読するには、このあたりが限界のようだ。どう
++しても細部がわからないし、事実が見えないから予想の積み重ねがたまって不
++安になる。
++
++実は、もう少しマメに図を起こして読み進んで行けばもっとわかることがあっ
++ただろうと思うのだが、それは面倒だし、間違える可能性がある(ここまでで
++何度か痛い思いをした)。以降は、いくつかのデータを実際に圧縮させその動
++きをデバッガで追うことで、これまでの解析結果を検証してみよう。
++
++・・・っと、その前に、ここまでですべての関数を網羅してしまったと思って
++いたのだが、一つ忘れていたものがあった。update() だ。この関数は、
++get_next() で呼び出されていたのだが、以前は無視していた。先にここを見
++ておこう。
++
++まず、get_next() を再掲する。
++
++static void get_next()
++{
++    remainder--;
++    if (++pos >= txtsiz - maxmatch) {
++        update();
++    }
++    hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
++}
++
++remainder と pos を進めた後、pos が txtsiz - maxmatch に達してしまった
++場合(pos == 2 * 2^dicbit の場合)に呼び出されるようだ。つまり、以下の図
++の状態だ。これが、update() を呼び出す時の初期状態だ。
++
++----------------------------------------------------------------------------
++                                
++                                dicsiz=2^dicbit               2*2^dicbit
++                                   v                           v   txtsiz
++       +-------------+-------------+-------------+-------------+---+
++  text |             |             |             |             |   |
++       +-------------+-------------+-------------+-------------+---+
++                                                              /<--->
++                                                             /  maxmatch{256}
++                                                           pos
++
++                                                                <-->
++                                                              remainder
++
++----------------------------------------------------------------------------
++
++では、update() に入る。
++
++static void update()
++{
++    unsigned int i, j;
++    unsigned int k;
++    long n;
++
++#if 0
++    memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
++#else
++    {
++        int m;
++        i = 0; j = dicsiz; m = txtsiz-dicsiz;
++        while (m-- > 0) {
++            text[i++] = text[j++];
++        }
++    }
++#endif
++    n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)], 
++                               (unsigned)dicsiz, infile);
++
++    remainder += n;
++    encoded_origsize += n;
++
++    pos -= dicsiz;
++    for (i = 0; i < HSHSIZ; i++) {
++        j = hash[i];
++        hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
++        too_flag[i] = 0;
++    }
++    for (i = 0; i < dicsiz; i++) {
++        j = prev[i];
++        prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
++    }
++}
++
++先頭で、なぜか memmove() を for ループで書き換えている。なぜこのような
++ことを行っているのだろう。for ループを見てみてもやっていることは変わら
++ない。謎だが、とにかく、text[] の右半分(maxmatch 部分も含む) を左に移
++している。
++
++次に fread_crc() で、新たにファイルを読み込む。今度の読み込み位置は
++&text[txtsiz - dicsiz] で、長さは dicsiz である。当然、remainder も更
++新している。encoded_origsize は以前と同様無視。pos は dicsiz 分減らさ
++れている。これはつまり図示すると、以下の状態になると言う事だ
++
++----------------------------------------------------------------------------
++                                
++                                dicsiz=2^dicbit               2*2^dicbit
++                                   v                           v   txtsiz
++       +-------------+-------------+---+---------+-------------+---+
++  text |             |             |   |         |             |   |
++       +-------------+-------------+---+---------+-------------+---+
++                                  /<--->                       <--->
++                                 / maxmatch{256}              maxmatch{256}
++                                pos
++
++                                   <------------------------------->
++                                              remainder
++
++       |------- 以前のデータ  ---------|--- 新しいデータ  ---------|
++
++----------------------------------------------------------------------------
++
++以降、ファイルの読み込みは常にこの update()でしか行われない。pos は、
++初期状態と同じ位置なので、初期状態が再現されている。ここまでで、
++maxmatch の領域はなんだろうと思うが、おそらく先読みのためだろう。それ
++らしい処理は、match_insert() の冒頭にあった(が、現時点で詳細には触れて
++いない)。
++
++# maxmatch 分の余分な領域は、pos の位置から最大 maxmatch 長の文字列照
++# 合を行うために必要な領域。先読みとはまた見当外れなことを書いたものだ。
++# ちょっと考えればわかることなのに・・
++
++update() の残りを見る。
++
++    for (i = 0; i < HSHSIZ; i++) {
++        j = hash[i];
++        hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
++        too_flag[i] = 0;
++    }
++    for (i = 0; i < dicsiz; i++) {
++        j = prev[i];
++        prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
++    }
++
++内容は、想像がつくので詳細は省略しよう。単に以前のデータが移動したので、
++ハッシュ値を更新しているだけだ。しかし、これはなかなか無駄な処理だ。
++
++以前、text[] は環状バッファだろうと予想したが予想がはずれたことがわかっ
++た。環状バッファにしていれば、このハッシュの書き換えは不要にできただろ
++うと思うのだが・・・
++# そのかわり、位置の大小比較が繁雑にならないので、これはこれで良いのか
++# もしれない。どちらが優れているかは実験してみなければわからないだろう。
++
++これで、一応は slide.c を網羅する事ができた。まだ不明な点は多いが、デ
++バッガで実際の処理を追いかければまたわかることがあるだろう。
++
++・・・しばし、休息・・・
++
++さて、デバッガでと以前は考えていたのだが、あきらめるのはまだ早い(元気
++が出たらしい)、そもそも最初に「デバッガを使わずにどこまで解読できるか」っ
++と冒頭に書いてたのにたった2回の通読でもうあきらめようとしていた。が、
++ここまで書いてきた本書を何度か読み返したが、まだまだ検討の余地はある。
++
++まず、match_insert() の処理でわからなかった部分を解読しよう。実は、こ
++れに関してはどうしてもわからず悩んでいたところ、Lha for UNIX のメンテ
++ナである岡本さんに教えてもらうことができた(ありがとうございます)その内
++容を確認しつつ match_insert() を見ることにする。
++
++まずは、復習だ。通常の状態に関しては match_insert() の解読は済んでいる。
++match_insert() は、text[pos] から始まる文字列を辞書から検索し、見つかっ
++た位置と一致長を matchpos, matchlen に設定する処理だ。そして、ついでに 
++insert() で、text[pos] の位置をハッシュ配列に記録し、次回の検索に備え
++ることもしている。
++
++では、不明な部分はなんだったかというと too_flag[] まわりである。
++too_flag のフラグが立っていると。辞書検索の頼りとなるハッシュ値を変更
++している。この部分がまったく皆目検討がつかなかったのだ。これに関してソー
++スを読み進めよう。以下ソースを再掲する。
++
++static void match_insert()
++{
++    unsigned int scan_pos, scan_end, len;
++    unsigned char *a, *b;
++    unsigned int chain, off, h, max;
++
++    max = maxmatch; /* MAXMATCH; */
++    if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
++    matchpos = pos;
++
++    off = 0;
++    for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
++        h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
++    }
++    if (off == maxmatch - THRESHOLD) off = 0;
++    for (;;) {
++        chain = 0;
++        scan_pos = hash[h];
++        scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++        while (scan_pos > scan_end) {
++            chain++;
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++                if (len > matchlen) {
++                    matchpos = scan_pos - off;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++            }
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++        }
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++        if (matchlen > off + 2 || off == 0)
++            break;
++        max = off + 2;
++        off = 0;
++        h = hval;
++    }
++    prev[pos & (dicsiz - 1)] = hash[hval];
++    hash[hval] = pos;
++}
++
++まず、too_flag[] は、最初すべての要素が 0 である。そして、新たにファイ
++ルを読むとき(update())も 0 に再初期化されるのだった。このフラグが立つ
++条件はというと、この match_insert() の中だけである。その処理は
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++この部分だけだ。chain が LIMIT以上になったら h (これは検索対象のハッシュ
++値だ)に関して、フラグを立てる。chain は while ループ(これは文字列の照
++合を行う処理)のループ回数だ。h に関しての検索が LIMIT{256} 以上の場合
++に too_flag[h] のフラグが立っている。
++
++while ループは一致文字列の一致長が最長一致長に達するか、辞書を最後まで
++探索するまでループする。つまり、あるハッシュ h に関してそのチェーンが 
++256 以上のものに関しては、too_flag[h] が 1 になっている。
++
++では、そのような h に関して、match_insert() がどのような処理になってい
++るかを見る。まず初期化部分
++
++    max = maxmatch; /* MAXMATCH; */
++    if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
++    matchpos = pos;
++
++これは、とりあえず無視。
++
++    off = 0;
++    for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
++        h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
++    }
++    if (off == maxmatch - THRESHOLD) off = 0;
++
++通常 off は、0 なのだが、too_flag[h] が 1 であるものに関しては値が変わ
++る。検索対象となる文字列 text[pos](のハッシュ値) hval に関して、
++too_flag[h] が立っていれば、(このハッシュのチェーンが 256 以上であるこ
++とが事前にわかっていれば)
++
++        h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
++
++で、検索対象となるハッシュ値を変更している。このハッシュ値が示すのは元
++の検索対象文字列の 1 文字先だ。
++
++----------------------------------------------------------------------------
++
++                           |--- c --|
++                        |--- b --|  |
++                     |-- a ---|  |  |
++       +-------------+--------+--------+
++text   |             |  |  |  |  |  |  |
++       +-------------+--------+--------+
++                      \  \
++                      pos pos+1(off=1)
++
++----------------------------------------------------------------------------
++
++元の検索対象文字列が図の a だとすると、これを図の b にしている。初期化
++部のループは、もしこの b のハッシュチェーンに関して too_flag[h] がさら
++に 1 であるならさらに 先の文字列をハッシュ値とするようになっている。
++(これは元の pos の 2 文字先を示す。図の c の部分だ) h は、pos+off から
++の3文字のハッシュ値を示すものと言う事だ。
++
++ただし、h があまりにも先の方を見るようなハメになれば(off が maxmatch -
++THRESHOLD) off は 0 に再設定されるが、このとき h はそのままだ。この意
++味はまだわからないが、バグなのではないかと想像している(h = hval に再設
++定する必要があるだろう)
++
++では off = 1 だとして本処理を見ることにしよう。外側の for ループに関し
++ては、while ループを2回実行するかどうかだけのものだった。なので、 
++while ループ部だけを見てみよう。
++
++        chain = 0;
++        scan_pos = hash[h];
++        scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
++        while (scan_pos > scan_end) {
++            chain++;
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++                if (len > matchlen) {
++                    matchpos = scan_pos - off;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++            }
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++        }
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++scan_pos, scan_end に関しては検索開始位置と終了位置と言う事でもう良い
++だろう。で、最初の if の条件に着目する。
++
++            if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
++
++これが真となる状態を図示しよう。
++
++----------------------------------------------------------------------------
++
++                                                        |-- c ---|
++                    |-- a ---|                       |--- b --|
++       +---------------+--------+--------------------+--------+--------+
++text   |               |  |x'|  |                    |  |  |x |  |  |  |
++       +---------------+--------+--------------------+--------+--------+
++                       ^                             \  \
++                      scan_pos                       pos pos+1(off=1)
++
++----------------------------------------------------------------------------
++
++まず、if 条件の左辺
++
++  text[scan_pos + matchlen - off]
++
++matchlen は、match_insert() に入る直前に 2 に初期化されている(最初は)
++ので、照合するのは図の x' だ。
++
++if 条件の右辺
++
++  text[pos + matchlen]
++
++これは、図の x の位置だ。x' == x ならば本格的に照合を開始する。
++
++                {
++                    a = text + scan_pos - off;  b = text + pos;
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++ここで比較しているのは、図の a と b だ。b は、off がどのような場合でも
++変わらないが、a は、off が大きければ大きい程左側を指す。off が例えば
++3 であるときの場合も見てみよう。
++
++----------------------------------------------------------------------------
++
++              |-- a ---|                             |--- b --|-- c ---|
++       +---------------+--------+--------------------+--------+--------+
++text   |             x'|  |  |  |                    |  |  |x |  |  |  |
++       +---------------+--------+--------------------+--------+--------+
++                       ^                              \        \
++                      scan_pos                        pos      pos+3(off=3)
++
++----------------------------------------------------------------------------
++
++結局比較しているのは、pos からの文字列のハッシュ値を求めた場合と何も変
++わらない。off でいくら先を見ようとも比較するのは pos の位置だ。なぜこ
++のようなことをするのだろうか？これは最初どうしてもわからなかったのだが、
++説明を受けて納得した。
++
++これは単に効率(速度)のためということだ。もし、図の b に関して照合文字
++列の候補があまりにも多い場合(too_flag[h]=1)、ハッシュのチェーンを何度
++もたどる事になるので効率が悪い。しかし、辞書検索のキーを何文字か進める
++事で、この可能性を減らす事ができる。少なくとも最悪の 256 よりはマシに
++なるようなものを選んでいる。そうして、この while ループのループ回数を
++減らしているのだ。どうせ探したいのは最長一致文字列なので先の方の文字列
++が一致しないと話にならないのだからこれは合理的だ。
++
++これで、外側の for ループも納得だ。これは while ループをある条件でやり
++直す処理だった。
++
++        if (matchlen > off + 2 || off == 0)
++            break;
++
++最長一致長が見つかるか、あるいは off が 0 であればさっさとこの処理は終
++るのだが、もし off を進めて照合を行っていたとして、最長一致文字列が見
++つからなかったとすると
++
++        max = off + 2;
++        off = 0;
++        h = hval;
++
++という条件で照合をやり直す。これは元の文字列で照合をやり直すということ
++だからつまりは、最悪のハッシュチェーンを仕方ないから辿り直そうと言う事
++だ。さらに、pos から pos+off+3 までの文字列が、辞書から見つからなかっ
++たので、最大一致長を off + 2 として条件を緩めている(なぜこれが条件を緩
++める事になるかと言うと while ループは最大一致長の文字列が見つかったら
++すぐに抜けるからだ)。
++
++ところで、match_insert() の先の処理は以下の書き換えを行うともう少し見
++やすくなる。(と思う)。
++
++o scan_beg という変数を用意し、これを scan_pos - off にする。
++o scan_end は、pos - dicsiz にする。
++o while 条件を while (scan_pos != NIL && scan_beg > scan_end) にする。
++
++以下
++
++        unsigned int scan_pos = hash[h];
++        int scan_beg = scan_pos - off;
++        int scan_end = pos - dicsiz;
++
++        chain = 0;
++        while (scan_pos != NIL && scan_beg > scan_end) {
++            chain++;
++
++            if (text[scan_beg + matchlen] == text[pos + matchlen]) {
++                {
++                    unsigned char *a = &text[scan_beg];
++                    unsigned char *b = &text[pos];
++
++                    for (len = 0; len < max && *a++ == *b++; len++);
++                }
++
++                if (len > matchlen) {
++                    matchpos = scan_beg;
++                    if ((matchlen = len) == max) {
++                        break;
++                    }
++                }
++            }
++            scan_pos = prev[scan_pos & (dicsiz - 1)];
++            scan_beg = scan_pos - off;
++        }
++
++        if (chain >= LIMIT)
++            too_flag[h] = 1;
++
++----------------------------------------------------------------------------
++
++              |-- a ---|                             |--- b --|
++       +---------------+--------+--------------------+--------+--------+
++text   |      |      x'|  |  |  |                    |  |  |x |  |  |  |
++       +---------------+--------+--------------------+--------+--------+
++         ^     \        \                             \        \
++         |    scan_beg  scan_pos                        pos      pos+off
++     scan_end
++
++         |----|
++           scan_beg の有効範囲
++
++         |----------------- dicsiz ------------------|
++
++----------------------------------------------------------------------------
++
++scan_beg, scan_end の範囲もわかりやすいし、hash[h] が NIL の場合の処理
++も明示的だ。この書き換えを行う場合、scan_beg が負の値になる可能性があ
++る。元もとの処理では scan_end 等の変数を unsigned にしているので、これ
++らを int にして while 条件で負の scan_beg をはじかなければならないこと
++に注意。そうすると、scan_pos != NIL は必要なくなるのだがわかりやすさを
++追求した。
++
++これで match_insert() の解読は終りだ。match_insert() の処理とは以下の
++通りだ。
++
++----------------------------------------------------------------------------
++  match_insert() は、text[pos] から始まる文字列に一致する文字列を辞書
++  から検索し、見つかった位置と一致長を matchpos, matchlen に設定する。
++
++  もし、最長一致文字列が見つからなければ matchpos は、pos に設定され、
++  matchlen は更新されない。(実は、matchpos = pos の情報は特に使われてない)
++
++  見つかった場合、matchlen は呼び出し前の matchlen よりも大きくなる。
++  (呼び出し前では matchlen の意味は最低限一致しなくてはならない文字列
++  長で、照合条件の一つになっている)
++
++  この関数の入力は
++
++      matchlen
++      pos
++
++  出力は
++
++      matchlen
++      matchpos
++
++  といったところ。
++
++  さらに、insert() と同様の処理で、pos の位置をハッシュ配列に記録し、
++  次回の検索に備える。これはついでの処理。
++---------------------------------------------------------------------------- 
++
++これを踏まえた上で処理内容を再読しよう。(E) 〜 (H) だ。
++
++        /* (E) */
++        lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
++        --matchlen;
++
++        /* (F) */    /* (G) */
++        get_next();  match_insert();
++        if (matchlen > remainder) matchlen = remainder;
++
++        /* (H) */
++        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
++            /* (H.1) */
++            encode_set.output(text[pos - 1], 0);
++            count++;
++        } else {
++
++(H) の条件とは何なのかを見る。この条件が真なら、文字列をそのまま出力す
++るのだが、素直に slide 辞書法の処理を考えればこの条件は「辞書から見つ
++からなかった場合」となる。が、実際にはもう少し複雑だ。
++
++        /* (H) */
++        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
++
++matchlen は、pos の位置の文字列が見つかった辞書上の長さ
++lastmatchlen は、pos-1 の位置の文字列が見つかった辞書上の長さ
++
++であるとすると、この条件は、「pos の位置で見つかった長さが、pos-1 の位
++置で見つかった長さよりも長ければ」っとなる。
++
++これはつまり、pos-1 と pos のニ箇所に関して辞書を検索して、より長くマッ
++チする方を選ぼうとしているわけだ。matchlen の方が長いなら 1 つ前
++(pos-1)の文字はそのまま出力し、次のループに移る(もし、次の文字が
++さらに長くマッチするなら。またそのまま出力される)
++
++この条件で「見つからなかった場合」というのはどう表されているかを考える。
++もし、pos の文字列が辞書になければ pos - 1 の文字列は、どうすべきかと
++いうと「pos-1 の文字列が見つかってなければ。そのまま出力。辞書にあった
++なら <lastmatchlen, lastmatchoffset> のペアを出力」っとならなければな
++らない。
++
++lastmatchlen は、初期状態では THRESHOLD - 1 であったので、見つからなかっ
++たという条件は (H) の右側の条件 lastmatchlen < THRESHOLD でまず表され
++ている。
++
++では、例えば lastmatchlen が 5 であったとしよう。このとき (E) の処理で 
++matchlen は lastmatchlen - 1 つまり、4 に設定される。そして、match_insert()
++で次の文字列がもし辞書から見つからなければ matchlen は更新されないので
++  matchlen < lastmatchlen 
++となる。このような条件(前回見つかり、今回見つからない)場合に限り、(H.2)
++の処理が実行されるようになっている。では、(H.2) の処理を追いかけよう。
++
++まず、この状態を図示する。
++
++----------------------------------------------------------------------------
++
++                         lastmatchlen                  lastmatchlen
++                       |--          --|              |--          --|
++       +---------------+--------------+--------------+--------------+--+
++text   |               |  |  |  |  |  |              |  |  |  |  |  |  |
++       +---------------+--------------+--------------+--------------+--+
++                       ^                             |   \           \
++                      matchpos                    pos-1  pos         pos2
++
++                       |--------------------------|
++                             lastmatchoffset
++
++----------------------------------------------------------------------------
++
++
++            /* (H.2) */
++            encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
++               (lastmatchoffset) & (dicsiz-1) );
++            --lastmatchlen;
++
++            while (--lastmatchlen > 0) {
++                get_next();  insert();
++                count++;
++            }
++            get_next();
++            matchlen = THRESHOLD - 1;
++            match_insert();
++            if (matchlen > remainder) matchlen = remainder;
++        }
++
++まず、<長さ, 位置> のペアを出力する。これはいいだろう。出力する「位置」
++は0 なら 1 文字前を表すので、実際のオフセット pos - 1 - matchpos より
++も 1 小さい値になっていることに注意しておこう。
++
++そして、lastmatchlen は 1 引かれる。この場合例えば 4 になる。したがっ
++て、次のループでは 3 文字 pos が先送りされる(4 ではない)。pos は既に 1 
++文字先に進んでいるので、最初に 1 引くのはこのことを考慮している。while 
++ループが終った後はpos の位置は実際に出力した文字列の最後の文字 pos2-1 
++を指していることになる。
++
++そして、get_next() でまた 1 文字先に送る。pos は図の pos2 の位置になる。
++そして、match_insert() で、この位置の文字列を照合する。matchlen は、
++THRESHOLD - 1 に初期化されるので pos2 の位置の文字列が辞書から見つから
++なければ matchlen は、THRESHOLD-1 だ。これは初期状態と同じ状態を示すの
++で、次のループの処理も想像がつく((H) の条件の右側 lastmatchlen < THRESHOLD
++が有効になる)。では、見つかった場合はというと、次のループでさらに先 
++pos2+1 の照合結果と比較されるのでこの処理も想像がつく。
++
++最初、どうにもこの処理内容が理解できなかったのだが「現在の文字列と、次
++の文字列のそれぞれで辞書を検索し、より長く見つかった方を使う」という最
++適化を行っている事がわかってしまった後は解読は簡単だった。(実はこの事
++実も教えてもらった事だ。全然ダメじゃん)
++
++さて、これで一通りの解析は済んだわけだが、ここまでの解析内容を読み直し
++てみると、以下の点がまだひっかかる。
++
++1. ハッシュ関数は最適なのか？特に HSHSIZ{2^15} は最適なのか？
++2. too_flag[] は、実際に照合を行いループがLIMITを越えた場合に
++   設定される。しかし、ハッシュのチェーンを作る際にチェーンの
++   個数をあらかじめ数えておけば一度の探索すらも行われず。より
++   早く処理されないだろうか？
++
++現状、1, 2 とも実施してみたところ特に速度の改善は見られなかった。特に 
++1 は、微妙なところがありほとんどの書き換えは性能を悪くするだけだった。
++なかなか興味深いものがある。
++
++これは今後の課題としていずれまた検証しよう。そろそろ slide.c も飽きて
++きたのでひとまずはこれで終りにしたい。
++
++
++bit 入出力ルーチン (crcio.c)
++---------------------------
++
++これから Huffman 法の解読に移るのだが、その前準備として bit 入出力ルー
++チンの解読を行う。Huffman 法の実装では必ず bit 入出力処理が必要になる。
++LHa for UNIX ももちろん例外ではなく、Huffman 法の実装を解読するにあた
++りこの部分の処理内容ははっきりさせておいた方が良いと考えたのだ。
++
++LHa for UNIX version 1.14i では bit 入出力ルーチンは crcio.c で定義さ
++れている。(このようなファイル名に存在するのは意外な事だ。最近の LHa
++for UNIX では、私が bitio.c というファイルを設け、bit 入出力ルーチンは
++そこに切り出した)
++
++crcio.c のうち bit 入出力ルーチンは fillbuf(), getbits(), putcode(),
++putbits(), init_getbits(), init_putbits() の 6 関数だ。
++
++まず、初期化用の init_getbits(), init_putbits() を見よう。
++
++void
++init_getbits( /* void */ )
++{
++    bitbuf = 0;
++    subbitbuf = 0;
++    bitcount = 0;
++    fillbuf(2 * CHAR_BIT);
++#ifdef EUC
++    putc_euc_cache = EOF;
++#endif
++}
++
++void
++init_putbits( /* void */ )
++{
++    bitcount = CHAR_BIT;
++    subbitbuf = 0;
++    getc_euc_cache = EOF;
++}
++
++それぞれ bit 入力、bit 出力を行うための初期化処理だ。CHAR_BIT というの
++は 8 で、char の bit サイズを表しているらしい。詳細はわからないが初期
++状態はとにかくこれだ。ここで使用されている変数は、
++
++static unsigned char subbitbuf, bitcount;
++
++が、crcio.c で定義されており、
++
++EXTERN unsigned short bitbuf;
++
++が、lha.h で定義されている(EUC なんたらは本質ではない無視しよう)。グロー
++バル変数と言うのは忌むべきものだが、とにかく使用されている変数と初期値
++を確認したので次に移ろう。init_getbits() で、早速 fillbuf() が呼ばれて
++いる。この処理内容を見る。
++
++void
++fillbuf(n)          /* Shift bitbuf n bits left, read n bits */
++    unsigned char   n;
++{
++    /* (A) */
++    while (n > bitcount) {
++        n -= bitcount;
++        /* (B) */
++        bitbuf = (bitbuf << bitcount) + (subbitbuf >> (CHAR_BIT - bitcount));
++        /* (C) */
++        if (compsize != 0) {
++            compsize--;
++            subbitbuf = (unsigned char) getc(infile);
++        }
++        else
++            subbitbuf = 0;
++        bitcount = CHAR_BIT;
++    }
++    /* (D) */
++    bitcount -= n;
++    bitbuf = (bitbuf << n) + (subbitbuf >> (CHAR_BIT - n));
++    subbitbuf <<= n;
++}
++
++まず、初期状態として
++
++    bitbuf = 0;
++    subbitbuf = 0;
++    bitcount = 0;
++
++であり、fillbuf の引数 n には 2 * CHAR_BIT が与えられたのだった。いき
++なり while 条件を満たすのでループ部の解析を行わなくてはならなくなるが、
++ひとまずこれを無視して最後の 3 行 (D) に着目する。条件は少ない方が良い
++のだ。
++
++    /* (D) */
++    bitcount -= n;
++    bitbuf = (bitbuf << n) + (subbitbuf >> (CHAR_BIT - n));
++    subbitbuf <<= n;
++
++bitbuf << n, subbitbuf << n されているので、bitbuf, subbitbuf を n ビッ
++ト左にずらす処理のようだ。さらに bitbuf には、subbitbuf を n ビットず
++らしたときに溢れた部分を bitbuf にセットしている。っと、
++
++   (subbitbuf >> (CHAR_BIT - n))
++
++の部分を軽く説明したが、図示して確認しておこう。
++
++subbitbuf は unsigned char なので 8 bit の変数だ。
++
++----------------------------------------------------------------------------
++               7  6  5  4  3  2  1  0
++              +--+--+--+--+--+--+--+--+
++   subbitbuf  |                       |
++              +--+--+--+--+--+--+--+--+
++              <-- n -->
++----------------------------------------------------------------------------
++
++n が例えば 3 の場合、CHAR_BIT - n は、5 だから subbitbuf を 5 ビット右
++にずらした値を取っている。つまり、図の 7, 6, 5 ビット目が一番右に来る
++ようになっており、この値を bitbuf に足している。(C言語では、unsigned 
++な変数を右にシフトすると上位ビットには 0 が入る)
++
++fillbuf() の後半 3 行(いや、後半2行か)は。結局 bitbuf と subbitbuf を
++一つの bitbuf とみなして n ビット左にずらしていることがわかる。
++
++----------------------------------------------------------------------------
++<ビットバッファ全体図 (予想)>
++
++           7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
++          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++  bitbuf  |                             |          x  y  z|
++          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++                                         \        <-- n  ->
++                                         subbitbuf
++           <-------------- bitcount ------------->
++
++----------------------------------------------------------------------------
++
++このとき、当然図の x, y, z の部分(n = 3 は例としての値だ)が空く事になる。
++bitcount という変数が n 引かれていたが、これは bit バッファ全体の有効
++なビット数を表しているのではないかと予想しておく。すなわち図の状態なら
++21 だ。while ループは(関数名から)この空き部分を埋める処理なのではない
++かと適当に予想できる。では、while ループを見よう。もう一度初期値を確認
++し、最初に行われる処理内容を見よう。
++
++最初、
++
++    bitbuf = 0;
++    subbitbuf = 0;
++    bitcount = 0;
++
++であるから、bitバッファは空っぽだ。当然 fillbuf(2 * CHAR_BIT) されると
++while 条件を満たす。きっと 16 bit だけ bitバッファが補充されるはず(つ
++まり、bitbuf いっぱい、subbitbuf 空)だ。
++
++    /* (A) */
++    while (n > bitcount) {
++        n -= bitcount;
++
++で、ビットバッファが保持する bit 数以上を要求されたので、ループに入る。
++n -= bitcount で、本当に足りない部分が何ビットなのかを得ている。ここで
++は 16 だ。次の行
++
++        /* (B) */
++        bitbuf = (bitbuf << bitcount) + (subbitbuf >> (CHAR_BIT - bitcount));
++
++これは先程も出て来た処理だ。ビットバッファ全体を bitcount 分左にずらし
++ている(ただし、まだ subbitbuf はずらされていない)。この時点で予想が少
++し覆された。8 - bitcount で subbitbuf をずらしているから bitcount は最
++大 8 の値しか持たないだろうということだ。どういうことか、考えてみる・・・
++考えてもわからなかったので次に進もう。
++
++        /* (C) */
++        if (compsize != 0) {
++            compsize--;
++            subbitbuf = (unsigned char) getc(infile);
++        }
++        else
++            subbitbuf = 0;
++        bitcount = CHAR_BIT;
++
++compsize というのが出て来たが、この値がどうあろうとも subbitbuf は8 ビッ
++ト埋められ。bitcount は 8 に設定されている。わかった bitcount は、
++subbitbuf に保持する bit 数だ。図を訂正しよう。
++
++----------------------------------------------------------------------------
++<ビットバッファ全体図>
++
++           7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
++          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++  bitbuf  |                             |            x y z|
++          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++                                       /          <-- n  ->
++                                   subbitbuf
++                                        <-------->
++                                         bitcount
++
++----------------------------------------------------------------------------
++
++この図を踏まえてもう一度初期状態での処理内容を追いかける。
++
++まず、(A) で、subbitbuf は空なので、bitcount は 0 だ。要求した bit 数 
++n{16} より小さいのでループに入る。n は 16 のままだ。
++
++(B) で、subbitbuf に残っている bit を bitbuf にずらしている。今はまだ
++空なのでbitbuf はここでもまだ空だ。
++
++(C) で、8 ビットファイルからデータを読む(compsize は常に0でないと考え
++る)。bitcount は 8 になる。この時点で bitバッファ全体は subbitbuf だけ
++値が入った状態になる。
++
++次のループに移ろう。(A) で、subbitbuf はいっぱいであるが要求した n{16} 
++よりは小さいので、まだループは続く。n はここで 8 になる。
++
++(B) で、subbitbuf に残っている bit (8 bit だ)を bitbuf にずらしている。
++今度は subbitbuf 全体が bitbuf に移っているのと同じだ。(つまり、bitbuf
++= subbitbuf)
++
++(C) で、また subbitbuf は 8 bit 補充される。
++
++(A) で、n{8} > bitcount{8} は偽なのでループが終る。
++
++(D) で、subbitbuf に残っている bit はすべて bitbuf に移る。bitbuf は 16
++bit いっぱいになる。bitcount は 0 だ。
++
++この処理結果から fillbuf(n) は、bitbuf に n ビット読み込む処理だと言え
++る。引数に指定できる n が最大 16 ビットであることにも気づいて良いだろ
++う。処理内容を確認してみればわかる。
++
++ここで、subbitbuf の用途に気づいた。ファイルからの読み込みが 8 ビット
++単位でしかできないので、それを補うための先読みバッファであろう。例えば
++1 ビットだけ bitbuf を fill したければ subbitbuf に 7 bit 残し、1 bit
++だけ bitbuf に設定される(確認してみればわかる)
++
++fillbuf() がわかったので、それを利用している getbits() の内容を確認し
++よう。
++
++unsigned short
++getbits(n)
++    unsigned char   n;
++{
++    unsigned short  x;
++
++    x = bitbuf >> (2 * CHAR_BIT - n);
++    fillbuf(n);
++    return x;
++}
++
++    x = bitbuf >> (2 * CHAR_BIT - n);
++
++は、3 度も出て来たので
++
++     buf >> (sizeof(buf)*8 - n)
++
++を buf の上位 n ビットを得る式だとしてマクロにしても良いだろう。(が、
++良い名前が思い付かないのでそうはしない)。とにかく、bitbuf の上位 n ビット
++を下位 n ビットとして x に代入している。その後で、
++
++    fillbuf(n);
++
++している。n bit を x に渡したので bitbuf から上位 n ビットを捨てて、n 
++ビット補充する。ここで、bitbuf は常にいっぱいの状態になっていることが
++わかる。(ファイルの末尾付近の場合、正確に bitbuf に何ビット残っている
++かが判断できないが、種明かしをするとこのことは LHa の処理内容にとって
++はどうでもいいことだ。getbits() は decode 処理で使われるのだが、decode 
++処理は何ビットの情報を decode する必要があるかを他の情報からあらかじめ
++得ている)
++
++次に移ろう今度は putcode() だ。put の場合まずは、init_putbits() で
++初期化が行われている。その値は以下だ。
++
++    bitcount = CHAR_BIT;
++    subbitbuf = 0;
++    getc_euc_cache = EOF;
++
++getc_euc_cache は無視だ。bitcount と subbitbuf の値が設定され、bitbuf 
++は利用されない。先程とは違い subbitbuf が空なのにbitcount が 8 なので、
++bitcount の使われ方が多少異なるようだ。get の場合は、bitcount は、
++subbitbuf に保持する bit 数だったが今度は subbitbuf の空き bit 数だろ
++うと予想しておこう。
++
++そして、putcode(n, x) を見る。実はソースを見るとわかるのだが、もう一つ
++の出力ルーチン putbits() は、putcode() の呼び出しに書き換え可能だ。
++putbits() は、
++
++void
++putbits(n, x)           /* Write rightmost n bits of x */
++    unsigned char   n;
++    unsigned short  x;
++{
++    x <<= USHRT_BIT - n;
++    putcode(n, x);
++}
++
++っと書き換えられるのだ。なので、putcode() の内容を先に確認するわけだ。
++
++void
++putcode(n, x)           /* Write rightmost n bits of x */
++    unsigned char   n;
++    unsigned short  x;
++{
++    /* (A) */
++    while (n >= bitcount) {
++        n -= bitcount;
++        /* (B) */
++        subbitbuf += x >> (USHRT_BIT - bitcount);
++        x <<= bitcount;
++        /* (C) */
++        if (compsize < origsize) {
++            if (fwrite(&subbitbuf, 1, 1, outfile) == 0) {
++                /* fileerror(WTERR, outfile); */
++                fatal_error("Write error in crcio.c(putcode)\n");
++                /* exit(errno); */
++            }
++            compsize++;
++        }
++        else
++            unpackable = 1;
++        subbitbuf = 0;
++        bitcount = CHAR_BIT;
++    }
++    /* (D) */
++    subbitbuf += x >> (USHRT_BIT - bitcount);
++    bitcount -= n;
++}
++
++処理内容が fillbuf() のときと似ている。まずは、先程と同様に while 条件
++を無視して考えてみる。(D) だ。
++
++    /* (D) */
++    subbitbuf += x >> (USHRT_BIT - bitcount);
++    bitcount -= n;
++
++この式はもう 4 度目だ。まず、x の上位 bitcount ビットを得て、subbitbuf 
++に足している。bitcount は、先程 subbitbuf の空きであろうと予想したが、
++n 引かれているので、埋めた分空きが減っているわけだ。予想は当たっている
++だろう。この時点でこの関数が x の上位ビットを利用することがわかる。コ
++メントに rightmost n bits of x と書かれているが惑わされてはいけない。
++多くの場合、コメントはせいぜいヒントとしての情報でしかない。信用しては
++いけないものなのだ。(コメントはあまりデバッグされない。コメントが詳し
++ければ詳しい程コメントはエンバグしやすい。疑ってかかろう。これは本書に
++も言える。すべてを鵜のみにしてはいけないのだ)
++
++では、処理内容に移る。まずは (A)
++
++    /* (A) */
++    while (n >= bitcount) {
++        n -= bitcount;
++
++subbitbuf の空きが n 以下であればループに入る。subbitbuf 一つではn ビッ
++ト全部は賄えないからループで小刻みに処理しようということだろう(もう全
++体の処理内容の予想はついている)
++n から bitcount 引いているので、n ビットのうちこれから bitcount 分は
++処理されることをここでさっさと記録して次のループに備えている。
++
++        /* (B) */
++        subbitbuf += x >> (USHRT_BIT - bitcount);
++        x <<= bitcount;
++
++x の上位 bitcount ビットを subbitbuf に足している。subbitbuf の空きが
++これで埋まった。subbitbuf はもういっぱいだ。x を bitcount シフトするこ
++とで subbitbuf に渡した x の上位ビットを捨てている。
++
++        /* (C) */
++        if (compsize < origsize) {
++            if (fwrite(&subbitbuf, 1, 1, outfile) == 0) {
++                /* fileerror(WTERR, outfile); */
++                fatal_error("Write error in crcio.c(putcode)\n");
++                /* exit(errno); */
++            }
++            compsize++;
++        }
++        else
++            unpackable = 1;
++        subbitbuf = 0;
++        bitcount = CHAR_BIT;
++
++compsize は無視しても良い。処理の本質ではないからだが、すぐにわかるので
++一応説明すると、
++        if (compsize < origsize) {
++            ...
++        else
++            unpackable = 1;
++で、圧縮ファイルサイズが元のファイルサイズを上回ったときに
++処理を終るようになっている(unpackable = 1 して、他の箇所でこの変数を監視する。
++unpackable == 1 なら処理を中断する)
++
++とにかく (C) の時点では必ず subbitbuf がいっぱいになるので 1 バイトを
++ファイルに書き出している。その後、subbitbuf = 0, bitcount = 8 として 
++subbitbuf を空けて次のループに備えている。
++
++もういいだろう。putcode() は、論理的には x のうち上位 n ビットを出力す
++る処理だ。引数 n の上限が x の最大ビットサイズ 16 になるのは説明するま
++でもないだろう。
++
++putcode() は実装として、subbitbuf と x を一つに繋げて n bit 左にずらし
++ている処理だと考えても良い。そうして、subbitbuf がいっぱいになったらそ
++の都度(1 バイトずつ)ファイルに書き出すのだ。
++
++----------------------------------------------------------------------------
++<ビットバッファ全体図>
++
++                      <--- 左にずらす
++
++           7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
++          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++          |* * *          |x y z                          |
++          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++         /               / <-n->        
++      subbitbuf         x
++                 <-------->
++                  bitcount
++
++----------------------------------------------------------------------------
++
++putbits() も見よう。先程 putcode() の呼び出しに書き換えたコードを見ると
++すぐわかるが、
++
++    x <<= USHRT_BIT - n;
++    putcode(n, x);
++
++最初の式で、x の下位 n ビットを x の上位 n ビットにしている。
++そうして、putcode() を呼び出しているので、putbits(n, x) は、x
++の下位 n ビットを出力する処理だ。
++
++以上でビット入出力ルーチンは終りだ。出力に関して一つ捕捉しておくと
++putcode(), putbits() では最後の最後で subbitbuf に情報が残ったままファ
++イルに書き出されない状態になる。これを吐き出すために利用者は
++
++  putcode(7, 0)
++
++を行う必要がある。
++
++まとめよう
++
++----------------------------------------------------------------------------
++fillbuf(n)
++  bitbuf から上位 n ビットを捨てて、下位 n ビットをファイルから読み込
++  み埋める。
++
++getbits(n)
++  bitbuf の上位 n ビットを下位 n ビットとして返す。bitbuf は n ビット
++  補充される。
++
++putcode(n, x)
++  x の上位 n ビットをファイルに出力する。最後の出力時は putcode(7, 0)
++  する必要がある。
++
++putbits(n, x)
++  x の下位 n ビットをファイルに出力する。最後の出力時は putcode(7, 0)
++  する必要がある。
++
++init_getbits()
++  入力処理の初期化
++
++init_putbits()
++  出力処理の初期化
++----------------------------------------------------------------------------
++
++読み込みに関して、bitbuf のサイズが 16 ビットで常にその状態が保持され
++ているのは LHa にとって重要な事だ。decode 処理では直接 bitbuf を参照す
++る箇所がある。
++
++Huffman 法 (huf.c)
++------------------
++
++LHa for UNIX では、静的 Huffman 法として、shuf.c、動的 Huffman 法とし
++て dhuf.c があるらしいが、これらに関しては触れない。LHa では、これらは
++過去の版のアーカイブを解凍できるように decode のみサポートしているよう
++だ。そこで、まずは -lh4-, -lh5-, -lh6-, -lh7- で利用されている huf.c 
++の解析を中心に行うこととしたい。
++
++ところで、本書では Huffman 法がどういったものかは予備知識として既に知っ
++ているものとするが、いちおう概要を簡単に説明しておこう。
++
++以下の内容のテキストファイルがあったとする。
++
++        abcabcaba
++
++このテキストは 9 バイトあるわけだが、このファイルで使われている文字は3 
++種類しかない、a, b, c だ。だからこのファイルだけに関して言えば 1 文字
++は 2 ビットあれば表現可能である(このファイルの場合全体で、18ビットあれ
++ば表現可能)。さらに、出現頻度の高い文字を少ないビット数で表現し、まれ
++にしか現れない文字を長いビット数で表すようにすればよりビット数を少なく
++できる。例えば
++
++        文字   ビット表現
++        a      0
++        b      10
++        c      11
++
++であるとすると a は 4回、bは3回、cは2回現れるので、全体は 4 + 2*3 +
++2*2 = 14 ビットで表現できることになる。これが Huffman 法の圧縮原理であ
++る。このように Huffman 法では文字をビット単位で扱うためビット入出力ルー
++チンを先に解読したわけだ。また、符号化の際はあらかじめ各文字の出現頻度
++を求めておく必要があり、復号化の際はどのビット列がどの文字に対応するか
++をあらかじめ知る必要がある。
++
++では、符号化の際に文字に対応するビット列を求める方法だが、以下がそのア
++ルゴリズムだ。ハフマン法ではハフマン木という木構造を構築する。各文字の
++出現回数
++
++        a:4、b:3、c:2
++
++から、出現回数の低いもの同士を一つの節に束ねる。この節は 3+2=5 という
++出現回数を持つものと考える。
++
++          5
++         / \
++        b   c
++
++以降さらに出現回数の低いもの同士を一つの節に束ねる操作を繰り返す。この
++例では、もう一度束ねれば終りだ。
++
++       /\
++      /  \
++     /  / \
++    a  b   c
++
++ここで、木の左側が 0 右側が 1 であるとすると。a は根から左に1つ進むだ
++けなので 0。b は、右(1)→左(0) なので、10。c は右(1)→右(1) なので、11 
++となる。実際の符号化の際は文字からビット列を求めるので葉から根にむかっ
++て逆順に辿ることになる。また、復号の際は入力のビット列に沿ってこの木を
++辿ることで対応する文字を求める(なので圧縮文にはこの木構造が一緒に情報
++として格納されることになる)。
++
++このようなハフマン木を作成する箇所があるかどうかを探してみたところ 
++maketree.c:make_tree() が見つかった。これは「C言語による最新アルゴリズ
++ム辞典」(奥村晴彦著、技術評論社)に載っているものとほとんど同じだ。では、
++この関数の解読から始めよう(今回の解析はボトムアップ式に行うことにしよ
++うと思う。というのもデータ構造から攻めようにもグローバル変数がたくさん
++出て来るし、処理順に追っても正直よくわからなかったからだ)
++
++この関数のあるファイル maketree.c で使用しているデータ構造は以下だ。
++
++static short    n, heapsize, heap[NC + 1];
++static unsigned short *freq, *sort;
++static unsigned char *len;
++static unsigned short len_cnt[17];
++
++make_tree() は以下。
++
++short
++make_tree(nparm, freqparm, lenparm, codeparm)
++/* make tree, calculate len[], return root */
++    int             nparm;
++    unsigned short  freqparm[];
++    unsigned char   lenparm[];
++    unsigned short  codeparm[];
++{
++    short           i, j, k, avail;
++
++    /* (A) */
++    n = nparm;
++    freq = freqparm;
++    len = lenparm;
++    avail = n;
++    /* (B) */
++    heapsize = 0;
++    heap[1] = 0;
++    for (i = 0; i < n; i++) {
++        len[i] = 0;
++        if (freq[i])
++            heap[++heapsize] = i;
++    }
++    /* (C) */
++    if (heapsize < 2) {
++        codeparm[heap[1]] = 0;
++        return heap[1];
++    }
++    /* (D) */
++    for (i = heapsize / 2; i >= 1; i--)
++        downheap(i);    /* make priority queue */
++    /* (E) */
++    sort = codeparm;
++    do {            /* while queue has at least two entries */
++        i = heap[1];    /* take out least-freq entry */
++        if (i < n)
++            *sort++ = i;
++        heap[1] = heap[heapsize--];
++        downheap(1);
++        j = heap[1];    /* next least-freq entry */
++        if (j < n)
++            *sort++ = j;
++        k = avail++;    /* generate new node */
++        freq[k] = freq[i] + freq[j];
++        heap[1] = k;
++        downheap(1);    /* put into queue */
++        left[k] = i;
++        right[k] = j;
++    } while (heapsize > 1);
++    /* (F) */
++    sort = codeparm;
++    make_len(k);
++    make_code(nparm, lenparm, codeparm);
++    return k;       /* return root */
++}
++
++この関数の引数に、nparm, freqparm, lenparm, codeparm というのがある。
++これがなんなのかいきなりではわからないだろう。実は私にもわからない。今
++回の解析で特殊なのは、処理内容については私は(アルゴリズム辞典で)知って
++いることだ。強引に無視しても処理内容から想像がつくだろうことを期待して
++いる。
++
++とりあえず、冒頭の初期化部分 (A) で
++
++    /* (A) */
++    n = nparm;
++    freq = freqparm;
++    len = lenparm;
++    avail = n;
++
++としている。引数で受けた入力をこのファイルの static 変数にセットし、他
++のルーチンとデータ共有しているようだ。avail は後で説明しよう。
++
++    /* (B) */
++    heapsize = 0;
++    heap[1] = 0;
++    for (i = 0; i < n; i++) {
++        len[i] = 0;
++        if (freq[i])
++            heap[++heapsize] = i;
++    }
++
++ここで、heap[] を初期化している。heapsize は、heap の要素数となる。こ
++の処理は優先待ち行列 heap[] を作る部分なのだが、なぜ優先待ち行列が必要
++なのかというと先の説明で Huffman 法のアルゴリズムに出現回数の少ない順
++に葉を節に束ねるという部分があった。優先待ち行列はこのためのものだ。と
++りあえず、heap[] の要素は圧縮する文字であるということだけを書いておく。
++詳細はすぐ後で出るだろう。freq[i] (すなわち引数 freqparm) は、文字 i 
++の出現回数を表している。だから、n (nparm)は、符号化するモデル上の文字
++の種類の数を表していることになる。たとえば通常のファイルなら nparm は 
++256 だろう。まあ、結局は freq[] の要素数だ。
++
++    nparm               最大要素数
++    freqparm[0:nparm]   添字が文字で、その要素が出現回数
++
++注意すべきなのは heap[] の要素は 1 以降を使用していることだろう。
++heap[0] は使われない。
++
++    /* (C) */
++    if (heapsize < 2) {
++        codeparm[heap[1]] = 0;
++        return heap[1];
++    }
++
++これは、heapsize が 0 か 1 の場合を表している。符号化する文字の種類が 
++0 または 1 つしかない場合だ。heap[1] は、(B) で 0 に初期化していたので、
++codeparm[0] = 0 として、0 を返している。これは特殊な条件を示している。
++簡単に想像がつくことだが、出現する文字の種類が1種類しかない場合、ハフ
++マン木を作る必要がない。LHa ではこのような場合に特殊な構造あるいは方法
++を用いていることが想像できる。
++
++    /* (D) */
++    for (i = heapsize / 2; i >= 1; i--)
++        downheap(i);    /* make priority queue */
++
++優先待ち行列 heap[] を構築する。downheap() がなんなのか、これがどういっ
++た処理なのかの詳細は省略しよう。アルゴリズム辞典の「ヒープソート」の項
++に詳しいが、heap[] は木構造を示しており、この木構造(2分木)には「親は子
++より優先順位が同じか高い」という規則だけがある。この木構造は、
++
++        1. heap[n] の左の子は heap[2*n]、右の子は heap[2*n + 1]
++
++で、表現されており、このような半順序木 (partial ordered tree) には、以
++下の特徴がある
++
++        2. heap[n] の親は heap[n/2]
++        3. heap[1.. heapsize/2] は節で、heap[heapsize/2 .. heapsize] は葉
++
++この heap[] が最初ばらばらに要素が格納されているとき、葉に近い節から順
++に downheap() という操作を行う((D)の処理)と、ヒープを構築できるように
++なっている。downheap(i) は、節 heap[i] とその子 heap[2*i], heap[2*i+1] 
++で要素を比較し、子の優先順位の方が高ければ位置を交換する、という処理を
++葉に向かって繰り返す関数だ。以下、参考までに maketree.c:downheap() の
++内容を示す。
++
++static void
++downheap(i)
++/* priority queue; send i-th entry down heap */
++    int             i;
++{
++    short           j, k;
++
++    k = heap[i];
++    while ((j = 2 * i) <= heapsize) {
++        if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
++            j++;
++        if (freq[k] <= freq[heap[j]])
++            break;
++        heap[i] = heap[j];
++        i = j;
++    }
++    heap[i] = k;
++}
++
++とにかく (D) により、最も優先順位の高い(出現回数の少ない)要素が 
++heap[1] に来るようになる。この優先待ち行列はなかなか面白い(と私は思っ
++た)のでいろいろと調べてみるのもよいだろう。
++
++さて、続けよう (E) だ。
++
++    /* (E) */
++    sort = codeparm;
++    do {            /* while queue has at least two entries */
++        i = heap[1];    /* take out least-freq entry */
++        if (i < n)
++            *sort++ = i;
++        heap[1] = heap[heapsize--];
++        downheap(1);
++        j = heap[1];    /* next least-freq entry */
++        if (j < n)
++            *sort++ = j;
++        k = avail++;    /* generate new node */
++        freq[k] = freq[i] + freq[j];
++        heap[1] = k;
++        downheap(1);    /* put into queue */
++        left[k] = i;
++        right[k] = j;
++    } while (heapsize > 1);
++
++最初に、
++
++        i = heap[1];    /* take out least-freq entry */
++        if (i < n)
++            *sort++ = i;
++
++で、最も出現回数の少ない文字を取って来る。if の部分はひとまず無視しよう。
++
++        heap[1] = heap[heapsize--];
++        downheap(1);
++
++で、heap[] の最後尾の要素を先頭に持って来て downheap(1) を行っている。
++こうすると、ヒープが再構築され「親は子より優先順位が同じか高い」という
++条件をまた満たすようになる。heap[] の要素は1つ減っている。結局、ここま
++での処理は論理的には「優先待ち行列から優先度の高い要素を1つ取り出す」
++と言う処理だ。
++
++        j = heap[1];    /* next least-freq entry */
++        if (j < n)
++            *sort++ = j;
++
++続けて、2番目に優先度の高い要素を取り出す。また、if は無視しておこう。
++
++        k = avail++;    /* generate new node */
++        freq[k] = freq[i] + freq[j];
++        heap[1] = k;
++        downheap(1);    /* put into queue */
++
++avail は最初 n (nparm)だった。freq[] は、文字の出現回数なので最初文字
++の種類数分(nparm)の要素しかないがハフマン木の節の出現回数(というか優先
++順位)を格納するために freq[] は、nparm * 2 - 1 の格納域が必要となるこ
++とがわかる。(葉が n 個ある 2 分木には、節が n - 1 個ある)
++
++----------------------------------------------------------------------------
++
++     +-----------------------+-----------------------+
++freq |                       |                       |
++     +-----------------------+-----------------------+
++     0                       nparm                   nparm * 2 - 1
++
++     |-----------------------|-----------------------|
++      文字(ハフマン木の葉)    ハフマン木の節の優先順位
++      の優先順位
++
++
++      例:
++                 .     ... freq[4]
++                / \
++               .   \   ... freq[3]
++              /\    \
++             a  b    c ... freq[0 .. 2]
++
++----------------------------------------------------------------------------
++
++ここまでで、出現回数の低い2つの要素を取り出しその出現回数の和を 
++freq[k] に設定することになる。出現回数の和は heap[] に再設定され、
++downheap(1) で、優先待ち行列をまた再構築する。これは「葉を束ね節を作る」
++というハフマン木の構築アルゴリズムの実装だ。新しく作成した節が k でそ
++の最大値が最終的に avail-1 である。
++
++最後に
++
++        left[k] = i;
++        right[k] = j;
++
++で、ハフマン木を構造 left[]、right[] で作成する。
++
++この (E) を抽象度の高いコードで示してみよう。ハフマン木は
++    struct huffman {
++       ...
++    } huff;
++
++で表し、ハフマン木の1つの節は、
++    make_huff(huff, node, left, right)
++で作成できるとする。また、優先順位つき待ち行列を heap とし、heap から
++要素を取り出す処理、要素を格納する処理をそれぞれ仮に
++        n = delete_pqueue(heap)
++        insert_pqueue(heap, n)
++とすると、
++
++    /* (E) */
++    do {
++        left = delete_pqueue(heap);
++        right = delete_pqueue(heap);
++
++        node = avail++;
++        freq[node] = freq[left] + freq[right];
++
++        insert_pqueue(heap, freq[node]);
++
++        make_huff(&huff, node, left, right);
++    } while (heapsize > 1);
++
++こんなところだろうか。元の処理ではヒープからの要素の取り出しと挿入で無
++駄な処理を無くすために少し複雑になっている。(そしてデータ構造に依存し
++た処理になっている)。どちらがよりすぐれているかは微妙な所だ。私は多少
++の処理の無駄も目をつぶってよりわかりやすい方を優先するのが好きなのだが。
++これはちょっと考えさせられるところだ。
++
++ループを抜けた所で k (avail - 1) は、ハフマン木の根を表している。
++left[0:avail], right[0:avail] でハフマン木を表し、そのうち
++left[nparm...avail], right[nparm...avail] が節の子を示している。
++left[0...nparm], right[0...nparm] は使われないようだ。
++
++----------------------------------------------------------------------------
++      例:
++                 . -- k (= avail-1)
++                / \
++   left[k] --  .   \ 
++              /\    \
++             a  b    c -- right[k]
++             |   \
++             |    right[left[k]]
++          left[left[k]]
++
++----------------------------------------------------------------------------
++
++これで、ハフマン木の構築は終りなのだが、ハフマン法の符号化ではハフマン
++木の葉から根に向かって木を辿る必要があるはずなのに、left[]、right[] の
++構造では根から葉に向かってしか木を辿ることができないはずだ。これはどう
++いうことだろう？make_tree() ではまだ処理が続いている。
++
++    /* (F) */
++    sort = codeparm;
++    make_len(k);
++    make_code(nparm, lenparm, codeparm);
++    return k;       /* return root */
++
++どうやら、木構造の他にもなにやら構造を作成しているようだ。これは先程無
++視した if 文にも関連する。そしてこれは「アルゴリズム辞典」には載ってい
++ない部分だ。どうやら LHa なりの工夫があるようだ。
++
++まず、maketree.c:make_len(root) から見てみようと思うが、その前にこの関
++数は maketree.c:count_len(root) という関数を呼び出している。こちらから
++先に見ることにした。
++
++static void
++count_len(i)            /* call with i = root */
++    int             i;
++{
++    static unsigned char depth = 0;
++
++    if (i < n)
++        len_cnt[depth < 16 ? depth : 16]++;
++    else {
++        depth++;
++        count_len(left[i]);
++        count_len(right[i]);
++        depth--;
++    }
++}
++
++この関数に渡される i は、最初ハフマン木の根を指す値だ。この関数の全体
++を見れば、i が節や葉を示すことはすぐわかる。最初の if 文に出てくる n 
++は何かというとなんとこのファイル内の static 変数で、make_tree() の冒頭
++で nparm で初期化していた。先程は気にもとめなかったのだが、変数名の選
++び方がどうにもよろしくない。とにかく n は、nparm で、freqparm の最初の
++要素数で、文字の種類の数を表していたものだ。ここではハフマン木の節や葉
++となる i と比較していることから、i がハフマン木の節を示すか葉を示すか
++の判断に使用しているらしい。if 文の条件が真の場合(i < n)、i は葉である。
++偽の場合 i は節である。偽の場合は、depth を足して二つの子に対して再帰
++的にこの関数を呼び出している。で、結局この関数が何をしているかというと、
++先ほど構築したハフマン木に関して、ある深さの葉の数を数えているようだ。
++
++len_cnt[1] は、深さ 1 (根の子)の葉の数で 0 〜 2 の値になる。len_cnt[2] 
++は、深さ 2 (根の孫)の葉の数で 0 〜 4 の値を持つだろう。そして、深さ 16 
++以上の層に関しては len_cnt[16] にすべて計上されるようだ。とにかくその
++ような処理だということでこの関数を終え、make_len() を見よう。
++
++static void
++make_len(root)
++    int             root;
++{
++    int             i, k;
++    unsigned int    cum;
++
++    /* (A) */
++    for (i = 0; i <= 16; i++)
++        len_cnt[i] = 0;
++    count_len(root);
++    /* (B) */
++    cum = 0;
++    for (i = 16; i > 0; i--) {
++        cum += len_cnt[i] << (16 - i);
++    }
++#if (UINT_MAX != 0xffff)
++    cum &= 0xffff;
++#endif
++    /* (C) */
++    /* adjust len */
++    if (cum) {
++        fprintf(stderr, "17");
++        len_cnt[16] -= cum; /* always len_cnt[16] > cum */
++        do {
++            for (i = 15; i > 0; i--) {
++                if (len_cnt[i]) {
++                    len_cnt[i]--;
++                    len_cnt[i + 1] += 2;
++                    break;
++                }
++            }
++        } while (--cum);
++    }
++    /* (D) */
++    /* make len */
++    for (i = 16; i > 0; i--) {
++        k = len_cnt[i];
++        while (k > 0) {
++            len[*sort++] = i;
++            k--;
++        }
++    }
++}
++
++ちょっと複雑だがゆっくり見ていこう。まず (A) の初期化部分は先ほどの 
++count_len() を呼び出すだけのものなのでもうよいだろう。
++
++    /* (A) */
++    for (i = 0; i <= 16; i++)
++        len_cnt[i] = 0;
++    count_len(root);
++
++これで、len_cnt[0:16] にはハフマン木の各層の葉の数が計上される。続いて (B)
++
++    /* (B) */
++    cum = 0;
++    for (i = 16; i > 0; i--) {
++        cum += len_cnt[i] << (16 - i);
++    }
++#if (UINT_MAX != 0xffff)
++    cum &= 0xffff;
++#endif
++
++これは、どういうことだろう？len_cnt[] は short の配列だが、とにかく以
++下のような計算(len_cnt[] の要素を 1 ビットずらしながら足す)をしている。
++最後に int 型のサイズが 2 でない場合 0xffff で論理積をしているので 2バ
++イトの符号なし整数を結果として欲しいらしい。
++
++----------------------------------------------------------------------------
++                f e d c b a 9 8 7 6 5 4 3 2 1 0  bit
++  len_cnt[16]  |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|   (下位 16ビット)
+++ len_cnt[15]  |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|0|   (下位 15ビット)
+++ len_cnt[14]  |x|x|x|x|x|x|x|x|x|x|x|x|x|x|0|0|   (下位 14ビット)
+++     :                                                   :
+++ len_cnt[ 2]  |x|x|0|0|0|0|0|0|0|0|0|0|0|0|0|0|   (下位 2 ビット)
+++ len_cnt[ 1]  |x|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|   (下位 1 ビット)
++& 0xffff       |1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|
++------------------------------------------------
++= cum           x x x x x x x x x x x x x x x x
++----------------------------------------------------------------------------
++
++ここで、len_cnt[] の各要素の値が各層の葉の数であることを考えると、各要
++素で使用するビット数との関連が見える。
++
++              取り得る
++              値の範囲      使用ビット数
++ -----------------------------------------
++ len_cnt[16]  0.. 2^16以上  17ビット以上
++ len_cnt[15]  0.. 2^15      16ビット
++ len_cnt[14]  0.. 2^14      15ビット
++     :                  
++ len_cnt[ 3]  0.. 2^3        4 ビット
++ len_cnt[ 2]  0.. 2^2        3 ビット
++ len_cnt[ 1]  0.. 2^1        2 ビット
++
++先の計算式では len_cnt[] の各要素で使用し得るビット数から 1 引いたビッ
++ト数が計算に使用されている。例えば根の子がすべて葉なら len_cnt[1] は、
++2 になり、2進で、00000000 00000010 だが、cum の計算にはこの下位 1 ビッ
++トしか使用されない。
++
++       /\
++      a  b     .. len_cnt[1] = 00000000 00000010
++                                               |
++                                               v
++                                         cum = x0000000 00000000
++
++根の孫がすべて葉なら len_cnt[2] は、4 になり、2進で、00000000 00000100 
++だが、cum の計算にはこの下位 2 ビットしか使用されない。
++
++       / \     .. len_cnt[1] = 00000000 00000000
++      /\ /\
++     a b c d   .. len_cnt[2] =  00000000 00000100
++                                               ||
++                                               vv
++                                         cum = xx000000 00000000
++
++このようにある層のすべてが葉であるようなバランスのよいハフマン木に
++対しては先の計算結果 cum は 0 になるらしい。
++
++また、
++       /\
++      a /\     .. len_cnt[1] = 00000000 00000001
++        b c    .. len_cnt[2] =  00000000 00000010
++                                               ||
++                                               vv
++                                         cum = xx000000 00000000
++
++のような木に対しても計算結果はオーバーフローされ cum は 0 になる。
++
++       /\
++      a /\       .. len_cnt[1] = 00000000 00000001
++       b /\      .. len_cnt[2] =  00000000 00000001
++        c  d     .. len_cnt[3] =   00000000 00000010
++                                                 |||
++                                                 vvv
++                                           cum = xxx00000 00000000
++
++も同様に cum は 0 だ。結局 cum が 0 にならない木とはある節が 1 つの葉
++しかもたないような場合であるらしい。
++
++       /\
++      a /\       .. len_cnt[1] = 00000000 00000001
++       b  \      .. len_cnt[2] =  00000000 00000001
++           d     .. len_cnt[3] =   00000000 00000001
++                                                 |||
++                                                 vvv
++                                           cum = 11100000 00000000
++
++そして、ハフマン木の作り方からこのようなことは起こりえないのではないか
++と思える。
++
++(C) では、if (cum) で、この起こりえないハフマン木の場合になにか処理を
++行っている。まったく謎であるが、まず、この (C) を特殊条件とみなして先
++に (D) の方を見ることにしよう。
++
++    /* (D) */
++    /* make len */
++    for (i = 16; i > 0; i--) {
++        k = len_cnt[i];
++        while (k > 0) {
++            len[*sort++] = i;
++            k--;
++        }
++    }
++
++sort は何かというと、make_tree() の引数に渡された codeparm を指してい
++る。この配列の中には(ハフマン木を構築する際に設定されていたのだが)、出
++現頻度の低い順で平文の文字コードが入っている。make_tree() で、sort に
++値を設定する際、
++
++        if (j < n)
++            *sort++ = j;
++
++のように条件判断があったので、sort[] にはハフマン木の節は入っていない。
++そしてハフマン木はその構築の仕方から出現頻度の低い文字は木のより深い場
++所に位置づけられている。これらのことから make_len()で求めようとしてい
++るものが何なのかがわかる。make_len() は、
++    len[文字] = ハフマン木の深さ
++といった対応表を作成する処理だ。さらに言うとハフマン木の深さは文字を符
++号化した結果のビット数を表すことから
++    lenparm[文字] = 符号語のビット数
++といった対応表を作成する処理であると言った方が正解だろう。
++len[] は、make_tree() の冒頭で、lenparm を指すように設定された変数なの
++で、そのように置き換えておいた。
++
++では、謎の (C) を見よう。その前に cum != 0 は起こりえないと書いたがよ
++く考えたら len_cnt[16] だけは深さ16以上の葉すべての数を計上しているた
++め、どのような値もあり得る。つまり、この (C) の処理はハフマン木が深さ 
++17 以上になったときに処理されるものだと言えそうだ。思い切って図示しよ
++う例えばこんな木は、(C)の処理対象となる。
++
++       /\
++      a /\       .. len_cnt[ 1] = 0000000000000001
++       b /\       .. len_cnt[ 2] = 0000000000000001
++        c /\       .. len_cnt[ 3] = 0000000000000001
++         d /\       .. len_cnt[ 4] = 0000000000000001
++          e /\       .. len_cnt[ 5] = 0000000000000001
++           f /\       .. len_cnt[ 6] = 0000000000000001
++            g /\       .. len_cnt[ 7] = 0000000000000001
++             h /\       .. len_cnt[ 8] = 0000000000000001
++              i /\       .. len_cnt[ 9] = 0000000000000001
++               j /\       .. len_cnt[10] = 0000000000000001
++                k /\       .. len_cnt[11] = 0000000000000001
++                 l /\       .. len_cnt[12] = 0000000000000001
++                  m /\       .. len_cnt[13] = 0000000000000001
++                   n /\       .. len_cnt[14] = 0000000000000001
++                    o /\       .. len_cnt[15] = 0000000000000001
++                     p /\       .. len_cnt[16] = 0000000000000011
++                      q  r                       ||||||||||||||||
++                                                 vvvvvvvvvvvvvvvv
++                                           cum = 0000000000000001
++
++このような木は例えば各文字が以下の出現頻度となるファイルを作成すると起
++こる(実際には、LHA の場合、slide 辞書法の処理もあるのでこれほど単純で
++はない)。
++
++        文字    頻度        文字    頻度
++        ------------        ------------
++        r          1        i        256
++        q          1        h        512
++        p          2        g       1024
++        o          4        f       2048
++        n          8        e       4096
++        m         16        d       8129
++        l         32        c      16384
++        k         64        b      32768
++        j        128        a      65535
++
++ところで、cum の値は何なのかというと、
++
++                                                        :
++                               .. len_cnt[15] = 0000000000000001
++                     p /\       .. len_cnt[16] = 0000000000000100
++                      q /\                       ||||||||||||||||
++                       r  s                      vvvvvvvvvvvvvvvv
++                                           cum = 0000000000000010
++
++この場合は cum = 2 だ。
++                                                        :
++                               .. len_cnt[15] = 0000000000000001
++                     p /\       .. len_cnt[16] = 0000000000000101
++                      q /\                       ||||||||||||||||
++                       r /\                      vvvvvvvvvvvvvvvv
++                        s  t               cum = 0000000000000011
++
++この場合は cum = 3 だ。少なくともこの例では深さ 16 以上の葉の数 - 2に
++なるらしい(そうか、11111111 11111110 = -2 を足しているのだから当然だ)。
++
++では、今度こそ (C) を見る。
++
++    /* (C) */
++    /* adjust len */
++    if (cum) {
++        fprintf(stderr, "17");
++        len_cnt[16] -= cum; /* always len_cnt[16] > cum */
++        do {
++            for (i = 15; i > 0; i--) {
++                if (len_cnt[i]) {
++                    len_cnt[i]--;
++                    len_cnt[i + 1] += 2;
++                    break;
++                }
++            }
++        } while (--cum);
++    }
++
++である。いきなり fprintf() しているところがすごい。デバッグ用の出力が
++残っているのだろう。LHa for UNIX で 17 という出力を見たことがある人は
++教えて欲しい。
++
++で・・・、結局この (C) の部分は見てもよくわからなかった。ここまで書い
++ておいてなんだが、気持ちよく無視することにした。
++
++では、make_tree() から呼び出される最後の関数、maketree.c:make_code() 
++を見よう。make_code() は、make_tree() の(F) の部分で以下のように呼ばれ
++ていた。
++
++    make_code(nparm, lenparm, codeparm);
++
++この引数のうち、lenparm[] は先ほどの make_len[] で値が作られたものだが、
++    lenparm[文字] = 符号語のビット数
++という対応表だった。codeparm[] は、先ほども出たが make_tree() の中で設
++定されているものだった。出現頻度の低い順で平文の文字コードが入った配列
++だ。
++
++void
++make_code(n, len, code)
++    int             n;
++    unsigned char   len[];
++    unsigned short  code[];
++{
++    unsigned short  weight[17]; /* 0x10000ul >> bitlen */
++    unsigned short  start[17];  /* start code */
++    unsigned short  j, k;
++    int             i;
++
++    j = 0;
++    k = 1 << (16 - 1);
++    for (i = 1; i <= 16; i++) {
++        start[i] = j;
++        j += (weight[i] = k) * len_cnt[i];
++        k >>= 1;
++    }
++    for (i = 0; i < n; i++) {
++        j = len[i];
++        code[i] = start[j];
++        start[j] += weight[j];
++    }
++}
++
++最初の for 文では、変数 i に対して、weight[i] が以下のように設定される。
++
++  weight[i=1..16] = 2^(16-i)
++
++そして、start[i] は、
++
++  start[1] = 0
++  start[n] = start[n-1] + weight[n-1] * len_cnt[n-1]   (n > 1)
++
++という漸化式だ。starr[] の添字 i は、len_cnt[i](深さ i の葉の数)の添字
++でもあることから、ハフマン木の深さを表している。start が実際にどのよう
++な値を取るかと言うと、例えば len_cnt[i] の各要素が Li であった場合、
++
++     i     len_cnt[i]   weight[i]   start[i]
++ --------------------------------------------
++     1         L1        2^15       0
++     2         L2        2^14      2^15 * L1
++     3         L3        2^13      2^15 * L1 + 2^14 * L2
++     4         L4        2^12      2^15 * L1 + 2^14 * L2 + 2^13 * L3
++
++こんな感じだ。これはいったい何だろうか？続く for 文を見てみよう。
++
++    for (i = 0; i < n; i++) {
++        j = len[i];
++        code[i] = start[j];
++        start[j] += weight[j];
++    }
++
++ここでの i は、0...n の範囲であることから平文の文字を示す。紛らわしい
++ので、i は、c に書き換え、j を i にしよう。(これで、i は前の for 文の 
++i と同じ意味になる)
++
++    int c;
++
++    for (c = 0; c < n; c++) {
++        i = len[c];
++        code[c] = start[i];
++        start[i] += weight[i];
++    }
++
++i = len[c] は文字 c のビット長で、ハフマン木の深さを示す。
++code[c] には、start[i] が設定されるが、一度 start[i] が参照されると
++start[i] は、weight[i] を足した値が次回使われる。例えば、ある文字
++a, b, c がそれぞれ以下のハフマン木で表現されたとする。
++
++       /\               a: 0
++      a /\              b: 10
++        b c             c: 11
++
++
++              i     len_cnt[i]   weight[i]   start[i]
++          --------------------------------------------
++              1         1         2^15        0
++              2         2         2^14       2^15
++
++  c  len[c]   i     len_cnt[i]   weight[i]   code[c]
++ ---------------------------------------------------
++  a     1     1         1            2^15       0
++  b     2     2         2            2^14      2^15
++  c     2     2         2            2^14      2^15 + 2^14
++
++こんな感じになる。別のハフマン木の場合も見てみよう。
++
++        /\                a: 00
++      /\  /\              b: 01
++     a  b c d             c: 10
++                          d: 11
++
++              i     len_cnt[i]   weight[i]   start[i]
++          --------------------------------------------
++              1         0         2^15        0
++              2         4         2^14        0
++              3         0         2^13       2^14 * 4
++
++  c  len[c]   i     len_cnt[i]   weight[i]   code[c]
++ ---------------------------------------------------
++  a     2     2         4            2^14      0
++  b     2     2         4            2^14      2^14
++  c     2     2         4            2^14      2^14 * 2
++  d     2     2         4            2^14      2^14 * 3
++
++これで、ピント来ると凄いのだが code[c] には文字 c に対応する符号化した
++ビット列が設定されるようになっていることに気づくだろうか？つまりは、
++
++  c  len[c]   i     len_cnt[i]   weight[i]   code[c]
++ -----------------------------------------------------------
++  a     2     2         4            2^14  00000000 00000000
++  b     2     2         4            2^14  01000000 00000000
++  c     2     2         4            2^14  10000000 00000000
++  d     2     2         4            2^14  11000000 00000000
++
++だ。以降、code[] (実際には codeparm) を利用することで表引きで文字に
++対応するハフマン符号を得ることができるようになっている(code[c]のうち上
++位 len[c] ビットだけを見る)。符号化の際に木を辿る必要はなく、高速な符号
++化が可能になる(と期待される。どの程度効果があるかはいずれ検証してみた
++い。そういえば、葉から根に向かって木を辿るための情報が必要なかったこと
++もこれでわかった)。
++
++結局 make_tree(nparm, freqparm, lenparm, codeparm) は、lenparm[c] と 
++codeparm[c] を作成する関数だったわけだ(ハフマン表とでも言うのだろう
++か？)。実は、このことは make_tree() を呼び出し、 codeparm を使用してい
++る箇所(huf.c)を見るまでまるでわからなかった。しかも、まだちゃんと理解
++したわけではない。
++
++ふと思ったのだが、上記の表作成は文字コード順に依存している(コードの若
++い方が左の子になる)が、木を作成する場合はそのようなことはなかったはず
++だ。ハフマン木を辿った場合と表を参照した場合とでは得られる符号語は異な
++るのではないだろうか？ということは圧縮文に埋め込まれるのは木ではなくこ
++の表の方だということも想像がつく。木の構造を表す left[]、right[] はグ
++ローバル変数だが、実際には make_tree() 内でしか使われないのかも知れな
++い(少なくとも符号化に関してはそのようだ。huf.c を眺めるとどうやら復号
++時は left[]、right[]は使われるらしい)。
++
++さらにふと思い付いた。謎の (C) のコードだが 深さ 17 以上の木が作成され
++た場合に木を再構築する処理だということがわかった。最初、len_cnt[] (あ
++る深さの葉の数) だけが、操作されていたからよくわからなかったのだ、
++
++    /* (C) */
++    /* adjust len */
++    if (cum) {
++        fprintf(stderr, "17");
++        len_cnt[16] -= cum; /* always len_cnt[16] > cum */
++        do {
++            for (i = 15; i > 0; i--) {
++                if (len_cnt[i]) {
++                    len_cnt[i]--;
++                    len_cnt[i + 1] += 2;
++                    break;
++                }
++            }
++        } while (--cum);
++    }
++
++深さ n の葉の数を 1 つ減らして、その下の葉の数を 2 足している。
++これが、cum の数だけ繰り返される。例えば、前にも出た
++
++                                                     :
++                   n /\       .. len_cnt[14] = 0000000000000001
++                    o /\       .. len_cnt[15] = 0000000000000001
++                     p /\       .. len_cnt[16] = 0000000000000011
++                      q  r                       ||||||||||||||||
++                                                 vvvvvvvvvvvvvvvv
++                                           cum = 0000000000000001
++
++の例では、最初に len_cnt[16] から cum {1} が引かれ、
++
++                                                     :
++                   n /\       .. len_cnt[14] = 0000000000000001
++                    o /\       .. len_cnt[15] = 0000000000000001
++                     p /       .. len_cnt[16] = 0000000000000010
++                      q
++
++続いて、深さ 15 より上の葉のある節から 1 つ子を取り、
++
++                                                     :
++                   n /\       .. len_cnt[14] = 0000000000000001
++                      /\       .. len_cnt[15] = 0000000000000000
++                     p /        .. len_cnt[16] = 0000000000000010
++                      q
++
++下の葉の数(この例では、len_cnt[16])を 2 足している。
++
++                /   \
++              n    /  \       .. len_cnt[14] = 0000000000000001
++                 /\    /\      .. len_cnt[15] = 0000000000000000
++                o  r  p /       .. len_cnt[16] = 0000000000000100
++                       q
++
++cum は、この例では 0 になるので、これで木の平滑化は終る。テキストだと
++ちょっと見にくいが、そういう処理ということで間違いないだろう。
++lenparm[] の値はこの後の (D) で、この木を元に計算されている。
++
++ところで、本当の所は以下のような文字の対応になる(表を作成するときに文
++字コード順になっているため)のだが、結果的に元の木から p を含む節を取り
++除き o の位置に挿入する処理になっている。なんだか面白い。
++
++                /   \
++              n    /  \       .. len_cnt[14] = 0000000000000001
++                 /\    /\      .. len_cnt[15] = 0000000000000000
++                o  p  q  r      .. len_cnt[16] = 0000000000000100
++
++文字から Huffman 符号が得られるようになったので、圧縮処理を行う道具は
++揃った。いよいよ Huffman 法による圧縮処理全般 (huf.c) を見ることにしよ
++う。
++
++まず huf.c で定義されているデータ構造から確認しよう。データ構造がわかっ
++てしまえばアルゴリズムの 90% はわかったも同然だ(誇張)。
++
++huf.c には以下の変数が定義されている。
++
++unsigned short  left[2 * NC - 1], right[2 * NC - 1];
++unsigned char   c_len[NC], pt_len[NPT];
++unsigned short  c_freq[2 * NC - 1], c_table[4096], c_code[NC], p_freq[2 * NP - 1],
++                pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
++
++static unsigned char *buf;
++static unsigned int bufsiz;
++static unsigned short blocksize;
++static unsigned short output_pos, output_mask;
++static          int   pbit;
++static          int   np;
++
++使用されている定数も確認する lha_macro.h だ。
++
++#define NP          (MAX_DICBIT + 1)
++#define NT          (USHRT_BIT + 3)
++#define PBIT        5       /* smallest integer such that (1 << PBIT) > * NP */
++#define TBIT        5       /* smallest integer such that (1 << TBIT) > * NT */
++#define NC          (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
++/*      #if NT > NP #define NPT NT #else #define NPT NP #endif  */
++#define NPT         0x80
++#define CBIT                9   /* $\lfloor \log_2 NC \rfloor + 1$ */
++
++たくさんある。たくさんありすぎてくじけそうだが(事実、くじけた)、現時点
++でわかる変数もある。left[] や right[] は Huffman 木を構築するのに使用
++した変数だった。そこから NC は文字種の最大数であることがわかる。NC に 
++MAXMATCH{256} 等の値が使用されているのは謎だが、現時点では無視しておこ
++う。
++
++c_freq[] や c_len[], p_freq[], pt_len[] も make_tree() で出て来た変数
++名に似ている。おそらく make_tree() に渡す変数だろう。確認してみたとこ
++ろ huf.c から make_tree() の呼び出しを行っている部分を抜き出すと、
++
++    root = make_tree(NC, c_freq, c_len, c_code);
++    root = make_tree(NT, t_freq, pt_len, pt_code);
++    root = make_tree(np, p_freq, pt_len, pt_code);
++
++の 3 箇所が出て来た。つまり、
++
++   文字種の数  文字の出現回数   符号化した文字  文字に対応する
++                                の bit 長       Huffman 符号表
++   -----------------------------------------------------------
++     NC         c_freq          c_len           c_code
++     NT         t_freq          pt_len          pt_code
++     np         p_freq          pt_len          pt_code
++
++という関係のようだ。どうやら c_code、pt_code という 2 種類の
++Huffman 符号表を使用するらしい。
++
++その他の変数に関しても予想を立てたい所だが、もうくじけたので、処理内容
++から攻めることにした。
++
++slide 辞書法の解読で Huffman 法に関連した処理の呼び出しがいくつかあっ
++た。
++
++    /* initialize */
++    alloc_buf()
++
++    /* encoder */
++    encode_set.encode_start()
++    encode_set.output(c, off)
++    encode_set.encode_end()
++
++    /* decoder */
++    decode_set.decode_start()
++    decode_set.decode_c()
++    decode_set.decode_p()
++
++以上だ。lh4, 5, 6, 7 では、上記のそれぞれは、huf.c の以下の関数の呼び
++出しに対応している。これは、slide.c の冒頭部分で定義されている。
++
++    /* encoder */
++    encode_start() -> encode_start_st1()
++    output()       -> output_st1()
++    encode_end()   -> encode_end_st1()
++
++    /* decoder */
++    decode_start() -> decode_start_st1()
++    decode_c()     -> decode_c_st1()
++    decode_p()     -> decode_p_st1()
++
++このうちの圧縮処理にあたる部分 encode_start_st1(), output_st1(),
++encode_end_st1() を見ていこう。まずは、初期化処理である 
++encode_start_st1() から、
++
++void
++encode_start_st1( /* void */ )
++{
++    int             i;
++
++    if (dicbit <= 13) {
++        pbit = 4;   /* lh4,5 etc. */
++        np = 14;
++    } else {
++        pbit = 5;   /* lh6,7 */
++        if (dicbit == 16)
++            np = 17;
++        else
++            np = 16;
++    }
++
++    for (i = 0; i < NC; i++)
++        c_freq[i] = 0;
++    for (i = 0; i < np; i++)
++        p_freq[i] = 0;
++    output_pos = output_mask = 0;
++    init_putbits();
++    buf[0] = 0;
++}
++
++dicbit (これは辞書の bit サイズだった)によって、np, pbit の値が変わる。
++dicbit の違いというのは LHa の encoding メソッドの違いだ。それぞれ以下
++の対応になる。
++
++    method  dicbit  np  pbit
++   --------------------------
++    -lh4-   12      14  4
++    -lh5-   13      14  4
++    -lh6-   15      16  5
++    -lh7-   16      17  5
++
++np というのは、先程 make_tree() を呼び出している箇所の洗い出しで見かけ
++た変数だった。まだ、この関連はよくわからない。
++
++処理の後半では、文字の出現頻度を表す c_freq[]、p_freq[] の初期化を
++行っている。さらに
++
++    output_pos
++    output_mask
++    buf[]
++
++という初出の変数も 0 に初期化している。(buf は、buf[0] のみ初期化して
++いる) init_putbits() の呼び出しは bit 出力ルーチンの初期化処理だった。
++以降、putbits(), putcode() を使用できる。
++
++次に output_st1(c, p) を見る。slide.c でこの関数は以下のように使用され
++ていた。
++
++        output_st1(c, 0)        文字 c を出力
++        output_st1(len, off)    <len, off> のペアを出力
++
++このことを踏まえた上で、処理内容を見てみよう。
++
++void
++output_st1(c, p)
++    unsigned short  c;
++    unsigned short  p;
++{
++    static unsigned short cpos;
++
++    /* (A) */
++    output_mask >>= 1;
++    if (output_mask == 0) {
++        output_mask = 1 << (CHAR_BIT - 1);
++        if (output_pos >= bufsiz - 3 * CHAR_BIT) {
++            send_block();
++            if (unpackable)
++                return;
++            output_pos = 0;
++        }
++        cpos = output_pos++;
++        buf[cpos] = 0;
++    }
++    /* (B) */
++    buf[output_pos++] = (unsigned char) c;
++    c_freq[c]++;
++    /* (C) */
++    if (c >= (1 << CHAR_BIT)) {
++        buf[cpos] |= output_mask;
++        buf[output_pos++] = (unsigned char) (p >> CHAR_BIT);
++        buf[output_pos++] = (unsigned char) p;
++        c = 0;
++        while (p) {
++            p >>= 1;
++            c++;
++        }
++        p_freq[c]++;
++    }
++}
++
++(A) は、output_mask の値に応じて処理を行うようだ。初期化で output_mask 
++は 0 だから (A) の処理は最初から実行されるが、ひとまず無視しよう。
++
++(B) は、buf に引数で渡された文字 c を格納し、c_freq[c] の値(文字の出現
++頻度)を足している。どうやら基本は渡された文字 c を延々と buf に格納し、
++後で、圧縮を行う(おそらく (A) だろう)ようになっているようだ。
++
++この buf のサイズはと言うと、これは alloc_buf() で割り当てられていた。
++
++unsigned char  *
++alloc_buf( /* void */ )
++{
++    bufsiz = 16 * 1024 *2;  /* 65408U; */ /* t.okamoto */
++    while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) {
++        bufsiz = (bufsiz / 10) * 9;
++        if (bufsiz < 4 * 1024)
++            break;
++    }
++    return buf;
++}
++
++bufsiz が buf のサイズらしい。これはできるだけ大きく取るようにしている
++が、大きく取れなければそれはそれで良いようだ。
++
++さらに、(C) の処理を行うかどうかは、c >= (1 << CHAR_BIT) という条件で
++判断されている。この条件が真となる場合は何かと言うと c が「長さ」を表
++す場合だ。このとき引数 p で「位置」が渡されているのでこれも buf にセッ
++トしている。その具体的内容はというと、何やら cpos というこの関数内で 
++static な変数が使用されている。よくわからないが文字 c や <len,off> の
++ペアは、buf 上で以下のように表されるらしい。
++
++----------------------------------------------------------------------------
++
++output_st1(c1, 0)
++output_st1(c2, 0)
++output_st1(len, off)
++
++と呼び出した場合の buf の状態
++
++    +-----+-----+-----+-----+-----+
++buf | c1  | c2  | len |    off    |
++    +-----+-----+-----+-----+-----+
++
++----------------------------------------------------------------------------
++
++(C) の処理の最後の部分
++
++        c = 0;
++        while (p) {
++            p >>= 1;
++            c++;
++        }
++        p_freq[c]++;
++
++は、出現頻度 p_freq[] を求める処理だが、p_freq は、off 値の出現頻度を
++表しているらしい。ここでの c は、p (off) の bit 長になっている。off の
++値は大きい(辞書サイズだから最大(lh7)で、64KB)ので、代わりに bit 長を利
++用しているといったところか。そういえば、np という変数があり、
++make_tree() の第一引数に渡されることから、これは、p_freq[] の要素数を
++表す。p_freq[] の要素数とは、<off> の bit 長の最大値+1なので、lh7 で、
++64KB。つまり 16 bit + 1 が np になる。
++
++ついでに言うと、「長さ」はそのまま c_freq[] で頻度が計上されていた。同
++じく make_tree() の第一引数に渡される NC の値が
++
++#define NC          (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
++
++なのは、そういうことだ(長さを考えなければ文字の最大値{255}+1となるとこ
++ろだが、長さの最大値が、256 + MAXMATCH - THRESHOLD だから上の式になっ
++ているのだろうと思う。ちょっとわかりにくいが)
++
++ここまでで、圧縮を行う処理は現われなかった。やはり (A) の部分が圧縮処
++理だ。
++
++    /* (A) */
++    output_mask >>= 1;
++    if (output_mask == 0) {
++        output_mask = 1 << (CHAR_BIT - 1);
++        if (output_pos >= bufsiz - 3 * CHAR_BIT) {
++            send_block();
++            if (unpackable)
++                return;
++            output_pos = 0;
++        }
++        cpos = output_pos++;
++        buf[cpos] = 0;
++    }
++
++最初、output_mask は、0 なので if 条件を満たす。そして、output_mask は、
++(1 << (CHAR_BIT - 1)) つまり、128 になる。(A) の冒頭で、>>= 1 している
++ので、output_mask は、128, 64, 32, ..., 1, 128 という値を取るらしい。そ
++して、本当の初期値は 128 だ。
++
++次の条件
++
++  output_pos >= bufsiz - 3 * CHAR_BIT
++
++というのは、buf が bufsiz - 24 よりも大きくなったときの値だ。ひとまず
++無視しよう。そして、cpos = output_pos++ として、buf[cpos] = 0 にセット
++されている。どうやら、先にこちらを見るべきだったようだ。cpos の値
++と output_pos++ が (A) で行われていることを踏まえてもう一度 (B)、(C)
++の処理を見ると、buf は以下のように使用されているらしい。
++
++----------------------------------------------------------------------------
++
++output_st1(c1, 0)
++output_st1(c2, 0)
++output_st1(len, off)
++
++と呼び出した場合の buf の状態
++
++
++    +-----+-----+-----+-----+-----+-----+--
++buf |  32 | c1  | c2  | len |    off    |  ...
++    +-----+-----+-----+-----+-----+-----+--
++   cpos                                output_pos
++
++----------------------------------------------------------------------------
++
++<len, off> のペアを出力するとき buf[cpos] には以下のような値が設定され
++ていたことも図に書いてある。
++
++        buf[cpos] |= output_mask;
++
++もう少し注意深くこのあたりを考えよう。output_mask は、この関数が呼ばれ
++るたびに 128, 64, 32, ..., 1, 128, 64, ... という値になる。そして、buf 
++は、呼ばれるたびに c (1バイト)、あるいは <len, off> (3バイト)の値が設
++定されるが、output_mask が 128 になったときは、余分に 1 バイト空きがで
++きる(これは、buf[cpos]で示される)。この空きには <len,off> が設定される
++たびにその時点の output_mask 値が設定されるようだ。(A) が呼ばれるとき
++と言うのは、一番最初の output_mask = 0 の場合を除けば、
++
++----------------------------------------------------------------------------
++
++output_mask    128   64    32                16    8     4     2     1
++        +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
++buf     |  32 | c1  | c2  | len |    off    |  c3 |  c4 |  c5 |  c6 |  c7 |
++        +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
++        cpos                                                             /
++                                                                        /
++                                                               output_pos
++
++----------------------------------------------------------------------------
++
++このような状態になったときということだ。さらに、buf[cpos] には、
++<len,off> が格納されている位置を表している。この状態を 1 ブロックとし
++てこのブロック単位に情報が buf に格納され、buf がいっぱいになったら 
++(A) の処理の無視したif 文の中身で
++
++        if (output_pos >= bufsiz - 3 * CHAR_BIT) {
++            send_block();
++            if (unpackable)
++                return;
++            output_pos = 0;
++        }
++
++のように send_block() が呼ばれるようになっているようだ。この if の条件
++で、3 * CHAR_BIT というのは <len, off> の格納バイト数を示している。
++(と思ったが、3 * CHAR_BIT ではビット数だ。一方、bufsiz はバイト数だ。
++計算に使用している単位が違う。何やらバグっぽい雰囲気があるが、バグだと
++してもバッファを効率的に使用できないだけなので大したことはないのだろう)
++
++output_pos = 0 としていることからこの時点の buf の中身がすべて 
++send_block() で圧縮されファイルに出力されるだろうことが想像できる。
++
++この 1 ブロックに満たない状態でファイルの終りが来た場合、後処理 
++encode_end_st1() で send_block() が呼ばれるであろうことも想像できる。
++
++encode_end_st1( /* void */ )
++{
++    if (!unpackable) {
++        send_block();
++        putbits(CHAR_BIT - 1, 0);   /* flush remaining bits */
++    }
++}
++
++思った通りである。putbits(7, 0) というは、bitbuf に残った bit を吐き出す
++ためであることは、bit 入出力ルーチンの解読で確認済みだ。
++
++そういうわけで、send_block() が圧縮のメインルーチンである。
++send_block() の入力とは先に示した図の状態の buf だ。huf.c:send_block() 
++を見てみよう。
++
++static void
++send_block( /* void */ )
++{
++    unsigned char   flags;
++    unsigned short  i, k, root, pos, size;
++
++    /* (A) */
++    root = make_tree(NC, c_freq, c_len, c_code);
++    size = c_freq[root];
++    putbits(16, size);
++    /* (B) */
++    if (root >= NC) {
++        count_t_freq();
++        root = make_tree(NT, t_freq, pt_len, pt_code);
++        if (root >= NT) {
++            write_pt_len(NT, TBIT, 3);
++        } else {
++            putbits(TBIT, 0);
++            putbits(TBIT, root);
++        }
++        write_c_len();
++    } else {
++        putbits(TBIT, 0);
++        putbits(TBIT, 0);
++        putbits(CBIT, 0);
++        putbits(CBIT, root);
++    }
++    /* (C) */
++    root = make_tree(np, p_freq, pt_len, pt_code);
++    if (root >= np) {
++        write_pt_len(np, pbit, -1);
++    }
++    else {
++        putbits(pbit, 0);
++        putbits(pbit, root);
++    }
++    /* (D) */
++    pos = 0;
++    for (i = 0; i < size; i++) {
++        if (i % CHAR_BIT == 0)
++            flags = buf[pos++];
++        else
++            flags <<= 1;
++        if (flags & (1 << (CHAR_BIT - 1))) {
++            encode_c(buf[pos++] + (1 << CHAR_BIT));
++            k = buf[pos++] << CHAR_BIT;
++            k += buf[pos++];
++            encode_p(k);
++        } else
++            encode_c(buf[pos++]);
++        if (unpackable)
++            return;
++    }
++    /* (E) */
++    for (i = 0; i < NC; i++)
++        c_freq[i] = 0;
++    for (i = 0; i < np; i++)
++        p_freq[i] = 0;
++}
++
++なかなか大きな関数であるが、それほど難しいことはない。まず、(A)
++
++    /* (A) */
++    root = make_tree(NC, c_freq, c_len, c_code);
++    size = c_freq[root];
++    putbits(16, size);
++
++make_tree() で Huffman 表 c_len[], c_code[] を構築する。戻り値の root 
++は、Huffman 木の根を示し、c_freq[root] は、文字の出現回数の総和である
++から、size は、平文の総バイト数だ(size に <off> の分のサイズは含まれな
++い。c_freq[] が、<off> の出現頻度を数えなかったから)。ファイルには、こ
++の size がまず書き出されている(そういえば、この bit 入出力ルーチンを使
++用するとバイトオーダーに関して考慮する必要がなくなる)。
++
++----------------------------------------------------------------------------
++
++      16bit  
++   |---------|
++   +----+----+
++   |  size   |
++   +----+----+
++
++----------------------------------------------------------------------------
++
++続いて、(B)
++
++    if (root >= NC) {
++        count_t_freq();
++        root = make_tree(NT, t_freq, pt_len, pt_code);
++        if (root >= NT) {
++            write_pt_len(NT, TBIT, 3);
++        } else {
++            putbits(TBIT, 0);
++            putbits(TBIT, root);
++        }
++        write_c_len();
++    } else {
++        putbits(TBIT, 0);
++        putbits(TBIT, 0);
++        putbits(CBIT, 0);
++        putbits(CBIT, root);
++    }
++
++root が NC よりも大きい場合を判断しているが、ハフマン木の根は必ず NC よ
++りも大きい(make_tree() の avail の初期値を確認しよう)。では、この
++条件を満たさない場合と言うのは何かと言うと、同じく make_tree() を確認すると、
++
++    if (heapsize < 2) {
++        codeparm[heap[1]] = 0;
++        return heap[1];
++    }
++
++という例外条件があった。これは、圧縮する文字がない、あるいは1種類しか
++ない場合の処理だ。圧縮する文字がない場合に send_block() が呼ばれること
++はないだろうから、(B) の処理の else は 1 ブロック中に圧縮する文字が 1 
++種類しかない場合の処理である(この 1 種類の文字とは、make_tree() の戻り
++値 root だ)。このとき以下のような出力になる。(TBIT{5}, CBIT{9} である)
++
++----------------------------------------------------------------------------
++      TBIT    CBIT
++   TBIT   CBIT
++   |--|--|----|----|               TBIT: 5
++   +--+--+----+----+               CBIT: 9
++   | 0| 0|   0|root|
++   +--+--+----+----+
++
++----------------------------------------------------------------------------
++
++これが、1ブロックに1種類しか文字がない場合のファイルの状態だ(offの情報
++はまだ含まない)。(B)の if が真のときがどうなるかは複雑そうなので後で見
++ることにしよう。
++
++続いて (C)
++
++    root = make_tree(np, p_freq, pt_len, pt_code);
++    if (root >= np) {
++        write_pt_len(np, pbit, -1);
++    }
++    else {
++        putbits(pbit, 0);
++        putbits(pbit, root);
++    }
++
++p_freq[] を見ていることから今度は <off> の情報の Huffman 木を構築して
++いることがわかる。先程と同様に、<off> の値がすべて同じ場合は、else の
++条件になり、以下の出力が行われる。(np の値は、-lh7- の場合で、17 だ)
++
++----------------------------------------------------------------------------
++              
++      np bit    np bit              method  np
++   |---------|---------|            ----------
++   +----+----+---------+            -lh4-   14
++   |     0   |  root   |            -lh5-   14
++   +----+----+---------+            -lh6-   16
++                                    -lh7-   17
++
++----------------------------------------------------------------------------
++
++ここまでに出力した情報が何を示すかわかるだろうか？Huffman 法の符号化処
++理は文字を bit 列に変換する。これを復号する場合は bit 列に対応する文字
++を知る必要がある。すなわち Huffman 木である(実際には Huffman 表)。図示
++したのは、Huffman 木を構築する必要がない(構築できない)場合の情報になる
++が、現在解読を飛ばしている処理は Huffman 表をファイルに出力している箇
++所であることは容易に想像がつく。ということは残りの (D) が本当の圧縮文
++を出力する箇所だ。
++
++    /* (D) */
++    pos = 0;
++    for (i = 0; i < size; i++) {
++        if (i % CHAR_BIT == 0)
++            flags = buf[pos++];
++        else
++            flags <<= 1;
++        if (flags & (1 << (CHAR_BIT - 1))) {
++            encode_c(buf[pos++] + (1 << CHAR_BIT));
++            k = buf[pos++] << CHAR_BIT;
++            k += buf[pos++];
++            encode_p(k);
++        } else
++            encode_c(buf[pos++]);
++        if (unpackable)
++            return;
++    }
++
++size 数分ループしている。size は、<off> を除いた buf の文字数を示して
++いると前に書いたが、どうやら <len, off> を 1 文字と数えたときの buf の
++文字数を示していると考えた方が良さそうだ。
++
++最初の if で、
++
++        if (i % CHAR_BIT == 0)
++            flags = buf[pos++];
++        else
++            flags <<= 1;
++
++これが真になる条件は buf[pos] が buf[cpos] である場合だ(output_mask が 
++128, 64, ..., 1 と 8 つの値を巡回していたことを思い出そう)。
++flags は、<len, off> の buf 上の位置を示す bit マスクになる。
++
++        if (flags & (1 << (CHAR_BIT - 1))) {
++            encode_c(buf[pos++] + (1 << CHAR_BIT));
++            k = buf[pos++] << CHAR_BIT;
++            k += buf[pos++];
++            encode_p(k);
++        } else
++            encode_c(buf[pos++]);
++
++flags が、127 であるとき buf[pos] は、<len, off> を指し、
++
++  encode_c(len + 256)
++  encode_p(off)
++
++で、圧縮を行うようだ。len に 256 を足しているのは、buf[] に len を格納
++するとき(output_st1() の (B) の処理)に
++
++    buf[output_pos++] = (unsigned char) c;
++
++のように最上位 bit を捨てていたからだ。len は常に 256 以上なので、256 
++を足すことで元の len の値を圧縮ルーチンに渡している。
++
++通常の文字は
++
++  encode_c(buf[pos])
++
++で圧縮されている。encode_c() の処理内容は簡単なので見てみよう。
++
++static void
++encode_c(c)
++    short           c;
++{
++    putcode(c_len[c], c_code[c]);
++}
++
++c_len[], c_code[] が文字 c に対応する Huffman 符号の bit 長と符号を示
++しているので、それをそのまま出力している。簡単だ。
++
++encode_p() はもう少し複雑だ。
++
++static void
++encode_p(p)
++    unsigned short  p;
++{
++    unsigned short  c, q;
++
++    c = 0;
++    q = p;
++    while (q) {
++        q >>= 1;
++        c++;
++    }
++    putcode(pt_len[c], pt_code[c]);
++    if (c > 1)
++        putbits(c - 1, p);
++}
++
++最初の while 文で、<off> の bit 長を求め、その bit 長の情報を
++Huffman 符号化している。その後、putbits() で、必要 bit 数だけ
++出力する。つまり、<off> は以下のように符号化される。
++
++----------------------------------------------------------------------------
++off = 64 の圧縮
++
++     |---- 16 bit -------|
++     +----+----+----+----+
++off  |0000 0000 0100 0000|
++     +----+----+----+----+
++                 |-7 bit-|
++
++この圧縮文は以下(長さが 7 bit であるという情報(Huffman符号化)と値のペア)
++
++                       |-6 bit-|
++     +-----------------+-------+
++     | 7 のHuffman符号 |00 0000|
++     +-----------------+-------+
++
++----------------------------------------------------------------------------
++
++ここで、値を 6 bit しか出力しない(putbits() で c-1 を渡している)のは、
++7 bit 目が 1 であることが自明だからである。常に off != 0 だから、書き
++出す情報を 1 bit 削減できるわけだ。したがって、off=1 のときは bit 長が 
++1 という情報しか書き出さない。
++
++最後の (E) は頻度表をクリアしているだけだ。
++
++    /* (E) */
++    for (i = 0; i < NC; i++)
++        c_freq[i] = 0;
++    for (i = 0; i < np; i++)
++        p_freq[i] = 0;
++
++以上で、圧縮処理全体の概要がわかった。後は無視していた Huffman 表を出
++力する箇所だけだ。
++
++    /* (B) */
++    if (root >= NC) {
++        count_t_freq();
++        root = make_tree(NT, t_freq, pt_len, pt_code);
++        if (root >= NT) {
++            write_pt_len(NT, TBIT, 3);
++        } else {
++            putbits(TBIT, 0);
++            putbits(TBIT, root);
++        }
++        write_c_len();
++
++ここでは、c_len[], c_code[] という Huffman 表を出力するだけのはずだが、
++さらに Huffman 表 pt_len[], pt_code[] の構築を行っている。これは、
++<off> の bit 長の Huffman 符号表でもあった変数だが、単に変数を使い回し
++ているだけだ。ここでの pt_len[], pt_code[] が何の符号表かは、
++count_t_freq() を見る必要がある。
++
++static void
++count_t_freq(/*void*/)
++{
++    short           i, k, n, count;
++
++    for (i = 0; i < NT; i++)
++        t_freq[i] = 0;
++    n = NC;
++    while (n > 0 && c_len[n - 1] == 0)
++        n--;
++    i = 0;
++    while (i < n) {
++        k = c_len[i++];
++        if (k == 0) {
++            count = 1;
++            while (i < n && c_len[i] == 0) {
++                i++;
++                count++;
++            }
++            if (count <= 2)
++                t_freq[0] += count;
++            else if (count <= 18)
++                t_freq[1]++;
++            else if (count == 19) {
++                t_freq[0]++;
++                t_freq[1]++;
++            }
++            else
++                t_freq[2]++;
++        } else
++            t_freq[k + 2]++;
++    }
++}
++
++最初に頻度表 t_freq[] を初期化する。続いて、
++
++    n = NC;
++    while (n > 0 && c_len[n - 1] == 0)
++        n--;
++
++で、c_len[n] != 0 である最大の n を求めている。
++
++    i = 0;
++    while (i < n) {
++        k = c_len[i++];
++        if (k == 0) {
++            count = 1;
++            while (i < n && c_len[i] == 0) {
++                i++;
++                count++;
++            }
++            if (count <= 2)
++                t_freq[0] += count;
++            else if (count <= 18)
++                t_freq[1]++;
++            else if (count == 19) {
++                t_freq[0]++;
++                t_freq[1]++;
++            }
++            else
++                t_freq[2]++;
++        } else
++            t_freq[k + 2]++;
++    }
++
++c_len[i] は、文字 i の Huffman 符号での bit 長であった。この
++c_len[i] の値を以下の場合分けで t_freq[] に頻度計算している。
++count は、c_len[i] が連続で何回 0 であるかの数だ。
++
++  c_len[i]    count     t_freq[]
++  -------------------------------------------
++     0        0 .. 2    t_freq[0] += count
++     0        3 ..18    t_freq[1]++
++     0        19        t_freq[0]++, t_freq[1]++
++     0        20以上    t_freq[2]++
++   0以外                t_freq[c_len[i]+2]++;
++
++これがどういう理屈であるかはよくわからないが、とにかく頻度計算を行う場
++合に t_freq[0], t_freq[1], t_freq[2] を特別扱いしている。そして、頻度
++計算の対象が c_len[] であることから (B) の処理は、c_len[] に関して 
++Huffman 符号化を行う処理のようだ。
++
++そうして、make_tree() で、t_freq[] に関して Huffman 符号表を作成し、
++write_pt_len() で、この符号表(文字の Huffman 符号のビット長 c_len の 
++Huffman 符号のビット長) pt_len[] を出力する。
++
++static void
++write_pt_len(n, nbit, i_special)
++    short           n;
++    short           nbit;
++    short           i_special;
++{
++    short           i, k;
++
++    while (n > 0 && pt_len[n - 1] == 0)
++        n--;
++    putbits(nbit, n);
++    i = 0;
++    while (i < n) {
++        k = pt_len[i++];
++        if (k <= 6)
++            putbits(3, k);
++        else
++            putbits(k - 3, USHRT_MAX << 1);
++        if (i == i_special) {
++            while (i < 6 && pt_len[i] == 0)
++                i++;
++            putbits(2, i - 3);
++        }
++    }
++}
++
++最初に pt_len[] の要素数を nbit 出力し、続けて符号 bit 長 pt_len[] の
++要素を出力している。nbit は、n を格納するのに必要な bit 数を表している
++ようだ。ここでは、n (NT{19}) を出力するのに TBIT{5} bit 必要であるとい
++うことだ。
++
++pt_len[] を出力するときは、その値が 6 より大きいかどうかで形式を変えて
++出力している。6 以下であればそのまま 3 bit で出力し、7 bit 以上であれ
++ば、bit 数で表現するらしい。例えば pt_len[i] == 7 なら、1110 となる。
++最初の 3 bit は必ず 1 になり、最初の形式と区別がつくようになっている。
++
++さらに、i_special 番目の pt_len[i] を出力後は、i_special ... 6 の範囲
++で pt_len[i] == 0 が続くことを 2 bit で、表現している。i_special は
++write_pt_len() の 3 番目の引数で、今回の場合は 3 だ。例えば 
++pt_len[3..5] がすべて 0 なら pt_len[3] を出力後、i - 3 (= 3) を 2 bit 
++出力する。つまり、11 が出力される。このようなことをしている意味はこれ
++またよくわからない。ちょっと複雑なので図示してみた。
++
++----------------------------------------------------------------------------
++< pt_len[] の出力フォーマット >
++
++             0       TBIT{5}
++             +-------+-----------+-----------+--   --+-----------+
++             |   n   | pt_len[0] | pt_len[1] | ...    pt_len[n-1]|
++             +-------+-----------+-----------+--   --+-----------+
++
++pt_len[i] <= 6 の場合
++
++              0     3bit
++              +-----+
++    pt_len[i] | | | |
++              +-----+
++
++pt_len[i] >= 7 の場合
++
++              0             pt_len[i] - 3
++              +----------------+
++    pt_len[i] |1 1 1 1 ... 1 0 |
++              +----------------+
++
++pt_len[i_special] の直後は 2 bit の情報が付加される。この値を x とする
++と、pt_len[i_special .. x + 3] の範囲で 0 が続くことを意味する。
++
++----------------------------------------------------------------------------
++
++最後に、write_c_len() で、符号表 c_len[] と pt_code[] を出力する。
++
++static void
++write_c_len(/*void*/)
++{
++    short           i, k, n, count;
++
++    n = NC;
++    while (n > 0 && c_len[n - 1] == 0)
++        n--;
++    putbits(CBIT, n);
++    i = 0;
++    while (i < n) {
++        k = c_len[i++];
++        if (k == 0) {
++            count = 1;
++            while (i < n && c_len[i] == 0) {
++                i++;
++                count++;
++            }
++            if (count <= 2) {
++                for (k = 0; k < count; k++)
++                    putcode(pt_len[0], pt_code[0]);
++            }
++            else if (count <= 18) {
++                putcode(pt_len[1], pt_code[1]);
++                putbits(4, count - 3);
++            }
++            else if (count == 19) {
++                putcode(pt_len[0], pt_code[0]);
++                putcode(pt_len[1], pt_code[1]);
++                putbits(4, 15);
++            }
++            else {
++                putcode(pt_len[2], pt_code[2]);
++                putbits(CBIT, count - 20);
++            }
++        }
++        else
++            putcode(pt_len[k + 2], pt_code[k + 2]);
++    }
++}
++
++前に、頻度を数えたときと同様の条件で出力形式が変わっている。処理内容は
++簡単なので、以下の図を示すだけにする(理屈はよくわからない)。
++
++----------------------------------------------------------------------------
++< c_len[] の出力フォーマット >
++
++             0       CBIT{9}
++             +-------+-----------+-----------+--   --+-----------+
++             |   n   |  c_len[0] |  c_len[1] | ...     c_len[n-1]|
++             +-------+-----------+-----------+--   --+-----------+
++
++c_len[i] == 0 の場合
++
++ 0 が続く数を count とすると、
++
++ count == 0..2 の場合
++
++                pt_len[0]  
++              <----------> 
++             +------------+
++             | pt_code[0] |
++             +------------+
++
++ count == 3..18 の場合
++
++               pt_len[1]    4 bit
++              <----------> <------>
++             +------------+-------+
++             | pt_code[1] |count-3|
++             +------------+-------+
++
++ count == 19 の場合
++
++                pt_len[0]   pt_len[1]    4 bit
++              <----------> <----------> <------>
++             +------------+------------+-------+
++             | pt_code[0] | pt_code[1] |count-3|
++             +------------+------------+-------+
++
++  count >= 20 の場合
++
++                pt_len[2]    CBIT{9}
++              <----------> <------>
++             +------------+--------+
++             | pt_code[2] |count-20|
++             +------------+--------+
++
++c_len[i] != 0 の場合
++
++              pt_len[c_len[i]+2]
++             +-------------------+
++             |pt_code[c_len[i]+2]|
++             +-------------------+
++
++----------------------------------------------------------------------------
++
++こうして、文字の Huffman 符号表は、pt_len[] と pt_code[](pt_code[] は
++つまり c_len[] の Huffman 符号)を出力することで表現される。c_code[] が
++出力されてない思うかもしれないが、おそらく、decode 処理が c_len[] の値
++から計算して求めているのではないかと思われる。これは decode 処理の解読
++で明らかになるだろう。
++
++この後、send_block() は、(C) で、<off> の Huffman 符号表を出力するのだ
++が、
++
++        write_pt_len(np, pbit, -1);
++
++これは、先の pt_len[] の出力フォーマットと同じなので詳細ははしょろう。
++ただし、今度の pt_len[] の出力では write_pt_len() の第三引数 i_special 
++が -1 で指定されていて、i_special 番目の pt_len[i_special..6] に関して
++特別扱いがなくなっているところが異なる。
++
++np や pbit の意味もこの時点でわかるので一応説明しておく。np, pbit そし
++て、LHA の圧縮 method との関係は以下の表の通りなのだが、np は、<off>の
++最大bit長+1 だ。<off> の最大bit長はすなわち dicbit なので、np は、
++dicbit + 1 である。-lh4- のときにdicbit + 2 なのが不思議だが、これは歴
++史的な理由だろうと思われる。pbit は、値 np を出力するのに必要な bit 数
++なので表の通りになる。
++
++    method  dicbit  np  pbit
++   --------------------------
++    -lh4-   12      14  4
++    -lh5-   13      14  4
++    -lh6-   15      16  5
++    -lh7-   16      17  5
++
++
++まとめると LHA における圧縮ファイルの構造は以下の連続であると言えるよ
++うだ。
++
++----------------------------------------------------------------------------
++< LHA ファイルの構造(1 ブロック分) >
++
++    +-----------+
++    | blocksize |
++    +-----------+
++       16bit
++
++    +-----+--------------------+
++    | len |      pt_len        | c_lenのハフマン符号表
++    +-----+--------------------+
++      5bit        ?? bit
++      TBIT
++
++    +-------+------------------+
++    |  len  |     c_len        | 文字と長さのハフマン符号表
++    +-------+------------------+
++      9bit        ?? bit
++      CBIT
++
++    +---------+--------------------+
++    |   len   |   pt_len           | 位置のハフマン符号表
++    +---------+--------------------+
++     pbit         ?? bit
++                               (pbit=4bit(lh4,5) or 5bit(lh6,7))
++
++    +---------------------+
++    |  圧縮文             |
++    +---------------------+
++
++----------------------------------------------------------------------------
++
++ここまでの解読では細部をかなりはしょったが、decode 処理を見ればわかる
++こともあるであろうことを期待している。以降、decode 処理の内容を処理の
++流れを追うことで確認しよう。
++
++# Local Variables:
++# mode : indented-text
++# indent-tabs-mode: nil
++# End:
+diff -urN lha-1.14i-ac20030921/Makefile.am Makefile.am
+--- lha-1.14i-ac20030921/Makefile.am	Thu Nov 14 20:40:54 2002
++++ Makefile.am	Sun Sep 28 01:25:03 2003
+@@ -2,4 +2,4 @@
+ 
+ AUTOMAKE_OPTIONS = foreign
+ EXTRA_DIST = 00readme.autoconf header.doc.euc
+-SUBDIRS= man src tests olddoc
++SUBDIRS= man olddoc src tests
+diff -urN lha-1.14i-ac20030921/configure.ac configure.ac
+--- lha-1.14i-ac20030921/configure.ac	Sun Sep 21 16:07:41 2003
++++ configure.ac	Fri Sep 17 21:25:06 2004
+@@ -1,5 +1,5 @@
+ # Process this file with autoconf to produce a configure script.
+-AC_INIT([LHa for UNIX], 1.14i-ac20030921, jca02266@nifty.ne.jp, lha)
++AC_INIT([LHa for UNIX], 1.14i-ac20040918, jca02266@nifty.ne.jp, lha)
+ AC_CANONICAL_HOST
+ AC_CANONICAL_TARGET
+ AM_INIT_AUTOMAKE
+diff -urN lha-1.14i-ac20030921/src/cproto.sh src/cproto.sh
+--- lha-1.14i-ac20030921/src/cproto.sh	Thu Jan  1 01:00:00 1970
++++ src/cproto.sh	Sun Jul 20 20:26:23 2003
+@@ -0,0 +1,82 @@
++#!/bin/sh
++#
++# generate function prototypes `prototype.h'.
++#
++
++trap "rm -f prototypes.h.tmp prototypes.h.bak" 0 1 2 3 15
++
++CPROTO_FLAGS='-m -d'
++CPPFLAGS='-DSTDC_HEADERS=1
++	-DHAVE_STRDUP=1
++	-DHAVE_MEMSET=1
++	-DHAVE_MEMMOVE=1
++	-DHAVE_STRCASECMP=1
++	-DHAVE_BASENAME=1
++	-DMULTIBYTE_FILENAME=1
++	-Dinterrupt=dummy__
++	-DNEED_INCREMENTAL_INDICATOR=1
++'
++# `interrupt' is the reserved word for cproto.
++
++SOURCES='append.c bitio.c crcio.c dhuf.c extract.c header.c
++	huf.c indicator.c larc.c lhadd.c lharc.c lhext.c
++	lhlist.c maketbl.c maketree.c patmatch.c
++	shuf.c slide.c util.c
++'
++
++test -f prototypes.h && mv -f prototypes.h prototypes.h.bak
++
++# below makes cproto regard `RETSIGTYPE' as the variable type.
++cat <<END >prototypes.h
++typedef void RETSIGTYPE;
++END
++
++exec 5>&1 > prototypes.h.tmp
++
++cat <<END
++/* This file was generated by cproto. */
++#if PROTOTYPES /* defined in config.h */
++#define P_(s) s
++#else
++#define P_(s) ()
++#endif
++
++END
++
++cproto $CPROTO_FLAGS $CPPFLAGS $SOURCES |
++	sed -e '/^int main /d' -e 's/dummy__/interrupt/'
++
++cat <<END
++
++/* util.c */
++#if !HAVE_MEMMOVE
++void *memmove P_((void *dst, const void *src, size_t cnt));
++#endif
++#if !HAVE_STRDUP
++char *strdup P_((const char *buf));
++#endif
++#if !HAVE_MEMSET
++char *memset P_((char *s, int c, size_t n));
++#endif
++#if !HAVE_STRCASECMP
++int strcasecmp P_((const char *p1, const char *p2));
++#endif
++#if defined HAVE_DECL_BASENAME && !HAVE_DECL_BASENAME
++char *basename P_((char *s));
++#endif
++
++/* vsnprintf.c */
++#if !HAVE_VSNPRINTF
++int vsnprintf P_((char *str, size_t n, const char *fmt, va_list ap));
++int snprintf P_((char *str, size_t n, char const *fmt, ...));
++#endif
++
++#undef P_
++END
++
++exec 1>&5
++if test -f prototypes.h.bak && cmp -s prototypes.h.tmp prototypes.h.bak; then
++  mv -f prototypes.h.bak prototypes.h
++else
++  mv -f prototypes.h.tmp prototypes.h
++fi
+diff -urN lha-1.14i-ac20030921/src/header.c src/header.c
+--- lha-1.14i-ac20030921/src/header.c	Sun Jul 27 08:21:17 2003
++++ src/header.c	Wed Dec 17 19:32:41 2003
+@@ -424,7 +424,8 @@
+ {
+ #if HAVE_UINT64_T
+     uint64_t t;
+-    uint64_t epoch = 0x019db1ded53e8000; /* 1970-01-01 00:00:00 (UTC) */
++    uint64_t epoch = ((uint64_t)0x019db1de << 32) + 0xd53e8000;
++                     /* 0x019db1ded53e8000ULL: 1970-01-01 00:00:00 (UTC) */
+ 
+     t = (unsigned long)get_longword();
+     t |= (uint64_t)(unsigned long)get_longword() << 32;
+diff -urN lha-1.14i-ac20030921/src/lha.h src/lha.h
+--- lha-1.14i-ac20030921/src/lha.h	Sun Sep 21 15:58:52 2003
++++ src/lha.h	Fri Sep 17 21:20:57 2004
+@@ -321,6 +321,8 @@
+ EXTERN int      quiet_mode;
+ 
+ EXTERN boolean backup_old_archive;
++EXTERN boolean  extract_broken_archive;
++
+ /* ------------------------------------------------------------------------ */
+ /*  Globale Variable                                                        */
+ /* ------------------------------------------------------------------------ */
+diff -urN lha-1.14i-ac20030921/src/lharc.c src/lharc.c
+--- lha-1.14i-ac20030921/src/lharc.c	Sun Sep 21 15:58:52 2003
++++ src/lharc.c	Fri Sep 17 21:20:57 2004
+@@ -103,6 +103,8 @@
+ #else
+     backup_old_archive = FALSE;
+ #endif
++
++    extract_broken_archive = FALSE;
+ }
+ 
+ /* ------------------------------------------------------------------------ */
+@@ -132,7 +134,7 @@
+ LHa      for UNIX  V 1.00  Copyright(C) 1992  Masaru Oki\n\
+ LHa      for UNIX  V 1.14  Modified     1995  Nobutaka Watazaki\n\
+ LHa      for UNIX  V 1.14i Modified     2000  Tsugio Okamoto\n\
+-                   Autoconfiscated 2001-2003  Koji Arai\n\
++                   Autoconfiscated 2001-2004  Koji Arai\n\
+ ");
+ 
+     print_tiny_usage();
+@@ -465,6 +467,10 @@
+                     error("unknown kanji code \"%s\"", opt);
+                     return -1;
+                 }
++            }
++            else if (strncmp(opt, "extract-broken-archive",
++                             sizeof("extract-broken-archive")-1) == 0) {
++                extract_broken_archive = TRUE;
+             }
+             else {
+                 error("unknown long option \"--%s\"", opt);
+diff -urN lha-1.14i-ac20030921/src/lhext.c src/lhext.c
+--- lha-1.14i-ac20030921/src/lhext.c	Sat Jul 12 19:53:50 2003
++++ src/lhext.c	Sat May  8 00:16:10 2004
+@@ -25,6 +25,9 @@
+     NULL
+ };
+ 
++static void add_dirinfo(char* name, LzHeader* hdr);
++static void adjust_dirinfo();
++
+ /* ------------------------------------------------------------------------ */
+ static          boolean
+ inquire_extract(name)
+@@ -222,8 +225,14 @@
+         q = (char *) strrchr(hdr->name, '/') + 1;
+     }
+     else {
++        if (is_directory_traversal(q)) {
++            fprintf(stderr, "Possible directory traversal hack attempt in %s\n", q);
++            exit(111);
++        }
++
+         if (*q == '/') {
+-            q++;
++            while (*q == '/') { q++; }
++
+             /*
+              * if OSK then strip device name
+              */
+@@ -406,6 +415,8 @@
+             } else { /* make directory */
+                 if (!output_to_stdout && !make_parent_path(name))
+                     return read_size;
++                /* save directory information */
++                add_dirinfo(name, hdr);
+             }
+         }
+     }
+@@ -468,5 +479,80 @@
+     /* close archive file */
+     fclose(afp);
+ 
++    /* adjust directory information */
++    adjust_dirinfo();
++
+     return;
++}
++
++int
++is_directory_traversal(char *string)
++{
++    unsigned int type = 0; /* 0 = new, 1 = only dots, 2 = other chars than dots */
++    char *temp;
++
++    temp = string;
++
++    while (*temp != 0) {
++        if (temp[0] == '/') {
++            if (type == 1) { return 1; }
++            type = 0;
++            temp++;
++            continue;
++        }
++
++        if ((temp[0] == '.') && (type < 2))
++            type = 1;
++        if (temp[0] != '.')
++            type = 2;
++
++        temp++;
++    } /* while */
++
++    return (type == 1);
++}
++
++/*
++ * restore directory information (time stamp).
++ * added by A.Iriyama  2003.12.12
++ */
++
++typedef struct lhdDirectoryInfo_t {
++    struct lhdDirectoryInfo_t *next;
++    LzHeader hdr;
++} LzHeaderList;
++
++static LzHeaderList *dirinfo;
++
++static void add_dirinfo(char *name, LzHeader *hdr)
++{
++    LzHeaderList *p;
++
++    if (memcmp(hdr->method, LZHDIRS_METHOD, 5) != 0)
++        return;
++
++    p = xmalloc(sizeof(LzHeaderList));
++
++    memcpy(&p->hdr, hdr, sizeof(LzHeader));
++    strncpy(p->hdr.name, name, sizeof(p->hdr.name));
++    p->hdr.name[sizeof(p->hdr.name)-1] = 0;
++
++    {
++        LzHeaderList *tmp = dirinfo;
++        dirinfo = p;
++        dirinfo->next = tmp;
++    }
++}
++
++static void adjust_dirinfo()
++{
++    while (dirinfo) {
++        adjust_info(dirinfo->hdr.name, &dirinfo->hdr);
++
++        {
++            LzHeaderList *tmp = dirinfo;
++            dirinfo = dirinfo->next;
++            free(tmp);
++        }
++    }
+ }
+diff -urN lha-1.14i-ac20030921/src/makezero.c src/makezero.c
+--- lha-1.14i-ac20030921/src/makezero.c	Thu Jan  1 01:00:00 1970
++++ src/makezero.c	Mon Jan 29 19:17:02 2001
+@@ -0,0 +1,11 @@
++
++#include <stdio.h>
++
++main()
++{
++  int i;
++
++  for (i=0; i<10000; i++)
++	fputc(0, stdout);
++
++}
+diff -urN lha-1.14i-ac20030921/src/prototypes.h src/prototypes.h
+--- lha-1.14i-ac20030921/src/prototypes.h	Sun Sep 21 15:58:52 2003
++++ src/prototypes.h	Sat May  8 00:16:50 2004
+@@ -98,6 +98,7 @@
+ void lha_exit P_((int status));
+ /* lhext.c */
+ void cmd_extract P_((void));
++int is_directory_traversal P_((char *string));
+ /* lhlist.c */
+ void cmd_list P_((void));
+ /* maketbl.c */
+diff -urN lha-1.14i-ac20030921/src/slide.c src/slide.c
+--- lha-1.14i-ac20030921/src/slide.c	Sat Jul 12 18:36:31 2003
++++ src/slide.c	Fri Sep 17 21:20:57 2004
+@@ -314,7 +314,7 @@
+     init_slide();
+ 
+     encode_set.encode_start();
+-    memset(text, 0, TXTSIZ);
++    memset(text, ' ', TXTSIZ);
+ 
+     remainder = fread_crc(&crc, &text[dicsiz], txtsiz-dicsiz, infile);
+ 
+@@ -405,7 +405,20 @@
+     INITIALIZE_CRC(crc);
+     dicsiz = 1L << dicbit;
+     dtext = (unsigned char *)xmalloc(dicsiz);
+-    memset(dtext, 0, dicsiz);
++
++    if (extract_broken_archive)
++
++        /* LHa for UNIX (autoconf) had a fatal bug since version
++           1.14i-ac20030713 (slide.c revision 1.20).
++
++           This bug is possible to make a broken archive, proper LHA
++           cannot extract it (probably it report CRC error).
++
++           If the option "--extract-broken-archive" specified, extract
++           the broken archive made by old LHa for UNIX. */
++        memset(dtext, 0, dicsiz);
++    else
++        memset(dtext, ' ', dicsiz);
+     decode_set.decode_start();
+     dicsiz1 = dicsiz - 1;
+     adjust = 256 - THRESHOLD;
diff --git a/archivers/lha-ac/files/patch-lha.h b/archivers/lha-ac/files/patch-lha.h
new file mode 100644
index 000000000000..56cf5ba4b970
--- /dev/null
+++ b/archivers/lha-ac/files/patch-lha.h
@@ -0,0 +1,10 @@
+--- src/lha.h.orig	Sun Sep 21 15:58:52 2003
++++ src/lha.h	Thu Sep 23 07:10:33 2004
+@@ -16,6 +16,7 @@
+ #endif
+ 
+ #include <stdio.h>
++#include <stdlib.h>
+ #include <errno.h>
+ #include <ctype.h>
+ #include <sys/types.h>
diff --git a/archivers/lha-ac/files/patch-lharc.c b/archivers/lha-ac/files/patch-lharc.c
new file mode 100644
index 000000000000..be16dc19f33f
--- /dev/null
+++ b/archivers/lha-ac/files/patch-lharc.c
@@ -0,0 +1,51 @@
+--- src/lharc.c.orig	Sun Sep 21 15:58:52 2003
++++ src/lharc.c	Thu Sep 23 07:22:19 2004
+@@ -994,9 +994,10 @@
+     struct stat     tmp_stbuf, arc_stbuf, fil_stbuf;
+     int exist_tmp = 1, exist_arc = 1;
+ 
+-    strcpy(newname, name);
++    strncpy(newname, name, sizeof(newname));
++    newname[sizeof(newname)-1] = 0;
+     len = strlen(name);
+-    if (len > 0 && newname[len - 1] != '/') {
++    if (len > 0 && newname[len - 1] != '/' && len < (sizeof(newname)-1)) {
+         newname[len++] = '/';
+         newname[len] = 0;
+     }
+@@ -1014,12 +1015,16 @@
+ 
+     while ((dp = readdir(dirp)) != NULL) {
+         n = NAMLEN(dp);
++        if (len >= (sizeof(newname)-1)
++            || (len+n) >= (sizeof(newname)-1)
++            || n  <= 0
++            || (len+n) <= 0)
++            break;
+ 
+         /* exclude '.' and '..' */
+         if (strncmp(dp->d_name, ".", n) == 0
+             || strncmp(dp->d_name, "..", n) == 0)
+             continue;
+-
+         /* exclude exclude_files supplied by user */
+         for (i = 0; exclude_files && exclude_files[i]; i++) {
+             if (fnmatch(exclude_files[i], dp->d_name,
+@@ -1092,10 +1097,16 @@
+ #else
+     char           *p, *s;
+ 
+-    strcpy(temporary_name, archive_name);
++    strncpy(temporary_name, archive_name, sizeof(temporary_name));
++    temporary_name[sizeof(temporary_name)-1] = 0;
+     for (p = temporary_name, s = (char *) 0; *p; p++)
+         if (*p == '/')
+             s = p;
++  
++    if( sizeof(temporary_name) - ((size_t) (s-temporary_name)) - 1
++        <= strlen("lhXXXXXX"))
++        exit(-1);
++
+     strcpy((s ? s + 1 : temporary_name), "lhXXXXXX");
+ #endif
+ #ifdef HAVE_MKSTEMP
diff --git a/archivers/lha-ac/files/patch-lhext.c b/archivers/lha-ac/files/patch-lhext.c
new file mode 100644
index 000000000000..6372deb03e7c
--- /dev/null
+++ b/archivers/lha-ac/files/patch-lhext.c
@@ -0,0 +1,25 @@
+--- src/lhext.c.orig	Thu Sep 23 09:01:34 2004
++++ src/lhext.c	Thu Sep 23 09:01:34 2004
+@@ -88,7 +88,8 @@
+     register char  *p;
+ 
+     /* make parent directory name into PATH for recursive call */
+-    strcpy(path, name);
++    memset(path, 0, sizeof(path));
++    strncpy(path, name, sizeof(path)-1);
+     for (p = path + strlen(path); p > path; p--)
+         if (p[-1] == '/') {
+             *--p = '\0';
+@@ -249,8 +250,10 @@
+ 
+     if (extract_directory)
+         xsnprintf(name, sizeof(name), "%s/%s", extract_directory, q);
+-    else
+-        strcpy(name, q);
++    else {
++        strncpy(name, q, sizeof(name));
++        name[sizeof(name) - 1] = '\0';
++    }
+ 
+ 
+     /* LZHDIRS_METHODを持つヘッダをチェックする */
diff --git a/archivers/lha-ac/pkg-descr b/archivers/lha-ac/pkg-descr
new file mode 100644
index 000000000000..ca40a39722f8
--- /dev/null
+++ b/archivers/lha-ac/pkg-descr
@@ -0,0 +1,3 @@
+     LHa for UNIX with autoconf
+
+WWW: http://sourceforge.jp/projects/lha/