汇编中的递归斐波那契

Question

我正在尝试在汇编中实现递归斐波那契程序。但是，我的程序崩溃了，出现未处理的异常，而且我似乎无法找出问题所在。我不怀疑这涉及我对堆栈的不当使用，但我似乎无法指出在哪里......

.386
.model Flat
public Fibonacci
include iosmacros.inc ;includes macros for outputting to the screen

.code
Fibonacci proc

MOV EAX, [EBP+8]
CMP EAX, 1
    JA Recurse
    MOV ECX, 1
    JMP exit

Recurse:
    DEC EAX
    MOV EDX, EAX
    PUSH EAX
    CALL Fibonacci
    ADD ESP, 4
    MOV EBX, ECX
    DEC EDX
    PUSH EDX
    CALL Fibonacci
    ADD ECX, EBX
exit:
ret
Fibonacci endp


.data


end

此外，我已将用于获取斐波那契值的数字推送到堆栈中一个外部过程。有什么想法可能是问题出在哪里吗？

Answer 1

当您执行调用时，下一个操作的地址将作为返回值推送到堆栈。创建函数时，通常习惯创建“堆栈框架”。该帧可用于打印调用堆栈以及局部变量和参数的偏移量。该帧是通过函数开头的两个操作创建的：

push ebp
mov ebp, esp

在函数结束时，使用 leave 删除调用堆栈，这相当于这两个操作的相反操作。使用堆栈帧时，esp 的值存储到 ebp 中，使其指向堆栈上称为帧基址的位置。由于在此地址之上有 ebp 的旧值和返回地址，因此您通常会使用 [ebp+8] 获取第一个参数。但是，您没有设置堆栈框架。这意味着ebp的旧值没有被压入堆栈，并且ebp的当前值不能用于获取参数，因为你不知道它在哪里。因此，您应该使用 [esp+4] 来获取参数。

此外，通常将返回值放置在 eax 和 ebx 中为调用者保留。您的代码不遵循这些约定。此外，从技术上讲，函数不需要保留 ecx 或 edx，因此，如果您希望保留它们，通常应该在调用另一个函数之前将它们推送到堆栈。使用此代码，如果使用大于 2 的值调用，edx 和 ebx 将被覆盖，从而导致无效结果。

这是一个完整的列表，其中包括我提到的所有修复。我没有创建堆栈框架，因为它不是必需的，并且您的代码也没有。

.386
.model Flat
public Fibonacci
include iosmacros.inc ;includes macros for outputting to the screen

.code
Fibonacci proc

    MOV EAX, [ESP+4]
    CMP EAX, 1
    JA Recurse
    MOV EAX, 1 ; return value in eax
    JMP exit

Recurse:
    PUSH EBX ; preserve value of ebx
    DEC EAX
    PUSH EAX
    CALL Fibonacci
    MOV EBX, EAX ; ebx is preserved by callee, so it is safe to use
    DEC [ESP] ; decrement the value already on the stack
    CALL Fibonacci
    ADD EAX, EBX ; return value in eax
    ADD ESP, 4 ; remove value from stack
    POP EBX ; restore old value of ebx
exit:
ret
Fibonacci endp

Answer 2

几个问题：

• 如果要在堆栈上传递参数，则没有正确的（标准）函数入口，因此 EBP 指向错误的位置，
• 您没有在 edx 中正确保存参数值，

这就是我的想法想要，假设您在堆栈上传递参数（最好为每个指令添加注释
明确你的想法）：

Fibonacci proc
  PUSH EBP          ; save previous frame pointer
  MOV  EBP, ESP     ; set current frame pointer

  MOV  EAX, [EBP+8] ; get argument N
  CMP  EAX, 1       ; N<=1?
  JA   Recurse      ; no, compute it recursively
  MOV  ECX, 1       ; yes, Fib(1)--> 1
  JMP  exit

Recurse:
  DEC  EAX          ; = N-1
  MOV  EDX, EAX     ; = N-1
  PUSH EDX          ; save N-1
  PUSH EAX          ; set argument = N-1
  CALL Fibonacci    ; compute Fib(N-1) to ECX
  POP  EAX          ; pop N-1
  DEC  EAX          ; = N-2
  PUSH ECX          ; save Fib(N-1)
  PUSH EAX          ; set argument = N-2
  CALL Fibonacci    ; compute Fib(N-2) to ECX
  POP  EAX          ; = Fib(N-1)
  ADD  ECX, EAX     ; = Fib(N-1)+FIB(N-2)
exit:
  MOV  ESP,EBP      ; reset stack to value at function entry 
  POP  EBP          ; restore caller's frame pointer
  RET               ; and return

但是你不必在堆栈上传递参数。使用寄存器更有效：

Fibonacci proc ; computes Fib(EAX) --> EAX; do not call with EAX==0
  CMP  EAX, 1      ; N<=1?
  JBE  exit        ; yes, we have the answer
  DEC  EAX         ; = N-1
  PUSH EAX         ; save N-1
  CALL Fibonacci   ; computing FIB(n-1)to EAX
  XCHG EAX,0[ESP]  ; swap FIB(n-1) for saved N-1 (You'll love this instruction, look it up in the Intel manual)
  DEC  EAX         ; = N-2
  CALL Fibonacci   ; computing FIB(N-2) to EAX
  POP  ECX         ; = FIB(N-1)
  ADD  EAX,ECX     ; = FIB(N-1)+FIB(N-2)
exit:
  RET