CSCI 2122 Assignment 4
Due date: 11:59pm, Sunday, March 30, 2025, submitted via git
Objectives
The purpose of this assignment is to practice your coding in C, and to reinforce the concepts discussed in class on program representation.
In this assignment you will implement a CPU simulator for a simple instruction set (much simpler than x86). This assignment is divided into several parts to make it simpler. In the first part, you will implement the memory part of the simulator and loader, which loads the code from a file into the simulated memory. In the second part, you will implement the fetch-decode-execute part of the CPU.
Preparation:
1. Complete Assignment 0 or ensure that the tools you would need to complete it are installed.
2. Clone your assignment repository:
|
https://git.cs.dal.ca/courses/2025-Winter/csci-2122/assignment-4/????.git
|
where ???? is your CSID. Please see instructions in Assignment 0 and the tutorials on Brightspace if you are not sure how.
Inside the repository there are two directories: xsim1 and xsim2, where code is to be written. You should set up a separate CLion project for each of these directories, like the labs. Inside each directory is a tests directory that contains tests that will be executed each time you submit your code. Please do not modify the tests directory or the .gitlab-ci.yml file that is found in the root directory. Mod- ifying these files may break the tests. These files will be replaced with originals when the assignments are graded. You are provided with sample Makefile files that can be used to build your program. If you are using CLion, a Makefile will be generated from the CMakeLists.txt file generated by CLion.
Background:
For this assignment you will implement a simplified RISC-based 16-bit CPU simulator. Specifically, the CPU has 16 general purpose registers and a small number (approximately 35) instructions, most of which are two bytes (one word) in size. As well, there are a couple special purpose registers, such as the program counter (PC) and the status (F) register.
The X Architecture comprises a 64KB (65536 bytes) memory space with addresses ranging from 0 to 65535, and a CPU with 16 general purpose 16-bit registers (r0 . . . r15 ). The CPU is a 16-bit CPU, meaning that the word size is 16-bits (2 bytes). Thus, nearly all operations operate on 16-bit chunks of data, i.e., in this case one word is 16 bits. Thus, all values and addresses are 16 bits in size. All 16-bit values are also encoded in big-endian format, meaning that the most-significant byte comes first.
Apart from the 16 general purpose registers, the CPU has two special 16-bit registers: a program counter (PC), which stores the address of the next instruction that will be executed, and the status (F), which stores bit-flags representing the state of the CPU. The status register contains two flags. The least significant bit is the condition flag, which represents the truth value of the last logical test operation. The bit is set to true if the condition was true, and to false otherwise. The second least significant bit indicates whether the debug mode is on or off. If the debug mode is on, then after each instruction is executed, the CPU simulator prints out the state of all its registers (using the provided function).
Additionally, the CPU uses the last general-purpose register, r15, to store the pointer to the program stack. This register is incremented by two when an item is popped off the stack and decremented by two when an item is pushed on the stack.
The size of the program stack is specified by the code being executed. The program stack is used to store temporary values, arguments to a function, and the return address of a function call.
The CPU takes one clock tick to execute a Fetch, Decode, Execute cycle for any instruction:
1. The instruction is fetched from memory using the PC to index into the memory space.
2. The PC is incremented by two.
3. The instruction is decoded.
4. The instruction is executed.
5. Lastly, if the debug mode is turned on, the CPU state is displayed using the xcpu_print() function found in xcpuprnt.c.
The CPU has the following instruction set.
The X Instruction Set
The instruction set comprises approximately 35 instructions that perform. arithmetic and logic, data move- ment, stack manipulation, and flow control. Most instructions take registers as their operands stack, and store the result of the operation in a register. However, some instructions also take immediate values as operands. Thus, there are four classes of instructions: 0-operand instructions, 1-operand instructions, 2- operand instructions, and extended instructions, which take two words (4 bytes) instead of one word.
All but the extended instructions are encoded as a single word (16 bits). The extended instructions are also one word but are followed by an additional one-word operand. Thus, if the instruction is an extended instruction, the PC needs an additional increment 2 during the instruction’s execution. As mentioned previously, most instructions are encoded as a single word. The most significant two bits of the word indicates whether the instruction is a 0-operand instruction (00), a 1-operand instruction (01), a 2-operand instruction (10), or an extended instruction (11). For a 0-operand instruction, the encoding is
where the two most significant bits are 00 and the next six bits represent the instruction identifier. The second byte of the instruction is 0.
For a 1-operand instruction, the encoding is
where the two most significant bits are 01, the next bit indicates whether the operand is an immediate or a register, and the next five bits represent the instruction identifier. If the third most significant bit is 0, then the four most significant bits of the second byte encode the register that is to be operated on (0 …
15). Otherwise, if the third most significant bit is 1, then the second byte encodes the immediate value.
For a 2-operand instruction, the encoding is
where the two most significant bits are 10, and the next six bits represent the instruction identifier. The second byte encodes the two register operands in two four-bit chunks. Each of the 4-bit chunks identifies one of the 16 registers (0 … 15).
For an extended instruction the encoding is
where the two most significant bits are 11, the next bit indicates whether a second register operand is used, and the next five bits represent the instruction identifier. If the third most significant bit is 0, then the instruction only uses the one-word immediate operand that follows the instruction. Otherwise, if the third most significant bit is 1, then the four most significant bits of the second byte encode (1 … 15) the register that is the second operand of the instruction.
The instruction set is described in Tables 1, 2, 3, and 4. Each description includes the mnemonic (and syntax), the encoding of the instruction, the instruction’s description and function. For example, the add, loadi, and push instructions have the following descriptions:
First, observe that the add instruction takes two register operands and adds the first register to the sec- ond. All 2-operand instructions operate only on registers and the second register is both a source and destination, while the first is the source. It is 2-operand instruction, hence the first two bits are 10, its instruction identifier is 000001 hence the first byte of the instruction is 0x81.
Second, the loadi instruction is an extended instruction that takes a 16-bit immediate and stores it in a register. Hence, the the first two bits are 11, the register bit is set to 1, and the instruction identifier is 00001. Hence, the first byte is encoded as 0xE1.
Third, the push instruction is a 1-operand instruction, taking a single register operand. Hence, the first two bits are 01, the immediate bit is 0, and the instruction identifier is 00011. Hence, the first byte is encoded as 0x43.
Note that S and D are 4-bit vectors representing S and D.
Table 1: 0-Operand Instructions
Table 2: 2-Operand Instructions
Table 1: Extended Instructions
Note that in the case of extended instructions, the label L or value V are encoded as a single word (16-bit value) following the word containing the instruction. The 0 in the encodings above repre- sents a 4-bit 0 vector.
Table 2: 1-Operand Instructions
An Assembler for this Instruction Set
An assembler is provided for you to use (if needed). The assembler manual is at the end of the assignment.
The X Memory Specification
The X Memory module (xmem.c) manages the memory (RAM) that is read from and written to by the X- CPU, as it executes each instruction. Hence, the module has a very simple function. (i) It allocates memory of a specified size for the simulation’s memory space when the module is initialized, and stores a pointer to the memory. (ii) It provides a “store” operation that takes a pointer to a word of data and an index (address) in the allocated memory space, and stores the word of at the specified address. (iii) It provides a “load” operation that takes an index (address) in the allocated memory space and a pointer to a desti- nation, and loads a word of data from the specified address in the memory space into the destination. I.e., this module simulates the memory system of a computer. Note: a word is 16-bits (2 bytes).
The X Simulator Specification
An X-CPU simulation is conducted in the following manner. The simulator initializes the memory module, which allocates a 64KB memory space. The simulator loads the specified program from a file and stores it in memory using the memory module’s “store” operation. Once a program is loaded into memory, the CPU context is initialized: All registers should be zeroed, including the PC because this is the point in memory where the CPU begins execution. Once the CPU context is initialized the program is executed.
An execution of the program takes place by repeatedly calling the CPU execution function, which fetches, decodes, and executes the next instruction pointed to by the PC. The execution proceeds for a specified number of ticks or until the program halts the CPU. A program halts the CPU when it executes an illegal instruction, such as the opcode 0. When this happens, the simulator exits.
Your task will be to implement the X Simulator and the X-CPU, which is used to execute programs as- sembled with the provided assembler.
Task 1: Implement the main() for the Simulator
Your first task is to implement the main() function of the X Simulator in the xsim1 directory of your repo. The source file main.c should contain the main() function. The simulator should do the following:
1. Take two (2) arguments on the command line: The first parameter is a nonnegative integer de- noting the maximum number of cycles that a program should run for, and the remaining argument is the object/executable file of the program to run. For example, the invocation
./xsim 1000 hello.xo
instructs the simulator to load the program hello.xo and run the program for at most 1000 cycles. If 0 cycles is specified this is interpreted as an infinite number of cycles. I.e., the program should never run out of cycles.
2. Allocate or instantiate an xcpu structure (defined in xcpu.h).
3. Initialize the X Memory module by calling xmem_init(65536) (defined in xmem.c), thus al- locating a 64KB memory space.
4. Load the program into memory from the file specified on the command-line. The program should be loaded starting at the start of the memory space (address 0) using the xmem_store ()func- tion, declared in xmem.h. The program will need to open, read, and close the file.
5. Initialize the xcpu structure.
6. Execute the loaded program for the specified number of cycles or until the program halts. Your code should use a loop and call the xcpu_execute() function (declared in xcpu.h) that you will implement in the next part of this assignment. For Task 1, an implementation in xcpu.o is provided.
7. Terminate the simulator once the program halts or runs out of cycles.
Note: the sample solution is less than 80 lines of code. (But there is no limit on the length.)
Input
The input to the program is via the command line. The program takes two arguments
• cycles: the maximum number of instructions to execute. If the value is 0, the execution is unlimited.
• program_file: the program file containing the assembled code to be executed.
Processing
All input shall be correct. All program files shall at most 65536 bytes (64KB). The simulator will need to open and read the program file and store it in the memory module. There is no need to interpret the program code in this part of the assignment.
The last part of the simulation involves calling the xcpu_execute() function, in a loop. Each call exe- cutes one instruction. This function returns 1 on success and 0 on failure. The loop should continue until the specified number of instructions have been executed, or until the function returns 0. This function is implemented in xcpu.o and will be the focus of the next part of the assignment.
Recommendation: While no error checking is required, it may be helpful to still do error checking, e.g., make sure files are properly opened because it will help with debugging as well.
Output
There is no required output for this part of the assignment. The provided code will do the output.
Task 2: Implement xcpu_execute()
Your second task is to implement the X-CPU in the file xcpu.c. in the xsim2 directory of your repo. First, copy the main.c from xsim1 to xsim2. You are now to implement the function:
extern int xcpu_execute( xcpu *c );
which is declared in xcpu.h and simulates one cycle of a CPU. The function takes a pointer to the xcpu struct:
typedef struct xcpu_context {
unsigned short regs[X_MAX_REGS]; /* general register file */
unsigned short pc; /* program counter */
unsigned short state; /* state (F) register */
} xcpu;
which stores the context of a program. The structure is defined in xcpu.h and contains CPU registers. The function should
1. Fetch the current instruction pointed to by the PC from the xmem memory (use xmem_load()), 2. Increment the PC, decode the instruction, and
3. Execute the instruction, modifying the PC, other registers, or memory, depending on the instruc- tion.
4. If the debugging bit is turned on in the F (state) register (see std and cld instructions in Table 1) call the xcpu_print() function (declared in xcpu.h) to display the CPU registers.
5. Return 1 if the instruction was successfully executed, and 0 if an illegal instruction was executed. Note: the sample solution is less than 200 lines of code. The opcodes for all the instructions can be found in xis.h, so you should not need to do a lot of work to get this working.
Input
The input is the same as Task 1.
Processing
Use the information in Tables 1 – 4 to implement the function xcpu_execute(). No error checking is needed. Use the xmem_load() and xmem_store() functions (declared in xmem.h) to read and write to the X memory.
For the out instruction (see Table 4), output the lower byte of the operand using the standard library function putchar().
Output
Almost all output is done using the xcpu_print () function, which is provided. The only other output occurs when the out instruction is executed. In this case, output the single character stored in the lower byte of the operand, treating it as an ASCII value. (Use putchar().)
Hints and Suggestions
• Use the unsigned short type for all registers and indices.
• You should only need to modify two files: main.c (Task 1) and xcpu.c (Task 2).
• Start early, the solution totals less than 250 lines of (additional) code, but there is a lot to digest in the assignment specifications.
• The library functions I found most useful are: sscanf(), printf(), open (), and read (), close ().