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
|
# --------------------------------------------
# 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
|