ICFP 2006 Universal Machine

Cargo.toml

[package]
name = "icfp-2006"
version = "0.1.0"
authors = ["Colin <vogon@icculus.org>"]

[dependencies]
byteorder = "0.4.2"
getopts = "0.2.14"
time = "0.1.34"

main.rs

use std::env;
use std::error::Error;
use std::fs::File;

extern crate byteorder;
use byteorder::{BigEndian, ReadBytesExt};

extern crate getopts;
use getopts::Options;


mod um;
use um::{UM, UMStatus};

fn dump_state(um: &UM) {
	match um.peek_array(0, um.get_ef()) {
		Some(insn) => println!("EF = 0x{:08x} (0x{:08x})", um.get_ef(), insn),
		None => println!("EF = 0x{:08x} (???)", um.get_ef())
	};

	let regs = um.dump_regs();

	println!("r0 = 0x{:08x} r1 = 0x{:08x} r2 = 0x{:08x} r3 = 0x{:08x}",
		regs[0], regs[1], regs[2], regs[3]);
	println!("r4 = 0x{:08x} r5 = 0x{:08x} r6 = 0x{:08x} r7 = 0x{:08x}",
		regs[4], regs[5], regs[6], regs[7]);
}

fn print_usage(program: &str, opts: Options) {
	let brief = format!("Usage: {} program [options]", program);
	print!("{}", opts.usage(&brief));
}

fn main() {
	let args: Vec<_> = env::args().collect();

	let mut opts = Options::new();
	opts.optflag("", "dump", "dump state before every step");
	opts.optopt("l", "limit", "execute for N instructions", "N");

	if args.len() == 1 {
		print_usage(&args[0], opts);
		return;
	}

	let matches = match opts.parse(&args[1..]) {
		Ok(m) => m,
		Err(f) => { panic!(f.to_string()) }
	};

	// grab limit parameter
	let limit = match matches.opt_str("limit") {
		// parameter present
		Some(arg) => match arg.parse::<usize>() {
			// argument was an integer
			Ok(n) => Some(n),
			// argument wasn't an integer
			Err(_) => {
				println!("error: non-integral argument passed to -l/--limit");
				print_usage(&args[0], opts);
				return;
			}
		},
		// parameter not present
		None => None
	};

	let mut file = match File::open(&args[1]) {
		Err(why) => panic!("couldn't open {}: {}", 
			args[1], Error::description(&why)),
		Ok(file) => file
	};

	let mut program = Vec::new();

	loop {
		let n = match file.read_u32::<BigEndian>() {
			Ok(n) => n,
			// stop reading by running off the end of the file
			Err(byteorder::Error::UnexpectedEOF) => break,
			Err(why) => panic!("read_u32 returned {}", why)
		};

		program.push(n);
	}

	println!("{} loaded and running.", args[1]);

	let mut machine = UM::new(&program);
	let mut insns_run = 0;

	loop {
		if matches.opt_present("dump") {
			dump_state(&machine);
			println!("==================================================");
		}

		match machine.step() {
			Ok(UMStatus::Continue) => { 
				insns_run += 1;

				match limit {
					Some(n) => if insns_run >= n { break; },
					None => ()
				};
			},
			Ok(UMStatus::Halt) => {
				println!("");
				println!("machine halted normally.");
				break;
			},
			Err(e) => {
				println!("");
				println!("machine halted with failure: {:?}", e);
				dump_state(&machine);
				break;
			}
		}
	}

	for opcode in 0..14 {
		let pc = machine.get_perf_counter(opcode);

		println!("opcode {}: {} executed, {} ns ({:.1} ns/insn)", opcode, 
			pc.n_insns, pc.ns, pc.ns as f64 / pc.n_insns as f64);
	}
}

um.rs

use std::char;
use std::collections::BTreeSet;
use std::io;
use std::io::Read;
use std::num::Wrapping;

extern crate time;
use self::time::precise_time_ns;

pub type Platter = u32;

#[derive(Debug)]
pub enum UMStatus {
	// the program is still running
	Continue,
	// the program requested to halt
	Halt,	
}

#[derive(Debug)]
pub enum UMFailure {
	// the execution finger points to a platter that does not encode a valid
	// instruction
	InvalidInstruction,
	// the program indexed or amended an inactive array
	InactiveArrayAccess,
	// the program tried to index or amend an array out of range
	OutOfBoundArrayAccess,
	// the program abandoned the program array
	AbandonedProgramArray,
	// the program abandoned an inactive array
	AbandonedArrayNotActive,
	// the program loaded a program from an inactive array
	InactiveArrayProgramLoaded,
	// the program output an out-of-range character
	InvalidOutputCharacter,
	// the execution finger points out of range in array 0
	InvalidEF,
}

pub struct PerformanceCounter {
	pub n_insns: u64,
	pub ns: u64
}

pub struct UM {
	regs: [Platter; 8],
	ef: Platter,
	arrays: Vec<Vec<Platter>>,
	free_array_ids: BTreeSet<Platter>,
	n_insns: [u64; 16],
	ns: [u64; 16],
}

impl UM {
	pub fn new(program: &[Platter]) -> UM {
		let mut new_um = UM {
			regs: [0; 8],
			ef: 0,
			arrays: Vec::new(),
			free_array_ids: BTreeSet::new(),
			n_insns: [0; 16],
			ns: [0; 16],
		};

		let program_id = new_um.allocate_array(program.len() as Platter);

		if let Some(vec) = new_um.arrays.get_mut(program_id as usize) {
			for i in 0..(program.len()) {
				vec[i] = program[i];
			}
		} else {
			unreachable!();
		}

		return new_um;
	}

	pub fn step(&mut self) -> Result<UMStatus, UMFailure> {
		// fetch insn
		let ns_start = time::precise_time_ns();

		let insn: Platter;

		{
			let program = match self.arrays.get_mut(0) {
				Some(p) => p,
				None => unreachable!()
			};

			if self.ef > (program.len() as u32) {
				// EF off the end of the program array
				return Err(UMFailure::InvalidEF);
			}

			insn = program[self.ef as usize];
		}

		// break out the individual fields
		let opcode = (insn >> 28) & 0xF;
		let imm_a = ((insn >> 25) & 0x7) as usize;
		let a = ((insn >> 6) & 0x7) as usize;
		let b = ((insn >> 3) & 0x7) as usize;
		let c = (insn & 0x7) as usize;
		let immediate = insn & 0x01FFFFFF;

		let stdin = io::stdin();

		match opcode {
			0 => {
				// conditional move
				if self.regs[c] != 0 {
					self.regs[a] = self.regs[b];
				}

				self.ef += 1;
			},
			1 => {
				// array index
				let val = self.index_array(self.regs[b], self.regs[c]);

				match val {
					Ok(_) => { self.regs[a] = val.unwrap(); self.ef += 1; },
					Err(e) => { return Err(e); }
				}
			},
			2 => {
				// array amendment
				let id = self.regs[a];
				let offset = self.regs[b];
				let value = self.regs[c];

				match self.amend_array(id, offset, value) {
					Ok(_) => { self.ef += 1; },
					Err(e) => { return Err(e); }
				}
			},
			3 => {
				// addition
				self.regs[a] = 
					(Wrapping(self.regs[b]) + Wrapping(self.regs[c])).0;

				self.ef += 1;
			},
			4 => {
				// multiplication
				self.regs[a] =
					(Wrapping(self.regs[b]) * Wrapping(self.regs[c])).0;

				self.ef += 1;
			},
			5 => {
				// division
				self.regs[a] =
					(Wrapping(self.regs[b]) / Wrapping(self.regs[c])).0;

				self.ef += 1;
			},
			6 => {
				// "not-and" (NAND)
				self.regs[a] = !(self.regs[b] & self.regs[c]);

				self.ef += 1;
			},
			7 => {
				// halt
				return Ok(UMStatus::Halt);
			},
			8 => {
				// array allocation
				let capacity = self.regs[c];
				let new_id = self.allocate_array(capacity);

				self.regs[b] = new_id;
				self.ef += 1;
			},
			9 => {
				// array abandonment
				let id = self.regs[c];

				match self.abandon_array(id) {
					Ok(_) => { self.ef += 1; },
					Err(e) => { return Err(e) }
				};
			},
			10 => {
				// output
				let c_val = self.regs[c];

				if c_val > 255 {
					return Err(UMFailure::InvalidOutputCharacter);
				} else {
					print!("{}", char::from_u32(c_val).unwrap());
					self.ef += 1;
				}
			},
			11 => {
				// input
				match stdin.lock().bytes().next() {
					Some(res) => 
						match res {
							Ok(ch) => { 
								self.regs[c] = (ch as u32) & 0xFF;
								self.ef += 1;
							},
							Err(e) => panic!(e)
						},
					None => { self.regs[c] = 0xFFFFFFFF; self.ef += 1; }
				}
			},
			12 => {
				// load program
				match self.load_program(b, c) {
					Ok(_) => () /* EF is reset by load_program() */,
					Err(e) => return Err(e)
				};
			},
			13 => {
				// "orthography": load immediate
				self.regs[imm_a] = immediate;
				self.ef += 1;
			},
			_ => {
				// insns 14-15 are undefined
				return Err(UMFailure::InvalidInstruction);
			}
		};

		let ns_end = time::precise_time_ns();

		self.n_insns[opcode as usize] += 1;
		self.ns[opcode as usize] += (ns_end - ns_start);

		// if we made it out here, increment EF
		return Ok(UMStatus::Continue);
	}

	pub fn get_ef(&self) -> Platter {
		return self.ef;
	}

	pub fn dump_regs(&self) -> [Platter; 8] {
		return self.regs.clone();
	}

	pub fn get_perf_counter(&self, opcode: usize) -> PerformanceCounter {
		return PerformanceCounter { 
			n_insns: self.n_insns[opcode], ns: self.ns[opcode]
		};
	}

	pub fn peek_array(&self, id: Platter, offset: Platter) -> Option<Platter> {
		return match self.index_array(id, offset) {
			Ok(x) => Some(x),
			Err(_) => None
		}
	}

	fn allocate_array(&mut self, capacity: Platter) -> Platter {
		//println!("allocating new array");

		// choose an ID for the new array
		let new_id = match self.free_array_ids.iter().next() {
			Some(id) => {
				*id as usize
			},
			None => {
				let old_len = self.arrays.len();
				self.arrays.push(Vec::new());

				old_len
			}
		};

		self.arrays[new_id].resize(capacity as usize, 0);
		self.free_array_ids.remove(&(new_id as Platter));

		return new_id as Platter;
	}

	fn index_array(&self, id: Platter, offset: Platter) 
			-> Result<Platter, UMFailure> {
		return match self.arrays.get(id as usize) {
			Some(arr) => 
				if offset as usize > arr.len() {
					Err(UMFailure::OutOfBoundArrayAccess)
				} else { 
					Ok(arr[offset as usize]) 
				},
			None => Err(UMFailure::InactiveArrayAccess)
		}
	}

	fn amend_array(&mut self, id: Platter, offset: Platter, value: Platter) 
			-> Result<(), UMFailure> {
		return match self.arrays.get_mut(id as usize) {
			Some(arr) => 
				if offset as usize > arr.len() {
					Err(UMFailure::OutOfBoundArrayAccess)
				} else {
					arr[offset as usize] = value;
					Ok(())
				},
			None => Err(UMFailure::InactiveArrayAccess)
		}
	}

	fn abandon_array(&mut self, id: Platter) -> Result<(), UMFailure> {
		// println!("abandoning array");

		if id == 0 {
			// abandoning the program array
			return Err(UMFailure::AbandonedProgramArray);
		}

		if self.free_array_ids.contains(&id) || 
				id as usize >= self.arrays.len() {
			// abandoning an array not present in the list of arrays
			return Err(UMFailure::AbandonedArrayNotActive);
		} else {
			self.free_array_ids.insert(id);
			self.arrays[id as usize].clear();

			return Ok(());
		}
	}

	fn load_program(&mut self, b: usize, c: usize) -> Result<(), UMFailure> {
		// fetch args from regs
		let array_id = self.regs[b];
		let new_ef = self.regs[c];

		match array_id {
			0 => {
				// fast path: don't duplicate 0-array
			},
			_ => {
				// slow path: copy non-0 array to 0-array

				unsafe {
				// load B array and copy it
				let old_program = match self.arrays.get(array_id as usize) {
						Some(a) => a as *const Vec<Platter>,
						// trying to load program out of an unallocated array
						None => return Err(UMFailure::InactiveArrayProgramLoaded)
				};

				self.arrays[0].clone_from(&*old_program);
				}
			}
		};

		// reset the EF from C
		self.ef = new_ef;

		return Ok(());
	}
}