################################################################################ ## ## LSU EE 4720 Fall 2004 Homework 2 Solution ## ## .data name: .asciiz "Solution" # 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. ## 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.) 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. # Grading Note: # Many solutions initialized the product with the first element # which is better than using the constant 1, as done below. addi $v0, $0, 1 mtc1 $v0, $f0 cvt.d.w $f0, $f0 LOOP: lwc1 $f2, 0($a0) cvt.d.w $f2, $f2 addi $a0, $a0, 4 bne $a0, $a1 LOOP mul.d $f0, $f0, $f2 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. # 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). ## If array has one element return immediately. # # Note that there is no need to save if code returns here. sub $t0, $a1, $a0 slti $t1, $t0, 8 beq $t1, $0, SOCONTINUE nop jr $ra nop SOCONTINUE: ## 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. # sw $s0, -4($sp) sw $s1, -8($sp) sw $ra, -12($sp) addi $sp, $sp, -12 ## Load the pivot element. # # Elements less than the pivot will be moved to the beginning # of the array and elements equal or larger than the pivot # will be moved to the end. # lw $t2, 0($a0) # $t2 Pivot addi $t3, $t2, -1 # $t3 Pivot-1, used for a >= test. addi $s0, $a0, 4 addi $t1, $a1, -4 add $s1, $a1, $0 BIGLOOP: ## Increment small-end pointer ($s0) until element >= pivot ($t2) found. # SMALL_END_LOOP: slt $t7, $s0, $a1 beq $t7, $0 BIG_END_LOOP nop lw $t7, 0($s0) slt $t7, $t7, $t2 beq $t7, $0 BIG_END_LOOP nop j SMALL_END_LOOP addi $s0, $s0, 4 ## Decrement large-end pointer ($t1) until element < pivot ($t2) found. # BIG_END_LOOP: slt $t7, $a0, $t1 beq $t7, $0 EXITBIGEND nop lw $t7, 0($t1) slt $t7, $t3, $t7 beq $t7, $0 EXITBIGEND nop j BIG_END_LOOP addi $t1, $t1, -4 EXITBIGEND: ## Exit loop if small- and large-end pointers met. # slt $t7, $t1, $s0 bne $t7, $0 EXITBIGLOOP nop ## Swap out-of-place elements and continue moving large- and small-end pointers # lw $t7, 0($s0) lw $t6, 0($t1) sw $t7, 0($t1) j BIGLOOP sw $t6, 0($s0) EXITBIGLOOP: ## Move pivot element to its proper place. # lw $t6, 0($t1) sw $t6, 0($a0) sw $t2, 0($t1) ## Call sort routine recursively on large and small end of array. # jal sort addi $a1, $s0, 0 addi $a0, $s0, 0 # Restore a0. jal sort addi $a1, $s1, 0 ## Restore registers from the stack. # # Restore $s registers. # 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 first problem and makes sure # you put your name at the top of the file. 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