;******************************
;*
;* binSearch
;* 
;* r0 	 	search value
;* r1		length of table 
;* r2		tabel to search 	
;*
;* return
;*
;* r5 value found at position ($ffff = not found)
;*

binSearch
	
	push	r1
	push	r3
	push	r4
	push	r6
	
	movei	r3,0	;imin
	subqi	r4,r1,1	;imax = length - 1
	nop
	
binSearchLoop

	add	r6,r3,r4	;imid = imin + imax
	cmplo	r4,r3	;while !(imax < imin)
	brts	binSearchEnd
	lsri	r6,1		;imid /= 2			;delay slot
	nop			;delay slot
	add	r1,r2,r6	;delay slot
	nop			;delay slot

	rqldi	r1,0
	nop
	nop
	ld	r1		;r1 = midv
	nop
	
	cmpeq	r1,r0		;midv==svalue
	brts	binSearchEnd
	or	r5,r6,r6	;result = midv
	nop			;delay slot
	nop			;delay slot
	nop			;delay slot
	
	cmplo	r1,r0		;midv<svalue
	brtc	noLower
	subqi	r1,r6,1		;tmp = imid - 1	[higher or equal] delay slot
	nop			;delay slot
	nop			;delay slot
	nop			;delay slot
	
	or	r1,r4,r4	;tmp  = imax
	addqi	r3,r6,1		;imin = imid + 1
	
noLower
	
	br	binSearchLoop
	movei	r5,$ff		;delay slot
	or	r4,r1,r1	;imax=tmp					;delay slot
	moveih	r5,$ff		;posf = 0xffff (not equal as default)		;delay slot
	nop			;delay slot

binSearchEnd

	rqpop
	rqpop
	rqpop
	pop	r6
	pop	r4
	pop	r3

	rqpop
	jmpi	r7,0
	nop		;delay slot
	pop	r1	;delay slot
	nop		;delay slot
	nop		;delay slot