forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
mergeSort.s.html
145 lines (124 loc) · 15.5 KB
/
mergeSort.s.html
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="GNU source-highlight
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite">
<title>mergeSort.s</title>
</head>
<body style="background-color:white">
<pre><i><span style="color:#9A1900">; University of Virginia</span></i>
<i><span style="color:#9A1900">; CS 2150 In-Lab 8</span></i>
<i><span style="color:#9A1900">; Spring 2018</span></i>
<i><span style="color:#9A1900">; mergeSort.s </span></i>
global mergeSort
global merge
section <span style="color:#990000">.</span>text
<i><span style="color:#9A1900">; Parameter 1 is a pointer to the int array </span></i>
<i><span style="color:#9A1900">; Parameter 2 is the left index in the array </span></i>
<i><span style="color:#9A1900">; Parameter 3 is the right index in the array</span></i>
<i><span style="color:#9A1900">; Return type is void </span></i>
<b><span style="color:#000080">mergeSort:</span></b>
<i><span style="color:#9A1900">; Implement mergeSort here</span></i>
<i><span style="color:#9A1900">; Parameter 1 is a pointer to the int array </span></i>
<i><span style="color:#9A1900">; Parameter 2 is the left index in the array</span></i>
<i><span style="color:#9A1900">; Parameter 3 is the middle index in the array </span></i>
<i><span style="color:#9A1900">; Parameter 4 is the right index in the array</span></i>
<i><span style="color:#9A1900">; Return type is void </span></i>
<b><span style="color:#000080">merge:</span></b>
<i><span style="color:#9A1900">; Save callee-save registers</span></i>
<i><span style="color:#9A1900">; Store local variables </span></i>
<b><span style="color:#0000FF">push</span></b> rbx <i><span style="color:#9A1900">; int i</span></i>
<b><span style="color:#0000FF">push</span></b> r<span style="color:#993399">12</span> <i><span style="color:#9A1900">; int j</span></i>
<b><span style="color:#0000FF">push</span></b> r<span style="color:#993399">13</span> <i><span style="color:#9A1900">; int k</span></i>
<b><span style="color:#0000FF">push</span></b> r<span style="color:#993399">14</span> <i><span style="color:#9A1900">; int n1</span></i>
<b><span style="color:#0000FF">push</span></b> r<span style="color:#993399">15</span> <i><span style="color:#9A1900">; int n2</span></i>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">14</span><span style="color:#990000">,</span> rdx <i><span style="color:#9A1900">; n1 = mid - left + 1</span></i>
<b><span style="color:#0000FF">sub</span></b> r<span style="color:#993399">14</span><span style="color:#990000">,</span> rsi
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">14</span>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">15</span><span style="color:#990000">,</span> rcx <i><span style="color:#9A1900">; n2 = right - mid </span></i>
<b><span style="color:#0000FF">sub</span></b> r<span style="color:#993399">15</span><span style="color:#990000">,</span> rdx
<b><span style="color:#0000FF">lea</span></b> r<span style="color:#993399">11</span><span style="color:#990000">,</span> <span style="color:#990000">[</span>r<span style="color:#993399">14</span><span style="color:#990000">+</span>r<span style="color:#993399">15</span><span style="color:#990000">]</span> <i><span style="color:#9A1900">; r11 = rsp offset = 4(n1 + n2)</span></i>
<b><span style="color:#0000FF">lea</span></b> r<span style="color:#993399">11</span><span style="color:#990000">,</span> <span style="color:#990000">[</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">11</span><span style="color:#990000">]</span>
<b><span style="color:#0000FF">sub</span></b> rsp<span style="color:#990000">,</span> r<span style="color:#993399">11</span> <i><span style="color:#9A1900">; allocate space for temp arrays</span></i>
<b><span style="color:#0000FF">mov</span></b> rbx<span style="color:#990000">,</span> <span style="color:#993399">0</span> <i><span style="color:#9A1900">; i = 0</span></i>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">12</span><span style="color:#990000">,</span> <span style="color:#993399">0</span> <i><span style="color:#9A1900">; j = 0</span></i>
<i><span style="color:#9A1900">; Copy elements of arr[] into L[] </span></i>
<b><span style="color:#000080">copyLloop:</span></b>
<b><span style="color:#0000FF">cmp</span></b> rbx<span style="color:#990000">,</span> r<span style="color:#993399">14</span> <i><span style="color:#9A1900">; is i >= n1?</span></i>
<b><span style="color:#0000FF">jge</span></b> copyRloop
<i><span style="color:#9A1900">; L[i] = arr[left + i]</span></i>
<b><span style="color:#0000FF">lea</span></b> r<span style="color:#993399">10</span><span style="color:#990000">,</span> <span style="color:#990000">[</span>rsi<span style="color:#990000">+</span>rbx<span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">10</span>d<span style="color:#990000">,</span> DWORD <span style="color:#990000">[</span>rdi<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">10</span><span style="color:#990000">]</span> <i><span style="color:#9A1900">; r10 = arr[left + i]</span></i>
<b><span style="color:#0000FF">mov</span></b> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>rbx<span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; L[i] = r10</span></i>
<b><span style="color:#0000FF">inc</span></b> rbx <i><span style="color:#9A1900">; i++</span></i>
<b><span style="color:#0000FF">jmp</span></b> copyLloop
<i><span style="color:#9A1900">; Copy elements of arr[] into R[]</span></i>
<b><span style="color:#000080">copyRloop:</span></b>
<b><span style="color:#0000FF">cmp</span></b> r<span style="color:#993399">12</span><span style="color:#990000">,</span> r<span style="color:#993399">15</span> <i><span style="color:#9A1900">; is j >= n2?</span></i>
<b><span style="color:#0000FF">jge</span></b> endcopyR
<i><span style="color:#9A1900">; R[j] = arr[mid + 1 + j]</span></i>
<b><span style="color:#0000FF">lea</span></b> r<span style="color:#993399">10</span><span style="color:#990000">,</span> <span style="color:#990000">[</span>rdx<span style="color:#990000">+</span>r<span style="color:#993399">12</span><span style="color:#990000">+</span><span style="color:#993399">1</span><span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">10</span>d<span style="color:#990000">,</span> DWORD <span style="color:#990000">[</span>rdi<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">10</span><span style="color:#990000">]</span> <i><span style="color:#9A1900">; r10 = arr[mid + 1 + j]</span></i>
<b><span style="color:#0000FF">lea</span></b> rax<span style="color:#990000">,</span> <span style="color:#990000">[</span>r<span style="color:#993399">12</span><span style="color:#990000">+</span>r<span style="color:#993399">14</span><span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>rax<span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; R[j] = r10</span></i>
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">12</span> <i><span style="color:#9A1900">; j++</span></i>
<b><span style="color:#0000FF">jmp</span></b> copyRloop
<b><span style="color:#000080">endcopyR:</span></b>
<b><span style="color:#0000FF">mov</span></b> rbx<span style="color:#990000">,</span> <span style="color:#993399">0</span> <i><span style="color:#9A1900">; i = 0</span></i>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">12</span><span style="color:#990000">,</span> <span style="color:#993399">0</span> <i><span style="color:#9A1900">; j = 0</span></i>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">13</span><span style="color:#990000">,</span> rsi <i><span style="color:#9A1900">; k = left</span></i>
<i><span style="color:#9A1900">; Merge L[] and R[] into arr[]</span></i>
<b><span style="color:#000080">mergeLoop:</span></b>
<b><span style="color:#0000FF">cmp</span></b> rbx<span style="color:#990000">,</span> r<span style="color:#993399">14</span> <i><span style="color:#9A1900">; is i >= n1 or j >= n2?</span></i>
<b><span style="color:#0000FF">jge</span></b> loopL
<b><span style="color:#0000FF">cmp</span></b> r<span style="color:#993399">12</span><span style="color:#990000">,</span> r<span style="color:#993399">15</span>
<b><span style="color:#0000FF">jge</span></b> loopL
<b><span style="color:#0000FF">lea</span></b> r<span style="color:#993399">10</span><span style="color:#990000">,</span> <span style="color:#990000">[</span>r<span style="color:#993399">12</span><span style="color:#990000">+</span>r<span style="color:#993399">14</span><span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">10</span>d<span style="color:#990000">,</span> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">10</span><span style="color:#990000">]</span> <i><span style="color:#9A1900">; r10d = R[j]</span></i>
<b><span style="color:#0000FF">cmp</span></b> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>rbx<span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; is L[i] <= R[j]?</span></i>
<b><span style="color:#0000FF">jle</span></b> if
<b><span style="color:#0000FF">mov</span></b> DWORD <span style="color:#990000">[</span>rdi<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">13</span><span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; arr[k] = R[j]</span></i>
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">12</span> <i><span style="color:#9A1900">; j++</span></i>
<b><span style="color:#0000FF">jmp</span></b> endif
<b><span style="color:#000080">if:</span></b>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">10</span>d<span style="color:#990000">,</span> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>rbx<span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> DWORD <span style="color:#990000">[</span>rdi<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">13</span><span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; arr[k] = L[i] </span></i>
<b><span style="color:#0000FF">inc</span></b> rbx <i><span style="color:#9A1900">; i++</span></i>
<b><span style="color:#000080">endif:</span></b>
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">13</span> <i><span style="color:#9A1900">; k++ </span></i>
<b><span style="color:#0000FF">jmp</span></b> mergeLoop
<i><span style="color:#9A1900">; Copy elements of L[] into arr[]</span></i>
<b><span style="color:#000080">loopL:</span></b>
<b><span style="color:#0000FF">cmp</span></b> rbx<span style="color:#990000">,</span> r<span style="color:#993399">14</span> <i><span style="color:#9A1900">; is i >= n1?</span></i>
<b><span style="color:#0000FF">jge</span></b> loopR
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">10</span>d<span style="color:#990000">,</span> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>rbx<span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> DWORD <span style="color:#990000">[</span>rdi<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">13</span><span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; arr[k] = L[i]</span></i>
<b><span style="color:#0000FF">inc</span></b> rbx <i><span style="color:#9A1900">; i++</span></i>
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">13</span> <i><span style="color:#9A1900">; k++</span></i>
<b><span style="color:#0000FF">jmp</span></b> loopL
<i><span style="color:#9A1900">; Copy elements of R[] into arr[]</span></i>
<b><span style="color:#000080">loopR:</span></b>
<b><span style="color:#0000FF">cmp</span></b> r<span style="color:#993399">12</span><span style="color:#990000">,</span> r<span style="color:#993399">15</span> <i><span style="color:#9A1900">; is j >= n2?</span></i>
<b><span style="color:#0000FF">jge</span></b> endR
<b><span style="color:#0000FF">lea</span></b> r<span style="color:#993399">10</span><span style="color:#990000">,</span> <span style="color:#990000">[</span>r<span style="color:#993399">12</span><span style="color:#990000">+</span>r<span style="color:#993399">14</span><span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> r<span style="color:#993399">10</span>d<span style="color:#990000">,</span> DWORD <span style="color:#990000">[</span>rsp<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">10</span><span style="color:#990000">]</span>
<b><span style="color:#0000FF">mov</span></b> DWORD <span style="color:#990000">[</span>rdi<span style="color:#990000">+</span><span style="color:#993399">4</span><span style="color:#990000">*</span>r<span style="color:#993399">13</span><span style="color:#990000">],</span> r<span style="color:#993399">10</span>d <i><span style="color:#9A1900">; arr[k] = R[j]</span></i>
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">12</span> <i><span style="color:#9A1900">; j++</span></i>
<b><span style="color:#0000FF">inc</span></b> r<span style="color:#993399">13</span> <i><span style="color:#9A1900">; k++</span></i>
<b><span style="color:#0000FF">jmp</span></b> loopR
<b><span style="color:#000080">endR:</span></b>
<i><span style="color:#9A1900">; deallocate temp arrays</span></i>
<i><span style="color:#9A1900">; restore callee-save registers</span></i>
<b><span style="color:#0000FF">add</span></b> rsp<span style="color:#990000">,</span> r<span style="color:#993399">11</span>
<b><span style="color:#0000FF">pop</span></b> r<span style="color:#993399">15</span>
<b><span style="color:#0000FF">pop</span></b> r<span style="color:#993399">14</span>
<b><span style="color:#0000FF">pop</span></b> r<span style="color:#993399">13</span>
<b><span style="color:#0000FF">pop</span></b> r<span style="color:#993399">12</span>
<b><span style="color:#0000FF">pop</span></b> rbx
<b><span style="color:#0000FF">ret</span></b>
</pre>
</body>
</html>