CS 11 C track: Assignment 8

The virtual machine is implemented as a C struct which contains the following:

The heart of the VM is the instruction set which it implements. There are only 14 instructions, and here they are. The word in capital letters is the instruction name while the hexadecimal number in parentheses is the one-byte byte code of the instruction, which is how the instruction is represented in the computer’s memory (and in a file).

Some instructions (PUSH, LOAD, STORE, JMP, JZ, JNZ) take operands which are integers of different sizes (1, 2, or 4 bytes). These operands are part of the instructions that are read in from the program file. Next, we’ll talk about how to get these integer values.

Integers in a C program do not all have to be of the same size in bytes. In addition, they can be unsigned or signed. Usually we use signed integers, but in some cases a sign value would not mean anything, so we can use unsigned integers instead. Unsigned integers can hold larger values than signed integers, because one bit of the signed integer is taken up by the sign (actually it’s a bit more complicated than that, but never mind).

Here are the different integer sizes you can use in a C program:

In addition, many compilers (including gcc) support a long long type which is "longer than long" (which almost always means 64 bits), but we won’t need that here. For this program, we will only need the int, unsigned short and unsigned char types.

We will use these types as follows:

All of these values can be used like regular ints; you can add, subtract, increment, decrement them etc. to your heart’s content. You have to be careful when using unsigned values, because if you subtract 1 from 0, you will get a large value (255 for an unsigned char) since there is no way to represent -1 in an unsigned value (and the compiler won’t warn you that you are doing this). Similarly, if you add two shorts or unsigned chars you have to be extra careful about not overflowing, or the results will not be what you want. This is in line with the C philosophy that you have to know exactly what you’re doing at all times.

At the beginning of the program, the contents of the VM program file are read into the instruction array (vm.inst). As mentioned above, each instruction consists of a one-byte bytecode which identifies which instruction it is, and some instructions contain an operand which can be 1, 2, or 4 bytes long. We’ve supplied a function called read_n_byte_integer which will grab the next n bytes from the instruction array (where n = 1, 2, or 4) and convert them into a regular int. Once you have the integer value, it shouldn’t be hard to figure out what to do with it.

There are two parts to getting a VM program to run: writing the program and executing the program on the VM. You are only responsible for the second task. For the first, we’ve written a simple VM program which computes 10 factorial (10 × 9 × 8 × …​ × 2 × 1) and prints it to the terminal. The VM program is a binary file. Binary programs are very difficult to write directly, because you are writing directly in the "machine language" of the VM, which is not meant to be directly usable by humans (and not very friendly for your text editor either, although some editors have special modes to edit binary files).

To make it easier to write machine language programs, we’re supplying you with an "assembler" program that takes a slightly higher-level textual description of a VM program and translates it into the binary form actually executed by the VM. The text version of the program is said to be written in the VM’s "assembly language". There is a one-to-one relationship between instructions in the assembly language and instructions in the machine language, so you don’t lose any control writing programs in assembly language. However, the programs are a lot easier to read and write, and you can add comments etc.

The VM assembly language program is called factorial.bca and is located here. The .bca suffix means "byte-code assembler". Take a look at it now. Comments start with the character # and go to the end of the line. Empty lines are ignored. The other instructions are the same as the machine instructions described above, with one exception: they may have a numeric label at the beginning of the instruction. This label indicates a memory location where a JMP, JZ, or JNZ instruction may jump to. The arguments of these instructions are also labels of this form. These are converted to absolute memory locations (in the VM’s memory) by the assembler program, which is called bca (for "byte-code assembler") and which is located here. (We wrote this in python because it was too tedious to write in C.) You don’t need to understand how it works. In fact, you don’t need to use this program at all unless you want to write your own VM programs, since we’re supplying you with the machine language program as well (see below).

If you want to write your own programs for the VM, the procedure is as follows:

To simplify your task, we’re supplying you with a lot of supporting files. They are:

These are the only files you need for this assignment. To reiterate: the only thing you have to do is to fill in the parts of bci.c marked with a TODO (but you have to fill in all of them). (Remove the TODO comments, of course). Don’t change anything else. These implement the instructions of the virtual machine. This is not very much code; it can be done in less than 100 lines. The tricky part is to make sure that you update the stack pointer and instruction pointer correctly after each instruction (and it’s not really that tricky). In addition, you should add error-checking code to check that you don’t try to pop an empty stack or push onto a full stack (and similarly for all instructions which push or pop stack elements). You should also check that you don’t read beyond the end of the program instruction memory (or before the beginning), and you should check that you don’t try to load from or store to a non-existent register. If an error occurs, you should print an error message to stderr and exit the program with a nonzero exit value. Put error-checking code into the corresponding functions for machine operations.

When checking for stack overflow, the easiest way is to disallow any stack push that would fill up the last location on the stack (location 255 in our implementation). Even though this wastes some space, it’s easy to write the code for it. You might think that you could allow the use of location 255 but disallow pushing onto a stack that has that location filled. In fact, you could, but you’d have to be quite careful, because the largest integer in an unsigned char is 255, so you can’t increment the stack pointer and check that it’s no more than 255 (here, 255 + 1 wraps around and the result is zero). The compiler will warn you if you try to do something like this.

For this assignment, you should try to run the code on an Intel x86 family microprocessor, because the way that integers are laid out in the machine language is not guaranteed to work on other processors. ^[1]