二进制搜索程序集68HC11

Question

我必须在汇编(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..N1)，而不是实际的内存地址，这取决于单词的大小，这可能会使计算中点变得更加困难。

为了更简单，您可以使用单字节头和尾变量，但是最大数组将限制在256个条目。我把它作为单词留下，最多给出64K的条目。

为了简化初始化，我使用了一个静态数组(驻留在ROM中)。如果希望数组位于RAM中，则需要首先使用一些数据初始化数组，而不是使用DW指令，而应该使用人民币WORD_SIZE*ARRAY_SIZE来分配内存区域。

根本不需要使用全局变量。您可以编写BinarySearch例程，以便它可以与不同的表一起使用。例如，目标值可以在寄存器D中传递，寄存器X中数组的起始地址和寄存器Y中的数组元素数。然后，您的工作变量(mid_point、目标、头和尾)都可以在进入搜索时在堆栈上动态分配，并在退出之前取消分配，同时将结果(mid_point)加载到寄存器X中(例如)。

所有寄存器都在BinarySearch中销毁。如果您想要保护入口，请在出口处使用推送和拉。

如果找到目标，则BinarySearch退出，并使用相关指针更新mid_point变量。如果找不到目标，就设置进位，而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