Computer Science.

I need this assignment in complete workable version with screenshot of your code and output.

(please give me complete working code)

THIS HAS TO BE DONE IN MARS

Fibonacci Function

Objectives

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

Download the template files. 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 lab3_.... 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.

Implement a function that compute Fibonacci number recursively. The functions interface is

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.

You do not have to use $fp.

Additional comments: You may be tempted to compute F(n) in the way shown in exercise 2.31 (i.e., compute F(n-1) first then F(n-2)). You will find that it is much slower (you may not be patient enough to see the results). Think about why.

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

}

--------------------------------------------------------------------------------------

############ this is the file you will be working on # Recursive Fibonacci function .data #data segment name: .asciiz "CSE3666: Lab 3: Your Name(Your NetID) Enter an integer:" 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 

------------------------------------------------------------------------------------------

# 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, 'x', printf_intx # if 'x', print as an unsigned 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_intx: # deal with a %u: Added by Z. Shi move $a0, $s1 # do a print_int syscall of $s1. li $v0, 34 # 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