Рекурсивный Фибоначчи в сборке

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

Когда вы выполняете call, адрес следующей операции помещается в стек как возвращаемое значение.При создании функции часто принято создавать «кадр стека».Этот кадр можно использовать для печати стека вызовов, а также смещения для локальных переменных и аргументов.Кадр создается с помощью двух операций в начале функции:

push ebp
mov ebp, esp

В конце функции стек вызовов удаляется с использованием leave, что эквивалентно обратному выполнению этих двух операций.,При использовании фрейма стека значение esp сохраняется в ebp, что указывает на местоположение в стеке, называемое основанием фрейма.Поскольку выше этого адреса есть старое значение ebp и адрес возврата, вы обычно получите первый аргумент, используя [ebp+8].Однако вы не установили фрейм стека.Это означает, что старое значение ebp не было помещено в стек, а текущее значение ebp нельзя использовать для получения аргументов, поскольку вы не знаете, где оно находится.Поэтому вы должны получить аргумент, используя [esp+4].

Кроме того, обычно возвращаемые значения помещаются в eax и ebx сохраняется для вызывающей стороны.Ваш код не соответствует ни одному из этих соглашений.Кроме того, технически функции не требуются для сохранения ecx или edx, поэтому обычно вы должны помещать их в стек перед вызовом другой функции, если вы хотите, чтобы они были сохранены.С помощью этого кода edx и ebx будут перезаписаны, если их вызвать со значением, превышающим 2, что приведет к неверному результату.

Вот полный список, который включает все упомянутые мной исправления.Я не создал фрейм стека, так как он не нужен, а ваш код этого не сделал.

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

Answer 3

Во-первых, вы используете смещение стека 8 от EBP, почему? Разве вы не имеете в виду ESP? И обычный вызов использует только одну 32-битную ячейку, поэтому ваш аргумент arg должен быть со смещением 4. Я вполне уверен, что существуют другие проблемы, но вы можете начать с этого. <ч /> Возможно, вам следует написать какой-нибудь псевдокод, чтобы вы и мы могли видеть, чего вы пытаетесь достичь. <ч /> Если вы хотите обмануть, прибегая к помощи «nasm recursive fibonacci», вы попадете в рабочую программу. Но вы станете лучшим программистом, если решите это сами.