Question

Task in this assignment is to write mips_sim a simulator for a small simple subset of the MIPS .

The input to mips_sim will be the 32-bit instruction codes for MIPS instructions as hexadecimal numbers.

mips_sim.c should simulate executing these instruction like this:

cat examples/42.hex
3404002a
34020001
c
3404000a
3402000b
c
dcc mips_sim.c -o mips_sim
./mips_sim examples/42.hex
0: 0x3404002A ori  $4, $0, 42
>>> $4 = 42
1: 0x34020001 ori  $2, $0, 1
>>> $2 = 1
2: 0x0000000C syscall
>>> syscall 1
<<< 42
3: 0x3404000A ori  $4, $0, 10
>>> $4 = 10
4: 0x3402000B ori  $2, $0, 11
>>> $2 = 11
5: 0x0000000C syscall
>>> syscall 11
<<<

A reference implementation is available as 1521 mips_sim which can use to find the correctoutput for any input, like this:

cat examples/square.hex
34100004
34110003
72108002
72318802
2302020
34020001
c
3404000a
3402000b
c
1521 mips_sim examples/square.hex
0: 0x34100004 ori  $16, $0, 4
>>> $16 = 4
1: 0x34110003 ori  $17, $0, 3
>>> $17 = 3
2: 0x72108002 mul  $16, $16, $16
>>> $16 = 16
3: 0x72318802 mul  $17, $17, $17
>>> $17 = 9
4: 0x02302020 add  $4, $17, $16
>>> $4 = 25
5: 0x34020001 ori  $2, $0, 1
>>> $2 = 1
6: 0x0000000C syscall
>>> syscall 1
<<< 25
7: 0x3404000A ori  $4, $0, 10
>>> $4 = 10
8: 0x3402000B ori  $2, $0, 11
>>> $2 = 11
9: 0x0000000C syscall
>>> syscall 11
<<<

You need to implement only these 10 MIPS instructions:

Assembler	C	Bit Pattern
add $d, $s, $t	d = s + t	000000ssssstttttddddd00000100000
sub $d, $s, $t	d = s - t	000000ssssstttttddddd00000100010
slt $d, $s, $t	d = s < t	000000ssssstttttddddd00000101010
mul $d, $s, $t	d = s * t	011100ssssstttttddddd00000000010
beq $s, $t, I	if (s == t) PC += I	000100ssssstttttIIIIIIIIIIIIIIII
bne $s, $t, I	if (s != t) PC += I	000101ssssstttttIIIIIIIIIIIIIIII
addi $t, $s, I	t = s + I	001000ssssstttttIIIIIIIIIIIIIIII
ori $t, $s, I	t = s | I	001101ssssstttttIIIIIIIIIIIIIIII
lui $t, I	t = I << 16	00111100000tttttIIIIIIIIIIIIIIII
syscall	syscall	00000000000000000000000000001100

You only need to implement these 3 system calls.

Description	$v0	Pseudo-C
print integer	1	printf("%d", $a0)
exit	10	exit(0)
print character	11	printf("%c", $a0)

Task is to add code under execute_instructions function and necessary additional functions.
// starting point code

// PUT YOUR HEADER COMMENT HERE

#include
#include
#include
#include
#include

#define MAX_LINE_LENGTH 256
#define INSTRUCTIONS_GROW 64

// ADD YOUR #defines HERE

void execute_instructions(int n_instructions,
uint32_t instructions[n_instructions],
int trace_mode);
char* process_arguments(int argc, char* argv[], int* trace_mode);
uint32_t* read_instructions(char* filename, int* n_instructions_p);
uint32_t* instructions_realloc(uint32_t* instructions, int n_instructions);

// ADD YOUR FUNCTION PROTOTYPES HERE

// YOU SHOULD NOT NEED TO CHANGE MAIN

int main(int argc, char* argv[]) {
int trace_mode;
char* filename = process_arguments(argc, argv, &trace_mode);

int n_instructions;
uint32_t* instructions = read_instructions(filename, &n_instructions);

execute_instructions(n_instructions, instructions, trace_mode);

free(instructions);
return 0;
}

// simulate execution of instruction codes in instructions array
// output from syscall instruction & any error messages are printed
//
// if trace_mode != 0:
// information is printed about each instruction as it executed
//
// execution stops if it reaches the end of the array

void execute_instructions(int n_instructions,
uint32_t instructions[n_instructions],
int trace_mode) {
// REPLACE CODE BELOW WITH YOUR CODE

int pc = 0;

while (pc < n_instructions) {
if (trace_mode) {
printf("%d: 0x%08X\n", pc, instructions[pc]);
}
pc++;
}
}

// ADD YOUR FUNCTIONS HERE

// YOU DO NOT NEED TO CHANGE CODE BELOW HERE

// check_arguments is given command-line arguments
// it sets *trace_mode to 0 if -r is specified
// *trace_mode is set to 1 otherwise
// the filename specified in command-line arguments is returned

char* process_arguments(int argc, char* argv[], int* trace_mode) {
if (
argc < 2 ||
argc > 3 ||
(argc == 2 && strcmp(argv[1], "-r") == 0) ||
(argc == 3 && strcmp(argv[1], "-r") != 0)) {
fprintf(stderr, "Usage: %s [-r] \n", argv[0]);
exit(1);
}
*trace_mode = (argc == 2);
return argv[argc - 1];
}

// read hexadecimal numbers from filename one per line
// numbers are return in a malloc'ed array
// *n_instructions is set to size of the array

uint32_t* read_instructions(char* filename, int* n_instructions_p) {
FILE* f = fopen(filename, "r");
if (f == NULL) {
fprintf(stderr, "%s: '%s'\n", strerror(errno), filename);
exit(1);
}

uint32_t* instructions = NULL;
int n_instructions = 0;
char line[MAX_LINE_LENGTH + 1];
while (fgets(line, sizeof line, f) != NULL) {

// grow instructions array in steps of INSTRUCTIONS_GROW elements
if (n_instructions % INSTRUCTIONS_GROW == 0) {
instructions = instructions_realloc(instructions, n_instructions + INSTRUCTIONS_GROW);
}

char* endptr;
instructions[n_instructions] = strtol(line, &endptr, 16);
if (*endptr != '\n' && *endptr != '\r' && *endptr != '\0') {
fprintf(stderr, "%s:line %d: invalid hexadecimal number: %s",
filename, n_instructions + 1, line);
exit(1);
}
n_instructions++;
}
fclose(f);
*n_instructions_p = n_instructions;
// shrink instructions array to correct size
instructions = instructions_realloc(instructions, n_instructions);
return instructions;
}

// instructions_realloc is wrapper for realloc
// it calls realloc to grow/shrink the instructions array
// to the speicfied size
// it exits if realloc fails
// otherwise it returns the new instructions array
uint32_t* instructions_realloc(uint32_t* instructions, int n_instructions) {
instructions = realloc(instructions, n_instructions * sizeof * instructions);
if (instructions == NULL) {
fprintf(stderr, "out of memory");
exit(1);
}
return instructions;
}

Answer 1

Working code implemented in C and appropriate comments provided for better understanding.

Source code for mips_sim.c:

///////////////// MIPS_SIMULATOR ///////////////// //
// //
// Description: Given valid hex-encoded mips //
// instructions, the program prints the correct //
// mips instructions (if -r option not given) //
// and the result of any syscalls to STDOUT //
//////////////////////////////////////////////////

///////////// INCLUDES ///////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>
//////////////////////////////////////

////////////// FLAGS /////////////////
// Mips encoding (32 bit):
#define OPCODE 0xFC000000
#define SRC1 0x3E00000
#define SRC2 0x1F0000
#define DEST 0xF800
#define SHIFT 0x7C0
#define FUNC 0x3F

#define IMMED 0xFFFF

// OPCODE Source 1 Source 2 Destination   Shift Amount Function
// 6 bits   5 bits   5 bits   5 bits   5 bits   6 bits

// Instructions:
#define ADD 0x20
#define SUB 0x22
#define SLT 0x2A
#define MUL 0x70000000
#define BEQ 0x10000000
#define BNE 0x14000000
#define ADDI 0x20000000
#define ORI 0x34000000
#define LUI 0x3C000000
#define SYSCALL 0xC
//////////////////////////////////////

//////////// CONSTANTS ///////////////
#define MAX_LINE_LENGTH 256
#define INSTRUCTIONS_GROW 64
#define NUM_OF_REGISTERS 32 // Number of mips registers (32 32-bit registers)
//////////////////////////////////////

/////////// FUNCTION DEFS ////////////
// Setup:
void execute_instructions(int n_instructions, uint32_t instructions[n_instructions], int syscall_mode);
char *process_arguments(int argc, char *argv[], int *syscall_mode);
uint32_t *read_instructions(char *filename, int *n_instructions_p);
uint32_t *instructions_realloc(uint32_t *instructions, int n_instructions);

// Helpers:
void instruction_handler(int8_t syscall_mode, int32_t hex, int *pc, int *registers);
void invalid_code(int8_t syscall_mode, int32_t hex, int pc);
int can_store(int reg);
void branch_check(int pc, int n_intructions);

// Instructions:
void add(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void sub(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void slt(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void mul(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void beq(int8_t syscall_mode, int *pc, int32_t hex, int *registers);
void bne(int8_t syscall_mode, int *pc, int32_t hex, int *registers);
void addi(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void ori(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void lui(int8_t syscall_mode, int pc, int32_t hex, int *registers);
void syscall(int8_t syscall_mode, int pc, int32_t hex, int *registers);
//////////////////////////////////////

/////////////// SETUP FUNCTIONS //////////////////
int main(int argc, char *argv[]) {
int syscall_mode; // If true (i.e. == 1), only the syscall results print
char *filename = process_arguments(argc, argv, &syscall_mode);

int n_instructions;
uint32_t *instructions = read_instructions(filename, &n_instructions);

execute_instructions(n_instructions, instructions, syscall_mode);

free(instructions);
return 0;
}

// simulate execution of instruction codes in instructions array
// output from syscall instruction & any error messages are printed
//
// if trace_mode != 0:
// information is printed about each instruction as it executed
//
// execution stops if it reaches the end of the array
void execute_instructions(int n_instructions, uint32_t instructions[n_instructions], int syscall_mode) {
int *registers = malloc(sizeof(int) * NUM_OF_REGISTERS); // Mimics the mips registers
registers[0] = 0; // Set the zero register

int pc = 0;
while (pc < n_instructions) {
int old_pc = pc;

instruction_handler(syscall_mode, instructions[pc], &pc, registers);
branch_check(pc, n_instructions);

if (old_pc == pc) { // Don't iterate pc if branch instruction given
pc++;
}
}
}

// check_arguments is given command-line arguments
// it sets *trace_mode to 0 if -r is specified
// *trace_mode is set to 1 otherwise
// the filename specified in command-line arguments is returned
char *process_arguments(int argc, char *argv[], int *trace_mode) {
if (
argc < 2 ||
argc > 3 ||
(argc == 2 && strcmp(argv[1], "-r") == 0) ||
(argc == 3 && strcmp(argv[1], "-r") != 0)) {
fprintf(stderr, "Usage: %s [-r] <file>\n", argv[0]);
exit(1);
}
*trace_mode = (argc != 2);
return argv[argc - 1];
}

// read hexadecimal numbers from filename one per line
// numbers are return in a malloc'ed array
// *n_instructions is set to size of the array
uint32_t *read_instructions(char *filename, int *n_instructions_p) {
FILE *f = fopen(filename, "r");
if (f == NULL) {
fprintf(stderr, "%s: '%s'\n", strerror(errno), filename);
exit(1);
}

uint32_t *instructions = NULL;
int n_instructions = 0;
char line[MAX_LINE_LENGTH + 1];
while (fgets(line, sizeof line, f) != NULL) {

// grow instructions array in steps of INSTRUCTIONS_GROW elements
if (n_instructions % INSTRUCTIONS_GROW == 0) {
instructions = instructions_realloc(instructions, n_instructions + INSTRUCTIONS_GROW);
}

char *endptr;
instructions[n_instructions] = strtol(line, &endptr, 16);
if (*endptr != '\n' && *endptr != '\r' && *endptr != '\0') {
fprintf(stderr, "%s:line %d: invalid hexadecimal number: %s",
filename, n_instructions + 1, line);
exit(1);
}
n_instructions++;
}
fclose(f);
*n_instructions_p = n_instructions;
// shrink instructions array to correct size
instructions = instructions_realloc(instructions, n_instructions);
return instructions;
}

// instructions_realloc is wrapper for realloc
// it calls realloc to grow/shrink the instructions array
// to the speicfied size
// it exits if realloc fails
// otherwise it returns the new instructions array
uint32_t *instructions_realloc(uint32_t *instructions, int n_instructions) {
instructions = realloc(instructions, n_instructions * sizeof *instructions);
if (instructions == NULL) {
fprintf(stderr, "out of memory");
exit(1);
}
return instructions;
}
////////////////////////////////////////////////////////

/////////////////// HELPER FUNCTIONS ///////////////////
// Hands off execution to relevant instruction functions based on their encoding
void instruction_handler(int8_t syscall_mode, int32_t hex, int *pc, int *registers) {
if (hex == 0) { // Zero binary
invalid_code(syscall_mode, hex, *pc);
} else if ((hex & OPCODE) == 0) {
if ((hex & (SHIFT | FUNC)) == ADD) {
add(syscall_mode, *pc, hex, registers);
} else if ((hex & (SHIFT | FUNC)) == SUB) {
sub(syscall_mode, *pc, hex, registers);
} else if ((hex & (SHIFT | FUNC)) == SLT) {
slt(syscall_mode, *pc, hex, registers);
} else if ((hex & (SHIFT | FUNC)) == SYSCALL) {
syscall(syscall_mode, *pc, hex, registers);
} else { // None of the defined instructions were matched
invalid_code(syscall_mode, hex, *pc);
}
} else {
if ((hex & OPCODE) == MUL) {
mul(syscall_mode, *pc, hex, registers);
} else if ((hex & OPCODE) == BEQ) {
beq(syscall_mode, pc, hex, registers);
} else if ((hex & OPCODE) == BNE) {
bne(syscall_mode, pc, hex, registers);
} else if ((hex & OPCODE) == ADDI) {
addi(syscall_mode, *pc, hex, registers);
} else if ((hex & OPCODE) == ORI) {
ori(syscall_mode, *pc, hex, registers);
} else if ((hex & OPCODE) == LUI) {
lui(syscall_mode, *pc, hex, registers);
} else { // None of the defined instructions were matched
invalid_code(syscall_mode, hex, *pc);
}
}
}

// If an invalid instruction code is given
void invalid_code(int8_t syscall_mode, int32_t hex, int pc) {
if (syscall_mode == 0) {
printf("%d: 0x%08X invalid instruction code\n", pc, hex);
} else {
printf("invalid instruction code\n");
}
exit(0);
}

// Checks that the register is usable (all except $0)
int can_store(int reg) {
if (reg < 1 || reg > 32) { // Not a usable register for storing
return 0;
}
return 1;
}

// Checks pc value conditions
void branch_check(int pc, int n_intructions) {
if (pc == n_intructions + 1) { // If branch to one after last instruction
exit(0);
} else if (pc < 0) { // If branch before all instructions
printf("Illegal branch to address before instructions: PC = %d\n", pc);
exit(0);
} else if (pc > n_intructions) { // If pc is past the last instruction
printf("Illegal branch to address after instructions: PC = %d\n", pc);
exit(0);
}
}
////////////////////////////////////////////////////////

/////////////// INSTRUCTION FUNCTIONS //////////////////
void add(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t d = (hex & DEST) >> 11;
int8_t s = (hex & SRC1) >> 21;
int8_t t = (hex & SRC2) >> 16;

int result = registers[s] + registers[t];
if (can_store(d)) { // Check if d is a valid register to store to
registers[d] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X add $%d, $%d, $%d\n", pc, hex, d, s, t);
printf(">>> $%d = %d\n", d, result);
}
}

void sub(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t d = (hex & DEST) >> 11;
int8_t s = (hex & SRC1) >> 21;
int8_t t = (hex & SRC2) >> 16;

int result = registers[s] - registers[t];
if (can_store(d)) { // Check if d is a valid register to store to
registers[d] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X sub $%d, $%d, $%d\n", pc, hex, d, s, t);
printf(">>> $%d = %d\n", d, result);
}
}

void slt(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t d = (hex & DEST) >> 11;
int8_t s = (hex & SRC1) >> 21;
int8_t t = (hex & SRC2) >> 16;

int result = registers[s] < registers[t];
if (can_store(d)) { // Check if d is a valid register to store to
registers[d] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X slt $%d, $%d, $%d\n", pc, hex, d, s, t);
printf(">>> $%d = %d\n", d, result);
}
}

void mul(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t d = (hex & DEST) >> 11;
int8_t s = (hex & SRC1) >> 21;
int8_t t = (hex & SRC2) >> 16;

int result = registers[s] * registers[t];
if (can_store(d)) { // Check if d is a valid register to store to
registers[d] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X mul $%d, $%d, $%d\n", pc, hex, d, s, t);
printf(">>> $%d = %d\n", d, result);
}
}

void beq(int8_t syscall_mode, int *pc, int32_t hex, int *registers) {
int8_t t = (hex & SRC2) >> 16;
int8_t s = (hex & SRC1) >> 21;
int16_t immed = hex & IMMED;

int old_pc = *pc;
if (registers[s] == registers[t]) { // If the registers are not equal
*pc += immed; // Shift pc by immed (move to diff instruction index)
}

if (syscall_mode == 0) {
printf("%d: 0x%08X beq $%d, $%d, %d\n", old_pc, hex, s, t, immed);
if (old_pc == *pc) { // pc was not changed
printf(">>> branch not taken\n");
} else {
printf(">>> branch taken to PC = %d\n", *pc);
}
}
}

void bne(int8_t syscall_mode, int *pc, int32_t hex, int *registers) {
int8_t t = (hex & SRC2) >> 16;
int8_t s = (hex & SRC1) >> 21;
int16_t immed = hex & IMMED;

int old_pc = *pc;
if (registers[s] != registers[t]) { // If the registers are not equal
*pc += immed; // Shift pc by immed (move to diff instruction index)
}

if (syscall_mode == 0) {
printf("%d: 0x%08X bne $%d, $%d, %d\n", old_pc, hex, s, t, immed);
if (old_pc == *pc) { // pc was not changed
printf(">>> branch not taken\n");
} else {
printf(">>> branch taken to PC = %d\n", *pc);
}
}
}

void addi(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t t = (hex & SRC2) >> 16;
int8_t s = (hex & SRC1) >> 21;
int16_t immed = hex & IMMED;

int result = registers[s] + immed;
if (can_store(t)) { // Check if t is a valid register to store to
registers[t] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X addi $%d, $%d, %d\n", pc, hex, t, s, immed);
printf(">>> $%d = %d\n", t, result);
}
}

void ori(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t t = (hex & SRC2) >> 16;
int8_t s = (hex & SRC1) >> 21;
int16_t immed = hex & IMMED;

int result = registers[s] | immed;
if (can_store(t)) { // Check if t is a valid register to store to
registers[t] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X ori $%d, $%d, %d\n", pc, hex, t, s, immed);
printf(">>> $%d = %d\n", t, result);
}
}

void lui(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
int8_t t = (hex & SRC2) >> 16;
int16_t immed = hex & IMMED;

int result;
if (immed > 0) { // immed is positive, behave normally
result = immed << 16;
} else { // immed is a negative number
result = -65536; // this matches the reference implementation
}

if (can_store(t)) { // Check if t is a valid register to store to
registers[t] = result;
}

if (syscall_mode == 0) {
printf("%d: 0x%08X lui $%d, %d\n", pc, hex, t, immed);
printf(">>> $%d = %d\n", t, result);
}
}

void syscall(int8_t syscall_mode, int pc, int32_t hex, int *registers) {
if (syscall_mode == 0) {
printf("%d: 0x%08X syscall\n", pc, hex);
printf(">>> syscall %d\n", registers[2]);
}

if (registers[2] == 1) { // Syscall 1
if (syscall_mode == 0) {
printf("<<< %d\n", registers[4]);
} else {
printf("%d", registers[4]);
}
} else if (registers[2] == 10) { // Syscall 10
exit(0);
} else if (registers[2] == 11) { // Syscall 11
if (syscall_mode == 0) {
printf("<<< %c\n", registers[4]);
} else {
printf("%c", registers[4]);
}
} else { // Unknown syscall number
printf("Unknown system call: %d\n", registers[2]);
exit(0);
}
}
////////////////////////////////////////////////////////