#-----------------------------------------------------------------------------
#       Procedure Name:         swap(int v[], int k)
#
#       Description:            Exch. the contents of v[k] and v[k+1]
#
#       Register Allocation:    $4:     pointer to v[0]
#                               $5:     k
#                               $2:     base register for array accesses
#                               $15:    scratch
#                               $16:    scratch
#-----------------------------------------------------------------------------

        .text
        
#-----------------------------------------------------------------------------
#       Save context of caller
#-----------------------------------------------------------------------------

swap:   addi    $29, $29, -12   # Allocate space on stack
        sw      $2, 0($29)      # Save $2 onto stack
        sw      $15, 4($29)     # Save $15 onto stack
        sw      $16, 8($29)     # Save $16 onto stack

#-----------------------------------------------------------------------------
#       Main procedure body
#-----------------------------------------------------------------------------

        sll     $2, $5, 2       # Turn index k into array offset
        add     $2, $4, $2      # + off. to base.   $2 points to v[k].
        lw      $15, 0($2)      # temp1 ($15) = v[k]
        lw      $16, 4($2)      # temp2 ($16) = v[k+1]
        sw      $16, 0($2)      # v[k] <-- v[k+1]
        sw      $15, 4($2)      # v[k+1] <-- v[k]

#-----------------------------------------------------------------------------
#       Restore the context of the caller
#-----------------------------------------------------------------------------

        lw      $2, 0($29)      # Restore $2
        lw      $15, 4($29)     # Restore $15
        lw      $16, 8($29)     # Restore $16
        addi    $29, $29, 12    # Restore the stack pointer

#-----------------------------------------------------------------------------
#       Execute return
#-----------------------------------------------------------------------------

        jr      $31             # Return to calling routine






#-----------------------------------------------------------------------------
#       Procedure Name:         sort(int v[], int n)
#
#       Description:            Sorts the contents of array v[] in
#                               ascending order using bubblesort
#                               (highly inefficient!).
#
#       Register Allocation:    $4:             pointer to v[0]
#                               $5:             n
#                               $17:            loop index j
#                               $19:            loop index i
#                               $21-$23:        scratch registers
#                               $31:            linkage register
#-----------------------------------------------------------------------------

#-----------------------------------------------------------------------------
#       Save context of caller
#
#       n.b.    See note below regarding saving $5 on function call.
#-----------------------------------------------------------------------------

sort:   addi    $29, $29, -24   # Space on stack for 6 registers
        sw      $17, 0($29)     # Save $17 - j loop index
        sw      $19, 4($29)     # Save $19 - i loop index
        sw      $21, 8($29)     # Save $21 - scratch
        sw      $22, 12($29)    # Save $22 - scratch
        sw      $23, 16($29)    # Save $23 - scratch
        sw      $31, 20($29)    # Save $31 - linkage register

#-----------------------------------------------------------------------------
#       Main procedure body
#       Set up outer loop:  for (i=0; i<n; i++)
#-----------------------------------------------------------------------------

        li      $19, 0          # $19 <-- loop index i, i=0;
for1tst: slt    $21, $19, $5    # i<n ?
        beq     $21, $0, exitol # No, take exit if outer loop complete (i>=n)

#-----------------------------------------------------------------------------
#       Set up inner loop:  for (j=i-1; j>=0 && v[j]>v[j+1]; j--)
#-----------------------------------------------------------------------------

        addi    $17, $19, -1    # $17 <-- loop index j, j=i-1
for2tst: slti   $21, $17, 0     # j<0 ?
        bne     $21, $0, exitil # Yes, exit inner loop
        sll     $21, $17, 2     # Turn j into array offset
        add     $21, $4, $21    # $21 <-- pointer to v[j]
        lw      $22, 0($21)     # $22 <-- v[j]
        lw      $23, 4($21)     # $23 <-- v[j+1]
        slt     $21, $23, $22   # v[j+1] < v[j] ?
        beq     $21, $0, exitil # No, exit inner loop

#-----------------------------------------------------------------------------
#       Procedure call swap[v,j];
#
#       n.b.    $5 is overwritten on function call.  Rather than save
#               on stack (time consuming), we save it in a temporary
#               register and restore it immediately afterwards.
#-----------------------------------------------------------------------------
        
        move    $21, $5         # Need to change $5 for function call
        move    $5, $17         # $4 <-- ptr v[j]; $5 <-- j
        jal     swap
        move    $5, $21         # Restore $5.

#-----------------------------------------------------------------------------
#       Bottom of inner loop
#-----------------------------------------------------------------------------
        
        addi    $17, $17, -1    # Decrement loop counter j
        b       for2tst         # Back to top of loop

#-----------------------------------------------------------------------------
#       Bottom of outer loop
#-----------------------------------------------------------------------------
        
exitil: addi    $19, $19, 1     # Increment loop counter i
        b       for1tst         # Back to top of loop

#-----------------------------------------------------------------------------
#       Restore context of the caller
#-----------------------------------------------------------------------------

exitol: lw      $17, 0($29)     # Restore $17
        lw      $19, 4($29)     # Restore $19
        lw      $21, 8($29)     # Restore $21
        lw      $22, 12($29)    # Restore $22
        lw      $23, 16($29)    # Restore $23
        lw      $31, 20($29)    # Restore linkage register
        addi    $29, $29, 24    # Restore stack pointer
                
#-----------------------------------------------------------------------------
#       Execute return
#-----------------------------------------------------------------------------
        
        jr      $31                     # Return to calling routine





#-----------------------------------------------------------------------------
#       Test Program
#
#       Test the sorting program on an array of 10 numbers.  Start off
#       by printing out the list (demonstration of SPIM's built-in
#       system calls), sort it, and print out the sorted result.
#-----------------------------------------------------------------------------

        .globl  main
        
#-----------------------------------------------------------------------------
#       Start off by printing a short banner and the unsorted list.
#-----------------------------------------------------------------------------
        
main:   la      $16, TstArray   # $16 <-- array to be sorted
        li      $18, 10         # $17 <-- loop counter for print
        la      $19, String1    # $19 <-- string to be printed
        move    $4, $19         # Point to the string
        li      $2, 4           # Code for print string
        syscall                 # Header for unsorted array

#-----------------------------------------------------------------------------
#       Printing loop - use the syscall (1) function to print array elements.
#-----------------------------------------------------------------------------

main10: lw      $4, 0($16)      # Get current array element
        li      $2, 1           # Code for print integer
        syscall                 # Execute call
        la      $4, crlf        # String for carriage return + line feed
        li      $2, 4           # Code for print string
        syscall                 # Execute call
        addi    $16, $16, 4     # Point to the next array element
        addi    $18, $18, -1    # Decrement loop counter
        bne     $18, $0, main10 # Loop until array printed
        
#-----------------------------------------------------------------------------
#       Skip a line between unsorted and sorted output
#-----------------------------------------------------------------------------
                
        la      $4, crlf        # String for carriage return + line feed
        li      $2, 4           # Code for print string
        syscall                 # Execute call

#-----------------------------------------------------------------------------
#       Next we use the sorting routine to put the array in order.
#-----------------------------------------------------------------------------

        la      $4, TstArray    # Set up call to sort
        li      $5, 10          # $4 <-- v[0]; $5 <-- size
        jal     sort
        
#-----------------------------------------------------------------------------
#       I really should have set up the print code as a function,
#       but I'll be lazy and simply cut-and-past the code.
#-----------------------------------------------------------------------------

        la      $16, TstArray   # $16 <-- array to be sorted
        li      $18, 10         # $17 <-- loop counter for print
        la      $19, String2    # $19 <-- string to be printed
        move    $4, $19         # Point to the string
        li      $2, 4           # Code for print string
        syscall                 # Header for sorted array

main20: lw      $4, 0($16)      # Get current array element
        li      $2, 1           # Code for print integer
        syscall                 # Execute call
        la      $4, crlf        # String for carriage return + line feed
        li      $2, 4           # Code for print string
        syscall                 # Execute call
        addi    $16, $16, 4     # Point to the next array element
        addi    $18, $18, -1    # Decrement loop counter
        bne     $18, $0, main20 # Loop until array printed
        
#-----------------------------------------------------------------------------
#       Finally we exit by doing the appropriate syscall.
#-----------------------------------------------------------------------------

        li      $2, 10          # Get exit code
        syscall                 # And we're out of here


#-----------------------------------------------------------------------------
#       All the data goes here (data segment)
#-----------------------------------------------------------------------------

        .data

String1: .asciiz "Unsorted array:\n\n"

String2: .asciiz "Sorted array:\n\n"

crlf:    .asciiz "\n"

         .align 2

TstArray: .word 5 299 4 -36 1101 2 25 8000 21 99