Rekursive Fibonacci Assembly

Question

Heute schrieb ich eine rekursive Fibonacci in Assembly und es funktioniert nicht. Ich habe es mit NASM zur Objektdatei kompiliert und dann mit gcc elf gemacht.
Wenn ich 1 oder 2 eingeben, funktioniert die Funktion perfekt, aber wenn ich 3, 4, 5, 6 oder mehr eingeben, funktioniert die Funktion nicht. Ich denke, es gibt ein Problem, wo die Funktion sich selbst nennt.

Dies ist der Code:

SECTION .data ;init data 




str: db "This equal: %d",10,0 

SECTION .text ;asm code 


extern printf 
global main 

main: 
push ebp 
mov ebp,esp 
;-------------------- 


push 03 ; the index 
call _fibonacci 
add esp,4 

push DWORD eax 
push str 
call printf 


;--------------------- 

mov esp,ebp 
pop ebp 
ret 

Dies ist die Funktion:

Segmentation fault (core dumped)

Was das Problem sein könnte:

_fibonacci: 

push ebp 
mov ebp,esp 


mov ebx, [ebp+8] ;; param n 
cmp ebx,0 
jne CHECK2 

mov eax,0 
jmp _endFIbofunc   

CHECK2: 
    cmp ebx,0x1 
    jne ELSE3 
    mov eax,1 
jmp _endFIbofunc 

ELSE3: 

mov ebx,[ebp+8] 
dec ebx ;; n-1 


;; FIRST call 
push ebx 
call _fibonacci 
add esp,4 
mov edx,eax 

;; SEC CALL 
dec ebx 
push ebx 
call _fibonacci 
add esp,4 
add eax,edx 


mov eax,[ebp-4] 

_endFIbofunc: 

mov esp,ebp 
pop ebp 
ret 

Nachdem ich es auf Ubuntu 16.04 es Fehler senden lief ?

Answer 1

Sie müssen die Register, die Sie im rekursiven Aufruf ändern möchten, speichern (push). Und dann stellen Sie ihre ursprünglichen Werte wieder her (Pop). Das sollte das Problem beheben.

Etwas wie folgt aus:

• Drücken alle Register Sie in Ihrer Funktion (außer eax, wo Sie Rückgabewert erhalten wird) verwenden werden
• Push-ebx als dass Ihre Parameter
• Call ist die esp Funktion
• hinzufügen, 4
• Pop alle Register Sie im ersten Schritt geschoben, nun in umgekehrter Reihenfolge

Answer 2

mov eax,[ebp-4] 

Sie verwenden den Speicher unter [ebp-4], ohne etwas Nützliches hineingesteckt zu haben! Sie müssen diesen Raum in Ihrer Funktion prolog reservieren:

_fibonacci: 
    push ebp 
    mov ebp, esp 
    sub esp, 4 

aus dem ersten rekursiven Aufruf Rückkehr Sie von EAX in diesem Speicher dword das Ergebnis setzen.
Zurückgeben von dem zweiten rekursiven Aufruf fügen Sie zu EAX den Inhalt dieses Speicher-dword hinzu.
Dadurch wird das EDX Register nicht mehr geplottert.

---

Warum verwenden Sie das EBX Register überhaupt? Wenn Sie es verwenden, müssen Sie es beibehalten, wie in der Antwort von Al Kepp erklärt wurde.
Wenn Sie beginnen, indem Sie das Argument in EAX setzen, wissen Sie, dass für beide Werte unter 2 (also 0 und 1) das Ergebnis genau gleich dem Argument ist. Einfach.

mov eax, [ebp+8] ;; param n 
    cmp eax, 2 
    jb _endFIbofunc   

Wenn Sie nicht über den Stapel direkt nach dem ersten rekursiven Aufruf ausgleichen, können Sie einfach die dword verringern, die bereits vorhanden ist und Ihren zweiten rekursive Anruf.

dec eax    ; n-1 
    push eax    ;(*) 
    call _fibonacci 
    mov [ebp-4], eax 
    dec dword ptr [esp] ; n-2 
    call _fibonacci 
    add esp,4   ;(*) 
    add eax, [ebp-4] 

Die ganze Prozedur:

_fibonacci: 
    push ebp 
    mov ebp, esp 
    sub esp, 4   ;(*) 
    mov eax, [ebp+8] ;; param n 
    cmp eax, 2 
    jb _endFIbofunc   
    dec eax    ; n-1 
    push eax    ;(*) 
    call _fibonacci 
    mov [ebp-4], eax 
    dec dword ptr [esp] ;(*) n-2 
    call _fibonacci 
    add esp,4   ;(*) 
    add eax, [ebp-4] 
_endFIbofunc: 
    mov esp, ebp 
    pop ebp 
    ret 

Answer 3

Zusätzlich zu den anderen Antworten zur Verfügung gestellt, hier ist eine alternative Lösung:

_fibonacci: 
     mov  eax,[esp+4]    ;eax = n 
     cmp  eax,2     ;br if n < 2 
     jb  _endFIbofunc 
     dec  eax      ;push n-1 
     push eax 
     call _fibonacci    ;returns eax = fib(n-1) 
     xchg eax,[esp]    ;eax = n-1, [esp] = fib(n-1) 
     dec  eax      ;push n-2 
     push eax 
     call _fibonacci    ;returns eax = fib(n-2) 
     add  eax,[esp+4]    ;eax = fib(n-1)+fib(n-2) 
     add  esp,8 
_endFIbofunc: 
     ret 

Trivia - fib (47) ist die größte < 2^32. Die Anzahl der rekursiven Aufrufe = 2 * fib (n + 1) -1.

n  fib(n)  # calls 

0   0   1 
1   1   1 
2   1   3 
3   2   5 
4   3   9 
5   5   15 
6   8   25 
7   13   41 
8   21   67 
9   34   109 
10   55   177 
11   89   287 
12  144   465 
13  233   753 
14  377   1219 
15  610   1973 
16  987   3193 
17  1597   5167 
18  2584   8361 
19  4181  13529 
20  6765  21891 
21  10946  35421 
22  17711  57313 
23  28657  92735 
24  46368  150049 
25  75025  242785 
26  121393  392835 
27  196418  635621 
28  317811  1028457 
29  514229  1664079 
30  832040  2692537 
31 1346269  4356617 
32 2178309  7049155 
33 3524578  11405773 
34 5702887  18454929 
35 9227465  29860703 
36 14930352  48315633 
37 24157817  78176337 
38 39088169 126491971 
39 63245986 204668309 
40 102334155 331160281 
41 165580141 535828591 
42 267914296 866988873 
43 433494437 1402817465 
44 701408733 2269806339 
45 1134903170 3672623805 
46 1836311903 5942430145 
47 2971215073 9615053951 
48 4807526976 ...