// Copyright (C) 2025 Thom Hayward. // // This program is free software: you can redistribute it and/or modify it under // the terms of the GNU General Public License as published by the Free Software // Foundation, version 3. // // This program is distributed in the hope that it will be useful, but WITHOUT // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS // FOR A PARTICULAR PURPOSE. See the GNU General Public License for more // details. // // You should have received a copy of the GNU General Public License along with // this program. If not, see . // use std::io::Read; use std::io::Write; use smallvec::SmallVec; use crate::ops::Operation; use crate::reg::{Page, Register}; pub const SMALLVEC_SIZE: usize = 24; /// Lossless conversion to `usize`. /// /// This should only be implemented on types which can be losslessly /// cast to a `usize`. trait IntoIndex: Sized + Copy { fn into_index(self) -> usize; } macro_rules! impl_into_index { ($t:ty) => { impl IntoIndex for $t { fn into_index(self) -> usize { self as usize } } }; } #[cfg(target_pointer_width = "16")] compile_error!("16 bit architectures are unsupported"); // usize *may* be 16 bits, so only implement if it is 32 or 64 bits. #[cfg(any(target_pointer_width = "64", target_pointer_width = "32"))] impl_into_index!(u32); #[derive(Default)] pub struct Um<'a> { pub program_counter: u32, pub registers: Page, /// Program memory, modelled as a `Vec` of `SmallVec`. /// /// Memory allocations greater than `SMALLVEC_SIZE` will incur a memory /// indirection penalty for every memory access within that block. pub memory: Vec>, pub free_blocks: Vec, /// Partially decoded operations cache. pub ops: Vec, pub stdin: Option<&'a mut dyn Read>, pub stdout: Option<&'a mut dyn Write>, } impl<'a> Um<'a> { /// Initialise a Universal Machine with the specified program scroll. #[must_use] pub fn new(program: Vec) -> Self { let ops = crate::ops::decode(&program); Self { memory: vec![program.into()], ops, ..Default::default() } } /// Sets the output for the universal machine. #[must_use] pub fn stdout(mut self, stdout: &'a mut T) -> Self { self.stdout.replace(stdout); self } /// Sets the input for the universal machine. #[must_use] pub fn stdin(mut self, stdin: &'a mut T) -> Self { self.stdin.replace(stdin); self } /// Begin the spin-cycle of the Universal Machine. /// /// # Panics /// /// Panics if the machine encounters an illegal instruction. /// #[inline(never)] #[allow(clippy::return_self_not_must_use, clippy::must_use_candidate)] pub fn run(mut self) -> Self { loop { // println!( // "{:?}, pc: {:08x}, r: {:08x?}", // self.ops[self.program_counter as usize], self.program_counter, self.registers // ); match self.ops[self.program_counter as usize] { Operation::ConditionalMove { a, b, c } => self.conditional_move(a, b, c), Operation::ArrayIndex { a, b, c } => self.array_index(a, b, c), Operation::ArrayAmendment { a, b, c } => self.array_amendment(a, b, c), Operation::Addition { a, b, c } => self.addition(a, b, c), Operation::Multiplication { a, b, c } => self.multiplication(a, b, c), Operation::Division { a, b, c } => self.division(a, b, c), Operation::NotAnd { a, b, c } => self.not_and(a, b, c), Operation::Halt => break, Operation::Allocation { b, c } => self.allocation(b, c), Operation::Abandonment { c } => self.abandonment(c), Operation::Output { c } => self.output(c), Operation::Input { c } => self.input(c), Operation::LoadProgram { b, c } => { self.load_program(b, c); continue; } Operation::Orthography { a, value } => self.orthography(a, value), Operation::IllegalInstruction => self.illegal_instruction(), } self.program_counter += 1; } self } // Un-commenting step() slows down the sandmark benchmark by ~3-5 seconds, even // though it has *no* interaction with the code path in Um::run(). // // /// Steps one instruction. // #[inline(never)] // pub fn step(&mut self) -> bool { // match self.ops[self.program_counter as usize] { // Operation::ConditionalMove { a, b, c } => self.conditional_move(a, b, c), // Operation::ArrayIndex { a, b, c } => self.array_index(a, b, c), // Operation::ArrayAmendment { a, b, c } => self.array_amendment(a, b, c), // Operation::Addition { a, b, c } => self.addition(a, b, c), // Operation::Multiplication { a, b, c } => self.multiplication(a, b, c), // Operation::Division { a, b, c } => self.division(a, b, c), // Operation::NotAnd { a, b, c } => self.not_and(a, b, c), // Operation::Halt => return false, // Operation::Allocation { b, c } => self.allocation(b, c), // Operation::Abandonment { c } => self.abandonment(c), // Operation::Output { c } => self.output(c), // Operation::Input { c } => self.input(c), // Operation::LoadProgram { b, c } => { // self.load_program(b, c); // return true; // } // Operation::Orthography { a, value } => self.orthography(a, value), // Operation::IllegalInstruction => self.illegal_instruction(), // } // self.program_counter += 1; // true // } /// Loads the value from the specified register. #[must_use] pub fn load_register(&self, register: Register) -> u32 { self.registers[register] } /// Saves a value to the specified register. pub fn save_register(&mut self, register: Register, value: u32) { self.registers[register] = value; } pub fn conditional_move(&mut self, a: Register, b: Register, c: Register) { if self.load_register(c) != 0 { self.save_register(a, self.load_register(b)); } } pub fn array_index(&mut self, a: Register, b: Register, c: Register) { let block = self.load_register(b); let offset = self.load_register(c); self.save_register(a, self.load_memory(block, offset)); } pub fn array_amendment(&mut self, a: Register, b: Register, c: Register) { let block = self.load_register(a); let offset = self.load_register(b); let value = self.load_register(c); self.store_memory(block, offset, value); } pub fn addition(&mut self, a: Register, b: Register, c: Register) { self.save_register(a, self.load_register(b).wrapping_add(self.load_register(c))); } pub fn multiplication(&mut self, a: Register, b: Register, c: Register) { self.save_register(a, self.load_register(b).wrapping_mul(self.load_register(c))); } pub fn division(&mut self, a: Register, b: Register, c: Register) { self.save_register(a, self.load_register(b).wrapping_div(self.load_register(c))); } pub fn not_and(&mut self, a: Register, b: Register, c: Register) { self.save_register(a, !(self.load_register(b) & self.load_register(c))); } pub fn allocation(&mut self, b: Register, c: Register) { let length = self.load_register(c); let index = self.allocate_memory(length); self.save_register(b, index); } pub fn abandonment(&mut self, c: Register) { let block = self.load_register(c); self.free_memory(block); } /// Write the value in the specified register to stdout. /// /// # Panics /// /// Panics if writing to stdout fails. /// pub fn output(&mut self, c: Register) { let value = self.load_register(c); if let Some(stdout) = self.stdout.as_mut() { let buffer = [(value & 0xff) as u8]; stdout.write_all(&buffer).unwrap(); } } /// Read a value from stdin into the specifed register. // // The `as` cast below benchmarks faster than using u32::from. #[allow(clippy::cast_lossless)] pub fn input(&mut self, c: Register) { if let Some(stdin) = self.stdin.as_mut() { let mut buffer = vec![0]; match stdin.read_exact(&mut buffer) { Ok(()) => self.save_register(c, buffer[0] as u32), Err(_) => self.save_register(c, u32::MAX), } } else { self.save_register(c, u32::MAX); } } pub fn load_program(&mut self, b: Register, c: Register) { let block = self.load_register(b); // Source array is always copied to array[0], but there // is no point copying array[0] to array[0]. if block != 0 { let duplicated = self.duplicate_memory(block); let ops = crate::ops::decode(duplicated); self.ops = ops; } self.program_counter = self.load_register(c); } pub fn orthography(&mut self, a: Register, value: u32) { self.save_register(a, value); } /// Print the current instruction, program counter, and registers to stderr and quit. /// /// # Panics /// /// Panics when called. Every time. /// #[cold] #[inline(never)] pub fn illegal_instruction(&self) -> ! { panic!( "illegal instruction: {:08x}, pc: {:08x}, r: {:08x?}", self.memory[0][self.program_counter.into_index()], self.program_counter, self.registers ) } /// Load a value from `offset` in the specified memory `block`. /// /// # Panics /// /// Panics if the `block` is not an allocated block, or if `offset` overflows the current /// memory block. /// #[must_use] pub fn load_memory(&self, block: u32, offset: u32) -> u32 { let block = block.into_index(); let offset = offset.into_index(); assert!(block < self.memory.len() && offset < self.memory[block].len()); self.memory[block][offset] } /// Store a `value` at `offset` in the specified memory `block`. /// /// # Panics /// /// Panics if the `block` is not an allocated block, or if `offset` overflows the current /// memory block. /// pub fn store_memory(&mut self, block: u32, offset: u32, value: u32) { let block = block.into_index(); let offset = offset.into_index(); assert!(block < self.memory.len() && offset < self.memory[block].len()); self.memory[block][offset] = value; } /// Duplicates a block of memory. /// /// The block is copied to the first block of memory. /// /// # Panics /// /// Panics if the `block` is not an allocated block of memory. /// pub fn duplicate_memory(&mut self, block: u32) -> &[u32] { let block = block.into_index(); assert!(block < self.memory.len()); self.memory[0] = self.memory[block].clone(); &self.memory[0] } /// Allocates a block of memory of the specified length. #[allow(clippy::cast_possible_truncation)] pub fn allocate_memory(&mut self, length: u32) -> u32 { if let Some(index) = self.free_blocks.pop() { self.memory[index.into_index()] = Self::new_block(length.into_index()); index } else { self.memory.push(Self::new_block(length.into_index())); // The Universal Machine only deals with 32-bit values, so truncation here is // impossible. (self.memory.len() - 1) as u32 } } /// Free a block of memory. /// /// # Panics /// /// Panics if `block` is not an allocated block of memory. /// pub fn free_memory(&mut self, block: u32) { assert!(block.into_index() < self.memory.len()); self.free_blocks.push(block); self.memory[block.into_index()] = Self::new_block(0); } /// Create a new block of memory. /// /// The block is initialised with `len` zeroes. /// #[must_use] pub fn new_block(len: usize) -> SmallVec<[u32; SMALLVEC_SIZE]> { smallvec::smallvec![0; len] } } #[cfg(test)] mod tests { use super::*; #[test] #[should_panic] fn empty_program() { Um::new(vec![]).run(); } #[test] fn just_halt() { Um::new(vec![0x70000000]).run(); } #[test] #[cfg(feature = "asm")] fn hello_world() { let program = crate::asm::assemble(include_str!("../files/hello-world.asm")); let mut buffer = Vec::new(); Um::new(program).stdout(&mut buffer).run(); assert_eq!(&buffer, b"Hello, world!\n"); } #[test] #[cfg(feature = "asm")] fn cat() { let program = crate::asm::assemble(include_str!("../files/cat.asm")); let input = include_bytes!("lib.rs"); let mut reader = std::io::Cursor::new(input); let mut buffer = Vec::new(); Um::new(program) .stdin(&mut reader) .stdout(&mut buffer) .run(); assert_eq!(&buffer, &input); } }