forked from uva-cs/pdr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
167 lines (166 loc) · 17.8 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
<!DOCTYPE html>
<html>
<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 type="text/css">code{white-space: pre;}</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 both be positive, so you need not consider negative numbers or zero. 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 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>