diff options
| -rw-r--r-- | src/main.s | 4 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/qsort.s | 124 |
2 files changed, 70 insertions, 58 deletions
@@ -15,8 +15,8 @@ _start: # Sort movq %rax, %rdi # Select address of array - movq %r15, %rsi # Select length of array - decq %rsi + leaq -1(%r15), %rcx # Select length of array -1 as high + xorq %rsi, %rsi # low = 0 movq $1, %rdx # Sort by key 1 call qsort # Sort the array diff --git a/src/qsort.s b/src/qsort.s index 233ec34..564a25e 100644..100755 --- a/src/qsort.s +++ b/src/qsort.s @@ -4,102 +4,114 @@ # based on the given key in A_i, # address and size of A. # INPUTS : rdi = address for A -# rsi = number of coordinates n +# rsi = low # rdx = index of key to sort by +# rcx = high # OUTPUTS : rax = address for sorted A -# CLOBBERS: none +# NOTES : preserves rdi, rdx # -------------------------------------------- .section .text .globl qsort .type qsort, @function qsort: - pushq %rbx pushq %r12 pushq %r13 + pushq %r14 - cmp $1, %rsi - jle .qsort_done + 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 - movq %rdi, %r12 # r12 = original array pointer - movq %rsi, %r13 # r13 = original length - call hoare_part - movq %rax, %rbx # rbx = partition + call hoare_part # rax = p - # --- left recursion --- - movq %r12, %rdi - movq %rbx, %rsi # n = p - call qsort + movq %rsi, %r12 # save low + movq %rcx, %r13 # save high + movq %rax, %r14 # save p - # --- 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) +# --- 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 -.qsort_done: - movq %r12, %rax # just returning the same buffer - popq %r13 # as quicksort is inplace + popq %r14 + popq %r13 popq %r12 - popq %rbx ret # -------------------------------------------- # FUNCTION: hoare_part -# PURPOSE : +# 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 +# rsi = low # rdx = index of key to sort by -# OUTPUTS : rax = Returns the partition index -# for quicksort. -# NOTES : rdx is preserved +# rcx = high +# OUTPUTS : rax = address for sorted A +# NOTES : preserves rdi, rdx # -------------------------------------------- +.section .text .globl hoare_part .type hoare_part, @function -hoare_part: +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 + leaq -1(%rsi), %rax # i = low - 1 + leaq 1(%rcx), %rbx # j = high + 1 -.hoare_loop: -# increment i -.hoare_Li: + # 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), %r12 - movq (%r12, %rdx, 8), %r12 # value of arr[i] - cmpq %r13, %r12 # if arr[i] < pivot - jl .hoare_Li - -# decrement j -.hoare_Lj: + 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), %r12 # r12 = arr[j] - movq (%r12, %rdx, 8), %r12 # value of arr[j] - cmpq %r13, %r12 # if arr[j] > pivot - jg .hoare_Lj + movq (%rdi, %rbx, 8), %r13 # &A[j] + movq (%r13, %rdx, 8), %r13 # A[j][idx] - # check crossing - cmpq %rbx, %rax # if i >= j - jge .hoare_done - - # swap a[i] and a[j] - movq (%rdi, %rax, 8), %r12 + 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 %r12, (%rdi, %rbx, 8) + movq %r13, (%rdi, %rbx, 8) + + jmp .hoare_part_left - jmp .hoare_loop +.hoare_part_done: + movq %rbx, %rax # return j as partion index -.hoare_done: - movq %rbx, %rax # return j as pivot popq %r14 popq %r13 popq %r12 |