Go up to the Labs table of contents page
To become familiar with programming with IBCM and understand how high-level language programs are represented at the machine level.
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.
The tutorial for this lab is the remainder of the Wikibooks article on Bash Shell Scripting. The tutorial will be necessary for the post-lab, though you may read through it earlier if you’d like.
averagetime.sh shell script by adding
control structuresFor 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.
Write an IBCM program that:
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.
# input
1
2
3
-1
-2
3
# output
0006
0000
ffff
fffe
0003Write another IBCM program that reads in an array and prints its elements forwards and backwards. Your program will first be given the array size n as input. The next n lines of input will contain the contents of the array.
You MUST iterate through the array by creating the array load instruction, similarly as was done in lecture in the array-ssummation.ibcm program. You may NOT have a series of separate instructions to each load a separate value from the array – such a program will receive zero credit.
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.
# 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
0001You MUST 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:
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.
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.
You may run your IBCM code via the online simulator at https://andromeda.cs.virginia.edu/ibcm/.
Beware of the following quirks of the simulator:
Submit addition.ibcm and array.ibcm with comments explaining your code. Your files MUST be called addition.ibcm and array.ibcm exactly.
Sprinkle some nop (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.
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.
How do you add variables in IBCM? Why, with the add
instruction, of course.
However, for arrays, the address you want to add from
changes every time! How do we account for that?
We need to dynamically change the add 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
store that later on in our program to execute
automatically!
Thus, if we wanted to sum an array, we would:
5000 – notice how it’s just an
add instruction without an address. This is
adit in the slides.add instructions to add the base array
address a and the current array index i to the
accumulator
5xyz,
where xyz is the location of a[i] in your
program.add
instruction!5xyz to add the value of
a[i] to the sum. This is doit in the
slides.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.
For the postlab, you will be writing an IBCM program that prints itself. This type of program is known as a quine.
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.
Wikipedia has a good article about quines, including examples in a few programming languages. The smallest C/C++ quine is described here for your enjoyment.
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.
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.
You may NOT submit a zero line quine! Even though this is technically valid, it will not earn credit for this lab.
We will test your program by running it, recording the output, and running that output as a program. You should do the same.
The tutorial for this lab is the remainder of the Wikibooks article on Bash Shell Scripting.
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.
First, download the counter.cpp (src), timer.cpp (src), and timer.h (src) 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 e and runs through an idle loop
10e times. You should not enter a value for
e greater than 9, as 109 (1 billion) is the largest
power of 10 that an int value can hold. On a modern
computer, entering 9 as the parameter should take between 1 and 5
seconds to run.
Do not compile your program with -O2, as clang++ is
smart enough to recognize that your for loop is not doing any work and
will remove it from the optimized binary!
Your averagetime.sh shell script should take in the
number of iterations as a single input value (not as a command line
parameter). If that input is quit, 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. You
MUST call your executable program a.out in your shell
script.
Your shell script MUST have an if
statement (to see if it should exit), and MUST have a
for or while loop. The number of times to
iterate through the for or while loop
(initially set to 5) should be a variable set previously in the
script.
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.
averagetime.sh, and
should have #!/bin/bash as the very first line of the
script$(( ...
))), there SHOULD be spaces around the
arithmetic operators as well as an equals sign within the
parentheses.for loop requires a do keyword before
the for loop body; likewise, an if statement has a
then before the body. Either these words must be on the
next line, or a semi-colon must be there before the do or
then./averagetime.sh. If your computer denies you permission,
remind it who’s boss and put it in its place with chmod +x
averagetime.sh. This tells your Unix system that averagetime.sh
is a program that can be executed (remember chmod?).Below is the output when we wrote this shell script. Obviously, your times may vary.
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 msThe most important thing to remember is that there is no distinction between instructions and variables in IBCM!
What is one way you can figure out what instructions your program
contains?
Hint: You know how to iterate through arrays; is there any way you could
apply that concept here?
If you want to compare values in an if or while expression (such as
the bash equivalent of while (i < s)), you should see here. In
particular, you need to use -lt for the less than operator,
and square brackets instead of the parentheses.
Download and look at the bubblesort.cpp (src) algorithm. You will need to read in 10 array elements and sort them with this algorithm in IBCM.
To encode this program, follow these steps:
The file should be called bubblesort.ibcm. As with the last assignment, you MUST comment your code.
NOTE: 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.
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.
# 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