forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
Copy pathindex.html
419 lines (419 loc) · 18.3 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
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
<!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 7: IBCM Programming</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-7-ibcm-programming">PDR: Laboratory 7: IBCM
Programming</h1>
<p><a href="../index.html">Go up to the Labs table of contents
page</a></p>
<h3 id="objective">Objective</h3>
<p>To become familiar with programming with IBCM and understand how
high-level language programs are represented at the machine level.</p>
<h3 id="background">Background</h3>
<p>IBCM (Itty Bitty Computing Machine) is a simulated computer with a
minimal instruction set. Despite its tiny instruction set, IBCM can
compute anything that a modern computer can.</p>
<h3 id="tutorial">Tutorial</h3>
<p>The tutorial for this lab is the remainder of the <a
href="https://en.wikibooks.org/wiki/Bash_Shell_Scripting">Wikibooks
article on Bash Shell Scripting</a>. The tutorial will be necessary for
the post-lab, though you may read through it earlier if you’d like.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<ol type="1">
<li>Read the <a href="../../slides/07-ibcm.html">slides on IBCM</a></li>
<li>Read <a href="../../book/ibcm-chapter.pdf">IBCM book chapter</a>
(PDF), especially sections 1.6 (Writing IBCM Programs) and 1.7 (Example
Programs)</li>
<li>Run IBCM code online <a
href="https://andromeda.cs.virginia.edu/ibcm/">here</a>. The sample code
in the book chapter is also in the repo: <a
href="../../ibcm/summation.ibcm">summation.ibcm</a> and <a
href="../../ibcm/array-summation.ibcm">array-summation.ibcm</a></li>
</ol>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Write two IBCM programs to familiarize yourself with IBCM</li>
<li>Files to download: None</li>
<li>Files to submit: addition.ibcm, array.ibcm</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol type="1">
<li>Implement a quine in IBCM</li>
<li>Improve your <code>averagetime.sh</code> shell script by adding
control structures</li>
<li>Files to download: <a href="counter.cpp.html">counter.cpp</a> (<a
href="counter.cpp">src</a>), <a href="timer.cpp.html">timer.cpp</a> (<a
href="timer.cpp">src</a>), <a href="timer.h.html">timer.h</a> (<a
href="timer.h">src</a>)</li>
<li>Files to submit: quine.ibcm, averagetime.sh</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol type="1">
<li>Implement bubble sort in IBCM</li>
<li>Files to download: <a href="bubblesort.cpp.html">bubblesort.cpp</a>
(<a href="bubblesort.cpp">src</a>)</li>
<li>Files to submit: bubblesort.ibcm</li>
</ol>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<p>For the pre-lab, you will need to write two IBCM programs. The
programs will need to have an .ibcm extension when submitting, but they
are text files, so you can still edit them in Emacs.</p>
<h3 id="addition.ibcm">addition.ibcm</h3>
<p>Write an IBCM program that:</p>
<ul>
<li>Gets three values from user input</li>
<li>Stores the values into three variables</li>
<li>Adds the variables together, and prints the sum (you may use
additional memory if you wish)</li>
<li>If the sum is zero, prints the three values and stops</li>
<li>If the sum is not zero, starts over (tries to get three values,
etc.)</li>
</ul>
<h3 id="sample-addition.ibcm-run">Sample addition.ibcm Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for. The output shown is a result of running
addition.ibcm in the ibcm simulator.</p>
<pre><code># input
1
2
3
-1
-2
3
# output
0006
0000
ffff
fffe
0003</code></pre>
<h3 id="array.ibcm">array.ibcm</h3>
<p>Write another IBCM program that reads in an array and prints its
elements forwards and backwards. Your program will first be given the
<strong>array size</strong> <em>n</em> as input. The next <em>n</em>
lines of input will contain the contents of the array.</p>
<ul>
<li>The array base address is hard-coded into memory, meaning it’s a
pre-set value that isn’t obtained by user input. We will be inputting
arrays of many different sizes into your program, so make sure you
carefully choose where to store your array in memory.</li>
<li>Before your program halts, it should print out the array both
forwards and backwards.</li>
</ul>
<p>You <strong><em>MUST</em></strong> iterate through the array by
creating the array load instruction, similarly as was done in lecture in
the <a href="../../ibcm/array-summation.ibcm">array-ssummation.ibcm</a>
program. You may <strong><em>NOT</em></strong> have a series of separate
instructions to each load a separate value from the array – such a
program will receive zero credit.</p>
<h3 id="sample-array.ibcm-run">Sample array.ibcm Run</h3>
<p>Below is a sample execution run to show you the output we are looking
for. The output shown is a result of running array.ibcm in the ibcm
simulator.</p>
<pre><code># input
# First input is size of the array (3)
# Next inputs are the array contents (1,2,3)
3
1
2
3
# output
0001
0002
0003
0003
0002
0001</code></pre>
<h3 id="writing-ibcm-code">Writing IBCM Code</h3>
<p>You <strong>MUST</strong> comment your IBCM code copiously. This
means (practically) every line should have a comment describing what you
are doing. However, you cannot have a line that is only comments, as the
emulator will have trouble reading that line! The examples provided in
the handouts posted on the course website and discussed in class
illustrate a good way of doing this, where there are columns for each of
the following:</p>
<ol type="1">
<li>the hexadecimal values that will go into that memory location</li>
<li>the address of that memory location</li>
<li>labels for jumps or variable names</li>
<li>the operation-name for the instruction on that line</li>
<li>a symbolic name for the address the instruction references</li>
<li>comments (that explain what’s happening in a higher-level form)</li>
</ol>
<p>Note that together the operation name and the address are sort of an
assembly language version of the hexadecimal version of the operations
in the first column. You probably want to write those first, and then
turn these into the hex instruction that will go into column 1.</p>
<p>The simulator will only read the first 4 characters on each line of a
file. So you can’t have entire lines with comments, or blank lines. The
simulator can’t handle these (and doesn’t check for this), and you will
get a strange error.</p>
<h3 id="running-ibcm-code">Running IBCM Code</h3>
<p>You may run your IBCM code via the online simulator at <a
href="https://andromeda.cs.virginia.edu/ibcm/">https://andromeda.cs.virginia.edu/ibcm/</a>.</p>
<p>Beware of the following quirks of the simulator:</p>
<ul>
<li>If your code contains an infinite loop, the simulator will hang your
browser</li>
<li>The simulator will not work if there are blank lines at the end of
the file</li>
</ul>
<h3 id="submission">Submission</h3>
<p>Submit addition.ibcm and array.ibcm with comments explaining your
code. <strong>Your files MUST be called addition.ibcm and array.ibcm
exactly</strong>.</p>
<h3 id="hints">Hints</h3>
<h4 id="leave-room-for-mistakes">Leave room for mistakes</h4>
<p>Sprinkle some <code>nop</code> (opcode: B) instructions throughout
your program that can be replaced later in case you realize that you
need some extra variables or are missing some instructions.</p>
<h4 id="working-with-arrays">Working with arrays</h4>
<p>Arrays can be difficult to work with in IBCM given the extremely
limited instruction set. We’ll walk through the array summation example
again from the slides to point out some helpful concepts.</p>
<p>How do you add variables in IBCM? Why, with the <code>add</code>
instruction, of course.<br />
However, for arrays, the address you want to <code>add</code> from
changes every time! How do we account for that?</p>
<p>We need to dynamically change the <code>add</code> instruction before
executing it to make it point to the right address. If we can generate
the appropriate instruction based off of the starting address of the
array and the index we want (hint: look back to lab 4), we can then
<code>store</code> that later on in our program to execute
automatically!</p>
<p>Thus, if we wanted to sum an array, we would:</p>
<ol type="1">
<li>Create a variable set to <code>5000</code> – notice how it’s just an
<code>add</code> instruction without an address. This is
<code>adit</code> in the slides.</li>
<li>Load that instruction into the accumulator</li>
<li>Use actual <code>add</code> instructions to add the base array
address <code>a</code> and the current array index <code>i</code> to the
accumulator
<ul>
<li>The accumulator should now contain something like <code>5xyz</code>,
where <code>xyz</code> is the location of <code>a[i]</code> in your
program.</li>
<li>The accumulator now contains a valid <code>add</code>
instruction!</li>
</ul></li>
<li>Store that instruction in the line where step 6 would be
running</li>
<li>Load your accumulated sum</li>
<li>Whatever was here previously was overwritten by step 4, and so now
we execute the instruction <code>5xyz</code> to add the value of
<code>a[i]</code> to the sum. This is <code>doit</code> in the
slides.</li>
<li>Store the sum!</li>
<li>Repeat steps 2-7 until the end of the array</li>
</ol>
<p>While this deals specifically with the example in the slides, it will
hopefully clarify the general approach of iterating through arrays and
give you more insight into how to print them out.</p>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<h3 id="quines">Quines</h3>
<p>For the postlab, you will be writing an IBCM program that prints
itself. This type of program is known as a <em>quine</em>.</p>
<blockquote>
<p>quine: /kwi:n/ /n./ [from the name of the logician Willard van Orman
Quine, via Douglas Hofstadter] A program that generates a copy of its
own source text as its complete output. Devising the shortest possible
quine in some given programming language is a common hackish
amusement.</p>
</blockquote>
<p>Wikipedia has a good <a
href="https://en.wikipedia.org/wiki/Quine_%28computing%29">article about
quines</a>, including examples in a few programming languages. The
smallest C/C++ quine is described <a
href="https://www.ioccc.org/1994/smr.hint">here</a> for your
enjoyment.</p>
<p>While at first this idea may sound like a serious mind-bender, in
reality it is a rather short program that is not too tough to do in
IBCM. Your program will be carefully crafted to only print itself out
and will most likely contain very specific information such as a
variable that holds the length of the program.</p>
<p>The lines you print out may differ from the original file read into
the IBCM simulator in a couple of places; as long as your output is
still a valid quine that can be executed to output itself yet again, you
do not have to worry about those differences. It is possible to write
this program in as few as 8 lines of IBCM code, but most likely you will
have closer to 15-20 lines.</p>
<p>You may <strong><em>NOT</em></strong> submit a zero line quine! Even
though this is technically valid, it will not earn credit for this
lab.</p>
<p>We will test your program by running it, recording the output, and
running that output as a program. You should do the same.</p>
<h3 id="more-shell-scripting">More shell scripting</h3>
<p>The tutorial for this lab is the remainder of the <a
href="https://en.wikibooks.org/wiki/Bash_Shell_Scripting">Wikibooks
article on Bash Shell Scripting</a>.</p>
<p>For this lab, you will need to work a bit more on the shell script
that you wrote for the last lab. The shell script will also compute the
average running time for 5 executions of a program. The difference is
that you will be using control structures, such as conditionals
(if-then-else) and loops (for or while) in this shell script.</p>
<p>First, download the <a href="counter.cpp.html">counter.cpp</a> (<a
href="counter.cpp">src</a>), <a href="timer.cpp.html">timer.cpp</a> (<a
href="timer.cpp">src</a>), and <a href="timer.h.html">timer.h</a> (<a
href="timer.h">src</a>) files. The timer program has been modified from
lab 6 to print out the time in milliseconds. counter.cpp doesn’t
actually do anything useful; it just takes in a numeric command line
parameter <em>e</em> and runs through an idle loop
10<sup><em>e</em></sup> times. You should not enter a value for
<em>e</em> greater than 9, as 10<sup>9</sup> (1 billion) is the largest
power of 10 that an <code>int</code> value can hold. On a modern
computer, entering 9 as the parameter should take between 1 and 5
seconds to run.</p>
<p>Do not compile your program with <code>-O2</code>, as clang++ is
smart enough to recognize that your for loop is not doing any work and
will remove it from the optimized binary!</p>
<p>Your <code>averagetime.sh</code> shell script should take in the
number of iterations as a single input value (not as a command line
parameter). If that input is <code>quit</code>, then the script should
exit. Otherwise, execute the program a total of 5 times, printing and
keeping track of the execution time taken for each one. Your script
should then print the average time taken for each execution. <strong>You
MUST call your executable program <code>a.out</code> in your shell
script.</strong></p>
<p>Your shell script <strong>MUST</strong> have an <code>if</code>
statement (to see if it should exit), and <strong>MUST</strong> have a
<code>for</code> or <code>while</code> loop. The number of times to
iterate through the <code>for</code> or <code>while</code> loop
(initially set to 5) should be a variable set previously in the
script.</p>
<p>Below are a few notes to keep in mind when writing your shell script.
Bash is a very powerful language, but it can be rather finicky and
unforgiving with syntax.</p>
<ul>
<li>Your program should be called <code>averagetime.sh</code>, and
should have <code>#!/bin/bash</code> as the very first line of the
script</li>
<li>When setting variables, do <strong>NOT</strong> have spaces around
the equals sign</li>
<li>When adding up values (using arithmetic expansion <code>$(( ...
))</code>), there <strong>SHOULD</strong> be spaces around the
arithmetic operators as well as an equals sign within the
parentheses.</li>
<li>A <code>for</code> loop requires a <code>do</code> keyword before
the for loop body; likewise, an <code>if</code> statement has a
<code>then</code> before the body. Either these words must be on the
next line, or a semi-colon must be there before the <code>do</code> or
<code>then</code></li>
<li>To grab program output (such as the output of the binary program),
you use back quotes (i.e. `)</li>
<li>To execute your script, you can just enter
<code>./averagetime.sh</code>. If your computer denies you permission,
remind it who’s boss and put it in its place with <code>chmod +x
averagetime.sh</code>. This tells your Unix system that averagetime.sh
is a program that can be executed (remember chmod?).</li>
</ul>
<p>Below is the output when we wrote this shell script. Obviously, your
times may vary.</p>
<pre><code>enter the exponent for counter.cpp:
9
Running iteration 1...
time taken: 1256 ms
Running iteration 2...
time taken: 1232 ms
Running iteration 3...
time taken: 1238 ms
Running iteration 4...
time taken: 1240 ms
Running iteration 5...
time taken: 1256 ms
5 iterations took 6222 ms
Average time was 1244 ms</code></pre>
<h3 id="hints-1">Hints</h3>
<h4 id="thinking-about-the-quine-is-hurting-my-head">Thinking about the
quine is hurting my head :(</h4>
<p>The most important thing to remember is that there is no distinction
between instructions and variables in IBCM!</p>
<p>What is one way you can figure out what instructions your program
contains?<br />
Hint: You know how to iterate through arrays; is there any way you could
apply that concept here?</p>
<h4 id="comparing-values-in-bash">Comparing values in Bash</h4>
<p>If you want to compare values in an if or while expression (such as
the bash equivalent of <code>while (i < s)</code>), you should see <a
href="https://tldp.org/HOWTO/Bash-Prog-Intro-HOWTO-7.html">here</a>. In
particular, you need to use <code>-lt</code> for the less than operator,
and square brackets instead of the parentheses.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<h3 id="bubble-sort">Bubble sort</h3>
<p>Download and look at the <a
href="bubblesort.cpp.html">bubblesort.cpp</a> (<a
href="bubblesort.cpp">src</a>) algorithm. You will need to read in 10
array elements and sort them with this algorithm in IBCM.</p>
<p>To encode this program, follow these steps:</p>
<ol type="1">
<li>Write up high-level pseudo-code for your design on paper (make sure
that it is absolutely correct, or you will probably regret it
later)</li>
<li>Refine this pseudo-code, making it closer to the assembly code
level</li>
<li>Alter your code into IBCM assembly code with labels instead of
addresses</li>
<li>Run through a sufficient number of test cases by hand of your IBCM
code from step (3) to convince yourself that it is correct</li>
<li>Encode into actual hex IBCM code and addresses, and test it using
the simulator</li>
<li>Identify and fix the errors that you did not pick up in the previous
steps</li>
</ol>
<p>The file should be called bubblesort.ibcm. As with the last
assignment, you <em>MUST</em> comment your code.</p>
<p><strong>NOTE:</strong> Just like for the pre-lab array.ibcm file, you
must create an array load instruction. If your program has separate
instructions for loading separate values from the array, you will
receive zero credit for this in-lab.</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the output we are looking
for. The output shown is a result of running bubblesort.ibcm in the ibcm
simulator.</p>
<pre><code># input
# Note that we are NOT providing the array size as input
# because it always 10. Input is the 10 array elements unsorted.
2
3
4
8
1
5
9
0
6
7
# output
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009</code></pre>
</body>
</html>