汇编中的递归Fibonacci

Question

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

.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

此外,我已经推送了我用于在外部过程中将Fibonacci值转换为堆栈的数字.任何想法可能存在的想法？

Answer 1

几个问题：

• 如果要在堆栈上传递参数，则没有正确的（标准）函数条目，因此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

Answer 2

执行a时call,下一个操作的地址将作为返回值推送到堆栈.在创建函数时,通常习惯于创建"堆栈帧".此框架可用于打印调用堆栈,以及局部变量和参数的偏移量.通过函数开头的两个操作创建框架:

push ebp
mov ebp, esp

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

此外,习惯上将返回值放入eax并ebx保留给调用者.您的代码不遵循这些约定.此外,技术上不需要保留函数,ecx或者edx通常在调用另一个函数之前将它们推送到堆栈中,如果你想保留它们的话.有了这个代码,edx并ebx会如果调用使用大于2的值被覆盖,导致无效结果.

这是一个完整的列表,其中包括我提到的所有修复程序.我没有创建堆栈框架,因为它没有必要,而你的代码没有.

.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