'===========================================================================
' Subject: ASSEMBLY SEARCH SUBROUTINES       Date: 12-15-99 (17:47)       
' Author:  Randall L. Glass                  Code: PB                     
' Origin:  rlglass@yahoo.com               Packet: PB.ABC
'===========================================================================
'****************************************************************************
' PowerBasic Inline Assembly Search Subroutines
'
' Donated to Public Domain By Randall Glass
' E-Mail Address rlglass@yahoo.com
'
' Comparsions Of String Search Methods
'
' Assembly hash Searhes And Almost NonAssembly Searches
' And Binary Searches.
'
' Four Different Hash Methods Included.
'
' 1. One Uses AN Collision Area
' 2. One Uses AN Random Key After Collosion
' 3. One uses Next Down lookup upon collision
' 4. One Maps Out the hash area and stores it in an hash map.
'
' All Hashes Use Key Generator Assembly Subroutine To Generate Key from
' string.
'
' I got the idea for this key generator from crc generator subroutines.
'
' For Tight Hash areas The Collision hash uses an overflow area,is very
' fast,And the hash map is almost as fast.
'
' To Keep it Simple And Fast use Next Down Hash ,with the array twice as big
' as needed.If The array is too small it will slow down drastically.
'
' Remember Large String arrays almost only use only the space of strings
' added to them.
'
' The Random Hash Search is only shown as an example. It is not really
' Practical because of the time needed to create the radiom table.
'
' I think the assembly language routines could be speeded up if one knew
' how to access the strings directly in PowerBasic. Instead of using
' Powerbasic internal procedures string access routines.
'
' I would appreciate it if someone would send me infomation on Powerbasic
' string structure so I could directly access the strings instead of using
' Powerbasic internal procedures. My E-mail address is rlglass@yahoo.com
'
'
' Included Non Assembly Binary Search For Qb Programmers.
'
' Thanks to Niklaus Wirth who wrote Algorithms & Data Structures.
' I was able to find a mistake in my old Assembly Binary Search.
' I don't reccomend the above Book. It is hard to read. The Only Thing
' I really found useful is the Simplifed Binary Search Routine.
'
' Hash Prime Number Generator included By Charles Graham,
' Hash Prime Number Geneerator Tweaked by Quinn Tyler Jackson
'*************************************************************************

DEFINT A-Z
$STACK 6000
DECLARE FUNCTION GetStrLoc(BYVAL AllocHandle%) AS LONG
DECLARE FUNCTION ArrayCalc???(BYVAL Index&, ArrayDescriptor AS ANY)
DECLARE FUNCTION GetStrLen(BYVAL AllocHandle%)

CLS
DIM RndNum%(1000),NumList%(1000),WordList$(414),HashList$(1000)
DIM HashMap%(1000),HashPointer%(1000),RandomWord$(414)

SHARED RndNum%(),WordList$()

RANDOMIZE TIMER

HashEntries% = HashPrime(600)
CollisionsEntries% = HashPrime(530)

FOR I% = 1 TO HashEntries%
	NumList%(i%) = i%
NEXT i%
ChipsLeft% = HashEntries%
FOR I% = 1 TO HashEntries%
	Chip% = RND(1,ChipsLeft%)
	RndNum%(I%) = NumList%(Chip%)
        ARRAY DELETE NumList%(Chip%)
        DECR ChipsLeft%
NEXT I%

RndNum%(HashEntries% + 1) = 1
DO
	Bad? = 0
        FOR I% = 1 TO HashEntries%
		IF RndNum%(I%) = I% THEN
                        Card1?? =RndNum%(Rnd(1,HashEntries%))
			SWAP RndNum%(i%),RndNum%(Card1??)
                        Bad? = 1
                        EXIT FOR
		END IF
		Entry% = RndNum%(I%)
	        NewEntry% = Entry%
	        FOR J% = 1 to HashEntries% -1
                        OldEntry% = NewEntry%
	        	NewEntry% = RndNum%(NewEntry%)
	                IF NewEntry% = Entry% THEN
                                Card1?? =RndNum%(Rnd(1,HashEntries%))
				SWAP RndNum%(OldEntry%),RndNum%(Card1??)
	                        Bad? = 1
	                END IF
        	NEXT J%
		IF BAD? = 1 THEN EXIT FOR
	NEXT I%
LOOP UNTIL Bad? = 0

'FOR I% = 1 TO HashEntries%
'	PRINT i%,RndNum%(i%)
'        IF (I% MOD 24) = 23 THEN SLEEP
'NEXT i%

I% = 0
open "pbcomand.dat" for input as #1
DO
        INCR I%
        INPUT #1,WordList$(I%)
LOOP UNTIL EOF(1)
ARRAY SORT WordList$(1) FOR I%
Total% = I%


FOR I% = 1 TO 414
        RndWord% = RND(1,Total%)
	RandomWord$(i%) = WordList$(RndWord%)
NEXT I%

ERASE HashList$
' I use CollisionsEntries% instead of HashEntries% to make this equivalent to the other
' Hashes

MTIMER
FOR I% = 1 TO 414
	k% = BiSearch%(WordList$(i%), WordList$() )
NEXT I%
T2! = MTIMER
PRINT
PRINT
PRINT
print "Binary Search Time = ";T2!/1000;" MilliSeconds"
PRINT

FOR I% = 1 To 414
        CollisionAreaAdd WordList$(i%),HashList$(),HashPointer%(),CollisionsEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

HashListAddr??? = VARPTR32(HashList$(0))
HashPointerAddr??? = VARPTR32(HashPointer%(0))
MTIMER
FOR I% = 1 TO 414
K% = CollisionAreaSearch%(WordList$(i%),HashList$(),HashPointer%(),CollisionsEntries%)
NEXT I%
T2! = MTIMER
PRINT
print "Collision Area Hash Search time = ";T2!/1000;" MilliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions = ";AverageCol!;" Ave. Tries = ";Tries!

'FOR I% = 1 TO HashEntries%
'	PRINT I%;" HashList = ";HashList$(I%);"         ";HashPointer%(I%)
'IF (I% MOD 24) = 23 THEN SLEEP
'NEXT I%

ERASE HashList$
Collisions% = 0
ReCollisions% = 0
FOR I% = 1 To 414
        IF WordList$(I%) = "RND" THEN
        	PRINT
        END IF
        RandomHashAdd WordList$(i%),HashList$(),HashEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

MTIMER
FOR I% = 1 TO 414
        K% = RandomKeySearch%(WordList$(I%),HashList$(),HashEntries%)
NEXT I%
T2! = MTIMER
PRINT
print "Random Key Hash2 Search Time = ";T2!/1000;" MilliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions = ";AverageCol!;" Ave Tries = ";Tries!

ERASE HashList$
Collisions% = 0
ReCollisions% = 0

FOR I% = 1 To 414
        NextDownAddArray WordList$(i%),HashList$(),HashEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

MTIMER
FOR I% = 1 TO 414
        K% = NextDownSearch%(WordList$(I%),HashList$(),HashEntries%)
NEXT I%
T2! = MTIMER
PRINT
print "Next Down From KeyEntry Hash3 Search Time = ";T2!/1000;" MiliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions = ";AverageCol!;" Ave Tries = ";Tries!

ERASE HashList$
Collisions% = 0
ReCollisions% = 0

FOR I% = 1 To 414
        AddHashMap WordList$(I%),HashList$(),HashMap%(),HashEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

MTIMER
FOR I% = 1 TO 414
        K% = HashMapSearch%(WordList$(I%),HashList$(),HashMap%(),HashEntries%)
NEXT I%
T2! = MTIMER
PRINT
print "HashMap Hash Search Time = ";T2!/1000;" MiliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions = ";AverageCol!;" Ave Tries = ";Tries!

LOCATE 24,25
PRINT "Press Any Key To Continue";
SLEEP
CLS
PRINT
PRINT
PRINT
MTIMER
WordHandleAddr??? = VARPTR32(WordList$(0))
FOR I% = 1 TO 414
	k% = BinSearch%(1,414,WordList$(i%),WordList$(),WordHandleAddr???)
NEXT I%
T2! = MTIMER
print "Assembly Binary Search Time = ";T2!/1000;" MilliSeconds"

ERASE HashList$
ERASE HashPointer%
' I use prime number 787 instead of HashEntries% to make this equivalent to the other
' Hashes
Collisions% = 0
ReCollisions% = 0

FOR I% = 1 To 414
        CollisionAreaAdd WordList$(i%),HashList$(),HashPointer%(),CollisionsEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

HashListAddr??? = VARPTR32(HashList$(0))
HashPointerAddr??? = VARPTR32(HashPointer%(0))
MTIMER
FOR I% = 1 TO 414
K% = AssemblyHashSearch%(WordList$(i%),CollisionsEntries%,HashListAddr???,HashPointerAddr???)
NEXT I%
T2! = MTIMER

PRINT
print "Assembly Collision Area Hash1 Search time = ";T2!/1000;" MilliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions% = ";AverageCol!;" Ave Tries = ";Tries!


ERASE HashList$
Collisions% = 0
ReCollisions% = 0

FOR I% = 1 To 414
        NextDownAddArray WordList$(i%),HashList$(),HashEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

HashListAddr??? = VARPTR32(HashList$(0))
MTIMER
FOR I% = 1 TO 414
        K% = AssemblyNextDown%(WordList$(I%),HashEntries%,BYVAL HashListAddr???)
NEXT I%
T2! = MTIMER
PRINT
print "Assembly Next Down Hash Search Time = ";T2!/1000;" MiliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions% = ";AverageCol!;" Ave Tries = ";Tries!

ERASE HashList$
Collisions% = 0
ReCollisions% = 0

FOR I% = 1 To 414
        AddHashMap WordList$(I%),HashList$(),HashMap%(),HashEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

HashListAddr??? = VARPTR32(HashList$(0))
HashMapPointer??? = VARPTR32(HashMap%(0))
MTIMER
FOR I% = 1 TO 414
        K% = AssemblyHashMapAndRandomSearch%(WordList$(I%),HashEntries%,HashListAddr???,HashMapPointer???)
NEXT I%
T2! = MTIMER
PRINT
print "Assembly HashMap Search Time = ";T2!/1000;" MiliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions% = ";AverageCol!;" Ave Tries = ";Tries!

ERASE HashList$
Collisions% = 0
ReCollisions% = 0
FOR I% = 1 To 414
        RandomHashAdd WordList$(i%),HashList$(),HashEntries%,Collisions%,ReCollisions%
NEXT I%
AverageCol! = Recollisions%/Collisions%
Tries! = ((414 -Collisions%) +Recollisions%)/414

HashListAddr??? = VARPTR32(HashList$(0))
RandomPointer??? = VARPTR32(RndNum%(0))
MTIMER
FOR I% = 1 TO 414
         K% = AssemblyHashMapAndRandomSearch%(WordList$(I%),HashEntries%,HashListAddr???,RandomPointer???)
NEXT I%
T2! = MTIMER
PRINT
print "Assembly Random Key Search Time = ";T2!/1000;" MilliSeconds"
Print "Collisions = ";Collisions%;"  ";"Average Recollisions% = ";AverageCol!;" Ave Tries = ";Tries!


END

FUNCTION BiSearch%(Find$,A$())
Lower% = 1                                'start at first element
Upper% = UBOUND(A$())                     'consider through last
WHILE Lower% < Upper%
  Middle% = (Upper% + Lower%) \ 2         'start testing in middle
  IF     A$(Middle%) < Find$ THEN         'too high, cut in half
    Lower% = Middle% + 1
  ELSE
    Upper% = Middle%                      'too low, cut other way
  END IF
WEND
IF  A$(Upper%) = Find$ THEN BiSearch% = Upper%     'return matching element
END FUNCTION

SUB CollisionAreaAdd(AddWord$,WordList$(),HashPointer%(),Entries%,Collisions%,ReCollisions%)
STATIC AddPos%
IF AddPos% = 0 THEN AddPos% = Entries%
TableEntry% = ModKey??(AddWord$,Entries%)

OldTableEntry% = TableEntry%
IF HashPointer%(TableEntry%) <> 0 THEN
        INCR Collisions%
	WHILE HashPointer%(TableEntry%) <> 0
                INCR ReCollisions%
		IF HashPointer%(TableEntry%) = -1 THEN
		        INCR AddPos%
			NewEntry% = AddPos%
			HashPointer%(TableEntry%) = NewEntry%
	                TableEntry% = NewEntry%
	        ELSE
	                TableEntry% = HashPointer%(TableEntry%)
		END IF
	WEND
END IF
WordList$(TableEntry%) = AddWord$
HashPointer%(TableEntry%)   = -1
END SUB

FUNCTION CollisionAreaSearch%(Find$,WordList$(),HashPointer%(),Entries%)
TableEntry% = ModKey??(Find$,Entries%)
WHILE WordList$(TableEntry%) <> FIND$
        IF HashPointer%(TableEntry%) = 0 THEN EXIT FUNCTION
        TableEntry% = HashPointer%(TableEntry%)
WEND
CollisionAreaSearch% = TableEntry%
END FUNCTION

SUB RandomHashAdd(AddWord$,Hash$(),Entries%,Collisions%,Recollisions%)
TableEntry% = ModKey??(AddWord$,Entries%)
IF Hash$(TableEntry%) <> "" THEN
        INCR Collisions%
	WHILE Hash$(TableEntry%) <> ""
                INCR Recollisions%
		TableEntry% = RndNum%(TableEntry%)
	WEND
END IF
Hash$(TableEntry%) = AddWord$
END SUB

FUNCTION RandomKeySearch%(Find$,Hash$(),Entries%)
TableEntry% = ModKey??(Find$,Entries%)
WHILE Hash$(TableEntry%) <> FIND$
        IF LEN(Hash$(TableEntry%)) = 0 THEN EXIT FUNCTION
	TableEntry% = RndNum%(TableEntry%)
WEND
RandomKeySearch% = TableEntry%
END FUNCTION

SUB NextDownAddArray(AddWord$,Hash$(),Entries%,Collisions%,Recollisions%)
TableEntry% = ModKey??(AddWord$,Entries%)
IF Hash$(TableEntry%) <> "" THEN
        INCR Collisions%
	WHILE Hash$(TableEntry%) <> ""
                INCR Recollisions%
                INCR TableEntry%
                IF TableEntry% > Entries% THEN TableEntry% = 1
	WEND
END IF
Hash$(TableEntry%) = AddWord$
END SUB

FUNCTION NextDownSearch%(Find$,Hash$(),Entries%)
TableEntry% = ModKey??(Find$,Entries%)
WHILE Hash$(TableEntry%) <> FIND$
        IF LEN(Hash$(TableEntry%)) = 0 THEN EXIT FUNCTION
	INCR TableEntry%
	IF TableEntry% > Entries% THEN TableEntry% = 1
WEND
NextDownSearch% = TableEntry%
END FUNCTION

SUB AddHashMap(AddWord$,Hash$(),HashMap%(),Entries%,Collisions%,ReCollisions%)
TableEntry% = ModKey??(AddWord$,Entries%)

IF Hash$(TableEntry%) <> "" THEN
        INCR Collisions%
	WHILE Hash$(TableEntry%) <> ""
                INCR ReCollisions%
                OldTableEntry% = TableEntry%
		IF HashMap%(TableEntry%) = 0 THEN
			WHILE Hash$(TableEntry%) <> ""
	                	TableEntry% = RND(1,Entries%)
                        WEND
			HashMap%(OldTableEntry%) = TableEntry%
		ELSE
                        TableEntry% = HashMap%(TableEntry%)
                END IF
	WEND
END IF
Hash$(TableEntry%) = AddWord$
END SUB

FUNCTION HashMapSearch%(Find$,Hash$(),HashMap%(),Entries%)
TableEntry% = ModKey??(Find$,Entries%)
WHILE Hash$(TableEntry%) <> FIND$
        IF LEN(Hash$(TableEntry%)) = 0 THEN EXIT FUNCTION
	TableEntry% = HashMap%(TableEntry%)
WEND
HashMapSearch% = TableEntry%
END FUNCTION

DEFINT A-Z
 ' This FUNCTION returns a prime number that is at least 30% greater than
 ' threshold.  It will TRY to return a prime number that also fits into the
 ' form 4K+3, where k is any integer, but if the prime number is twice the
 ' size of the threshold, it will ignore this criterion.
 '
 '       Written by Charles Graham, Tweaked by Quinn Tyler Jackson
 '

FUNCTION HashPrime(threshold) PUBLIC
TRUE = -1
FALSE =  ISFALSE TRUE

tp30 = INT((threshold * 1.3) + .5)
IF tp30 / 2 = tp30 \ 2 THEN
	tp30 = tp30 + 1
END IF
c = tp30 - 2
IF c < 1 THEN
	c = 1
END IF
t2 = threshold * 2
DO
	c = c + 2
	FOR z = 3 TO SQR(c)
		ind = TRUE
		IF c / z = c \ z THEN
			ind = FALSE
			EXIT FOR
		END IF
	NEXT z
	IF ind THEN
		IF (c - 3) / 4 = INT((c - 3) / 4) OR c > t2 THEN
                        HashPrime = c
			EXIT DO
		END IF
	END IF
LOOP
END FUNCTION

FUNCTION AssemblyHashSearch%(Find$,BYVAL Entries%,BYVAL ArrayHandleAddr???,BYVAL HashPointerAddr???)
  DIM FindPtr AS DWORD,TableEntry AS INTEGER,Ln AS WORD
  ! LES BX,Find$
  ! MOV AX,ES:[BX]
  ! push AX                  ; push it on the stack
  ! call GetStrLoc           ; find where the data is located
  ! JCXZ BinSearchDone2
  ! JMP Continue2
BinSearchDone2:
  ! JMP HashDone
Continue2:
  ! MOV Ln??,CX
  ! MOV FindPtr[0],AX
  ! MOV FindPtr[2],DX

  ! PUSH DS
  ! mov  DS, DX              ; put segment in ES
  ! mov  SI, AX              ; put offset in DI
  ! MOV DX,&HFFFF
  ! MOV AX,0
NEWCRC2:
  ! LODSB
  ! ADD DX,AX
  ! XCHG DH,DL
  ! LOOP NewCrc2

  ! POP DS
  ! MOV AX,DX
  ! MOV DX,0
  ! MOV CX,Entries%
  ! DIV CX
  ! INC DX
  ! MOV TableEntry%,DX
'WHILE WordList$(TableEntry%) <> FIND$
HashWhile:
  ! LES DI,ArrayHandleAddr???
  ! SHL DX,1
  ! ADD DI,DX
  ! MOV AX,ES:[DI]
  ! PUSH AX
  ! call GetStrLoc           ; find where the data is located
  ! JCXZ HashDone
  ! MOV BX,Ln??
  ! CMP BX,CX
  ! JNZ NotEqual
  ! mov  ES, DX              ; put segment in ES
  ! mov  DI, AX              ; put offset in DI
  ! PUSH DS
  ! LDS SI,FindPtr???
MinLen:
  ! CMPSB
  ! JNE NotEqualPop
  ! LOOP MinLen
  ! JMP Equal
NotEqualPoP:
  ! POP DS
NotEqual:
  ! LES DI,HashPointerAddr???
  ! MOV AX,TableEntry%
  ! SHL AX,1
  ! ADD DI,AX
  ! MOV DX,ES:[DI]
  ! CMP DX,0
  ! Je HashDone
  ! MOV TableEntry,DX
  ! JMP HashWhile
Equal:
  ! POP DS
  ! MOV AX,TableEntry%
  ! MOV FUNCTION,AX
HashDone:
END FUNCTION

FUNCTION AssemblyNextDown%(Find$,BYVAL Entries%,BYVAL ArrayHandleAddr???)
  DIM FindPtr AS DWORD,TableEntry AS INTEGER,Ln AS WORD
  DIM ArrayStrLen AS WORD

  ! LES BX,Find$
  ! MOV AX,ES:[BX]
  ! push AX                  ; push it on the stack
  ! call GetStrLoc           ; find where the data is located
  ! JCXZ BinSearchDone3
  ! JMP Continue3
BinSearchDone3:
  ! JMP HashDone3
Continue3:
  ! MOV Ln??,CX
  ! MOV FindPtr[0],AX
  ! MOV FindPtr[2],DX

  ! PUSH DS
  ! mov  DS, DX              ; put segment in ES
  ! mov  SI, AX              ; put offset in DI
  ! MOV DX,&HFFFF
  ! MOV AX,0
NEWCRC3:
  ! LODSB
  ! ADD DX,AX
  ! XCHG DH,DL
  ! LOOP NewCrc3

  ! POP DS
  ! MOV AX,DX
  ! MOV DX,0
  ! MOV CX,Entries%
  ! DIV CX
  ! INC DX
  ! MOV TableEntry%,DX
'WHILE WordList$(TableEntry%) <> FIND$
HashWhile3:
  ! LES DI,ArrayHandleAddr???
  ! SHL DX,1
  ! ADD DI,DX
  ! MOV AX,ES:[DI]
  ! PUSH AX
  ! call GetStrLoc           ; find where the data is located
  ! JCXZ HashDone3
  ! MOV BX,Ln??
  ! CMP BX,CX
  ! JNZ NotEqual3
  ! mov  ES, DX              ; put segment in ES
  ! mov  DI, AX              ; put offset in DI
  ! PUSH DS
  ! LDS SI,FindPtr???
MinLen3:
  ! CMPSB
  ! JNE NotEqualPop3
  ! LOOP MinLen3
  ! JMP Equal3
NotEqualPop3:
  ! POP DS
NotEqual3:
  ! MOV DX,TableEntry%
  ! INC DX
  ! CMP DX,Entries%
  ! JLE FinishCheck
  ! MOV DX,1
FinishCheck:
  ! MOV TableEntry,DX
  ! JMP HashWhile3
Equal3:
  ! POP DS
  ! MOV AX,TableEntry%
  ! MOV FUNCTION,AX
HashDone3:
END FUNCTION

FUNCTION AssemblyHashMapAndRandomSearch%(Find$,BYVAL Entries%,BYVAL ArrayHandleAddr???,BYVAL HashMapPointerAddr???)
  DIM FindPtr AS DWORD,TableEntry AS INTEGER,Ln AS WORD
  DIM ArrayStrLen AS WORD

  ! LES BX,Find$
  ! MOV AX,ES:[BX]
  ! push AX                  ; push it on the stack
  ! call GetStrLoc           ; find where the data is located
  ! JCXZ BinSearchDone5
  ! JMP Continue5
BinSearchDone5:
  ! JMP HashDone5
Continue5:
  ! MOV Ln??,CX
  ! MOV FindPtr[0],AX
  ! MOV FindPtr[2],DX

  ! PUSH DS
  ! mov  DS, DX              ; put segment in ES
  ! mov  SI, AX              ; put offset in DI
  ! MOV DX,&HFFFF
  ! MOV AX,0
NEWCRC5:
  ! LODSB
  ! ADD DX,AX
  ! XCHG DH,DL
  ! LOOP NewCrc5

  ! POP DS
  ! MOV AX,DX
  ! MOV DX,0
  ! MOV CX,Entries%
  ! DIV CX
  ! INC DX
  ! MOV TableEntry%,DX
'WHILE WordList$(TableEntry%) <> FIND$
HashWhile5:
  ! LES DI,ArrayHandleAddr???
  ! SHL DX,1
  ! ADD DI,DX
  ! MOV AX,ES:[DI]
  ! PUSH AX
  ! call GetStrLoc           ; find where the data is located
  ! JCXZ HashDone5
  ! MOV BX,Ln??
  ! CMP BX,CX
  ! JNZ NotEqual5
  ! mov  ES, DX              ; put segment in ES
  ! mov  DI, AX              ; put offset in DI
  ! PUSH DS
  ! LDS SI,FindPtr???
MinLen5:
  ! CMPSB
  ! JNE NotEqualPop5
  ! LOOP MinLen5
  ! JMP Equal5
NotEqualPop5:
  ! POP DS
NotEqual5:
  ! LES DI,HashMapPointerAddr???
  ! MOV AX,TableEntry%
  ! SHL AX,1
  ! ADD DI,AX
  ! MOV DX,ES:[DI]
  ! MOV TableEntry,DX
  ! JMP HashWhile5
Equal5:
  ! POP DS
  ! MOV AX,TableEntry%
  ! MOV FUNCTION,AX
HashDone5:
END FUNCTION


FUNCTION BinSearch% (byval Lower%,byval Upper%,Find$,a$(),BYVAL ArrayHandleAddr???) Public
DIM FindPtr AS DWORD,Middle AS INTEGER,Ln AS WORD
! LES BX,Find$
! MOV AX,ES:[BX]
! PUSH AX
! CALL GetStrLoc           ; find where the data is located
! JCXZ BinSearchDone1
! JMP Continue
BinSearchDone1:
! JMP BinSearchDone
Continue:
! MOV  FindPtr???[2],DX    ; put segment in ES
! MOV  FindPtr???[0],AX    ; put segment in ES
! MOV Ln??,CX

'WHILE Lower% < Upper%
BinaryWhile:
!      MOV BX,Lower%
!      MOV DX,Upper%
!      cmp  BX,DX
!      jae BinSearchDone
'if    Upper% >= Lower%  then Quit
!       MOV AX,BX        ;CX = Upper%
!       ADD AX,DX
!       shr AX,1         ;AX = Middle%
'  Middle% = (Upper% + Lower%) \ 2         'start testing in middle
! MOV Middle%,AX
! LES DI,ArrayHandleAddr???
! SHL AX,1
! ADD DI,AX
! MOV AX,ES:[DI]
! PUSH AX
! call GetStrLoc           ; find where the data is located
! JCXZ BinSearchDone
! mov  ES, DX              ; put segment in ES
! mov  DI, AX              ; put offset in DI
! MOV DX,Ln??
! MOV BX,CX
! CMP DX,CX
! JG  NoMin
! MOV CX,DX
NoMin:
! PUSH DS
! LDS SI,FindPtr???
NeMinLen:
! CMPSB
! JA AisGTFind
! JB AisLTFind
! LOOP NeMinLen
! CMP BX,DX
! Jl AisGtFind
! Je BinaryFoundIt
AisLTFind:
! POP DS
! MOV AX,Middle%
! MOV Upper%,AX
! JMP BinaryWhile
AisGtFind:
! POP DS
! MOV AX,Middle%
! INC AX
! MOV Lower%,AX
!JMP BinaryWhile
BinaryFoundIt:
! POP DS
! MOV AX,Middle%
! MOV FUNCTION,AX
BinSearchDone:
END FUNCTION

FUNCTION ModKey??(Block$,BYVAL Entries%) PUBLIC
  ! LES BX,Block$
  ! MOV AX,ES:[BX]
  ! push AX                  ; push it on the stack
  ! call GetStrLoc           ; find where the data is located
  ! PUSH DS
  ! mov  DS, DX              ; put segment in ES
  ! mov  SI, AX              ; put offset in DI
  ! MOV DX,&HFFFF
  ! MOV AX,0
NEWCRC1:
  ! LODSB
  ! ADD DX,AX
  ! XCHG DH,DL
  ! LOOP NewCrc1

  ! POP DS
  ! MOV AX,DX
  ! MOV DX,0
  ! MOV CX,Entries%
  ! DIV CX
  ! INC DX
  ! MOV FUNCTION,DX
END FUNCTION