/* * Wed Aug 26 01:00:19 JST 2009 Naoyuki Sawa
 * - ツリーを使ってフレーズ辞書を管理し、LZSS圧縮を高速化するコードです。以下の本を参考にしました。
 *   「データ圧縮ハンドブック―Ｃプログラマのための圧縮技法紹介」(トッパン) 第8章 移動窓による圧縮 8.3 プログラム
 * - おおよそ、上記の資料に載っているプログラムと同じですが、一部、おかしいと感じた点があったので、修正しました。
 *   上記の資料のプログラムは、ノード0番を空ノードに割り当てていますが、有効なフレーズ位置に対しても、0番ノードが使用され得るように見えます。
 *   0番ノードに登録されたフレーズは探索対象とならず、僅かに圧縮効率を低下しているように思います。
 *   4096分の1のフレーズが無効になるだけなので、ほとんど影響は無いのですが、少し気になりました。(この推測が当たっているかどうか、未検証です。)
 *   以下のプログラムは、有効なフレーズ位置に対するノードと、空ノードの位置が被らないよう、空ノードの位置を変更して作成しました。
 * - 本モジュールのコードは、LZSS圧縮の機能全体を提供するものではなく、フレーズ辞書のツリーを管理し、探索する基本機能のみを提供します。
 *   本モジュールのコードを使って、どのような圧縮バイナリフォーマットへ出力するかは、利用側のコードに委ねられています。
 *   利用例は、"lzss1.c"と"lzss2.c"を参照してください。
 */

/****************************************************************************
 *	LZSS基本ルーチン
 ****************************************************************************/

#if 0  /*{{このファイルをインクルードする箇所で設定してください。*/
#define LZSS_DEBUG	/* このシンボルを定義すると、慎重に検査しながら実行します。プログラムのバグ検出用です。プログラムが安定したら、コメントアウトしてください。 */
//{{調整可
//typedef const unsigned char LZSS_CHAR;	/* フレーズを構成する文字単位 */
typedef const unsigned short LZSS_CHAR;		/* フレーズを構成する文字単位 */
#define LZSS_MATCH_LEN_MAX	(15 + 2)	/* フレーズにマッチする最大長。最小長は0だが、一致長が2未満の一致の場合、通常は無圧縮として出力する */
//#define LZSS_MATCH_DIST_MAX	(15 + 1)	/* ウインドウサイズ。現在の入力位置から、マッチ可能な過去のフレーズまでの最大距離。最小距離は1 */
#define LZSS_MATCH_DIST_MAX	(4095 + 1)	/* ウインドウサイズ。現在の入力位置から、マッチ可能な過去のフレーズまでの最大距離。最小距離は1 */
//}}調整可
#endif /*}}このファイルをインクルードする箇所で設定してください。*/

/*---------------------------------------------------------------------------*/

#define LZSS_NODE_MAX		LZSS_MATCH_DIST_MAX	/* 有効なノード番号の最大値。(LZSS_MATCH_DIST_MAX+1)個の有効ノードが存在する。LZSS_search()内のコメント参照 */
#define LZSS_TREE_HEAD		(LZSS_NODE_MAX + 1)	/* ルートノードを指すダミノード番号。tree[LZSS_TREE_HEAD].child[LZSS_CHILD_GT]がルートノード番号を指す */
#define LZSS_NODE_NIL		(LZSS_NODE_MAX + 2)	/* ノードが無いことを表すダミーノード番号。tree[LZSS_NODE_NIL]に対しては、どんな書き換えを行なっても構わない */
#define LZSS_TREE_SIZE		(LZSS_NODE_MAX + 3)	/* LZSS_TREE_HEADとLZSS_NODE_NILを含む、ツリーノード数 */

/* LZSS_NODE.child */
#define LZSS_CHILD_LT		0
#define LZSS_CHILD_GT		1

typedef struct _LZSS_NODE {
	int parent;	/* このノードの親。LZSS_NODE_NILならば、このノードは未使用 */
	int child[2];	/* child[LZSS_CHILD_LT] = このノードよりも小さいフレーズを表す子, child[LZSS_CHILD_GT] = このノードよりも大きいフレーズを表す子 */
} LZSS_NODE;

typedef struct _LZSS {
	LZSS_CHAR* src_data;		/* 入力データの先頭アドレス。変更しない */
	int src_len;			/* 入力データの文字数。変更しない */
	int src_pos;			/* 現在のフレーズ位置。0から(src_len-1)まで増加する */
	LZSS_NODE tree[LZSS_TREE_SIZE];	/* ウインドウ内のフレーズを登録するツリー */
} LZSS;

static LZSS lzss;

/*---------------------------------------------------------------------------*/

/* 本モジュールを利用するコードから使用 */
static int LZSS_init(LZSS_CHAR* src_data, int src_len);
static int LZSS_search(int* p_dist);
static int LZSS_advance();
/* 本モジュールの内部でのみ使用 */
static void LZSS_delete_node(int node);
static int LZSS_find_next_node(int node);
static void LZSS_replace_node(int old_node, int new_node);
static void LZSS_contract_node(int old_node, int new_node);

/*---------------------------------------------------------------------------*/

#ifdef LZSS_DEBUG
#pragma warning(disable: 4702)	/* 制御が渡らないコードです。 */
#define LZSS_ASSERT(f) ((void)((f) || (LZSS_die("### %s(%d): %s", __FILE__, __LINE__, #f), 0)))
static void __declspec(noreturn)
LZSS_die(const char* fmt, ...)
{
	va_list ap;
	va_start(ap, fmt);
	fprintf(stderr, "\n");
	vfprintf(stderr, fmt, ap);
	va_end(ap);
#ifdef _DEBUG
	__asm int 3;
#else /*_DEBUG*/
	exit(1);
#endif /*_DEBUG*/
}
#else /*LZSS_DEBUG*/
#define LZSS_ASSERT(f)	((void)0)
#endif /*LZSS_DEBUG*/

/*---------------------------------------------------------------------------*/

/* ツリーを初期化する。
 * 現在のフレーズ位置を返す。必ず0である。
 */
static int
LZSS_init(LZSS_CHAR* src_data, int src_len)
{
	int i;

	/* 入力データの先頭アドレスと文字数を格納する。 */
	lzss.src_data = src_data;
	lzss.src_len = src_len;

	/* すべての有効ノードを未使用とし、ルートノード(lzss.tree[LZSS_TREE_HEAD].child[LZSS_CHILD_GT])を未存在とする。
	 * - lzss.tree[LZSS_TREE_HEAD].child[LZSS_CHILD_GT]だけでなく、lzss.tree[LZSS_TREE_HEAD].child[LZSS_CHILD_LT]も、参照される可能性がある。
	 *   LZSS_contract_node()において、削除するノードがルートノードであった場合に、親のどちらの子かを比較するためである。
	 *   偶然一致してしまうと、不正な処理となるので、lzss.tree[LZSS_TREE_HEAD].child[LZSS_CHILD_LT]を空ノード番号に初期化しておくことが必須。
	 */
	for(i = 0; i < LZSS_TREE_SIZE; i++) {
		lzss.tree[i].parent = LZSS_NODE_NIL;
		lzss.tree[i].child[LZSS_CHILD_GT] = LZSS_NODE_NIL;
		lzss.tree[i].child[LZSS_CHILD_LT] = LZSS_NODE_NIL;
	}

	/* 現在のフレーズ位置を初期化する。 */
	lzss.src_pos = 0;

	return lzss.src_pos;
}

/*---------------------------------------------------------------------------*/

/* 新規フレーズを登録する。
 * 新規フレーズに最長一致した、ウインドウ内のフレーズへの距離と、一致長を返す。
 */
static int
LZSS_search(int* p_dist)
{
	int new_node;
	int limit_len;
	int match_len;
	int match_pos;
	int child_sel;
	int test_node;
	int test_pos;
	int i;
	int delta;

	/* 現在のフレーズ位置が、入力データ内であること。 */
	LZSS_ASSERT((lzss.src_pos >= 0) && (lzss.src_pos <= lzss.src_len - 1));

	/* 新規フレーズを登録するための、ノード番号を求める。
	 * - (LZSS_NODE_MAX+1) が (2^N) とは限らないので、lzss.src_pos&(LZSS_NODE_MAX+1) としてはいけない。
	 *   実際に、通常のパラメータ設定において、(LZSS_NODE_MAX+1) は 17 または 4097 である。
	 *   このパラメータに限らず、本モジュールが扱うパラメータの中に、(2^N) を前提としているものは無い。
	 */
	new_node = lzss.src_pos % (LZSS_NODE_MAX + 1);

	/* - 新規フレーズを登録するためのノードには、最古のフレーズが入っているか、または、未使用である。
	 *   最古のフレーズは、新規フレーズから見て、(LZSS_MATCH_DIST_MAX+1)の距離に存在する。
	 *   即ちウインドウ外であり、新規フレーズにマッチさせてはいけないので、探索を行なう前に削除する。
	 *   探索直前にひとつのノードを未使用に戻すので、探索中の有効ノード数はウインドウサイズに一致する。
	 *   以上が、ツリー上の有効ノード数を、(ウインドウサイズ+1)とした理由である。
	 * - ツリー上の有効ノード数を、(ウインドウサイズ)丁度にできない理由は、以下のとおり。
	 *   もしそうすると、最古のフレーズはウィンドウ内であり、まだ有効であるから、探索前に削除できない。
	 *   探索終了後、新規フレーズを登録する直前に、最古のフレーズを削除する必要が生じる。
	 *   ところが、最古のフレーズのノードを削除した瞬間に、ツリー構造が変化する可能性がある。
	 *   ツリー構造が変化すると、新規フレーズのノードを登録できなくなってしまう。
	 *   以上の理由により、ツリー上の有効ノード数は、(ウインドウサイズ+1)でなくてはならない。
	 */
	LZSS_delete_node(new_node);

	/* 新規フレーズから入力データの末尾までの長さか、または、規定の最大長の、短い方を限界長とする。 */
	limit_len = lzss.src_len - lzss.src_pos;
	if(limit_len > LZSS_MATCH_LEN_MAX) {
		limit_len = LZSS_MATCH_LEN_MAX;
	}

	/* ここに、最長一致の長さを求める。 */
	match_len = 0;

	/* ここに、最長一致したフレーズ位置を求める。 */
	match_pos = 0;

	/* tree[LZSS_TREE_HEAD].child[LZSS_CHILD_GT]から、探索開始する。
	 * tree[LZSS_TREE_HEAD].child[LZSS_CHILD_GT]は、ルートノードを指しているか、または、空である。
	 */
	test_node = LZSS_TREE_HEAD;
	child_sel = LZSS_CHILD_GT;

	for(;;) {
		/* 次の探索ノードが無ければ、新規フレーズを格納して、終了する。 */
		if(lzss.tree[test_node].child[child_sel] == LZSS_NODE_NIL) {
			lzss.tree[test_node].child[child_sel] = new_node;
			lzss.tree[new_node].parent = test_node;
			lzss.tree[new_node].child[LZSS_CHILD_LT] = LZSS_NODE_NIL;
			lzss.tree[new_node].child[LZSS_CHILD_GT] = LZSS_NODE_NIL;
			break; /* 探索ここまで */
		}

		/* 次の比較フレーズに対応する、探索ノード番号を取得する。 */
		test_node = lzss.tree[test_node].child[child_sel];

		/* 探索ノードが、有効ノードであること。 */
		LZSS_ASSERT((test_node >= 0) && (test_node <= LZSS_NODE_MAX));

		/* 探索ノード番号に対応する、フレーズ位置を求める。
		 * - 現在のフレーズ位置と、ツリー上のノード番号から、そのノードのフレーズ位置を求める式です。
		 *   エクセルなどを使って、実際に値を並べてみると、この式で正しいことが理解できると思います。
		 */
		test_pos = (lzss.src_pos - 1) - (((lzss.src_pos - 1) - test_node) % (LZSS_NODE_MAX + 1));

		/* 比較フレーズ位置が、入力データの先頭から、現在のフレーズ位置の直前までの範囲であること。 */
		LZSS_ASSERT((test_pos >= 0) && (test_pos <= lzss.src_pos - 1));

		/* 比較フレーズと新規フレーズの、一致長を求める。 */
		i = 0;
		do {
			/* 比較フレーズの文字と、新規フレーズの文字の、大小を求める。 */
			delta = lzss.src_data[test_pos + i] - lzss.src_data[lzss.src_pos + i];

			/* 比較フレーズと新規フレーズが異なったら、ここまで。 */
			if(delta) {
				break; /* 比較ここまで */
			}
		} while(++i < limit_len); /* 限界長に達したら、比較ここまで */

		/* これまでの最長一致の長さを超えたら… */
		if(i > match_len) {
			/* 最長一致の長さを更新する。 */
			match_len = i;

			/* 最長一致したフレーズ位置を記憶する。 */
			match_pos = test_pos;

			/* 限界長で一致したら、これよりも長い一致は有り得ないので、探索を打ち切る。 */
			if(match_len == limit_len) {
				/* - 比較フレーズと新規フレーズは、現在の限界長以下の長さにおいて、完全一致と見なせる。
				 *   次回以降の比較で、限界長が増えることは有り得ないので、次回以降の比較においても完全一致と見なせる。
				 *   すなわち、比較フレーズと新規フレーズは、完全一致と見なせる。
				 *   同じフレーズが二つ登録されていることは無駄なので、古いフレーズの登録を、新規フレーズで差し替える。
				 * - 上記と逆に、古いフレーズを残して新規フレーズを登録しない、という方法は不可である。
				 *   古いフレーズは、新規フレーズよりも先にウインドウから外れて、削除されるからである。
				 *   次回以降に、古いフレーズが削除されると、ウインドウの中に新規フレーズが存在しているにもかかわらず、
				 *   ツリーに登録されていない状態となり、圧縮率が低下していまう。
				 */
				LZSS_replace_node(test_node, new_node);
				break; /* 探索ここまで */
			}
		}

		/* do〜whileのブロックをdelta=0で抜けた場合は、限界長の判断で探索を打ち切るので、ここへは来ないはず。 */
		LZSS_ASSERT(delta != 0);

		/* 比較フレーズと新規フレーズの大小によって、次に進む子の方向を選択する。 */
		if(delta < 0) {
			child_sel = LZSS_CHILD_LT;
		} else {
			child_sel = LZSS_CHILD_GT;
		}
	}

	/* 新規フレーズに最長一致した、ウインドウ内のフレーズへの距離を格納する。
	 * ただし、要求されていないか、一致したフレーズが無い場合は、格納しない。
	 */
	if(p_dist && match_len) {
		*p_dist = lzss.src_pos - match_pos;

		/* フレーズへの距離が、ウインドウ範囲内であることを確認する。 */
		LZSS_ASSERT((*p_dist >= 1) && (*p_dist <= LZSS_MATCH_DIST_MAX));
	}

	/* 最長一致の長さを返す。 */
	return match_len;
}

/*---------------------------------------------------------------------------*/

/* 現在のフレーズ位置を進める。
 * 進めた結果の、現在のフレーズ位置を返す。
 */
static int
LZSS_advance()
{
	/* 現在のフレーズ位置が、入力データ内であること。 */
	LZSS_ASSERT((lzss.src_pos >= 0) && (lzss.src_pos <= lzss.src_len - 1));

	/* 現在のフレーズ位置を進める。結果は、1〜lzss.src_lenの範囲となる。 */
	lzss.src_pos++;

	return lzss.src_pos;
}

/*---------------------------------------------------------------------------*/

/* このノードを削除する。 */
static void
LZSS_delete_node(int node)
{
	int next_node;

	/* 有効ノード以外に対して、この関数が呼び出されることは有り得ない。 */
	LZSS_ASSERT((node >= 0) && (node <= LZSS_NODE_MAX));

	/* 未使用ならば、何もしない。
	 * まだフレーズが読み込まれていないか、完全一致で古いフレーズが削除された場合である。
	 */
	if(lzss.tree[node].parent == LZSS_NODE_NIL) {
		return;
	}

	/* 小さい方の子が無ければ、このノードを削除し、大きい方の子を上昇する。大きい方の子も無かった場合は、このノードを削除するだけの処理となる。 */
	if(lzss.tree[node].child[LZSS_CHILD_LT] == LZSS_NODE_NIL) {
		LZSS_contract_node(node, lzss.tree[node].child[LZSS_CHILD_GT]);

	/* 大きい方の子が無ければ、このノードを削除し、小さい方の子を上昇する。小さい方の子も無かった場合は、このノードを削除するだけの処理となる。 */
	} else if(lzss.tree[node].child[LZSS_CHILD_GT] == LZSS_NODE_NIL) {
		LZSS_contract_node(node, lzss.tree[node].child[LZSS_CHILD_LT]);

	/* 両方の子が有れば、このノードを削除し、このノードの次に大きなフレーズのノードを上昇する。 */
	} else {
		/* このノードの次に大きなフレーズのノードを取得する。 */
		next_node = LZSS_find_next_node(node);

		/* 次に大きなフレーズのノードを、いったん削除する。
		 * 次に大きなフレーズのノードに対する、その親ノードや子ノードからのリンクを切るためである。
		 */
		LZSS_delete_node(next_node);

		/* 次に大きなフレーズのノードを、このノードの位置に上昇する。 */
		LZSS_replace_node(node, next_node);
	}
}

/*---------------------------------------------------------------------------*/

/* このノードの次に大きなフレーズの、ノード番号を取得する。 */
static int
LZSS_find_next_node(int node)
{
	/* 有効ノード以外に対して、この関数が呼び出されることは有り得ない。 */
	LZSS_ASSERT((node >= 0) && (node <= LZSS_NODE_MAX));

	/* 大きい方の子のツリーから、小さい方の子を末端までたどる。
	 * 言い換えると、このノードよりも大きいフレーズの中で、最小のフレーズを取得する。
	 */
	node = lzss.tree[node].child[LZSS_CHILD_GT];
	for(;;) {
		/* この関数は、基準ノードが両方の子を持っている場合に呼び出されるので、いきなり大きい方の子が無いことは有り得ない。
		 * それ以降は、小さい方の子を末端までたどる途中で、不正なノード番号が格納されていないことを確認する。
		 */
		LZSS_ASSERT((node >= 0) && (node <= LZSS_NODE_MAX));

		/* 小さい方の子が無ければ、現在のノードが末端である。 */
		if(lzss.tree[node].child[LZSS_CHILD_LT] == LZSS_NODE_NIL) {
			return node; /* ここまで */
		}

		/* 小さい方の子へたどって、継続する。 */
		node = lzss.tree[node].child[LZSS_CHILD_LT];
	}
}

/*---------------------------------------------------------------------------*/

/* 古いノードを削除し、新規ノードで差し替える。 */
static void
LZSS_replace_node(int old_node, int new_node)
{
	int parent;

	/* 有効ノード以外に対して、この関数が呼び出されることは有り得ない。 */
	LZSS_ASSERT((old_node >= 0) && (old_node <= LZSS_NODE_MAX));
	LZSS_ASSERT((new_node >= 0) && (new_node <= LZSS_NODE_MAX));

	/* 同じノードに対して、この関数が呼び出されることは有り得ない。 */
	LZSS_ASSERT(old_node != new_node);

	/* 古いノードの親ノード番号を取得する。 */
	parent = lzss.tree[old_node].parent;

	/* 親ノードは、有効ノードか、または、LZSS_TREE_HEADであるはず。 */
	LZSS_ASSERT(((parent >= 0) && (parent <= LZSS_NODE_MAX)) || (parent == LZSS_TREE_HEAD));

	/* 親ノードから古いノードへのポインタを、新規ノードに差し向ける。 */
	if(lzss.tree[parent].child[LZSS_CHILD_LT] == old_node) {
		lzss.tree[parent].child[LZSS_CHILD_LT] = new_node;
	} else {
		/* 古いノードは、親ノードの小さい方の子か、または、大きい方の子の、いずれかであるはず。
		 * 上の条件判断で、小さい方の子でなかったということは、大きい方の子でなければならない。
		 */
		LZSS_ASSERT(lzss.tree[parent].child[LZSS_CHILD_GT] == old_node);
		lzss.tree[parent].child[LZSS_CHILD_GT] = new_node;
	}

	/* 古いノードの子は、有効ノードか、または、空であるはず。 */
	LZSS_ASSERT(((lzss.tree[old_node].child[LZSS_CHILD_LT] >= 0) && (lzss.tree[old_node].child[LZSS_CHILD_LT] <= LZSS_NODE_MAX)) ||
	             (lzss.tree[old_node].child[LZSS_CHILD_LT] == LZSS_NODE_NIL));
	LZSS_ASSERT(((lzss.tree[old_node].child[LZSS_CHILD_GT] >= 0) && (lzss.tree[old_node].child[LZSS_CHILD_GT] <= LZSS_NODE_MAX)) ||
	             (lzss.tree[old_node].child[LZSS_CHILD_GT] == LZSS_NODE_NIL));

	/* 新規ノードから、親と子へのポインタを、古いノードと同じにする。 */
	lzss.tree[new_node] = lzss.tree[old_node];

	/* 新規ノードの子から、親へのポインタを、新規ノードに差し向ける。
	 * 子が空だった場合は、tree[LZSS_NODE_NIL]に対するダミー操作となり、安全である。
	 */
	lzss.tree[lzss.tree[new_node].child[LZSS_CHILD_LT]].parent = new_node;
	lzss.tree[lzss.tree[new_node].child[LZSS_CHILD_GT]].parent = new_node;

	/* 古いノードを未使用に戻す。 */
	lzss.tree[old_node].parent = LZSS_NODE_NIL;
}

/*---------------------------------------------------------------------------*/

/* 古いノードを削除し、古いノードの親と、新規ノードを直結させる。
 * 新規ノードに空ノードを指定した場合は、古いノードを削除するだけの処理となる。
 */
static void
LZSS_contract_node(int old_node, int new_node)
{
	int parent;

	/* 古いノードが、有効ノード以外に対して、この関数が呼び出されることは有り得ない。 */
	LZSS_ASSERT((old_node >= 0) && (old_node <= LZSS_NODE_MAX));

	/* 新規ノードは、有効ノードか、または、空であるはず。 */
	LZSS_ASSERT(((new_node >= 0) && (new_node <= LZSS_NODE_MAX)) || (new_node == LZSS_NODE_NIL));

	/* 同じノードに対して、この関数が呼び出されることは有り得ない。 */
	LZSS_ASSERT(old_node != new_node);

	/* 削除するノードの親ノード番号を取得する。 */
	parent = lzss.tree[old_node].parent;

	/* 削除するノードの親ノードは、有効ノードか、または、LZSS_TREE_HEADであるはず。 */
	LZSS_ASSERT(((parent >= 0) && (parent <= LZSS_NODE_MAX)) || (parent == LZSS_TREE_HEAD));

	/* 上昇させるノードから、親へのポインタを、削除するノードの親に差し向ける。
	 * 上昇させるノードが空ノードであった場合は、tree[LZSS_NODE_NIL]に対するダミー操作となり、安全である。
	 */
	lzss.tree[new_node].parent = parent;

	/* 削除するノードの親ノードから、子へのポインタを、上昇させるノードに差し向ける。 */
	if(lzss.tree[parent].child[LZSS_CHILD_LT] == old_node) {
		lzss.tree[parent].child[LZSS_CHILD_LT] = new_node;
	} else {
		/* 削除するノードは、親ノードの小さい方の子か、または、大きい方の子の、いずれかであるはず。
		 * 上の条件判断で、小さい方の子でなかったということは、大きい方の子でなければならない。
		 */
		LZSS_ASSERT(lzss.tree[parent].child[LZSS_CHILD_GT] == old_node);
		lzss.tree[parent].child[LZSS_CHILD_GT] = new_node;
	}

	/* 削除するノードを未使用に戻す。 */
	lzss.tree[old_node].parent = LZSS_NODE_NIL;
}
