From 98cef5e9a772602d42acfcf233838c760424db9a Mon Sep 17 00:00:00 2001 From: Nicolas James Date: Thu, 13 Feb 2025 18:00:17 +1100 Subject: initial commit --- comp1521/smips/helper.c | 54 +++++++++++ comp1521/smips/input.c | 52 +++++++++++ comp1521/smips/input.h | 12 +++ comp1521/smips/instr.c | 160 +++++++++++++++++++++++++++++++ comp1521/smips/instr.h | 103 ++++++++++++++++++++ comp1521/smips/smips.c | 243 ++++++++++++++++++++++++++++++++++++++++++++++++ comp1521/smips/smips.h | 20 ++++ 7 files changed, 644 insertions(+) create mode 100644 comp1521/smips/helper.c create mode 100644 comp1521/smips/input.c create mode 100644 comp1521/smips/input.h create mode 100644 comp1521/smips/instr.c create mode 100644 comp1521/smips/instr.h create mode 100644 comp1521/smips/smips.c create mode 100644 comp1521/smips/smips.h (limited to 'comp1521/smips') diff --git a/comp1521/smips/helper.c b/comp1521/smips/helper.c new file mode 100644 index 0000000..ebe798b --- /dev/null +++ b/comp1521/smips/helper.c @@ -0,0 +1,54 @@ +#include "helper.h" + +// Returns the n'th bit of a uint32_t value. +uint32_t get_nth_bit(const uint32_t value, const int n) { + return (value & (1u << n)) >> n; +} + +// Prints the bits of a uint32_t value. +void print_bits(const uint32_t value) { + for (int i = (int)sizeof(uint32_t)*8-1; i >= 0; --i) { + printf("%d", get_nth_bit(value, i)); + } + printf("\n"); +} + +// Skips past the next newline. +// If EOF, stays on EOF so that subsequent fgetc() calls return EOF. +void skip_past_newline(FILE *const fptr) { + int c = 0; + c = fgetc(fptr); + while (true) { + if (c == EOF) { + fseek(fptr, -1L, SEEK_CUR); + return; + } + else if (c == '\n') { + printf("newline\n"); + return; + } else { + fseek(fptr, -1L, SEEK_CUR); + return; + } + printf("skipping char\n"); + c = fgetc(fptr); + } +} + +// Converts decimal values to hex obviously. +uint32_t hex_to_decimal(const uint32_t decimal) { + uint32_t ret = 0; + for (size_t i = 0; i < sizeof(uint32_t); ++i) { // Iterate through 4 bytes. + uint32_t tmp = (decimal & (0xFFu << 8*i)) >> 8*i; + if (isalpha(tmp)) { + tmp -= 'a'; + tmp += 10; + } + else if (isdigit(tmp)) { + tmp -= '0'; + } + // There should be no other cases if the input is hex. + ret |= (tmp << 4*i); + } + return ret; +} diff --git a/comp1521/smips/input.c b/comp1521/smips/input.c new file mode 100644 index 0000000..0932978 --- /dev/null +++ b/comp1521/smips/input.c @@ -0,0 +1,52 @@ +#include "input.h" + +// Converts decimal values of a uint32_t argument to hex. +uint32_t hex_to_decimal(const uint32_t decimal) { + uint32_t ret = 0; + for (size_t i = 0; i < sizeof(uint32_t); ++i) { // Iterate through 4 bytes. + uint32_t tmp = (decimal & (0xFFu << 8 * i)) >> 8 * i; + if (isalpha(tmp)) { + tmp -= 'a'; + tmp += 10; + } else if (isdigit(tmp)) { + tmp -= '0'; + } + // There should be no other cases if the input is hex. + ret |= (tmp << 4 * i); + } + return ret; +} + +// Returns the next instruction in hex. Returns 0 if EOF reached. +uint32_t get_next_instruction(FILE *const iptr) { + uint32_t ret = 0; + int i = 0; + for (int c = fgetc(iptr); c != '\n'; c = fgetc(iptr), ++i) { + if (c == EOF) { + return 0u; + } + uint32_t tmp = hex_to_decimal((uint32_t)c); + ret |= (tmp << (28 - i * 4)); + } + // We have to take into account the potential for the hex value to not be + // "full", ie we may read abc instead of 00000abc. + ret >>= (32 - i * 4); + return ret; +} + +// Sets the iptr to the previous instruction, which sits on the newline so that +// later calls to get_next_instruction work as expected. +// Also, if unable to find a previous instruction, sets the iptr to EOF. +void goto_previous_instruction(FILE *const iptr) { + int c = 0; + fseek(iptr, -2L, SEEK_CUR); + while (ftell(iptr)) { + c = fgetc(iptr); + if (c == '\n') { + return; + } + fseek(iptr, -2L, SEEK_CUR); + } + // Start of file reached, out of bounds, so set EOF. + fseek(iptr, 0L, SEEK_END); +} diff --git a/comp1521/smips/input.h b/comp1521/smips/input.h new file mode 100644 index 0000000..44ac0c9 --- /dev/null +++ b/comp1521/smips/input.h @@ -0,0 +1,12 @@ +#ifndef INPUT_H_ +#define INPUT_H_ + +#include +#include +#include + +uint32_t hex_to_decimal(const uint32_t decimal); +uint32_t get_next_instruction(FILE *const iptr); +void goto_previous_instruction(FILE *const iptr); + +#endif diff --git a/comp1521/smips/instr.c b/comp1521/smips/instr.c new file mode 100644 index 0000000..645fbae --- /dev/null +++ b/comp1521/smips/instr.c @@ -0,0 +1,160 @@ +#include "instr.h" + +// Gets the immediate bits, clearing others and shifting right. +uint32_t get_i(const uint32_t instr) { return instr & IMMEDIATE_BITS; } + +// Gets the pattern bits, clearing others and shifting right. +uint32_t get_p(const uint32_t instr) { return (instr & PATTERN_BITS) >> 26; } + +// Gets the d bits, clearing others and shifting right. +uint32_t get_d(const uint32_t instr) { return (instr & D_BITS) >> 11; } + +// Gets the t bits, clearing others and shifting right. +uint32_t get_t(const uint32_t instr) { return (instr & T_BITS) >> 16; } + +// Gets the s bits, clearing others and shifting right. +uint32_t get_s(const uint32_t instr) { return (instr & S_BITS) >> 21; } + +// $d = $s + $t. +void mips_add(const uint32_t instr, uint32_t registers[32]) { + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[d] = registers[s] + registers[t]; +} + +// $d = $s - $t. +void mips_sub(const uint32_t instr, uint32_t registers[32]) { + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[d] = registers[s] - registers[t]; +} +// $d = $s & $t. +void mips_and(const uint32_t instr, uint32_t registers[32]) { + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[d] = registers[s] & registers[t]; +} + +// $d = $s | $t. +void mips_or(const uint32_t instr, uint32_t registers[32]) { + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[d] = registers[s] | registers[t]; +} + +// $d = ($s < $t). +void mips_slt(const uint32_t instr, uint32_t registers[32]) { + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[d] = registers[s] < registers[t]; +} + +// $d = $s * $t. +void mips_mul(const uint32_t instr, uint32_t registers[32]) { + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[d] = registers[s] * registers[t]; +} + +// If ($s == $t) PC += i. +void mips_beq(FILE *const fptr, const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + if (registers[s] != registers[t]) { + return; + } + if (i >= 0) { + for (int j = 0; j <= i; ++j) { + get_next_instruction(fptr); + } + } else { + for (int j = 0; j <= -1 * i; ++j) { + goto_previous_instruction(fptr); + } + } +} + +// If ($s != $t) PC += i. +void mips_bne(FILE *const fptr, const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + if (registers[s] == registers[t]) { + return; + } + if (i >= 0) { + for (int j = 0; j <= i; ++j) { + get_next_instruction(fptr); + } + } else { + for (int j = 0; j <= -1 * i; ++j) { + goto_previous_instruction(fptr); + } + } +} + +// $t = $s + i. +void mips_addi(const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[t] = registers[s] + (uint32_t)i; +} + +// $t = $s < i. +void mips_slti(const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[t] = registers[s] < (uint32_t)i; +} + +// $t = $s & i. +void mips_andi(const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[t] = registers[s] & (uint32_t)i; +} + +// $t = $s | i. +void mips_ori(const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + registers[t] = registers[s] | (uint32_t)i; +} + +// $t = i << 16u. +void mips_lui(const uint32_t instr, uint32_t registers[32]) { + int i = (int16_t)get_i(instr); + int t = (int16_t)get_t(instr); + registers[t] = (uint32_t)i << 16u; +} + +// Syscall function which returns non-zero if execution should stop. +int mips_syscall(uint32_t registers[32]) { + uint32_t v0 = registers[2]; + uint32_t a0 = registers[4]; + switch (v0) { + case 1: + printf("%u", a0); + break; + case 11: + printf("%c", a0 & 0xFFu); + break; + case 10: + return 1; + default: + printf("Unknown system call: %d\n", v0); + return 1; + } + return 0; +} diff --git a/comp1521/smips/instr.h b/comp1521/smips/instr.h new file mode 100644 index 0000000..720d32f --- /dev/null +++ b/comp1521/smips/instr.h @@ -0,0 +1,103 @@ +#ifndef INSTR_H_ +#define INSTR_H_ + +#include +#include +#include + +#include "input.h" + +// We have to use bit masks to identify the instruction we are to perform. +// Instructions are stored in a uint32_t, and inputted from hex. +// The format of the bit masks vary between +// +// PPPPPP SSSSS TTTTT DDDDD IIIIIIIIIII +// 6 5 5 5 11 +// +// PPPPPP SSSSS TTTTT IIIIIIIIIIIIIIII +// 6 5 5 16 +// +// P = pattern_mask +// S = five bit register number +// T = five bit register number +// D = five bit register number +// I = immediate mask (size can very between instructions) + +// Definitions for 32 bit instruction bits. +#define PATTERN_BITS 0xFC000000 // 11111100000000000000000000000000 +#define IMMEDIATE_BITS 0xFFFF // 00000000000000001111111111111111 +#define SHORT_IMMEDIATE_BITS 0x7FF // 00000000000000000000011111111111 +#define S_BITS 0x3e00000 // 00000011111000000000000000000000 +#define T_BITS 0x1f0000 // 00000000000111110000000000000000 +#define D_BITS 0xf800 // 00000000000000001111100000000000 + +// Contains bit masks for instructions for the immediate field. +enum immediate_mask { + im_add = 0x20u, // 100000 + im_sub = 0x22u, // 100010 + im_and = 0x24u, // 100100 + im_or = 0x25u, // 100101 + im_slt = 0x2au, // 101010 + im_mul = 0x2u, // 000010 + im_syscall = 0xcu // 001100 +}; + +// Contains bit masks for the pattern field. +enum pattern_mask { + pm_add = 0x0u, // 000000 + pm_sub = 0x0u, // 000000 + pm_and = 0x0u, // 000000 + pm_or = 0x0u, // 000000 + pm_slt = 0x0u, // 000000 + pm_mul = 0x1cu, // 011100 + pm_beq = 0x4u, // 000100 + pm_bne = 0x5u, // 000101 + pm_addi = 0x8u, // 001000 + pm_slti = 0xau, // 001010 + pm_andi = 0xcu, // 001100 + pm_ori = 0xdu, // 001101 + pm_lui = 0xfu, // 001111 +}; + +// Contains an enum representing instructions. +enum instructions { + add, + sub, + and, + or, + slt, + mul, + beq, + bne, + addi, + slti, + andi, + ori, + lui, + syscall +}; + +// Functions which extract bitfields from an instruction. +uint32_t get_i(const uint32_t instr); +uint32_t get_p(const uint32_t instr); +uint32_t get_d(const uint32_t instr); +uint32_t get_t(const uint32_t instr); +uint32_t get_s(const uint32_t instr); + +// Functions which emulate mips instructions. +void mips_add(const uint32_t instr, uint32_t registers[32]); +void mips_sub(const uint32_t instr, uint32_t registers[32]); +void mips_and(const uint32_t instr, uint32_t registers[32]); +void mips_or(const uint32_t instr, uint32_t registers[32]); +void mips_slt(const uint32_t instr, uint32_t registers[32]); +void mips_mul(const uint32_t instr, uint32_t registers[32]); +void mips_beq(FILE *const fptr, const uint32_t instr, uint32_t registers[32]); +void mips_bne(FILE *const fptr, const uint32_t instr, uint32_t registers[32]); +void mips_addi(const uint32_t instr, uint32_t registers[32]); +void mips_slti(const uint32_t instr, uint32_t registers[32]); +void mips_andi(const uint32_t instr, uint32_t registers[32]); +void mips_ori(const uint32_t instr, uint32_t registers[32]); +void mips_lui(const uint32_t instr, uint32_t registers[32]); +int mips_syscall(uint32_t registers[32]); + +#endif diff --git a/comp1521/smips/smips.c b/comp1521/smips/smips.c new file mode 100644 index 0000000..19acd73 --- /dev/null +++ b/comp1521/smips/smips.c @@ -0,0 +1,243 @@ +// July 2020. +// Simple mips emulator which only reads hex instructions. + +#include "smips.h" + +// Prints an instruction and its variables based off a supplied type. +static void print_wrapper(const uint32_t instr, const char *name, const int type) { + int i = (int16_t)get_i(instr); + int d = (int16_t)get_d(instr); + int t = (int16_t)get_t(instr); + int s = (int16_t)get_s(instr); + switch (type) { + case DST: + printf("%-4s $%d, $%d, $%d", name, d, s, t); + break; + case STI: + printf("%-4s $%d, $%d, %d", name, s, t, i); + break; + case TSI: + printf("%-4s $%d, $%d, %d", name, t, s, i); + break; + case TI: + printf("%-4s $%d, %d", name, t, i); + break; + } +} + +// Returns the instruction type as defined in the instr enum. +// Returns >= 0 if the instruction was found. +static int query_instruction(const uint32_t instr) { + uint32_t pattern = get_p(instr); + uint32_t immediate = get_i(instr); + + // Syscall, mul and lui are special cases which should be dealt with before + // we move into the switch statatement. + if (pattern == pm_mul && (immediate & SHORT_IMMEDIATE_BITS) == im_mul) { + return mul; + } else if (instr == im_syscall) { + return syscall; + } else if (get_p(instr) == pm_lui && get_s(instr) == 0) { + return lui; + } + + // If the pattern bits are empty, we are dealing with instructions between + // add and slt inclusive. This is only true after the special cases of mul, + // syscall and lui are dealt with. The others can be encapsulated in an + // else. + if (!pattern) { + switch (immediate & SHORT_IMMEDIATE_BITS) { + case im_add: + return add; + case im_sub: + return sub; + case im_and: + return and; + case im_or: + return or ; + case im_slt: + return slt; + default: + return -1; + } + } else { + switch (pattern) { + case pm_beq: + return beq; + case pm_bne: + return bne; + case pm_addi: + return addi; + case pm_slti: + return slti; + case pm_andi: + return andi; + case pm_ori: + return ori; + default: + return -1; + } + } + return 0; +} + +// Calls print wrapper with the correct name char *. +static void print_instruction(const uint32_t instr) { + switch (query_instruction(instr)) { + case mul: + print_wrapper(instr, "mul", DST); + break; + case lui: + print_wrapper(instr, "lui", TI); + break; + case syscall: + printf("syscall"); + break; + case add: + print_wrapper(instr, "add", DST); + break; + case sub: + print_wrapper(instr, "sub", DST); + break; + case and: + print_wrapper(instr, "and", DST); + break; + case or: + print_wrapper(instr, "or", DST); + break; + case slt: + print_wrapper(instr, "slt", DST); + break; + case beq: + print_wrapper(instr, "beq", STI); + break; + case bne: + print_wrapper(instr, "bne", STI); + break; + case addi: + print_wrapper(instr, "addi", STI); + break; + case slti: + print_wrapper(instr, "slti", TSI); + break; + case andi: + print_wrapper(instr, "andi", TSI); + break; + case ori: + print_wrapper(instr, "ori", TSI); + break; + } +} + +// Executes a mips_? function based off the enum returned from the +// query_instruction function. Non-zero values indicates execution should stop. +static int execute_instruction(FILE *const iptr, const uint32_t instr, + uint32_t registers[32]) { + // At this point, guaranteed to be known instructions. + switch (query_instruction(instr)) { + case add: + mips_add(instr, registers); + break; + case sub: + mips_sub(instr, registers); + break; + case and: + mips_and(instr, registers); + break; + case or: + mips_or(instr, registers); + break; + case slt: + mips_slt(instr, registers); + break; + case mul: + mips_mul(instr, registers); + break; + case beq: + mips_beq(iptr, instr, registers); + break; + case bne: + mips_bne(iptr, instr, registers); + break; + case addi: + mips_addi(instr, registers); + break; + case slti: + mips_slti(instr, registers); + break; + case andi: + mips_andi(instr, registers); + break; + case ori: + mips_ori(instr, registers); + break; + case lui: + mips_lui(instr, registers); + break; + case syscall: + return mips_syscall(registers); + break; + } + // We need to restore $0, which should always be zero. So after each + // instruction, simply set it back to 0. Syscalls do not touch $0! + registers[0] = 0; + return 0; +} + +int main(const int argc, const char *argv[]) { + if (argc < 2) { + printf("Not enough arguments!\n"); + return EXIT_FAILURE; + } + FILE *iptr = fopen(argv[1], "r"); + if (iptr == NULL) { + printf("File does not exist!\n"); + return EXIT_FAILURE; + } + // We will read through program first, then perform a loop which + // reads out the instructions, loop which executes the instructions, then + // finally a loop which prints changed registers. + int i = 1; + uint32_t instr = 0; + while ((instr = get_next_instruction(iptr))) { // Proofread loop. + if (query_instruction(instr) == -1) { + printf("%s:%d: invalid instruction code: %08x\n", argv[1], i, + instr); + return EXIT_FAILURE; + } + ++i; + } + rewind(iptr); + + i = 0; + printf("Program\n"); + while ((instr = get_next_instruction(iptr))) { // Print loop. + printf("%3d: ", i); + print_instruction(instr); + printf("\n"); + ++i; + } + rewind(iptr); + + uint32_t registers[32] = {0}; + printf("Output\n"); + while ((instr = get_next_instruction(iptr))) { // Execution loop. + // The iptr may change after execute_instruction runs due to branch + // instructions. + // In addition, execute instruction returns a non-zero if execution + // should stop due to syscalls, etc. + if (execute_instruction(iptr, instr, registers)) { + break; + } + } + + printf("Registers After Execution\n"); // Print registers loop. + for (size_t j = 0; j < sizeof(registers) / sizeof(uint32_t); ++j) { + if (registers[j]) { + printf("$%-2d = %u\n", (int)j, registers[j]); + } + } + + fclose(iptr); + return EXIT_SUCCESS; +} diff --git a/comp1521/smips/smips.h b/comp1521/smips/smips.h new file mode 100644 index 0000000..94edf90 --- /dev/null +++ b/comp1521/smips/smips.h @@ -0,0 +1,20 @@ +#ifndef SMIPS_H_ +#define SMIPS_H_ + +#include +#include +#include +#include +#include + +#include "input.h" // Contains functions for input and file processing. +#include "instr.h" // Contains mips related instructions and bitmasks. + +// Definitions for printing multipliers (read print_wrapper). +#define DST 1 +#define STI 2 +#define TSI 3 +#define TI 4 +#define SYSCALL 5 + +#endif -- cgit v1.2.3