Language: Mars (Needs to be done with MARS simulator)

Download link: http://courses.missouristate.edu/KenVollmar/MARS/download.htm

fact4b.asm (File) # ============================================================= # main PROCEDURE TEMPLATE # 4b # # Use with "proc_template4b.asm" as the template for other procedures # # Based on Slide 37 of Lecture 9 (Procedures and Stacks) # (main is simpler than other procedures because it does not have to # clean up anything before exiting) # # Assumptions: # # - main calls other procedures with no more than 4 arguments ($a0-$a3) # - any local variables needed are put into registers (not memory) # - no values are put in temporaries that must be preserved across a call from main # to another procedure # # ============================================================= .data 0x0 # # declare global variables here .text 0x3000 .globl main main: ori $sp, $0, 0x3000 # Initialize stack pointer to the top word below .text # The first value on stack will actually go at 0x2ffc # because $sp is decremented first. addi $fp, $sp, -4 # Set $fp to the start of main's stack frame # ============================================================= # No need to create room for temporaries to be protected. # ============================================================= # ============================================================= # BODY OF main # ... # ... # ... # ... CODE FOR main HERE # ===================================================== # main CALLS proc1 # # Suppose main needs to call proc1, but there are no # temporaries that need to be protected for this call. # # There is only one argument to send to proc1: say # factorial(4) # Here's how to do it. ori $a0, $0, 4 # Put 4 in $a0 jal factorial # call proc1 # valued returned by proc1 will be in $v0-$v1 # ===================================================== # ... MORE CODE FOR main HERE add $a0, $0, $v0 # print the factorial result li $v0, 1 syscall # END OF BODY OF main # ============================================================= exit_from_main: ori $v0, $0, 10 # System call code 10 for exit syscall # Exit the program end_of_main: # ============================================================= # PROCEDURE WRITING TEMPLATE # 4b # # Based on Slide 37 of Lecture 9 (Procedures and Stacks) # (slightly more expanded version than the one in the lecture) # # Assumptions: # # - this procedure calls other procedures with no more than 4 arguments ($a0-$a3) # - any local variables needed are put into registers (not memory) # - no values are put in temporaries that must be preserved across a call from this # procedure to another procedure # # Write the code for the body of this procedure first, # without worrying much about saving/restoring values # on/from the stack. # # Which registers out of $s0-$s7 does this procedure modify? # It needs to save those at the beginning and restore them # at the end. # # ============================================================= .text .globl factorial # Simply means proc1 can be found by code residing in other files factorial: addi $sp, $sp, -8 # Make room on stack for saving $ra and $fp sw $ra, 4($sp) # Save $ra sw $fp, 0($sp) # Save $fp addi $fp, $sp, 4 # Set $fp to the start of proc1's stack frame # From now on: # 0($fp) --> $ra's saved value # -4($fp) --> caller's $fp's saved value # ============================================================= # Save any $sx registers that proc1 will modify # Save any of the $sx registers that proc1 modifies addi $sp, $sp, -4 # e.g., $s0, $s1, $s2, $s3 sw $s0, 0($sp) # Save $s0 # From now on: # -8($fp) --> $s0's saved value # ============================================================= # ============================================================= # No need to create room for temporaries to be protected # ============================================================= # ============================================================= # BODY OF proc1 # ... # ... li $v0, 1 # base case: factorial(0) = 1 beq $a0, $0, return_from_proc1 # We are done if $a0 = 0 add $s0, $0, $a0 # We need to save the argument $a0. # Let's put it in $s0 because that # won't be clobbered by the recursive # call. # ===================================================== # proc1 CALLS proc2 # # Suppose proc1 needs to call proc2, but there are no # temporaries that need to be protected for this call. # # Proc 2 here is factorial itself, i.e., a recursive call. # It should be called with $a0 - 1. Here's how to do it. addi $a0, $a0, -1 # n = n - 1 jal factorial # call proc2 # valued returned by proc2 will be in $v0-$v1 # By now, $v0 has factorial(n-1) # ===================================================== mult $v0, $s0 # Multiply factorial(n-1) by n mflo $v0 # $v0 now has the result of n * factorial(n-1) # ... # ... # put return values, if any, in $v0-$v1 # END OF BODY OF proc1 # ============================================================= # ============================================================= # Restore $sx registers lw $s0, -8($fp) # Restore $s0 # ============================================================= # ============================================================= # Restore $fp, $ra, and shrink stack back to how we found it, # and return to caller. return_from_proc1: addi $sp, $fp, 4 # Restore $sp lw $ra, 0($fp) # Restore $ra lw $fp, -4($fp) # Restore $fp jr $ra # Return from procedure # ============================================================= end_of_proc1:

Coding Assignment (100 points in total) Implement the Fibonacci function in MIPS given the following C code int fib (int n) return n se return fib (n 1)fib (n 2 Note that this code contains two recursive calls. Be careful and save the result of the first fib before calling it again. There is only one input, so pass n in register Sa0 in the main procedure The input n should be asked from the keyboard and the output should be print out by another syscall. Check Lab 5 to implement the I/O calls. Templates: Assembly coding templates have been provided for the main procedure (main_template4b.asm) and for other procedures (proc_template4b.asm). To simplify the assembly coding, these templates assume the following: (i) no procedure call needs more than 4 arguments) any local variables are placed in registers and not created on the stack; (ii) no "temporary" registers need to be protected from a subsequent call to another procedure. You may develop your code for each procedure in a separate file using the templates provided, but for this lab, all your final assembly code must be within one file; simply copy-and-paste your procedures below main. You can also choose not to use the template, and please add comment to your code to earn partial credits. EactorialExample: As an example of how to use these templates to write a recursive procedure, assembly code is provided for calculating factorial in a recursive fashion, using the "4b" templates. Please carefully study the code for the main procedure as well as the recursive factorial procedure. The two procedures have been concatenated together into a single assembly file (fact4b.asm); open this file in Mars and run it step-by-step to follow the execution of the recursive procedure. Use these files as guidance to develop your code for this exercise Coding Assignment (100 points in total) Implement the Fibonacci function in MIPS given the following C code int fib (int n) return n se return fib (n 1)fib (n 2 Note that this code contains two recursive calls. Be careful and save the result of the first fib before calling it again. There is only one input, so pass n in register Sa0 in the main procedure The input n should be asked from the keyboard and the output should be print out by another syscall. Check Lab 5 to implement the I/O calls. Templates: Assembly coding templates have been provided for the main procedure (main_template4b.asm) and for other procedures (proc_template4b.asm). To simplify the assembly coding, these templates assume the following: (i) no procedure call needs more than 4 arguments) any local variables are placed in registers and not created on the stack; (ii) no "temporary" registers need to be protected from a subsequent call to another procedure. You may develop your code for each procedure in a separate file using the templates provided, but for this lab, all your final assembly code must be within one file; simply copy-and-paste your procedures below main. You can also choose not to use the template, and please add comment to your code to earn partial credits. EactorialExample: As an example of how to use these templates to write a recursive procedure, assembly code is provided for calculating factorial in a recursive fashion, using the "4b" templates. Please carefully study the code for the main procedure as well as the recursive factorial procedure. The two procedures have been concatenated together into a single assembly file (fact4b.asm); open this file in Mars and run it step-by-step to follow the execution of the recursive procedure. Use these files as guidance to develop your code for this exercise