I'm creating a compiler (source code is a C-like language, and I'm translating it to x86 NASM).
I've tested my compiler with programs that have recursive functions, and they all have the expected result except this Fibonacci program.
I know my code is not optimized at all, I will fix that later.
Can someone tell me what is wrong with the ASM code? If I print the Fibonacci numbers from 0 to 13 this should be the output:
1123581321345589144233377
but I'm getting: 1123354759611713
or this, if I format it: 1,1,2,3,3,5,4,7,5,9,6,11,7,13
Can someone tell what's wrong? The source code is:
int f
//global var f
int fibonacci( int n ){
if ((n=0) or (n=1)){
return 1
}
else{
return fibonacci(n-1) + fibonacci(n-2)
}
}
main(){
f = fibonacci(6)
print(f)
}
ASM code is:
;fibonacci (not optimized)
extern printf
global main
section .data
format db '%d', 0
f dd 0
temp0 dd 0
temp1 dd 0
temp2 dd 0
temp3 dd 0
temp4 dd 0
temp5 dd 0
temp6 dd 0
temp7 dd 0
temp8 dd 0
temp9 dd 0
temp10 dd 0
temp11 dd 0
temp12 dd 0
section .text
fibonacci:
push ebp
mov ebp, esp
;eq expr
mov dword[temp0], 0
mov eax, dword[ebp + 8]
cmp eax, dword[temp0]
mov eax, 0
sete al
mov dword[temp0], eax
;eq expr
mov dword[temp1], 1
mov eax, dword[ebp + 8]
cmp eax, dword[temp1]
mov eax, 0
sete al
mov dword[temp1], eax
;or expr
cmp dword[temp0], 1
je label1
cmp dword[temp1], 1
je label1
mov dword[temp2], 0
jmp label2
label1:
mov dword[temp2], 1
label2:
;ifStmt
cmp dword[temp2], 0
je label3
;return statement
mov dword[temp3], 1
mov eax, dword[temp3]
;jmp to epilogue
jmp label0
jmp label4
;else label
label3:
;return statement
mov dword[temp5], 1
mov esi, dword[ebp + 8]
sub esi, dword[temp5]
mov dword[temp6], esi
push dword[temp6]
;subprogram call
call fibonacci
add esp, 4
mov dword[temp4], eax
mov dword[temp8], 2
mov esi, dword[ebp + 8]
sub esi, dword[temp8]
mov dword[temp9], esi
push dword[temp9]
;subprogram call
call fibonacci
add esp, 4
mov dword[temp7], eax
mov esi, dword[temp4]
add esi, dword[temp7]
mov dword[temp10], esi
mov eax, dword[temp10]
;jmp to epilogue
jmp label0
label4:
label0:
pop esi
mov esp, ebp
pop ebp
ret
main:
mov dword[temp12], 6
push dword[temp12]
;subprogram call
call fibonacci
add esp, 4
mov dword[temp11], eax
mov eax, dword[temp11]
mov dword[f], eax
push dword[f]
push format
call printf
add esp, 8
ret
Can somebody also explain why is my compiler working for this gcd function and not for the Fibonacci?
int a, b, c
// greatest common divisor
int gcd(int x, int y){
if(b = 0){
return x
}else{
return gcd(y, x mod y)
}
}
main(){
a = 51492
b = 20636
c = gcd(a, b)
print c
}
extern printf
global main
section .data
format db '%d', 0
a dd 0
b dd 0
c dd 0
temp0 dd 0
temp1 dd 0
temp2 dd 0
temp3 dd 0
temp4 dd 0
temp5 dd 0
section .text
gcd:
push ebp
mov ebp, esp
;eq expr
mov dword[temp0], 0
mov eax, dword[ebp + 12]
cmp eax, dword[temp0]
mov eax, 0
sete al
mov dword[temp0], eax
;ifStmt
cmp dword[temp0], 0
je label1
;return statement
mov eax, dword[ebp + 8]
;jmp to epilogue
jmp label0
;elseStmt
label1:
;return
mov eax, dword[ebp + 8]
mov edx, 0
div dword[ebp + 12]
mov dword[temp2], edx
push dword[temp2]
push dword[ebp + 12]
;call to subprogram
call gcd
add esp, 8
mov dword[temp1], eax
mov eax, dword[temp1]
label0:
mov esp, ebp
pop ebp
ret
main:
mov dword[temp3], 51492
mov eax, dword[temp3]
mov dword[a], eax
mov dword[temp4], 20636
mov eax, dword[temp4]
mov dword[b], eax
push dword[b]
push dword[a]
;call to subprogram
call gcd
add esp, 8
mov dword[temp5], eax
mov eax, dword[temp5]
mov dword[c], eax
push dword[c]
push format
call printf
add esp, 8
ret
