################################################################################ ## ## LSU EE 4720 Fall 2004 Homework 2 ## ## ## Due Friday, 1 October 2004 .data name: .asciiz "" # Put your name between the quotes. ## Instructions: # # (1) Copy this assignment, local path name # /home/classes/ee4720/com/s/hw2.s, to a directory ~/hw in your # class account. (~ is your home directory.) Use this file for your # solution. # # (2) Find the problems in this file and solve them. # # A procedure shell has been provided for the each problem. Place # your solution there. # # Assembler code following the problems runs your solutions. # That code can be modified. # # Your entire solution should be in this file. # # Do not rename the line labels in this file and be sure to use the # directory and filename given above. (Line labels may be added.) # # (3) Your solution will automatically be copied from your account by # the TA-bot. # # (4) Start early! Problem 2 is significantly more interesting than # Problem 1. # # (5) Feel free to look at the test code (after the problems) for ideas. ## Additional Resources # # MIPS Architecture Manual Volume 2 (Contains a list of instructions.) # http://www.ece.lsu.edu/ee4720/mips32v2.pdf # Note: SPIM implements MIPS-I instructions. # # SPIM Documentation: # Appendix A of Patterson and Hennessey. # http://www.ece.lsu.edu/3755/spim.pdf # # Account Setup and Emacs (Text Editor) Instructions # http://www.ece.lsu.edu/ee4720/proc.html # To learn Emacs look for and follow instructions for the Emacs tutorial. # # Unix Help # http://www.ece.lsu.edu/v/4ltrwrd/ ## Grading Criteria # # The code must work. # # The code must be reasonably efficient. # # Points will be DEDUCTED for obviously unnecessary or inefficient code. # For example, instead of doing this: # add $2, $0, $0 # This instruction not needed!!!!!!!!!!!!!!!!!!! # or $2, $3, $4 # Do this: # or $2, $3, $4 # Division or multiplication by powers of 2 must use shift instructions. ## Note on SPIM # # Clicking the close button (usually the upper-right-hand button on # the window frame) of any window will immediately exit SPIM. # ## Troubleshooting # # Make sure that the "run" dialog box shows 0x0400000 for the starting # address. If not, __start was not properly defined, possibly due to # an error before __start. # # Check the messages (bottommost) pane for syntax and other errors. It # may be necessary to shorten other panes to make the messages pane visible. # Common syntax errors include using "addi" instead of "add", or vice versa. # Another common error is mistyping a label in a branch or jump target. # # Check the "Text Segments" pane to make sure all of your program is there. # If not, there may have been an error reading the program. # # If your program fails a test or otherwise does not produce the # expected output modify the test code so that the particular test it # fails comes first (if it's not already). Then, single-step the code # (using the "step") button until you find the problem. # # If you've hit a wall ask the TA or instructor help. It's better to # err on the side of too many questions than too few. .text ################################################################################ ## Problem 1 # # Complete the routine below so that it returns the product of # the elements of an integer array. As described in the comments, # the array elements are four-byte (one-word) integers. The returned # product should be a double-precision floating-point number. # [ ] A correct solution uses 10 instructions. (Can be longer.) # [ ] Remember to convert numbers properly. # [ ] The only allowable synthetic instruction is nop. product: # CALL VALUE: $a0 Address of start of array. # CALL VALUE: $a1 Address of end of array (element after last). # Array elements are word-sized signed integers. # RETURN VALUE: $f0/$f1 Product of elements in array as double. # Solution goes here. jr $ra nop ################################################################################ ## Problem 2 # # Complete the routine below so that it sorts elements of array # $A0-$A1 into ascending order. Elements are interpreted as # word-sized signed integers. Array is to be sorted in place. (That # is, rearrange the elements, don't copy them into a new array.) # # Sort using the quicksort algorithm. C code for quicksort is shown # below: # void # sort(int *start, int *stop) // Start same as $a0, stop same as $a1 # { # int a0 = *start; // Pivot element. # int *sptr = start + 1; // Small-end pointer. # if( sptr >= stop ) return; # int *lptr = stop - 1; // Large-end pointer. # while( 1 ) # { # while( sptr < stop && *sptr < a0 ) sptr++; # while( lptr > start && *lptr >= a0 ) lptr--; # if( sptr >= lptr ) break; # int s = *sptr; *sptr = *lptr; *lptr = s; # } # *start = *lptr; *lptr = a0; # sort(start,sptr); # sort(sptr,stop); # } # The routine is best solved recursively. If a recursive solution # is provided registers must be saved and restored properly. Code # for doing so is shown below. # # As an aid to debugging sample code for printing the contents of the # array is shown. Please remove (or comment out) this code when you # are done debugging. # [ ] A correct solution has 54 instructions. # [ ] Be sure to save any $s registers your code will overwrite. # [ ] Save any $t or $a registers before calling other routines. # [ ] Do not save or restore registers unnecessarily. # [ ] The only allowable synthetic instruction is nop (and la in debug code). # When things go wrong: # [ ] Make sure recursion is not infinite. That will cause a stack error. # [ ] Make sure registers are saved and restored properly. sort: # CALL VALUE: $a0 Address of start of array. # CALL VALUE: $a1 Address of end of array (element after last). # Some solution might go here. (Hint) ## Save registers on the stack. # # Save $s registers that this code will write. # Save $ra and any $t registers that will be needed after a call. # No need to save $s registers that this code does not write. # No need to save $t registers that this code does not read. # Be sure to reduce the stack pointer by four bytes per register saved. # Do not save or restore registers unnecessarily. # sw $s0, -4($sp) # Remove if not needed. sw $s1, -8($sp) # Remove if not needed. sw $ra, -12($sp) addi $sp, $sp, -12 # Adjust as needed. # Most of the solution would go here. # Code for showing array. Uncomment when needed, re-comment afterwards. # la $a2, msg_null # jal show # nop ## Restore registers from the stack. # # Restore $s registers. # Any $t registers saved should be restored up above, before being read. # addi $sp, $sp, 12 lw $s1, -8($sp) lw $ra, -12($sp) jr $ra lw $s0, -4($sp) ################################################################################ ## Main Routine # This routine runs the test code for the problems It does not have to # be modified but it can be if it would help. If you're thinking of # improving your grade by deleting the test cases which your code gets # wrong you'll need to come up with a better plan. .data array: .word 1 7 4 3 8 arraym: .word 12 1 7 4 3 8 arrayb: .word 50 99 10 51 98 83 70 40 30 35 19 arraydull: .word 1 1 1 1 1 1 no_more_arrays: .word 0 # Keep label above word-aligned products: .double 672. .double 8064. .double 1147045048380000000. .double 1. arrays: .word array .word arraym .word arrayb .word arraydull .word no_more_arrays .word 0 descriptions: .asciiz "Minimum element first." .asciiz "Maximum element first." .asciiz "Middle element first." .asciiz "All ones." msg_element: .asciiz "%/t5/s %/t1/2d " msg_running_test: .ascii "Running test: %/a2/s, XX below shows any sort error position.\n" .asciiz "Before: " msg_bye: .asciiz "Done with tests.\n" msg_before: .asciiz "Before: " msg_after: .asciiz "After : " msg_null: .asciiz "" msg_xx: .asciiz "XX" msg_eol: .asciiz "\n" msg_prod: .asciiz "Product of:" msg_prod_is: .asciiz " returned is %/f0/.2f, correct is %/f2/.2f.\n\n" .text .globl __start __start: la $s0, arrays la $s1, descriptions la $s2, products MSLOOP: lw $a1, 4($s0) beq $a1, $0 MSEXIT nop jal product lw $a0, 0($s0) addi $v0, $0, 11 la $a0, msg_prod syscall lw $a0, 0($s0) la $a2, msg_null jal show lw $a1, 4($s0) ldc1 $f2, 0($s2) addi $s2, $s2, 8 la $a0, msg_prod_is addi $v0, $0, 11 syscall jal strlen addi $a0, $s1, 0 add $s1, $s1, $v0 addi $s1, $s1, 1 j MSLOOP addi $s0, $s0, 4 la $s0, arrays la $s1, descriptions MSEXIT: la $s0, arrays la $s1, descriptions MLOOP: lw $a1, 4($s0) beq $a1, $0 MEXIT lw $a0, 0($s0) jal runsort addi $a2, $s1, 0 jal strlen addi $a0, $s1, 0 add $s1, $s1, $v0 addi $s1, $s1, 1 j MLOOP addi $s0, $s0, 4 MEXIT: la $a0, msg_bye addi $v0, $0, 11 syscall addi $v0, $0, 10 syscall ################################################################################ ## runsort: Call sort routine on array. # # Print descriptive message, array $A0-$A1 (before version), call sort, # then print array again, showing an XX at between first misordered # elements (if any). # CALL VALUE: $a0 Address of array. # CALL VALUE: $a1 Address of array end. (Element after last.) # CALL VALUE: $a2 Address of string describing array. runsort: sw $ra, -4($sp) sw $s0, -8($sp) sw $s1, -12($sp) addi $sp, $sp, -12 addi $s0, $a0, 0 addi $s1, $a1, 0 addi $v0, $0, 11 la $a0, msg_running_test syscall addi $a0, $s0, 0 la $a2, msg_null jal show nop addi $a0, $s0, 0 addi $a1, $s1, 0 jal sort nop la $a0, msg_after addi $v0, $0, 11 syscall la $a2, msg_xx addi $a0, $s0, 0 jal show addi $a1, $s1, 0 addi $v0, $0, 11 la $a0, msg_eol syscall addi $sp, $sp, 12 lw $ra, -4($sp) lw $s0, -8($sp) jr $ra lw $s1, -12($sp) ################################################################################ ## show: Print elements of array. # # Print elements of array $A0-$A1. Put string $A2 between misordered # elements (if any). # # CALL VALUE: $a0 Array start. # CALL VALUE: $a1 Array end # CALL VALUE: $a2 XX show: addi $v0, $0, 11 addi $t0, $a0, 0 la $a0, msg_element la $t3, msg_null lw $t2, 0($t0) SHLOOP: lw $t1, 0($t0) slt $t7, $t1, $t2 addi $t2, $t1, 0 beq $t7, $0 SHSKIP addi $t5, $t3, 0 # Speculative addi $t5, $a2, 0 SHSKIP: addi $t0, $t0, 4 bne $t0, $a1 SHLOOP syscall la $a0, msg_eol syscall jr $ra nop ################################################################################ ## strlen: String Length strlen: ## Register Usage # # CALL VALUE : $a0: Address of first character of string. # RETURN VALUE: $v0: The length of the string. # # $t0: Character being examined. # $t1: Address of current character being examined. # addi $t1, $a0, 0 SLOOP: lbu $t0, 0($t1) bne $t0, $0, SLOOP addi $t1, $t1, 1 addi $t1, $t1, -1 jr $ra sub $v0, $t1, $a0