From 4c3b2fec322feb8afd23703866d81f1dda51b6ae Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sat, 11 Feb 2023 09:41:54 -0800 Subject: 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. --- bytecode/.gitignore | 3 ++ bytecode/Makefile | 17 ++++++++ bytecode/bytecode.c | 71 +++++++++++++++++++++++++++++++ bytecode/encoding.c | 118 ++++++++++++++++++++++++++++++++++++++++++++++++++++ bytecode/encoding.h | 61 +++++++++++++++++++++++++++ bytecode/oper.c | 93 +++++++++++++++++++++++++++++++++++++++++ bytecode/oper.h | 8 ++++ bytecode/panic.c | 15 +++++++ bytecode/panic.h | 7 ++++ bytecode/shell.nix | 6 +++ bytecode/slice.c | 15 +++++++ bytecode/slice.h | 16 +++++++ bytecode/value.c | 42 +++++++++++++++++++ bytecode/value.h | 21 ++++++++++ 14 files changed, 493 insertions(+) create mode 100644 bytecode/.gitignore create mode 100644 bytecode/Makefile create mode 100644 bytecode/bytecode.c create mode 100644 bytecode/encoding.c create mode 100644 bytecode/encoding.h create mode 100644 bytecode/oper.c create mode 100644 bytecode/oper.h create mode 100644 bytecode/panic.c create mode 100644 bytecode/panic.h create mode 100644 bytecode/shell.nix create mode 100644 bytecode/slice.c create mode 100644 bytecode/slice.h create mode 100644 bytecode/value.c create mode 100644 bytecode/value.h (limited to 'bytecode') 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 +#include +#include + +#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 +#include + +#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 +#include + +#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 +#include + +#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 +#include +#include + +#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 {} }: +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 + +#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 +#include + +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 +#include + +#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 +#include + +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 -- cgit v1.3.1