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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
# --------------------------------------------
# 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
# --------------------------------------------
.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
|