ASM Binary Search for LONG arrays

[Bern Ertl]

#COMPILE EXE
#DIM ALL
#OPTIMIZE SPEED

FUNCTION asmBinarySearch (BYVAL plArray AS LONG PTR, BYVAL lUBound AS LONG, BYVAL lValue AS LONG) AS LONG

	'Returns subscript from array( 1 TO lUBound) matching lValue if found, else returns 0
	'Assumes array is base 0
	'Max value in array must be <= 1,073,741,823

	!mov esi, 1
	!mov edi, lUBound

	!mov edx, lValue
	!mov eax, plArray
DoStart:
	!mov ecx, esi
	!add ecx, edi
	!shr ecx, 1                  ;ecx = (I + J) \ 2
	!cmp [eax]+[ecx * 4], edx
	!jg  short AdjustJ           ;IF @plArray[ ecx] > lValue THEN GOTO AdjustJ
	!jl  short AdjustI           ;IF @plArray[ ecx] < lValue THEN GOTO AdjustJ
	!mov FUNCTION, ecx           ;@plArray[ ecx] = lValue, return ecx
	EXIT FUNCTION

AdjustJ:
	!mov edi, ecx                ;J = ecx - 1
	!dec edi
	!cmp edi, esi
	!jge short DoStart           ;IF J >= I THEN GOTO DoStart
	EXIT FUNCTION

AdjustI:
	!mov esi, ecx                ;I = ecx + 1
	!inc esi
	!cmp edi, esi
	!jge short DoStart           ;IF J >= I THEN GOTO DoStart

END FUNCTION

FUNCTION pbBinarySearch (BYVAL plArray AS LONG PTR, BYVAL lUBound AS LONG, BYVAL lValue AS LONG) AS LONG

	'Returns subscript from array( 1 TO lUBound) matching lValue if found, else returns 0
	'Assumes array is base 0
	'Max value in array can be up to limit of LONG values

	REGISTER I AS LONG, J AS LONG

	LOCAL lIndex AS LONG

	'Find key
	I = 1
	J = lUBound

	DO
	  lIndex = (I + J) \ 2
	  SELECT CASE AS LONG @plArray[ lIndex]
		  CASE > lValue
			  J = lIndex - 1
		  CASE < lValue
			  I = lIndex + 1
		  CASE ELSE  ' = lValue
			  FUNCTION = lIndex
			  EXIT FUNCTION
	  END SELECT
	LOOP UNTIL J < I

END FUNCTION

FUNCTION BinSrch(BYVAL ArrayAddr AS LONG, BYVAL dItem AS DWORD, BYVAL NumItens AS DWORD) AS DWORD

	'http://www.powerbasic.com/support/pbforums/showthread.php?t=4296 (vBulletin)
	'http://www.powerbasic.com/support/forums/Forum4/HTML/004379.html (POFFs)
	'Roberto Valois
	'Assumes array is base 1
	'Max value in array must be <= 1,073,741,823

	!mov esi,ArrayAddr    ' ESI = Array base addr
	!mov edx,dItem         ' EDX = Item to be found
	!xor ebx,ebx          ' EBX = Low - First item
	!mov ecx,NumItens     ' ECX = High - Last Item
	!dec ecx              ' Adjust High - We are now zero based, Low = 0 and High = NumItens - 1
	AGAIN:
	!cmp ecx,ebx          ' High have to be >= Low
	!jl short NOTFOUND    ' If not get out
	!mov eax,ebx          ' Mid = Low
	!add eax,ecx          ' Mid = Low + High
	!shr eax,1            ' Mid = (Low + High) \ 2
	!cmp edx,[esi+eax*4]  ' Compare Item with (Mid)
	!jg short GT          ' Item > (Mid) ?
	!jl short LT          ' Item < (Mid) ?
	!inc eax              ' Found ! Item = (Mid). Adjust Mid to 1 based
	!jmp short FOUND      ' Happy get out
	LT:
	!mov ecx,eax          ' High = Mid
	!dec ecx              ' High = Mid - 1
	!jmp short AGAIN      ' Play it again Sam
	GT:
	!mov ebx,eax          ' Low = Mid
	!inc ebx              ' Low = Mid + 1
	!jmp short AGAIN      ' Play it again Sam
	NOTFOUND:
	!xor eax,eax          ' eax = %False
	FOUND:
	!mov Function,eax     ' Function = what is in eax

END FUNCTION

%NumElements = 10000
%NumTests = 1000000

FUNCTION PBMAIN () AS LONG

	LOCAL I AS LONG, J AS LONG
	LOCAL qpbBinarySearchTix AS QUAD, qasmBinarySearchTix AS QUAD, qasmBinSrchTix AS QUAD
	LOCAL lResult1 AS LONG, lResult2 AS LONG

	DIM lData( %NumElements) AS LOCAL LONG
	DIM lValues( %NumTests) AS LOCAL LONG

	RANDOMIZE TIMER

	'Seed array with data
	FOR I = 1 TO %NumElements
		lData( I) = RND( 1, %NumElements)
	NEXT

	'Sort Data
	ARRAY SORT lData( 1)

	DO
		'Make array of test values
		FOR I = 1 TO %NumTests
			lValues( I) = RND( 1, %NumElements)
		NEXT

		'Test pbBinarySearch
		TIX qpbBinarySearchTix
		FOR I = 1 TO %NumTests
			J = pbBinarySearch( VARPTR( lData( 0)), %NumElements, lValues( I))
		NEXT
		TIX END qpbBinarySearchTix

		lResult1 = J

		'Test pbBinarySearch
		TIX qasmBinSrchTix
		FOR I = 1 TO %NumTests
			J = BinSrch( VARPTR( lData( 1)), lValues( I), %NumElements)
		NEXT
		TIX END qasmBinSrchTix

		lResult2 = J

		'Test asmBinarySearch
		TIX qasmBinarySearchTix
		FOR I = 1 TO %NumTests
			J = asmBinarySearch( VARPTR( lData( 0)), %NumElements, lValues( I))
		NEXT
		TIX END qasmBinarySearchTix

	LOOP UNTIL MSGBOX( "pbBinarySearch took " + FORMAT$( qpbBinarySearchTix, "#,") + " tix.  Found " + FORMAT$( lValues( %NumTests)) + " at lData( " + FORMAT$( lResult1) + ") = " + FORMAT$( lData( lResult1)) + $CRLF + $CRLF + _
			 "BinSrch took " + FORMAT$( qasmBinSrchTix, "#,") + " tix.  Found " + FORMAT$( lValues( %NumTests)) + " at lData( " + FORMAT$( lResult2) + ") = " + FORMAT$( lData( lResult2)) + $CRLF + $CRLF + _
			 "asmBinarySearch took " + FORMAT$( qasmBinarySearchTix, "#,") + " tix.  Found " + FORMAT$( lValues( %NumTests)) + " at lData( " + FORMAT$( J) + ") = " + FORMAT$( lData( J)) + $CRLF + $CRLF + _
			 "Test again?", %MB_ICONQUESTION OR %MB_YESNO, "Binary Search") = %IDNO


END FUNCTION