; KPMTemplatea.asm -- assembly portion of KPM pattern matcher
; Copyright Xerox Corporation 1979

.bext MatchKPMTemplate

.srel

MatchKPMTemplate: .MatchKPMTemplate

.nrel

; MatchKPMTemplate(string, template) = 0 or index of failing char
; matches string against template.
; see KPMTemplateb.bcpl for bcpl version of this procedure.
; *** this version is not reentrant ***

.MatchKPMTemplate:
	sta 3 1 2
	sta 0 2 2		;string
	sta 1 3 2		;template
	lda 0 @2 2		;get string length
	lda 1 c177400
	ands 1 0
	inc 0 0			;add 1
	sta 0 sCount		;store count
	sta 0 iCount		;initial count
	mkone 0 0		;start on right byte
	sta 0 sByte

; back here when all matches have failed and we need to restart
; the match with a new string character.
restin:	mkzero 0 0		;initialize template index
	sta 0 tIndex

; get next string character
strnxt:	dsz sCount		;decrement and test string count
	 jmp .+2
	 jmp strend		;end of string
	lda 0 @2 2		;get word containing next byte
	dsz sByte		;which byte next?
	 jmp strlft		;left
	lda 1 c377		;right, mask it
	and 1 0
	isz 2 2			;advance pointer for next
	jmp chklwc

strlft:	lda 1 c177400		;left, mask and swap
	ands 1 0
	mkone 1 1		;next byte is right
	sta 1 sByte

chklwc:	lda 1 c140		;lower-case letter?
	sgt 0 1
	 jmp tmpnxt		;no
	lda 1 c172
	sle 0 1
	 jmp tmpnxt		;no
	lda 1 c40		;yes, convert to upper
	sub 1 0

; advance template index
tmpnxt:	isz tIndex
	lda 1 tIndex

; MatchKPMTemplate (cont'd)

; compare current string character against template token
compar:	lda 3 3 2		;get template pointer
	add 1 3			;make pointer to token
	lda 3 -1 3		;get token
	lda 1 c377		;mask just char in token
	and 3 1
	sne 0 1			;string char match template?
	 jmp strnxt		;yes, on to next
	neg 1 1 snr		;no, check for special match code
	 jmp cfail		;mcEnd = 0, treat as fail
	inc 1 1 snr
	 jmp cstar		;mcStar = 1
	inc 1 1 snr
	 jmp rzero		;mcEndStar = 2, successful match
	inc 1 1 snr
	 jmp rfail		;mcFail = 3, return fail index

; here when the character did not match and the token was not
; a special match code (or was mcEnd)
cfail:	lda 1 c177400		;get fail index from token
	ands 3 1 snr
	 jmp restin		;zero means restart match
	sta 1 tIndex		;store new template index
	jmp compar		;fall back and retry match

; here when token was mcStar.  advance past it and begin a new
; match against the next part of the template
cstar:	lda 3 3 2		;advance template pointer past *
	lda 1 tIndex
	add 1 3
	sta 3 3 2
	mkone 1 1		;reset index to 1
	sta 1 tIndex
	jmp compar		;retry match

; here when the end of the string is reached.
; the next template token must be mcEnd or mcEndStar for
; a successful match.
strend:	lda 1 tIndex		;get current index
	lda 3 3 2		;get next token
	add 1 3
	lda 3 0 3
	lda 0 c2
	lda 1 c377		;mask just char
	and 1 3 szr		;mcEnd (= 0)?
	sne 0 3			;mcEndStar (= 2)?
	 jmp rzero		;yes, successful
rfail:	lda 0 iCount		;no, compute index of failure
	lda 1 sCount
	sub 1 0 skp		;return fail index
rzero:	 mkzero 0 0		;return zero for success
	lda 3 1 2
	jmp 1 3

; variables
sCount:	0
iCount:	0
sByte:	0
tIndex:	0

; constants
c2:	2
c40:	40
c140:	140
c172:	172
c377:	377
c177400: 177400

	.end