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
|
# --------------------------------------------
# FUNCTION: insertion_sort
# 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 = length of A in 64 bit chunks
# rdx = index of key to sort by
# OUTPUTS : rax = address for sorted A
# CLOBBERS: none
# NOTES : Preserves all registers. Recursive psudocode taken from
# https://en.wikipedia.org/wiki/Insertion_sort
# --------------------------------------------
.section .text
.globl insertion_sort
.type insertion_sort, @function
insertion_sort:
# Save registers
push %rbx
push %rbp
push %r12
push %r13
push %r14
push %r15
cmp $0, %rsi # Check if length of array is zero
je end # Jump to end if it is
push %rsi # Save array size
subq $1, %rsi # Decrease size of array
call insertion_sort # Sort recursively
pop %rsi # Restore array size
movq (%rdi, %rsi, 8), %rbp # Save address at A[n] in rbp
movq (%rbp, %rdx, 8), %rbx # Save value of A[n] in rbx
movq %rsi, %r15 # Save copy of n in r15
subq $1, %r15 # Make r15 = n-1 = j
while:
cmp $0, %r15 # Compare j with 0
jl end_while # Go to end if less than
movq (%rdi, %r15, 8), %rbp # Save address at A[j] to rbp
movq (%rbp, %rdx, 8), %r12 # Move value at A[j] into r12
cmp %r12, %rbx # Compare A[j] with A[n]
jge end_while # Go to end if greater than or equal
movq %r15, %r14 # Duplicate r15 into r14
addq $1, %r14 # And add 1: j+1
movq (%rdi, %r14, 8), %rbp # Save address of A[j+1] in rbp
movq %r12, (%rbp, %rdx, 8) # Move value at A[j] into value at A[j+1]
subq $1, %r15 # j = j - 1
jmp while # Go back to start of loop
end_while:
addq $1, %r15 # j = j + 1
movq (%rdi, %r15, 8), %rbp # Move address at A[j] into rbp
movq %rbx, (%rbp, %rdx) # A[j] = x
end:
# Restore registers
pop %r15
pop %r14
pop %r13
pop %r12
pop %rbp
pop %rbx
ret
|