/*	
 *	clipzip.c
 *
 *	P/ECE Zlib
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2004 Naoyuki Sawa
 *
 *	* Sat Mar 13 13:00:00 JST 2004 Naoyuki Sawa
 *	- 1st release.
 *	* Sun Mar 14 16:52:00 JST 2004 Naoyuki Sawa
 *	- _pdeflate_uncompress()にて、ブロック毎にノードバッファのリセットを忘れていました。
 *	  たくさんのブロックを含む大きな圧縮データを展開すると、ノードバッファが消費されて行って、
 *	  いずれノード不足になり展開処理が失敗してしまっていました。
 *	  今回、このBugを修正し、ブロック毎にノードバッファをリセットするようにしました。
 *	- ノードバッファサイズを半分にしました。
 *	  これまでは2048要素確保していましたが、通常の圧縮データでは300〜400程度しか使いません。
 *	  余裕がありすぎるので、1024まで減らしました。
 *	  まだ三倍程度余裕があるのでたぶん大丈夫だと思いますが、引き続き注意が必要です。
 *	* Sun Mar 15 12:30:00 JST 2004 Naoyuki Sawa
 *	- pdeflate_uncompress()が、展開成功時に出力サイズでなく0を返していたBugを修正。
 *	  展開成功時は、正しく出力サイズを返すようになりました。
 *	- Zip展開インターフェイスを追加しました。
 *	* Sun Oct 24 13:47:00 JST 2004 Naoyuki Sawa
 *	- PUNZIPDIR.filename[]のサイズを44→128へ増やしました。
 *	  SPC音楽ファイル等において、ファイル名が内容の説明(ゲーム名+曲名,etc)になっている場合、
 *	  非常に長いファイル名が付けられていることがあったためです。
 *	* Sun Dec 19 20:21:00 JST 2004 Naoyuki Sawa
 *	- clippzl.cからclipzip.cへ名前変更しました。
 *	- 関数名のプレフィクスをp〜からzlib〜へ変更しました。
 *	  関数名のプレフィクスをpunzip〜からzip〜へ変更しました。
 *	  構\造体名のプレフィクスをP〜からZLIB〜へ変更しました。
 *	  構\造体名のプレフィクスをPUNZIP〜ZIP〜へ変更しました。
 *	  これまで、本物のZlibとの名前衝突を恐れてp〜等の名前を付けていたのですが、
 *	  上記のように名前変更しても、本物のZlibとの名前衝突は起こらないようなので、
 *	  わかりやすさを優先してzlib〜、zip〜等の名前に変更することにしました。
 */
#include "clip.h"

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

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

/* * P/ECE APIで利用する場合は、次のマクロ定義を有効にしてください。
 *   P/ECE API以外で利用する場合は、コメントアウトしてください。
 * * P/ECEで利用する場合でも、malloc()/free()を使う場合は、マクロ定義不要です。
 *   malloc()/free()を使うには、ansi_InitMalloc()を使ってヒープを初期化します。
 */
///#define malloc  pceHeapAlloc
///#define free    pceHeapFree

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

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

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

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

	return 0;
}

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

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

	return 1;
}

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

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

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

	return 0;
}

int
zlib_bitstream_get(ZLIBBITSTREAM* in, int* out, int bits)
{
	//	                        s2  s1
	//	                        /   /
	//	                      +-+----+
	//	MSB|.....xxx|xxxxxxxx|xxx.....|LSB
	//	         +--------------+    |
	//	                /       |    |
	//	              bits     pos   p
	//	  mask = 111_11111111_111

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

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

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

	v = *p++ >> s1;
	n = bits - s2;
	while(n > 0) {
		v |= *p++ << s2;
		s2 += 8;
		n -= 8;
	}

	mask = (unsigned)-1 >> (32 - bits);
	if(out) *out = v &= mask;
	in->pos += bits;

	return bits;
}

int
zlib_bitstream_align(ZLIBBITSTREAM* in, int bits)
{
	if(bits < 1 || bits > 32) return ERRNO;

	/* posをbitsの倍数に切上げます。 */
	in->pos = (in->pos + (bits - 1)) / bits * bits;

	return 0;
}

/****************************************************************************
 *	ハフマン復号
 ****************************************************************************/

int
zlib_hufftree_init(ZLIBHUFFTREE pht[/*len*/], int len, const unsigned char code_bits[/*values*/], int values)
{
	int retval, value, bits, code, index;
	unsigned short bits_count[ZLIBHUFFTREE_MAX_BITS + 1]; /* 2x16=32[byte] */
	unsigned short bits_code [ZLIBHUFFTREE_MAX_BITS + 1]; /* 2x16=32[byte] */

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

	/* ハフマン木の全ノードのnext[0,1]を、ZLIBHUFFTREE_BLANKに初期化します。 */
	memset(pht, -1, sizeof(ZLIBHUFFTREE) * len);

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

	/* 各ビット数の最初の符号を割り当てます。 */
	code = 0;
	for(bits = 1; bits <= ZLIBHUFFTREE_MAX_BITS; 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 = zlib_hufftree_add(pht, len, code, bits, value);
			if(retval < 0) return retval;
			if(retval > index) index = retval;
		}
	}

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

int
zlib_hufftree_add(ZLIBHUFFTREE pht[/*len*/], int len, int code, int code_bits, int value)
{
	int index, bit, next_index;
	ZLIBHUFFTREE* node;

	if(code_bits < 1 || code_bits > ZLIBHUFFTREE_MAX_BITS ) return ERRNO;
	if(value     < 0 || value     > ZLIBHUFFTREE_MAX_VALUE) return ERRNO;

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

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

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

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

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

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

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

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

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

	/* 後続リンクを作成する処理。 */
	index = next_index;
	node = &pht[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] != ZLIBHUFFTREE_BLANK) return ERRNO; /* ハフマン木破損 */
		node->next[bit] = (unsigned short)index;
		node++;
	}

FINAL:
	/* 値を格納します。 */
	if(node->next[bit] != ZLIBHUFFTREE_BLANK) return ERRNO; /* ハフマン木破損 */
	node->next[bit] = (unsigned short)(value | ZLIBHUFFTREE_LEAF);

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

int
zlib_hufftree_lookup(ZLIBHUFFTREE pht[/*len*/], int len, ZLIBBITSTREAM* in)
{
	int index, bit, next_index, value;
	ZLIBHUFFTREE* node;

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

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

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

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

	/* 値を取得します。 */
	value = next_index & ~ZLIBHUFFTREE_LEAF;
	if(value < 0 || value > ZLIBHUFFTREE_MAX_VALUE) return ERRNO; /* ハフマン木破損 */
	/*↑next_index=ZLIBHUFFTREE_BLANKだった場合も、これでエラー検出できます。*/

	/* 値を返します。 */
	return value;
}

/****************************************************************************
 *	Deflate形式
 ****************************************************************************/

/* Code Length code 展開の並び替え順序 (仕様) */
static const unsigned char zlib_deflate_code_length_code_order[19] = {
	16,	/* 0*/
	17,	/* 1*/
	18,	/* 2*/
	 0,	/* 3*/
	 8,	/* 4*/
	 7,	/* 5*/
	 9,	/* 6*/
	 6,	/* 7*/
	10,	/* 8*/
	 5,	/* 9*/
	11,	/*10*/
	 4,	/*11*/
	12,	/*12*/
	 3,	/*13*/
	13,	/*14*/
	 2,	/*15*/
	14,	/*16*/
	 1,	/*17*/
	15	/*18*/
};

/* Length code 257〜285 の追加ビット数とベース長 (仕様) */
typedef struct _PDEFLATELENGTHCODEINFO {
	short extra_bits;	/* 追加ビット数 */
	short length;		/* ベース長     */
} PDEFLATELENGTHCODEINFO;
static const PDEFLATELENGTHCODEINFO zlib_deflate_length_code_info[285 - 257 + 1] = {
	{0,  3},	/*257*/
	{0,  4},	/*258*/
	{0,  5},	/*259*/
	{0,  6},	/*260*/
	{0,  7},	/*261*/
	{0,  8},	/*262*/
	{0,  9},	/*263*/
	{0, 10},	/*264*/
	{1, 11},	/*265*/
	{1, 13},	/*266*/
	{1, 15},	/*267*/
	{1, 17},	/*268*/
	{2, 19},	/*269*/
	{2, 23},	/*270*/
	{2, 27},	/*271*/
	{2, 31},	/*272*/
	{3, 35},	/*273*/
	{3, 43},	/*274*/
	{3, 51},	/*275*/
	{3, 59},	/*276*/
	{4, 67},	/*277*/
	{4, 83},	/*278*/
	{4, 99},	/*279*/
	{4,115},	/*280*/
	{5,131},	/*281*/
	{5,163},	/*282*/
	{5,195},	/*283*/
	{5,227},	/*284*/
	{0,258},	/*285*/
};

/* Distance code 0〜29 の追加ビット数とベース距離 (仕様) */
typedef struct _PDEFLATEDISTANCECODEINFO {
	short extra_bits;	/* 追加ビット数 */
	short distance;		/* ベース距離   */
} PDEFLATEDISTANCECODEINFO;
static const PDEFLATEDISTANCECODEINFO zlib_deflate_distance_code_info[29 + 1] = {
	{ 0,    1},	/* 0*/
	{ 0,    2},	/* 1*/
	{ 0,    3},	/* 2*/
	{ 0,    4},	/* 3*/
	{ 1,    5},	/* 4*/
	{ 1,    7},	/* 5*/
	{ 2,    9},	/* 6*/
	{ 2,   13},	/* 7*/
	{ 3,   17},	/* 8*/
	{ 3,   25},	/* 9*/
	{ 4,   33},	/*10*/
	{ 4,   49},	/*11*/
	{ 5,   65},	/*12*/
	{ 5,   97},	/*13*/
	{ 6,  129},	/*14*/
	{ 6,  193},	/*15*/
	{ 7,  257},	/*16*/
	{ 7,  385},	/*17*/
	{ 8,  513},	/*18*/
	{ 8,  769},	/*19*/
	{ 9, 1025},	/*20*/
	{ 9, 1537},	/*21*/
	{10, 2049},	/*22*/
	{10, 3073},	/*23*/
	{11, 4097},	/*24*/
	{11, 6145},	/*25*/
	{12, 8193},	/*26*/
	{12,12289},	/*27*/
	{13,16385},	/*28*/
	{13,24577},	/*29*/
};

static int
_zlib_deflate_uncompress(ZLIBBYTESTREAM* out, ZLIBBITSTREAM* in, unsigned char code_bits[/*ZLIBHUFFTREE_MAX_VALUE + 1*/], ZLIBHUFFTREE nodes[/*PDEFLATE_NODES_LEN*/])
{
	int out_pos0 = out->pos; /* 出力バイト数を調べるため、初期位置を保存しておきます */
	//
	int retval;
	int i;
	int v;
	int bits;
	int dist;
	/* 3 header bits */
	int bfinal;
	int btype;
	/* 00 - no compression */
	int len;
	int nlen;
	/* 10 - compressed with dynamic Huffman codes */
	int hlit;
	int hdist;
	int hclen;

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

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

		/* 3 header bits
		 * [  0]: BFINAL is set if and only if this is the last block of the data set.
		 * [2:1]: BTYPE specifies how the data are compressed, as follows:
		 *	  00 - no compression
		 *	  01 - compressed with fixed Huffman codes
		 *	  10 - compressed with dynamic Huffman codes
		 *	  11 - reserved (error)
		 */
		if(zlib_bitstream_get(in, &bfinal, 1) < 0) return ERRNO;
		if(zlib_bitstream_get(in, &btype, 2) < 0) return ERRNO;

		switch(btype) {
		/*==========================================================*
		 *	00 - NO COMPRESSION
		 *==========================================================*/
		case 0:
			/* ビットストリームをバイト境界まで進めます。 */
			retval = zlib_bitstream_align(in, 8);
			if(retval < 0) return retval;

			/* +0,2: LEN is the number of data bytes in the block.
			 * +2,2: NLEN is the one's complement of LEN.
			 */
			if(zlib_bitstream_get(in, &len, 16) < 0) return ERRNO;
			if(zlib_bitstream_get(in, &nlen, 16) < 0) return ERRNO;
			if((len ^ 0xffff) != nlen) return ERRNO;

			/* 読み込んだバイト列をそのまま出力します。 */
			while(len--) {
				if(zlib_bitstream_get(in, &v, 8) < 0) return ERRNO;
				if(zlib_bytestream_put(out, v) < 0) return ERRNO;
			}

			/* このブロックの展開が完了しました。 */
			break;

		/*==========================================================*
		 *	01 - COMPRESSED WITH FIXED HUFFMAN CODES
		 *==========================================================*/
		case 1:
			/***** Literal/Length code 展開 ******/

			/* 各 Literal/Length code のビット数を設定します。(仕様) */
			memset(code_bits, 0, sizeof(unsigned char) * (ZLIBHUFFTREE_MAX_VALUE + 1));
			i = 0;					// Lit Value | Bits | Codes
			while(i <= 143) code_bits[i++] = 8;	//   0 - 143 |    8 | 00110000  - 10111111
			while(i <= 255) code_bits[i++] = 9;	// 144 - 255 |    9 | 110010000 - 111111111
			while(i <= 279) code_bits[i++] = 7;	// 256 - 279 |    7 | 0000000   - 0010111
			while(i <= 287) code_bits[i++] = 8;	// 280 - 287 |    8 | 11000000  - 11000111
								// Literal/Length values 286-287 will never actually occur in the compressed data.

			/* Literal/Length code のハフマン木を作成します。 */
			literal_length_code_tree = tree; /* 空きノードの先頭アドレスを取得 */
			retval = zlib_hufftree_init(literal_length_code_tree, tree_len, code_bits, ZLIBHUFFTREE_MAX_VALUE + 1);
			if(retval < 0) return retval;
			literal_length_code_tree_len = retval;
			tree += retval; /* 空きノードの先頭アドレスを進める */
			tree_len -= retval; /* 空きノード数を減らす */

			/***** Distance code 展開 ******/

			/* 各 Distance code のビット数を設定します。(仕様) */
			memset(code_bits, 0, sizeof(unsigned char) * (ZLIBHUFFTREE_MAX_VALUE + 1));
			i = 0;
			while(i <= 31) code_bits[i++] = 5;	// Distance codes 0-31 are represented by (fixed-length) 5 bit codes.
								// Distance codes 30-31 will never actually occur in the compression data.

			/* Distance code のハフマン木を作成します。 */
			distance_code_tree = tree; /* 空きノードの先頭アドレスを取得 */
			retval = zlib_hufftree_init(distance_code_tree, tree_len, code_bits, ZLIBHUFFTREE_MAX_VALUE + 1);
			if(retval < 0) return retval;
			distance_code_tree_len = retval;
			tree += retval; /* 空きノードの先頭アドレスを進める */
			tree_len -= retval; /* 空きノード数を減らす */

			/* データ展開処理へ。 */
			goto DECOMPRESS_DATA;

		/*==========================================================*
		 *	10 - COMPRESSED WITH DYNAMIC HUFFMAN CODES
		 *==========================================================*/
		case 2:
			/* [ 4: 0]: HLIT, # of Literal/Length codes - 257 (257〜286)
			 * [ 9: 5]: HDIST, # of Distance codes - 1        (  1〜 32)
			 * [13:10]: HCLEN, # of Code Length codes - 4     (  4〜 19)
			 */
			if(zlib_bitstream_get(in, &hlit, 5) < 0) return ERRNO;
			if(zlib_bitstream_get(in, &hdist, 5) < 0) return ERRNO;
			if(zlib_bitstream_get(in, &hclen, 4) < 0) return ERRNO;
			hlit += 257;
			if(hlit < 257 || hlit > 286) return ERRNO;
			hdist += 1;
			if(hdist < 1 || hdist > 32) return ERRNO;
			hclen += 4;
			if(hclen < 4 || hclen > 19) return ERRNO;

			/***** Code Length code 展開 ******/

			/* 各 Code Length code のビット数を読み込みます。 */
			memset(code_bits, 0, sizeof(unsigned char) * (ZLIBHUFFTREE_MAX_VALUE + 1));
			i = 0;
			while(i < hclen) {
				if(zlib_bitstream_get(in, &v, 3) < 0) return ERRNO;
				code_bits[zlib_deflate_code_length_code_order[i++]] = (unsigned char)v;
			}

			/* Code Length code のハフマン木を作成します。 */
			code_length_code_tree = tree; /* 空きノードの先頭アドレスを取得 */
			retval = zlib_hufftree_init(code_length_code_tree, tree_len, code_bits, ZLIBHUFFTREE_MAX_VALUE + 1);
			if(retval < 0) return retval;
			code_length_code_tree_len = retval;
			tree += retval; /* 空きノードの先頭アドレスを進める */
			tree_len -= retval; /* 空きノード数を減らす */

			/***** Literal/Length code 展開 ******/

			/* 各 Literal/Length code のビット数を読み込みます。 */
			memset(code_bits, 0, sizeof(unsigned char) * (ZLIBHUFFTREE_MAX_VALUE + 1));
			i = 0;
			while(i < hlit) {
				retval = zlib_hufftree_lookup(code_length_code_tree, code_length_code_tree_len, in);
				if(retval < 0) return retval;
				v = retval;
				if(v <= 15) {
					/* 0 - 15: Represent code lengths of 0 - 15 */
					code_bits[i++] = (unsigned char)v;
				} else if(v == 16) {
					/* 16: Copy the previous code length 3 - 6 times. */
					if(!i) return ERRNO; /* 前の値がない */
					v = code_bits[i - 1];
					if(zlib_bitstream_get(in, &len, 2) < 0) return ERRNO; /* 2bit: 繰り返し回数-3 */
					len += 3;
					while(len--) {
						if(i > hlit - 1) return ERRNO; /* 繰り返し回数が終端を超えた */
						code_bits[i++] = (unsigned char)v;
					}
				} else if(v == 17) {
					/* 17: Repeat a code length of 0 for 3 - 10 timnes. */
					if(zlib_bitstream_get(in, &len, 3) < 0) return ERRNO; /* 3bit: 繰り返し回数-3 */
					len += 3;
					while(len--) {
						if(i > hlit - 1) return ERRNO; /* 繰り返し回数が終端を超えた */
						code_bits[i++] = 0;
					}
				} else if(v == 18) {
					/* 18: Repeat a code length of 0 for 11 - 138 timnes. */
					if(zlib_bitstream_get(in, &len, 7) < 0) return ERRNO; /* 7bit: 繰り返し回数-11 */
					len += 11;
					while(len--) {
						if(i > hlit - 1) return ERRNO; /* 繰り返し回数が終端を超えた */
						code_bits[i++] = 0;
					}
				} else {
					return ERRNO;
				}
			}

			/* Literal/Length code のハフマン木を作成します。 */
			literal_length_code_tree = tree; /* 空きノードの先頭アドレスを取得 */
			retval = zlib_hufftree_init(literal_length_code_tree, tree_len, code_bits, ZLIBHUFFTREE_MAX_VALUE + 1);
			if(retval < 0) return retval;
			literal_length_code_tree_len = retval;
			tree += retval; /* 空きノードの先頭アドレスを進める */
			tree_len -= retval; /* 空きノード数を減らす */

			/***** Distance code 展開 ******/

			/* 各 Distance code のビット数を読み込みます。 */
			memset(code_bits, 0, sizeof(unsigned char) * (ZLIBHUFFTREE_MAX_VALUE + 1));
			i = 0;
			while(i < hdist) {
				retval = zlib_hufftree_lookup(code_length_code_tree, code_length_code_tree_len, in);
				if(retval < 0) return retval;
				v = retval;
				if(v <= 15) {
					/* 0 - 15: Represent code lengths of 0 - 15 */
					code_bits[i++] = (unsigned char)v;
				} else if(v == 16) {
					/* 16: Copy the previous code length 3 - 6 times. */
					if(!i) return ERRNO; /* 前の値がない */
					v = code_bits[i - 1];
					if(zlib_bitstream_get(in, &len, 2) < 0) return ERRNO; /* 2bit: 繰り返し回数-3 */
					len += 3;
					while(len--) {
						if(i > hdist - 1) return ERRNO; /* 繰り返し回数が終端を超えた */
						code_bits[i++] = (unsigned char)v;
					}
				} else if(v == 17) {
					/* 17: Repeat a code length of 0 for 3 - 10 timnes. */
					if(zlib_bitstream_get(in, &len, 3) < 0) return ERRNO; /* 3bit: 繰り返し回数-3 */
					len += 3;
					while(len--) {
						if(i > hdist - 1) return ERRNO; /* 繰り返し回数が終端を超えた */
						code_bits[i++] = 0;
					}
				} else if(v == 18) {
					/* 18: Repeat a code length of 0 for 11 - 138 timnes. */
					if(zlib_bitstream_get(in, &len, 7) < 0) return ERRNO; /* 7bit: 繰り返し回数-11 */
					len += 11;
					while(len--) {
						if(i > hdist - 1) return ERRNO; /* 繰り返し回数が終端を超えた */
						code_bits[i++] = 0;
					}
				} else {
					return ERRNO;
				}
			}

			/* Distance code のハフマン木を作成します。 */
			distance_code_tree = tree; /* 空きノードの先頭アドレスを取得 */
			retval = zlib_hufftree_init(distance_code_tree, tree_len, code_bits, ZLIBHUFFTREE_MAX_VALUE + 1);
			if(retval < 0) return retval;
			distance_code_tree_len = retval;
			tree += retval; /* 空きノードの先頭アドレスを進める */
			tree_len -= retval; /* 空きノード数を減らす */

			/* データ展開処理へ。 */
			goto DECOMPRESS_DATA;

		/*==========================================================*
		 *	01 - COMPRESSED WITH FIXED HUFFMAN CODES
		 *	                   AND
		 *	10 - COMPRESSED WITH DYNAMIC HUFFMAN CODES
		 *==========================================================*/
DECOMPRESS_DATA:
			for(;;) {
				/* Literal/Length code を取得します。 */
				retval = zlib_hufftree_lookup(literal_length_code_tree, literal_length_code_tree_len, in);
				if(retval < 0) return retval;
				v = retval;
				if(v <= 255) {
					/* 0 - 255: copy byte (literal byte) to output stream */
					if(zlib_bytestream_put(out, v) < 0) return ERRNO;

				} else if(v == 256) {
					/* 256: end of block */
					break;

				} else if(v <= 285) {
					/* 257 - 285: move backwords distance bytes in tye output stream,
					 *            and copy length bytes from this position to the output stream.
					 */

					/* コピー長を求めます。 */
					v -= 257;
					bits = zlib_deflate_length_code_info[v].extra_bits;
					len  = zlib_deflate_length_code_info[v].length;
					if(bits) {
						if(zlib_bitstream_get(in, &v, bits) < 0) return ERRNO;
						len += v;
					}

					/* コピー開始位置への距離を求めます。 */
					retval = zlib_hufftree_lookup(distance_code_tree, distance_code_tree_len, in);
					if(retval < 0) return retval;
					v = retval;
					if(v > 29) return ERRNO;
					bits = zlib_deflate_distance_code_info[v].extra_bits;
					dist = zlib_deflate_distance_code_info[v].distance;
					if(bits) {
						if(zlib_bitstream_get(in, &v, bits) < 0) return ERRNO;
						dist += v;
					}

					/* コピーします。 */
					i = out->pos - dist;
					if(i < 0) return ERRNO; /* 出力バッファ開始位置より前からはコピー不可 */
					while(len--) {
						v = out->buffer[i++];
						if(zlib_bytestream_put(out, v) < 0) return ERRNO;
					}

				} else {
					return ERRNO;
				}
			}

			/* このブロックの展開が完了しました。 */
			break;

		/*==========================================================*
		 *	11 - RESERVED (ERROR)
		 *==========================================================*/
		default:
			return ERRNO;
		}

	} while(!bfinal); /* 最終ブロックの展開が完了したら抜けます */

	/* 出力バイト数を返します。 */
	return out->pos - out_pos0;
}

int
zlib_deflate_uncompress(ZLIBBYTESTREAM* out, ZLIBBITSTREAM* in)
{
	int retval;
	unsigned char* code_bits/*[ZLIBHUFFTREE_MAX_VALUE + 1]*/;
	ZLIBHUFFTREE* nodes/*[PDEFLATE_NODES_LEN]*/;

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

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

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

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

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

	return retval;
}

/****************************************************************************
 *	Zlib形式
 ****************************************************************************/

int
zlib_uncompress(void* outbuf, int outlen, const void* inbuf, int inlen)
{
	ZLIBBYTESTREAM _out;
	ZLIBBYTESTREAM* out = &_out;
	//
	ZLIBBITSTREAM _in;
	ZLIBBITSTREAM* in = &_in;
	//
	int retval;
	int cmf, flg;
	int adler32;

	/* バイトストリーム(出力)を作成します。 */
	retval = zlib_bytestream_init(out, outbuf, outlen);
	if(retval < 0) return retval;

	/* ビットストリーム(入力)を作成します。 */
	retval = zlib_bitstream_init(in, inbuf, inlen);
	if(retval < 0) return retval;

	/* +0,1: CMF (Compression Method and flags)
	 *	 [3:0]: CM (Compression method)
	 *	 [7:4]: CINFO (Compression info)
	 */
	if(zlib_bitstream_get(in, &cmf, 8) < 0) return ERRNO;
	if((cmf & 0xf) != 8) return ERRNO;	/* 8:Deflate(仕様) */
	if((cmf >> 4) > (15 - 8)) return ERRNO;	/* WBITS<=15(仕様) */

	/* +1,1: FLG (FLaGs)
	 *	 [4:0]: FCHECK (check bits for CMF and FLG)
	 *	 [  5]: FDICT (preset dictionary)
	 *	 [7:6]: FLEVEL (compression level)
	 */
	if(zlib_bitstream_get(in, &flg, 8) < 0) return ERRNO;
	if(flg & (1 << 5)) return ERRNO;	/* PresetDictionary未対応 */
	if((cmf << 8 | flg) % 31) return ERRNO;	/* CheckDigit(仕様) */

	/* 展開。 */
	retval = zlib_deflate_uncompress(out, in);
	if(retval < 0) return retval;
	outlen = retval; /* 出力バイト数 */

	/* 入力ビットストリームを次のバイト境界まで進めます。 */
	retval = zlib_bitstream_align(in, 8);
	if(retval < 0) return retval;

	/* +n,4: ADLER32 (Adler-32 checksum)
	 *	 !!LITTLE-ENDIAN!!
	 */
	if(zlib_bitstream_get(in, &retval, 8) < 0) return ERRNO;
	adler32  = retval << 24;
	if(zlib_bitstream_get(in, &retval, 8) < 0) return ERRNO;
	adler32 |= retval << 16;
	if(zlib_bitstream_get(in, &retval, 8) < 0) return ERRNO;
	adler32 |= retval <<  8;
	if(zlib_bitstream_get(in, &retval, 8) < 0) return ERRNO;
	adler32 |= retval <<  0;
	retval = zlib_adler32(outbuf, outlen);
	if(retval != adler32) return ERRNO;

	return outlen;
}

int
zlib_adler32(const void* data, int len)
{
	const unsigned char* p = (const unsigned char*)data;
	int s1 = 1/*(仕様)*/;
	int s2 = 0;

	while(len--) {
		s1 = (s1 + *p++) % 65521/*(仕様)*/;
		s2 = (s1 + s2  ) % 65521/*(仕様)*/;
	}

	return s1 | s2 << 16;
}

/****************************************************************************
 *	Zip形式
 ****************************************************************************/

/* Zipファイル形式のローカルファイルヘッダを、ZIPDIR構\造体に読み込みます。
 * [in]
 *	dir		ファイル情報を格納するZIPDIR構\造体。
 *	header		ローカルファイルヘッダへのポインタ。
 * [out]
 *	戻り値		成功ならば、0を返します。
 *			失敗ならば、負の値を返します。
 */
static int
zip_getdir(ZIPDIR* dir, const ZIPLOCALFILEHEADER* header)
{
	int v;
	int filename_length;
	int extra_field_length;
	const unsigned char* p;

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

	/* local_file_header_signature[4] */
	v = header->local_file_header_signature[0]
	  | header->local_file_header_signature[1] <<  8
	  | header->local_file_header_signature[2] << 16
	  | header->local_file_header_signature[3] << 24;
	if(v != ZIPLOCALFILEHEADER_SIGNATURE) return ERRNO;

	/* version_needed_to_extract[2] */
	// 検査しません。

	/* general_purpose_bit_flag[2] */
	// 検査しません。
	// [   0]: 暗号化されています。
	//         →展開時に失敗します。
	// [ 2:1]: 圧縮形式特有のフラグです。
	//         →必要ありません。
	// [   3]: ファイルサイズとCRC-32がDataDescriptorに格納されています。
	//         →展開時に失敗します。
	//           また、これ以降のファイル情報走査にも失敗します。
	// [15:4]: 未使用です。

	/* compression_method[2] */
	v = header->compression_method[0]
	  | header->compression_method[1] << 8;
	dir->compression_method = v;

	/* last_mod_file_time[2] */
	/* last_mod_file_date[2] */
	// 使いません。

	/* crc32[4] */
	// GeneralPurposeBitFlagのbit3=1 の場合、0が格納されています。
	// →展開時に失敗します。
	v = header->crc32[0]
	  | header->crc32[1] <<  8
	  | header->crc32[2] << 16
	  | header->crc32[3] << 24;
	dir->crc32 = v;

	/* compressed_size[4] */
	// GeneralPurposeBitFlagのbit3=1 の場合、0が格納されています。
	// →展開時に失敗します。
	v = header->compressed_size[0]
	  | header->compressed_size[1] <<  8
	  | header->compressed_size[2] << 16
	  | header->compressed_size[3] << 24;
	dir->compressed_size = v;

	/* uncompressed_size[4] */
	// GeneralPurposeBitFlagのbit3=1 の場合、0が格納されています。
	// →展開時に失敗します。
	v = header->uncompressed_size[0]
	  | header->uncompressed_size[1] <<  8
	  | header->uncompressed_size[2] << 16
	  | header->uncompressed_size[3] << 24;
	dir->uncompressed_size = v;

	/* filename_length[2] */
	v = header->filename_length[0]
	  | header->filename_length[1] <<8;
	filename_length = v;

	/* extra_field_length[2] */
	v = header->extra_field_length[0]
	  | header->extra_field_length[1] <<8;
	extra_field_length = v;

	/* filename[filename_length] */
	p = (const unsigned char*)(header + 1);
	if(filename_length <= sizeof dir->filename - 1) {
		memcpy(dir->filename, p, filename_length);
	} else {
		memcpy(dir->filename, p, sizeof dir->filename - 1); /* ファイル名が長すぎる場合は、後方を省略 */
	}
	p += filename_length;

	/* extra_field[extra_field_length] */
	// 使いません。
	p += extra_field_length;

	/* file_data[compressed_size] */
	dir->file_data = p;
	p += dir->compressed_size;

	/* 次のファイル情報までの相対距離を返します。
	 * GeneralPurposeBitFlagのbit3=1の場合、FileDataの後にDataDescriptorが存在しますが、ここでは考慮していません。
	 * この関数が返した相対距離に従ってファイル情報走査位置を進めると、走査位置はDataDescriptorを指すことになり、
	 * 次回ファイル情報読み込み時のシグネチャ検査が失敗します。
	 * DataDescriptorは旧いDOS用のPKZIPで使われていた機能\みたいで、最近のZipファイルでは使われていないようです。
	 */
	return p - (const unsigned char*)header;
}

/* ファイル名を比較します。
 * [in]
 *	s1,s2		比較するファイル名。
 * [out]
 *	戻り値		一致したら、0を返します。
 *			一致しなければ、0以外の値を返します。
 * [note]
 *	* ファイル名の大文字と小文字は区別しません。
 *	  また、パス名の"/"と"\"は区別しません。
 */
static int
zip_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
zip_init(ZIP* zip, const void* data, int len)
{
	if(len < 0) return ERRNO;

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

	return 0;
}

int
zip_dir(ZIP* zip, ZIPDIR* dir)
{
	int retval;

	if(dir) {
		/* 既に終端まで走査していたら、失敗です。 */
		if(zip->dir_pos >= zip->len) return ERRNO;

		/* ファイル情報を読み込みます。 */
		retval = zip_getdir(dir, (const ZIPLOCALFILEHEADER*)&zip->data[zip->dir_pos]);
		if(retval < 0) return retval;

		/* ファイル情報走査位置を次へ進めます。 */
		zip->dir_pos += retval;
	} else {
		/* ファイル情報走査位置を先頭へ戻します。 */
		zip->dir_pos = 0;
	}

	return 0;
}

int
zip_find(ZIP* zip, const char* filename, ZIPDIR* dir)
{
	int retval;
	int dir_pos0 = zip->dir_pos; /* ファイル情報走査位置退避 */

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

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

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

int
zip_uncompress(ZIP* zip, const char* filename, void* outbuf, int outlen)
{
	int retval;
	int crc32;
	ZIPDIR dir;
	ZLIBBITSTREAM in;
	ZLIBBYTESTREAM out;

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

	switch(dir.compression_method) {
	/*==========================================================*
	 *	Method 0 - The file is stored (no compression)
	 *==========================================================*/
	case 0:
		/* 無圧縮なので、圧縮サイズと展開サイズは同じはず。 */
		if(dir.compressed_size != dir.uncompressed_size) return ERRNO;

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

		break;
	/*==========================================================*
	 *	Method 8 - The file is Deflated
	 *==========================================================*/
	case 8:
		/* 入力ストリーム初期化。 */
		retval = zlib_bitstream_init(&in, dir.file_data, dir.compressed_size);
		if(retval < 0) return retval;

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

		/* 出力バッファへ展開。 */
		retval = zlib_deflate_uncompress(&out, &in);
		if(retval < 0) return retval;
		if(retval != dir.uncompressed_size) return ERRNO; /* 出力サイズ不一致 */

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

	/* CRC検査。 */
	crc32 = zip_crc32(outbuf, dir.uncompressed_size);
	if(dir.crc32 != crc32) return ERRNO;

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

int
zip_crc32(const void* data, int len)
{
#define POLY	((1<<(31-26))|	\
		 (1<<(31-23))|	\
		 (1<<(31-22))|	\
		 (1<<(31-16))|	\
		 (1<<(31-12))|	\
		 (1<<(31-11))|	\
		 (1<<(31-10))|	\
		 (1<<(31- 8))|	\
		 (1<<(31- 7))|	\
		 (1<<(31- 5))|	\
		 (1<<(31- 4))|	\
		 (1<<(31- 2))|	\
		 (1<<(31- 1))|	\
		 (1<<(31- 0)))

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

	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 ^ 0xffffffff;

#undef POLY
}

