2

我正在尝试在 64 位 Linux 上运行的 NASM 中实现一个数组的选择排序。

数组声明为：

section .bss
strbuf resb 10
small  resb  1  ; current minimum value

排序算法本身很简单，但我觉得受到两件事的限制：可用寄存器的数量，以及无法交换立即数（即括号）

我需要跟踪未排序的数组边界、它的索引、当前最小值的位置以及它的索引。那已经是四个寄存器了。我还需要跟踪两个循环计数器，一个用于表示未排序数组边界的外循环，另一个用于每次遍历的迭代（即内循环）。那是另外两个，总共六个寄存器。

由于立即数不能相互移动，例如mov [var1], [var2]当我需要交换两个元素时，我需要使用寄存器作为临时占位符。在跟踪哪些寄存器保存哪些信息方面，这很快变得笨拙！

以下是我迄今为止的尝试。请注意，这是触发分段错误的非工作代码。但也许你能察觉到我想要做什么，并指出我的方法哪里出了问题。

我不希望使用简化结构的宏，例如那些提供 .IF 和 .ELSE 的宏。

; ====== Sorting begins here ======
sorting:
    mov edi, strbuf  ; outer loop pointer
    mov esi, strbuf  ; inner loop pointer
    mov eax, 0  ; inner loop counter
    mov ebx, 0  ; outer loop counter

innerloop:
    ; store the value of first element in [small]
    mov edx, [esi]
    mov [small], edx

    ; compare the current small value with the value pointed by esi
    mov edx, [esi]  
    cmp [small], edx

    jg  new_small
    inc esi
    inc eax
    cmp eax, 9
    jle innerloop
    cmp eax, 9
    jg  innerloop_done

new_small:
    mov [small], edx  ; save the new small value
    mov ecx, esi      ; save its index in ecx
    inc esi
    inc eax
    cmp eax, 9

    jle     innerloop

innerloop_done:
    ; When the inner loop is completed...
    ; First, do the swap
    push    rax
    mov eax, [edi]
    mov edx, [small]
    mov [ecx], edx
    pop rax

    inc edi  ; move the outer loop pointer forward
    inc esi  ; move the inner loop pointer forward
    inc ebx  ; increment the outer loop counter (the unsorted array becomes smaller)
    inc eax  ; increment the inner loop counter (same reason as above)
    cmp ebx, 9

    jle innerloop   

; ====== Sorting ends here ======
4

2 回答 2

2

如果这应该在 64 位模式下执行，则必须使用 64 位地址，这意味着当您获取这些地址并将它们放入寄存器时，这些接收寄存器也必须是 64 位的，否则您将截断地址和访问内存不是你想要的。

另外，您没有调试器来单步执行您的代码吗？

于 2012-04-29T07:38:50.823 回答
1

对于 64 位代码，有 16 个通用寄存器：RAX、RBX、RCX、RDX、RSI、RDI、RSP、RBP、R8、R9、R10、R11、R12、R13、R14、R15。

其中，RSP 有一个特殊用途，只能用于该用途（当前堆栈地址）。RBP 寄存器通常由编译器用于跟踪堆栈帧（不包括“-fomit-frame-pointer”可能性），但您不是编译器，可以将它用于任何您喜欢的事情。

这意味着在您可以使用的 15 个寄存器中，您只使用了其中的 6 个。

如果您确实确实用完了寄存器，那么您可以将一些东西转移到堆栈空间。例如：

foo:
    sub rsp,8*5        ;Create space for 5 values
%define .first   rsp
%define .second  rsp+8
%define .third   rsp+8*2
%define .fourth  rsp+8*3
%define .fifth   rsp+8*4
%define .first   rsp+8*5

    mov [.first],rax
    mov [.second],rax
    mov rax,[.first]
    add rax,[.second] 
    mov [.third],rax
...
    add rsp,8*5        ;Clean up stack
    ret

希望您可以看到堆栈上可能有数百个值，并在需要时使用一些寄存器（临时）保存这些值。通常你会计算出最常使用的值（例如在内部循环中）并尝试为它们使用寄存器并将堆栈用于最不常用的变量。但是，对于 64 位代码（您可以使用更多的 8 个寄存器），寄存器用完的情况很少见，如果您这样做了，这可能表明您需要将例程拆分为多个例程。

于 2012-04-30T03:31:36.660 回答