#**********************************************************************
#   CS 232: Comp. Arch. I
#   Written:  1/5/00, JP Mellor
#
#   This file contains procedure:
#     -- fib
#   
#   It expects one argument n stored in $a0 and return fib(n)
#   
#**********************************************************************

    .globl fib

#**********************************************************************

    .text

# $s0 - n
# $s1 - fib(n)

fib:	sub	$sp, $sp, 16		# adjust stack for 4 items
	sw	$s0, 12($sp)		# save $s0
	sw	$s1, 8($sp)		# save $s1
	sw	$ra, 4($sp)		# save $ra
	move	$s0, $a0		# save n
	move	$v0, $a0		# fib(n) = n for n < 2
	slt	$t0, $s0, 2		# test if n == 0 or n == 1
	bne	$t0, $zero, Skip	# skip recursion
	sub	$a0, $s0, 1		# pass n-1
	jal	fib			#	to fib
	move	$s1, $v0		# save fib(n-1)
	sub	$a0, $s0, 2		# pass n-2
	jal	fib			#	to fib
	add	$v0, $s1, $v0		# put fib(n-1) + fib(n-2)
Skip:	lw	$ra, 4($sp)		# restore $ra
	lw	$s1, 8($sp)		# restore $s1
	lw	$s0, 12($sp)		# restore $s0
	add	$sp, $sp, 16		# adjust stack
	jr	$ra			# return