Récursive de Fibonacci en Assemblée

Je suis d'essayer de mettre en œuvre un appel récursif de Fibonacci programme à l'Assemblée. Cependant, mon programme plante, avec une exception non gérée, et je n'arrive pas à choisir le problème. Je ne doute pas que cela implique de mon utilisation incorrecte de la pile, mais je n'arrive pas à un point où...

.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

Aussi, j'ai poussé à le nombre que j'utilise pour obtenir la valeur de Fibonacci de la pile dans une procédure externe. Toute idée d'où le problème pourrait se situer?

OriginalL'auteur muttley91 | 2011-04-11

assembly fibonacci

6

Lorsque vous effectuez une call, l'adresse de la prochaine opération est poussé sur la pile en tant que valeur de retour. Lors de la création d'une fonction, il est souvent d'usage de créer un "stack frame". Ce cadre peut être utilisé pour imprimer la pile d'appel, ainsi que d'un décalage pour les variables locales et les arguments. Le cadre est créé par le biais de deux opérations au début de la fonction:
```
push ebp
mov ebp, esp
```
À la fin de la fonction, la pile d'appel est retiré à l'aide de leave, ce qui est équivalent à l'inverse de ces 2 opérations. Lors de l'utilisation d'un cadre de pile, la valeur de esp est stocké dans ebp, le faisant pointer vers un emplacement sur la pile appelé la structure de base. Depuis, au-dessus de cette adresse, il y a l'ancienne valeur de ebp et l'adresse de retour, vous devriez normalement obtenir le premier argument en utilisant [ebp+8]. Cependant, vous n'avez pas défini un cadre de pile. Cela signifie que l'ancienne valeur de ebp n'a pas été poussé sur la pile et la valeur actuelle de ebp ne peut pas être utilisé pour obtenir des arguments parce que vous ne savez pas où il est. Par conséquent, vous devriez obtenir votre argument en utilisant [esp+4].

Aussi, il est d'usage que les valeurs de retour sont placés dans eax et ebx être préservées pour l'appelant. Votre code ne permet pas de suivre l'une de ces conventions. Aussi, techniquement, les fonctions ne sont pas nécessaires à la préservé ecx ou edx, donc, normalement, vous devriez pousser à la pile avant l'appel d'une autre fonction si vous souhaitez les conserver. Avec ce code, edx et ebx serait remplacée si elle est appelée avec une valeur supérieure à 2, ce qui provoque un résultat non valide.

Voici une liste complète qui inclut tous les correctifs que j'ai mentionnés. Je n'ai pas de créer un cadre de pile comme il n'est pas nécessaire et que votre code n'a pas.
```
.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
```
Après l'utilisation de ce, le code fonctionne correctement, mais il se bloque toujours quelque part. Hors de debug - merci!

OriginalL'auteur ughoavgfhw
5

Plusieurs problèmes:
- si vous allez passer des paramètres sur la pile, vous n'avez pas le droit (standard) entrée de la fonction, de sorte EBP points à la mauvaise place
- vous n'êtes pas l'enregistrement de la valeur de l'argument correctement dans edx
Voici ce que je pense que vous avez voulu, en supposant que vous êtes de passage des paramètres sur la pile (le plus simple pour ajouter un commentaire pour chaque instruction
rendre clair ce que vous pensez que cela fonctionne):
```
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
```
Mais vous n'avez pas à passer les paramètres sur la pile. Il est plus efficace d'utiliser les registres:
```
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
```
Vous avez oublié de pop ebp à la fin. Ce code va toujours revenir à un emplacement sur la pile.
Yep, merci, fixe. Va juste pour prouver que l'auto-proclamé des experts vis en place, trop
J'ai fait les réglages, mais mon code ne fonctionne toujours pas. Cependant, cette réponse semble toujours être la réponse que je cherche. Je crois que mon problème est ailleurs, maintenant. Comme pour l'utilisation de registres, j'ai essayé cette origine, mais il juste ne semble pas fonctionner. Je vais peut-être lui donner une autre chance. Merci!
Nous avons déjà compris que l'expert ne peut pas le code de droit :- } Utiliser un débogueur et unique étape les instructions. Il ne vous faudra pas longtemps pour comprendre le problème et l'expérience est inestimable.
vous avez fait de choisir le patch, j'ai fait basé sur ughoavgfw (wow) observation?

OriginalL'auteur Ira Baxter
1

Tout d'abord, vous êtes à l'aide d'une pile de décalage de 8 de EBP, pourquoi? Ne pas vous dire ESP? Et un appel normal n'utilise qu'un seul 32 bits de la cellule, de sorte que votre arg doit être à la position 4. Je suis assez sûr que d'autres problèmes existent, mais vous pouvez commencer à le faire.

Vous devriez écrire des pseudo-code de sorte que vous, et nous pouvons voir ce que vous essayez d'accomplir.

Si vous voulez tricher, googler "msna récursive de fibonacci" vous emmène à un programme de travail. Mais vous allez être un meilleur programmeur si vous le résoudre vous-même.

OriginalL'auteur jcomeau_ictx

Vous devez vous connecter pour publier un commentaire.