From fe3b403d5788c3ead9391d02a95c4684daab0272 Mon Sep 17 00:00:00 2001 From: Andreas Kapp Lindquist Date: Tue, 28 Oct 2025 10:58:47 +0100 Subject: refactor(quicksort): renamed to qsort to quicksort and added helper function for better interface --- src/qsort.s | 119 ------------------------------------------------ src/quicksort.s | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 137 insertions(+), 119 deletions(-) delete mode 100755 src/qsort.s create mode 100755 src/quicksort.s (limited to 'src') diff --git a/src/qsort.s b/src/qsort.s deleted file mode 100755 index 564a25e..0000000 --- a/src/qsort.s +++ /dev/null @@ -1,119 +0,0 @@ -# -------------------------------------------- -# 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 diff --git a/src/quicksort.s b/src/quicksort.s new file mode 100755 index 0000000..78b9eea --- /dev/null +++ b/src/quicksort.s @@ -0,0 +1,137 @@ +# -------------------------------------------- +# FUNCTION: quicksort +# PURPOSE : Calls the _quicksort function with the right parameters +# INPUTS : rdi = address for A +# rsi = number of coordinates n +# rdx = index of key to sort by +# OUTPUTS : rax = address for sorted A +# NOTES : preserves rdi, rdx +# -------------------------------------------- +.section .text +.globl quicksort +.type quicksort, @function +quicksort: + leaq -1(%rsi), %rcx + xorq %rsi, %rsi + call _quicksort + ret + +# -------------------------------------------- +# FUNCTION: _quicksort +# 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 _quicksort +.type _quicksort, @function +_quicksort: + 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 _quicksort + +# --- right recursion --- + leaq 1(%r14), %rsi # low = p + 1 + movq %r13, %rcx # high + call _quicksort + +.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 -- cgit v1.2.3-70-g09d2