-
Notifications
You must be signed in to change notification settings - Fork 485
/
index.html
366 lines (365 loc) · 18.2 KB
/
index.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>PDR: Laboratory 8: x86 Assembly Language, part 1 (64 bit)</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="pdr-laboratory-8-x86-assembly-language-part-1-64-bit">PDR:
Laboratory 8: x86 Assembly Language, part 1 (64 bit)</h1>
<p><a href="../index.html">Go up to the Labs table of contents
page</a></p>
<h3 id="objective">Objective</h3>
<p>This lab is one of two labs meant to familiarize you with the process
of writing, assembling, and linking assembly language code. The purposes
of the in-lab and post-lab activities are to investigate how various C++
language features are implemented at the assembly level.</p>
<p>There are both <a href="../lab08-32bit/index.html">32 bit</a> (<a
href="../lab08-32bit/index.md">md</a>) and <a
href="../lab08-64bit/index.html">64 bit</a> (<a
href="../lab08-64bit/index.md">md</a>) versions of this lab. This is the
<strong><em>64 bit version</em></strong>.</p>
<h3 id="background">Background</h3>
<p>The Intel x86 assembly language is currently one of the most popular
assembly languages and runs on many architectures from the x86 line
through the Pentium 4. It is a <a
href="http://en.wikipedia.org/wiki/Complex_instruction_set_computing">CISC</a>
instruction set that has been extended multiple times (e.g. <a
href="http://en.wikipedia.org/wiki/MMX_%28instruction_set%29">MMX</a>)
into a larger instruction set. In 2004 it was extended to allow for a 64
bit memory space.</p>
<h3 id="tutorial">Tutorial</h3>
<p>The tutorial for this lab is the following two readings on <a
href="../../book/x86-64bit-asm-chapter.pdf">x86</a> and the <a
href="../../book/x86-64bit-ccc-chapter.pdf">C Calling
convention</a>.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<ol type="1">
<li>Read the <a href="../../slides/08-assembly-64bit.html">slides on 64
bit x86</a></li>
<li>The x86 book chapters on <a
href="../../book/x86-64bit-asm-chapter.pdf">x86</a> and the <a
href="../../book/x86-64bit-ccc-chapter.pdf">C calling
convention</a></li>
<li>The <a href="https://www.youtube.com/watch?v=XbZQ-EonR_I">x86 Call
Stack</a> introduction from the University of Washington</li>
<li>An optional online reading is <a
href="https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf">x86-64
Machine-Level Programming</a> from CMU, although they use the other
assembly language format</li>
<li>An optional <a
href="https://medium.com/@connorstack/a-guide-to-x86-calling-convention-824a3236ed65">Medium
article</a> stepping through the calling convention once again.</li>
</ol>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Understand how to compile x86 assembly code</li>
<li>Review the sample <code>vecsum.s</code> program</li>
<li>Write a program in x86, <code>mathlib.s</code>, to compute the
product of two numbers and power of two numbers</li>
<li>Create a C++ program, <code>mathfun.cpp</code>, to call the
functions in <code>mathlib.s</code></li>
<li>Ensure your code compiles on a x64 Linux machine</li>
<li>Files to download <a href="vecsum.s.html">vecsum.s</a> (<a
href="vecsum.s">src</a>), <a href="main.cpp.html">main.cpp</a> (<a
href="main.cpp">src</a>), <a href="Makefile.html">Makefile</a> (<a
href="Makefile">src</a>)</li>
<li>Files to submit mathlib.s, mathfun.cpp, Makefile</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol start="2" type="1">
<li>Write an x86 function to perform merge sort</li>
<li>Files to download: <a href="mergeSort.s.html">mergeSort.s</a> (<a
href="mergeSort.s">src</a>), <a
href="testMergeSort.cpp.html">testMergeSort.cpp</a> (<a
href="testMergeSort.cpp">src</a>)</li>
<li>Files to submit: mergeSort.s, testMergeSort.cpp, Makefile</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol type="1">
<li>Write an x86 function to perform a linear search</li>
<li>Files to download: <a
href="testLinearSearch.cpp.html">testLinearSearch.cpp</a> (<a
href="testLinearSearch.cpp">src</a>)</li>
<li>Files to submit: testLinearSearch.cpp, linearSearch.s</li>
</ol>
<hr />
<h2 id="platform-architectures">Platform Architectures</h2>
<p>There are a few differences when writing x86 assembly code, depending
on whether you are using Linux or macOS. Specifically, the object file
format for nasm will differ, as well as the subroutine name itself. The
instructions in this lab will assume the use of Linux – if you are using
macOS, use the table below for the correct instructions.</p>
<table>
<thead>
<tr class="header">
<th>Platform</th>
<th>nasm flag</th>
<th>x86 subroutine name</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>64-bit Linux</td>
<td>-f elf64</td>
<td><code>vecsum</code></td>
</tr>
<tr class="even">
<td>64 bit macOS</td>
<td>-f macho64</td>
<td><code>_vecsum</code></td>
</tr>
</tbody>
</table>
<p>Some additional notes:</p>
<ul>
<li>The subroutine name must be changed everywhere it appears in the
assembly file, including in <code>global</code></li>
<li>On Linux, you may need to install the <code>g++-multilib</code>
command for compilation to succeed</li>
</ul>
<p><strong>IMPORTANT:</strong> When you submit your code, it
<strong>MUST</strong> be in 64-bit Linux format.</p>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<h3 id="compiling-assembly-with-c">Compiling Assembly With C++</h3>
<p>For this part, you will need to download three files: <a
href="vecsum.s.html">vecsum.s</a> (<a href="vecsum.s">src</a>), <a
href="main.cpp.html">main.cpp</a> (<a href="main.cpp">src</a>), and <a
href="Makefile.html">Makefile</a> (<a href="Makefile">src</a>).</p>
<p>To compile a program written partly in x86 assembly and partly in
C++, we have to build the program in parts. We build the C++ file as we
have in the past:</p>
<pre><code>clang++ -Wall -g -c main.cpp
</code></pre>
<p>Note that we used the -c flag, which tells the compiler to compile
but not link the program. Linking it will create the final executable –
but as there is not a <code>vecsum()</code> function defined (yet), the
compiler will report an error stating that it does not know what the
vecsum() function is. We also added a few more flags (<code>-Wall
-g</code>) to print all warnings and compile debugging symbols into the
program.</p>
<p>Next, we need to compile the assembly file. To do this, we enter the
following:</p>
<pre><code>nasm -f elf64 -g vecsum.s</code></pre>
<p>This invokes <code>nasm</code>, which is the assembler that we are
using for this course. <code>-f elf64</code> tells nasm to output the
object file using the ELF 64-bit format, which is specific to Linux (and
would need to be changed to <code>-f macho64</code> for macOS as
detailed above). We also tell it to include debugging symbols via
<code>-g</code>. The assembly file name is specified by the
<code>vecsum.s</code> at the end of the command line.</p>
<p>Finally, we have to link the two files into the final executable. We
do this as before:</p>
<pre><code>clang++ -Wall -g vecsum.o main.o</code></pre>
<p>This tells clang++ to link both of the .o files created above into an
executable, which it called <code>a.out</code>. There isn’t any
compiling done at this stage – this just links the two object files into
the final executable.</p>
<h3 id="vecsum">Vecsum</h3>
<p>Examine the vecsum subroutine in <a href="vecsum.s.html">vecsum.s</a>
(<a href="vecsum.s">src</a>). Use the slides and readings to help
understand what is happening in vecsum.s. Make sure you understand the
prologue and epilogue implementation, as well as the instructions used
in the subroutine.</p>
<p>Compile and run the vecsum program:</p>
<ul>
<li>Use the tutorial as a guide, but see the instructions above.</li>
<li>If you forget the lldb commands described below, see the <a
href="../../docs/lldb_summary.html">LLDB command summary</a>, which has
a summary of all of these commands.</li>
<li>You can find the assembly and C++ source code in the repository (<a
href="vecsum.s.html">vecsum.s</a> (<a href="vecsum.s">src</a>), <a
href="main.cpp.html">main.cpp</a> (<a href="main.cpp">src</a>), <a
href="Makefile.html">Makefile</a> (<a href="Makefile">src</a>)). For the
C++ code compilation (i.e. main.cpp) and the final link, use the
<code>-g</code> flag, which allows the program to work well with the
lldb debugger.</li>
<li>Use the debugger to step through the assembly code, view the
register contents, and view the computer’s memory.</li>
<li>Set a breakpoint at the line in the main.cpp where the vecsum()
function is called (probably line 38).</li>
<li>Normally, you would use the <code>step</code> function to step into
the next instruction. However, since no debugging information was
included with the assembler (a shortcoming of nasm), we can’t use
<code>step</code> – it will just move to the next C++ instruction (the
<code>cout</code>). Instead, we will use <code>stepi</code>, which will
step exactly one <em>assembly instruction</em>, which is what we
want.</li>
<li>To display the assembly code that is currently being executed, enter
<code>disassemble</code>. This is just like <code>list</code>, but it
displays the assembly code instead of the C++ code.</li>
<li>Note that this prints things in a different assembly format. To set
the format to the style we are used to (and the style we are programming
in with nasm), enter <code>settings set target.x86-disassembly-flavor
intel</code>. Now enter <code>disassemble</code> again – the format
should look more familiar. You only have to enter that set command once
(unless you exit and re-enter lldb).</li>
<li>To see the vecsum function, enter <code>disassemble --name
vecsum</code>. Note that this only lists the first third (or so) of the
routine – up until the <code>start</code> label. To see the rest of the
code, enter <code>disassemble --name start</code>, <code>disassemble
--name done</code>, etc.</li>
<li>To show the contents of the registers, use the <code>register
read</code> command.</li>
</ul>
<h3 id="pre-lab-program-mathlib.s">Pre-lab program: mathlib.s</h3>
<p>You will need to write two routines in assembly, one that computes
the product of two numbers, and one that computes the power of two
numbers.</p>
<p>The first subroutine will compute the product of the two integer
parameters passed in. The restrictions are that it <strong>can only use
addition</strong>, and thus cannot use a multiplication operation. We
will assume that both of the parameters are positive integers. It must
compute this <strong>iteratively</strong>, not recursively. The
resulting product is then returned to the calling routine. This
subroutine should be called <code>product</code>. We will assume that
values will not be provided to the subroutine that will cause an
overflow, nor will negative (or zero) parameters be passed in.</p>
<p>The second subroutine will compute the power of the two integer
parameters passed in. We will assume that the first parameter is the
base, and the second parameter is the exponent. Again, both are
integers. The restrictions on this routine are that it <strong>can only
use the multiplication</strong> routine described above – it cannot use
<code>imul</code> or call any exponentiation routine. Furthermore, it
must be defined <strong>recursively</strong>, not iteratively. This
routine should be called <code>power</code>.</p>
<p>You can assume that the numbers passed into both routines will be
non-negative. Furthermore, as described above, no values will be used on
your program that could cause an integer overflow.</p>
<p>Both of these routines should be in a file called mathlib.s, and must
use the proper C-style calling convention. You must also provide a
mathfun.cpp file, which calls both of your subroutines – see the
main.cpp file provided as a template. The program should take in ONLY
two integers (we’ll call them <em>x</em> and <em>y</em>). It should then
print out the output of calling <code>product(x,y)</code> and
<code>power(x,y)</code>. Thus, if the input is 3 and 4, it would print
out 12 and 81.</p>
<p>Input is to be read via standard input (i.e., <code>cin</code>), not
through command-line parameters.</p>
<p>In order for routines in an assembly file to be callable from C/C++,
you need to declare them with <code>global</code>, like is done in
<code>vecsum.s</code>. To have multiple routines in a single assembly
file (as is needed for mathlib.s), you should have multiple
<code>global</code> lines, one for each subroutine that you plan on
calling from your C/C++ code.</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>Enter integer 1: 3
Enter integer 2: 2
Product: 6
Power: 9</code></pre>
<p>Once you have completed the pre-lab, submit mathlib.s, mathfun.cpp,
and your Makefile</p>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<p>Come to lab with a functioning version of the pre-lab, and be
prepared to demonstrate that you understand how to build and run the
pre-lab programs. If you are unsure about any part of the pre-lab, talk
to a TA. You should be able to explain and write recursive functions in
assembly for the exams in this course, so make sure that you understand
how to implement the pre-lab program.</p>
<p>Before starting the in-lab, make sure you read and understand the
book chapters on the C calling convention. For the in-lab, you will be
implementing merge sort in x86 assembly. We have provided the helper
function <code>merge</code> in mergeSort.s. Note: <code>merge</code>
makes use of two caller-saved registers, r10 and r11. <strong>Remember
to save and restore these registers</strong> before and after calling
<code>merge</code>.</p>
<p>Download <a href="mergeSort.s.html">mergeSort.s</a> (<a
href="mergeSort.s">src</a>), as well as <a
href="testMergeSort.cpp.html">testMergeSort.cpp</a> (<a
href="testMergeSort.cpp">src</a>), which you will use to test your code.
Make sure you do not alter testMergeSort.cpp, as you must include the
original file in your submission.</p>
<p>Your task for the in-lab is to implement the <code>mergeSort</code>
function in mergeSort.s. This function takes in three parameters. The
first parameter is a pointer to an int array. The second parameter is an
integer corresponding to the left index in the array. The third
parameter is an integer corresponding to the right index in the array.
The return type of this function is void, and it modifies the original
array. You may assume the size of the array is nonzero. When testing
your function using testMergeSort.cpp, input will be read via standard
input, not through command-line parameters. After entering the array
size, you will be prompted to enter each element one by one. This test
file will call your <code>mergeSort</code> function on the array, and
print the result. Make sure you test your function on arrays of various
sizes.</p>
<h3 id="sample-execution-run-1">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>Enter the array size: 5
Enter value 0: -7
Enter value 1: 2
Enter value 2: -39
Enter value 3: 12
Enter value 4: 8
Unsorted array: -7 2 -39 12 8
Sorted array: -39 -7 2 8 12</code></pre>
<p>The following resource explains the merge sort algorithm. This is
what you need to implement in x86 assembly: <a
href="https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/">www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/</a></p>
<p>Once you have completed the in-lab, submit mergeSort.s,
testMergeSort.cpp, and your Makefile.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<p>Download <a href="testLinearSearch.cpp.html">testLinearSearch.cpp</a>
(<a href="testLinearSearch.cpp">src</a>), which you will use to test
your code. Make sure you do not alter testLinearSearch.cpp, as you must
include the original file in your submission.</p>
<p>Your task for the post-lab is to implement the
<code>linearSearch</code> function in assembly. This function will scan
through an array from left to right iteratively until it finds the
target element or reaches the end of the array. The function takes in
three parameters. The first parameter is a pointer to an int array. The
second parameter is an integer representing the size of the array. The
third parameter is an integer representing the target element to find in
the array. The return type of this fuction is int, and will be the index
into the array that the target was found, or -1 if it wasn’t. Just like
with the <code>testMergeSort</code> program in the in-lab,
<code>testLinearSearch</code> will take input from std and pass it on to
your <code>linearSearch</code> routine. Make sure you test your function
on various sized arrays, both sorted and unsorted.</p>
<h3 id="sample-execution-run-2">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>Enter the array size: 5
Enter value 0: -7
Enter value 1: 2
Enter value 2: -39
Enter value 3: 12
Enter value 4: 8
Enter target to search for: 2
Found 2 at index 1</code></pre>
<p>Once you have completed the in-lab, submit linearSearch.s,
testLinearSearch.cpp, and your Makefile</p>
<h3 id="hints">Hints</h3>
<h4 id="accessing-array-elements-in-assembly">Accessing Array Elements
in Assembly</h4>
<p>Recall that C++ arrays are stored contiguously in memory. This means
that if you know the start address of the array <code>&a</code>, and
the size of the elements that are being stored, you can find the address
of an element at any index <code>i</code> with <code>&a[i] = &a
+ <size_of_elements>*i</code> (if the array is one-dimensional).
Use this fact along with <a
href="../slides/08-assembly-64bit.html#/3/8">the memory addressing
slide</a> from lecture to access array elements in assembly.</p>
</body>
</html>