Getting Started

Synopsis

  • Read the lab writeup on Canvas.
  • This lab is due on October 17, 2017 at 23:59:59.
  • This lab features two parts. Be sure to do both parts.

Requirements

  • MobaXTerm (Windows), Terminal (OS X & Linux)
  • Arduino Due
Note: I have written another guide for introducing you to the terminal: Introduction to the Terminal
Synopsis
This lab consists of two parts. The first part is a redux on your 102 final lab done without your Arduino. The second part is building a cache simulator on Arduino. Therefore, half of this lab requires Arduino, half of it doesn't. You will need to be comfortable with the command line in order to do the first part. Not really an incentive, but whenever you step into CS140, they will just expect you to know how to use the Terminal, so this is your chance to practice. Don't worry, there will be a guide posted for it, and I will also provide resources exclusively for this lab to ensure that you are able to do it even outside of the lab room.
The Terminal
For Computer Scientists looking to get a degree, you will be spending most of your time on the terminal from here on out. It may sound intimidating at first, but whenever you get the hang of it, it isn't bad at all. In fact, your productivity will increase as you get proficient with it.

I'm going to assume you're on Hydra or Tesla for the sake of this guide. So let's begin with opening terminal. You can easily just open "terminal" or press Alt+F2 on your machine and type in "gnome-terminal". You'll be staring at a screen of text. Welcome to the terminal.


Feel free to explore around and try out various commands. Here are a few that I recommend you to be familiar with:
Command Description Usage(s) Example
ls Lists files in current directory... or a directory specified ls
ls FOLDER_NAME
ls
cd Change Directory (literally).
You start out in your "~" directory (your home directory) and use "cd" to move to a different one.
cd FOLDER_NAME cd FOLDER
cd ../
mkdir Make Directory (literally).
This will allow you to make a folder.
mkdir FOLDER_NAME <-
rm Remove (literally)/Delete.
This will allow you to delete a file or a folder. If you try it on a folder, you must add "-r" as a parametre.
WARNING: Once you delete a file, it's gone. You're not getting it back.
rm FILE_NAME
rm -r FOLDER_NAME
<-
mv Move (literally).
This will allow you to move a file or a folder. It also serves to allow you to rename a file to another name.
mv OLD_NAME NEW_NAME <-
man Manual (literally).
Type this along with another command and (usually) a page will appear telling you how to use that command. It is, as the name implies, a manual page that is a quick resource for help. Press "q" to quit "man" when it's open.
man COMMAND_NAME man ls
man gcc
diff Difference (literally).
Will tell you the difference between two files. If there is no difference, nothing is printed out.
diff FILE1 FILE2 <-
nano Nano (literally) Text Editor.
Dr. Marz's preferred Terminal Text Editor. Commands are shown at the bottom of the screen (e.g. Ctrl+X = Exit).
nano FILE <-
vi/vim Vim (literally) Text Editor.
My preferred (and clearly superior) text editor. Vim is very powerful but it also takes some time to get used to compared to Nano. You'll use it in CS140 and CS302.
vi FILE
vim FILE
<-
gedit Gedit (literally) Text Editor.
This one actually isn't a terminal application. It will execute a graphical text editor kind of like TextEdit on Mac and Notepad on Windows. However, you can not use your terminal while Gedit is open.
vi FILE
vim FILE
<-
g++ A C++ Compiler.
You will be using this for pretty much your entire time here. It will make an executable from your C++ source code files.
g++ -o EXECUTABLE SOURCE g++ -o test test.cpp
ssh Secure Shell.
Allows you to remotely connect to other machines. i.e., connect to UTK's Hydra machines from your own personal computers.
ssh USERNAME@ADDRESS ssh cnguyen@hydra0.eecs.utk.edu

Demonstration

Here's a live demonstration of how to use the terminal. Here, I make a directory named "cs130", then a directory named "lab0" inside of it. Then inside of "lab0", I make 2 C++ programs named "test1.cpp" and "test2.cpp". I also show how to compile and run them in the Terminal.

"Well that's fine and all, but I think I'll just use CodeLite!"

Oh my, you're in for making your life much harder than it needs to be.

tl;dr: Don't do it.

Sure, you can use CodeLite for this lab I guess. But good luck doing that in the remaining labs where it's just ARM code. You can not use CodeLite for that. It's better to just get used to the terminal now so you don't have to worry about it later on while trying to do assembly labs. However, I'm not going to tell you what to do. I'll just let the assignments speak for themselves. :)

Also, there are a few issues that arise from CodeLite:
  1. You are coding in C++, yes. But you're coding in a "certain standard" of C++. The compiler you use for CodeLite is different. Therefore, some rules you learned in CS102 may not apply, and will result in your program not wanting to compile if you are not careful.
  2. You'd have to copy files back and forth constantly to run the program on Hydra/Tesla.
  3. Your program may work on your computer, but it may not on Hydra/Tesla. Just because something compiles on CodeLite, Visual Studio, or any other IDE does not mean it will compile on Hydra. In CS140, if it doesn't compile on Hydra, it's likely a 0 on your assignment. And the "it compiles on my machine!" argument won't work. I know it didn't for students whenever I took CS140.
  4. You're delaying the inevitable.
reinterpret_cast
reinterpret_cast may sound useless at first (and it probably is to casual programmers), but needless to say, I have found multiple uses of it in C++, and even in C (in its "old" form). reinterpret_cast isn't much of a cast as much as it is basically saying "Treat this set of bits as a different data type". Unlike static_cast, it completely skips any conversions. I showed this in lab, but let's compare 127 as a long long to 127 as a double in binary (aka static_casting from long long to double):

long long
0000000000000000000000000000000000000000000000000000000001111111 = 127
double
0100000001011111110000000000000000000000000000000000000000000000 = 127
So if we had to static_cast a long long to a double, the program will convert the data type so that it represents the same value in the other type. The Double type represents "127" differently in binary because it also has to handle decimals. You'll figure out how this is done later on in the semester. For now, just assume that it just works.

"Okay... so what about reinterpret_cast?"

Right. You saw how static_cast does a conversion above? reintepret_cast completely skips that. Behold:

long long
0000000000000000000000000000000000000000000000000000000001111111 = 127
double
0000000000000000000000000000000000000000000000000000000001111111 = 6.27463e-322
Yeah that value looks like garbage doesn't it? That's how it works. It just treats it as another data type.

"But Clara, how do I use it?"

Right, when you used static_cast, you likely did something like this:
int main() {
	long long var = 127;
	cout << static_cast<double>(var) << endl;
}
This will print out "127", as expected, however, the value was casted to a double prior to printing. Now let's try that with reinterpret_cast. You'll quickly find out that it fails...
int main() {
	long long var = 127;
	cout << reinterpret_cast<double>(var) << endl;
}
It'll give this error message whenever you try compiling it:
main.cpp: In function ‘int main()’:
main.cpp:8:39: error: invalid cast from type ‘long long int’ to type ‘double’
  cout << reinterpret_cast<double>(var) << endl;
What gives? It failed to compile with this message. The solution is simple (and it's another reason why you learned pointers). The C++ Standard only guarantees the following:

reinterpret_cast only guarantees that if you cast a pointer to a different type, and then reinterpret_cast it back to the original type, you get the original value.

Right... what does that mean? We need to perform reinterpret_cast on the pointer to the variable, not on the actual value itself.
int main() {
	long long var = 127;
	cout << *reinterpret_cast<double*>(&var) << endl;
	//      ^                       ^  ^
	//      |                       |  |
	//Notice these!
}
Sure enough... it worked and prints this out:
6.27463e-322
Think about what exactly is going on here. Think about what kind of conversions you are doing to prevent the bits from converting.
long long -> long long* -> double* -> double

1.) var                               //long long
2.) &var                              //long long*
3.) reinterpret_cast<double*>(&var)   //double*
4.) *reinterpret_cast<double*>(&var)  //double
You go from value, to pointer, then change the data type pointer (which does nothing), and then go back to that address and get the value back. It will just be "interpreted" as the other data type.

There is a shortcut if you use C-style casting, but it isn't guaranteed to work on all compilers:
*(double*)&var
Using reinterpret_cast on bytes
This is where things get interesting, and it is a very useful case of reinterpret_cast. Let's say I had a binary file with the following bytes:
00 FF 00 00
Notice: 0x0000FF00 (read it backwards) is 65280. We'll need this later.

So the binary file just has those 4 bytes. It is NOT text. It is literally bytes. Let's name it "data.bin".

Let's read this in to a C++ program into an array of chars... being size 4.
#include <iostream>
#include <fstream>

using namespace std;

int main() {
	unsigned char bytes[4];                     //Array to hold binary data.
	ifstream fp;
	fp.open("data.bin", ios::binary);           //Open the file in binary mode (not text mode).
	fp.read(reinterpret_cast<char*>(bytes), 4); //Read in 4 bytes into bytes.
	fp.close();                                 //Close the file.
}

"...why the reinterpret_cast here?"

g++ has a tendency to be very whiny about data types. We want to store the bytes in "bytes", which is unsigned char*. But fp.read() only accepts char* in its first argument. "bytes", when referenced alone, gives a pointer to the first element (It's the same as &bytes[0]). So we can abuse that it, being a unsigned char*, can be reinterpret_cast'd into a char* so it'd shut the compiler the hell up.

tl;dr: It is a way to "lie" to fp.read() to make it think we are giving it a "char*" even though we are giving it an "unsigned char*".

Extracting the integer in the read bytes

This... is what you're here for. Remember, I said that 0x0000FF00 is 65280. So let's get it from that array of bytes.
unsigned int val = *reinterpret_cast<unsigned int*>(&bytes[0]);

//If that looks scary, then here's the C-style
unsigned int val = *(unsigned int*)&bytes[0];
Did I lose you yet? That's fine if so. I got you:
  1. Take note, we declared an unsigned int. This is the data type we are reading the data in to.
  2. Notice &bytes[0], and why I wrote it like that instead of bytes (even though they are the same). There are going to be cases where you want to read bytes starting from like... the 18th bit instead of the first bit. I'll show a more complex example below.
  3. reinterpret_cast that to an int*. And then dereference it in to an int. Then finally, assign "val" to that integer.
The value we get from "cout"ing it?
65280

The whole program without files

Just so you understand the whole thing. Here's the C++ source without files.
#include <iostream>

using namespace std;

int main() {
	//Array to hold binary data.
	unsigned char bytes[4] = {0x00, 0xFF, 0x00, 0x00};
	
	//Extract integer encoded in the bytes array
	unsigned int val = *reinterpret_cast<unsigned int*>(&bytes[0]);
	
	//Print out the integer
	cout << val << endl;
}
You may test it online here! http://cpp.sh/87p64
Reading Bytes and assigning variables to values in them
Computers encode numbers into bits and bytes. An integer, as you know, is stored as 32 bits (4 bytes). I showed you in the last section about reading an int from 4 bytes. But what if you had way more than that?

Consider the following 16 bytes.
FF FF FF FF 00 00 00 00 01 00 00 00 02 00 00 00
So if we break it up into 4 groups of 4 bytes, we will have the following:
FF FF FF FF
00 00 00 00
01 00 00 00
02 00 00 00
Now when we read them flip them. So the numbers translate to the following (assume it's unsigned):
FF FF FF FF = 0xFFFFFFFF = 4294967295 (if signed, it's -1)
00 00 00 00 = 0x00000000 = 0
01 00 00 00 = 0x00000001 = 1
02 00 00 00 = 0x00000002 = 2
So I taught you how to do that conceptually, but what about via C++?
#include <iostream>

using namespace std;

int main() {
	//Array to hold binary data.
	unsigned char bytes[16] = {
		0xFF, 0xFF, 0xFF, 0xFF,
		0x00, 0x00, 0x00, 0x00,
		0x01, 0x00, 0x00, 0x00,
		0x02, 0x00, 0x00, 0x00
	};
	
	//Extract integer encoded in the bytes array
	unsigned int val[4];
	val[0] = *reinterpret_cast<unsigned int*>(&bytes[ 0]);
	val[1] = *reinterpret_cast<unsigned int*>(&bytes[ 4]);
	val[2] = *reinterpret_cast<unsigned int*>(&bytes[ 8]);
	val[3] = *reinterpret_cast<unsigned int*>(&bytes[12]);
	
	//Print out the integers
	for (int i = 0; i < 4; i++)
		cout << val[i] << endl;
}
And the output is.........
4294967295
0
1
2
Don't believe me? Try it out yourself! http://cpp.sh/2n76t

How it works

In the previous section, I showed you how to get something from the beginning of the unsigned char array of byte data. However, you aren't restricted to just getting data from the beginning. You may skip ahead any number of bytes and start reading from there instead.

Consider val[2], being stored 8 bytes in to that array. Here's it colour-coded. I also point to where the pointer is pointing at.
FF FF FF FF 00 00 00 00 01 00 00 00 02 00 00 00
                        ^
                    &bytes[8]
If we read it as a char*, we'd only get the first byte, being 0x01. But since we are reinterpreting it as a unsigned int*, we read that byte and the following 3 bytes because an int is 4 bytes in size.
A more complex example of "byte encoding"
So the above section was definitely a mouthful, but it's a very useful thing to know for a class like CS360 (Systems Programming... the crown jewel of the Computer Science major here. You can thank me later). Let's say that we have a more complex file such as this one with 16 bytes:
FF 22 48 01 43 61 74 01
F0 45 22 02 43 61 74 00
Okay you have no idea what this data is for yet. Let's say we had this struct:
struct cat_group {
	unsigned int num; //Number of cats
	char letter[3];   //Letters
	char colour;      //0 - White, 1 - Black, >=2 - Other
};
...Yes I'm a cat person. Don't judge. Anyways, the size of this struct can be found by adding up the sizes of all of the data types.
struct cat_group {
	unsigned int num; //4
	char letter[3];   //1 x 3
	char colour;      //1
};

//4 + (1 * 3) + 1 = 8
We can also just cheat and use cout << sizeof(cat) << endl;. We will see that it ends up being 8. Do note though that the size of a struct must be in multiples of 4. So if we added another char into it, then the size would become 12 even though it's only allocating 9 bytes.

Read bytes directly into struct

Now let's have some fun. We can load those bytes directly into the struct with pointers. Let's look at it.
#include <iostream>
#include <fstream>

using namespace std;

struct cat_group {
	unsigned int num; //Number of cats
	char letter[3];   //Letters
	char colour;      //0 - White, 1 - Black, >=2 - Other
};

int main() {
	/*
		NOTE: our binary file has the following bytes:
		0x1A, 0x00, 0x00, 0x00, 0x43, 0x61, 0x74, 0x01
		0xF0, 0x45, 0x22, 0x02, 0x43, 0x61, 0x74, 0x00
	*/
	
	//Declare our instances of "cat_group" as "group1" and "group2"
	cat_group group1, group2;
	
	//Open up our file and read in the bytes... directly into "group1" and "group2".
	ifstream fp;
	fp.open("data.bin", ios::binary);
	fp.read(reinterpret_cast<char*>(&group1), 8); //Read the first 8 bytes into group1
	fp.read(reinterpret_cast<char*>(&group2), 8); //Read the next 8 bytes into group1
	fp.close();
	
	//Print out data to verify.
	cout << "Group 1 Information" << endl;
	cout << "Num    : " << group1.num << endl;
	cout << "Letters: " << group1.letter[0] << group1.letter[1] << group1.letter[2] << endl;
	cout << "Colour : " << (int)group1.colour << endl << endl;
	
	cout << "Group 2 Information" << endl;
	cout << "Num    : " << group2.num << endl;
	cout << "Letters: " << group2.letter[0] << group2.letter[1] << group2.letter[2] << endl;
	cout << "Colour : " << (int)group2.colour << endl;
}
Sure enough, the output is:
Group 1 Information
Num    : 21504767
Letters: Cat
Colour : 1

Group 2 Information
Num    : 35800560
Letters: Cat
Colour : 0
That's a lot of kitties! Millions of them.

The breakdown

The memory was outlined above. Here it is again, with colour coding:
FF 22 48 01 43 61 74 01
F0 45 22 02 43 61 74 00
Let's look at how the memory of the struct is laid out... colour-coded too:
struct cat_group {
	unsigned int num; //(4     bytes) Number of cats
	char letter[3];   //(1 x 3 bytes) Letters
	char colour;      //(1     byte ) 0 - White, 1 - Black, >=2 - Other
};
We made 2 instances of the "cat_group" struct named "group1" and "group2". Those are in memory somewhere, and they have an address. Let's assume (just because we can) that their addresses are 0x42467BC0 and 0x42467BC8 respectively. So when we call cat_group group1, group2;, the memory looks like this:
Address    Bytes
42467BC0   00 00 00 00 00 00 00 00
42467BC8   00 00 00 00 00 00 00 00
Note: In a realistic matter, the data isn't guaranteed to be all 0's. The kernel just assigns it an address which may have garbage data from previous use at that address. For now though, we will assume they are 0's.

Notice a pattern? The format of the struct matches the file information we are reading in "exactly". This is a common trick in C and C++ where we make structs in a very specific way and then just read in everything into the struct as if it was raw bytes.

Hint: This is also why I was telling you to make your Pixel struct's order as "blue", "green", "red". Order matters.

Now, remember what weapons we have. We can use reinterpret_cast on a pointer to the struct (cat_group*) to make it appear as a char* array. What's next? Let's just read all of the bytes directly into the struct's data using its address.
fp.read(reinterpret_cast<char*>(&group1), 8);
	
Address    Bytes
42467BC0   FF 22 48 01 43 61 74 01 <- This has been written to
42467BC8   00 00 00 00 00 00 00 00
At this point in the code, we can try printing out "group1.num", and the value we get will be 21504767, which is 0x014822FF in hex. (Notice it's flipped of FF 22 48 01?)

Let's execute the second read command.
fp.read(reinterpret_cast<char*>(&group2), 8);
	
Address    Bytes
42467BC0   FF 22 48 01 43 61 74 01
42467BC8   F0 45 22 02 43 61 74 00 <- This has been written to
Now the data has been read in to the second struct as well. Close the file, and print out the information. You'll see it's the output listed above.
Lab Simulator
I don't think my server can handle simulating bitmap modification for Part A of this lab. As for Part B, I might get to writing a simulator for it sometime, but don't get your hopes up. If I happen to do it, I'll put a link here. Check often!