////////////////////////////////////////////////////////////////////////////////
// Lab 5
////////////////////////////////////////////////////////////////////////////////

// Include the checkoff program:
.include "checkoff.uasm"

// Leave the following as zero to run ALL the test cases, and get your solution
//   validated if all pass.  If you have trouble with test case N, set it to N
//   to run JUST that test case (for easier debugging):
TestCase:       LONG(0)

// Quicksort-in-place code.  We include the C/Python version here as a comment;
// you can use this as a model for your Beta assembly version:

//def partition(array,left,right):
//    # choose middle element of array as pivot
//    pivotIndex = (left+right) >> 1;
//    pivotValue = array[pivotIndex]
//
//    # swap array[right] and array[pivotIndex]
//    # note that we already store array[pivotIndex] in pivotValue
//    array[pivotIndex] = array[right]
//
//    # elements <= the pivot are moved to the left (smaller indices)
//    storeIndex = left
//    for i in xrange(left,right):  # don't include array[right]
//        temp = array[i]
//        if temp <= pivotValue:
//            array[i] = array[storeIndex]
//            array[storeIndex] = temp
//            storeIndex += 1
//
//    # move pivot to its final place
//    array[right] = array[storeIndex]
//    array[storeIndex] = pivotValue;
//    return storeIndex;

partition:
        PUSH(LP)        // standard entry sequence
        PUSH(BP)
        MOVE(SP, BP)

        // save registers we use below
        PUSH(R1)
        PUSH(R2)
        PUSH(R3)
        PUSH(R4)
        PUSH(R5)
        PUSH(R6)
        PUSH(R7)
        PUSH(R8)
        PUSH(R9)
        PUSH(R10)
        PUSH(R11)
        PUSH(R12)
        PUSH(R13)

        LD(BP, -12, R3) // R3 = address of array[0]
        LD(BP, -16, R2) // R2 = left
        LD(BP, -20, R1) // R1 = right

        // pivotIndex = (left + right) >> 1
        ADD(R1, R2, R0) // R0 = left + right
        SHRC(R0, 1, R4) // R4 = (left + right) >> 1 = pivotIndex

        // pivotValue = array[pivotIndex]
        MULC(R4, 4, R0) // R0 = pivotIndex*4
        ADD(R3, R0, R0) // R0 = address of array[0] + 4*pivotIndex
                        //    = address of array[pivotIndex]
        LD(R0, 0, R5)   // R5 = array[pivotIndex] = pivotValue

        // array[pivotIndex] = array[right]
        MULC(R1, 4, R6) // R6 = right*4
        ADD(R3, R6, R6) // R6 = address of array[0] + 4*right
                        //    = address of array[right]
        LD(R6, 0, R6)   // R6 = Mem(address of array[right]) = array[right]
        ST(R6, 0, R0)   // Mem[address of array[pivotIndex]] = array[right]

        // storeIndex = left
        ADDC(R2, 0, R6) // R6 = left + 0 = left = storeIndex

        // for i in xrange(left, right)
        SUB(R1, R2, R7) // R7 = right - left = iterations left
        ADDC(R2, 0, R8) // R8 = left + 0 = i = counter
start_of_loop:
        BEQ(R7, end_of_loop, R31)

        // DO SHIT
        // temp = array[i]
        MULC(R8, 4, R0) // R0 = i*4
        ADD(R3, R0, R0) // R0 = address of array[0] + i*4
                        //    = address of array[i]
        LD(R0, 0, R9)   // R9 = Mem[address of array[i] + 0] = temp

        // if temp <= pivotValue:
        CMPLE(R9, R5, R10)  // R10 = bool of "temp <= pivotValue"
        BEQ(R10, end_of_if, R31)    // if-condition check

        // array[i] = array[storeIndex]
        MULC(R6, 4, R11)    // R11 = storeIndex * 4
        ADD(R3, R11, R11)   // R11 = address of array[0] + storeIndex*4
                            //     = address of array[storeIndex]
        LD(R11, 0, R12) // R12 = Mem[R11 + 0] = array[storeIndex]
        ST(R12, 0, R0)  // Mem(R0 + 0) = R12
                        // Mem(address of array[i]) = array[storeIndex]
                        // array[i] = array[storeIndex]

        // array[storeIndex] = temp
        ST(R9, 0, R11)  // Mem(R11 + 0) = R9
                        // Mem(address of array[storeIndex]) = temp
                        // array[storeIndex] = temp

        // storeIndex += 1
        ADDC(R6, 1, R6)

        // END DO SHIT

end_of_if:
        SUBC(R7, 1, R7)
        ADDC(R8, 1, R8)
        BR(start_of_loop, R31)

end_of_loop:

        // array[right] = array[storeIndex]
        MULC(R6, 4, R0) // R0 = storeIndex*4
        ADD(R3, R0, R0) // R0 = address of array[0] + storeIndex*4
                        //    = address of array[storeIndex]
        LD(R0, 0, R13)  // R13 = Mem(R0 + 0) = Mem(address of array[storeIndex])
                        //     = array[storeIndex]
        MULC(R1, 4, R0) // R0 = right*4
        ADD(R3, R0, R0) // R0 = address of array[0] + right*4
                        //    = address of array[right]
        ST(R13, 0, R0)  // Mem(R0 + 0) = R13
                        // Mem(address of array[right]) = array[storeIndex]
                        // array[right] = array[storeIndex]

        // array[storeIndex] = pivotValue
        MULC(R6, 4, R0) // R0 = storeIndex*4
        ADD(R3, R0, R0) // R0 = address of array[0] + storeIndex*4
                        //    = address of array[storeIndex]
        ST(R5, 0, R0)   // Mem(R0 + 0) = R5
                        // Mem(address of array[storeIndex]) = pivotValue
                        // array[storeIndex] = pivotValue

        // return storeIndex
        ADDC(R6, 0, R0) // R0 = R6 + 0 = storeIndex


        // restore saved registers
        POP(R13)
        POP(R12)
        POP(R11)
        POP(R10)
        POP(R9)
        POP(R8)
        POP(R7)
        POP(R6)
        POP(R5)
        POP(R4)
        POP(R3)
        POP(R2)
        POP(R1)

        MOVE(BP, SP)
        POP(BP)
        POP(LP)
        JMP(LP)


//def quicksort(array, left, right):
//    if left < right:
//        pivotIndex = partition(array,left,right)
//        quicksort(array,left,pivotIndex-1)
//        quicksort(array,pivotIndex+1,right)

// quicksort(ArrayBase, left, right)
quicksort:
        PUSH(LP)        // standard entry sequence
        PUSH(BP)
        MOVE(SP, BP)

        // save registers we use below
        PUSH(R1)
        PUSH(R2)
        PUSH(R3)
        PUSH(R4)
        PUSH(R5)

        LD(BP, -12, R3) // R3 = address of array[0]
        LD(BP, -16, R2) // R2 = left
        LD(BP, -20, R1) // R1 = right

        // if left < right
        CMPLT(R2, R1, R4) // R4 = bool of if-condition
        BEQ(R4, end_of_quicksort, R31) // branch if if-condition not true

        // call partition, according to templete in L10 slide 23
        // return value will be in R0, which is pivotIndex
        PUSH(R1)            // push 'right'
        PUSH(R2)            // push 'left'
        PUSH(R3)            // push 'ArrayBase'
        BR(partition, LP)   // call partition()
        DEALLOCATE(3)       // clean up!

        ADDC(R0, 0, R5)     // move pivotIndex to R5

        // quicksort(array, left, pivotIndex - 1)
        SUBC(R5, 1, R0)     // R0 = pivotIndex - 1
        PUSH(R0)            // push 'pivotIndex - 1'
        PUSH(R2)            // push 'left'
        PUSH(R3)            // push 'ArrayBase'
        BR(quicksort, LP)   // call quicksort()
        DEALLOCATE(3)       // clean up!

        // quicksort(array, pivotIndex+1, right)
        ADDC(R5, 1, R0)     // R0 = pivotIndex + 1
        PUSH(R1)            // push 'right'
        PUSH(R0)            // push 'pivotIndex + 1'
        PUSH(R3)            // push 'ArrayBase'
        BR(quicksort, LP)   // call quicksort()
        DEALLOCATE(3)       // clean up!

end_of_quicksort:
        // restore saved registers
        POP(R5)
        POP(R4)
        POP(R3)
        POP(R2)
        POP(R1)

        MOVE(BP, SP)    // standard exit sequence
        POP(BP)
        POP(LP)
        JMP(LP)

// Allocate a stack: SP is initialized by checkoff code.
StackBasePtr:
        LONG(StackArea)

.unprotect

StackArea:
        STORAGE(1000)