summaryrefslogtreecommitdiffstats
path: root/bytecode/src
diff options
context:
space:
mode:
Diffstat (limited to 'bytecode/src')
-rw-r--r--bytecode/src/encoding.rs139
-rw-r--r--bytecode/src/heap.rs144
-rw-r--r--bytecode/src/main.rs87
-rw-r--r--bytecode/src/value.rs31
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)
+ }
+}
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 06:01:28 +0000