#**********************************************************************
#  CS 232: Lab 4.
#  Written:  1/5/00, JP Mellor
#
#  This section contains procedure:
#     -- main
#  which sets up for fib
#
#**********************************************************************

	.globl main
	.globl Start
	.globl Okay
	.globl Again
	.globl ExitMain

	.data
prompt:		.asciiz "Input a non-negative integer => "
prompt2:	.asciiz "Do you wish to try another? (1/0) "
message:	.asciiz "fibonacci number "
message2:	.asciiz " is: "
newline:	.asciiz "\n"
error:		.asciiz "The integer must be non-negative\n"
	
#----------------------------------------------------------------------
#   Frame is 2 words long, as follows:
#     -- previous fp
#     -- previous ra
#
#   Register allocations:
#
#   no arguments, no returns
#   asks user for number n and gives n to fib
#----------------------------------------------------------------------

#----------------------------------------------------------------------
#

# $s0 - n
# $t0 - temp storage for fib(n)

	.text

main:
	sub	$sp, $sp, 8	# Create a 2-word frame.
	sw	$ra, 4($sp)	# Save $ra
	sw	$s0, 0($sp)	# Save $s0

#----------------------------------------------------------------------
# 	Read an integer
#----------------------------------------------------------------------

Start:	la	$a0, prompt	# load address of prompt
	li 	$v0, 4		# use system call to
	syscall			# print prompt
	li	$v0, 5		# use system call for reading
	syscall			# an integer n
	move	$s0, $v0	# Copy integer n into $s0

#----------------------------------------------------------------------
# 	Check if the integer is in bounds
#----------------------------------------------------------------------

	slt	$t0, $a0, $zero	# check if n is negative
	beq	$t0, $zero, Okay # if non-negative, calc fib(n)
	la	$a0, error	# load address of prompt
	li 	$v0, 4		# use system call to
	syscall			# print error mesage
	j	Again

# ---------------------------------------------------------------------
#   Execute the fib procedure.
# ---------------------------------------------------------------------

Okay:	move	$a0, $s0	# Pass n to
	jal	fib		#	fib
	move	$t0, $v0	# save result
	la	$a0, message	# load address of message
	li 	$v0, 4		# use system call to
	syscall			# print message
	move	$a0, $s0	# n
	li	$v0, 1		# use system call to
	syscall			# print n
	la	$a0, message2	# load address of message2
	li 	$v0, 4		# use system call to
	syscall			# print message2
	move	$a0, $t0	# fib(n)
	li	$v0, 1		# use system call to
	syscall			# print fib(n)
	la	$a0, newline	# load address of newline
	li	$v0, 4		# use system call to
	syscall			# print newline
	la	$a0, newline	# load address of newline
	li	$v0, 4		# use system call to
	syscall			# print newline
	
# ---------------------------------------------------------------------
#   Do it again?
# ---------------------------------------------------------------------

Again:	la	$a0, prompt2	# load address of prompt2
	li	$v0, 4		# use system call to
	syscall			# print prompt2
	li	$v0, 5		# use system call for reading
	syscall			# an integer
	move	$t0, $v0	# save response
	la	$a0, newline	# load address of newline
	li	$v0, 4		# use system call to
	syscall			# print newline
	bne	$t0, $zero, Start # do it again.

# ---------------------------------------------------------------------
#   Exit the main procedure.
# ---------------------------------------------------------------------

ExitMain:
	lw	$ra, 4($sp)	# Restore $ra
	lw	$s0, 0($sp)	# Restore $s0
	add	$sp, $sp, 8	# Undo the 2-word frame.
	jr	$ra		# Return

#**********************************************************************
#   CS 232: Comp. Arch. I
#   Written:  1/5/00, JP Mellor
#
#   This section 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