# --------------------------------------------
# FUNCTION: qsort
# PURPOSE : Sorts array A, with references to arrays A_i,
#           based on the given key in A_i,
#           address and size of A.
# INPUTS  : rdi = address for A
#           rsi = number of coordinates n
#           rdx = index of key to sort by
# OUTPUTS : rax = address for sorted A
# CLOBBERS: none
# --------------------------------------------
.section .text
.globl qsort
.type qsort, @function
qsort:
    pushq %rbx
    pushq %r12
    pushq %r13

    cmp $1, %rsi
    jle .qsort_done

    movq %rdi, %r12             # r12 = original array pointer
    movq %rsi, %r13             # r13 = original length
    call hoare_part
    movq %rax, %rbx             # rbx = partition

    # --- left recursion ---
    movq %r12, %rdi
    movq %rbx, %rsi             # n = p
    call qsort

    # --- right recursion ---
    leaq 1(%rbx), %rax          # rax = p + 1
    leaq (%r12, %rax, 8), %rdi  # rdi = A + (p + 1)
    movq %r13, %rsi             # rsi = original length
    subq %rax, %rsi             # rsi = n - (p + 1)
    call qsort

.qsort_done:
    movq %r12, %rax             # just returning the same buffer
    popq %r13                   # as quicksort is inplace
    popq %r12
    popq %rbx
    ret

# --------------------------------------------
# FUNCTION: hoare_part
# PURPOSE : 
# INPUTS  : rdi = address for A
#           rsi = number of coordinates n
#           rdx = index of key to sort by
# OUTPUTS : rax = Returns the partition index
#           for quicksort.
# NOTES   : rdx is preserved
# --------------------------------------------
.globl hoare_part
.type hoare_part, @function
hoare_part: 
    pushq %rbx
    pushq %r12
    pushq %r13
    pushq %r14

    movq $-1, %rax              # i = -1
    leaq 1(%rsi), %rbx          # j = n + 1
    movq (%rdi), %r12           # pivot pointer = A[0]
    movq (%r12, %rdx, 8), %r13  # value of pivot

.hoare_loop:
# increment i
.hoare_Li:
    incq %rax
    movq (%rdi, %rax, 8), %r12
    movq (%r12, %rdx, 8), %r12  # value of arr[i]

    cmpq %r13, %r12             # if arr[i] < pivot
    jl .hoare_Li
    
# decrement j
.hoare_Lj:
    decq %rbx
    movq (%rdi, %rbx, 8), %r12  # r12 = arr[j]
    movq (%r12, %rdx, 8), %r12  # value of arr[j]

    cmpq %r13, %r12             # if arr[j] > pivot
    jg .hoare_Lj

    # check crossing
    cmpq %rbx, %rax             # if i >= j
    jge .hoare_done
    
    # swap a[i] and a[j]
    movq (%rdi, %rax, 8), %r12
    movq (%rdi, %rbx, 8), %r14
    movq %r14, (%rdi, %rax, 8)
    movq %r12, (%rdi, %rbx, 8)

    jmp .hoare_loop

.hoare_done:
    movq %rbx, %rax              # return j as pivot
    popq %r14
    popq %r13
    popq %r12
    popq %rbx
    ret