Implemented LC-3 with C traps

3 files changed, 420 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..7b720bc
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+lc3
+*.obj
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..8b71495
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,8 @@
+CFLAGS+=-Wall -Wextra -Wpedantic
+
+lc3:
+
+clean:
+	rm -f lc3
+
+.PHONY: clean
diff --git a/lc3.c b/lc3.c
new file mode 100644
index 0000000..5dc7112
--- /dev/null
+++ b/lc3.c
@@ -0,0 +1,410 @@
+#include <endian.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <signal.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <termios.h>
+#include <unistd.h>
+
+#include <sys/select.h>
+#include <sys/stat.h>
+#include <sys/time.h>
+#include <sys/types.h>
+
+enum Register
+{
+	REGISTER_R0 = 0,
+	REGISTER_R1,
+	REGISTER_R2,
+	REGISTER_R3,
+	REGISTER_R4,
+	REGISTER_R5,
+	REGISTER_R6,
+	REGISTER_R7,
+	REGISTER_PC,
+	REGISTER_COND,
+	REGISTER_COUNT,
+};
+
+enum Opcode
+{
+	OP_BR = 0,
+	OP_ADD,
+	OP_LD,
+	OP_ST,
+	OP_JSR,
+	OP_AND,
+	OP_LDR,
+	OP_STR,
+	OP_RTI,
+	OP_NOT,
+	OP_LDI,
+	OP_STI,
+	OP_JMP,
+	OP_RES,
+	OP_LEA,
+	OP_TRAP,
+};
+
+enum Flag
+{
+	FLAG_POS = 1u << 0,
+	FLAG_ZRO = 1u << 1,
+	FLAG_NEG = 1u << 2,
+};
+
+enum Trap
+{
+	TRAP_GETC = 0x20,
+	TRAP_OUT = 0x21,
+	TRAP_PUTS = 0x22,
+	TRAP_IN = 0x23,
+	TRAP_HALT = 0x25,
+};
+
+const uint16_t PC_START = 0x3000;
+const uint16_t KBSR = 0xfe00;
+const uint16_t KBDR = 0xfe02;
+
+uint16_t memory[UINT16_MAX];
+uint16_t registers[REGISTER_COUNT];
+
+struct termios tio;
+
+void die(int result, const char * str)
+{
+	if (-1 == result)
+	{
+		perror(str);
+		exit(EXIT_FAILURE);
+	}
+}
+
+void prepare_terminal()
+{
+	int r = tcgetattr(0, &tio);
+	die(r, "prepare_terminal tcgetattr()");
+	struct termios disabled = tio;
+	disabled.c_lflag &= ~ICANON & ~ECHO;
+	r = tcsetattr(0, TCSANOW, &disabled);
+	die(r, "prepare_terminal tcsetattr()");
+}
+
+void restore_terminal()
+{
+	int r = tcsetattr(0, TCSANOW, &tio);
+	die(r, "restore_terminal tcsetattr()");
+}
+
+void handle_interrupt(int signal)
+{
+	(void) signal;
+	restore_terminal();
+	exit(EXIT_FAILURE);
+}
+
+uint16_t sign_extend(uint16_t value, const int bits)
+{
+	const uint16_t mask = 1u << (bits - 1);
+	value &= (1u << bits) - 1;
+	return (value ^ mask) - mask;
+}
+
+uint16_t check_key()
+{
+	fd_set fds;
+	struct timeval tv;
+	FD_ZERO(&fds);
+	FD_SET(0, &fds);
+	tv.tv_sec = 0;
+	tv.tv_sec = 0;
+	const int r = select(1, &fds, NULL, NULL, &tv);
+	die(r, "check_key select()");
+	return 0 != r;
+}
+
+uint16_t read_memory(const uint16_t address)
+{
+	if (address == KBSR)
+	{
+		if (check_key())
+		{
+			memory[KBSR] = 1u << 15;
+			memory[KBDR] = getchar();
+		}
+		else
+		{
+			memory[KBSR] = 0;
+		}
+	}
+	return memory[address];
+}
+
+void write_memory(const uint16_t address, const uint16_t value)
+{
+	memory[address] = value;
+}
+
+void update_cond(const uint16_t reg)
+{
+	if (registers[reg] == 0)
+	{
+		registers[REGISTER_COND] = FLAG_ZRO;
+	}
+	else if (registers[reg] >> 15)
+	{
+		registers[REGISTER_COND] = FLAG_NEG;
+	}
+	else
+	{
+		registers[REGISTER_COND] = FLAG_POS;
+	}
+}
+
+void trap(const uint16_t instruction)
+{
+	switch (instruction & 0xff)
+	{
+		case TRAP_GETC:
+		{
+			uint8_t c;
+			ssize_t r = read(0, &c, 1);
+			die(r, "TRAP_GETC read()");
+			registers[REGISTER_R0] = (uint16_t) c;
+			break;
+		}
+		case TRAP_OUT:
+		{
+			uint8_t c = (uint8_t) registers[REGISTER_R0];
+			ssize_t r = write(1, &c, 1);
+			die(r, "TRAP_OUT write()");
+			break;
+		}
+		case TRAP_PUTS:
+		{
+			uint16_t * w = memory + registers[REGISTER_R0];
+			uint8_t c;
+			while (*w)
+			{
+				c = (uint8_t) *w;
+				ssize_t r = write(1, &c, 1);
+				die(r, "TRAP_PUTS write()");
+				++w;
+			}
+			fsync(0);
+			break;
+		}
+		case TRAP_IN:
+		{
+			printf("> ");
+			uint8_t c;
+			ssize_t r = read(0, &c, 1);
+			die(r, "TRAP_IN read()");
+			r = write(1, &c, 1);
+			die(r, "TRAP_IN write()");
+			registers[REGISTER_R0] = (uint16_t) c;
+			break;
+		}
+		case TRAP_HALT:
+			exit(EXIT_SUCCESS);
+		default:
+			exit(EXIT_FAILURE);
+	}
+}
+
+void step(const uint16_t instruction)
+{
+	const uint16_t opcode = instruction >> 12;
+	switch (opcode)
+	{
+		case OP_BR:
+		{
+			const uint16_t offset = sign_extend(instruction & 0x1ff, 9);
+			const uint16_t flag = (instruction >> 9) & 0x07;
+			if (flag & registers[REGISTER_COND])
+			{
+				registers[REGISTER_PC] += offset;
+			}
+			break;
+		}
+		case OP_ADD:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t lhs = (instruction >> 6) & 0x07;
+			const uint16_t immediate = (instruction >> 5) & 0x01;
+			if (immediate)
+			{
+				const uint16_t rhs = sign_extend(instruction & 0x1f, 5);
+				registers[dest] = registers[lhs] + rhs;
+			}
+			else
+			{
+				const uint16_t rhs = instruction & 0x07;
+				registers[dest] = registers[lhs] + registers[rhs];
+			}
+			update_cond(dest);
+			break;
+		}
+		case OP_LD:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x1ff, 9);
+			registers[dest] = read_memory(registers[REGISTER_PC] + offset);
+			update_cond(dest);
+			break;
+		}
+		case OP_ST:
+		{
+			const uint16_t src = (instruction >> 9) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x1ff, 9);
+			const uint16_t address = registers[REGISTER_PC] + offset;
+			write_memory(address, registers[src]);
+			break;
+		}
+		case OP_JSR:
+		{
+			const uint16_t long_jump = (instruction >> 11) & 1;
+			registers[REGISTER_R7] = registers[REGISTER_PC];
+			if (long_jump)
+			{
+				const uint16_t offset = sign_extend(instruction & 0x7ff, 11);
+				registers[REGISTER_PC] += offset;
+			}
+			else
+			{
+				const uint16_t src = (instruction >> 6) & 0x07;
+				registers[REGISTER_PC] = registers[src];
+			}
+			break;
+		}
+		case OP_AND:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t lhs = (instruction >> 6) & 0x07;
+			const uint16_t immediate = (instruction >> 5) & 0x01;
+			if (immediate)
+			{
+				const uint16_t rhs = sign_extend(instruction & 0x1f, 5);
+				registers[dest] = registers[lhs] & rhs;
+			}
+			else
+			{
+				const uint16_t rhs = instruction & 0x07;
+				registers[dest] = registers[lhs] & registers[rhs];
+			}
+			update_cond(dest);
+			break;
+		}
+		case OP_LDR:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t src = (instruction >> 6) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x3f, 6);
+			const uint16_t address = registers[src] + offset;
+			registers[dest] = read_memory(address);
+			update_cond(dest);
+			break;
+		}
+		case OP_STR:
+		{
+			const uint16_t src = (instruction >> 9) & 0x07;
+			const uint16_t dest = (instruction >> 6) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x3f, 6);
+			const uint16_t address = registers[dest] + offset;
+			write_memory(address, registers[src]);
+			break;
+		}
+		case OP_NOT:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t src = (instruction >> 6) & 0x07;
+			registers[dest] = ~registers[src];
+			update_cond(dest);
+			break;
+		}
+		case OP_LDI:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x1ff, 9);
+			const uint16_t address = read_memory(registers[REGISTER_PC] + offset);
+			registers[dest] = read_memory(address);
+			update_cond(dest);
+			break;
+		}
+		case OP_STI:
+		{
+			const uint16_t src = (instruction >> 9) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x1ff, 9);
+			const uint16_t address = read_memory(registers[REGISTER_PC] + offset);
+			write_memory(address, registers[src]);
+			break;
+		}
+		case OP_JMP:
+		{
+			const uint16_t src = (instruction >> 6) & 0x07;
+			registers[REGISTER_PC] = registers[src];
+			break;
+		}
+		case OP_LEA:
+		{
+			const uint16_t dest = (instruction >> 9) & 0x07;
+			const uint16_t offset = sign_extend(instruction & 0x1ff, 9);
+			registers[dest] = registers[REGISTER_PC] + offset;
+			update_cond(dest);
+			break;
+		}
+		case OP_TRAP:
+			trap(instruction);
+			break;
+		case OP_RTI:
+		case OP_RES:
+		default:
+			exit(EXIT_FAILURE);
+	}
+}
+
+int read_image(const char * path)
+{
+	const int fd = open(path, O_RDONLY);
+	if (-1 == fd)
+	{
+		return -1;
+	}
+	uint16_t origin;
+	ssize_t length = read(fd, &origin, sizeof(origin));
+	die(length, "read_image read origin");
+	origin = be16toh(origin);
+	const size_t maximum = UINT16_MAX - origin;
+	uint16_t * dest = memory + origin;
+	length = read(fd, dest, maximum * sizeof(origin));
+	die(length, "read_image read dest");
+	for (; length > 0; length -= 2)
+	{
+		*dest = be16toh(*dest);
+		dest++;
+	}
+	return close(fd);
+}
+
+int main(int argc, char ** argv)
+{
+	if (argc < 2)
+	{
+		exit(EXIT_FAILURE);
+	}
+	for (int i = 1; i < argc; ++i)
+	{
+		die(read_image(argv[i]), "read_image");
+	}
+	signal(SIGINT, handle_interrupt);
+	atexit(restore_terminal);
+	prepare_terminal();
+	registers[REGISTER_PC] = PC_START;
+	for (;;)
+	{
+		const uint16_t instruction = read_memory(registers[REGISTER_PC]++);
+		step(instruction);
+	}
+}