6809_BINSCH.s

	.macro	CLC
		ANDCC	#$FE
	.endm
	.macro	SEC
		ORCC	#1
	.endm

;	Title:			Binary Search 
;	Name:			BINSCH 
;
;	Purpose:		Search an ordered array of unsigned bytes,
;				with a maximum size of 255 elements.
;
;	Entry:			TOP OF STACK
;				High byte of return address
;				Low  byte of return address
;				Value to find
;				Length (size) of array
;				High byte of base address of array
;				Low  byte of base address of array
;
;	Exit:			If the value is found then
;					Carry flag = 0
;					Register X = Address of value
;				Else
;					Carry flag = 1
;
;	Registers Used:		All
;
;	Time:			Approximately 50 cycles for each iteration of
;				the search loop plus 50 cycles overhead
;
;				A binary search takes on the order of 
;				log base 2 of N searches, 
;				where N is the number of
;				elements in the array.
;
;	Size:			Program 64 bytes
; 
BINSCH:
	;
	; EXIT WITH CARRY SET IF ARRAY CONTAINS NO ELEMENTS
	;
	LDU	,S		; SAVE RETURN ADDRESS
	SEC			; SET CARRY IN CASE ARRAY HAS NO ELEMENTS
	LDB	3,S		; CHECK NUMBER OF ELEMENTS
	BEQ	EXITBS		; BRANCH (EXIT) WITH CARRY SET IF NO
				; ELEMENTS VALUE SURELY CANNOT BE FOUND
	;
	; INITIALIZE INDEXES OF UPPER BOUND, LOWER BOUND
	; LOWER BOUND = BASE ADDRESS
	; UPPER BOUND = ADDRESS OF LAST ELEMENT =
	; BASE ADDRESS + SIZE 1
	;
	DECB			; INDEX OF UPPER BOUND = NUMBER OF
	STB	1,S		; ELEMENTS 1
	CLR	,S		; INDEX OF LOWER BOUND = 0 INITIALLY
	LDX	4,S		; GET BASE ADDRESS OF ARRAY
	;
	; ITERATION OF BINARY SEARCH
	;
	; 1) COMPARE VALUE TO MIDDLE ELEMENT
	;
	; 2) IF THEY ARE NOT EQUAL, DISCARD HALF THAT
	; CANNOT POSSIBLY CONTAIN VALUE (BECAUSE OF ORDERING)
	;
	; 3) CONTINUE IF THERE IS ANYTHING LEFT TO SEARCH
	;
SRLOOP:
	LDA	,S		; ADD LOWER AND UPPER BOUND INDEXES
	ADDA	1,S
	RORA			; DIVIDE BY 2, TRUNCATING FRACTION
	;
	; IF INDEX OF MIDDLE ELEMENT IS GREATER THAN UPPER BOUND,
	; THEN ELEMENT IS NOT IN ARRAY
	;
	CMPA	1,S		; COMPARE INDEX OF MIDDLE ELEMENT TO
				; UPPER BOUND
	BMI	NOTFND		; BRANCH (NOT FOUND) IF INDEX GREATER
				; THAN UPPER BOUND
	;
	; IF INDEX OF MIDDLE ELEMENT IS LESS THAN LOWER BOUND, THEN
	; ELEMENT IS NOT IN ARRAY
	;
	CMPA	,S		; COMPARE INDEX OF MIDDLE ELEMENT TO
				; LOWER BOUND
	BLO	NOTFND		; BRANCH (NOT FOUND) IF INDEX LESS
				; THAN LOWER BOUND
	;
	; CHECK IF MIDDLE ELEMENT IS THE VALUE BEING SOUGHT
	;
	LDB	A,X		; GET ELEMENT WITH MIDDLE INDEX
	CMPB	2,S		; COMPARE ELEMENT WITH VALUE SOUGHT
	BLO	RPLCLW		; BRANCH IF VALUE LARGER THAN ELEMENT
	BEQ	FOUND		; BRANCH IF VALUE FOUND
				; VALUE IS SMALLER THAN ELEMENT WITH MIDDLE INDEX
				; MAKE MIDDLE INDEX 1 INTO NEW UPPER BOUND
				;
	DECA			; SUBTRACT 1 SINCE VALUE CAN ONLY BE
				; FURTHER DOWN
	STA	1,S		; SAVE DIFFERENCE AS NEW UPPER BOUND
	CMPA	#$FF		; CONTINUE SEARCHING IF UPPER BOUND DOES
	BNE	SRLOOP		; NOT UNDERFLOW
	BEQ	NOTFND		; EXIT IF UPPER BOUND UNDERFLOWED
; VALUE IS LARGER THAN ELEMENT WITH MIDDLE INDEX
; MAKE MIDDLE INDEX + 1 INTO NEW LOWER BOUND
;
RPLCLW:
	INCA			; ADD 1 SINCE VALUE CAN ONLY BE FURTHER UP
	STA	,S		; SAVE SUM AS NEW LOWER BOUND
	BNE	SRLOOP		; CONTINUE SEARCHING IF LOWER BOUND DOES
				; NOT OVERFLOW
	BEQ	NOTFND		; EXIT IF LOWER BOUND OVERFLOWED
	;
	; FOUND THE VALUE
	; GET ITS ADDRESS AND CLEAR CARRY
	;
FOUND:
	LEAX	A,X		; GET ADDRESS OF VALUE
	CLC			; CLEAR CARRY, INDICATING VALUE FOUND
	BRA	EXITBS
	;
	; DID NOT FIND THE VALUE SET CARRY TO INDICATE FAILURE
NOTFND:
	SEC			; SET CARRY, INDICATING VALUE NOT FOUND
	;
	; REMOVE PARAMETERS FROM STACK AND EXIT
	;
EXITBS:
	LEAS	6,S		; REMOVE PARAMETERS FROM STACK
	JMP	,U		; EXIT TO RETURN ADDRESS
;
; SAMPLE EXECUTION
;
SC6E:	
	; SEARCH FOR A VALUE THAT IS IN THE ARRAY
	;
	LDX	BF		; GET BASE ADDRESS OF BUFFER
	LDB	BFSZ		; GET ARRAY SIZE IN BYTES
	LDA	#7		; GET VALUE TO FIND
	PSHS	D,X		; SAVE PARAMETERS IN STACK BINARY SEARCH
	JSR	BINSCH		; BINARY SEARCH
				; CARRY FLAG = 0 (VALUE FOUND)
				; X = ADDRESS OF 7 IN ARRAY
	;
	; SEARCH FOR A VALUE THAT IS NOT IN THE ARRAY
	;
	LDX	BF		; GET BASE ADDRESS OF BUFFER
	LDB	BFSZ		; GET ARRAY SIZE IN BYTES
	LDA	#7		; GET VALUE TO FIND
	PSHS	D,X		; SAVE PARAMETERS IN STACK BINARY SEARCH
	JSR	BINSCH		; BINARY SEARCH
				; CARRY FLAG = 1 (VALUE NOT FOUND)

	BRA	SC6E		; LOOP FOR MORE TESTS
;
; DATA
;
SIZE	EQU	$10		; SIZE OF BUFFER IN BYTES

BFSZ:	FCB	SIZE		; SIZE OF BUFFER IN BYTES

BF:				; BUFFER
	FCB	1
	FCB	2
	FCB	4
	FCB	5
	FCB	7
	FCB	9
	FCB	10
	FCB	11
	FCB	23
	FCB	50
	FCB	81
	FCB	123
	FCB	191
	FCB	199
	FCB	250
	FCB	255

	END