2019-12-07 12:57:46 +00:00
|
|
|
use failure::Error;
|
|
|
|
|
|
|
|
#[repr(u8)]
|
|
|
|
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy, Debug)]
|
|
|
|
pub enum ParameterMode {
|
|
|
|
Position = 0,
|
|
|
|
Immediate = 1,
|
2019-12-09 08:04:37 +00:00
|
|
|
Relative = 2,
|
2019-12-07 12:57:46 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
impl ParameterMode {
|
|
|
|
pub fn decode(code: CELL) -> Result<(Self, CELL), Error> {
|
|
|
|
let rem = code / 10;
|
|
|
|
let mode = match code % 10 {
|
|
|
|
0 => Self::Position,
|
|
|
|
1 => Self::Immediate,
|
2019-12-09 08:04:37 +00:00
|
|
|
2 => Self::Relative,
|
2019-12-07 12:57:46 +00:00
|
|
|
m => failure::bail!("Unknown parameter mode: {}", m),
|
|
|
|
};
|
|
|
|
Ok((mode, rem))
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
#[repr(u8)]
|
|
|
|
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy, Debug)]
|
|
|
|
pub enum Instruction {
|
|
|
|
Add = 1,
|
|
|
|
Mul = 2,
|
|
|
|
In = 3,
|
|
|
|
Out = 4,
|
|
|
|
JumpIfTrue = 5,
|
|
|
|
JumpIfFalse = 6,
|
|
|
|
LessThan = 7,
|
|
|
|
Equal = 8,
|
2019-12-09 08:04:37 +00:00
|
|
|
AdjustBase = 9,
|
2019-12-07 12:57:46 +00:00
|
|
|
Halt = 99,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl Instruction {
|
|
|
|
pub fn decode(opcode: CELL) -> Result<(Self, CELL), Error> {
|
|
|
|
let rem = opcode / 100;
|
|
|
|
let instr = match opcode % 100 {
|
|
|
|
1 => Self::Add,
|
|
|
|
2 => Self::Mul,
|
|
|
|
3 => Self::In,
|
|
|
|
4 => Self::Out,
|
|
|
|
5 => Self::JumpIfTrue,
|
|
|
|
6 => Self::JumpIfFalse,
|
|
|
|
7 => Self::LessThan,
|
|
|
|
8 => Self::Equal,
|
2019-12-09 08:04:37 +00:00
|
|
|
9 => Self::AdjustBase,
|
2019-12-07 12:57:46 +00:00
|
|
|
99 => Self::Halt,
|
|
|
|
n => failure::bail!("Unknown instruction code {}", n),
|
|
|
|
};
|
|
|
|
Ok((instr, rem))
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy, Debug)]
|
|
|
|
pub struct OpCode {
|
|
|
|
pub instruction: Instruction,
|
|
|
|
pub modes: [ParameterMode; 3],
|
|
|
|
}
|
|
|
|
|
|
|
|
impl OpCode {
|
|
|
|
pub fn decode(opcode: CELL) -> Result<OpCode, Error> {
|
|
|
|
let (instruction, code) = Instruction::decode(opcode)?;
|
|
|
|
let (mode0, code) = ParameterMode::decode(code)?;
|
|
|
|
let (mode1, code) = ParameterMode::decode(code)?;
|
|
|
|
let (mode2, code) = ParameterMode::decode(code)?;
|
|
|
|
failure::ensure!(code == 0);
|
|
|
|
let modes = [mode0, mode1, mode2];
|
|
|
|
|
|
|
|
Ok(OpCode {
|
|
|
|
instruction,
|
|
|
|
modes,
|
|
|
|
})
|
|
|
|
}
|
|
|
|
}
|
2019-12-07 10:20:57 +00:00
|
|
|
|
|
|
|
pub type CELL = i64;
|
|
|
|
|
|
|
|
#[derive(PartialEq, Eq, Clone, Debug)]
|
|
|
|
pub enum SimulateStep {
|
|
|
|
Finished,
|
|
|
|
WaitForInput,
|
|
|
|
Output(CELL),
|
|
|
|
}
|
|
|
|
|
|
|
|
impl SimulateStep {
|
|
|
|
pub fn expect_output(self) -> CELL {
|
|
|
|
if let Self::Output(v) = self {
|
|
|
|
return v;
|
|
|
|
}
|
|
|
|
panic!("Expected Output, got {:?}", self);
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn expect_finished(self) {
|
|
|
|
if let Self::Finished = self { return; }
|
|
|
|
panic!("Expected Finished, got {:?}", self);
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn expect_wait_for_input(self) {
|
|
|
|
if let Self::WaitForInput = self { return; }
|
|
|
|
panic!("Expected WaitForInput, got {:?}", self);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
#[derive(PartialEq, Eq, Clone, Debug)]
|
|
|
|
pub struct IntCode {
|
2019-12-07 12:57:46 +00:00
|
|
|
/// instruction pointer
|
2019-12-07 10:20:57 +00:00
|
|
|
pub ip: usize,
|
2019-12-09 08:04:37 +00:00
|
|
|
/// base for relative mode
|
|
|
|
pub base: CELL,
|
2019-12-07 12:57:46 +00:00
|
|
|
/// next value to use for an "IN" (3) instruction (which will clear it)
|
2019-12-07 10:20:57 +00:00
|
|
|
pub next_input: Option<CELL>,
|
2019-12-07 12:57:46 +00:00
|
|
|
/// memory of machine (both code and data)
|
2019-12-07 10:20:57 +00:00
|
|
|
pub data: Vec<CELL>,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl IntCode {
|
2019-12-09 08:04:37 +00:00
|
|
|
fn read(&self, addr: CELL) -> CELL {
|
|
|
|
assert!(addr >= 0, "Tried reading negative address");
|
|
|
|
self.data.get(addr as usize).cloned().unwrap_or(0)
|
|
|
|
}
|
|
|
|
|
|
|
|
fn write(&mut self, addr: CELL, value: CELL) {
|
|
|
|
assert!(addr >= 0, "Tried reading negative address");
|
|
|
|
let addr = addr as usize;
|
|
|
|
if addr >= self.data.len() {
|
|
|
|
self.data.resize(addr + 1, 0);
|
|
|
|
}
|
|
|
|
self.data[addr] = value;
|
|
|
|
}
|
|
|
|
|
2019-12-07 10:20:57 +00:00
|
|
|
#[inline(always)]
|
2019-12-07 12:57:46 +00:00
|
|
|
fn fetch(&mut self, modes: &mut &[ParameterMode]) -> CELL {
|
|
|
|
let mode = modes[0];
|
|
|
|
*modes = &modes[1..];
|
2019-12-09 08:04:37 +00:00
|
|
|
let imm = self.read(self.ip as CELL);
|
2019-12-07 10:20:57 +00:00
|
|
|
self.ip += 1;
|
|
|
|
match mode {
|
2019-12-09 08:04:37 +00:00
|
|
|
ParameterMode::Position => self.read(imm),
|
2019-12-07 12:57:46 +00:00
|
|
|
ParameterMode::Immediate => imm,
|
2019-12-09 08:04:37 +00:00
|
|
|
ParameterMode::Relative => self.read(self.base + imm),
|
2019-12-07 10:20:57 +00:00
|
|
|
}
|
|
|
|
}
|
2019-12-07 12:57:46 +00:00
|
|
|
|
2019-12-07 10:20:57 +00:00
|
|
|
#[inline(always)]
|
2019-12-07 12:57:46 +00:00
|
|
|
fn store(&mut self, modes: &mut &[ParameterMode], value: CELL) {
|
|
|
|
let mode = modes[0];
|
|
|
|
*modes = &modes[1..];
|
2019-12-09 08:04:37 +00:00
|
|
|
let addr = self.ip as CELL;
|
2019-12-07 10:20:57 +00:00
|
|
|
self.ip += 1;
|
2019-12-09 08:04:37 +00:00
|
|
|
let addr = match mode {
|
|
|
|
ParameterMode::Position => self.read(addr),
|
|
|
|
ParameterMode::Immediate => addr,
|
|
|
|
ParameterMode::Relative => self.base + self.read(addr),
|
|
|
|
};
|
|
|
|
self.write(addr, value);
|
2019-12-07 10:20:57 +00:00
|
|
|
}
|
|
|
|
|
2019-12-07 12:57:46 +00:00
|
|
|
fn binop<F>(&mut self, op: F, modes: &mut &[ParameterMode])
|
2019-12-07 10:20:57 +00:00
|
|
|
where
|
|
|
|
F: FnOnce(CELL, CELL) -> CELL,
|
|
|
|
{
|
2019-12-07 12:57:46 +00:00
|
|
|
let src1 = self.fetch(modes);
|
|
|
|
let src2 = self.fetch(modes);
|
|
|
|
self.store(modes, op(src1, src2));
|
2019-12-07 10:20:57 +00:00
|
|
|
}
|
|
|
|
|
2019-12-07 12:57:46 +00:00
|
|
|
/// run simple machine without I/O to completion
|
2019-12-07 10:20:57 +00:00
|
|
|
pub fn simulate(&mut self) {
|
|
|
|
assert_eq!(self.ip, 0);
|
|
|
|
assert!(self.next_input.is_none());
|
|
|
|
self.simulate_step().expect_finished();
|
|
|
|
}
|
|
|
|
|
2019-12-09 08:04:37 +00:00
|
|
|
pub fn simulate_io<I>(&mut self, i: I) -> Vec<CELL>
|
|
|
|
where
|
|
|
|
I: IntoIterator<Item = CELL>,
|
|
|
|
{
|
|
|
|
assert_eq!(self.ip, 0);
|
|
|
|
assert!(self.next_input.is_none());
|
|
|
|
let mut i = i.into_iter().fuse();
|
|
|
|
let mut buf = Vec::new();
|
|
|
|
loop {
|
|
|
|
match self.simulate_step() {
|
|
|
|
SimulateStep::Finished => break,
|
|
|
|
SimulateStep::WaitForInput => {
|
|
|
|
self.next_input = Some(i.next().expect("no further input"));
|
|
|
|
},
|
|
|
|
SimulateStep::Output(n) => buf.push(n),
|
|
|
|
}
|
|
|
|
}
|
|
|
|
if i.next().is_some() {
|
|
|
|
panic!("Input not used completely");
|
|
|
|
}
|
|
|
|
buf
|
|
|
|
}
|
|
|
|
|
2019-12-07 12:57:46 +00:00
|
|
|
/// run a machine until:
|
|
|
|
/// - it needs input, but `next_input` is `None`
|
|
|
|
/// - it outputs a value
|
|
|
|
/// - it finishes
|
2019-12-07 10:20:57 +00:00
|
|
|
pub fn simulate_step(&mut self) -> SimulateStep {
|
|
|
|
loop {
|
2019-12-07 12:57:46 +00:00
|
|
|
let opcode = OpCode::decode(self.data[self.ip]).unwrap();
|
|
|
|
let modes = &mut &opcode.modes[..];
|
2019-12-07 10:20:57 +00:00
|
|
|
self.ip += 1;
|
2019-12-07 12:57:46 +00:00
|
|
|
|
|
|
|
match opcode.instruction {
|
|
|
|
Instruction::Add => self.binop(|a, b| a + b, modes),
|
|
|
|
Instruction::Mul => self.binop(|a, b| a * b, modes),
|
|
|
|
Instruction::LessThan => self.binop(|a, b| if a < b { 1 } else { 0 }, modes),
|
|
|
|
Instruction::Equal => self.binop(|a, b| if a == b { 1 } else { 0 }, modes),
|
|
|
|
Instruction::In => {
|
2019-12-07 10:20:57 +00:00
|
|
|
if let Some(v) = self.next_input.take() {
|
2019-12-07 12:57:46 +00:00
|
|
|
self.store(modes, v);
|
2019-12-07 10:20:57 +00:00
|
|
|
} else {
|
|
|
|
self.ip -= 1; // go back to opcode
|
|
|
|
return SimulateStep::WaitForInput;
|
|
|
|
}
|
|
|
|
},
|
2019-12-07 12:57:46 +00:00
|
|
|
Instruction::Out => {
|
|
|
|
return SimulateStep::Output(self.fetch(modes));
|
2019-12-07 10:20:57 +00:00
|
|
|
},
|
2019-12-07 12:57:46 +00:00
|
|
|
Instruction::Halt => {
|
2019-12-07 10:20:57 +00:00
|
|
|
self.ip -= 1; // make re-running this step end up here again
|
|
|
|
return SimulateStep::Finished;
|
|
|
|
},
|
2019-12-07 12:57:46 +00:00
|
|
|
Instruction::JumpIfTrue => {
|
|
|
|
if self.fetch(modes) != 0 {
|
|
|
|
self.ip = self.fetch(modes) as usize;
|
2019-12-07 10:20:57 +00:00
|
|
|
} else {
|
2019-12-07 12:57:46 +00:00
|
|
|
self.ip += 1; // skip parameter for target
|
2019-12-07 10:20:57 +00:00
|
|
|
}
|
|
|
|
},
|
2019-12-07 12:57:46 +00:00
|
|
|
Instruction::JumpIfFalse => {
|
|
|
|
if self.fetch(modes) == 0 {
|
|
|
|
self.ip = self.fetch(modes) as usize;
|
2019-12-07 10:20:57 +00:00
|
|
|
} else {
|
2019-12-07 12:57:46 +00:00
|
|
|
self.ip += 1; // skip parameter for target
|
2019-12-07 10:20:57 +00:00
|
|
|
}
|
|
|
|
},
|
2019-12-09 08:04:37 +00:00
|
|
|
Instruction::AdjustBase => {
|
|
|
|
self.base += self.fetch(modes);
|
|
|
|
}
|
2019-12-07 10:20:57 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
impl std::str::FromStr for IntCode {
|
|
|
|
type Err = <CELL as std::str::FromStr>::Err;
|
|
|
|
|
|
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
|
|
Ok(IntCode {
|
|
|
|
ip: 0,
|
2019-12-09 08:04:37 +00:00
|
|
|
base: 0,
|
2019-12-07 10:20:57 +00:00
|
|
|
next_input: None,
|
|
|
|
data: s.split(',').map(|s| s.trim().parse::<CELL>()).collect::<Result<_, _>>()?,
|
|
|
|
})
|
|
|
|
}
|
|
|
|
}
|