CS 1713 Section 3, Spring 1997
Assignment 8: Structs and Files: Simulating a CPU

For this assignment, you will simulate a simple CPU, along with memory and output, in C.
The CPU, or Central Processing Unit, is the brain of the computer. It fetches instructions from the memory (which may be thought of as part of the CPU) and executes them. It communicates with the outside world through special instructions that deal with input and output. Most CPU instructions are very simple. They do things like add the contents of one memory address to another, or begin executing instructions at a different location. A special instruction, HALT, tells the CPU to stop executing altogether. These instructions are the machine language of our CPU.

Our CPU stores its instructions in an array of C structs. It can hold up to 10000 instructions. It represents memory as another array of 10000 ints; it is assumed for the rest of this document that you will call this array memory, i.e. int memory[10000]; . Our CPU has special integer variable in it called the Program Counter. This is the index into the instruction array where the currently executing instruction is found. Our CPU simulator uses the following algorithm to execute programs; you can consider it pseudocode for your program.
  1. Read the file named on the command line into the array of instructions.
  2. Set the Program Counter (PC) equal to 0.
  3. Continue with steps 4 and 5 until "halt" is encountered.
  4. Fetch the instruction at the PC element of the array, then add one to the PC.
  5. Execute the instruction, possibly changing the PC again. If the instruction is the "halt" instruction, break out of the fetch/execute loop and exit the program, otherwise continue at step 3.
The instructions are stored in the following format:
typedef struct _instruction {
        int     type,		/* type of instruction */
                addr1,		/* first address */
                addr2,		/* second address */
                data;		/* data for the instruction */
} instruction;
You will read the file named on the command line into an array of these structs. The files will be binary files, not suitable for reading with fscanf() or fgets(); you must use fread() to read the records into the array. These files are actually programs in our CPU's machine language. The first field, type, indicates the type of instruction to be executed. For instance, if type is 7, then the instruction is a "multiply" instruction. The second and third fields, addr1 and addr2, are "addresses." These are usually indices into the memory array, but in some special cases they will be indices into the instruction array. The last field, data, is used to hold miscellaneous information a particular instruction might need. Here is a table of all the instructions in our simple CPU. Each instruction is given by
CPU Instructions
type ValueMnemonicDescription
0 NOP No Operation; just does nothing
1 STORE_CONST Store constant: memory[addr1] = data
2 MOVE Move memory: memory[addr1] = memory[addr2]
3 MOVEID Move memory indirect to direct: memory[memory[addr1]] = memory[addr2]
4 MOVEDI Move memory direct to indirect: memory[addr1] = memory[memory[addr2]]
5 ADD_CONST Add constant: memory[addr1] += data
6 ADD Add: memory[addr1] += memory[addr2]
7 MUL Multiply: memory[addr1] *= memory[addr2]
8 DIV Divide: memory[addr1] /= memory[addr2]
9 MOD Modulus (i.e., remainder): memory[addr1] %= memory[addr2]
10 OUTPUT Convert memory[addr1] to char and print to standard output. putchar(memory[addr1]) will do this.
11 COMPARE Compare memory[addr1] to memory[addr2];
if memory[addr1] < memory[addr2] then memory[addr1] = -1;
if memory[addr1] > memory[addr2] then memory[addr1] = 1;
if memory[addr1] is equal to memory[addr2] then memory[addr1] = 0. Note that this destroys one of the items being compared, and that's okay.
12 JUMP "Jump" to another instruction; Program Counter = addr1
13 COND_JUMP Conditional Jump: if memory[addr1] is equal to data, then Program Counter = addr2; otherwise, continue as usual.
14 STOREPC Store Program Counter to memory: memory[addr1] = Program Counter
15 LOADPC Load Program Counter from memory: Program Counter = memory[addr1]
99 HALT Halt; stop execution of instructions.

There are sample programs for you to run on runner in the directory ~djimenez/cs1713. They are stored in our CPU's machine language in the struct format described above. You can click on the name of each program to see a listing of its instructions. This is not the format your program should read, rather, an aid to help you see what is contained in the binary files. You will notice that most of the instructions are STORE_CONST and OUTPUT; this is because printing a string to the screen involves long sequences of these. It bears repeating that If your program is using things like fscanf() and strcmp() then it's not doing the right thing; you need to use fread() to read in binary data into structs. The links below are something for you to read, while the actual binary files they represent are elsewhere on runner.

You don't need to understand the flow of instructions in these programs, although hello and test are not too hard to figure out. They are basically what you would see if you looked at an assembly language listing of the compiler output for C programs that do the same things. They're not pretty, but they are much closer to what your programs really look like when the computer runs them.

An executable has been placed on runner in ~djimenez/bin/sim; it is my version of the simulator. You can use it to run those sample programs and see what the output is supposed to look like.

Note: If you develop your program on a little endian machine using an Intel processor such as the i486, Pentium, etc., then the binary files on runner won't work for you until you run your program on runner. Let me know and I'll make some little endian versions of these files. Macintosh (e.g., CodeWarrior) and SGI users should be OK; let me know if there any problems.

Turn in your program by e-mailing it to the instructor. Write up your observations of the behavior of your program on the four input files, and post this with your weekly progress report.

This assignment is due Monday, April 28 1997 at midnight.