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

Question

嗨，我正在努力找出为什么我的二进制搜索实现是seg故障(我是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的递归调用有关，这导致了seg错误。(在里面找到。继续(在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

双字[ebp]将保存旧的ebp值，双字[ebp+4]将保存要返回的旧eip值，然后您的参数将跟随。按此顺序，这些是n、list、low和high。当堆栈向下增长时，您需要按顺序推送堆栈，以便首先推送最高寻址参数(恰好为"高"(，然后推送第二高(低(，依此类推(list，n，eip，ebp(。

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

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

(ecx或edx在递归调用之前被修改。但它们仍然充当该代码中的"低"one_answers"高"变量。(

现在检查您的递归调用站点。从本质上讲，您希望将正在使用的所有寄存器再次传递给函数。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替换为"；尾部呼叫"；参数更改为当前传递给CCD_ 24的参数。并重新使用整个堆栈帧。不过，在这一点上，它看起来非常类似于一个循环。也许您确实想要一个实际的(字面上(递归实现。尾部调用优化或迭代方法需要O(1(的堆栈空间，而不是O(log2n(。