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