7

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

.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

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

4

3 回答 3

7

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

push ebp
mov ebp, esp

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

此外，习惯上将返回值放入eax并ebx保留给调用者。您的代码不遵循这些约定中的任何一个。此外，从技术上讲，函数不需要保留ecxor 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
于 2011-04-11T04:43:45.080 回答
6

几个问题：

  • 如果要在堆栈上传递参数，则没有正确的（标准）函数入口，因此 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
于 2011-04-11T04:32:28.957 回答
1

首先，您使用的是 EBP 的 8 堆栈偏移量，为什么？你不是说ESP吗？正常调用只使用一个 32 位单元，因此您的 arg 应位于偏移量 4。我相当确定存在其他问题，但您可以从那开始。

您可能应该编写一些伪代码，以便您和我们可以看到您要完成的工作。
如果你想作弊，谷歌搜索“nasm recursive fibonacci”会带你进入一个工作程序。但是如果你自己解决它，你会成为一个更好的程序员。

于 2011-04-11T04:21:12.423 回答