/*	
 *	cliplzh.c
 *
 *	P/ECE LZH
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2004 Naoyuki Sawa
 *
 *	* Wed Apr 14 12:30:00 JST 2004 Naoyuki Sawa
 *	- 作成開始。
 *	* Mon Apr 19 12:30:00 JST 2004 Naoyuki Sawa
 *	- ディレクトリ単体のエントリ(-lhd-)を無視するように変更しました。
 *	  IGNORE_DIRECTORYシンボルの説明を参照してください。
 *	* Sun Oct 24 13:47:00 JST 2004 Naoyuki Sawa
 *	- LZHDIR.pathname[]のサイズを44→128へ増やしました。
 *	  SPC音楽ファイル等において、ファイル名が内容の説明(ゲーム名+曲名,etc)になっている場合、
 *	  非常に長いファイル名が付けられていることがあったためです。
 */
#include "clip.h"

/****************************************************************************
 *	
 ****************************************************************************/

/* * エラーコードの値は、行番号を負値にしたものです。
 *   プログラムを修正すると、エラーコードも変わる可能性があります。
 *   エラーコードの値は、デバッグのためだけに利用してください。
 */
#define ERRNO	(-__LINE__)

/* * IGNORE_DIRECTORYシンボルを定義すると、ディレクトリ単体のエントリ(-lhd-)を無視します。
 *   具体的には、次のような動作となります。
 *   - lzh_dir()によるディレクトリ一覧取得で、ディレクトリ単体のエントリをスキップします。
 *   - lzh_find()によるファイルエントリ検索で、ディレクトリ単体のエントリには一致しません。
 *   - lzh_uncompress()によるファイル展開で、ディレクトリ単体を指定するとエラーを返します。
 * * ディレクトリ単体のエントリ(-lhd-)を無視することにした理由は、次のとおりです。
 *   通常は、LZHファイル作成時にディレクトリ単体を含みませんが、
 *   オプション指定により、ディレクトリ単体を含むLZHファイルを作成することも可能です。
 *   しかしながらP/ECE上での利用において、ディレクトリ単体を扱うことはまずありません。
 *   ファイルエントリ一覧にディレクトリ単体が含まれるとかえって扱いづらい場面が多いので、
 *   ディレクトリ単体のエントリを無視することにしました。
 * * IGNORE_DIRECTORYシンボルの定義を解除すると、ディレクトリ単体のエントリ(-lhd-)を無視しません。
 *   ただし前述の通り、通常のLZHファイルはディレクトリ単体のエントリを含まないので、
 *   ディレクトリ単体のエントリが存在することを前提としたプログラムを作ってはいけません。
 */
#define IGNORE_DIRECTORY

/****************************************************************************
 *	ファイルヘッダ
 ****************************************************************************/

int
lzh_chksum(const void* data, int len)
{
	int sum = 0;
	const unsigned char* p = (const unsigned char*)data;
	while(len--) sum += *p++;
	return sum & 0xff; /* 下位8ビットのみ使用 */
}

int
lzh_crc16(const void* data, int len)
{
#define POLY	((1<<(15-15))|	\
		 (1<<(15- 2))|	\
		 (1<<(15- 0)))

	const unsigned char* p = (const unsigned char*)data;
	int i, r, v;

	r = 0;

	while(len--) {
		v = *p++;
		for(i = 0; i < 8; i++) {
			if((r ^ v) & 1) {
				r = (r >> 1) ^ POLY;
			} else {
				r =  r >> 1;
			}
			v >>= 1;
		}
	}

	return r;

#undef POLY
}

int
lzh_strcmp(const char* s1, const char* s2)
{
	int c1, c2;
	do {
		c1 = tolower(*s1++ & 0xff);
		c2 = tolower(*s2++ & 0xff);
		if(c1 == '\\') c1 = '/';
		if(c2 == '\\') c2 = '/';
	} while(c1 != '\0' && c1 == c2);
	return c1 - c2;
}

int
lzh_getexthdr(LZHDIR* dir, const void* exthdr, int next_header_size, const char* filename, int filename_size)
{
	int i;
	int ext_type;
	int data_size;
	int name_length;
	char c;
	const unsigned char* p;
	const unsigned char* next_p;
	//
	int total_extheader_size = 0;
	const char* directory = NULL;
	int directory_size = 0;

	/* pは最初の拡張ヘッダを指します。 */
	p = (const unsigned char*)exthdr;

	/* 拡張ヘッダは少なくとも識別子(1バイト)と次の拡張ヘッダサイズ(2バイト)の合計3バイト以上必要です。 */
	while(next_header_size) {
		if(next_header_size < 1/*ext_type*/ + 2/*next_header_size*/) return ERRNO;
		total_extheader_size += next_header_size; /* 拡張ヘッダサイズ合計 */

		/* 次の拡張ヘッダ位置を保存。 */
		next_p = p + next_header_size;

		/* データ部分のサイズを取得。 */
		data_size = next_header_size - (1 + 2);

		/* 識別子、次の拡張ヘッダサイズを取得。 */
		ext_type = LZHBYTE(p);
		next_header_size = LZHHALF(&p[next_header_size - 2]);

		/* pはデータ部分を指します。 */
		p += 1;

		switch(ext_type) {
		case LZH_EXTTYPE_HEADER_CRC:
			/* ヘッダのCRC-16検査は行いません。
			 * ヘッダのCRC-16は、格納されているCRC-16値をクリアしてから求めなければいけません。
			 * しかし、現在の実装ではヘッダ全体をROMに置いたまま処理することを想定しているので、ヘッダ上のCRC-16値をクリアすることができません。
			 * ヘッダ全体をRAMに読み込んで処理すれば可能ですが、実際に破損ヘッダに出会うことはまずないと判断し、今回は検査しないことにしました。
			 */
			break;
		case LZH_EXTTYPE_FILENAME:
			filename = (const char*)p;
			filename_size = data_size;
			break;
		case LZH_EXTTYPE_DIRECTORY:
			directory = (const char*)p;
			directory_size = data_size;
			break;
		default:
			/* 上記以外の拡張ヘッダは無視します。 */
			break;
		}

		/* 次の拡張ヘッダ位置を復元。 */
		p = next_p;
	}

	/* ディレクトリ名とファイル名をつなげて格納します。 */
	name_length = 0;
	for(i = 0; i < directory_size; i++) {
		if(name_length == sizeof(dir->pathname) - 1) break;
		c = directory[i];
		if(c == '\xff') c = '/'; /* '\'や'/'は、'\xff'に変換して格納されています */
		dir->pathname[name_length++] = c;
	}
	/* directory[]の末尾にはセパレータが付いているはずなので、明示的な追加は不要です */
	for(i = 0; i < filename_size; i++) {
		if(name_length == sizeof(dir->pathname) - 1) break;
		c = filename[i];
		if(c == '\xff') c = '/'; /* '\'や'/'は、'\xff'に変換して格納されています */
		dir->pathname[name_length++] = c;
	}

	return total_extheader_size;
}

int
lzh_gethdr0(LZHDIR* dir, const LZHLEVEL0HEADER* header)
{
	int header_size;
	int header_sum;
	int name_length;
	const unsigned char* p;

	/* まずクリア。 */
	memset(dir, 0, sizeof(LZHDIR));

	/* ヘッダのレベルを検査。 */
	if(LZHBYTE(header->level) != 0x00) return ERRNO; /* レベル不正 */

	/* ヘッダの大きさを取得。 */
	header_size = LZHBYTE(header->header_size);

	/* ヘッダのチェックサムを検査。 */
	header_sum = lzh_chksum(header->method_id, header_size);
	if(header_sum != LZHBYTE(header->header_sum)) return ERRNO; /* チェックサム不正 */

	/* 圧縮法の種類、圧縮後のファイルサイズ、元のファイルサイズを取得。 */
	memcpy(dir->method_id, header->method_id, 5);
	dir->packed_size = LZHWORD(header->packed_size);
	dir->original_size = LZHWORD(header->original_size);

	/* pはpathnameを指します。 */
	p = (const unsigned char*)(header + 1);

	/* ファイル名(フルパス名)を取得。 */
	name_length = LZHBYTE(header->name_length);
	if(name_length <= sizeof(dir->pathname) - 1) {
		memcpy(dir->pathname, p, name_length);
	} else {
		memcpy(dir->pathname, p, sizeof(dir->pathname) - 1); /* ファイル名が長すぎる場合は後ろを省略 */
	}
	p += name_length;

	/* ファイルのCRC-16を取得。 */
	dir->file_crc = LZHHALF(p);
	p += 2;

	/* 圧縮データアドレスを格納。 */
	p = (const unsigned char*)header;
	dir->file_data = p + 1/*header_size*/ + 1/*header_sum*/ + header_size;

	return 1/*header_size*/ + 1/*header_sum*/ + header_size + dir->packed_size;
}

int
lzh_gethdr1(LZHDIR* dir, const LZHLEVEL1HEADER* header)
{
	int header_size;
	int header_sum;
	int skip_size;
	int filename_size;
	int next_header_size;
	int total_extheader_size;
	const char* filename;
	const unsigned char* p;

	/* まずクリア。 */
	memset(dir, 0, sizeof(LZHDIR));

	/* ヘッダのレベル、予約フィールドを検査。 */
	if(LZHBYTE(header->level) != 0x01) return ERRNO; /* レベル不正 */
	if(LZHBYTE(header->reserved) != 0x20) return ERRNO; /* 予約フィールド不正 */

	/* 基本ヘッダの大きさを取得。 */
	header_size = LZHBYTE(header->header_size);

	/* 基本ヘッダのチェックサムを検査。 */
	header_sum = lzh_chksum(header->method_id, header_size);
	if(header_sum != LZHBYTE(header->header_sum)) return ERRNO; /* チェックサム不正 */

	/* 圧縮法の種類、スキップサイズ、元のファイルサイズを取得。 */
	memcpy(dir->method_id, header->method_id, 5);
	skip_size = LZHWORD(header->skip_size);
	dir->original_size = LZHWORD(header->original_size);

	/* pはfilenameを指します。 */
	p = (const unsigned char*)(header + 1);

	/* ファイル名(ファイル名のみ)を取得。
	 * header->name_length=0ならば、ファイル名も拡張ヘッダに格納されています。
	 * 拡張ヘッダ内にファイル名を見つけたら、ここで取得した値を上書きします。
	 */
	filename = (const char*)p;
	filename_size = LZHBYTE(header->name_length);
	p += filename_size;

	/* ファイルのCRC-16を取得。 */
	dir->file_crc = LZHHALF(p);
	p += 2;

	/* pはnext_header_sizeを指します。 */
	p = (const unsigned char*)header;
	p += 1/*header_size*/ + 1/*header_sum*/ + header_size - 2/*next_header_size*/;

	/* 最初の拡張ヘッダサイズを取得。 */
	next_header_size = LZHHALF(p);

	/* pは最初の拡張ヘッダを指します。 */
	p += 2/*next_header_size*/;

	/* 拡張ヘッダを読み込みます。 */
	total_extheader_size = lzh_getexthdr(dir, p, next_header_size, filename, filename_size);
	if(total_extheader_size < 0) return total_extheader_size;

	/* 圧縮後のファイルサイズ、圧縮データアドレスを格納。 */
	dir->packed_size = skip_size - total_extheader_size;
	dir->file_data = p + total_extheader_size;

	return 1/*header_size*/ + 1/*header_sum*/ + header_size + skip_size;
}

int
lzh_gethdr2(LZHDIR* dir, const LZHLEVEL2HEADER* header)
{
	int total_header_size;
	int next_header_size;
	int total_extheader_size;
	const unsigned char* p;

	/* まずクリア。 */
	memset(dir, 0, sizeof(LZHDIR));

	/* ヘッダのレベル、予約フィールドを検査。 */
	if(LZHBYTE(header->level) != 0x02) return ERRNO; /* レベル不正 */
	if(LZHBYTE(header->reserved) != 0x20) return ERRNO; /* 予約フィールド不正 */

	/* 全ヘッダの大きさを取得。 */
	total_header_size = LZHBYTE(header->total_header_size);

	/* 圧縮法の種類、圧縮後のファイルサイズ、元のファイルサイズ、ファイルのCRC-16を取得。 */
	memcpy(dir->method_id, header->method_id, 5);
	dir->packed_size = LZHWORD(header->packed_size);
	dir->original_size = LZHWORD(header->original_size);
	dir->file_crc = LZHHALF(header->file_crc);

	/* 最初の拡張ヘッダサイズを取得。 */
	next_header_size = LZHHALF(header->next_header_size);

	/* pは最初の拡張ヘッダを指します。 */
	p = (const unsigned char*)(header + 1);

	/* 拡張ヘッダを読み込みます。 */
	total_extheader_size = lzh_getexthdr(dir, p, next_header_size, NULL, 0);
	if(total_extheader_size < 0) return total_extheader_size;

	/* 圧縮データアドレスを格納。
	 * レベル2ヘッダの場合、拡張ヘッダの後にパディング領域が存在する場合があるので、
	 *	dir->file_data = p + total_extheader_size
	 * としてはいけません。
	 * total_header_sizeはパディング領域も含んだサイズなので、次のように計算します。
	 */
	p = (const unsigned char*)header;
	dir->file_data = p + total_header_size;

	return total_header_size + dir->packed_size;
}

/****************************************************************************
 *	出力バイトストリーム
 ****************************************************************************/

int
lzh_bytestream_init(LZHBYTESTREAM* out, void* buffer, int len)
{
	if(len < 0) return ERRNO;

	memset(out, 0, sizeof(LZHBYTESTREAM));
	out->buffer = (unsigned char*)buffer;
	out->len = len;

	return 0;
}

int
lzh_bytestream_put(LZHBYTESTREAM* out, int value)
{
	if(out->pos >= out->len) return ERRNO;

	out->buffer[out->pos++] = (unsigned char)value;

	return 1;
}

/****************************************************************************
 *	入力ビットストリーム
 ****************************************************************************/

int
lzh_bitstream_init(LZHBITSTREAM* in, const void* data, int len)
{
	if((len < 0) || (len > INT_MAX / 8 - 1)) return ERRNO;

	memset(in, 0, sizeof(LZHBITSTREAM));
	in->data = (const unsigned char*)data;
	in->len = len * 8; /* bit単位 */

	return 0;
}

int
lzh_bitstream_get(LZHBITSTREAM* in, int* out, int bits)
{
	//	       s1  s2                 
	//	       /   /                  
	//	    +----+-+                  
	//	LSB|.....xxx|xxxxxxxx|xxx.....|MSB
	//	    |    +--------------+     
	//	    p    |      /             
	//	        pos   bits            

	int v, n, s1, s2;
	const unsigned char* p;

	if(bits < 0 || bits > 32) return ERRNO;
	if(in->pos + bits > in->len) return ERRNO;

	/* 32bit値に対する32bitシフトは、C言語仕様的にはアウトです。
	 * 32bitシフトを避けるために、bits=0の場合を別処理とします。
	 */
	if(!bits) {
		*out = 0;
		return 0;
	}

	p = &in->data[in->pos / 8];
	s1 = in->pos & 7;
	s2 = 8 - s1;

	v = (*p++ << 24) << s1;
	n = bits - s2;
	while(n > 0) {
		v |= (unsigned)(*p++ << 24) >> s2;
		//   ~~~~~~~~~~明示的な型変換が必要です。
		//             (unsigned char)に対して<<演算子を使うと、暗黙の変換で(int)になります。
		//             (int)のまま>>演算子を使うと、最上位ビットが符号拡張されてしまいます。
		//             最上位ビットが符号拡張されないよう、明示的に(unsigned)に変換します。
		s2 += 8;
		n -= 8;
	}

	*out = (unsigned)v >> (32 - bits);
	in->pos += bits;

	return bits;
}

/****************************************************************************
 *	二分木 (binary tree)
 ****************************************************************************/

int
lzh_binarytree_init(LZHBINARYTREE tree[/*len*/], int len, const unsigned char code_bits[/*values*/], int values)
{
	int retval;
	int value;
	int bits;
	int code;
	int index;
	unsigned short bits_count[LZHBINARYTREE_MAXBITS + 1]; /* 2x17=34[byte] */
	unsigned short bits_code [LZHBINARYTREE_MAXBITS + 1]; /* 2x17=34[byte] */

	if(values < 0 || values > LZHBINARYTREE_MAXVALUE + 1) return ERRNO;

	/* 二分木の全ノードのnext[0,1]を、LZHBINARYTREE_BLANKに初期化します。 */
	memset(tree, -1, sizeof(LZHBINARYTREE) * len);

	/* 各符号ビット数が割り当てられた値の数を数えます。 */
	memset(bits_count, 0, sizeof bits_count);
	for(value = 0; value < values; value++) {
		bits = code_bits[value];
		if(bits > LZHBINARYTREE_MAXBITS) return ERRNO;
		if(bits) bits_count[bits]++; /* 符号ビット数0の値は不使用 */
	}

	/* 各ビット数の最初の符号を割り当てます。 */
	code = 0;
	for(bits = 1; bits <= LZHBINARYTREE_MAXBITS; bits++) {
		code = (code + bits_count[bits - 1]) << 1;
		bits_code[bits] = (unsigned short)code;
	}

	/* 各値に符号を割り当て、二分木に{符号、値}のペアを追加します。 */
	index = -1; /* 値を格納したノードインデクスの最大値 */
	for(value = 0; value < values; value++) {
		bits = code_bits[value];
		if(bits) { /* 0ビット符号の値(=未使用)は追加しません */
			code = bits_code[bits]++;
			retval = lzh_binarytree_add(tree, len, code, bits, value);
			if(retval < 0) return retval;
			if(retval > index) index = retval;
		}
	}

	/* 使用したノード数(=値を格納したノードインデクスの最大値+1)を返します。 */
	return index + 1;
}

int
lzh_binarytree_add(LZHBINARYTREE tree[/*len*/], int len, int code, int code_bits, int value)
{
	int index;
	int bit;
	int next_index;
	LZHBINARYTREE* node;

	if(code_bits < 1 || code_bits > LZHBINARYTREE_MAXBITS ) return ERRNO;
	if(value     < 0 || value     > LZHBINARYTREE_MAXVALUE) return ERRNO;

	/* 既存のリンクをたどる処理。 */
	index = 0;
	for(;;) {
		/* ノードを取得します。 */
		if(index > len - 1) return ERRNO; /* 二分木破損 */
		node = &tree[index];

		/* 残り符号ビット数を減らします。 */
		code_bits--;

		/* 探索方向(0or1)を取得します。 */
		bit = (code >> code_bits) & 1;

		/* 最後のビットなら、値格納へ。 */
		if(!code_bits) goto FINAL;

		/* 次のノードインデクスを取得します。 */
		next_index = node->next[bit];

		/* リンクが途切れたら、抜けます。 */
		if(next_index == LZHBINARYTREE_BLANK) break;

		/* ノードインデクスを更新し、ループ。 */
		if(next_index <= index) return ERRNO; /* 前方へ戻ることはありえない */
		index = next_index;
		if(index & LZHBINARYTREE_LEAF) return ERRNO; /* 二分木破損 */
	}

	/* 現在のノードより後ろで、両方向とも空きのノードを探します。
	 * ~~~~~~~~~~~~~~~~~~~~重要!!現在のノードも両方向とも空きの可能性があります。
	 */
	for(next_index = index + 1; next_index < len; next_index++) {
		if(tree[next_index].next[0] == LZHBINARYTREE_BLANK &&
		   tree[next_index].next[1] == LZHBINARYTREE_BLANK) break;
	}
	if(next_index == len) return ERRNO; /* ノード不足 */

	/* 最初の空きノードへリンクします。 */
	node->next[bit] = (unsigned short)next_index;

	/* 後続リンクを作成する処理。 */
	index = next_index;
	node = &tree[index];
	for(;;) {
		/* 残り符号ビット数を減らします。 */
		code_bits--;

		/* 探索方向(0or1)を取得します。 */
		bit = (code >> code_bits) & 1;

		/* 最後のビットなら、値格納へ。 */
		if(!code_bits) goto FINAL;

		/* 次のノードへリンクします。 */
		index++;
		if(index > len - 1) return ERRNO; /* ノード不足 */
		if(node->next[bit] != LZHBINARYTREE_BLANK) return ERRNO; /* 二分木破損 */
		node->next[bit] = (unsigned short)index;
		node++;
	}

FINAL:
	/* 値を格納します。 */
	if(node->next[bit] != LZHBINARYTREE_BLANK) return ERRNO; /* 二分木破損 */
	node->next[bit] = (unsigned short)(value | LZHBINARYTREE_LEAF);

	/* 値を格納したノードのインデクスを返します。 */
	return index;
}

int
lzh_binarytree_lookup(LZHBINARYTREE tree[/*len*/], int len, LZHBITSTREAM* in, int* out)
{
	int index;
	int bit;
	int next_index;
	int value;
	LZHBINARYTREE* node;

	/* 既存のリンクをたどる処理。 */
	index = 0;
	for(;;) {
		/* ノードを取得します。 */
		if(index > len - 1) return ERRNO; /* 二分木破損 */
		node = &tree[index];

		/* 符号を1ビット読み込みます。 */
		if(lzh_bitstream_get(in, &bit, 1) < 0) return ERRNO;

		/* 次のノードインデクスを取得します。 */
		next_index = node->next[bit];
		if(next_index & LZHBINARYTREE_LEAF) break; /* リーフ(or空き)ならば抜けます */

		/* ノードインデクスを更新し、ループ。 */
		if(next_index <= index) return ERRNO; /* 前方へ戻ることはありえない */
		index = next_index;
	}

	/* 値を取得します。 */
	value = next_index & ~LZHBINARYTREE_LEAF;
	if(value < 0 || value > LZHBINARYTREE_MAXVALUE) return ERRNO; /* 二分木破損 */
	/*↑next_index=LZHBINARYTREE_BLANKだった場合も、これでエラー検出できます。*/

	/* 値を格納します。 */
	*out = value;

	return 0;
}

/****************************************************************************
 *	-lh5-展開サブルーチン
 ****************************************************************************/

/* * lzh_uncompress_lh5()で確保する、二分木ノードバッファの要素数です。
 *   Code Length code、Literal/Length code、Distance code 各ツリーは、このノードバッファ上に作成します。
 *   三つのツリーの合計ノード数がノードバッファ要素数を超えると、展開処理が失敗しエラーを返します。
 * * 最大合計ノード数は理論で求められないようなので、実験で調整するしかありません。
 *   いくつかの圧縮データで試してみたところ、三つのツリーの合計ノード数は300〜400程度となりました。
 *   1024も取っておけば充分すぎると思いますが、もしも1024を超えることがあれば、再調整してください。
 */
#define LH5_NODES_LEN	1024	/* ※調整可※ */

int
lzh_uncompress_lh5(LZHDIR* dir, LZHBYTESTREAM* out, LZHBITSTREAM* in)
{
	int retval;
	unsigned char* code_bits/*[LZHBINARYTREE_MAXVALUE + 1]*/;
	LZHBINARYTREE* nodes/*[LH5_NODES_LEN]*/;

	/* 符号ビット数配列用メモリを確保します。 */
	code_bits = (unsigned char*)malloc(sizeof(unsigned char) * (LZHBINARYTREE_MAXVALUE + 1));
	if(!code_bits) {
		return ERRNO;
	}

	/* 二分木ノードバッファ用メモリを確保します。 */
	nodes = (LZHBINARYTREE*)malloc(sizeof(LZHBINARYTREE) * LH5_NODES_LEN);
	if(!nodes) {
		free(code_bits);
		return ERRNO;
	}

	/* 展開処理の本体を呼び出します。 */
	retval = _lzh_uncompress_lh5(dir, out, in, code_bits, nodes, LH5_NODES_LEN);

	/* 二分木ノードバッファ用メモリを開放します。 */
	free(nodes);

	/* 符号ビット数配列用メモリを開放します。 */
	free(code_bits);

	return retval;
}

int
_lzh_uncompress_lh5(LZHDIR* dir, LZHBYTESTREAM* out, LZHBITSTREAM* in,
	unsigned char code_bits[/*LZHBINARYTREE_MAXVALUE + 1*/], LZHBINARYTREE nodes[/*nodes_len*/], int nodes_len)
{
	int retval;
	int blocksize;
	int values;
	int value;
	int code;
	int zerocount_3to5;
	int bitlength;
	int length;
	int distance;

	LZHBINARYTREE* tree;				/* ノードバッファの空き要素先頭ノード */
	int tree_len;					/* ノードバッファの残り空き要素数 */
	//
	LZHBINARYTREE* code_length_code_tree;		/* Code Length code ツリーの先頭ノード */
	int code_length_code_tree_len;			/* Code Length code ツリーのノード数 */
	//
	LZHBINARYTREE* literal_length_code_tree;	/* Literal/Length code ツリーの先頭ノード */
	int literal_length_code_tree_len;		/* Literal/Length code ツリーのノード数 */
	//
	LZHBINARYTREE* distance_code_tree;		/* Distance code ツリーの先頭ノード */
	int distance_code_tree_len;			/* Distance code ツリーのノード数 */

	while(out->pos < dir->original_size) {
		/* ブロックサイズを取得します。 */
		if(lzh_bitstream_get(in, &blocksize, 16) < 0) return ERRNO;
		if(!blocksize) blocksize = 1 << 16; /* 1〜64K */

		/* ノードバッファをリセットします。★忘れないで!!★ */
		tree = nodes;
		tree_len = nodes_len;

		/***** Code Length code ツリー展開 *****/

		ASSERT(LZHBINARYTREE_MAXVALUE >= 18);
		memset(code_bits, 0, 18 + 1);
		if(lzh_bitstream_get(in, &values, 5) < 0) return ERRNO;
		if(values > 18 + 1) return ERRNO;
		if(!values) {
			if(lzh_bitstream_get(in, &value, 5) < 0) return ERRNO;
			if(value > 18) return ERRNO;
			code_bits[value] = 1;
		} else {
			for(value = 0; value < values; value++) {
				if(value == 3) {
					if(lzh_bitstream_get(in, &zerocount_3to5, 2) < 0) return ERRNO;
					if(zerocount_3to5) { /* 3〜5までの間で0が連続する数 */
						value += zerocount_3to5 - 1;
						continue;
					}
				}
				retval = lzh_bitlength_decode_lh5(in, &bitlength);
				if(retval < 0) return retval;
				code_bits[value] = (unsigned char)bitlength;
			}
		}
		retval = lzh_binarytree_init(tree, tree_len, code_bits, 18 + 1);
		if(retval < 0) DIE();
		code_length_code_tree = tree;
		code_length_code_tree_len = retval;
		tree += retval;
		tree_len -= retval;

		/***** Literal/Length code ツリー展開 *****/

		memset(code_bits, 0, LZHBINARYTREE_MAXVALUE + 1);
		if(lzh_bitstream_get(in, &values, 9) < 0) return ERRNO;
		if(values > LZHBINARYTREE_MAXVALUE + 1) return ERRNO;
		if(!values) {
			if(lzh_bitstream_get(in, &value, 9) < 0) return ERRNO;
			if(value > LZHBINARYTREE_MAXVALUE) return ERRNO;
			code_bits[value] = 1;
		} else {
			for(value = 0; value < values; value++) {
				retval = lzh_binarytree_lookup(code_length_code_tree, code_length_code_tree_len, in, &code);
				if(retval < 0) return retval;
				if(code < 0) {
					return ERRNO;
				} else if(code == 0) {	/* code=0 => bits=0 */
					/** no job **/
				} else if(code == 1) {	/* code=1 => bits=0×3〜18 */
					if(lzh_bitstream_get(in, &code, 4) < 0) return ERRNO;
					value +=  3 + code - 1;
				} else if(code == 2) {	/* code=2 => bits=0×20〜531 */
					if(lzh_bitstream_get(in, &code, 9) < 0) return ERRNO;
					value += 20 + code - 1;
				} else if(code <= 18) {	/* code=3〜18 => bits=1〜16 */
					code_bits[value] = (unsigned char)(1 + (code - 3));
				} else {
					return ERRNO;
				}
			}
		}
		retval = lzh_binarytree_init(tree, tree_len, code_bits, LZHBINARYTREE_MAXVALUE + 1);
		if(retval < 0) DIE();
		literal_length_code_tree = tree;
		literal_length_code_tree_len = retval;
		tree += retval;
		tree_len -= retval;

		/***** Distance code ツリー展開 *****/

		ASSERT(LZHBINARYTREE_MAXVALUE >= 13); /* 2^13=8KB */
		memset(code_bits, 0, 13 + 1);
		if(lzh_bitstream_get(in, &values, 4) < 0) return ERRNO;
		if(values > 13 + 1) return ERRNO;
		if(!values) {
			if(lzh_bitstream_get(in, &value, 4) < 0) return ERRNO;
			if(value > 13) return ERRNO;
			code_bits[value] = 1;
		} else {
			for(value = 0; value < values; value++) {
				retval = lzh_bitlength_decode_lh5(in, &bitlength);
				if(retval < 0) return retval;
				code_bits[value] = (unsigned char)bitlength;
			}
		}
		retval = lzh_binarytree_init(tree, tree_len, code_bits, 13 + 1);
		if(retval < 0) DIE();
		distance_code_tree = tree;
		distance_code_tree_len = retval;
		tree += retval;
		tree_len -= retval;

		/***** スライド辞書による復号メイン処理 *****/

		do {
			/* Literal/Length 復号。 */
			retval = lzh_binarytree_lookup(literal_length_code_tree, literal_length_code_tree_len, in, &code);
			if(retval < 0) return retval;

			if(code < 256) {
				/* Literal */
				if(lzh_bytestream_put(out, code) < 0) return ERRNO;
			} else {
				/* Length & Distance */
				length = 3 + (code - 256);
				retval = lzh_distance_decode_lh5(distance_code_tree, distance_code_tree_len, in, &distance);
				if(retval < 0) return retval;
				if(distance > out->pos) return ERRNO; /* 出力バッファ開始位置より前からはコピー不可 */
				do {
					if(lzh_bytestream_put(out, out->buffer[out->pos - distance]) < 0) return ERRNO;
				} while(--length);
			}
		} while(--blocksize > 0);
	}

	return out->pos;
}

int
lzh_bitlength_decode_lh5(LZHBITSTREAM* in, int* out)
{
	int bitlength;
	int x;

	/*	ビット長	ビットパターン
	 *	 0		000
	 *	 1		001
	 *	 2		010
	 *	 3		011
	 *	 4		100
	 *	 5		101
	 *	 6		110
	 *	 7		1110
	 *	 8		11110
	 *	 9		111110
	 *	10		1111110
	 *	11		11111110
	 *	12		111111110
	 *	13		1111111110
	 *	14		11111111110
	 *	15		111111111110
	 *	16		1111111111110
	 */
	if(lzh_bitstream_get(in, &bitlength, 3) < 0) return ERRNO;
	if(bitlength == 7) {
		for(;;) {
			if(lzh_bitstream_get(in, &x, 1) < 0) return ERRNO;
			if(!x) break;
			bitlength++;
			if(bitlength > 16) return ERRNO;
		}
	}
	*out = bitlength;

	return 0;
}

int
lzh_distance_decode_lh5(LZHBINARYTREE* distance_code_tree, int distance_code_tree_len, LZHBITSTREAM* in, int* out)
{
	int retval;
	int bitlength;
	int distance;

	/*	距離		ビットパターン
	 *	1+0		0000
	 *	1+1		0001
	 *	1+2〜3		0010n
	 *	1+4〜7		0011nn
	 *	1+8〜15		0100nnn
	 *	1+16〜31	0101nnnn
	 *	1+32〜63	0110nnnnn
	 *	1+64〜127	0111nnnnnn
	 *	1+128〜255	1000nnnnnnn
	 *	1+256〜511	1001nnnnnnnn
	 *	1+512〜1023	1010nnnnnnnnn
	 *	1+1024〜2047	1011nnnnnnnnnn
	 *	1+2048〜4095	1100nnnnnnnnnnn
	 *	1+4096〜8191	1101nnnnnnnnnnnn
	 */
	retval = lzh_binarytree_lookup(distance_code_tree, distance_code_tree_len, in, &bitlength);
	if(bitlength < 0) {
		return ERRNO;
	} else if(bitlength == 0) {
		distance = 0;
	} else if(bitlength <= 13) { /* 2^13=8KB */
		bitlength--;
		if(lzh_bitstream_get(in, &distance, bitlength) < 0) return ERRNO;
		distance |= 1 << bitlength;
	} else {
		return ERRNO;
	}
	*out = 1 + distance;

	return 0;
}

/****************************************************************************
 *	LZHデコーダ
 ****************************************************************************/

int
lzh_init(LZH* lzh, const void* data, int len)
{
	if(len < 0) return ERRNO;

	memset(lzh, 0, sizeof(LZH));
	lzh->data = (const unsigned char*)data;
	lzh->len = len;

	return 0;
}

int
lzh_dir(LZH* lzh, LZHDIR* dir)
{
	int retval;
	const unsigned char* header;

	if(dir) {
#ifdef IGNORE_DIRECTORY
		do {
#endif /*IGNORE_DIRECTORY*/
			/* エンドマーク(0x00)を検出したら、まだデータが残っていても走査終了とします。
			 * 有効なヘッダの1バイト目が0x00であってはいけません。
			 * 特にレベル2ヘッダの場合、total_header_sizeの下位バイトが0x00にならないよう、
			 * 必要に応じてパディングを追加し、ヘッダサイズを調整してあります。(エンコーダの仕事)
			 */
			if(lzh->dir_pos < lzh->len && !lzh->data[lzh->dir_pos]) return ERRNO;

			/* 残りデータがヘッダサイズに満たなければ、走査失敗です。
			 * レベル0〜2のヘッダはいずれもオフセット20の位置にレベルが格納されています。
			 * 従って、少なくとも現在位置より後ろに21バイト以上なければ終端と見なします。
			 * 正しいLZHファイルの終端は、前述のエンドマークにて示されるはずです。
			 * ここで終端を検出した場合、エンドマーク欠落やファイル破損の可能性があります。
			 */
			if(lzh->len - lzh->dir_pos < 21) return ERRNO;

			/* ファイル情報を読み込みます。 */
			header = &lzh->data[lzh->dir_pos];
			switch(header[20]) {
			case 0:	/* レベル0ヘッダ */
				retval = lzh_gethdr0(dir, (const LZHLEVEL0HEADER*)header);
				break;
			case 1:	/* レベル1ヘッダ */
				retval = lzh_gethdr1(dir, (const LZHLEVEL1HEADER*)header);
				break;
			case 2:	/* レベル2ヘッダ */
				retval = lzh_gethdr2(dir, (const LZHLEVEL2HEADER*)header);
				break;
			default:
				return ERRNO;
			}

			/* ファイル情報走査位置を次へ進めます。 */
			lzh->dir_pos += retval;
#ifdef IGNORE_DIRECTORY
		} while(memcmp(dir->method_id, "-lhd-", 5) == 0); /* ディレクトリ単体ならば、無視します */
#endif /*IGNORE_DIRECTORY*/
	} else {
		/* ファイル情報走査位置を先頭へ戻します。 */
		lzh->dir_pos = 0;
	}

	return 0;
}

int
lzh_find(LZH* lzh, const char* pathname, LZHDIR* dir)
{
	int retval;
	int dir_pos0 = lzh->dir_pos; /* ファイル情報走査位置退避 */

	/* ファイル情報走査位置を先頭へ戻します。 */
	lzh_dir(lzh, NULL);
	for(;;) {
		/* ファイル情報を読み込みます。 */
		retval = lzh_dir(lzh, dir);
		if(retval < 0) break;

		/* ファイル名を比較します。 */
		if(lzh_strcmp(dir->pathname, pathname) == 0) {
			retval = 0;
			break;
		}
	}

	lzh->dir_pos = dir_pos0; /* ファイル情報走査位置復元 */
	return retval;
}

int
lzh_uncompress(LZH* lzh, const char* pathname, void* outbuf, int outlen)
{
	int retval;
	int crc16;
	LZHDIR dir;
	LZHBITSTREAM in;
	LZHBYTESTREAM out;

	/* ファイル情報を探します。 */
	retval = lzh_find(lzh, pathname, &dir);
	if(retval < 0) return retval;
	if(dir.original_size > outlen) return ERRNO; /* 出力バッファ不足 */

	if(dir.method_id[0] == '-' &&
	   dir.method_id[1] == 'l' &&
	   dir.method_id[2] == 'h' &&
	   dir.method_id[4] == '-') {
		switch(dir.method_id[3]) {
		/*==========================================================*
		 *	-lh0-	無圧縮
		 *==========================================================*/
		case '0':
			/* 無圧縮なので、圧縮サイズと展開サイズは同じはず。 */
			if(dir.packed_size != dir.original_size) return ERRNO;

			/* 無圧縮データを出力バッファにコピーします。 */
			memcpy(outbuf, dir.file_data, dir.original_size);

			break;

		/*==========================================================*
		 *	-lh5-	8KBスライド辞書圧縮
		 *==========================================================*/
		case '5':
			/* 入力ストリームを初期化します。 */
			retval = lzh_bitstream_init(&in, dir.file_data, dir.packed_size);
			if(retval < 0) return retval;

			/* 出力ストリームを初期化します。 */
			retval = lzh_bytestream_init(&out, outbuf, outlen);
			if(retval < 0) return retval;

			/* 展開します。 */
			retval = lzh_uncompress_lh5(&dir, &out, &in);
			if(retval < 0) return retval;
			if(retval != dir.original_size) return retval; /* 出力サイズ不一致 */

			break;

		/*==========================================================*
		 *	-lhd-	ディレクトリ
		 *==========================================================*/
		case 'd':
			return ERRNO; /* 未対応 */

		/*==========================================================*
		 *	その他の圧縮形式には未対応です。
		 *==========================================================*/
		default:
			return ERRNO; /* 未対応 */
		}
	}

	/* CRC検査。 */
	crc16 = lzh_crc16(outbuf, dir.original_size);
	if(dir.file_crc != crc16) return ERRNO;

	/* 出力サイズを返します。 */
	return dir.original_size;
}

