.data
prompt:	.asciiz "Please enter a positive integer: "
printa:	.asciiz "fib("
printb:	.asciiz ") = "
nl:	.asciiz "\n"

	.align 2

	.text
main:	# We are going to use $ra when we call fib, so we need
	# to save it.  However, main() is a special case function
	# in that it doesn't technically have a caller, so it
	# doesn't need to save any of the other preserved
	# registers it uses.
	
	addi $sp, $sp, -4
	sw $ra, 0($sp)
	
	# prompt for value
	la $a0, prompt
	li $v0, 4  # print_string
	syscall

	# read value, load into $a0
	li $v0, 5
	syscall  # read_int
	move $a0, $v0   # $a0 = n
	
	# Also, save a copy in $s0, since $a0 isn't a preserved
	# register, and we will be calling other
	# procedures.
	move $s0, $a0  # $s0 == n
	
	jal fib

	# save returned value of fib(n)
	move $t0, $v0  # $t0 = fib(n)

	# print answer: "fib ("
	la $a0, printa
	li $v0, 4
	syscall

	# print value of n
	move $a0, $s0
	li $v0, 1
	syscall

	# print ") ="
	la $a0, printb
	li $v0, 4
	syscall

	# print fib(n)
	li $v0, 1 
	move $a0, $t0
	syscall
	
	la $a0, nl
	li $v0, 4
	syscall

	# We're done.  Restore $ra and return from main().
	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra

	# --------------------
	# here is fib
	# --------------------

fib:	# Adjust stack to save $ra, $s0 .. $s2.
	# We spill $ra because this is not a leaf procedure.
	# We spill $s0 .. $s2 because we use them and they
	# are preserved registers.
	addi $sp, $sp, -16
	sw $ra, 12($sp)
	sw $s0, 8($sp)
	sw $s1, 4($sp)
	sw $s2, 0($sp)

	# body of fib function

	# if (n == 1): branch on n != 1
	li $t0, 1
	bne $a0, $t0, if1_done
	
	li $v0, 1  # return 1
	j fib_done # restore from stack and return

if1_done:
	# if (n == 2): branch on n != 2
	li $t0, 2
	bne $a0, $t0, if2_done

	li $v0, 1   # return 1
	j fib_done  # restore from stack and return

if2_done:
	# recursive steps - first calculate fib (n - 1)
	# n is currently in $a0
	# save $a0 in $s0
	move $s0, $a0
	addi $a0, $a0, -1   	# parm for fib ( n - 1)
	jal fib			# call fib(n - 1)
	move $s1, $v0		# $s1 = fib(n - 1)

	# next, calculate fib (n - 2)
	addi $a0, $s0, -2	# parm for fib (n - 2)
	jal fib			# call fib (n - 2)
	move $s2, $v0		# $s2 = fib (n - 2)

	# return fib (n - 1) + fib (n - 2)
	add $v0, $s1, $s2

fib_done: # restore from stack and return
	lw $s2, 0($sp)
	lw $s1, 4($sp)
	lw $s0, 8($sp)
	lw $ra, 12 ($sp)
	addi $sp, $sp, 16

	jr $ra