我应该如何为字节和字大小的数组编写一个代码 对于一个字节大小的数组和另一个字大小的数组,下面的代码不会终止
在这个代码中,气泡排序算法用于对两个名为data和data2的数组进行排序,但当我运行代码时,它不会终止并继续运行。我写的代码是正确的还是应该有更改?
[org 0x0100]
jmp start
data: dw 60,40,50,22,5
data2: db 3,4,1,9,6
swapflag: db 0
swap:
mov ax, [bx+si]
xchg ax, [bx+si+2]
mov [bx+si], ax
ret
bubblesort:
dec cx
shl cx, 1
mainloop:
mov si, 0
mov byte [swapflag], 0
innerloop:
mov ax, [bx+si]
cmp ax, [bx+si+2]
jbe noswap
call swap
mov byte [swapflag], 1
noswap:
add si, 2
cmp si, cx
jne innerloop
cmp byte [swapflag], 1
je mainloop
ret
start:
mov bx, data
mov cx, 10
call bubblesort
mov bx, data2
mov cx, 20
call bubblesort
mov ax, 0x4c00
int 0x21
mov bx, data mov cx, 10 <<< 5 elements !!! call bubblesort mov bx, data2 mov cx, 20 <<< 5 elements !!! call bubblesort
您调用的bubblesort子例程的计数对于现有的5元素数组来说太高了。这个错误将处理垃圾数据,但不能解释为什么";它不终止";。
无限循环问题存在,因为在内部循环结束时,您忘记降低CX寄存器中的限制。正是通过降低限制,我们表明最后一个要素已经到位,我们不再需要考虑它,从而减少了任务并朝着结束的方向努力。
接下来是代码的更正版本。我没有优化它,这样你仍然可以识别问题以及它是如何解决的。
; IN (bx,cx)
bubblesort16:
dec cx
shl cx, 1 *
mainloop:
mov si, 0
mov byte [swapflag], 0
innerloop:
mov ax, [bx+si] *
cmp ax, [bx+si+2] *
jbe noswap
swap: ;
xchg ax, [bx+si+2] * ; better have this inlined
mov [bx+si], ax * ;
mov byte [swapflag], 1
noswap:
add si, 2 *
cmp si, cx
jne innerloop
cmp byte [swapflag], 0 ;
je done ;
sub cx, 2 * ; new (solution)
jnz mainloop ;
done: ;
ret
我用星号标记了字节大小版本需要更改的行。
我应该如何为字节和字大小的数组编写单个代码?
我对拥有一个可以处理字节和字数组的单一代码的第一反应是,由于内部循环中有额外的分支,这会导致代码速度变慢。事实证明并非如此。我成功地编写了一个双Bubblesort代码,该代码满足了要求,并且与相应的BubbleSort16和BubbleSort8版本性能相当(甚至快一点(。@PeterCodes在评论中给出的建议对得出这一结果非常有帮助
双重解决方案的一个小缺点是,除了计数和地址外,它还需要CX={1=字节,2=字}中的第三个不同参数。
; --------------------------------------
; IN (ax,bx,cx) OUT () MOD (ax,dx,si,di,bp)
BubbleSort:
sub ax, 1 ; Number of elements
jbe .Done
mul cx
add ax, bx ; -> Address of the last element
xor bp, bp ; SwapFlag [0,1]
.Outer: mov si, bx
.Inner: mov dx, [si]
cmp cx, 2
jb .Byte
.Word: mov di, [si+2]
cmp dx, di
jle .Skip
mov [si+2], dx
mov [si], di
mov bp, 1
.Skip: add si, cx ; CX=[1,2]
cmp si, ax
jb .Inner
.Both: dec bp
jnz .Done
sub ax, cx ; CX=[1,2]
cmp bx, ax
jb .Outer
.Done: ret
.Byte: cmp dl, dh
jle .Skip
rol dx, 8
mov [si], dx
mov bp, cx ; CX=1
inc si
cmp si, ax
jb .Inner
jmp .Both
; --------------------------------------
; IN (ax,bx) OUT () MOD (ax,dx,si,bp)
BubbleSort8:
nop
nop
sub ax, 1 ; Number of elements
jbe .Done
add ax, bx ; -> Address of the last element
xor bp, bp ; SwapFlag [0,1]
.Outer: mov si, bx
.Inner: mov dx, [si]
cmp dl, dh
jle .Skip
rol dx, 8
mov [si], dx
mov bp, 1
.Skip: inc si
cmp si, ax
jb .Inner
dec bp
jnz .Done
dec ax
cmp bx, ax
jb .Outer
.Done: ret
; --------------------------------------
; IN (ax,bx) OUT () MOD (ax,dx,si,di,bp)
BubbleSort16:
sub ax, 1 ; Number of elements
jbe .Done
shl ax, 1
add ax, bx ; -> Address of the last element
xor bp, bp ; SwapFlag [0,1]
.Outer: mov si, bx
.Inner: mov dx, [si]
mov di, [si+2]
cmp dx, di
jle .Skip
mov [si+2], dx
mov [si], di
mov bp, 1
.Skip: add si, 2
cmp si, ax
jb .Inner
dec bp
jnz .Done
sub ax, 2
cmp bx, ax
jb .Outer
.Done: ret
; --------------------------------------
英特尔奔腾双核T2080:上的测量时间
Sorting an array with 46 bytes
------------------------------
BubbleSort 17.2 µsec - 17.3 µsec
BubbleSort8 17.2 µsec - 18.5 µsec
Sorting an array with 23 words
------------------------------
BubbleSort 3.8 µsec - 3.9 µsec
BubbleSort16 4.1 µsec - 4.3 µsec