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
|
# --------------------------------------------
# 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 %r12
pushq %r13
pushq %r14
pushq %rbx
cmp $1, %rsi
jle .qsort_done
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
# --- left recursion ---
movq %r13, %rdi
movq %r12, %rsi # n = p
movq %rbx, %rdx # restore column
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
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
popq %r12
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.
# --------------------------------------------
.globl hoare_part
.type hoare_part, @function
hoare_part:
pushq %r12
pushq %r13
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
.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]
cmpq %r11, %r12 # if arr[i] < pivot
jl .hoare_Li
# decrement j
.hoare_Lj:
subq $1, %r9
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
jg .hoare_Lj
# check crossing
cmpq %r9, %r8 # if arr[i] > arr[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)
jmp .hoare_loop
.hoare_done:
popq %r11
popq %r13
popq %r12
movq %r9, %rax
ret
|