# --------------------------------------------
# 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 = low
#           rdx = index of key to sort by
#           rcx = high
# OUTPUTS : rax = address for sorted A
# NOTES   : preserves rdi, rdx
# --------------------------------------------
.section .text
.globl qsort
.type qsort, @function
qsort:
    pushq %r12
    pushq %r13
    pushq %r14

    cmpq $0, %rsi               # if 0 < low 
    jl .qsort_exit
    cmpq $0, %rcx               # if 0 < high 
    jl .qsort_exit
    cmpq %rcx, %rsi             # if high < low 
    jge .qsort_exit

    call hoare_part             # rax = p

    movq %rsi, %r12             # save low
    movq %rcx, %r13             # save high
    movq %rax, %r14             # save p

# --- left recursion ---
    movq %r12, %rsi             # low
    movq %r14, %rcx             # high = p
    call qsort
    
# --- right recursion ---
    leaq 1(%r14), %rsi          # low = p + 1
    movq %r13, %rcx             # high
    call qsort

.qsort_exit:
    movq %rdi, %rax

    popq %r14
    popq %r13
    popq %r12
    ret

# --------------------------------------------
# FUNCTION: hoare_part
# 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 = low
#           rdx = index of key to sort by
#           rcx = high
# OUTPUTS : rax = address for sorted A
# NOTES   : preserves rdi, rdx
# --------------------------------------------
.section .text
.globl hoare_part
.type hoare_part, @function
hoare_part:
    pushq %rbx
    pushq %r12
    pushq %r13
    pushq %r14

    leaq -1(%rsi), %rax         # i = low - 1
    leaq 1(%rcx), %rbx          # j = high + 1

    # r12 = pivot
    movq (%rdi, %rsi, 8), %r12  # &A[low]
    movq (%r12, %rdx, 8), %r12  # A[low][idx]
    
# left index
.hoare_part_left:
    incq %rax

    movq (%rdi, %rax, 8), %r13  # &A[i]
    movq (%r13, %rdx, 8), %r13  # A[i][idx]

    cmpq %r12, %r13             # while pivot < A[i][idx]
    jl .hoare_part_left

# right index
.hoare_part_right:
    decq %rbx

    movq (%rdi, %rbx, 8), %r13  # &A[j]
    movq (%r13, %rdx, 8), %r13  # A[j][idx]

    cmpq %r12, %r13             # while pivot > A[j][idx] 
    jg .hoare_part_right

# check crossing
    cmpq %rbx, %rax             # i >= j
    jge .hoare_part_done

# swap A[i] and A[j]
    movq (%rdi, %rax, 8), %r13
    movq (%rdi, %rbx, 8), %r14
    movq %r14, (%rdi, %rax, 8)
    movq %r13, (%rdi, %rbx, 8)

    jmp .hoare_part_left

.hoare_part_done:
    movq %rbx, %rax             # return j as partion index

    popq %r14
    popq %r13
    popq %r12
    popq %rbx
    ret