/*	
 *	clipmisc.c
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2010 Naoyuki Sawa
 *
 *	* Wed Dec 12 21:51:29 JST 2001 Naoyuki Sawa
 *	- 作成開始。
 *	* Thu May 30 22:41:27 JST 2002 Naoyuki Sawa
 *	- die()の終了ボタンを、STARTからSELECTに変更。
 *	* Sun Jan 26 19:33:00 JST 2003 Naoyuki Sawa
 *	- die()関数の宣言に__attribute__((noreturn))属性を追加したので、
 *	  警告抑制のため、die()関数の最後にexit(1)を追加。
 *	  メモ:__attribute__((...))は関数宣言時のみ指定可能\です。
 *	       関数実装時に指定するとコンパイルエラーとなります。
 *	* Sun May 4 18:05:00 JST 2003 Naoyuki Sawa
 *	- fpk_size()/fpk_load()を追加しました。
 *	  以前、zip形式のサポート追加時に、fpk形式のサポートは削除したのですが、
 *	  空きメモリ容量が逼迫してzip展開用バッファ(≒32K)も取れないような場合に
 *	  やはりfpk形式を使うこともあるので、fpk形式のサポートを再実装しました。
 *	* Sat Nov 22 06:00:00 JST 2003 Naoyuki Sawa
 *	- トレース出力(TRACE_ON/TRACE/trace())を追加しました。
 *	* Wed Sep 15 06:36:00 JST 2004 Naoyuki Sawa
 *	- コンパイラバグ回避のため、RND8/16,RND8/16_RANGEをマクロ→関数化しました。
 *	  過去のソ\ースの互換性のため、関数を呼び出すマクロも定義してあります。
 *	* Tue Dec 13 04:26:00 JST 2005 Naoyuki Sawa
 *	- die()内の不要なpceLCDDispStop()呼び出しを削除しました。
 *	* Mon Dec 26 01:25:00 JST 2005 Naoyuki Sawa
 *	- コレクション関連の実装を、clipmisc.cからclipcoll.cへ分離しました。
 *	- インターフェイス関連の実装を、clipmisc.cからclipintf.cへ分離しました。
 *	* Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
 *	- 32bit擬似乱数生成関数(rnd32())を追加しました。
 *	  32bit疑似乱数生成アルゴリズムとして、「Xorshift RNGs」を採用しました。(以下、Xorshift法と呼ぶことにします)
 *	  Xorshift法の資料を、「clip\keep\Xorshift RNGs.zip」に保存しました。
 *	- Xorshift法による32bit擬似乱数生成関数(rnd32())を新設したことに伴い、8bit擬似乱数も線形合成法→Xorshift法に変更しました。
 *	  線形合成法に問題が有ったわけではありませんが、全体の統一のためと、Xorshift法の方が良い擬似乱数(かな?)と思ったからです。
 *	- Xorshift法による32bit擬似乱数生成関数(rnd32())を新設したことに伴い、16bit擬似乱数も線形合成法→Xorshift法に変更しました。
 *	  線形合成法に問題が有ったわけではありませんが、全体の統一のためと、Xorshift法の方が良い擬似乱数(かな?)と思ったからです。
 *	* Tue Oct 03 01:05:53 JST 2006 Naoyuki Sawa
 *	- 呼び出し階層の少ないデバッグブレークを「DebugBreak()」→「__asm int 3」に変更しました。
 *	  2006/10/3現在は、呼び出し階層の少なさよりもエラーダイアログの判り易さを優先して、
 *	  「DebugBreak()」でも「__asm int 3」でもなく「abort()」を採用しているのですが、
 *	  今後のための覚え書きとして、コメントとして残しておくことにしました。
 *	* Thu Aug 13 17:02:32 JST 2009 Naoyuki Sawa
 *	- ユーティリティ：検索のセクションを追加しました。
 *	- quick_search()を追加しました。
 *	* Sat Jan 23 03:38:06 JST 2010 Naoyuki Sawa
 *	- match()を追加しました。
 */
#include "clip.h"

/*****************************************************************************
 *	汎用マクロ・関数
 *****************************************************************************/

//int
//rnd8(int* seed)
//{
//	/* 8ビット乱数(『Z80マシン語秘伝の書』より) */
//	*seed = *seed * 5 + 0x3711;
//	return (*seed >> 8) & 0xff;
//}
//↓* Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
//↓- Xorshift法による32bit擬似乱数生成関数(rnd32())を新設したことに伴い、8bit擬似乱数も線形合成法→Xorshift法に変更しました。
//↓  線形合成法に問題が有ったわけではありませんが、全体の統一のためと、Xorshift法の方が良い擬似乱数(かな?)と思ったからです。
int
rnd8(int* seed)
{
	/* 32bit擬似乱数値の中央8bitを、8bit擬似乱数値として返します。
	 * - 大きなビット数の擬似乱数値から、小さなビット数の擬似乱数値を取り出す場合、
	 *   最上位や最下位から取り出すよりも、中央部を取り出す方が良いとされています。
	 *
	 *	++++-++++-++++-++++-++++-++++-++++-++++-< rnd32()
	 *	|||| |||| |||| |||| |||| |||| |||| ||||
	 *	1111 1111 1111 1111 0000 0000 0000 0000
	 *	fedc ba98 7654 3210 fedc ba98 7654 3210
	 *	               |||| ||||
	 *	               ++++-++++----------------> rnd8()
	 */
	return (unsigned char)(rnd32(seed) >> ((32 - 8) / 2));
}

//int
//rnd16(int* seed)
//{
//	/* 16ビット乱数(VisualC++ 6.0 \VC98\CRT\SRC\RAND.C を参考にしました) */
//	*seed = *seed * 214013 + 2531011;
//	return (*seed >> 16) & 0xffff;
//}
//↓* Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
//↓- Xorshift法による32bit擬似乱数生成関数(rnd32())を新設したことに伴い、16bit擬似乱数も線形合成法→Xorshift法に変更しました。
//↓  線形合成法に問題が有ったわけではありませんが、全体の統一のためと、Xorshift法の方が良い擬似乱数(かな?)と思ったからです。
int
rnd16(int* seed)
{
	/* 32bit擬似乱数値の中央16bitを、16bit擬似乱数値として返します。
	 * - 大きなビット数の擬似乱数値から、小さなビット数の擬似乱数値を取り出す場合、
	 *   最上位や最下位から取り出すよりも、中央部を取り出す方が良いとされています。
	 *
	 *	++++-++++-++++-++++-++++-++++-++++-++++-< rnd32()
	 *	|||| |||| |||| |||| |||| |||| |||| ||||
	 *	1111 1111 1111 1111 0000 0000 0000 0000
	 *	fedc ba98 7654 3210 fedc ba98 7654 3210
	 *	          |||| |||| |||| ||||
	 *	          ++++-++++-++++-++++-----------> rnd16()
	 */
	return (unsigned short)(rnd32(seed) >> ((32 - 16) / 2));
}

/* * Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
 * - 32bit擬似乱数生成関数(rnd32())を追加しました。
 *   32bit疑似乱数生成アルゴリズムとして、「Xorshift RNGs」を採用しました。(以下、Xorshift法と呼ぶことにします)
 *   Xorshift法の資料を、「clip\keep\Xorshift RNGs.zip」に保存しました。
 * - 旧いrnd16()関数で利用していた線形合成方法をそのまま使い、16bit右シフトせずにそのまま32bit擬似乱数として返す方法も可能\ですが、
 *   その方法では、偶数/奇数が交互に生成されてしまうこと等、良くない擬似乱数であると判断したので、Xorshift法を使うことにしました。
 */
int
rnd32(int* seed)
{
#define MAGIC_NUMBER 2463534242u /* 0以外ならば何でも可 */

	/* 前回の乱数値を取り出します。
	 * - 以下のシフト演算は、算術シフトでなく論理シフトで行う必要があるので、符号無し値として取り出します。
	 *   関数インターフェイス(seed引数)は、利用側の使い易さを考えて、符号付き値へのポインタとしてあります。
	 */
	unsigned y = *seed;

	/* 前回の乱数値が0だったならば、0以外の適当な値に置き換えます。
	 * - Xorshift法の乱数列は、M系列乱数に性格が似ていて、0を生成できません。
	 *   32ビット乱数列を生成する場合、周期は「2^32」でなく「(2^32)-1」です。
	 *   すなわち、0x00000000〜0xFFFFFFFFの範囲の乱数列を生成するのではなく、0x00000001〜0xFFFFFFFFの範囲の乱数列を生成します。
	 *   0を含めるには、乱数列の適当な位置に、明示的に0を挟む必要があります。
	 * - MAGIC_NUMBERの値に意味は無く、0以外の値ならば何でも構\いません。
	 *   Xorshift法の原典のサンプルコードが、たまたま初期シード値として「2463534242」を使っていたので、それにちなんだだけです。
	 *   初期シード値も、0以外ならば何でも良く、Xorshift法の原典資料のサンプルコードにおいても、「2463534242」に意味はありません。
	 * - 本関数は、Xorshift法の原典のサンプルコードに手を加えて、0にも対応しているので、初期シード値として0を指定することも可能\です。
	 *   MAGIC_NUMBERにだけは、0を指定することは不可です。
	 */
	if(y == 0) y = MAGIC_NUMBER;

	/* Xorshift法を使って、前回の乱数値から、今回の乱数値を生成します。
	 * - シフト数[13,17,5]の組み合わせは、Xorshift法の原典のサンプルコードを参考にしました。
	 *   Xorshift法の原典には、これ以外にも、様々なシフト数の組み合わせが載っています。
	 */
	y ^= (y << 13);
	y ^= (y >> 17);
	y ^= (y <<  5);

	/* 今回の乱数値が特定の値になったら、その前に、明示的に0を挟みます。
	 * - Xorshift法は0を生成できないので、乱数列の適当な位置に、明示的に0を挟む必要があります。
	 *   上述のコメントを参照してください。
	 */
	if(y == MAGIC_NUMBER) y = 0;

	/* 今回の乱数値を、次回の乱数シードとして格納します。
	 * - 関数の戻り値である乱数値と格納する乱数シードは同じ値なので、seed引数を無くすことも可能\ですが、
	 *   たとえば、以下のような呼び出し方ができると便利なので、あえてseed引数を設けてあります。
	 *
	 *	retval = rnd32(&seed) % 100; // 0〜99の乱数値を生成する
	 *
	 *   また、今後、疑似乱数生成に利用するアルゴリズムを変更し、戻り値と乱数シードが同じでなくなった場合にも対応できます。
	 *   実際に今回、疑似乱数生成アルゴリズムを、線形合成法→Xorshift法に変更したわけですが、関数インターフェイスに変化はありません。
	 * - rnd32()の戻り値は(int)なので、0x00000000〜0xFFFFFFFFではなく、-0x80000000〜0x7FFFFFFFとなります。
	 *   rnd8()の戻り値が0x00〜0xFFであることや、rnd16()の戻り値が0x0000〜0xFFFFであることに較べると、一貫性に欠けます。
	 *   それでもあえてこの仕様とした理由は、rnd8()もrnd16()も戻り値が(int)であり、rnd32()だけ戻り値の型を変えるのが嫌だったからです。
	 *   0x00000000〜0xFFFFFFFFの乱数値が必要ならば、呼び出し側にて戻り値を(unsigned)にキャストしてください。
	 *   明示的な(unsigned)へのキャストを要求する方が、見た目で判らない(unsigned)値が式に与える影響の伝播よりも、安全だと考えました。
	 */
	return (*seed = y);

#undef MAGIC_NUMBER
}

int
rnd8_range(int* seed, int a, int b)
{
	return rnd8(seed) % (b - a) + a;
}

int
rnd16_range(int* seed, int a, int b)
{
	return rnd16(seed) % (b - a) + a;
}

int
rnd32_range(int* seed, int a, int b)
{
	return (unsigned)rnd32(seed) % (unsigned)(b - a) + a;
	//     ~~~~~~~~~~←─必要!!─→~~~~~~~~~~
}

void
shuffle(void* base, int num, int width, int* seed)
{
	int i;
	int c;
	int i_dst;
	int i_src;
	unsigned char* p_dst;
	unsigned char* p_src;

	///* 0要素未満の配列は不正です。また、
	// * 現在の実装は16bit乱数を利用しているため、65536要素超過の配列には未対応です。
	// */
	//if((num < 0) || (num > (1<<16))) {
	//	DIE();
	//}
	//↓2006/07/06 numの範囲検査を削除しました。
	// * Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
	// - rnd32()の新設に伴い、16bit乱数→32bit乱数を利用するよう変更しました。
	//   この変更により、65536要素以上の配列をシャッフルできなかった制限が無くなりました。
	//   (num < 0)の制限は引き続き存在しますが、自明なので、検査を省略することにしました。

	/* 先頭要素から最終要素まで順番に... */
	p_dst = base;
	for(i_dst = 0; i_dst < num; i_dst++) {

		/* 交換相手の要素を決定します。 */
		//i_src = RND16_RANGE(*seed, i_dst, num);
		//↓* Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
		//↓- rnd32()の新設に伴い、16bit乱数→32bit乱数を利用するよう変更しました。
		//↓  この変更により、65536要素以上の配列をシャッフルできなかった制限が無くなりました。
		i_src = RND32_RANGE(*seed, i_dst, num);
		p_src = (unsigned char*)base + width * i_src;

		/* 1バイトづつ交換します。 */
		for(i = 0; i < width; i++) {
			c = *p_dst;
			    *p_dst = *p_src;
			             *p_src = c;
			p_dst++;
			p_src++;
		}
	}
}

/*****************************************************************************
 *	エラー処理
 *****************************************************************************/

#ifdef PIECE
/* void die(const char* fmt, ...) __attribute__((noreturn)) */
asm("
	.code
	.align	1
	.global	die
die:
	; as33アセンブラは、未定義シンボルをexternと見なすので、
	; 明示的なextern宣言は必要ありません。(_def_vbuffのこと)
	;//xcall pceLCDDispStop		; pceLCDDispStop(); {{2005/12/13 Naoyuki Sawa 不要なので削除しました}}
	xld.w %r12, _def_vbuff		; pceLCDSetBuffer(_def_vbuff);
	xcall pceLCDSetBuffer
	xcall pceLCDDispStart		; pceLCDDispStart();
	xld.w %r12, 0			; pceFontSetType(0);
	xcall pceFontSetType
	xld.w %r12, 3			; pceFontSetTxColor(3);
	xcall pceFontSetTxColor
	xld.w %r12, 0			; pceFontSetBkColor(0);
	xcall pceFontSetBkColor
	xld.w %r12, 0			; pceFontSetPos(0, 0);
	xld.w %r13, 0
	xcall pceFontSetPos
	xld.w %r4, die_L10		; pceFontPrintf(fmt, ...);
	xld.w [%sp], %r4
	xjp pceFontPrintf
die_L10:
	xcall pceLCDTrans		; pceLCDTrans();
die_L20:				; for(;;) {
	xcall yield			;	yield();
	xcall pcePadGet			;	if(pcePadGet() & TRG_SELECT) {
	xand %r10, %r10, 0x4000		;
	xjreq die_L30			;
	xld.w %r12, 1			;		pceAppReqExit(1);
	xcall pceAppReqExit		;
die_L30:				;	}
	xjp die_L20			; }
");
#else /*PIECE*/
/* * __declspec(noreturn)は、.hファイルの関数宣言に付加するだけで良いようです。
 *   .cファイルの関数定義には、付加してもしなくても同じみたいです。(実験より)
 *   GCCの__attribute__((noreturn))が、関数定義には付加できないことに合わせて、
 *   __declspec(noreturn)も、関数定義には付加しないことにしました。
 * * GCCは、__attribute__((noreturn))を付加した関数が、誤って処理を返した場合、
 *   コンパイル時に警告を表\示します。
 *   Visual C++は、__declspec(noreturn)を付加した関数が、誤って処理を返しても、
 *   コンパイル時に警告を表\示しないので、注意が必要です。
 */
/*__declspec(noreturn)*/ void
die(const char* fmt, ...)
{
	va_list ap;
	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);
#if 1
	abort(); /* DebugBreak()よりもエラーダイアログが判り易いです */
#else
	//DebugBreak(); /* abort()よりも呼び出し階層が少なくて済みます */
	//↓* Tue Oct 03 01:05:53 JST 2006 Naoyuki Sawa
	//↓- 呼び出し階層の少ないデバッグブレークを「DebugBreak()」→「__asm int 3」に変更しました。
	//↓  2006/10/3現在は、呼び出し階層の少なさよりもエラーダイアログの判り易さを優先して、
	//↓  「DebugBreak()」でも「__asm int 3」でもなく「abort()」を採用しているのですが、
	//↓  今後のための覚え書きとして、コメントとして残しておくことにしました。
	__asm int 3; /* DebugBreak()よりもさらに呼び出し階層が少なくて済みます */
#endif
}
#endif /*PIECE*/

/*****************************************************************************
 *	トレース出力
 *****************************************************************************/

void
trace(const char* fmt, ...)
{
	va_list ap;
	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);
}

/*****************************************************************************
 *	ユーティリティ：任意長パケットキュー
 *****************************************************************************/

QUEUE*
create_queue(int capacity)
{
	QUEUE* queue;

	if(capacity < 0) {
		DIE();
	}

	/* パケットサイズ格納用のsizeof(int)を加算して、実際のストレージサイズとします。
	 * 最大で、capacityバイトのパケットを一つ、キューに格納できるようにするためです。
	 */
	capacity += sizeof(int);

	/* ヘッダとストレージのメモリを確保します。 */
	queue = malloc(sizeof(QUEUE) + capacity);
	if(!queue) {
		DIE(); /* メモリ不足 */
	}

	/* ヘッダを初期化します。 */
	queue->capacity = capacity;
	queue->size = 0;

	return queue;
}

void
delete_queue(QUEUE* queue)
{
	/* ヘッダとストレージのメモリを開放します。 */
	free(queue);
}

void
clear_queue(QUEUE* queue)
{
	queue->size = 0;
}

int
write_queue(QUEUE* queue, const void* packet/*[length]*/, int length)
{
	unsigned char* storage = (unsigned char*)(queue + 1);

	if(length < 0) {
		DIE();
	}

	/* パケットサイズとパケットデータを追加する空き容量があるか？ */
	if((int)(queue->size + (sizeof(int) + length)) > queue->capacity) {
		return -1;
	}

	/* キューの末尾にパケットサイズとパケットデータを追加します。 */
	PUT_LEWORD(storage + queue->size, length);
	memcpy(storage + queue->size + sizeof(int), packet, length);
	queue->size += (sizeof(int) + length);

	return length;
}

int
read_queue(QUEUE* queue, void* packet/*[maxlength]*/, int maxlength)
{
	unsigned char* storage = (unsigned char*)(queue + 1);
	int length;

	if(maxlength < 0) {
		DIE();
	}

	/* キューが空でないか？ */
	if(!queue->size) {
		return -1;
	}

	/* キューの先頭のパケットサイズを取得します。 */
	if(queue->size < sizeof(int)) {
		DIE(); /* キュー破損？ */
	}
	length = LEWORD(storage);
	if((length < 0) || ((int)(sizeof(int) + length) > queue->size)) {
		DIE(); /* キュー破損？ */
	}

	/* 指定されたメモリ領域に格納できるか？ */
	if(length > maxlength) {
		return -1;
	}

	/* キューの先頭のパケットを、指定されたメモリ領域にコピーします。
	 * ただし、packet=NULLならば、読み出したパケットデータを破棄します。
	 */
	if(packet) {
		memcpy(packet, storage + sizeof(int), length);
	}

	/* キューの先頭のパケットを削除し、その分、キューを詰めます。 */
	queue->size -= (sizeof(int) + length);
	memmove(storage, storage + (sizeof(int) + length), queue->size);

	return length;
}

const void*
peek_queue(QUEUE* queue, int* _length)
{
	unsigned char* storage = (unsigned char*)(queue + 1);
	int length;

	/* キューが空か？ */
	if(!queue->size) {
		return NULL;
	}

	/* キューの先頭のパケットサイズを取得します。 */
	if(queue->size < sizeof(int)) {
		DIE(); /* キュー破損？ */
	}
	length = LEWORD(storage);
	if((length < 0) || ((int)(sizeof(int) + length) > queue->size)) {
		DIE(); /* キュー破損？ */
	}

	/* パケットサイズを格納します。 */
	if(_length) {
		*_length = length;
	}

	/* パケットデータの先頭アドレスを返します。 */
	return storage + sizeof(int);
}

int
queue_space(QUEUE* queue)
{
	int space = queue->capacity - queue->size - sizeof(int);
	if(space < 0) {
		space = 0;
	}
	return space;
}

/*****************************************************************************
 *	ユーティリティ：リングバッファ
 *****************************************************************************/

BUFFER*
create_buffer(int capacity)
{
	BUFFER* buffer;

	if(capacity < 0) {
		DIE();
	}

	/* ヘッダとストレージのメモリを確保します。 */
	buffer = malloc(sizeof(BUFFER) + capacity);
	if(!buffer) {
		DIE(); /* メモリ不足 */
	}

	/* ヘッダを初期化します。 */
	buffer->capacity = capacity;
	buffer->size = 0;

	return buffer;
}

void
delete_buffer(BUFFER* buffer)
{
	/* ヘッダとストレージのメモリを開放します。 */
	free(buffer);
}

void
clear_buffer(BUFFER* buffer)
{
	buffer->size = 0;
}

int
write_buffer(BUFFER* buffer, const void* data/*[length]*/, int length)
{
	unsigned char* storage = (unsigned char*)(buffer + 1);

	if(length < 0) {
		DIE();
	}

	/* 書き込むデータ長を、ストレージの空き容量へ切り詰めます。 */
	if(length > (buffer->capacity - buffer->size)) {
		length = (buffer->capacity - buffer->size);
	}

	/* ストレージへ、データを書き込みます。 */
	memcpy(storage + buffer->size, data, length);
	buffer->size += length;

	/* 実際に書き込んだデータ長を返します。 */
	return length;
}

int
read_buffer(BUFFER* buffer, void* data/*[maxlength]*/, int maxlength)
{
	unsigned char* storage = (unsigned char*)(buffer + 1);
	int length;

	if(maxlength < 0) {
		DIE();
	}

	/* 読み出すデータ長を、指定されたメモリ領域サイズへ切り詰めます。 */
	length = maxlength < buffer->size
	       ? maxlength : buffer->size;

	/* ストレージ先頭のデータを、指定されたメモリ領域にコピーします。
	 * ただし、data=NULLならば、読み出したデータを破棄します。
	 */
	if(data) {
		memcpy(data, storage, length);
	}

	/* ストレージ先頭のデータを削除し、その分、ストレージを詰めます。 */
	buffer->size -= length;
	memmove(storage, storage + length, buffer->size);

	/* 実際に読み出したデータ長を返します。 */
	return length;
}

const void*
peek_buffer(BUFFER* buffer, int* length)
{
	/* データ長を格納します。 */
	if(length) {
		*length = buffer->size;
	}

	/* ストレージの先頭アドレスを返します。 */
	return buffer + 1;
}

int
buffer_space(BUFFER* buffer)
{
	/* 書き込み可能\な最大データ長は、ストレージの空き容量です。 */
	return buffer->capacity - buffer->size;
}

/*****************************************************************************
 *	ユーティリティ：ダブルリンクリスト
 *****************************************************************************/

void
InitializeListHead(LIST_ENTRY* ListHead)
{
	ListHead->Flink = ListHead->Blink = ListHead;
}

int
IsListEmpty(LIST_ENTRY* ListHead)
{
	return ListHead->Flink == ListHead;
}

LIST_ENTRY*
RemoveHeadList(LIST_ENTRY* ListHead)
{
	LIST_ENTRY* Head = ListHead->Flink;
	RemoveEntryList(Head);
	return Head;
}

LIST_ENTRY*
RemoveTailList(LIST_ENTRY* ListHead)
{
	LIST_ENTRY* Tail = ListHead->Blink;
	RemoveEntryList(Tail);
	return Tail;
}

void
RemoveEntryList(LIST_ENTRY* Entry)
{
	LIST_ENTRY* Flink = Entry->Flink;
	LIST_ENTRY* Blink = Entry->Blink;
	Blink->Flink = Flink;
	Flink->Blink = Blink;
}

void
InsertHeadList(LIST_ENTRY* ListHead, LIST_ENTRY* Entry)
{
	LIST_ENTRY* Head = ListHead->Flink;
	Entry->Flink = Head;
	Entry->Blink = ListHead;
	ListHead->Flink = Head->Blink = Entry;
}

void
InsertTailList(LIST_ENTRY* ListHead, LIST_ENTRY* Entry)
{
	LIST_ENTRY* Tail = ListHead->Blink;
	Entry->Flink = ListHead;
	Entry->Blink = Tail;
	Tail->Flink = ListHead->Blink = Entry;
}

/*****************************************************************************
 *	ユーティリティ：検索
 *****************************************************************************/

#ifndef PIECE
void*
quick_search(const void* _mem1/*[len1]*/, int len1, const void* _mem2/*[len2]*/, int len2)
{
	int tbl[256]; /* スタックを1KB消費します */
	unsigned char* mem1 = (unsigned char*)_mem1;
	unsigned char* mem2 = (unsigned char*)_mem2;
	unsigned char* tmp1;
	unsigned char* tmp2;
	unsigned char* lim1;
	int i;

	/* 空パターン検索は、データ先頭に一致する */
	if(!len2) {
		return mem1;
	}

	/* データの比較窓の、最大アドレスを求める */
	len1 -= len2;
	if(len1 < 0) {
		return NULL;
	}
	lim1 = mem1 + len1; /* = mem1+(len1-len2) */

	/* スキップテーブルを初期化する */
	i = 0;
	do {
		tbl[i] = -1;
	} while(++i < 256);
	i = 0;
	do {
		tbl[mem2[i]] = i;
	} while(++i < len2);

	/* 検索ループ */
	do {
		/*{{memcmp(mem1,mem2,len2)*/
		tmp1 = mem1;
		tmp2 = mem2;
		i = len2;
		while(*tmp1++ == *tmp2++) {
			if(!--i) {
				return mem1;
			}
		}
		/*}}memcmp(mem1,mem2,len2)*/

		/* 比較窓の次の文字を参照して、比較窓の位置をずらす */
		if(mem1 == lim1) { /* mem1の末尾+1へのアクセス防止 */
			break;
		}
		mem1 += len2;
		mem1 -= tbl[*mem1];
	} while(mem1 <= lim1);

	return NULL;
}
#else /*PIECE*/
void* quick_search(const void* _mem1/*[len1]*/, int len1, const void* _mem2/*[len2]*/, int len2);
asm("
		.code
		.align		1
		.global		quick_search
quick_search:
		xsub		%sp, %sp, 1024			;// %sp  := tbl
		ld.w		%r4, %sp			;// %r4  := tbl
		;//---------------------------------------------;//
		cmp		%r15, 0				;// if(!len2)
		jreq		quick_search_RET0		;//   return NULL
		;//---------------------------------------------;//
		sub		%r13, %r15			;// %r13 := len1 -= len2
		jrlt		quick_search_RET0		;// if(len1 < 0) return NULL
		add		%r13, %r12			;// %r13 := lim1 = mem1 + len1
		;//---------------------------------------------;//
		ld.w		%r5, %sp			;// %r5  := ptr = tbl
		ld.w		%r6, -1				;// %r6  := -1
		xld.w		%r7, 256			;// %r7  := cnt = 256
		 ld.w		[%r5]+, %r6			;// do { *ptr++ = -1
		 sub		%r7, 1				;//      %r7  := cnt--
		jrne		-2				;// } while(cnt)
		;//---------------------------------------------;//
		ld.w		%r5, %r14			;// %r5  := ptr = mem2
		ld.w		%r6, 0				;// %r6  := i = 0
		 ld.ub		%r7, [%r5]+			;// do { %r7  :=      *ptr++
		 sla		%r7, 2				;//      %r7  :=      *ptr++ * sizeof(int)
		 add		%r7, %r4			;//      %r7  := &tbl[*ptr++]
		 ld.w		[%r7], %r6			;//               tbl[*ptr++] = i
		 add		%r6, 1				;//      %r6  := i++
		 cmp		%r6, %r15			;//
		jrne		-6				;// } while(i != len2)
		;//---------------------------------------------;//
quick_search_LOOP:						;// do {
		ld.w		%r5, %r12			;//   %r5  := tmp1 = mem1
		ld.w		%r6, %r14			;//   %r6  := tmp2 = mem2
		ld.w		%r7, %r15			;//   %r7  := i    = len2
		 ld.ub		%r10, [%r5]+			;//   do { %r10 := *tmp1++
		 ld.ub		%r11, [%r6]+			;//        %r11 := *tmp2++
		 cmp		%r10, %r11			;//        if(*tmp1++ != *tmp2++)
		 jrne		quick_search_NEXT		;//          goto NEXT
		 sub		%r7, 1				;//        %r7  := i--
		jrne		-5				;//   } while(i)
		jp.d		quick_search_RET		;//   return mem1
		ld.w		%r10, %r12			;//   %r10 := mem1				*delay*
quick_search_NEXT:						;//
		cmp		%r12, %r13			;//   if(mem1 == lim1)
		jreq		quick_search_RET0		;//     return NULL
		add		%r12, %r15			;//   %r12 :=              mem1 += len2
		ld.ub		%r5, [%r12]			;//   %r5  :=             *mem1
		sla		%r5, 2				;//   %r5  :=             *mem1 * sizeof(int)	!INTERLOCK!
		add		%r5, %r4			;//   %r5  :=        &tbl[*mem1]
		ld.w		%r5, [%r5]			;//   %r5  :=         tbl[*mem1]
		sub		%r12, %r5			;//   %r12 := mem1 -= tbl[*mem1]		!INTERLOCK!
		cmp		%r12, %r13			;//
		jrle		quick_search_LOOP		;// } while(mem1 <= lim1)
		;//---------------------------------------------;//
quick_search_RET0:
		ld.w		%r10, 0
quick_search_RET:
		xadd		%sp, %sp, 1024
		ret
");
#endif /*PIECE*/

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

static int matchhere(const char* regexp, const char* text);
static int matchstar(int c, const char* regexp, const char* text);

/* match: search for regexp anywhere in text */
int match(const char* regexp, const char* text) {
	if(regexp[0] == '^') {
		return matchhere(regexp + 1, text);
	}
	do { /* must look even if string is empty */
		if(matchhere(regexp, text)) {
			return 1;
		}
	} while(*text++ != '\0');
	return 0;
}

/* matchhere: search for regexp at beginning of text */
static int matchhere(const char* regexp, const char* text) {
	if(regexp[0] == '\0') {
		return 1;
	}
	if(regexp[1] == '*') {
		return matchstar(regexp[0], regexp + 2, text);
	}
	if((regexp[0] == '$') && (regexp[1] == '\0')) {
		return *text == '\0';
	}
	if((*text != '\0') && ((regexp[0] == '.') || (regexp[0] == *text))) {
		return matchhere(regexp + 1, text + 1);
	}
	return 0;
}

/* matchstar: search for c*regexp at beginning of text */
static int matchstar(int c, const char* regexp, const char* text) {
	do { /* a * matches zero or more instances */
		if(matchhere(regexp, text)) {
			return 1;
		}
	} while((*text != '\0') && ((*text++ == c) || (c == '.')));
	return 0;
}

