diff options
Diffstat (limited to '2018/src/device.rs')
| -rw-r--r-- | 2018/src/device.rs | 354 |
1 files changed, 354 insertions, 0 deletions
diff --git a/2018/src/device.rs b/2018/src/device.rs new file mode 100644 index 0000000..7eaf8d3 --- /dev/null +++ b/2018/src/device.rs @@ -0,0 +1,354 @@ +#![allow(dead_code)] + +use std::fmt; +use std::io::{self, BufRead}; +use std::str; + +#[derive(Copy, Clone)] +enum RawOpcode { + Addr, Addi, + Mulr, Muli, + Banr, Bani, + Borr, Bori, + Setr, Seti, + Gtir, Gtri, Gtrr, + Eqir, Eqri, Eqrr, +} + +impl str::FromStr for RawOpcode { + type Err = io::Error; + + fn from_str(s: &str) -> io::Result<Self> { + Ok(match s { + "addr" => RawOpcode::Addr, + "addi" => RawOpcode::Addi, + "mulr" => RawOpcode::Mulr, + "muli" => RawOpcode::Muli, + "banr" => RawOpcode::Banr, + "bani" => RawOpcode::Bani, + "borr" => RawOpcode::Borr, + "bori" => RawOpcode::Bori, + "setr" => RawOpcode::Setr, + "seti" => RawOpcode::Seti, + "gtir" => RawOpcode::Gtir, + "gtri" => RawOpcode::Gtri, + "gtrr" => RawOpcode::Gtrr, + "eqir" => RawOpcode::Eqir, + "eqri" => RawOpcode::Eqri, + "eqrr" => RawOpcode::Eqrr, + _ => panic!("Invalid raw opcode"), + }) + } +} + +#[derive(Copy, Clone)] +pub enum Oper { + Reg(usize), + Num(usize), +} + +impl Oper { + pub fn map_reg<F: Fn(usize) -> Oper>(&mut self, func: F) { + *self = match *self { + Oper::Reg(r) => func(r), + Oper::Num(n) => Oper::Num(n) + }; + } +} + +impl fmt::Display for Oper { + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { + match self { + Oper::Reg(r) => write!(w, "r{}", r), + Oper::Num(n) => write!(w, "{}", n), + } + } +} + +struct RawInstr { + op: RawOpcode, + a: usize, + b: usize, + c: usize, +} + +impl fmt::Display for RawInstr { + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { + match self.op { + RawOpcode::Addr => write!(w, "r{} <- {} + {}", self.c, self.a, self.b), + RawOpcode::Addi => write!(w, "r{} <- {} + {}", self.c, self.a, self.b), + RawOpcode::Mulr => write!(w, "r{} <- {} * {}", self.c, self.a, self.b), + RawOpcode::Muli => write!(w, "r{} <- {} * {}", self.c, self.a, self.b), + RawOpcode::Banr => write!(w, "r{} <- {} & {}", self.c, self.a, self.b), + RawOpcode::Bani => write!(w, "r{} <- {} & {}", self.c, self.a, self.b), + RawOpcode::Borr => write!(w, "r{} <- {} | {}", self.c, self.a, self.b), + RawOpcode::Bori => write!(w, "r{} <- {} | {}", self.c, self.a, self.b), + RawOpcode::Setr => write!(w, "r{} <- {}", self.c, self.a), + RawOpcode::Seti => write!(w, "r{} <- {}", self.c, self.a), + RawOpcode::Gtir => write!(w, "r{} <- {} > {}", self.c, self.a, self.b), + RawOpcode::Gtri => write!(w, "r{} <- {} > {}", self.c, self.a, self.b), + RawOpcode::Gtrr => write!(w, "r{} <- {} > {}", self.c, self.a, self.b), + RawOpcode::Eqir => write!(w, "r{} <- {} == {}", self.c, self.a, self.b), + RawOpcode::Eqri => write!(w, "r{} <- {} == {}", self.c, self.a, self.b), + RawOpcode::Eqrr => write!(w, "r{} <- {} == {}", self.c, self.a, self.b), + } + } +} + +impl str::FromStr for RawInstr { + type Err = io::Error; + + fn from_str(line: &str) -> io::Result<Self> { + let mut iter = line.split(' '); + + let mut next_string = move || iter.next().ok_or(io::Error::new(io::ErrorKind::Other, "Invalid raw instruction")); + macro_rules! next_int { + ( $var:ident ) => { + let $var = next_string()?.parse() + .or(Err(io::Error::new(io::ErrorKind::Other, "Invalid number in raw instruction")))?; + } + }; + + let op = next_string()?.parse()?; + next_int!(a); + next_int!(b); + next_int!(c); + Ok(RawInstr { op, a, b, c }) + } +} + +pub enum Instr { + // src1, src2, dest + Add(Oper, Oper, usize), + Mul(Oper, Oper, usize), + Ban(Oper, Oper, usize), + Bor(Oper, Oper, usize), + Grt(Oper, Oper, usize), + Equ(Oper, Oper, usize), + Set(Oper, usize), +} + +impl Instr { + fn from_raw_instr(ins: &RawInstr) -> Self { + match ins.op { + RawOpcode::Addr => Instr::Add(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Addi => Instr::Add(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), + RawOpcode::Mulr => Instr::Mul(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Muli => Instr::Mul(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), + RawOpcode::Banr => Instr::Ban(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Bani => Instr::Ban(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), + RawOpcode::Borr => Instr::Bor(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Bori => Instr::Bor(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), + RawOpcode::Setr => Instr::Set(Oper::Reg(ins.a), ins.c), + RawOpcode::Seti => Instr::Set(Oper::Num(ins.a), ins.c), + RawOpcode::Gtir => Instr::Grt(Oper::Num(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Gtri => Instr::Grt(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), + RawOpcode::Gtrr => Instr::Grt(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Eqir => Instr::Equ(Oper::Num(ins.a), Oper::Reg(ins.b), ins.c), + RawOpcode::Eqri => Instr::Equ(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), + RawOpcode::Eqrr => Instr::Equ(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), + } + } + + pub fn map_reads<F: Fn(usize) -> Oper>(&mut self, func: F) { + match self { + Instr::Add(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, + Instr::Mul(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, + Instr::Ban(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, + Instr::Bor(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, + Instr::Grt(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, + Instr::Equ(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, + Instr::Set(a, _) => a.map_reg(func), + }; + } + + pub fn inline_reg(&mut self, reg: usize, value: Oper) { + self.map_reads(|r| if r == reg { value } else { Oper::Reg(r) }); + } +} + +impl fmt::Display for Instr { + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { + match self { + Instr::Add(a, b, c) => write!(w, "r{} <- {} + {}", c, a, b), + Instr::Mul(a, b, c) => write!(w, "r{} <- {} * {}", c, a, b), + Instr::Ban(a, b, c) => write!(w, "r{} <- {} & {}", c, a, b), + Instr::Bor(a, b, c) => write!(w, "r{} <- {} | {}", c, a, b), + Instr::Grt(a, b, c) => write!(w, "r{} <- {} > {}", c, a, b), + Instr::Equ(a, b, c) => write!(w, "r{} <- {} == {}", c, a, b), + Instr::Set(a, c) => write!(w, "r{} <- {}", c, a), + } + } +} + +#[derive(PartialEq, Eq, Clone)] +pub struct Machine { + pub regs: [usize; 6], +} + +impl Machine { + pub fn exec(&mut self, instr: &Instr) { + match instr { + &Instr::Add(a, b, c) => self.regs[c] = self.eval_oper(a) + self.eval_oper(b), + &Instr::Mul(a, b, c) => self.regs[c] = self.eval_oper(a) * self.eval_oper(b), + &Instr::Ban(a, b, c) => self.regs[c] = self.eval_oper(a) & self.eval_oper(b), + &Instr::Bor(a, b, c) => self.regs[c] = self.eval_oper(a) | self.eval_oper(b), + &Instr::Grt(a, b, c) => self.regs[c] = if self.eval_oper(a) > self.eval_oper(b) { 1 } else { 0 }, + &Instr::Equ(a, b, c) => self.regs[c] = if self.eval_oper(a) == self.eval_oper(b) { 1 } else { 0 }, + &Instr::Set(a, c) => self.regs[c] = self.eval_oper(a), + } + } + + pub fn exec_program(&mut self, prog: &[Instr], ip_reg: usize) { + let mut ip = 0; + while ip < prog.len() { + self.regs[ip_reg] = ip; + println!("{} ip={} {}", self, ip, prog[ip]); + self.exec(&prog[ip]); + ip = self.regs[ip_reg] + 1; + } + } + + pub fn eval_oper(&self, oper: Oper) -> usize { + match oper { + Oper::Reg(r) => self.regs[r], + Oper::Num(n) => n, + } + } +} + +impl fmt::Display for Machine { + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { + write!(w, "{}", self.regs[0])?; + for i in 1..6 { + write!(w, " {}", self.regs[i])?; + } + Ok(()) + } +} + +pub fn parse_program<T: BufRead>(reader: T) -> io::Result<(usize, Vec<Instr>)> { + let mut lines = reader.lines(); + let ip_reg = match lines.next() { + Some(line) => { + let line = line?; + if line.starts_with("#ip ") && line.len() == 5 { + (line.as_bytes()[4] - '0' as u8) as usize + } else { + return Err(io::Error::new(io::ErrorKind::Other, "Program parse error: initial line not '#ip n'")); + } + } + None => { + return Err(io::Error::new(io::ErrorKind::Other, "Program parse error: empty file")); + } + }; + + let instrs = lines.map(|l| { + Ok(Instr::from_raw_instr(&l?.parse()?)) + }).collect::<io::Result<Vec<Instr>>>()?; + + Ok((ip_reg, instrs)) +} + +#[derive(Clone, PartialEq, Eq)] +pub enum SymVal { + Val(usize), + Add(Box<SymVal>, Box<SymVal>), + Mul(Box<SymVal>, Box<SymVal>), + Ban(Box<SymVal>, Box<SymVal>), + Bor(Box<SymVal>, Box<SymVal>), + Grt(Box<SymVal>, Box<SymVal>), + Equ(Box<SymVal>, Box<SymVal>), + If1(Box<SymVal>, Box<SymVal>, Box<SymVal>), +} + +impl Default for SymVal { + fn default() -> Self { + SymVal::Val(0) + } +} + +impl SymVal { + pub fn simplify(&mut self) { + let optres = match self { + SymVal::Val(n) => Some(SymVal::Val(*n)), + SymVal::Add(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x + y) } + SymVal::Mul(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x * y) } + SymVal::Ban(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x & y) } + SymVal::Bor(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x | y) } + SymVal::Grt(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| (x > y) as usize) } + SymVal::Equ(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| (x == y) as usize) } + SymVal::If1(c, t, e) => { + c.simplify(); t.simplify(); e.simplify(); + match **c { + SymVal::Val(1) => Some((**t).clone()), + SymVal::Val(_) => Some((**e).clone()), + _ => None, + } + } + }; + if let Some(res) = optres { + *self = res; + } + } + + pub fn eval_vals<F: Fn(usize, usize) -> usize>(a: &SymVal, b: &SymVal, func: F) -> Option<SymVal> { + match (a, b) { + (&SymVal::Val(x), &SymVal::Val(y)) => Some(SymVal::Val(func(x, y))), + _ => None, + } + } +} + +pub struct SymbolicMachine { + pub regs: [SymVal; 6], +} + +impl SymbolicMachine { + pub fn from(m: &Machine) -> Self { + let mut sm = SymbolicMachine { regs: Default::default() }; + for i in 0..6 { + sm.regs[i] = SymVal::Val(m.regs[i]); + } + sm + } + + pub fn exec_oper(&self, oper: Oper) -> SymVal { + match oper { + Oper::Reg(r) => self.regs[r].clone(), + Oper::Num(n) => SymVal::Val(n), + } + } + + pub fn exec(&mut self, instr: &Instr) { + let (c, mut val) = match instr { + &Instr::Add(a, b, c) => (c, SymVal::Add(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), + &Instr::Mul(a, b, c) => (c, SymVal::Mul(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), + &Instr::Ban(a, b, c) => (c, SymVal::Ban(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), + &Instr::Bor(a, b, c) => (c, SymVal::Bor(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), + &Instr::Grt(a, b, c) => (c, SymVal::Grt(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), + &Instr::Equ(a, b, c) => (c, SymVal::Equ(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), + &Instr::Set(a, c) => (c, self.exec_oper(a)), + }; + + val.simplify(); + self.regs[c] = val; + } + + fn exec_find_loop(&mut self, prog: &[Instr], start_ip: usize, ip_reg: usize) -> bool { + let mut ip = start_ip; + while ip != start_ip { + self.regs[ip_reg] = SymVal::Val(ip); + // println!("{} ip={} {}", self, ip, prog[ip]); + self.exec(&prog[ip]); + self.regs[ip_reg].simplify(); + ip = match self.regs[ip_reg] { + SymVal::Val(v) => v, + _ => return false, + }; + } + + false + } +} + |