102 lines
2.3 KiB
Text
102 lines
2.3 KiB
Text
org 100h ; Entry for test code
|
|
jmp test
|
|
|
|
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
|
;; Binary search in array of unsigned 8-bit integers
|
|
;; B = value to look for
|
|
;; HL = begin of array (low)
|
|
;; DE = end of array, inclusive (high)
|
|
;; The entry point is 'binsrch'
|
|
;; On return, HL = location of value (if contained
|
|
;; in array), or insertion point (if not)
|
|
|
|
binsrch_lo: inx h ; low = mid + 1
|
|
inx sp ; throw away 'low'
|
|
inx sp
|
|
|
|
binsrch: mov a,d ; low > high? (are we there yet?)
|
|
cmp h ; test high byte
|
|
rc
|
|
mov a,e ; test low byte
|
|
cmp l
|
|
rc
|
|
|
|
push h ; store 'low'
|
|
|
|
dad d ; mid = (low+high)>>1
|
|
mov a,h ; rotate the carry flag back in
|
|
rar ; to take care of any overflow
|
|
mov h,a
|
|
mov a,l
|
|
rar
|
|
mov l,a
|
|
|
|
mov a,m ; A[mid] >= value?
|
|
cmp b
|
|
jc binsrch_lo
|
|
|
|
xchg ; high = mid - 1
|
|
dcx d
|
|
pop h ; restore 'low'
|
|
jmp binsrch
|
|
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
|
;; Test data
|
|
|
|
primes: db 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
|
|
db 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83
|
|
db 89, 97, 101, 103, 107, 109, 113, 127, 131
|
|
db 137, 139, 149, 151, 157, 163, 167, 173, 179
|
|
db 181, 191, 193, 197, 199, 211, 223, 227, 229
|
|
db 233, 239, 241, 251
|
|
primes_last: equ $ - 1
|
|
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
|
;; Test code (CP/M compatible)
|
|
|
|
yep: db ": yes", 13, 10, "$"
|
|
nope: db ": no", 13, 10, "$"
|
|
|
|
num_out: mov a,b ;; Output number in B as decimal
|
|
mvi c,100
|
|
call dgt_out
|
|
mvi c,10
|
|
call dgt_out
|
|
mvi c,1
|
|
dgt_out: mvi e,'0' - 1 ;; Output 100s, 10s or 1s
|
|
dgt_out_loop: inr e ;; (depending on C)
|
|
sub c
|
|
jnc dgt_out_loop
|
|
add c
|
|
e_out: push psw ;; Output character in E
|
|
push b ;; preserving working registers
|
|
mvi c,2
|
|
call 5
|
|
pop b
|
|
pop psw
|
|
ret
|
|
|
|
;; Main test code
|
|
test: mvi b,0 ; Test value
|
|
|
|
test_loop: call num_out ; Output current number to test
|
|
|
|
lxi h,primes ; Set up input for binary search
|
|
lxi d,primes_last
|
|
call binsrch ; Search for B in array
|
|
|
|
lxi d,nope ; Location of "no" string
|
|
mov a,b ; Check if location binsrch returned
|
|
cmp m ; contains the value we were looking for
|
|
jnz str_out ; If not, print the "no" string
|
|
lxi d,yep ; But if so, use location of "yes" string
|
|
str_out: push b ; Preserve B across CP/M call
|
|
mvi c,9 ; Print the string
|
|
call 5
|
|
pop b ; Restore B
|
|
|
|
inr b ; Test next value
|
|
jnz test_loop
|
|
|
|
rst 0
|