Geek Answers Handbook

Fibonacci Recursive Assembly

Today I wrote a recursive fibonacci in an assembly, and it does not work. I compiled it into an object file with NASM and made it an elf with gcc.
When I enter 1 or 2, the function works fine, but when I enter 3, 4, 5, 6 or more, the function does not work. I think there is a problem when a function calls itself.

This 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

This is the function:

 _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

After starting Ubuntu 16.04, he sent an error:

Segmentation error (kernel flushing)

What could be the problem?

0
source share
3 answers

You must save (click) the registers that you are about to change in the recursive call. And then restore their original values ​​(pop). This should solve the problem.

Something like that:

  • Press all the registers that you are going to use in your function (except eax, where you will get the return value)
  • Click ebx as this is your parameter
  • Function call
  • Add esp, 4
  • Put all the registers you clicked on in the first step, now in the reverse order
0
source 
 mov eax,[ebp-4]

You use memory in [ebp-4] without investing anything useful in it! You must reserve this space in your prolog function:

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

Returning from the first recursive call, you put the result from EAX into this memory slot.
Returning from the second recursive call, you add the contents of this memory dictionary to EAX .
Thus, the EDX register will no longer be closed.

Why are you using the EBX register at all? If you use it, you must save it, as explained in Al Kepp's answer .
If you start by placing the argument in EAX , you know that for both values ​​below 2 (so 0 and 1), the result will be equal to the argument. Plain.

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

If you do not balance the stack immediately after the first recursive call, you can simply reduce the colon that already exists and make a second recursive call.

  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]

The whole process:

 _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
0
source

In addition to the other answers provided, here is an alternative solution:

 _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

General information - fib (47) is the largest <2 ^ 32. The number of recursive calls = 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 ...
0
source

More articles:


All Articles