/*	
 *	clipmatc.c
 *
 *	ユーティリティ：検索
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2015 Naoyuki Sawa
 *
 *	* Tue Jan 06 21:26:41 JST 2015 Naoyuki Sawa
 *	- 新規作成。
 *	- 「ユーティリティ：検索」を、clipmisc.*⇒clipmatc.*へ分離しました。
 *	  使用頻度が低いので、無駄にリンクして容量が増加する事を防ぐためです。
 */
#include "clip.h"

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

#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) {
//↓ * Mon Jan 03 22:48:46 JST 2011 Naoyuki Sawa
//↓ - match()→VERY_simple_RegEx_matching()に名前変更しました。
int VERY_simple_RegEx_matching(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;
}
