Binary Search Assembly 68HC11

Question

Мне нужно сделать алгоритм бинарного поиска в Assembly (69HC11) с помощью петель. Это то, что я сделал:

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 

Проблема заключается в том, что цикл я хочу, чтобы вычислить среднюю позицию, а затем хранения в D значение, которое находится в этом положении. Я пытался написать что-то вроде $ MID, но не могу.

Answer 1

(Прежде всего я использовал этот ассемблер:.. http://www.aspisys.com/asm11.htm Это может потребоваться некоторые незначительные корректировки синтаксиса, чтобы сделать его совместимым с другой ассемблер, например, @@ указывает локальные символы в пределах текущего PROC)

Лучше работать с простыми индексами (0..N-1), а не с фактическими адресами памяти, которые в зависимости от размера слова могут сделать его более сложно рассчитать среднюю точку.

Для большей простоты вы можете использовать переменные одного байта и хвоста , но тогда ваш максимальный массив будет ограничен 256 элементами. Я оставил его как слово, давая максимум 64 тыс. Записей.

Я использовал статический массив (находящийся в ПЗУ) для простоты инициализации. Если вы хотите, чтобы массив находился в ОЗУ, вам нужно сначала инициализировать его с помощью , а вместо использования директив DW вместо этого следует использовать RMB WORD_SIZE * ARRAY_SIZE для выделения области памяти.

Нет необходимости использовать глобальные переменные вообще. Вы можете написать процедуру BinarySearch, чтобы ее можно было использовать с разными таблицами. Для примера целевое значение может быть передано в регистре D, начальном адресе массива в регистре X и количестве элементов массива в регистре . Затем ваши рабочие переменные (mid_point, target, head и tail) все могут быть динамически распределены в стеке при входе в Search и де-выделены перед выходом, а загружать результат (mid_point) в регистр X (например).

Все регистры уничтожены внутри BinarySearch. Используйте PUSH при входе и PULL на выходе, если вы хотите, чтобы они были защищены.

BinarySearch завершает работу с Carry Clear, если цель найдена, а переменная mid_point обновляется соответствующим указателем. Carry установлен, если цель не найдена , а mid_point - «мусор».

;******************************************************************************* 
; 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