Rewrite the bytecode interpreter in Rust.

4 files changed, 401 insertions, 0 deletions

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<u8, Box<dyn Error>> {
+        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<u8, Box<dyn Error>> {
+        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<u64, Box<dyn Error>> {
+        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<Arg, Box<dyn Error>> {
+        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<dyn Error>> {
+        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<u64>,
+    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<usize, Box<dyn Error>> {
+        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<Value, Box<dyn Error>> {
+        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<dyn Error>> {
+        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<dyn Error>> {
+        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<dyn Error>> {
+    let args: Vec<OsString> = std::env::args_os().collect();
+    if args.len() != 2 {
+        return Err(Box::from("usage: bytecode <file>"));
+    }
+    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<i64> {
+        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<usize> {
+        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)
+    }
+}