*
* BM法による文字列サーチ
*  Oh!X 1993/3 p60-61
* Improved 1997 AIG-Soft
*
	.xref	ctypetable
*
LMAX	equ	256		* パターン最大長（EOSを含まない）
				* ワークエリアが.bなのでこれ以上にしないこと
*
* ワークエリア内構造定義
	.offset	0
PATLEN	.ds.w	1	* パターン長−１
TABLE	.ds.b	LMAX	* 移動量のテーブル
PAT	.ds.b	LMAX	* パターン（反転）
SIZEofWORK:
*
* 前処理:パターン（検索文字列）の前処理
* int _bm_comp(unchar *ptrn)
* ret(d0.l):>0=パターン長 , <0=エラー（パターンが長すぎる）
*
	.offset 4
ptrn:	.ds.l	1		* パターン
*
	.text
	.even
*
	.xdef	__bm_comp
__bm_comp:
SAVREGS	reg	d1/a0-a2
SAVSIZ	=	(1+3)*4
	movem.l	SAVREGS,-(sp)
	movea.l	ptrn+SAVSIZ(sp),a1	* a1=パターン
	*
	lea.l	work,a0			* a0=ワーク先頭
	lea.l	PAT(a0),a2		* a2=PAT
	moveq.l	#0,d0			* d0.lの上位ワードをクリア
	move.w	#LMAX-1,d1		* -1 for dbeq
	move.w	d1,d0
1:	move.b	(a1)+,(a2)+		* パターンをPATにコピー
	dbeq	d1,1b			* EOS/LMAXまで
	bne	TooLong			* 長すぎる
	*
	sub.w	d1,d0			* d0=パターン長
	move.w	d0,d1
	subq.w	#1,d1			* d1=パターン長-1
	move.w	d1,(a0)+		* 記録(a0=PATLEN->TABLE)
	bmi	cretn			* パターンが空文字列だった(d0.l=0)
	*
	move.w	#LMAX-1,d1		* TABLEをパターン長で埋める
2:	move.b	d0,(a0)+
	dbra	d1,2b			* a0->PAT
	*
	movea.l	a0,a1			* a1=a2=PAT
	movea.l	a0,a2
	lea.l	-LMAX(a0),a0		* a0=TABLE
	* テーブル作成
	moveq.l	#0,d1			* for .b=.w
	subq.w	#1,d0			* PATLEN -1 for dbra
3:	move.b	(a2)+,d1
	move.b	d0,0(a0,d1.w)
	dbra	d0,3b
	* パターンを反転する
4:	move.b	-(a2),d1		*  a2=PAT末尾 , a1=PAT(先頭)
	move.b	(a1),(a2)		* 入れ換え
	move.b	d1,(a1)+		*  
	cmpa.l	a2,a1
	bcs	4b
	*
	move.w	-(a0),d0		* TABLE-w=PATLEN
	addq.w	#1,d0			* パターン長(.w=.l)
cretn:	movem.l	(sp)+,SAVREGS
	rts
*
TooLong:
	moveq.l	#-1,d0			* エラー
	bra	cretn

*
* サーチ処理本体
* int _bm_exec(unchar *txt,unchar *txtend)
* ret(d0.l)=0:一致(Z=1) , <0:不一致(Z=0)
* a0.l=サーチ成功位置
*
	.offset	4
txt:	.ds.l	1	* テキスト
txtend:	.ds.l	1	* テキスト末尾
*
	.text
	.even
*
	.xdef	__bm_exec
__bm_exec:
SAVREGS	reg	d1-d3/a1-a6
SAVSIZ	=	(3+6)*4
	movem.l	SAVREGS,-(sp)
	movem.l	txt+SAVSIZ(sp),a0/a5	* a0=テキスト先頭
	*				* a5=テキスト末尾
	lea.l	work,a1			* a1=ワーク先頭
	lea.l	PAT+1(a1),a2		* a2=パターン末尾の文字の１つ手前
	move.w	(a1)+,d1		* d1=パターン長−１(a1=TABLE)
	bmi	qretn			* パターン長が０だった
	lea.l	ctypetable,a6		* a6=文字種判別用テーブル
	move.l	a0,d3			* d3=テキスト先頭
	adda.w	d1,a0			* a0=パターン末尾との重ね位置
	subq.w	#1,d1			* パターン長-1 -1 for dbra
	* パターン末尾と一致する文字を探す
	moveq.l	#0,d0		* d0.wの上位バイトをクリア
	bra	next0
loop0:	move.b	(a0),d0		* d0=入力文字
	move.b	0(a1,d0.w),d0	* d0=対応する移動量
	beq	break0		* それが0ならパターン末尾の文字
	adda.w	d0,a0		* ポインタを移動量分進める
next0:	cmpa.l	a5,a0		* 末尾を超えるまで繰り返す
	bcs	loop0
	bra	nmatch		* パターンは見つからなかった
*
break0:	movea.l	a0,a3		* a0=パターン末尾との一致位置
	movea.l	a2,a4		* a4=パターン末尾の１文字手前
	move.w	d1,d2		* パターン長-1 -1 for dbra
	bmi	zenchk		* パターン長が1だった
	*
loop1:	move.b	-(a3),d0	* パターン末尾側からサーチ
	cmp.b	(a4)+,d0
	dbne	d2,loop1
	beq	zenchk		* 全文字一致した
	*
	move.b	0(a1,d0.w),d0	* d0=不一致を起こした文字の移動量
	adda.w	d0,a3		* その分ポインタを進める
	exg.l	a3,a0
	cmpa.l	a0,a3		* 後戻りした？
	bcs	next0		* No
	lea.l	2(a3),a0	* もしそうなら２バイト進める
	cmpa.l	a5,a0		* 末尾を超えるまで繰り返す
	bcs	loop0
	* サーチ失敗
nmatch:	moveq.l	#-1,d0		* 不一致(Z=0)
	bra	retn
*
* サーチ成功位置が全角文字の２バイト目でないことを確認する
zenchk:	movea.l	a3,a4		* a4=サーチ成功位置先頭
	move.l	a4,d2		* d2=テキスト先頭から
	sub.l	d3,d2		*  サーチ位置までのバイト数
	beq	match		* 先頭なら間違いない
	*
	subq.l	#1,d2		* テキストを遡り
	swap.w	d2		* SHIFT-JISの１バイト目
zloop1:	swap.w	d2		*  にはならない文字の位置を探す
zloop2:	move.b	-(a4),d0
	tst.b	0(a6,d0.w)
	dbpl	d2,zloop2
	bpl	zchk0
	swap.w	d2
	dbra	d2,zloop1
	bra	zchk1
*
zchk0:	addq.l	#1,a4		* a4=全角文字の２バイト目ではないことが保証された文字位置
zchk1:	move.l	a3,d2		* d2=その文字位置とサーチ成功位置の差
	sub.l	a4,d2
	andi.b	#1,d2		* 偶数?
	beq	match		* そうならサーチ成功
	* サーチ成功位置は全角文字の２バイト目だった
	addq.l	#1,a0
	cmpa.l	a5,a0
	bcs	loop0
	bra	nmatch
	* サーチ成功
match:	movea.l	a3,a0		* a0=サーチ成功位置
qretn:	moveq.l	#0,d0		* 一致(Z=1)
	*
retn:	movem.l	(sp)+,SAVREGS
	rts
*
	.bss
	.even
work:	.ds.b	SIZEofWORK
*
	.end
