assembly - recursividad - serie fibonacci funcion

Fibonacci recursivo en Asamblea

Question

Estoy intentando implementar un programa recursivo de Fibonacci en la Asamblea. Sin embargo, mi programa falla, con una excepción no controlada, y parece que no puedo distinguir el problema. No dudo que se trate de mi uso incorrecto de la pila, pero no puedo señalar dónde ...

.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

Además, presioné el número que estoy usando para obtener el valor de Fibonacci en la pila en un procedimiento externo. ¿Alguna idea de dónde podría estar el problema?

Answer 1

Cuando realiza una call , la dirección de la siguiente operación se envía a la pila como un valor de retorno. Al crear una función, a menudo es costumbre crear un "marco de pila". Este marco se puede utilizar para imprimir la pila de llamadas, así como un desplazamiento para variables locales y argumentos. El marco se crea mediante dos operaciones al comienzo de la función:

push ebp
mov ebp, esp

Al final de la función, la pila de llamadas se elimina usando leave , que es equivalente al reverso de esas 2 operaciones. Cuando se utiliza un marco de pila, el valor de esp se almacena en ebp , lo que hace que apunte a una ubicación en la pila llamada base del marco. Dado que, encima de esta dirección, está el antiguo valor de ebp y la dirección de retorno, normalmente obtendría el primer argumento usando [ebp+8] . Sin embargo, no configuró un marco de pila. Esto significa que el valor anterior de ebp no se ebp a la pila, y el valor actual de ebp no se puede usar para obtener argumentos porque no se sabe dónde está. Por lo tanto, deberías obtener tu argumento usando [esp+4] .

Además, es habitual que los valores devueltos se coloquen en eax y se preserve ebx para la persona que llama. Su código no sigue ninguna de estas convenciones. Además, técnicamente no se requieren funciones para ecx o edx preservados, por lo que normalmente deberías empujarlos a la pila antes de llamar a otra función si quieres que se conserven. Con este código, edx y ebx se sobrescribirán si se llama con un valor mayor que 2, lo que causa un resultado no válido.

Aquí hay una lista completa que incluye todas las correcciones que he mencionado. No creé un marco de pila ya que no es necesario y tu código no.

.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

Primero, estás usando un desplazamiento de pila de 8 de EBP, ¿por qué? ¿No te refieres a ESP? Y una llamada normal solo usa una celda de 32 bits, por lo que su argumento debería estar en el desplazamiento 4. Estoy bastante seguro de que existen otros problemas, pero puede comenzar con eso.

Probablemente deberías escribir algunos pseudocódigos para que tú y nosotros podamos ver lo que estás tratando de lograr. Si quiere hacer trampa, buscar en Google "nasa recursive fibonacci" lo lleva a un programa de trabajo. Pero serás un mejor programador si lo resuelves tú mismo.

Answer 3

Varios problemas:

• si va a pasar parámetros en la pila, no tiene la entrada de la función correcta (estándar), por lo que EBP apunta al lugar equivocado
• no está guardando correctamente el valor del argumento en edx

Esto es lo que creo que usted quería, suponiendo que está pasando parámetros en la pila (lo mejor es agregar un comentario a cada instrucción dejando en claro lo que cree que es):

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

Pero no tienes que pasar los parámetros en la pila. Es más eficiente usar los registros:

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