forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
mergeSort.s
131 lines (110 loc) · 2.6 KB
/
mergeSort.s
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
; University of Virginia
; CS 2150 In-Lab 8
; Spring 2018
; mergeSort.s
global mergeSort
global merge
section .text
; Parameter 1 is a pointer to the int array
; Parameter 2 is the left index in the array
; Parameter 3 is the right index in the array
; Return type is void
mergeSort:
; Implement mergeSort here
; Parameter 1 is a pointer to the int array
; Parameter 2 is the left index in the array
; Parameter 3 is the middle index in the array
; Parameter 4 is the right index in the array
; Return type is void
merge:
; Save callee-save registers
; Store local variables
push rbx ; int i
push r12 ; int j
push r13 ; int k
push r14 ; int n1
push r15 ; int n2
mov r14, rdx ; n1 = mid - left + 1
sub r14, rsi
inc r14
mov r15, rcx ; n2 = right - mid
sub r15, rdx
lea r11, [r14+r15] ; r11 = rsp offset = 4(n1 + n2)
lea r11, [4*r11]
sub rsp, r11 ; allocate space for temp arrays
mov rbx, 0 ; i = 0
mov r12, 0 ; j = 0
; Copy elements of arr[] into L[]
copyLloop:
cmp rbx, r14 ; is i >= n1?
jge copyRloop
; L[i] = arr[left + i]
lea r10, [rsi+rbx]
mov r10d, DWORD [rdi+4*r10] ; r10 = arr[left + i]
mov DWORD [rsp+4*rbx], r10d ; L[i] = r10
inc rbx ; i++
jmp copyLloop
; Copy elements of arr[] into R[]
copyRloop:
cmp r12, r15 ; is j >= n2?
jge endcopyR
; R[j] = arr[mid + 1 + j]
lea r10, [rdx+r12+1]
mov r10d, DWORD [rdi+4*r10] ; r10 = arr[mid + 1 + j]
lea rax, [r12+r14]
mov DWORD [rsp+4*rax], r10d ; R[j] = r10
inc r12 ; j++
jmp copyRloop
endcopyR:
mov rbx, 0 ; i = 0
mov r12, 0 ; j = 0
mov r13, rsi ; k = left
; Merge L[] and R[] into arr[]
mergeLoop:
cmp rbx, r14 ; is i >= n1 or j >= n2?
jge loopL
cmp r12, r15
jge loopL
lea r10, [r12+r14]
mov r10d, DWORD [rsp+4*r10] ; r10d = R[j]
cmp DWORD [rsp+4*rbx], r10d ; is L[i] <= R[j]?
jle if
mov DWORD [rdi+4*r13], r10d ; arr[k] = R[j]
inc r12 ; j++
jmp endif
if:
mov r10d, DWORD [rsp+4*rbx]
mov DWORD [rdi+4*r13], r10d ; arr[k] = L[i]
inc rbx ; i++
endif:
inc r13 ; k++
jmp mergeLoop
; Copy elements of L[] into arr[]
loopL:
cmp rbx, r14 ; is i >= n1?
jge loopR
mov r10d, DWORD [rsp+4*rbx]
mov DWORD [rdi+4*r13], r10d ; arr[k] = L[i]
inc rbx ; i++
inc r13 ; k++
jmp loopL
; Copy elements of R[] into arr[]
loopR:
cmp r12, r15 ; is j >= n2?
jge endR
lea r10, [r12+r14]
mov r10d, DWORD [rsp+4*r10]
mov DWORD [rdi+4*r13], r10d ; arr[k] = R[j]
inc r12 ; j++
inc r13 ; k++
jmp loopR
endR:
; deallocate temp arrays
; restore callee-save registers
add rsp, r11
pop r15
pop r14
pop r13
pop r12
pop rbx
ret