;;; author: Younes EL Amrani
;;; First Modification: March 25, 2007
;;;  Last Modification: March 25, 2007
;;; file: fibo.asm, Recursive Fibonacci

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

extern _printf, _scanf
global _main       

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

%macro print 2
push %2
push %1
call _printf
add esp, 8
%endmacro

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

%macro read 2
push %2
push %1
call _scanf
add esp, 8
%endmacro

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
;;; The actual program
segment .data 

;;;declare here initialised data
msg1:           db      "Enter a value:   " , 0
newline:        db      13, 10, 0 
integerFormat:  db      "%d" , 0
textFormat:     db      "%s" , 0

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

segment .bss

;;;declare here uninitialised data
N:   resd 1

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; code segment
segment .text

fibo:
.l1:	push ebp
.l2:	mov ebp, esp
.l3     push ebx                 ; plan to store fibo( N - 2 ) in ebx
.l4	push ecx                 ; plan to store fibo( N - 1 ) in ecx
.l5:	 cmp dword [ ebp + 8 ] , 2
.l6:	 jg .rec
.l7:	 mov eax , 1
.l8:	 jmp .end
.rec:
.l9:	 mov eax , [ebp + 8]	 ; read parameter N
.l10:	 add eax , -2            ; compute N - 2
.l11:	 push eax                ; pass argument ( N - 2 ) on stack
.l12	   call fibo             ; compute fibo( N - 2 )
.l13:	   mov ebx , eax         ; load fibo( N - 2 ) in ebx
.l14:	 add esp , 4             ; remove ( N - 2 ) from stack
.l15:	 mov eax , [ebp + 8]	 ; re-read parameter N
.l16:	 dec eax                 ; compute N - 1
.l17:	 push eax                ; pass argument ( N - 1 ) on stack
.l18:	   call fibo             ; compute fibo( N - 1 )
.l19:	   mov ecx , eax         ; store fibo( N - 1 ) in ecx
.l20:	 add esp , 4             ; remove ( N - 1 ) from stack
.l21:	 lea eax , [ ebx + ecx ] ; compute fibo( N - 2 ) + fibo( N - 1 )
.end: 		                 ; fibo epilogue
.l22:	pop edx                  ; restore edx
.l23:   pop ebx                  ; restore ebx
.l24	mov esp, ebp
.l25	pop ebp
.l26	ret

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

_main:
	enter 0, 0
 	print textFormat, msg1               ; ask user to enter value
	read integerFormat,  N               ; read integer value from user
	print integerFormat , dword [N]      ; print value of user
	print textFormat, newline            ; print new line
	push dword [ N ]                     ; pass parameter on stack
        call fibo                            ; call fibonacci
        print integerFormat , eax            ; print result
        add esp , 4                          ; remove parameter from stack
.end:   			             ; labels indicates locally main end
	mov eax, 0                           ; prepare to return control
	leave                                ; free frame, restore stack base
	ret                                  ; restore instruction pointer

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;