From 17face3633686e374aa0859271ccf462a48e60aa Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sun, 4 Feb 2024 16:46:20 -0800 Subject: Rewrite the bytecode interpreter in Rust. --- bytecode/.gitignore | 4 +- bytecode/Cargo.lock | 7 +++ bytecode/Cargo.toml | 8 +++ bytecode/Makefile | 17 ------ bytecode/byte_slice.h | 10 ---- bytecode/bytecode.c | 59 ------------------- bytecode/encoding.c | 118 -------------------------------------- bytecode/encoding.h | 63 --------------------- bytecode/heap.c | 125 ---------------------------------------- bytecode/heap.h | 27 --------- bytecode/oper.c | 97 ------------------------------- bytecode/oper.h | 8 --- bytecode/panic.c | 15 ----- bytecode/panic.h | 7 --- bytecode/shell.nix | 6 -- bytecode/slice.h | 33 ----------- bytecode/src/encoding.rs | 139 +++++++++++++++++++++++++++++++++++++++++++++ bytecode/src/heap.rs | 144 +++++++++++++++++++++++++++++++++++++++++++++++ bytecode/src/main.rs | 87 ++++++++++++++++++++++++++++ bytecode/src/value.rs | 31 ++++++++++ bytecode/value.c | 42 -------------- bytecode/value.h | 21 ------- bytecode/value_slice.h | 9 --- 23 files changed, 417 insertions(+), 660 deletions(-) create mode 100644 bytecode/Cargo.lock create mode 100644 bytecode/Cargo.toml delete mode 100644 bytecode/Makefile delete mode 100644 bytecode/byte_slice.h delete mode 100644 bytecode/bytecode.c delete mode 100644 bytecode/encoding.c delete mode 100644 bytecode/encoding.h delete mode 100644 bytecode/heap.c delete mode 100644 bytecode/heap.h delete mode 100644 bytecode/oper.c delete mode 100644 bytecode/oper.h delete mode 100644 bytecode/panic.c delete mode 100644 bytecode/panic.h delete mode 100644 bytecode/shell.nix delete mode 100644 bytecode/slice.h create mode 100644 bytecode/src/encoding.rs create mode 100644 bytecode/src/heap.rs create mode 100644 bytecode/src/main.rs create mode 100644 bytecode/src/value.rs delete mode 100644 bytecode/value.c delete mode 100644 bytecode/value.h delete mode 100644 bytecode/value_slice.h diff --git a/bytecode/.gitignore b/bytecode/.gitignore index 4052d93..ea8c4bf 100644 --- a/bytecode/.gitignore +++ b/bytecode/.gitignore @@ -1,3 +1 @@ -*.o -*.d -bytecode +/target diff --git a/bytecode/Cargo.lock b/bytecode/Cargo.lock new file mode 100644 index 0000000..f495832 --- /dev/null +++ b/bytecode/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "bytecode" +version = "0.1.0" diff --git a/bytecode/Cargo.toml b/bytecode/Cargo.toml new file mode 100644 index 0000000..8303233 --- /dev/null +++ b/bytecode/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "bytecode" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/bytecode/Makefile b/bytecode/Makefile deleted file mode 100644 index 2e23fba..0000000 --- a/bytecode/Makefile +++ /dev/null @@ -1,17 +0,0 @@ -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/byte_slice.h b/bytecode/byte_slice.h deleted file mode 100644 index 7109b52..0000000 --- a/bytecode/byte_slice.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef _BYTE_SLICE_H_ -#define _BYTE_SLICE_H_ - -#include - -#include "slice.h" - -DEFINE_SLICE(uint8_t) - -#endif diff --git a/bytecode/bytecode.c b/bytecode/bytecode.c deleted file mode 100644 index 9ac4a1e..0000000 --- a/bytecode/bytecode.c +++ /dev/null @@ -1,59 +0,0 @@ -#include -#include -#include - -#include "oper.h" -#include "panic.h" -#include "byte_slice.h" - -static uint8_t_slice xrealloc(void *ptr, size_t size) -{ - void *p = realloc(ptr, size); - if (!p) { - panicf("Out of memory!\n"); - } - return (uint8_t_slice) { - .buf = p, - .size = size, - }; -} - -static uint8_t_slice read_file(char *filename) -{ - FILE *f = fopen(filename, "r"); - if (!f) { - panicf("File %s does not exit!\n", filename); - } - uint8_t_slice out = { .size = 0, .buf = NULL }; - size_t offset = 0; - while (true) { - if (offset >= out.size) { - size_t new_size = 2 * out.size + 1; - 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"); - } - return uint8_t_slice2(out, 0, offset + n); - } - offset += n; - } -} - -int main(int argc, char **argv) -{ - if (argc < 2) { - printf("Usage error: need a filename.\n"); - return 1; - } - - uint8_t_slice program = read_file(argv[1]); - - run(program); - - // run never returns. I'm just putting this here to taunt you: - free(program.buf); -} diff --git a/bytecode/encoding.c b/bytecode/encoding.c deleted file mode 100644 index 246e944..0000000 --- a/bytecode/encoding.c +++ /dev/null @@ -1,118 +0,0 @@ -#include -#include - -#include "panic.h" -#include "byte_slice.h" -#include "value.h" - -#include "encoding.h" - -struct reader { - uint8_t_slice data; - int n; -}; - -static void advance(struct reader *r, int size) -{ - r->data = uint8_t_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 >= NUM_LOCALS) { - 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(uint8_t_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 deleted file mode 100644 index 9d4da14..0000000 --- a/bytecode/encoding.h +++ /dev/null @@ -1,63 +0,0 @@ -#ifndef _ENCODING_H_ -#define _ENCODING_H_ - -#include -#include - -#include "byte_slice.h" -#include "value.h" - -typedef uint8_t local; - -#define NUM_LOCALS 8 - -// 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(uint8_t_slice); - -#endif diff --git a/bytecode/heap.c b/bytecode/heap.c deleted file mode 100644 index 1ba5faf..0000000 --- a/bytecode/heap.c +++ /dev/null @@ -1,125 +0,0 @@ -#include -#include -#include - -#include "encoding.h" -#include "heap.h" -#include "panic.h" -#include "value.h" -#include "value_slice.h" - -struct heap new_heap(value_slice gc_roots) -{ - return (struct heap) { - .buf = NULL, - .active = { .size = 0 }, - .standby = { .size = 0 }, - .free_ptr = 0, - .last_free = 0, - .gc_roots = gc_roots, - }; -} - -static bool forwarded(struct heap *h, value *p) -{ - if (!is_pointer(*p)) { - return false; - } - value *q = to_pointer(*p); - return h->active.buf <= q && q <= h->active.buf + h->active.size; -} - -static size_t alloc_size(value *p) -{ - return p[-1] >> 1; -} - -static value *simple_alloc(struct heap *h, int64_t size) -{ - h->active.buf[h->free_ptr] = size << 1; - value *p = h->active.buf + h->free_ptr + 1; - h->free_ptr += size; - return p; -} - -static value process_gc_value(struct heap *h, value val) -{ - if (!is_pointer(val)) { - return val; - } - value *p = to_pointer(val); - if (forwarded(h, p)) { - return *p; - } - - size_t size = alloc_size(p); - - // Allocate space in the new buffer. - value *q = simple_alloc(h, size); - - // Write forwarding pointer. - value first_value = p[0]; - p[0] = from_pointer(q); - - // Copy values, recursively modifying pointers. - q[0] = process_gc_value(h, first_value); - for (size_t i = 1; i < size; i++) { - q[i] = process_gc_value(h, p[i]); - } - - return from_pointer(q); -} - -static void collect_garbage(struct heap *h) -{ - if (h->free_ptr < 2 * h->last_free) { - return; - } - - // Swap the heaps. - value_slice temp = h->active; - h->active = h->standby; - h->standby = temp; - - h->free_ptr = 0; - - for (size_t i = 0; i < h->gc_roots.size; i++ ) { - h->gc_roots.buf[i] = process_gc_value(h, h->gc_roots.buf[i]); - } -} - -static value_slice xcalloc(size_t size) -{ - value *p = calloc(size, sizeof(value)); - if (!p) { - panicf("Out of memory!\n"); - } - return (value_slice) { .size = size, .buf = p }; -} - -static void more_space(struct heap *h, int64_t size_hint) -{ - size_t new_size = h->active.size * 2 + size_hint; - value_slice new_buf = xcalloc(2 * new_size); - memcpy(new_buf.buf, h->active.buf, h->active.size * sizeof(value)); - - free(h->buf); - h->buf = new_buf.buf; - h->active = value_slice2(new_buf, 0, new_size); - h->standby = value_slice1(new_buf, new_size); -} - -value *alloc(struct heap *h, int64_t size) -{ - if (size <= 0) { - panicf("Alloc of zero size!\n"); - } - collect_garbage(h); - - if (h->free_ptr + size >= h->active.size) { - more_space(h, size); - } - value *p = simple_alloc(h, size); - memset(p, 0, size * sizeof(value)); - return p; -} diff --git a/bytecode/heap.h b/bytecode/heap.h deleted file mode 100644 index c6c10c4..0000000 --- a/bytecode/heap.h +++ /dev/null @@ -1,27 +0,0 @@ -#ifndef _HEAP_H_ -#define _HEAP_H_ - -#include -#include - -#include "value.h" -#include "value_slice.h" - -struct heap { - // The heap is divided into two halves for garbage collection. - // buf holds the malloc'd heap buffer. - value *buf; - // active and standby are slices that partition buf. - value_slice active; - value_slice standby; - - size_t free_ptr; - - size_t last_free; - value_slice gc_roots; -}; - -struct heap new_heap(value_slice); -value *alloc(struct heap *, int64_t); - -#endif diff --git a/bytecode/oper.c b/bytecode/oper.c deleted file mode 100644 index 0bdb8f6..0000000 --- a/bytecode/oper.c +++ /dev/null @@ -1,97 +0,0 @@ -#include -#include - -#include "byte_slice.h" -#include "encoding.h" -#include "heap.h" -#include "panic.h" -#include "value.h" -#include "value_slice.h" - -#include "oper.h" - -struct st { - size_t i; - value locals[NUM_LOCALS]; - struct heap heap; -}; - -static value read_arg(struct st *s, struct arg arg) -{ - if (arg.constant) { - return arg.constant; - } - return s->locals[arg.local]; -} - -static void oalloc(struct st *s, struct op oper) -{ - s->locals[oper.alloc.out] = from_pointer(alloc(&s->heap, to_int(read_arg(s, oper.alloc.size)))); -} - -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: - oalloc(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(uint8_t_slice prog) -{ - struct st s = { - .i = 0, - .locals = { 0 }, - }; - s.heap = new_heap((value_slice) { .size = NUM_LOCALS, .buf = s.locals }); - while (true) { - struct result oper = parse(uint8_t_slice1(prog, s.i)); - s.i += oper.n; - op(&s, oper.op); - } -} diff --git a/bytecode/oper.h b/bytecode/oper.h deleted file mode 100644 index 7174e1d..0000000 --- a/bytecode/oper.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef _OPER_H_ -#define _OPER_H_ - -#include "byte_slice.h" - -void run(uint8_t_slice); - -#endif diff --git a/bytecode/panic.c b/bytecode/panic.c deleted file mode 100644 index db2b6f8..0000000 --- a/bytecode/panic.c +++ /dev/null @@ -1,15 +0,0 @@ -#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 deleted file mode 100644 index d9904a8..0000000 --- a/bytecode/panic.h +++ /dev/null @@ -1,7 +0,0 @@ -#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 deleted file mode 100644 index 2b86acd..0000000 --- a/bytecode/shell.nix +++ /dev/null @@ -1,6 +0,0 @@ -{ pkgs ? import {} }: -with pkgs; -mkShell { - nativeBuildInputs = [ gcc gnumake valgrind gdb ]; - hardeningDisable = [ "fortify" ]; -} diff --git a/bytecode/slice.h b/bytecode/slice.h deleted file mode 100644 index 4f4624c..0000000 --- a/bytecode/slice.h +++ /dev/null @@ -1,33 +0,0 @@ -#ifndef _SLICE_H_ -#define _SLICE_H_ - -#include -#include - -#define DEFINE_SLICE(t) \ - typedef struct { \ - size_t size; \ - t *buf; \ - } t##_slice; \ - \ - static inline t##_slice \ - t##_slice2(t##_slice slice, size_t i, size_t j) \ - { \ - assert(i <= slice.size && j <= slice.size && i <= j); \ - return (t##_slice) { \ - .size = j - i, \ - .buf = slice.buf + i, \ - }; \ - } \ - \ - static inline t##_slice \ - t##_slice1(t##_slice slice, size_t i) \ - { \ - assert(i <= slice.size); \ - return (t##_slice) { \ - .size = slice.size - i, \ - .buf = slice.buf + i, \ - }; \ - } - -#endif diff --git a/bytecode/src/encoding.rs b/bytecode/src/encoding.rs new file mode 100644 index 0000000..e37696d --- /dev/null +++ b/bytecode/src/encoding.rs @@ -0,0 +1,139 @@ +use crate::heap; +use crate::value::Value; +use std::error::Error; + +pub enum Arg { + Local(u8), + Const(Value), +} + +pub struct Alloc { + pub out: u8, + pub size: Arg, +} + +pub struct Poke { + pub offset: usize, + pub ptr: u8, + pub val: Arg, +} + +pub struct Peek { + pub out: u8, + pub offset: usize, + pub val: Arg, +} + +pub struct Shuf { + pub out: u8, + pub val: Arg, +} + +pub struct Exit { + pub val: Arg, +} + +pub enum Op { + Alloc(Alloc), + Call, + Poke(Poke), + Peek(Peek), + Shuf(Shuf), + Exit(Exit), +} + +struct Reader<'a> { + data: &'a [u8], + n: usize, +} + +impl Reader<'_> { + fn advance(&mut self, size: usize) { + self.data = &self.data[size..]; + self.n += size; + } + + fn parse_byte(&mut self) -> Result> { + if self.data.is_empty() { + return Err(Box::from("read byte: no data")); + } + let res = self.data[0]; + self.advance(1); + Ok(res) + } + + fn parse_local(&mut self) -> Result> { + if self.data.is_empty() { + return Err(Box::from("local: no data")); + } + let res = self.data[0]; + if usize::from(res) >= heap::NUM_LOCALS { + return Err(Box::from(format!("invalid local (out of range): {}", res))); + } + self.advance(1); + Ok(res) + } + + fn parse_u64(&mut self) -> Result> { + if self.data.len() < 8 { + return Err(Box::from("value: no data")); + } + let mut res = [0; 8]; + res.copy_from_slice(&self.data[..8]); + self.advance(8); + Ok(u64::from_le_bytes(res)) + } + + fn parse_arg(&mut self, is_const: bool) -> Result> { + if is_const { + Ok(Arg::Const(Value(self.parse_u64()?))) + } else { + Ok(Arg::Local(self.parse_local()?)) + } + } +} + +impl Op { + pub fn parse(data: &[u8]) -> Result<(usize, Op), Box> { + let mut r = Reader { data, n: 0 }; + let code_byte = r.parse_byte()?; + let code = code_byte >> 2; + let arg1_const = code_byte & 2 != 0; + // let arg2_const = code_byte & 1 != 0; + + let op = match code { + 1 => { + let out = r.parse_local()?; + let size = r.parse_arg(arg1_const)?; + Op::Alloc(Alloc { out, size }) + } + 2 => Op::Call, + 3 => { + let offset = usize::try_from(r.parse_u64()?)?; + let ptr = r.parse_local()?; + let val = r.parse_arg(arg1_const)?; + Op::Poke(Poke { offset, ptr, val }) + } + 4 => { + let out = r.parse_local()?; + let offset = usize::try_from(r.parse_u64()?)?; + let val = r.parse_arg(arg1_const)?; + Op::Peek(Peek { out, offset, val }) + } + 5 => { + let out = r.parse_local()?; + let val = r.parse_arg(arg1_const)?; + Op::Shuf(Shuf { out, val }) + } + 6 => { + let val = r.parse_arg(arg1_const)?; + Op::Exit(Exit { val }) + } + _ => { + return Err(Box::from(format!("invalid code {}", code))); + } + }; + + Ok((r.n, op)) + } +} diff --git a/bytecode/src/heap.rs b/bytecode/src/heap.rs new file mode 100644 index 0000000..f1b9d81 --- /dev/null +++ b/bytecode/src/heap.rs @@ -0,0 +1,144 @@ +use crate::value::Value; +use std::error::Error; + +pub const NUM_LOCALS: usize = 8; + +pub struct Heap { + pub buf: Vec, + free_ptr: usize, + last_live: usize, + pub locals: [Value; NUM_LOCALS], +} + +impl Heap { + pub fn new() -> Heap { + Heap { + buf: Vec::new(), + free_ptr: 0, + last_live: 0, + locals: [Value(0); NUM_LOCALS], + } + } + + fn forwarded(&self, p: usize) -> bool { + let Some(q) = Value(self.buf[p]).to_pointer() else { + return false; + }; + return (self.free_ptr < self.buf.len() / 2) == (q < self.buf.len() / 2); + } + + fn alloc_size(&self, p: usize) -> usize { + usize::try_from(self.buf[p - 1] >> 1).expect("using 32 bits in 2024 LULW") + } + + fn simple_alloc(&mut self, size: usize) -> usize { + self.buf[self.free_ptr] = u64::try_from(size).expect("how even??") << 1; + let p = self.free_ptr + 1; + self.free_ptr += size + 1; + p + } + + fn process_gc_value(&mut self, val: Value) -> Value { + let Some(p) = val.to_pointer() else { + return val; + }; + if self.forwarded(p) { + return Value(self.buf[p]); + } + + let size = self.alloc_size(p); + + // Allocate space in the new buffer. + let q = self.simple_alloc(size); + + // Write forwarding pointer. + let first_val = Value(self.buf[p]); + self.buf[p] = Value::from_pointer(q).repr(); + + // Copy values, recursively modifying pointers. + self.buf[q] = self.process_gc_value(first_val).repr(); + for i in 1..size { + self.buf[q + i] = self.process_gc_value(Value(self.buf[p + i])).repr(); + } + + Value::from_pointer(q) + } + + fn collect_garbage(&mut self) { + if self.free_ptr < 2 * self.last_live { + return; + } + + // Swap the heaps. + if self.free_ptr < self.buf.len() / 2 { + self.free_ptr = self.buf.len() / 2; + } else { + self.free_ptr = 0; + } + + for i in 0..self.locals.len() { + self.locals[i] = self.process_gc_value(self.locals[i]); + } + if self.free_ptr < self.buf.len() / 2 { + self.last_live = self.free_ptr; + } else { + self.last_live = self.free_ptr - self.buf.len() / 2; + } + } + + fn more_space(&mut self, size_hint: usize) { + let current_size = self.buf.len() / 2; + let mut new_size = current_size * 2; + if new_size == 0 { + new_size = 1; + } + while new_size <= current_size + size_hint { + new_size *= 2; + } + + let active; + if self.free_ptr < current_size { + active = &self.buf[..current_size]; + } else { + active = &self.buf[current_size..]; + self.free_ptr -= current_size; + } + + let mut new_buf = Vec::with_capacity(new_size * 2); + new_buf.extend_from_slice(active); + new_buf.resize(new_size * 2, 0); + self.buf = new_buf; + } + + pub fn alloc(&mut self, size: i64) -> Result> { + if size <= 0 { + return Err(Box::from("alloc of zero size")); + } + let usize = usize::try_from(size).expect("32 bits in 2024 LULW"); + self.collect_garbage(); + if self.free_ptr + usize + 1 >= self.buf.len() / 2 { + self.more_space(usize); + } + + let p = self.simple_alloc(usize::try_from(size).expect("using 32 bits in 2024 LULW")); + for i in 0..usize { + self.buf[p + i] = 0; + } + Ok(p) + } + + pub fn peek(&self, p: usize) -> Result> { + if p >= self.buf.len() { + return Err(Box::from("peek: out of range")); + } + Ok(Value(self.buf[p])) + } + + pub fn poke(&mut self, p: usize, val: Value) -> Result<(), Box> { + if p >= self.buf.len() { + return Err(Box::from("poke: out of range")); + } + self.buf[p] = val.repr(); + Ok(()) + } +} diff --git a/bytecode/src/main.rs b/bytecode/src/main.rs new file mode 100644 index 0000000..a4970e0 --- /dev/null +++ b/bytecode/src/main.rs @@ -0,0 +1,87 @@ +mod encoding; +mod heap; +mod value; + +use encoding::{Arg, Op}; +use heap::Heap; +use std::error::Error; +use std::ffi::OsString; +use std::io::{stderr, Write}; +use value::Value; + +struct State { + i: usize, + heap: Heap, +} + +impl State { + fn read_arg(&self, a: Arg) -> Value { + match a { + Arg::Local(l) => self.heap.locals[usize::from(l)], + Arg::Const(c) => c, + } + } + + fn op(&mut self, op: Op) -> Result<(), Box> { + match op { + Op::Alloc(op) => { + let Some(i) = self.read_arg(op.size).to_int() else { + return Err(Box::from("alloc needs an int")); + }; + self.heap.locals[usize::from(op.out)] = Value::from_pointer(self.heap.alloc(i)?); + } + Op::Call => { + let Some(i) = self.heap.locals[0].to_int() else { + return Err(Box::from("call needs an int")); + }; + self.i = usize::try_from(i)?; + } + Op::Poke(op) => { + let Some(p) = self.heap.locals[usize::from(op.ptr)].to_pointer() else { + return Err(Box::from("poke needs a pointer")); + }; + self.heap.poke(p + op.offset, self.read_arg(op.val))?; + } + Op::Peek(op) => { + let Some(p) = self.read_arg(op.val).to_pointer() else { + return Err(Box::from("peek needs a pointer")); + }; + self.heap.locals[usize::from(op.out)] = self.heap.peek(p + op.offset)?; + } + Op::Shuf(op) => { + self.heap.locals[usize::from(op.out)] = self.read_arg(op.val); + } + Op::Exit(op) => { + let Some(i) = self.read_arg(op.val).to_int() else { + std::process::exit(255); + }; + std::process::exit(i as i32); + } + } + Ok(()) + } +} + +fn run() -> Result<(), Box> { + let args: Vec = std::env::args_os().collect(); + if args.len() != 2 { + return Err(Box::from("usage: bytecode ")); + } + let prog = std::fs::read(&args[1])?; + let mut st = State { + i: 0, + heap: Heap::new(), + }; + loop { + let (n, op) = Op::parse(&prog[st.i..])?; + st.i += n; + st.op(op)?; + } +} + +fn main() { + if let Err(err) = run() { + let _ = writeln!(stderr(), "FAIL: {}", err); + std::process::exit(255); + } +} diff --git a/bytecode/src/value.rs b/bytecode/src/value.rs new file mode 100644 index 0000000..fbaa128 --- /dev/null +++ b/bytecode/src/value.rs @@ -0,0 +1,31 @@ +#[derive(Clone, Copy)] +pub struct Value(pub u64); + +impl Value { + pub fn repr(self) -> u64 { + let Value(v) = self; + v + } + + pub fn to_int(self) -> Option { + if self.repr() & 1 == 0 { + return None; + } + Some(self.repr() as i64 >> 1) + } + + pub fn from_int(i: i64) -> Value { + Value((i as u64) << 1 | 1) + } + + pub fn to_pointer(self) -> Option { + if self.repr() == 0 || self.repr() & 7 != 0 { + return None; + } + Some(usize::try_from(self.repr() >> 3).expect("using 32 bits in 2024 LULW")) + } + + pub fn from_pointer(p: usize) -> Value { + Value(u64::try_from(p).expect("a usize should always fit in a u64... right?") << 3) + } +} diff --git a/bytecode/value.c b/bytecode/value.c deleted file mode 100644 index 1b18a96..0000000 --- a/bytecode/value.c +++ /dev/null @@ -1,42 +0,0 @@ -#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 0x%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 0x%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 deleted file mode 100644 index 3fa78c4..0000000 --- a/bytecode/value.h +++ /dev/null @@ -1,21 +0,0 @@ -#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 diff --git a/bytecode/value_slice.h b/bytecode/value_slice.h deleted file mode 100644 index 09b2873..0000000 --- a/bytecode/value_slice.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef _VALUE_SLICE_H_ -#define _VALUE_SLICE_H_ - -#include "slice.h" -#include "value.h" - -DEFINE_SLICE(value) - -#endif -- cgit v1.3.1