/* hand coded assembly for tail-recursive fibonacci:	

	fib(int n, int a, int b)
	{ if (n<2) return b; else return fib(n-1,b,a+b); }

To run the program:

   gcc fib.s
   ./a.out 
*/
	
	.file "fib.s"
	.text

.globl fib
	.type fib, @function
fib:
	push %ebp
	mov %esp,%ebp
fiter:		                /* goto label for optimized version */
	cmp $2, 8(%ebp)  	/*  if n<2  */
	jl fibbase		
	/* make recurisve call (non-optomized tail recursion):	 */
	mov 16(%ebp), %eax    /* b */
	mov 12(%ebp), %ebx    /* a */
	add %eax,%ebx         /* a+b */
	mov 8(%ebp), %ecx
	dec %ecx	       /* n-1 */
	push %ebx
	push %eax
	push %ecx
	call fib
	add $12, %esp	      /* deallocate args */
	jmp fibexit

	/* optimized version avoids recursive call 
		mov 8(%ebp),%eax
		dec %eax
		mov %eax, 8(%ebp)
		mov 16(%ebp), %eax  
		mov 12(%ebp), %ebx  
		mov %eax, 12(%ebp)
		add %ebx, %eax
		mov %eax, 16(%ebp)
		jmp fiter
	*/

fibbase:	
	mov 16(%ebp), %eax   /* store return value b in eax */
fibexit:
	mov %ebp,%esp
	pop %ebp 
	ret
        .size   fib, .-fib
		
.section        .rodata
STR1:   .string "the 8th fib number is %d\n"
STR2:	.string "eax now contains %d\n"	
        .text

	
.globl main
	.type main, @function

main:
	push %ebp
	mov %esp, %ebp
	push $1         /* make call fib(8,1,1)  */
	push $1
	push $8
	call fib
	add $12, %esp
	push %eax
	push $STR1
	call printf
	add $8, %esp
	push $0
	call exit
	.size main, .-main