1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
# --------------------------------------------
# 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
|