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