Попытка сделать бинарный поиск по упорядоченному массиву в сборке Motorola 68k - PullRequest
Новая
       34

Попытка сделать бинарный поиск по упорядоченному массиву в сборке Motorola 68k

0 голосов
/ 30 апреля 2018

Я пытаюсь выяснить, как сделать процедуру двоичного поиска в массиве ORDERED, используя m68k. Для Java я бы сделал 

int binSearch(int key, int &lo, int &hi) 
{
    if (hi < lo)
        return NOT_FOUND;                  //RETURN with V = 1  
    int mid = (lo+hi) / 2;
    if (key == array[mid])
        return mid;
    else if (key < array[mid])             // go left
        return binSearch(key, lo, mid-1);  // left
    else
       return binSearch(key, mid+1, hi);   // right
}

Я пытаюсь собрать это в сборку. То, что я пока имею, это 

link        A6,#0
movem.l     D1/A1-A2,-(sp) 
move.w      8(A6),D1   *key t
movea.l     10(A6),A1  *lo
movea.l     14(A6),A2  *hi
cmpa.l      A1,A2 *if hi>lo
BHS            else
move.l      A1,D1 *low D1
add.l       A2,D1 *adds hi
asr.l       #1,D1 * divide by 2

В основном, что мне делать в этот момент? Сравниваю ли я D1 с номером, который я ищу, и затем, в зависимости от того, является ли он ниже и выше, снова вызывает подпрограмму? У D1 есть номер в средней точке, как я хочу, или я ошибаюсь? Заранее спасибо!

1 Ответ

0 голосов
/ 06 сентября 2018

Метод петли: 

           ORG $1000
START
            LEA       ARRAY,A0     ; start of array
            MOVE.L    #KEY,D0      ; key to find
            MOVE.W    #ELEMENTS,D1 ; length of array
            BSR.S     BINSEARCH
            ; D0 contains mid or -1 if fail
            SIMHALT

BINSEARCH
            MOVE.W     D1,D2       ; high
            MOVEQ      #0,D1       ; low
BINLOOP
            CMP.W      D2,D1       ; hi = low?
            BMI.S      NOT_FOUND
            MOVE.W     D2,D3       
            ADD.W      D1,D3
            LSR.W      #1,D3          ;mid

; there are no scaled index methods on a basic 68k
; check also that word index register addressing works on CPU
; if not some operations will have to be changed to long word

            MOVE.W     D3,D4
            LSL.W      #2,D4          ; *4 for long word
            CMP.L      (A0, D4.W),D0  ; compare mid element to key
            BEQ.S      BIN_FOUND
            BMI.S      SETLO
 SETHI      SUBQ.W     #1,D2
            MOVE.W     D3,D2          ; hi = mid-1

            BRA.S      BINLOOP
 SETLO      ADDQ.W     #1,D3
            MOVE.W     D3,D1          ; lo = mid+1
            BRA.S      BINLOOP
 NOT_FOUND  MOVEQ      #-1,D3           
 BIN_FOUND  MOVE.W     D3,D0          ; return index or -1
            RTS

            ORG $1400
ARRAY       DC.L        1,2,3,4,5,6,7,8,9,10,11
ARRAYEND
ELEMENTS    EQU         (ARRAYEND-ARRAY)/4
KEY         EQU          3
...