嗨，我正在努力找出为什么我的二进制搜索实现存在段错误（我是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错误。（位于.CONTINUE内部）我该如何混淆与多个递归调用不同的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位模式
这部分定义了函数的协议：
%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返回旧值，然后遵循您的参数。依次为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 ecxnot dec ecx。
程序调用该函数的调用约定是什么？您似乎正在使用大量寄存器，并且仅保留ebp和esp。
如果您的调用约定允许无限制地更改堆栈框架参数的内容，则可以call通过“尾部调用”替换用于递归的文字，将参数更改为当前传递给的参数call。并重新使用整个堆栈框架。不过，这看上去与循环非常相似。也许您确实想要一个实际的（字面意义上的）递归实现。但是，尾部调用优化或迭代方法需要O（1）的堆栈空间，而不是O（log2 n）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句