在使用指针增量与索引寻址模式的插入排序中跟踪两个不同的数组索引？

Question

所以为了自学循环和条件，我尝试实现 Wikipedia:

中的插入排序算法

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

我想我已经翻译了 可以很好地组装的代码，但它无法运行。我认为问题的原因可能与索引有关（特别是 A[j or j - something] 部分），但我无法修复它。这是我的代码：

.386 
.model flat,stdcall
.stack 4096

ExitProcess proto,dwExitCode:dword

.data
arr DWORD 4,5,1,7


.code
main proc
mov esi, OFFSET arr
mov eax, 1 ; eax is i, i <- 1

L2:

    mov ebx, eax ; ebx is j, j <- i

    ; while j > 0
    INNERWHILE:
    cmp ebx, 0
    jle L3  

    ; and A[j-1] > A[j]
    mov ecx, [esi + 4*ebx] ; A[j]
    sub esi, 4
    cmp [esi + 4*ebx], ecx ;A[j-1] > A[j]
    jle L3

    ; swap A[j] and A[j-1]
    mov edx, [esi + 4*ebx] ; edx = A[j-1]
    add esi, 4
    mov ecx, [esi + 4*ebx] ; ecx = A[j]

    ; Begin Swap
    mov [esi + 4*ebx], edx ; A[j-1] <- A[j]
    sub esi, 4
    mov [esi + 4*ebx], ecx  ; A[j] <-  A[j-1]
    dec ebx
    jmp INNERWHILE
L3:
inc eax
cmp eax, LENGTHOF arr
jl L2
invoke ExitProcess,0
main ENDP
END main

感谢任何帮助，我的水平是 x86 的初学者，所以欢迎任何提示。

这就是我感到困惑的地方：高级语言假设数组从 0 开始并继续移动。但是 A[j] != [esi] 因为 j 可能不是 = 0，因此，我完全陷入了基于索引的寻址部分。

Answer 1

您尝试将 esi 用作 A+i 并将 ebx 用作 j。

似乎是在给自己找麻烦

为 A、i 和 j 使用总共三个不同的寄存器而不是试图优化 A+i ] 到一个寄存器中。

所以 A[i] 是 [esi + edi*4] 而 A[j] 是 [esi + ebx*4].

那将是将该伪代码直接翻译成 asm。

一旦你开始工作，你可以稍后做一些优化，比如可能将 A+i 和 A+j 优化到寄存器中，这样你就可以使用 [reg] 寻址模式而不是 [reg+idx*4]寻址模式。

并且您可能根本不将 A 保留在寄存器中，而仅将其用作 j>0 的内存源操作数，而不是 cmp edx, OFFSET arr 或 cmp edx, [esp+0] 如果您假装基地址不是编译时常量并将其压入堆栈。

然后 j = i 变成 mov edx, esi.

您可能想将伪代码转换为 C 并查看优化编译器的作用。（编写一个将指针作为函数 arg 的排序函数，因此编译器无法对常量数组进行常量传播，而只是发出存储常量排序结果的代码 :P）http://gcc.godbolt.org/ is handy for that, and see also .

在使用指针增量与索引寻址模式的插入排序中跟踪两个不同的数组索引？

Keeping track of two different array indices in insertion sort with pointer increments vs. indexed addressing modes?

x86

masm

insertion-sort