diff options
Diffstat (limited to '')
| -rw-r--r-- | src/main.s | 1 | ||||
| -rw-r--r-- | src/qsort.s | 80 |
2 files changed, 36 insertions, 45 deletions
@@ -16,6 +16,7 @@ _start: # Sort movq %rax, %rdi # Select address of array movq %r15, %rsi # Select length of array + decq %rsi movq $1, %rdx # Sort by key 1 call qsort # Sort the array diff --git a/src/qsort.s b/src/qsort.s index addcf5a..233ec34 100644 --- a/src/qsort.s +++ b/src/qsort.s @@ -13,40 +13,35 @@ .globl qsort .type qsort, @function qsort: + pushq %rbx pushq %r12 pushq %r13 - pushq %r14 - pushq %rbx cmp $1, %rsi jle .qsort_done + movq %rdi, %r12 # r12 = original array pointer + movq %rsi, %r13 # r13 = original length call hoare_part - movq %rax, %r12 # r8 = partition - movq %rdi, %r13 # r13 = original array pointer - movq %rsi, %r14 # r14 = original n - movq %rdx, %rbx # rbx = column index + movq %rax, %rbx # rbx = partition # --- left recursion --- - movq %r13, %rdi - movq %r12, %rsi # n = p - movq %rbx, %rdx # restore column + movq %r12, %rdi + movq %rbx, %rsi # n = p call qsort # --- right recursion --- - leaq 1(%r12), %rax # rax = p + 1 - leaq (%r13, %rax, 8), %rdi # rdi = A + (p + 1) - movq %r14, %rsi # rsi = original n + 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) - movq %rbx, %rdx # restore column call qsort .qsort_done: - movq %r13, %rax - popq %rbx - popq %r14 - popq %r13 + movq %r12, %rax # just returning the same buffer + popq %r13 # as quicksort is inplace popq %r12 + popq %rbx ret # -------------------------------------------- @@ -57,61 +52,56 @@ qsort: # 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, %r8 # i = -1 - movq %rsi, %r9 # j = arr.len - movq (%rdi), %r10 # pivot = &arr[0] - movq (%r10, %rdx, 8), %r11 # value of pivot - pushq %r11 + 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: - addq $1, %r8 - - cmpq %r9, %r8 - jge .hoare_done - - movq (%rdi, %r8, 8), %r13 - movq (%r13, %rdx, 8), %r12 # value of arr[i] + incq %rax + movq (%rdi, %rax, 8), %r12 + movq (%r12, %rdx, 8), %r12 # value of arr[i] - cmpq %r11, %r12 # if arr[i] < pivot + cmpq %r13, %r12 # if arr[i] < pivot jl .hoare_Li # decrement j .hoare_Lj: - subq $1, %r9 + decq %rbx + movq (%rdi, %rbx, 8), %r12 # r12 = arr[j] + movq (%r12, %rdx, 8), %r12 # value of arr[j] - cmpq $0, %r9 - jl .hoare_done - - movq (%rdi, %r9, 8), %r13 - movq (%r13, %rdx, 8), %r12 # value of arr[j] - - cmpq %r11, %r12 # if arr[j] > pivot + cmpq %r13, %r12 # if arr[j] > pivot jg .hoare_Lj # check crossing - cmpq %r9, %r8 # if arr[i] > arr[j] + cmpq %rbx, %rax # if i >= j jge .hoare_done # swap a[i] and a[j] - movq (%rdi, %r8, 8), %r12 - movq (%rdi, %r9, 8), %r13 - movq %r13, (%rdi, %r8, 8) - movq %r12, (%rdi, %r9, 8) + 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: - popq %r11 + movq %rbx, %rax # return j as pivot + popq %r14 popq %r13 popq %r12 - movq %r9, %rax + popq %rbx ret |