IA-32架构下递归二分查找x86汇编代码段错误排查求助

我需要把以下C语言的递归二分查找函数，实现为IA-32架构下的Intel x86汇编代码，但编写的汇编除特定测试用例外均出现段错误，附上C代码与我的汇编代码，请求帮忙排查问题。

原C代码 #

int binary_search(int n, int list[], int low, int high) 
{
    int middle;

    if (low > high) {
        return -1;
    }
       
    middle = low + (high-low) / 2;

    if (n == list[middle]) {
        return middle;
    }
    if (n < list[middle]) {
        high = middle - 1;
    } else {
        low = middle + 1;
    }
    
    return binary_search(n, list, low, high);
}

我编写的汇编代码 #

;*****************************************************************************
;* int binary_search(int n, int list[], int low, int high);                  *
*****************************************************************************
%define high [ebp+20]
%define low [ebp+16]
%define list [ebp+12]
%define n [ebp+8] ;;;define variables
binary_search:
  push ebp
  mov ebp, esp ; initialise stack frame

  mov eax, low 
  cmp eax, high  

  jg .baseCase ; if low > high, .baseCase
  jle .middle ; if low <= high, .middle

.baseCase:
  mov eax, -1
  pop ebp
  ret

.middle: ;calculate middle
  push ebx
  push ecx
  push edx
  push esi
  push edi

;middle = low + (high-low) / 2
  mov eax, high
  sub eax, low 
  sar eax, 1
  
  xor ecx, ecx ; clean ecx
  xor edx, edx ; clean edx

  mov esi, list
  mov ecx, n

  mov ebx, [esi+eax*4] ; ebx <- list[middle]
  mov edi, eax ; edi <- eax

  cmp ecx, ebx ; if list[middle] == n, return mid
  jl .recurseDecHigh
  jg .recurseIncLow

  pop edi
  pop esi
  pop edx
  pop ecx
  pop ebx
  pop ebp
  ret ; return middle, currently in eax

.recurseDecHigh:
  mov eax, list
  push eax
  mov eax, n
  mov eax, low
  push eax
  mov eax, edi
  dec eax
  push eax

  xor ecx, ecx
  xor edx, edx

  call binary_search

  pop edi
  pop esi
  pop edx
  pop ecx
  pop ebx
  pop ebp
  ret

.recurseIncLow:
  mov eax, list
  push eax
  mov eax, n
  push eax
  mov eax, edi
  inc eax
  push eax
  mov eax, high
  push eax

  xor ecx, ecx
  mov edx, edx

  call binary_search

  pop edi
  pop esi
  pop edx
  pop ecx
  pop ebx
  pop ebp
  ret

错误分析 #

• Middle值计算错误：原C代码中middle = low + (high-low)/2，但汇编里只计算了(high-low)/2并赋值给eax，没有加上low，导致middle的值完全错误，访问数组时要么越界要么取错元素，直接引发段错误。
• 递归参数压栈顺序错误：C的cdecl调用约定要求参数从右往左压栈，原函数参数顺序是n, list, low, high，所以递归调用时应该先压high，再压low，接着压list，最后压n。你的代码里参数顺序完全混乱，导致递归时函数拿到的参数全错，访问非法内存。
• 递归调用后的栈平衡错误：调用binary_search前push了4个参数，但调用后没有弹出这些参数就直接恢复寄存器并返回，导致栈里残留的参数没有被清理，栈指针错位，后续操作必然出错。
• 寄存器恢复逻辑错误：在.middle段保存了ebx、ecx等寄存器，但递归分支里在调用返回后直接pop这些寄存器，没有考虑call指令压入栈的返回地址，加上之前的参数没清理，栈结构完全混乱，最终触发段错误。
• 冗余操作干扰：比如.recurseIncLow里的mov edx, edx是无效操作，部分xor ecx, ecx/xor edx, edx属于冗余操作，可能干扰正确的寄存器值。

修正后的汇编代码 #

;*****************************************************************************
;* int binary_search(int n, int list[], int low, int high);                  *
;* 遵循cdecl调用约定：参数从右往左压栈，调用者清理栈                          *
*****************************************************************************
%define high [ebp+20]
%define low [ebp+16]
%define list [ebp+12]
%define n [ebp+8]

binary_search:
    push ebp
    mov ebp, esp        ; 初始化栈帧

    mov eax, low
    cmp eax, high
    jg .baseCase        ; low > high，进入基准情况

    ; 计算middle = low + (high - low)/2
    mov eax, high
    sub eax, low
    sar eax, 1          ; 算术右移等价于除以2（针对有符号数）
    add eax, low        ; 补上low，得到正确的middle值
    mov edi, eax        ; 保存middle到edi

    ; 取出list[middle]
    mov esi, list
    mov ebx, [esi + edi*4]  ; ebx = list[middle]
    mov ecx, n

    ; 比较n和list[middle]
    cmp ecx, ebx
    je .found           ; 相等，返回middle
    jl .recurse_dec_high; n < list[middle]，递归时high=middle-1
    jg .recurse_inc_low; n > list[middle]，递归时low=middle+1

.found:
    ; 恢复寄存器，返回middle（eax中）
    pop ebp
    ret

.baseCase:
    mov eax, -1
    pop ebp
    ret

.recurse_dec_high:
    ; 按右往左顺序压参数：high(middle-1), low, list, n
    mov eax, edi
    dec eax
    push eax            ; 压入新的high = middle-1
    push low            ; 压入原low
    push list           ; 压入原list
    push n              ; 压入原n

    call binary_search

    ; 清理栈上的4个参数（每个4字节，共16字节）
    add esp, 16
    pop ebp
    ret

.recurse_inc_low:
    ; 按右往左顺序压参数：high, low(middle+1), list, n
    push high           ; 压入原high
    mov eax, edi
    inc eax
    push eax            ; 压入新的low = middle+1
    push list           ; 压入原list
    push n              ; 压入原n

    call binary_search

    ; 清理栈上的4个参数
    add esp, 16
    pop ebp
    ret

内容的提问来源于stack exchange，提问作者Ceetron