Fibonacci Function in MIPS/MARS.

Implement a recursive function that computes Fibonacci numbers. You experiment with 1) using stack in functions, 2) implementing recursive functions, 3) using multiple source files in MARS.

Steps 1. Download the template files (NOTED BELOW). There are two files. Put them (and ONLY these two files) in a directory. You will be working on the file whose name starts with .... The other file implements printf function. When you assemble the files, make sure you have checked Settings / Assemble all files in directory option so that both files are assembled and loaded to run. Otherwise, MARS complains that symbol printf is not found. You can run the template files. The program asks you for an integer and calls an empty function to compute F(n). The empty function returns 0 (error). In the main function, you can find how Fibonacci2 is called with two arguments

2. Implement a function that compute Fibonacci number recursively. int Fibonacci2(unsigned int n, unsigned int *p) The function takes one integer (n) as input and computes F(n) and F(n 1). The results are stored in the buffer specified by p. p[0] = F(n) and p[1] = F(n-1). Following the calling convention, the argument n is in $a0 and b is in $a1. To compute F(n), you call Fibonacci2 to compute F(n 1) and F(n 2). After you have F(n 1) and F(n 2), you can easily compute F(n) = F(n 1) + F(n 2). Remember store the results in the correct locations. The function returns 1 on success and 0 on error. The pseudo code is listed on the next page. Tips: 1. There are multiple returns in the function. It is better to have only one place to restore the stack. Whenever you want to return from the function, set the return value and then branch (or jump) to the sequence of code that restores stack. 2. If you do not want to enter the integer every time when debugging your code, you can comment out the syscall instruction that reads an integer and add an instruction to load a value into $v0. Remember to switch back when you submit your code. 3. At the beginning, you do not have to check overflow. After you can compute smaller numbers correctly, add the code to check if an overflow takes place during the addition. 4. Register use. What registers have you changed in the function? Do you have to save any registers to the stack? For practicing, you can save all the registers you changed in the function, except for $v0. 5. You do not have to use $fp.

3. Test your code, add good comments

Pseudo-code for computing Fibonacci numbers int Fibonacci2(int n, unsigned int * p) { # $a0 is n, $a1 is p (an address) Allocate space on stack and save registers if (n <= 0) { rv = 0; goto exit } # return 0 on error if (n == 1) { # set the first Fibonacci number p[0] = 1; p[1] = 0 rv = 1; goto exit # return 1 } r = Fibonacci2(n 1, p) # compute F(n-1) and F(n-2) if (r == 0) { rv = 0; goto exit } # return 0 r = p[0] + p[1] # F(n) = F(n-1)+F(n-2) if (there is an overflow) {rv = 0; goto exit} # return 0 p[1] = p[0] # p[1] is F(n-1) p[0] = r # p[0] is F(n) rv = 1 # set the return value exit: Restore saved registers and stack return rv }

TEMPLATE THAT NEEDS TO BE USED IS BELOW, PLEASE DO NOT JUST COPY ANOTHER SIMILAR QUESTION, I NEED A UNIQUE CODE ANSWER TO UNDERSTAND THE MATERIAL AS OTHER ANSWER DON'T WORK

# Recursive Fibonacci function

.data #data segment name: .asciiz "Your Name" msg0: .asciiz "F(%d) cannot be computed. " msg1: .asciiz "F(%d) = (%d) "

.align 2 buffer: .space 8 # reserve space for two words n_in: .space 4 # get input from the user

.text # Code segment .globl main # declare main to be global

main: la $a0, name jal printf # call printf function

li $s0, 49 li $v0, 5 #read an integer syscall move $s0, $v0 #save the user input

la $s1, buffer # buffer

#call jal move $a0, $s0 # set the 1st argument move $a1, $s1 # set the 2nd argument jal Fibonacci2 bne $v0, $zero, l_ok

# 0 is returned la $a0,msg0 # $a0 := address of message 1 move $a1, $s0 # the number jal printf j Exit

l_ok: la $a0, msg1 move $a1, $s0 lw $a2, ($s1) # p[0] is F(n) jal printf

Exit: li $v0,10 # System call, type 10, standard exit syscall # ...and call the OS

# Fibonacci2(n, p) # Used registers # Fibonacci2: li $v0, 0 # return error for now. jr $ra

FILE THAT COMES WITH THE TEMPLATE EXAMPLE TO HELP

# printf function

## Daniel J. Ellard -- 03/13/94

## printf.asm--

## an implementation of a simple printf work-alike.

## printf--

## A simple printf-like function. Understands just the basic forms

## of the %s, %d, %c, and %% formats, and can only have 3 embedded

## formats (so that all of the parameters are passed in registers).

## If there are more than 3 embedded formats, all but the first 3 are

## completely ignored (not even printed).

## Register Usage:

## $a0,$s0 - pointer to format string

## $a1,$s1 - format argument 1 (optional)

## $a2,$s2 - format argument 2 (optional)

## $a3,$s3 - format argument 3 (optional)

## $s4 - count of formats processed.

## $s5 - char at $s4.

## $s6 - pointer to printf buffer

##

.text

.globl printf

printf:

subu $sp, $sp, 36 # set up the stack frame,

sw $ra, 32($sp) # saving the local environment.

sw $fp, 28($sp)

sw $s0, 24($sp)

sw $s1, 20($sp)

sw $s2, 16($sp)

sw $s3, 12($sp)

sw $s4, 8($sp)

sw $s5, 4($sp)

sw $s6, 0($sp)

addu $fp, $sp, 36

# grab the arguments:

move $s0, $a0 # fmt string

move $s1, $a1 # arg1 (optional)

move $s2, $a2 # arg2 (optional)

move $s3, $a3 # arg3 (optional)

li $s4, 0 # set # of formats = 0

# sent up the temporay buffer 36 bytes

# it was defined as a global buffer. -- Z. Shi

subu $sp, $sp, 36

move $s6, $sp

#la $s6, printf_buf # set s6 = base of printf buffer.

printf_loop: # process each character in the fmt:

lb $s5, 0($s0) # get the next character, and then

addu $s0, $s0, 1 # bump up $s0 to the next character.

beq $s5, '%', printf_fmt # if the fmt character, then do fmt.

beq $0, $s5, printf_end # if zero, then go to end.

printf_putc:

sb $s5, 0($s6) # otherwise, just put this char

sb $0, 1($s6) # into the printf buffer,

move $a0, $s6 # and then print it with the

li $v0, 4 # print_str syscall

syscall

b printf_loop # loop on.

printf_fmt:

lb $s5, 0($s0) # see what the fmt character is,

addu $s0, $s0, 1 # and bump up the pointer.

#beq $s4, 3, printf_loop # if we've already processed 3 args,

beq $s4, 3, printf_invalidtag #

# then *ignore* this fmt.

beq $s5, 'd', printf_int # if 'd', print as a decimal integer.

beq $s5, 'u', printf_intu # if 'u', print as an unsigned decimal integer.

beq $s5, 's', printf_str # if 's', print as a string.

beq $s5, 'c', printf_char # if 'c', print as a ASCII char.

beq $s5, '%', printf_perc # if '%', print a '%'

#b printf_loop # otherwise, just continue.

# Added by Z. Shi

printf_invalidtag: # print out invalid tags

sb $0, 2($s6) # the a null.

sb $s5, 1($s6) # the tag specifier

li $s5, '%' # %,

sb $s5, 0($s6)

move $a0, $s6 # and then do a print_str syscall

li $v0, 4 # on the buffer.

syscall

b printf_loop # branch to printf_loop

printf_shift_args: # shift over the fmt args,

move $s1, $s2 # $s1 = $s2

move $s2, $s3 # $s2 = $s3

add $s4, $s4, 1 # increment # of args processed.

b printf_loop # and continue the main loop.

printf_int: # deal with a %d:

move $a0, $s1 # do a print_int syscall of $s1.

li $v0, 1

syscall

b printf_shift_args # branch to printf_shift_args

printf_intu: # deal with a %u: Added by Z. Shi

move $a0, $s1 # do a print_int syscall of $s1.

li $v0, 36 # 36 for unsigned integer

syscall

b printf_shift_args # branch to printf_shift_args

printf_str: # deal with a %s:

move $a0, $s1 # do a print_string syscall of $s1.

li $v0, 4

syscall

b printf_shift_args # branch to printf_shift_args

printf_char: # deal with a %c:

sb $s1, 0($s6) # fill the buffer in with byte $s1,

sb $0, 1($s6) # and then a null.

move $a0, $s6 # and then do a print_str syscall

li $v0, 4 # on the buffer.

syscall

b printf_shift_args # branch to printf_shift_args

printf_perc: # deal with a %%:

li $s5, '%' # (this is redundant)

sb $s5, 0($s6) # fill the buffer in with byte %,

sb $0, 1($s6) # and then a null.

move $a0, $s6 # and then do a print_str syscall

li $v0, 4 # on the buffer.

syscall

b printf_loop # branch to printf_loop

printf_end:

subu $sp, $fp, 36

lw $ra, 32($sp) # restore the prior environment:

lw $fp, 28($sp)

lw $s0, 24($sp)

lw $s1, 20($sp)

lw $s2, 16($sp)

lw $s3, 12($sp)

lw $s4, 8($sp)

lw $s5, 4($sp)

lw $s6, 0($sp)

addu $sp, $sp, 36 # release the stack frame.

jr $ra # return.

## end of printf.asm