I have to make a binary search algorithm in Assembly (69HC11) with loops. This is what I have done:
ORG $C400
;n1-n5 will have numbers
N1 RMB 2
N2 RMB 2
N3 RMB 2
N4 RMB 2
N5 RMB 2
IZQ RMB 2
DER RMB 2
;Here is where is going to be the answer
MID RMB 2
;The number im searching
T RMB 2
ORG $C500
LDD #$400
STD IZQ
LDD #$408
STD DER
LOOP: LDD IZQ
ADDD DER
LDX #2
IDIV
STX MID
LDD MID
CPD #T
BLO LAZO1
BHI LAZO2
BEQ LAZO3
LDD IZQ
CPD DER
BLS LOOP
LAZO1:
;izq = mid + 1
INX
STX IZQ
BRA LOOP
LAZO2:
;der = mid - 1
DEX
STX DER
BRA LOOP
LAZO3:
Fin: BRA Fin
The problem is that the loop I want to calculate the mid position and then storage in D the value that is in that position. I tried to write something like $MID but is not posible.
(First of all I have used this assembler: http://www.aspisys.com/asm11.htm It may need some minor syntax adjustments to make it compatible to another assembler. For example, the @@ indicates local symbols within the current PROC.)
It's better to work with simple indices (0..N-1) rather than actual memory addresses which depending on the word size may make it more difficult to calculate the mid point.
For greater simplicity you could use single byte head and tail variables but then your maximum array would be limited to 256 entries. I left it as word, giving a maximum of 64K entries.
I used a static array (residing in ROM) for initialization simplicity. If you want the array to be in RAM, you need to first initialize it with some data, and rather than using DW directives, you should instead use RMB WORD_SIZE*ARRAY_SIZE to allocate the memory area.
There is no need for using global variables at all. You could write the BinarySearch routine so that it can be used with different tables. For example, the target value could be passed in register D, the starting address of the array in register X, and the number of array elements in register Y. Then, your work variables (mid_point, target, head, and tail) could all be dynamically allocated on the stack upon entry to Search, and de-allocated before exit, while load the result (mid_point) into register X (for example).
All registers are destroyed inside BinarySearch. Use PUSH on entry and PULL on exit if you want them protected.
BinarySearch exits with Carry Clear if target is found, and the mid_point variable updated with the related pointer. Carry is Set if target is not found, and mid_point is 'garbage'.
;*******************************************************************************
; Constants
;*******************************************************************************
STACKTOP equ $0DFF
Vreset equ $FFFE
VARS_ORG equ $0300
ARRAY_ORG equ $C400
CODE_ORG equ $C500
;*******************************************************************************
; Variables
;*******************************************************************************
#RAM
org VARS_ORG
mid_point rmb 2 ; eventually holds the answer
target rmb 2 ; the number to search for
head rmb 2 ; head work pointer
tail rmb 2 ; tail work pointer
;*******************************************************************************
; Code
;*******************************************************************************
#ROM
org ARRAY_ORG ;wherever you want your array to be
array dw 1000
WORD_SIZE equ *-array ;bytes per entry in array
dw 2000
dw 3000
dw 4000
dw 5000
dw 6000
dw 7000
dw 8000
dw 9000
ARRAY_SIZE equ *-array/WORD_SIZE
;*******************************************************************************
;org CODE_ORG ;wherever you want your code to be
BinarySearch proc
clra ;D = 0
clrb
std head ;initialize head pointer to zero
ldd #ARRAY_SIZE-1 ;initialize tail pointer to N-1
std tail
Loop@@ ldd head
addd tail
rora ;LSRD will not work if previous
rorb ; ADDD produced a carry
std mid_point ;update mid_point
lsld ;multiply by WORD_SIZE (x2 -- a shift left will do)
addd #array ;offset into array
xgdx ;X = pointer
ldd target ;target number to search for
cpd ,x ;compare against array value
beq Found@@ ;if equal, we're done
bhi Upper@@ ;if greater than, use upper half
; blo Lower@@ ;if less than, use lower half
Lower@@ ldx mid_point ;tail = mid_point - 1
dex
stx tail
bra Cont@@
Upper@@ ldx mid_point ;head = mid_point + 1
inx
stx head
Cont@@ ldx head
cpx tail
bls Loop@@
NotFound@@ sec ;indicates 'not found'
bra Done@@
Found@@ ldd mid_point
lsld
addd #array
std mid_point
clc ;indicates 'found'
Done@@ rts
;*******************************************************************************
Start proc
lds #STACKTOP
ldd #12345
std target
bsr BinarySearch
ldd #5000
std target
bsr BinarySearch
ldd #3000
std target
bsr BinarySearch
bra *
;*******************************************************************************
#VECTORS
org Vreset
dw Start