Add a bytecode interpreter.

I wrote it in C because I actually like programming in C. Turns out
setting up a Makefile is really easy too.

14 files changed, 493 insertions, 0 deletions

diff --git a/bytecode/.gitignore b/bytecode/.gitignore
new file mode 100644
index 0000000..4052d93
--- /dev/null
+++ b/bytecode/.gitignore
@@ -0,0 +1,3 @@
+*.o
+*.d
+bytecode
diff --git a/bytecode/Makefile b/bytecode/Makefile
new file mode 100644
index 0000000..2e23fba
--- /dev/null
+++ b/bytecode/Makefile
@@ -0,0 +1,17 @@
+CFLAGS = -std=c11 -Wall -Wextra -Wpedantic -Werror -O3
+
+sources = $(wildcard *.c)
+
+default: bytecode
+
+bytecode: $(sources:.c=.o)
+
+%.d: %.c
+	$(CC) -MM $< > $@.$$$$ && \
+	sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.$$$$ > $@ && \
+	rm $@.$$$$
+
+include $(sources:.c=.d)
+
+clean:
+	rm *.o *.d bytecode
diff --git a/bytecode/bytecode.c b/bytecode/bytecode.c
new file mode 100644
index 0000000..a21231b
--- /dev/null
+++ b/bytecode/bytecode.c
@@ -0,0 +1,71 @@
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "oper.h"
+#include "panic.h"
+#include "slice.h"
+
+static struct slice xmalloc(size_t size)
+{
+	void *p = malloc(size);
+	if (!p) {
+		panicf("Out of memory!\n");
+	}
+	return (struct slice) {
+		.buf = p,
+		.size = size,
+	};
+}
+
+static struct slice xrealloc(void *ptr, size_t size)
+{
+	void *p = realloc(ptr, size);
+	if (!p) {
+		panicf("Out of memory!\n");
+	}
+	return (struct slice) {
+		.buf = p,
+		.size = size,
+	};
+}
+
+void read_file(struct slice *out, char *filename)
+{
+	FILE *f = fopen(filename, "r");
+	if (!f) {
+		panicf("File %s does not exit!\n", filename);
+	}
+	size_t offset = 0;
+	while (true) {
+		if (offset >= out->size) {
+			size_t new_size = 2 * out->size;
+			*out = xrealloc(out->buf, new_size);
+		}
+		size_t read_size = out->size - offset;
+		size_t n = fread(out->buf + offset, 1, read_size, f);
+		if (n < read_size) {
+			if (ferror(f)) {
+				panicf("Read error!\n");
+			}
+			out->size = offset + n;
+			return;
+		}
+		offset += n;
+	}
+}
+
+int main(int argc, char **argv)
+{
+	if (argc < 2) {
+		printf("Usage error: need a filename.\n");
+		return 1;
+	}
+
+	struct slice program = xmalloc(1);
+	read_file(&program, argv[1]);
+
+	run(program);
+
+	free(program.buf);
+}
diff --git a/bytecode/encoding.c b/bytecode/encoding.c
new file mode 100644
index 0000000..62c9762
--- /dev/null
+++ b/bytecode/encoding.c
@@ -0,0 +1,118 @@
+#include <stdint.h>
+#include <stdlib.h>
+
+#include "panic.h"
+#include "slice.h"
+#include "value.h"
+
+#include "encoding.h"
+
+struct reader {
+	struct slice data;
+	int n;
+};
+
+static void advance(struct reader *r, int size)
+{
+	r->data = slice1(r->data, size);
+	r->n += size;
+}
+
+static uint8_t parse_byte(struct reader *r)
+{
+	if (r->data.size < 1) {
+		panicf("read byte: no data!\n");
+	}
+	uint8_t res = r->data.buf[0];
+	advance(r, 1);
+	return res;
+}
+
+static local parse_local(struct reader *r)
+{
+	if (r->data.size < 1) {
+		panicf("local: no data!\n");
+	}
+	local res = r->data.buf[0];
+	if (res > 7) {
+		panicf("Invalid local (out of range): %d\n", res);
+	}
+	advance(r, 1);
+	return res;
+}
+
+static value parse_value(struct reader *r)
+{
+	if (r->data.size < 8) {
+		panicf("value: no data!\n");
+	}
+	uint64_t res = *(uint64_t *) r->data.buf;
+	advance(r, 8);
+	return res;
+}
+
+static struct arg parse_arg(struct reader *r, bool is_const)
+{
+	if (is_const) {
+		return (struct arg) { .constant = parse_value(r) };
+	}
+	return (struct arg) { .local = parse_local(r) };
+}
+
+static uint8_t parse_offset(struct reader *r)
+{
+	if (r->data.size < 1) {
+		panicf("offset: no data!\n");
+	}
+	uint8_t res = r->data.buf[0];
+	advance(r, 1);
+	return res;
+}
+
+struct result parse(struct slice data)
+{
+	struct reader r = { .data = data, .n = 0 };
+
+	uint8_t codeByte = parse_byte(&r);
+	enum opcode code = codeByte >> 2;
+	bool arg1_const = codeByte & 0x2;
+	// bool arg2_const = codeByte & 0x1;
+
+	struct op out = {
+		.code = code,
+	};
+
+	switch (code) {
+	case OALLOC:
+		out.alloc.out = parse_local(&r);
+		out.alloc.size = parse_arg(&r, arg1_const);
+		break;
+	case OCALL:
+		// No arguments.
+		break;
+	case OPOKE:
+		out.poke.offset = parse_offset(&r);
+		out.poke.pointer = parse_local(&r);
+		out.poke.value = parse_arg(&r, arg1_const);
+		break;
+	case OPEEK:
+		out.peek.out = parse_local(&r);
+		out.peek.offset = parse_offset(&r);
+		out.peek.value = parse_arg(&r, arg1_const);
+		break;
+	case OSHUF:
+		out.shuf.out = parse_local(&r);
+		out.shuf.value = parse_arg(&r, arg1_const);
+		break;
+	case OEXIT:
+		out.exit.value = parse_arg(&r, arg1_const);
+		break;
+	default:
+		panicf("Invalid code %d\n", code);
+	}
+
+	return (struct result) {
+		.op = out,
+		.n = r.n,
+	};
+}
diff --git a/bytecode/encoding.h b/bytecode/encoding.h
new file mode 100644
index 0000000..49357f6
--- /dev/null
+++ b/bytecode/encoding.h
@@ -0,0 +1,61 @@
+#ifndef _ENCODING_H_
+#define _ENCODING_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#include "slice.h"
+#include "value.h"
+
+typedef uint8_t local;
+
+// An arg can be a value or a constant.
+struct arg {
+	local local;
+	value constant;
+};
+
+enum opcode {
+	OALLOC = 1,
+	OCALL = 2,
+	OPOKE = 3,
+	OPEEK = 4,
+	OSHUF = 5,
+	OEXIT = 6,
+};
+
+struct op {
+	enum opcode code;
+	union {
+		struct {
+			local out;
+			struct arg size;
+		} alloc;
+		struct {
+			uint8_t offset;
+			local pointer;
+			struct arg value;
+		} poke;
+		struct {
+			local out;
+			uint8_t offset;
+			struct arg value;
+		} peek;
+		struct {
+			local out;
+			struct arg value;
+		} shuf;
+		struct {
+			struct arg value;
+		} exit;
+	};
+};
+
+struct result {
+	struct op op;
+	int n;
+};
+
+struct result parse(struct slice);
+
+#endif
diff --git a/bytecode/oper.c b/bytecode/oper.c
new file mode 100644
index 0000000..ed4a681
--- /dev/null
+++ b/bytecode/oper.c
@@ -0,0 +1,93 @@
+#include <stdbool.h>
+#include <stdlib.h>
+
+#include "encoding.h"
+#include "panic.h"
+#include "slice.h"
+#include "value.h"
+
+#include "oper.h"
+
+struct st {
+	size_t i;
+	value locals[8];
+};
+
+static value read_arg(struct st *s, struct arg arg)
+{
+	if (arg.constant) {
+		return arg.constant;
+	}
+	return s->locals[arg.local];
+}
+
+static void alloc(struct st *s, struct op oper)
+{
+	s->locals[oper.alloc.out] = from_pointer(calloc(to_int(read_arg(s, oper.alloc.size)), sizeof(value)));
+}
+
+static void call(struct st *s)
+{
+	s->i = to_int(s->locals[0]);
+}
+
+static void poke(struct st *s, struct op oper)
+{
+	value *p = to_pointer(s->locals[oper.poke.pointer]);
+	p[oper.poke.offset] = read_arg(s, oper.poke.value);
+}
+
+static void peek(struct st *s, struct op oper)
+{
+	value *p = to_pointer(read_arg(s, oper.peek.value));
+	s->locals[oper.peek.out] = p[oper.peek.offset];
+}
+
+static void shuf(struct st *s, struct op oper)
+{
+	s->locals[oper.shuf.out] = read_arg(s, oper.shuf.value);
+}
+
+static void oexit(struct st *s, struct op oper)
+{
+	exit(to_int(read_arg(s, oper.exit.value)));
+}
+
+static void op(struct st *s, struct op oper)
+{
+	switch (oper.code) {
+	case OALLOC:
+		alloc(s, oper);
+		break;
+	case OCALL:
+		call(s);
+		break;
+	case OPOKE:
+		poke(s, oper);
+		break;
+	case OPEEK:
+		peek(s, oper);
+		break;
+	case OSHUF:
+		shuf(s, oper);
+		break;
+	case OEXIT:
+		oexit(s, oper);
+		break;
+	default:
+		panicf("Invalid op: %x\n", oper.code);
+	}
+}
+
+void run(struct slice prog)
+{
+	struct st s = {
+		.i = 0,
+		.locals = { 0 },
+	};
+	while (true) {
+		struct result oper = parse(slice1(prog, s.i));
+		s.i += oper.n;
+		op(&s, oper.op);
+	}
+}
diff --git a/bytecode/oper.h b/bytecode/oper.h
new file mode 100644
index 0000000..f3bb688
--- /dev/null
+++ b/bytecode/oper.h
@@ -0,0 +1,8 @@
+#ifndef _OPER_H_
+#define _OPER_H_
+
+#include "slice.h"
+
+void run(struct slice);
+
+#endif
diff --git a/bytecode/panic.c b/bytecode/panic.c
new file mode 100644
index 0000000..db2b6f8
--- /dev/null
+++ b/bytecode/panic.c
@@ -0,0 +1,15 @@
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "panic.h"
+
+void panicf(const char *format, ...)
+{
+	va_list ap;
+	va_start(ap, format);
+	vfprintf(stderr, format, ap);
+	va_end(ap);
+
+	exit(1);
+}
diff --git a/bytecode/panic.h b/bytecode/panic.h
new file mode 100644
index 0000000..d9904a8
--- /dev/null
+++ b/bytecode/panic.h
@@ -0,0 +1,7 @@
+#ifndef _PANIC_H_
+#define _PANIC_H_
+
+// Prints a message to stderr and exits the process.
+void panicf(const char *, ...);
+
+#endif
diff --git a/bytecode/shell.nix b/bytecode/shell.nix
new file mode 100644
index 0000000..2b86acd
--- /dev/null
+++ b/bytecode/shell.nix
@@ -0,0 +1,6 @@
+{ pkgs ? import <nixpkgs> {} }:
+with pkgs;
+mkShell {
+  nativeBuildInputs = [ gcc gnumake valgrind gdb ];
+  hardeningDisable = [ "fortify" ];
+}
diff --git a/bytecode/slice.c b/bytecode/slice.c
new file mode 100644
index 0000000..c7b2820
--- /dev/null
+++ b/bytecode/slice.c
@@ -0,0 +1,15 @@
+#include <assert.h>
+
+#include "slice.h"
+
+struct slice slice(struct slice a, size_t i, size_t j)
+{
+	assert(i <= a.size && j <= a.size && i <= j);
+	return (struct slice) { .size = j - i, .buf = a.buf + i };
+}
+
+struct slice slice1(struct slice a, size_t i)
+{
+	assert(i <= a.size);
+	return (struct slice) { .size = a.size - i, .buf = a.buf + i };
+}
diff --git a/bytecode/slice.h b/bytecode/slice.h
new file mode 100644
index 0000000..509f7ca
--- /dev/null
+++ b/bytecode/slice.h
@@ -0,0 +1,16 @@
+#ifndef _SLICE_H_
+#define _SLICE_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+struct slice {
+	size_t size;
+	uint8_t *buf;
+};
+
+struct slice slice(struct slice, size_t, size_t);
+
+struct slice slice1(struct slice, size_t);
+
+#endif
diff --git a/bytecode/value.c b/bytecode/value.c
new file mode 100644
index 0000000..2a15b44
--- /dev/null
+++ b/bytecode/value.c
@@ -0,0 +1,42 @@
+#include <stdbool.h>
+#include <stdint.h>
+
+#include "panic.h"
+
+#include "value.h"
+
+bool is_int(value v)
+{
+	return v & 0x1;
+}
+
+int64_t to_int(value v)
+{
+	if (!is_int(v)) {
+		panicf("value %lx is not an int!\n", v);
+	}
+	return (int64_t) v >> 1;
+}
+
+value from_int(int64_t i)
+{
+	return i << 1 | 0x1;
+}
+
+bool is_pointer(value v)
+{
+	return v && !(v & 0x7);
+}
+
+value *to_pointer(value v)
+{
+	if (!is_pointer(v)) {
+		panicf("value %lx is not a pointer!\n", v);
+	}
+	return (value *) v;
+}
+
+value from_pointer(value *p)
+{
+	return (value) p;
+}
diff --git a/bytecode/value.h b/bytecode/value.h
new file mode 100644
index 0000000..3fa78c4
--- /dev/null
+++ b/bytecode/value.h
@@ -0,0 +1,21 @@
+#ifndef _VALUE_H_
+#define _VALUE_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+typedef uint64_t value;
+
+bool is_int(value);
+
+int64_t to_int(value);
+
+value from_int(int64_t);
+
+bool is_pointer(value);
+
+value *to_pointer(value);
+
+value from_pointer(value *);
+
+#endif