Assignment 1: emu, A MIPS Emulator

version: 1.6 last updated: 2019-11-03 00:20:00

Aims

• Understanding encoding of MIPS instructions
• Understanding semantics of MIPS instructions
• Generally building a concrete understanding of an example CPU
• Practising C, including bit operations

Getting Started

Create a new directory for this assignment called emu, change to this directory, and fetch the provided code by running these commands:

mkdir emu
cd emu
1521 fetch emu

The Assignment

You have been given files which provide code for emu, a MIPS emulator.

However, two important functions — print_instruction and execute_instruction — remain to be completed. Your task is to implement these functions.

Part 1: implementing print_instruction

The first part of the assignment is to implement the function print_instruction in print_instruction.c. print_instruction is given a MIPS instruction as a 32-bit unsigned integer value, You need to add code to print_instruction which prints out the assembler for the instruction.

// If you use C library functions add includes here.

#include "emu.h"
#include "ram.h"
#include "registers.h"

/*
 * print a MIPS instruction (no newline)
 * run reference implementation if unsure what to print
 */
void print_instruction(uint32_t instruction) {
    printf("add $3, $7, $5"); // REPLACE ME WITH YOUR CODE
}

// PUT YOUR FUNCTIONS HERE

For example, print_instruction(0x00851820) should print add $3, $4, $5.

Tables below describe how MIPS instructions are encoded. There is also a reference implementation which you can use if you are unclear what string should be printed for an instruction.

emu takes several command-line arguments. The -p option indicates the rest of the command is hexadecimal integers describing instructions that print_instruction will be called on — for example:

make
dcc     emu.c ram.c registers.c execute_instruction.c print_instruction.c   -o emu
./emu -p 0x00851820
[00400024] 00851820 add $3, $4, $5

The code you have been given prints [00400024] 00851820 : the first part is the address this instruction would be placed, and the second part is the number passed. Your code only needs to print add $3, $4, $5, the instruction that value encodes.

emu -p will also accept assembler statements, each of which it will convert to integers, and print_instruction will be called on that result. For example:

./emu -p 'add $3, $4, $5'
[00400024] 00851820 add $3, $4, $5

Remember to quote the assembler instructions, as in the above example. This is needed because the $ character has a special meaning to the shell.

emu also has a -P option, which takes a file of assembler statements, converts them to integers, and calls print_instruction for each integer, for example:

./emu -P print10.s
[00400024] 34080001 ori $8, $0, 1
[00400028] 2901000B slti $1, $8, 11
[0040002C] 10200009 beq $1, $0, 9
[00400030] 00082020 add $4, $0, $8
[00400034] 34020001 ori $2, $0, 1
[00400038] 0000000C syscall
[0040003C] 3404000A ori $4, $0, 10
[00400040] 3402000B ori $2, $0, 11
[00400044] 0000000C syscall
[00400048] 21080001 addi $8, $8, 1
[0040004C] 0401FFF7 bgez $0, -9
[00400050] 03E00008 jr $31

If you are uncertain what output is correct, run the reference implementation on a CSE machine:

1521 emu -p 0x03E00008
[00400024] 03E00008 jr $31

The reference implementation can print (almost) all MIPS instructions.

Instructions that print with a '!' after them can not be executed by the reference implementation, and do not need to be printed or executed by your assignment code.

If you find a bug in the reference implementation, please report it on the course forum.

The assembly files you have been given will help you debug and test your print_instruction. In addition, autotests are available to help with your testing:

1521 autotest emu part1
...

If you create extra .c or .h files, you will need to supply them explicitly to autotest; for example:

1521 autotest emu part1 extra1.c extra2.c extra3.h
...

Part 2: implementing execute_instruction

The second part of the assignment is to implement the function execute_instruction in execute_instruction.c, execute_instruction is given a MIPS instruction as a 32-bit unsigned integer value, You need to add code to execute_instruction which implements the instruction.

// If you use C library functions add includes here.

#include "emu.h"
#include "ram.h"
#include "registers.h"

/**
 * execute a MIPS instruction
 *
 * This function should:
 *
 * get register values by calling `get_register(register_type register_number)`
 * change registers by calling `set_register(register_type register_number, uint32_t value)`
 *
 * get memory values by `calling get_byte(uint32_t address)`
 * changes memory by `set_byte(uint32_t address, uint8_t value)`
 *
 * updates program_counter to address of next instruction
 *
 * returns 1 if an exit syscall is executed, 0 otherwise
 */
int execute_instruction(uint32_t instruction, uint32_t *program_counter) {
    // example code to implement add $4, $14, $12
    uint32_t x = get_register(14);
    uint32_t y = get_register(12);
    uint32_t sum = x + y;
    set_register(4, sum);

    // Update program_counter to address of next instructions
    // Most instructions will simply do the following:
    (*program_counter) += 4;
    // Jump & Branch instructions will do something different

    // 0 should be returned, unless an exit syscall is executed
    return 0;
}

// PUT EXTRA FUNCTIONS HERE

You implement instructions by appropriately calling the functions get_register, set_register, get_byte and set_byte. execute_instruction must also update the program counter.

emu has a -e option, will also accept assembler statements, convert them to integers, and calls execute_instruction for each integer, then print the value of registers. For example:

./emu -e 'add $4, $14, $12'
R0  [$zero] = 00000000
R1  [$at] = 00000000
R2  [$v0] = 00000000
R3  [$v1] = 00000000
R4  [$a0] = 0000000A
R5  [$a1] = 00000000
R6  [$a2] = 00000000
R7  [$a3] = 00000000
R8  [$t0] = 00000000
R9  [$t1] = 00000001
R10 [$t2] = 00000002
R11 [$t3] = 00000003
R12 [$t4] = 00000004
R13 [$t5] = 00000005
R14 [$t6] = 00000006
R15 [$t7] = 00000007
R16 [$s0] = 00000000
R17 [$s1] = 00000000
R18 [$s2] = 00000000
R19 [$s3] = 00000000
R20 [$s4] = 00000000
R21 [$s5] = 00000000
R22 [$s6] = 00000000
R23 [$s7] = 00000000
R24 [$t8] = 00000000
R25 [$t9] = 00000000
R26 [$k0] = 00000000
R27 [$k1] = 00000000
R28 [$gp] = 10008000
R29 [$sp] = 7FFFF8E4
R30 [$fp] = 00000000
R31 [$ra] = 00400018

Note that emu sets registers 9 to 16 to the values 1 through 7 before execution to have convenient values available for testing single instructions.

emu also has a -E option, which like -P takes a file of assembler statements, converts them to integers, and calls execute_instruction multiple times to execute them. For example:

./emu -E sum_100_squares.s
338350

emu can also be run interactively:

./emu add_memory.s
PC = [00400024] 34080011 ori $8, $0, 17
emu > h
In interactive mode, available commands are:
    s       step (execute one instruction)
    r       execute all remaining instructions
    q       quit
    h       this help message
    P       print Program
    R       print Registers
    D       print Data segment
    S       print Stack segment
    T       print Text segment
Entering nothing will re-send the previous command.

emu > R
R0  [$zero] = 00000000
R1  [$at] = 00000000
R2  [$v0] = 00000000
R3  [$v1] = 00000000
R4  [$a0] = 00000000
R5  [$a1] = 00000000
R6  [$a2] = 00000000
R7  [$a3] = 00000000
R8  [$t0] = 00000000
R9  [$t1] = 00000001
R10 [$t2] = 00000002
R11 [$t3] = 00000003
R12 [$t4] = 00000004
R13 [$t5] = 00000005
R14 [$t6] = 00000006
R15 [$t7] = 00000007
R16 [$s0] = 00000000
R17 [$s1] = 00000000
R18 [$s2] = 00000000
R19 [$s3] = 00000000
R20 [$s4] = 00000000
R21 [$s5] = 00000000
R22 [$s6] = 00000000
R23 [$s7] = 00000000
R24 [$t8] = 00000000
R25 [$t9] = 00000000
R26 [$k0] = 00000000
R27 [$k1] = 00000000
R28 [$gp] = 10008000
R29 [$sp] = 7FFFF8E4
R30 [$fp] = 00000000
R31 [$ra] = 00400018
PC = [00400024] 34080011 ori $8, $0, 17
emu > s
PC = [00400028] 3C011001 lui $1, 4097
emu > s
PC = [0040002C] AC280000 sw $8, 0($1)
emu > D
[10000000..1000FFFC] 00000000
[10010000] 00000011
[10010004] 00000019
[10010008] 0000002A

The assembly files you have been given will help you debug and test your execution_instruction. In addition, autotests are available to help with your testing:

1521 autotest emu part2
...

As before, if you create extra .c or .h files, you will need to supply them explicitly to autotest; for example:

1521 autotest emu part2 extra1.c extra2.c extra3.h
...

MIPS Architecture

You only need to implement the following subset of instructions and system calls; emu will only be tested on these.

MIPS Instructions

You need to implement only this subset of MIPS instructions:

The instruction 'Bit Pattern' uniquely identifies each instruction:

• 0: Literal bit zero
• 1: Literal bit one
• X: Immediate, print as hex with '0x' prefix
• I: Immediate, print as dec
• b: Base register field (number is the N in $N)
• O: Offset immediate, print as dec
• [lowercase letter]: Register field (number is the N in $N)

Arithmetic instruction should assume registers contain a signed 32-bit number. Arithmetical instruction should not attempt to stop overflows as a result of their operation.

Every instruction has a PC += 4 after the operation, except for instruction that directly change the program counter, such as branches or jumps.

System Calls

You only need to implement this subset of system calls.

Read String should read bytes until a newline is read or $a1 - 1 bytes have been read. It should fill the remainder of the buffer with zero bytes.

This means that a string will always be null-terminated and that any spare space in the buffer will be filled with zero bytes.

Print Character should print the lowest 8 bits of $a0.

You do not have to implement error handling for syscalls. You can assume a valid syscall number is supplied. You can assume valid arguments are supplied. You can assume any I/O (scanf, fgetc, fputc, fgets, printf) succeeds.

Assumptions and Clarifications

Like all good programmers, you should make as few assumptions as possible.

You can assume that your functions are given only valid instructions as listed in the table above, and that memory accesses are valid.

You do not have to implement MIPS instructions, system calls, or features which are not explicitly mentioned in the tables above. In particular, you do not have to implement or consider delay slots or traps, which are beyond the scope of this assignment.

If in doubt, match the output of the reference implementation.

You must submit execute_instruction.c and print_instruction.c. You cannot not change the supplied files (emu.c, emu.h, ram.c, ram.h, registers.c, and registers.h). You may optionally submit extra .c or .h files; if you do, add extra .c files to your emu.mk to ensure your code compiles. You may not submit other files.

Your submitted code must be C only. You may call functions from the standard C library (e.g., functions from stdio.h, stdlib.h, string.h, etc.) and the mathematics library (math.h). You may use assert.h.

You may not submit code in other languages. You may not use system or other C functions to run external programs. You may not use functions from other libraries; in other words, you cannot use dcc's -l flag.

If you need clarification on what you can and cannot use or do for this assignment, ask in the class forum.

You are required to submit intermediate versions of your assignment. See below for details.

Your program must not require extra compile options. It must compile with dcc *.c -o emu, and it will be run with dcc when marking. Run-time errors from illegal C will cause your code to fail automarking.

If your program writes out debugging output, it will fail automarking tests: make sure you disable debugging output before submission.

Change Log

Version 1.0
(2019-10-15 16:59:59)

• Initial release onto unsuspecting students.

Version 1.1
(2019-10-25 18:10:00)

• The reference implementation now uses a signed comparison for SLT.
• The reference implementation now implements sign extension for LB and LH.
• The reference implementation now prints a '!' after instructions not required by the assignment.

Version 1.2
(2019-10-28 16:00:00)

• The reference implementation now behaves more like SPIM with syscall 12.
• Updated registers.[ch] to follow new c_check rules when possible

Version 1.3
(2019-10-28 19:00:00)

• The reference implementation now prints bitwise immediates as unsigned

Version 1.4
(2019-10-29 08:00:00)

• syscall handling clarified

Version 1.5
(2019-10-29 11:30:00)

• Fixed typo in registers.h

Version 1.6
(2019-11-03 00:20:00)

• The reference implementation now stops execution on SYSCALL 10

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest emu

give cs1521 ass1_emu print_instruction.c execute_instruction.c [other .c or .h files]