Fibonacci recursiv în Assembly (Programare, Asamblare, Fibonacci)

muttley91 a intrebat.

Încerc să implementez un program Fibonacci recursiv în Assembly. Cu toate acestea, programul meu se blochează, cu o excepție neadministrată, și se pare că nu pot alege problema. Nu mă îndoiesc că este vorba de utilizarea mea necorespunzătoare a stivei, dar nu reușesc să punctez unde…

.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

De asemenea, am împins numărul pe care îl folosesc pentru a obține valoarea Fibonacci în stivă într-o procedură externă. Aveți vreo idee unde ar putea fi problema?

3 răspunsuri
ughoavgfhw

Atunci când efectuați o call, , adresa următoarei operații este împinsă în stivă ca valoare de întoarcere. Atunci când se creează o funcție, se obișnuiește adesea să se creeze un „cadru de stivă”. Acest cadru poate fi utilizat pentru a imprima stiva de apeluri, precum și un offset pentru variabilele locale și argumente. Cadrul este creat prin două operații la începutul funcției:

push ebp
mov ebp, esp

La sfârșitul funcției, stiva de apeluri este eliminată folosind leave, , care este echivalentă cu inversarea celor două operații. Atunci când se utilizează un cadru de stivă, valoarea esp este stocată în ebp, , ceea ce face ca aceasta să indice o locație de pe stivă numită baza cadrului. Deoarece, deasupra acestei adrese, se află vechea valoare de ebp și adresa de întoarcere, în mod normal veți obține primul argument folosind [ebp+8]. Cu toate acestea, nu ați configurat un cadru de stivă. Acest lucru înseamnă că vechea valoare a ebp nu a fost împinsă pe stivă, iar valoarea curentă a lui ebp nu poate fi utilizată pentru a obține argumente, deoarece nu știți unde se află. Prin urmare, ar trebui să obțineți argumentul folosind [esp+4].

De asemenea, se obișnuiește ca valorile de returnare să fie plasate în eax și ebx să fie păstrate pentru apelant. Codul dvs. nu respectă niciuna dintre aceste convenții. De asemenea, din punct de vedere tehnic, funcțiile nu sunt obligate să păstreze ecx sau edx, așa că, în mod normal, ar trebui să le împingeți în stivă înainte de a apela o altă funcție dacă doriți să le păstrați. Cu acest cod, edx și ebx ar fi suprascrise dacă ar fi apelate cu o valoare mai mare de 2, provocând un rezultat invalid.

Iată o listă completă care include toate corecturile pe care le-am menționat. Nu am creat un cadru de stivă, deoarece nu este necesar, iar codul dvs. nu a făcut-o.

.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

Comentarii

  • După ce am utilizat acest lucru, codul funcționează corect, dar tot se blochează undeva. Am plecat la depanare – mulțumesc! –  > Por muttley91.
Ira Baxter

Mai multe probleme:

  • dacă aveți de gând să treceți parametrii pe stivă, nu aveți intrarea corectă (standard) a funcției, deci EBP indică locul greșit
  • nu salvați corect valoarea argumentului în edx

Iată ce cred eu că ai vrut, presupunând că treci parametrii pe stivă (cel mai bine este să adaugi un comentariu la fiecare instrucțiunepentru a clarifica ce crezi că face):

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

Dar nu trebuie să treceți parametrii pe stivă. Este mai eficient să folosiți registrele:

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

Comentarii

  • Ați uitat să faceți pop ebp la sfârșit. Acest cod se va întoarce întotdeauna la o locație de pe stivă. –  > Por ughoavgfhw.
  • @ughoavgfhw: Da, mulțumesc, fixat. Asta demonstrează că și experții autoproclamați o dau în bară –  > Por Ira Baxter.
  • Am făcut ajustările, dar codul meu tot nu funcționează. Cu toate acestea, acest răspuns pare a fi încă răspunsul pe care îl caut. Cred că problema mea este în altă parte, acum. În ceea ce privește utilizarea registrelor, am încercat inițial acest lucru, dar nu părea să funcționeze. Poate că voi mai încerca o dată. Mulțumesc! –  > Por muttley91.
  • @rar: Ne-am dat deja seama că expertul nu poate codifica corect :-} Folosiți un depanator și urmați instrucțiunile pas cu pas. Nu vă va lua mult timp să vă dați seama de problemă și experiența este neprețuită. –  > Por Ira Baxter.
  • @rar: ai ales patch-ul pe care l-am făcut pe baza observației lui ughoavgfw (wow)? –  > Por Ira Baxter.
jcomeau_ictx

În primul rând, folosești un offset de stivă de 8 de la EBP, de ce? Nu te referi la ESP? Iar un apel normal folosește doar o celulă de 32 de biți, deci arg-ul tău ar trebui să fie la offset 4. Sunt destul de sigur că există și alte probleme, dar poți începe cu asta.


Probabil că ar trebui să scrii un pseudocod pentru ca tu, și noi, să vedem ce încerci să realizezi.


Dacă vrei să trișezi, dacă cauți pe Google „nasm recursive fibonacci” te duce la un program funcțional. Dar vei fi un programator mai bun dacă o rezolvi singur.