################################################################################
##
## 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