# Table-Driven Programming, and CPU Machine Code

CS 301 Lecture, Dr. Lawlor

## The C++ "Array Initializer"

So C++ allows this handy "array initializer syntax" for setting up a 1D array:
const int arr[]={7,9,23};
This makes an array, "arr", containing three ints: seven, nine, and twenty-three.

It's the same as declaring:
int arr[3];
arr[0]=7;
arr[1]=9;
arr[2]=23;
But clearly the initializer is shorter and simpler!

Whitespace inside an initializer doesn't matter, and you can even add comments and stuff in there:
const int arr[]={
7, /* dwarves, in decimal */
0x9, /* cube of three, expressed in hexadecimal */
027, /* number of angels that can dance on the head of a pin, in octal */
};
It's still the same three ints as before.

If you want to save memory, you can make a 1D array of unsigned char (which are like int, but only 8 bits wide):
const unsigned char arr[]={7,9,23};

## Table-Driven Programming

A little array that tells the program what to do is called a "table", and programs written this way are called "table-driven".  Here's a simple table-driven program that prints out a certain number of "#" signs on each line, with the exact number determined from a little table:
`const unsigned char table[]={	20,	20,	2,	2,	2,	20,	20,	0 /* end of the table */};int foo(void) {	int i=0; /* location in the table */	while (table[i]!=0) { /* print one entry in the table */		int  n=table[i++]; /* number of times to print */		char c='#'; /* character to print */		for (int repeat=0;repeat<n;repeat++) /* print it n times */			std::cout<<c<<" ";		std::cout<<std::endl;	}	return 0;}`

(Try this in NetRun now!)

Here's a similar table-driven program that reads two entries in the table each time around the loop.  The first table entry is treated as a repetition count, and the second table entry is the letter to repeat.  Again, the program stops when it hits a repetition count of zero:
`const unsigned char table[]={/* ---  n, character to print n times ---- */	3,'q',	2,'@',	4,'~',	1,'z',	0 /* end of the table */};int foo(void) {	int i=0; /* location in the table */	while (table[i]!=0) { /* print one entry in the table */		int  n=table[i++]; /* number of times to print */		char c=table[i++]; /* character to print */		for (int repeat=0;repeat<n;repeat++) /* print it n times */			std::cout<<c<<" ";	}	return 0;}`

(Try this in NetRun now!)

Note that the above is just a nine-entry table; the relationship between 3 and 'q' is purely conceptual.

The big advantage of table-driven programming is "separation of concerns".   The table, and the code that walks through the table (the function "foo" above), are completely separate pieces.  They can be written by different people.  They can be updated independently.  They can be read from different sources.  For example:
• In a game, the code used to make a character do stuff (like attack the player, or drool, or buy and sell stuff) is part of the executable, written by the game engine company.  The particular stuff the character should do, and when they should do it, comes from some sort of table, usually part of that level's map, and is read from disk or downloaded from the network.
• The table can contain user interface strings from the program, like "Please enter a number".  To translate the program into another human language, like German or Greek, you just have to change the table to contain "Bitte geben Sie eine Zahl" or "Παρακαλώ εισάγετε έναν αριθμό".  This "look up user interface text from a table" idea is a key part of internationalization (i18n), as implemented in, e.g., GNU gettext.
• A short program can look up "the answer" in a table.  The answer can be the result of a much longer (slower, more resource-intensive) program, or even human effort.  This only works if there are only a small possible number of questions.  I've used this method for problems like designing playoff tournaments; big tournaments are regular (a big tree) and hence the general case is easy, but small tournaments are tricky to write code for, so I just encoded all the good small tournaments in a table!

## The C++ "Switch" statement

In C++, if you have several values to test, you can use a series of "if" statements:
`int x=0; std::cin>>x; /* read what to do */if (x==3) std::cout<<"Lucky three!\n";else if (x==7) std::cout<<"Seven!  Yes!\n";else if (x==13) std::cout<<"NooooOOOO!!!!\n";else std::cout<<"meh\n";`

(Try this in NetRun now!)

If all the "if" statements are testing the same integral value, a "switch" does the same thing:
`int x=0; std::cin>>x; /* read what to do */switch (x) {	case 3: std::cout<<"Lucky three!\n"; break;	case 7: std::cout<<"Seven!  Yes!\n"; break;	case 13: std::cout<<"NooooOOOO!!!!\n"; break;	default: std::cout<<"meh\n"; break;}`

(Try this in NetRun now!)

Often "switch" is faster than a nested block of "if" statements, especially if there are many possibilities.  I'm using "switch" below, so I thought I'd explain this syntax first.

## How this relates to CS 301: Machine Code

"Machine code" is a block of binary data that the CPU interprets as a long table of commands.  You'll be writing machine code for HW2.  There's nothing magical about machine code, and in fact you can easily write a little program that walks through and executes a table of our own newly-defined "machine code":
`const unsigned char table[]={	0, /*yo! */	1, /*print x */	1, /*print x */	0, /*yo! */	2 /* exit */};int foo(void) {	int i=0; /* our location in the table */	while (1) /* always keep looping through the table */	switch (table[i++]) { /* look at the next thing in the table */	case 0: cout<<"Yo!\n"; break; /* single-Yo instruction */	case 1: cout<<"x\n"; break; /* single-X instruction */	case 2: return 0; /* stop looping through the table */	default:		cout<<"Unrecognized table entry!\n";		return -999;	}}`

Rather than having two identical "print x" commands, we can make the "x" command repeatable, by adding a repetition count.

`const unsigned char table[]={	0, /*yo! */	1, /*print x... */	   2, /*       ... two times */	0, /*yo! */	2 /* exit */};int foo(void) {	int i=0; /* our location in the table */	while (1) /* always keep looping through the table */	switch (table[i++]) { /* look at the next thing in the table */	case 0: cout<<"Yo!\n"; break; /* single-Yo instruction */	case 1: { /* multi-x instruction */		int count=table[i++]; /* next byte in table is the x repeat count */		for (int repeat=0;repeat<count;repeat++)			std::cout<<'x'<<endl;		break;	}	case 2: return 0; /* stop looping through the table */	default:		cout<<"Unrecognized table entry!\n";		return -999;	}}`

(Try this in NetRun now!)

Note that 0, a "Yo!" instruction, stands alone in the table, while 1, a "multi-x" instruction, takes two bytes, because the second byte is an x count.  The indented "2" is not an exit command, it's the repetition count for the 1 instruction!

## x86 Machine Code

You can of course use any numbers you like for the table values.  Here's the same exact idea, but with x86-compatible instruction numbers:
`const unsigned char table[]={	0xb0, /*set x = ... */	7, /*         ... this byte */	0xc3 /* exit */};int foo(void) {	int x=0; /* our "register" (temporary storage, and return value) */	int i=0; /* our location in the table */	while (1) /* always keep looping through the table */	switch (table[i++]) { /* look at the next thing in the table */	case 0xb0: { /* set-x instruction */		x=table[i++]; /* next byte is the new value for x */		break;	}	case 0xc3: return x; /* stop looping through the table */	default:		cout<<"Illegal instruction!\n";		return -999;	}}`

Our table just has (8-bit) bytes in it, but sometimes we want to be able to set an entire (32-bit) int.  The standard x86 solution to this is to split the integer into four bytes: first the low byte (lowest value, last two hex digits), then the not-so-low byte, the not-so-high byte, and the highest byte, like so.

`const unsigned char table[]={	0xb8, /* set x =... */	4, /* low byte is 4 (that is, 0x04) */	1, /* next byte is 1 (that is, 0x01) */	0, /* highest two bytes are both zero */	0,	0xc3 /* return that */};int foo(void) {	int x=0; /* register */	int i=0;	while (1) switch (table[i++]) {	case 0xb8:		x=table[i]|(table[i+1]<<8)|(table[i+2]<<16)|(table[i+3]<<24); 		i+=4;		break; 	case 0xc3: return x;	default:		cout<<"Illegal instruction!\n";		return -999;	}}`

(Try this in NetRun now!)

This returns "0x104".  The "0x04" is the low byte.  "0x01" is the next higher byte, and all higher bytes are zero.

## Multiple Registers

To actually get work done, it's handy to have several different values loaded up, not just one "x" like above.  In assembly language, we use "registers", which are just integers we can use for temporary storage.  Somehow, we need to be able to load different values into these registers--here, we use the low bits of the 0xb8 instruction to determine which register to write to.  For example, "0xb8" will load the integer into register 0 (our main register), while "0xb9" will load the integer into register 1, "0xba" will load into register 2, and so on.

x86 32-bit load instruction (5 bytes long)
Opcode byte:
 1 0 1 1 1 r r r
rrr bits give register number
E.g., "0xb8"
Low byte
Not-so-low byte
Not-quite-high byte
High byte

Here's the code to simulate multiple registers and our new load instruction:

`const unsigned char table[]={	0xb8,0x04,0x1,0,0, /* set register 0 to 0x104 */	0xba,0x05,0x0,0,0, /* set register 2 to 0x5 */	0xc3};int foo(void) {	int regs[8]; /* registers */	int i=0;	while (1) {	  unsigned char instruction=table[i++];	  switch (instruction) {	  case 0xb8: case 0xb9: case 0xba: case 0xbb: case 0xbc: case 0xbd: case 0xbe: case 0xbf: 		regs[instruction&7]=table[i]|(table[i+1]<<8)|(table[i+2]<<16)|(table[i+3]<<24); 		i+=4; /* skip over entries in table we just read */		break; 	  case 0xc3: return regs[0];	  default:		cout<<"Unrecognized table entry!\n";		return -999;	} }}`

## "Add" instruction and ModRM Byte

We'd also like to be able to add our choice of registers together, which we can do in an "add" instruction, the byte "0x03".  The CPU determines which registers to add by reading the next byte, which is called "modR/M" on x86.  "modR/M" is a byte, so it has 8 bits.  The high two bits are both 1's (indicating a register-to-register add).  The next three bits determine the destination register (the register being added to).  The low three bits determine the source register (the register being read for the add).  Because of these three-bit register counts, it's easiest to write a modR/M byte in octal.

x86 register-register add instruction (2 bytes long)
0x03

ModR/M byte:
 1 1 d d d s s s
ddd bits give destination register number
sss bits give source register number

Here are some example modR/M bytes:
• 0302 (binary 11000010): register[0] += register[2];
• 0312 (binary 11001010): register[1] += register[2];
• 0310 (binary 11001000): register[1] += register[0];
• 0317 (binary 11001111): register[1] += register[7];
Here's our simulator, now with an "add" instruction:

`const unsigned char table[]={	0xb8,0x04,0x1,0,0, /* set register 0 to 0x104 */	0xba,0x05,0x0,0,0, /* set register 2 to 0x5 */	0x03,0302, /* add register 2 to register 0 */	0xc3};int foo(void) {	int regs[8]; /* registers */	int i=0;	while (1) {	  unsigned char instruction=table[i++];	  switch (instruction) {	  case 0x03: {		int modRM=table[i++]; /* figure out what to add based on next byte */		int S=modRM&7, D=(modRM>>3)&7, hi=modRM>>6;		if (hi!=3) return -998; /* high bits must be 1 for a register-register operation */		regs[D] += regs[S]; break;	  }	  case 0xb8: case 0xb9: case 0xba: case 0xbb: case 0xbc: case 0xbd: case 0xbe: case 0xbf: 		regs[instruction&7]=table[i]|(table[i+1]<<8)|(table[i+2]<<16)|(table[i+3]<<24); 		i+=4; /* skip over entries in table we just read */		break; 	  case 0xc3: return regs[0];	  default:		cout<<"Unrecognized table entry!\n";		return -999;	} }}`

And for the final horror, because above I "happened" to chose the same numbers as a real x86 CPU uses in its executable table (that is, x86 machine code), now we can actually execute our table directly on the hardware, rather than writing an interpreter.  Don't worry about the function pointer syntax in foo; all the interesting stuff is happening in the bytes of the table, and the CPU hardware that they command!

`const unsigned char table[]={	0xb8,0x04,0x1,0,0, /* set register 0 to 0x104 */	0xba,0x05,0x0,0,0, /* set register 2 to 0x5 */	0x03,0302, /* add register 2 to register 0 */	0xc3};int foo(void) {	typedef int (*myFn)(void); /* defines a function type that returns int */	myFn f=(myFn)table; /* make "table" into that function type */	return f(); /* call our newly-defined function */}`

(Try this in NetRun now!)

The bottom line: this notion of "read a table to figure out what to do next" is very powerful--it's the basis for programmable computers!

## BONUS: Lecture-developed version

Here's the same type of program we developed in class:
`const int program[]={	10,42, /* load into reg 0 */	11, 3, /* load into register 1 */	3,0,1, /* regs[0] += regs[1] */	0 /* return */};int regs[8];int where=0;int instruction=0;while (true) {	instruction=program[where++];	switch (instruction) {	case 0: 		std::cout<<"We're done!  The answer is "<<regs[0]<<"\n"; 		return regs[0]; 		break;	case 10: 		regs[0]=program[where++]; 		break;	case 11: 		regs[1]=program[where++]; 		break;	case 3: {		int dest=program[where++];		int src=program[where++];		regs[dest] += regs[src]; 		break;	}	default: std::cout<<"ILLEGAL INSTRUCTION ERROR! ERROR!\n"; break;	}}`

(Try this in NetRun now!)