From 235ac0674304c847488ec8fd00f6971add654b4e Mon Sep 17 00:00:00 2001 From: Cassie Jones Date: Sun, 19 Jan 2020 07:54:42 -0500 Subject: [PATCH] Implement instruction decoder --- isa.txt | 2 +- toolchain/Cargo.lock | 153 +++++++++++++++++- toolchain/Cargo.toml | 1 + toolchain/proptest-regressions/inst/test.txt | 5 + toolchain/src/inst.rs | 17 +- toolchain/src/inst/decode.rs | 154 ++++++++++++++++++- toolchain/src/inst/encode.rs | 38 +++-- toolchain/src/inst/test.rs | 8 +- 8 files changed, 339 insertions(+), 39 deletions(-) diff --git a/isa.txt b/isa.txt index 846e799..82eed60 100644 --- a/isa.txt +++ b/isa.txt @@ -15,9 +15,9 @@ ALUI: lsl lsr asr rol clr set tog ext 1000_aabb => MOVE: a = b # when a != b 1001_aaoo => ALU1: a = op a 101f_aabb => LDST: a <-> [b] -110o_aabb oiii_iiii => BRNC: branch if a op b # when a != b 1100_0000 iiii_iiii => JUMP: jump offset 1101_aabb fiii_iiii => LSI0: a <-> [imm * 2] # a == b +110o_aabb oiii_iiii => BRNC: branch if a op b # when a != b 1110_aa00 iiii_iiii => ALUA: a = a + imm 1110_aa01 oooo_iiii => ALUI: a = a op imm 1110_aa10 iiii_iiii => LDLI: lo(a) = imm diff --git a/toolchain/Cargo.lock b/toolchain/Cargo.lock index 3df833b..3ae9849 100644 --- a/toolchain/Cargo.lock +++ b/toolchain/Cargo.lock @@ -33,6 +33,28 @@ version = "1.2.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693" +[[package]] +name = "bitmatch" +version = "0.1.0" +dependencies = [ + "boolean_expression", + "proc-macro2 1.0.8", + "quote 1.0.2", + "syn 1.0.13", +] + +[[package]] +name = "boolean_expression" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d8bc527fa8fb9f89e6d049fdea9ab86d738265a1bc814ec7ac6e93e1d4769f84" +dependencies = [ + "indoc", + "itertools", + "rand 0.3.23", + "smallvec", +] + [[package]] name = "byteorder" version = "1.3.2" @@ -86,6 +108,35 @@ dependencies = [ "wasi", ] +[[package]] +name = "indoc" +version = "0.2.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "098a82c5223d3162a32d79f84e43d718c32f050d07b796285684ee43059bc8c4" +dependencies = [ + "indoc-impl", + "proc-macro-hack", +] + +[[package]] +name = "indoc-impl" +version = "0.2.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "55cf2a15c870db1b07595cc9adaece19fac97d59a16665e79cd728b391a6b711" +dependencies = [ + "proc-macro-hack", + "proc-macro2 0.4.30", + "quote 0.6.13", + "syn 0.15.44", + "unindent", +] + +[[package]] +name = "itertools" +version = "0.4.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c4a9b56eb56058f43dc66e58f40a214b2ccbc9f3df51861b63d51dec7b65bc3f" + [[package]] name = "lazy_static" version = "1.4.0" @@ -113,13 +164,37 @@ version = "0.2.6" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "74490b50b9fbe561ac330df47c08f3f33073d2d00c150f719147d7c54522fa1b" +[[package]] +name = "proc-macro-hack" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "463bf29e7f11344e58c9e01f171470ab15c925c6822ad75028cc1c0e1d1eb63b" +dependencies = [ + "proc-macro-hack-impl", +] + +[[package]] +name = "proc-macro-hack-impl" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38c47dcb1594802de8c02f3b899e2018c78291168a22c281be21ea0fb4796842" + [[package]] name = "proc-macro2" version = "0.4.30" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "cf3d2011ab5c909338f7887f4fc896d35932e29146c12c8d01da6b22a80ba759" dependencies = [ - "unicode-xid", + "unicode-xid 0.1.0", +] + +[[package]] +name = "proc-macro2" +version = "1.0.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3acb317c6ff86a4e579dfa00fc5e6cca91ecbb4e7eb2df0468805b674eb88548" +dependencies = [ + "unicode-xid 0.2.0", ] [[package]] @@ -148,9 +223,9 @@ version = "0.1.2" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "d31edb17edac73aeacc947bd61462dda15220584268896a58e12f053d767f15b" dependencies = [ - "proc-macro2", - "quote", - "syn", + "proc-macro2 0.4.30", + "quote 0.6.13", + "syn 0.15.44", ] [[package]] @@ -165,7 +240,39 @@ version = "0.6.13" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "6ce23b6b870e8f94f81fb0a363d65d86675884b34a09043c81e5562f11c1f8e1" dependencies = [ - "proc-macro2", + "proc-macro2 0.4.30", +] + +[[package]] +name = "quote" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "053a8c8bcc71fcce321828dc897a98ab9760bef03a4fc36693c231e5b3216cfe" +dependencies = [ + "proc-macro2 1.0.8", +] + +[[package]] +name = "rand" +version = "0.3.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "64ac302d8f83c0c1974bf758f6b041c6c8ada916fbb44a609158ca8b064cc76c" +dependencies = [ + "libc", + "rand 0.4.6", +] + +[[package]] +name = "rand" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "552840b97013b1a26992c11eac34bdd778e464601a4c2054b5f0bff7c6761293" +dependencies = [ + "fuchsia-cprng", + "libc", + "rand_core 0.3.1", + "rdrand", + "winapi", ] [[package]] @@ -357,15 +464,32 @@ dependencies = [ "wait-timeout", ] +[[package]] +name = "smallvec" +version = "0.1.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fcc8d19212aacecf95e4a7a2179b26f7aeb9732a915cf01f05b0d3e044865410" + [[package]] name = "syn" version = "0.15.44" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "9ca4b3b69a77cbe1ffc9e198781b7acb0c7365a883670e8f1c1bc66fba79a5c5" dependencies = [ - "proc-macro2", - "quote", - "unicode-xid", + "proc-macro2 0.4.30", + "quote 0.6.13", + "unicode-xid 0.1.0", +] + +[[package]] +name = "syn" +version = "1.0.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e4ff033220a41d1a57d8125eab57bf5263783dfdcc18688b1dacc6ce9651ef8" +dependencies = [ + "proc-macro2 1.0.8", + "quote 1.0.2", + "unicode-xid 0.2.0", ] [[package]] @@ -386,6 +510,7 @@ dependencies = [ name = "toolchain" version = "0.1.0" dependencies = [ + "bitmatch", "proptest", "proptest-derive", ] @@ -396,6 +521,18 @@ version = "0.1.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "fc72304796d0818e357ead4e000d19c9c174ab23dc11093ac919054d20a6a7fc" +[[package]] +name = "unicode-xid" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c" + +[[package]] +name = "unindent" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "63f18aa3b0e35fed5a0048f029558b1518095ffe2a0a31fb87c93dece93a4993" + [[package]] name = "wait-timeout" version = "0.2.0" diff --git a/toolchain/Cargo.toml b/toolchain/Cargo.toml index fd9a1be..bb6101e 100644 --- a/toolchain/Cargo.toml +++ b/toolchain/Cargo.toml @@ -7,6 +7,7 @@ edition = "2018" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] +bitmatch = { path = "../../../rust/bitmatch" } [dev-dependencies] proptest = "0.9.4" diff --git a/toolchain/proptest-regressions/inst/test.txt b/toolchain/proptest-regressions/inst/test.txt index ddfe16f..89ecff8 100644 --- a/toolchain/proptest-regressions/inst/test.txt +++ b/toolchain/proptest-regressions/inst/test.txt @@ -5,3 +5,8 @@ # It is recommended to check this file in to source control so that # everyone who runs the test benefits from these saved cases. cc bd1463681b9efb78a1ecf699478179a28e5228c837d2b2ee06b2b8418f24419f # shrinks to inst = Nope +cc af33135027a031746327d679fc7f54559b8aa44221558d7f95d7bc38e095df0c # shrinks to inst = Move(R0, R0) +cc 7cb716a881c511f52040ab2b46969de5c36bf65ef63769178c837147c336cfe0 # shrinks to inst = Mem(Ld, R0, Extended { base: R0, offset: I5(0), stack: false, size: Byte }) +cc ff0a86719d997a70f2503b3e56b81efef7ca07725b94faa03f01e0f19d428a41 # shrinks to inst = Mem(Ld, R0, Fixed(U7(0))) +cc 5f30401f2762182ff6a8cf0074a54e473bb3aad534d23b122448558788b75c3b # shrinks to inst = LdImm(Low, R1, 0) +cc 9941d1de2ba8e9f7a16de9d2824f0b8f6962a459ef9d7b4e0bc91231f0eec583 # shrinks to inst = AluCompact(R0, Lsl, U4(16)) diff --git a/toolchain/src/inst.rs b/toolchain/src/inst.rs index 5f20e61..130afc9 100644 --- a/toolchain/src/inst.rs +++ b/toolchain/src/inst.rs @@ -65,7 +65,7 @@ pub enum Op2 { #[derive(Clone, Copy, Debug, PartialEq, Eq)] #[cfg_attr(test, derive(Arbitrary))] -pub struct U4(#[cfg_attr(test, proptest(strategy = "0..=16u8"))] u8); +pub struct U4(#[cfg_attr(test, proptest(strategy = "0..=15u8"))] u8); #[derive(Clone, Copy, Debug, PartialEq, Eq)] #[cfg_attr(test, derive(Arbitrary))] pub struct I5(#[cfg_attr(test, proptest(strategy = "-16..=15i8"))] i8); @@ -74,7 +74,7 @@ pub struct I5(#[cfg_attr(test, proptest(strategy = "-16..=15i8"))] i8); pub struct I7(#[cfg_attr(test, proptest(strategy = "-64..=63i8"))] i8); #[derive(Clone, Copy, Debug, PartialEq, Eq)] #[cfg_attr(test, derive(Arbitrary))] -pub struct U7(#[cfg_attr(test, proptest(strategy = "0..=128u8"))] u8); +pub struct U7(#[cfg_attr(test, proptest(strategy = "0..=127u8"))] u8); #[derive(Clone, Copy, Debug, PartialEq, Eq)] #[cfg_attr(test, derive(Arbitrary))] @@ -108,17 +108,17 @@ pub enum Addr { #[derive(Clone, Copy, Debug, Eq)] #[cfg_attr(test, derive(Arbitrary))] pub enum Cond { - #[cfg_attr(test, proptest(strategy = "test::cond_strategy(Cond::Eql)"))] + #[cfg_attr(test, proptest(strategy = "test::regpair(Cond::Eql)"))] Eql(Reg, Reg), - #[cfg_attr(test, proptest(strategy = "test::cond_strategy(Cond::Neq)"))] + #[cfg_attr(test, proptest(strategy = "test::regpair(Cond::Neq)"))] Neq(Reg, Reg), - #[cfg_attr(test, proptest(strategy = "test::cond_strategy(Cond::Test)"))] + #[cfg_attr(test, proptest(strategy = "test::regpair(Cond::Test)"))] Test(Reg, Reg), - #[cfg_attr(test, proptest(strategy = "test::cond_strategy(Cond::TestNot)"))] + #[cfg_attr(test, proptest(strategy = "test::regpair(Cond::TestNot)"))] TestNot(Reg, Reg), - #[cfg_attr(test, proptest(strategy = "test::cond_strategy(Cond::Lt)"))] + #[cfg_attr(test, proptest(strategy = "test::regpair(Cond::Lt)"))] Lt(Reg, Reg), - #[cfg_attr(test, proptest(strategy = "test::cond_strategy(Cond::Ult)"))] + #[cfg_attr(test, proptest(strategy = "test::regpair(Cond::Ult)"))] Ult(Reg, Reg), } @@ -129,6 +129,7 @@ pub enum Inst { Nope, Alu2(Reg, Op2, Reg), Jalr(Reg), + #[cfg_attr(test, proptest(strategy = "test::regpair(Inst::Move)"))] Move(Reg, Reg), Alu1(Reg, Op1), Mem(LdSt, Reg, Addr), diff --git a/toolchain/src/inst/decode.rs b/toolchain/src/inst/decode.rs index 66dc13f..659d057 100644 --- a/toolchain/src/inst/decode.rs +++ b/toolchain/src/inst/decode.rs @@ -1,12 +1,160 @@ -use crate::inst::Inst; -use std::io::{self, Read}; +use crate::inst::{Addr, Cond, Half, Inst, LdSt, Op1, Op2, OpC, Reg, Size, I5, I7, U4, U7}; +use bitmatch::bitmatch; +use std::{ + convert::TryInto, + fmt::Debug, + io::{self, Read}, +}; pub trait Decode { fn decode(code: &mut impl Read) -> io::Result; } impl Decode for Inst { + #[bitmatch] fn decode(code: &mut impl Read) -> io::Result { - Ok(Inst::Halt) + use Inst::*; + let x = read_1_byte(code)?; + Ok( + #[bitmatch] + match x { + "0000_0000" => Halt, + "0000_0001" => Nope, + "000?_????" => return Err(reserved()), + "0ooo_aabb" => Alu2(reg(a), op2(o), reg(b)), + "1000_aabb" if a == b => Jalr(reg(a)), + "1000_aabb" => Move(reg(a), reg(b)), + "1001_aaoo" => Alu1(reg(a), op1(o)), + "101f_aabb" => Mem(ldst(f), reg(a), Addr::Reg(reg(b))), + "11??_????" => { + let y = read_1_byte(code).map_err(reject_eof)?; + #[bitmatch] + match bitpack!("xxxx_xxxx yyyy_yyyy") { + "00_0000 iiii_iiii" => JumpI(i as i8), + "01_aabb fiii_iiii" if a == b => Mem(ldst(f), reg(a), fixed(i)), + "0o_aabb oiii_iiii" => Branch(cond(o, a, b), i7(i)), + "10_aa00 iiii_iiii" => AddI(reg(a), i as i8), + "10_aa01 oooo_iiii" => AluCompact(reg(a), op_c(o), U4(i as u8)), + "10_aa10 iiii_iiii" => LdImm(Half::Low, reg(a), i as u8), + "10_aa11 iiii_iiii" => LdImm(Half::High, reg(a), i as u8), + "11_aabb wpsi_iiii" => Mem( + ldst(w), + reg(a), + Addr::Extended { + base: reg(b), + offset: i5(i), + stack: p != 0, + size: size(s), + }, + ), + } + } + }, + ) } } + +fn fixed(x: u16) -> Addr { + Addr::Fixed(U7(x as u8)) +} + +fn i7(x: u16) -> I7 { + I7(((x as i8) << 1) >> 1) +} + +fn i5(x: u16) -> I5 { + I5(((x as i8) << 3) >> 3) +} + +fn read_1_byte(r: &mut impl Read) -> io::Result { + let mut result = [0]; + r.read_exact(&mut result[..])?; + Ok(result[0]) +} + +fn reject_eof(err: io::Error) -> io::Error { + if err.kind() == io::ErrorKind::UnexpectedEof { + io::Error::new( + io::ErrorKind::InvalidInput, + "instruction missing second byte", + ) + } else { + err + } +} + +fn reg(r: impl TryInto) -> Reg { + match r.try_into().unwrap() & 3 { + 0 => Reg::R0, + 1 => Reg::R1, + 2 => Reg::R2, + _ => Reg::R3, + } +} + +fn cond(o: u16, a: u16, b: u16) -> Cond { + let (a, b) = (reg(a), reg(b)); + debug_assert_ne!(a, b); + match (o, a < b) { + (0, true) => Cond::Eql(a, b), + (0, false) => Cond::Neq(a, b), + (1, true) => Cond::Test(a, b), + (1, false) => Cond::TestNot(a, b), + (2, _) => Cond::Lt(a, b), + (3, _) => Cond::Ult(a, b), + _ => unreachable!("invalid op"), + } +} + +fn ldst(l: impl TryInto) -> LdSt { + match l.try_into().unwrap() & 1 { + 0 => LdSt::Ld, + _ => LdSt::St, + } +} + +fn op1(o: u8) -> Op1 { + match o { + 0 => Op1::Inc, + 1 => Op1::Dec, + 2 => Op1::Neg, + 3 => Op1::Compl, + _ => unreachable!("invalid Op1 value"), + } +} + +fn op2(o: u8) -> Op2 { + match o { + 2 => Op2::Add, + 3 => Op2::Sub, + 4 => Op2::AddPc, + 5 => Op2::And, + 6 => Op2::Or, + 7 => Op2::Xor, + _ => unreachable!("invalid Op2 value"), + } +} + +fn op_c(c: u16) -> OpC { + match c & 7 { + 0 => OpC::Lsl, + 1 => OpC::Lsr, + 2 => OpC::Asr, + 3 => OpC::Rol, + 4 => OpC::Clr, + 5 => OpC::Set, + 6 => OpC::Tog, + _ => OpC::Ext, + } +} + +fn size(u: u16) -> Size { + match u & 1 { + 0 => Size::Byte, + _ => Size::Word, + } +} + +fn reserved() -> io::Error { + io::Error::new(io::ErrorKind::InvalidInput, "reserved instruction") +} diff --git a/toolchain/src/inst/encode.rs b/toolchain/src/inst/encode.rs index 0103e46..e8aedb6 100644 --- a/toolchain/src/inst/encode.rs +++ b/toolchain/src/inst/encode.rs @@ -1,4 +1,5 @@ -use crate::inst::{Addr, Cond, Inst, Reg, I7, U4}; +use crate::inst::{Addr, Cond, Inst, LdSt, Reg, Size, I5, I7, U4, U7}; +use bitmatch::bitmatch; use std::io::{self, Write}; pub trait Encode { @@ -11,7 +12,7 @@ fn unpack_cond(c: Cond) -> (u8, u8, Reg, Reg) { Eql(ra, rb) => (0, 0, ra.min(rb), ra.max(rb)), Neq(ra, rb) => (0, 0, ra.max(rb), ra.min(rb)), Test(ra, rb) => (0, 1, ra.min(rb), ra.max(rb)), - TestNot(ra, rb) => (0, 1, ra.min(rb), ra.max(rb)), + TestNot(ra, rb) => (0, 1, ra.max(rb), ra.min(rb)), Lt(ra, rb) => (1, 0, ra, rb), Ult(ra, rb) => (1, 1, ra, rb), }; @@ -20,6 +21,7 @@ fn unpack_cond(c: Cond) -> (u8, u8, Reg, Reg) { } impl Encode for Inst { + #[bitmatch] fn encode(&self, out: &mut impl Write) -> io::Result<()> { use Inst::*; match *self { @@ -31,36 +33,40 @@ impl Encode for Inst { Jalr(r) => out.write_all(&[0x80 | (r as u8) << 2 | r as u8])?, Move(rd, r2) => { debug_assert_ne!(rd, r2, "Can't move to self"); - out.write_all(&[0x00, (rd as u8) << 2 | r2 as u8])? + out.write_all(&[0x80 | (rd as u8) << 2 | r2 as u8])? } Alu1(r, op) => out.write_all(&[0x90 | (r as u8) << 2 | op as u8])?, Mem(op, r_data, Addr::Reg(r_addr)) => { out.write_all(&[0xa0 | (op as u8) << 4 | (r_data as u8) << 2 | r_addr as u8])? } - Branch(cond, I7(off)) => { - let (o2, o1, ra, rb) = unpack_cond(cond); - out.write_all(&[ - 0xc0 | o2 << 4 | (ra as u8) << 2 | rb as u8, - o1 << 7 | off as u8, - ])? + Branch(cond, I7(i)) => { + let (o, p, a, b) = unpack_cond(cond); + out.write_all(&[bitpack!("110o_aabb"), bitpack!("piii_iiii")])? } JumpI(off) => out.write_all(&[0xc0, off as u8])?, - Mem(op, rd, Addr::Fixed(addr)) => out.write_all(&[])?, + Mem(f, a, Addr::Fixed(U7(i))) => { + let b = a; + out.write_all(&[bitpack!("1101_aabb"), bitpack!("fiii_iiii")])? + } AddI(rd, imm) => out.write_all(&[0xe0 | (rd as u8) << 2, imm as u8])?, AluCompact(rd, op, U4(imm)) => { out.write_all(&[0xe1 | (rd as u8) << 2, (op as u8) << 4 | imm as u8])? } - LdImm(h, rd, imm) => out.write_all(&[0xe2 | (h as u8) << 1, imm])?, + LdImm(h, a, i) => out.write_all(&[bitpack!("1110_aa1h"), bitpack!("iiii_iiii")])?, Mem( op, - rd, + a, Addr::Extended { - base, - offset, - stack, + base: b, + offset: I5(i), + stack: p, size, }, - ) => out.write_all(&[])?, + ) => { + let w = op == LdSt::St; + let s = size == Size::Word; + out.write_all(&[bitpack!("1111_aabb"), bitpack!("wpsi_iiii")])? + } } Ok(()) } diff --git a/toolchain/src/inst/test.rs b/toolchain/src/inst/test.rs index 826da5a..efe1b5e 100644 --- a/toolchain/src/inst/test.rs +++ b/toolchain/src/inst/test.rs @@ -1,8 +1,8 @@ use super::{Cond, Decode, Encode, Inst, Reg}; use proptest::prelude::*; -use std::io::Cursor; +use std::{fmt::Debug, io::Cursor}; -pub(super) fn cond_strategy(op: impl Fn(Reg, Reg) -> Cond) -> impl Strategy { +pub(super) fn regpair(op: impl Fn(Reg, Reg) -> T) -> impl Strategy { (0..4u8, 1..4u8).prop_map(move |(a, b)| op(reg_num(a), reg_num(a + b))) } @@ -22,9 +22,11 @@ proptest! { let mut buffer = [0, 0]; let mut cursor = Cursor::new(&mut buffer[..]); inst.encode(&mut cursor).expect("Should encode instruction"); + let len = cursor.position(); cursor.set_position(0); let out_inst = Inst::decode(&mut cursor) .expect(&format!("Should decode instruction bytes {:?}", cursor.get_ref())); - prop_assert_eq!(inst, out_inst, "inst should round-trip the same"); + let buffer = &buffer[..len as usize]; + prop_assert_eq!(inst, out_inst, "inst should round-trip the same. Encoded as {:x?}", buffer); } } -- 2.47.0