; Smith-Waterman algorithm for ARM9
;
; ARM7 can not run this code due to lack of implementation
; of half-word loads and stores.
;
; Scott F. Smith
; Department of Electrical and Computer Engineering
; Boise State University
; 1910 University Drive
; Boise, ID  83725-2075
;
; SFSmith@BoiseState.edu
;
; February 2003

PARAM_START	EQU	&1000			; Memory location of parameter block
WORKING_START	EQU	&2000			; Memory location of working arrays
WEIGHT_SIZE	EQU	400			; Number of bytes in weight matrix
VECTOR_SIZE	EQU	1024			; Number of bytes in each working vector

; Parameter block
N		EQU	PARAM_START		; Memory location of N
M		EQU	N + 4			; Memory location of M
END_OF_SEQ	EQU	M + 4			; Memory location of END_OF_SEQ
END_OF_DB	EQU	END_OF_SEQ + 1		; Memory location of END_OF_DB
START_PEN	EQU	END_OF_DB + 1		; Memory location of START_PEN
CONT_PEN	EQU	START_PEN + 1		; Memory location of CONT_PEN

; Working arrays
WEIGHT		EQU	WORKING_START		; Start of WEIGHT matrix in memory
MATCH		EQU	WEIGHT + WEIGHT_SIZE	; Start of MATCH vector in memory
DELETE		EQU	MATCH + VECTOR_SIZE	; Start of DELETE vector in memory
INSERT		EQU	DELETE + VECTOR_SIZE	; Start of INSERT vector in memory
QUERY		EQU	INSERT + VECTOR_SIZE	; Start of QUERY string in memory

; Input and output data
DB		EQU	&100000			; Start of database
BEST		EQU	&200000			; Start of best list

Nreg		RN	r0			; Register to hold N value
Mreg		RN	r1			; Register to hold M value
EOSreg		RN	r2			; Register to hold END_OF_SEQ value
EODreg		RN	r3			; Register to hold END_OF_DB value
SPreg		RN	r4			; Register to hold START_PEN value
CPreg		RN	r5			; Register to hold CONT_PEN value
DBIreg		RN	r6			; Database index register
QIreg		RN	r7			; Query index register
Breg		RN	r8			; Best value register
MTreg		RN	r9			; Temporary match value register
WTreg		RN	r10			; Wieght value register
TMP1reg		RN	r11			; Temporary register #1
TMP2reg		RN	r12			; Temporary register #2
TMP3reg		RN	r13			; Temporary register #3

	AREA 	SW, CODE, READONLY		; Smith-Waterman code
	ENTRY

		; Load register constants		
		ADRL	TMP1reg,	N		; get N into Nreg
		LDR	Nreg,		[TMP1reg]
		ADRL	TMP1reg,	M		; get M into Mreg
		LDR	Mreg,		[TMP1reg]
		ADRL	TMP1reg,	END_OF_SEQ	; get END_OF_SEQ into EOSreg	
		LDRB	EOSreg, 	[TMP1reg]
		ADRL	TMP1reg,	END_OF_DB	; get END_OF_DB into EODreg
		LDRB	EODreg, 	[TMP1reg]
		ADRL	TMP1reg,	START_PEN	; get START_PEN into SPreg
		LDRB	SPreg, 		[TMP1reg]
		ADRL	TMP1reg,	CONT_PEN	; get CONT_PEN into CPreg		
		LDRB	CPreg, 		[TMP1reg]

		; db_index = 0
		MOV	DBIreg,		#0

		; while DATABASE (db_index) != END_OF_DB
Top		MOV	TMP1reg,	#DB			; get next DATABASE value
		LDRB	TMP1reg,	[TMP1reg, DBIreg]		
		CMP	TMP1reg,	EODreg			; check if end of database
		BEQ	ProgEnd					; if so, quit

		; for query_index = 0 to N do ...
		MOV	TMP2reg,	#0			; get a zero to store
		MOV	QIreg,		#0			; start loop query_index at 0
ILoop		ADRL	TMP3reg,	MATCH			; zero Match ( )
		ADD	TMP3reg,	TMP3reg, QIreg		
		STRH	TMP2reg,	[TMP3reg, QIreg]
		ADRL	TMP3reg,	DELETE			; zero Delete ( )
		ADD	TMP3reg,	TMP3reg, QIreg
		STRH	TMP2reg,	[TMP3reg, QIreg]
		ADRL	TMP3reg,	INSERT			; zero Insert ( )
		ADD	TMP3reg,	TMP3reg, QIreg
		STRH	TMP2reg,	[TMP3reg, QIreg]
		CMP	QIreg,		Nreg			; check if end of loop
		ADD	QIreg,		QIreg, #1		; increment loop counter
		BEQ	ILoop

		; while DATABASE (db_index) != END_OF_SEQ 
		B	Over					; skip read if first in seq.
MoreSeq		MOV	TMP1reg,	#DB			; get next DATABASE value
		LDRB	TMP1reg,	[TMP1reg, DBIreg]
		CMP	TMP1reg,	EOSreg			; check if end of sequence
		BEQ	Top					; if so, reintialize

		; best = 0
Over		MOV	Breg,		#0

		; for query_index = 1 to N do
		MOV	QIreg,		#1			; start loop query_index at 1
Loop		ADRL	TMP2reg,	QUERY			; get next QUERY value
		LDRB	TMP2reg,	[TMP2reg, QIreg]

		; weight = M_WEIGHT (QUERY(query_index), DATABASE (db_index))
		MLA	TMP1reg,	Mreg, TMP1reg, TMP2reg	; compute matrix location
		ADD	TMP1reg,	TMP1reg, #WEIGHT
		LDRB	WTreg,		[TMP1reg]		; get weight value

		; match_temp = max [ Insert (query_index-1), Delete (query_index-1) ]
		ADRL	TMP1reg,	INSERT			; get Insert (query_index-1)
		SUB	TMP1reg,	TMP1reg, #2
		ADD	TMP1reg,	TMP1reg, QIreg 
		LDRSH	TMP1reg,	[TMP1reg, QIreg]
		ADRL	TMP2reg,	DELETE			; get Delete (query_index-1)
		SUB	TMP2reg,	TMP2reg, #2
		ADD	TMP2reg,	TMP2reg, QIreg 
		LDRSH	TMP2reg,	[TMP2reg, QIreg]
		CMP	TMP1reg,	TMP2reg			; if Insert > Delete
		MOVGT	MTreg,		TMP1reg			; match_temp = Insert	
		MOVLE	MTreg,		TMP2reg			; match_temp = Delete

		; match_temp = max [ max_temp, Match (query_index-1) ]
		ADRL	TMP1reg,	MATCH			; get Match (query_index-1)
		SUB	TMP1reg,	TMP1reg, #2
		ADD	TMP1reg,	TMP1reg, QIreg 
		LDRH	TMP1reg,	[TMP1reg, QIreg]
		CMP	TMP1reg,	MTreg			; if Match > match_temp
		MOVGT	MTreg,		TMP1reg			; match_temp = Match

		; match_temp = max [ match_temp + weight, 0 ]
		ADDS	MTreg,		MTreg, WTreg		;match_temp=match_temp+weight 
		MOVMI	MTreg,		#0			; make match_temp >= 0

		;Delete=max[Delete(query_index)+CONT_PEN, Match (query_index)+START_PEN]
		ADRL	TMP1reg,	DELETE			; get Delete (query_index)
		ADD	TMP1reg,	TMP1reg, QIreg 
		LDRSH	TMP1reg,	[TMP1reg, QIreg]
		SUB	TMP1reg,	TMP1reg, CPreg		; Delete = Delete - CONT_PEN
		ADRL	TMP1reg,	MATCH			; get Match (query_index)
		ADD	TMP2reg,	TMP2reg, QIreg 
		LDRH	TMP2reg,	[TMP2reg, QIreg]
		SUB	TMP2reg,	TMP2reg, SPreg		; Match = Match - START_PEN
		CMP	TMP2reg,	TMP1reg			; if Match > Delete
		MOVGT	TMP1reg,	TMP2reg			; store Match instead Delete
		ADRL	TMP2reg,	DELETE			; store Delete (query_index)
		ADD	TMP2reg,	TMP2reg, QIreg 
		STRH	TMP1reg,	[TMP2reg, QIreg]

		;Insert=max[Insert(query_index-1)+CONT_PEN,Match(query_index-1)+START_PEN]
		ADRL	TMP1reg,	INSERT			; get Insert (query_index-1)
		SUB	TMP1reg,	TMP1reg, #2
		ADD	TMP1reg,	TMP1reg, QIreg 
		LDRSH	TMP1reg,	[TMP1reg, QIreg]
		SUB	TMP1reg,	TMP1reg, CPreg		; Insert = Insert - CONT_PEN
		ADRL	TMP2reg,	MATCH			; get Match (query_index-1)
		SUB	TMP2reg,	TMP2reg, #2
		ADD	TMP2reg,	TMP2reg, QIreg 
		LDRH	TMP2reg,	[TMP2reg, QIreg]
		SUB	TMP2reg,	TMP2reg, SPreg		; Match = Match - START_PEN
		CMP	TMP2reg,	TMP1reg			; if Match > Insert
		MOVGT	TMP1reg,	TMP2reg			; store Match instead Insert
		ADRL	TMP2reg,	INSERT			; store Insert(query_index-1)
		ADD	TMP2reg,	TMP2reg, QIreg 
		STRH	TMP1reg,	[TMP2reg, QIreg]
	
		; Match (query_index) = match_temp
		ADRL	TMP1reg,	MATCH
		ADD	TMP1reg,	TMP1reg, QIreg 
		STRH	MTreg,		[TMP1reg, QIreg]
	
		; best = max [ best, match_temp ]
		CMP	MTreg,		Breg			; if match_temp > best
		MOVGT	Breg,		MTreg			; best = match_temp

		CMP	QIreg,		Nreg			; check if end of loop
		ADD	QIreg,		QIreg, #1		; increment loop counter
		BEQ	Loop

		; BestList (db_index) = best
		MOV	TMP1reg,	#BEST
		ADD	TMP1reg,	TMP1reg, DBIreg 
		STRH	MTreg,		[TMP1reg, DBIreg]

		; db_index = db_index + 1
		ADD	DBIreg,		DBIreg, #1			

		B	MoreSeq

ProgEnd		NOP

	END