NASM 程序集中二进制搜索中的段错误

Question

嗨，我正在努力找出为什么我的二进制搜索实现出现段错误（我是 NASM 程序集的新手）

抱歉，我知道它不是一个 MVP，但我想不出一个合适的方法来组装它。

%define n [ebp+8]
%define list [ebp+12]
%define low [ebp+16]
%define high [ebp+20] ; Parameters loading from the stack
binary_search:
  push ebp
  mov ebp, esp

  mov ebx, n
  mov edi, list
  mov ecx, low
  mov edx, high

  cmp ecx, edx ; if (low > high)
  jg .FIRST

  mov eax, edx ; Next few lines for mid = low + (high - low)/2
  sub eax, ecx
  sar eax, 1 ; Will this give an appropriate index? (i.e is it floor division?)
  add eax, ecx
  lea esi, [edi+eax*4] ;Getting list[mid]
  cmp ebx, [esi]; if (n == list[mid])
  je .END
  jl .SECOND
  jg .THIRD

  jmp .END

.FIRST:
  mov eax, -1 ; return -1
  jmp .END

.SECOND:
  mov edx, eax ; return middle - 1
  dec edx
  jmp .CONTINUE

.THIRD:
  mov ecx, eax ; low = mid - 1
  dec ecx
  jmp .CONTINUE

.CONTINUE:
  push edx
  push ecx
  push edi
  push esi
  push ebx
  call binary_search ; recursive call, causing the segfault.
  pop ebx
  pop esi
  pop edi
  pop ecx
  pop edx
  jmp .END

.END:
  mov esp, ebp
  pop ebp
  ret

在注释掉不同的部分后，我确定这肯定与我对 binary_search 的递归调用有关，这导致了段错误。（在里面找到。继续）我搞砸了不同意多次递归调用的 binary_search 主体的什么东西？

二分查找算法：

binary_search(n, list, low, high)

    if (low > high)
        return -1

    mid = low + (high - low) / 2

    if (n == list[mid])
       return middle;
    if (n < list[mid])
       high = mid - 1
    else
        low = mid + 1

    return binary_search(n, list, low, high)

我知道这是不可能的，谢谢 :)

编辑：它的 32 位模式

Answer 1

这部分定义了您的函数的协议：

%define n [ebp+8]
%define list [ebp+12]
%define low [ebp+16]
%define high [ebp+20] ; Parameters loading from the stack
binary_search:
  push ebp
  mov ebp, esp

dword [ebp] 将保存旧的 ebp 值，dword [ebp+4] 将保存旧的 eip 到 return ，然后你的参数随之而来。它们依次是 n、list、low 和 high。随着堆栈向下增长，您需要按顺序压入堆栈，以便首先压入地址最高的参数（恰好是“高”），然后压入第二高的参数（低），依此类推（列表，n， eip, ebp).

下一部分确定您使用哪些寄存器来保存从这些堆栈帧参数初始化的变量：

  mov ebx, n
  mov edi, list
  mov ecx, low
  mov edx, high

（在递归调用之前修改了 ecx 或 edx。但它们仍然充当该代码中的“低”和“高”变量。）

现在检查您的递归调用站点。本质上，您希望再次将您正在使用的所有寄存器传递给该函数。 ebx = n，edi = 列表，ecx = 低，edx = 高。这就是你要做的：

.CONTINUE:
  push edx
  push ecx
  push edi
  push esi
  push ebx
  call binary_search ; recursive call, causing the segfault.
  pop ebx
  pop esi
  pop edi
  pop ecx
  pop edx

如果您将推送的变量与您的函数协议所期望的堆栈帧参数相匹配，您将得到：

  push edx    ; (unused)
  push ecx    ; high
  push edi    ; low
  push esi    ; list
  push ebx    ; n
  call binary_search

esi 表示的变量仅供您的函数内部使用。它不需要传递给后续调用。更重要的是，它会扰乱您的函数协议。 edx、ecx 和 edi 被推高一个堆栈槽，比它们应该将这些变量传递给您的递归调用。解决方案是在此处删除 push esi 和 pop esi。

您的代码还有一些潜在问题：

正如我在评论中提到的，您应该使用 inc ecx 而不是 dec ecx。
你的程序调用这个函数的调用约定是什么？您似乎使用了很多寄存器并且只保留 ebp 和 esp.
如果您的调用约定允许无限制地更改堆栈帧参数内容，您可以通过带有参数的“尾调用”替换用于递归的文字 call更改为您当前传递给 call 的那些。和 re-using 整个堆栈框架。不过，此时它看起来与循环非常相似。也许您确实想要一个实际的（字面上的）递归实现。 tail-call-optimised 或迭代方法需要 O(1) 的堆栈 space，而不是你的 O(log2 n)。

NASM 程序集中二进制搜索中的段错误

Seg faults in Binary search in NASM assembly

assembly

nasm

binary-search