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
|
# --------------------------------------------
# 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 bytes
# rdx = index of key to sort by
# OUTPUTS : rax = address for sorted A
# CLOBBERS: none
# NOTES : Preserves all registers
# --------------------------------------------
.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, 1), %rdx), %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 %r15, $0 # Compare j with 0
jl end # Go to end if less than
movq ((%rdi, %r15, 1), %rdx), %r12 # Move A[j] into r12
cmp %r12, %rbx # Compare A[j] with A[n]
jge end # Go to end if greater than or equal
movq %r15, %r14 # Duplicate r15 into r14
addq $1, %r14 # And add 1: j+1
movq %r12, ((%rdi, %r14, 1), %rdx) # Move A[j] into 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 %rbx, ((%rdi, %r15, 1), %rdx) # A[j+1] = x
end:
# Restore registers
pop %r15
pop %r14
pop %r13
pop %r12
pop %rbp
pop %rbx
ret
|