use std::fmt;
use std::rc::Rc;
#[derive(Clone, Copy, PartialEq, Eq)]
pub(crate) enum Op {
And,
Or,
Xor,
Add,
Sub,
Mul,
Udiv,
Urem,
Sdiv,
Srem,
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub(crate) enum Cmp {
Eq,
Ne,
Ult,
Ule,
Slt,
Sle,
}
pub(crate) enum Node {
Const(u32, u64),
Var(u32, usize),
Not(Bv),
Neg(Bv),
Bin(Op, Bv, Bv),
ShlC(Bv, u32),
ShrC(Bv, u32, bool), ShlV(Bv, Bv), ShrV(Bv, Bv, bool), RotC(Bv, u32, bool), RotV(Bv, Bv, bool), Compare(Cmp, Bv, Bv),
Zext(Bv, u32),
Sext(Bv, u32),
Extract(Bv, u32, u32), Concat(Bv, Bv), Ite(Bv, Bv, Bv), }
#[derive(Clone)]
pub struct Bv(pub(crate) Rc<Node>);
impl Bv {
pub(crate) fn wrap(n: Node) -> Bv {
Bv(Rc::new(n))
}
#[must_use]
pub fn ptr_eq(&self, other: &Bv) -> bool {
Rc::ptr_eq(&self.0, &other.0)
}
#[must_use]
pub fn width(&self) -> u32 {
match &*self.0 {
Node::Const(w, _) | Node::Var(w, _) => *w,
Node::Not(a) | Node::Neg(a) | Node::Bin(_, a, _) => a.width(),
Node::ShlC(a, _) | Node::ShrC(a, _, _) => a.width(),
Node::ShlV(a, _) | Node::ShrV(a, _, _) | Node::RotC(a, _, _) | Node::RotV(a, _, _) => {
a.width()
}
Node::Compare(_, _, _) => 1,
Node::Zext(_, w) | Node::Sext(_, w) => *w,
Node::Extract(_, hi, lo) => hi - lo + 1,
Node::Concat(a, b) => a.width() + b.width(),
Node::Ite(_, a, _) => a.width(),
}
}
#[must_use]
pub fn val(v: u64, w: u32) -> Bv {
assert!(
(1..=64).contains(&w),
"constant width must be 1..=64, got {w}"
);
Bv::wrap(Node::Const(w, mask(v, w)))
}
#[must_use]
pub fn as_const(&self) -> Option<u64> {
if let Node::Const(_, v) = &*self.0 {
Some(*v)
} else {
None
}
}
#[must_use]
pub fn var_ids(&self) -> Vec<usize> {
let mut seen = std::collections::HashSet::new();
let mut ids = Vec::new();
let mut stack = vec![self.clone()];
while let Some(cur) = stack.pop() {
if !seen.insert(Rc::as_ptr(&cur.0) as usize) {
continue;
}
match &*cur.0 {
Node::Const(_, _) => {}
Node::Var(_, id) => ids.push(*id),
Node::Not(a)
| Node::Neg(a)
| Node::ShlC(a, _)
| Node::ShrC(a, _, _)
| Node::RotC(a, _, _)
| Node::Zext(a, _)
| Node::Sext(a, _)
| Node::Extract(a, _, _) => stack.push(a.clone()),
Node::Bin(_, a, b)
| Node::Compare(_, a, b)
| Node::Concat(a, b)
| Node::ShlV(a, b)
| Node::ShrV(a, b, _)
| Node::RotV(a, b, _) => {
stack.push(a.clone());
stack.push(b.clone());
}
Node::Ite(a, b, c) => {
stack.push(a.clone());
stack.push(b.clone());
stack.push(c.clone());
}
}
}
ids
}
#[must_use]
pub fn not(&self) -> Bv {
Bv::wrap(Node::Not(self.clone()))
}
#[must_use]
pub fn neg(&self) -> Bv {
Bv::wrap(Node::Neg(self.clone()))
}
#[must_use]
pub fn and(&self, o: &Bv) -> Bv {
self.bin(Op::And, o)
}
#[must_use]
pub fn or(&self, o: &Bv) -> Bv {
self.bin(Op::Or, o)
}
#[must_use]
pub fn xor(&self, o: &Bv) -> Bv {
self.bin(Op::Xor, o)
}
#[must_use]
pub fn add(&self, o: &Bv) -> Bv {
self.bin(Op::Add, o)
}
#[must_use]
pub fn sub(&self, o: &Bv) -> Bv {
self.bin(Op::Sub, o)
}
#[must_use]
pub fn mul(&self, o: &Bv) -> Bv {
self.bin(Op::Mul, o)
}
#[must_use]
pub fn udiv(&self, o: &Bv) -> Bv {
self.bin(Op::Udiv, o)
}
#[must_use]
pub fn urem(&self, o: &Bv) -> Bv {
self.bin(Op::Urem, o)
}
#[must_use]
pub fn sdiv(&self, o: &Bv) -> Bv {
self.bin(Op::Sdiv, o)
}
#[must_use]
pub fn srem(&self, o: &Bv) -> Bv {
self.bin(Op::Srem, o)
}
fn bin(&self, op: Op, o: &Bv) -> Bv {
assert_eq!(
self.width(),
o.width(),
"bitvector op needs equal widths, got {} and {}",
self.width(),
o.width()
);
Bv::wrap(Node::Bin(op, self.clone(), o.clone()))
}
#[must_use]
pub fn shl(&self, k: u32) -> Bv {
Bv::wrap(Node::ShlC(self.clone(), k))
}
#[must_use]
pub fn lshr(&self, k: u32) -> Bv {
Bv::wrap(Node::ShrC(self.clone(), k, false))
}
#[must_use]
pub fn ashr(&self, k: u32) -> Bv {
Bv::wrap(Node::ShrC(self.clone(), k, true))
}
#[must_use]
pub fn shl_var(&self, k: &Bv) -> Bv {
Bv::wrap(Node::ShlV(self.clone(), k.clone()))
}
#[must_use]
pub fn lshr_var(&self, k: &Bv) -> Bv {
Bv::wrap(Node::ShrV(self.clone(), k.clone(), false))
}
#[must_use]
pub fn ashr_var(&self, k: &Bv) -> Bv {
Bv::wrap(Node::ShrV(self.clone(), k.clone(), true))
}
#[must_use]
pub fn rotl(&self, k: u32) -> Bv {
Bv::wrap(Node::RotC(self.clone(), k, true))
}
#[must_use]
pub fn rotr(&self, k: u32) -> Bv {
Bv::wrap(Node::RotC(self.clone(), k, false))
}
#[must_use]
pub fn rotl_var(&self, k: &Bv) -> Bv {
Bv::wrap(Node::RotV(self.clone(), k.clone(), true))
}
#[must_use]
pub fn rotr_var(&self, k: &Bv) -> Bv {
Bv::wrap(Node::RotV(self.clone(), k.clone(), false))
}
#[must_use]
pub fn eq(&self, o: &Bv) -> Bv {
self.cmp(Cmp::Eq, o)
}
#[must_use]
pub fn ne(&self, o: &Bv) -> Bv {
self.cmp(Cmp::Ne, o)
}
#[must_use]
pub fn ult(&self, o: &Bv) -> Bv {
self.cmp(Cmp::Ult, o)
}
#[must_use]
pub fn ule(&self, o: &Bv) -> Bv {
self.cmp(Cmp::Ule, o)
}
#[must_use]
pub fn ugt(&self, o: &Bv) -> Bv {
o.cmp(Cmp::Ult, self)
}
#[must_use]
pub fn uge(&self, o: &Bv) -> Bv {
o.cmp(Cmp::Ule, self)
}
#[must_use]
pub fn slt(&self, o: &Bv) -> Bv {
self.cmp(Cmp::Slt, o)
}
#[must_use]
pub fn sle(&self, o: &Bv) -> Bv {
self.cmp(Cmp::Sle, o)
}
#[must_use]
pub fn sgt(&self, o: &Bv) -> Bv {
o.cmp(Cmp::Slt, self)
}
#[must_use]
pub fn sge(&self, o: &Bv) -> Bv {
o.cmp(Cmp::Sle, self)
}
fn cmp(&self, c: Cmp, o: &Bv) -> Bv {
assert_eq!(
self.width(),
o.width(),
"comparison needs equal widths, got {} and {}",
self.width(),
o.width()
);
Bv::wrap(Node::Compare(c, self.clone(), o.clone()))
}
#[must_use]
pub fn zext(&self, new_w: u32) -> Bv {
assert!(
new_w >= self.width(),
"zext must widen: {} to {new_w}",
self.width()
);
assert!(new_w <= 64, "width must be 1..=64, got {new_w}");
Bv::wrap(Node::Zext(self.clone(), new_w))
}
#[must_use]
pub fn sext(&self, new_w: u32) -> Bv {
assert!(
new_w >= self.width(),
"sext must widen: {} to {new_w}",
self.width()
);
assert!(new_w <= 64, "width must be 1..=64, got {new_w}");
Bv::wrap(Node::Sext(self.clone(), new_w))
}
#[must_use]
pub fn extract(&self, hi: u32, lo: u32) -> Bv {
assert!(
hi >= lo && hi < self.width(),
"extract[{hi}:{lo}] out of range for width {}",
self.width()
);
Bv::wrap(Node::Extract(self.clone(), hi, lo))
}
#[must_use]
pub fn concat(&self, low: &Bv) -> Bv {
let w = self.width() + low.width();
assert!(
w <= 64,
"concatenation is {w} bits wide, over the 64-bit limit"
);
Bv::wrap(Node::Concat(self.clone(), low.clone()))
}
#[must_use]
pub fn ite(cond: &Bv, then: &Bv, els: &Bv) -> Bv {
assert_eq!(
cond.width(),
1,
"ite condition must be 1 bit, got {}",
cond.width()
);
assert_eq!(
then.width(),
els.width(),
"ite branches must match: {} and {}",
then.width(),
els.width()
);
Bv::wrap(Node::Ite(cond.clone(), then.clone(), els.clone()))
}
#[must_use]
pub fn land(&self, o: &Bv) -> Bv {
assert_eq!(
self.width(),
1,
"land operand must be 1 bit, got {}",
self.width()
);
assert_eq!(
o.width(),
1,
"land operand must be 1 bit, got {}",
o.width()
);
self.and(o)
}
}
#[must_use]
pub fn mask(v: u64, w: u32) -> u64 {
if w >= 64 { v } else { v & ((1u64 << w) - 1) }
}
impl fmt::Debug for Bv {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "Bv({self})")
}
}
impl fmt::Display for Bv {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match &*self.0 {
Node::Const(w, v) => write!(f, "#{v:x}:{w}"),
Node::Var(w, id) => write!(f, "v{id}:{w}"),
Node::Not(a) => write!(f, "(~ {a})"),
Node::Neg(a) => write!(f, "(- {a})"),
Node::Bin(op, a, b) => {
let s = match op {
Op::And => "&",
Op::Or => "|",
Op::Xor => "^",
Op::Add => "+",
Op::Sub => "-",
Op::Mul => "*",
Op::Udiv => "/u",
Op::Urem => "%u",
Op::Sdiv => "/s",
Op::Srem => "%s",
};
write!(f, "({s} {a} {b})")
}
Node::ShlC(a, k) => write!(f, "(<< {a} {k})"),
Node::ShrC(a, k, arith) => {
write!(f, "({} {a} {k})", if *arith { ">>s" } else { ">>u" })
}
Node::ShlV(a, k) => write!(f, "(<<v {a} {k})"),
Node::ShrV(a, k, arith) => {
write!(f, "({}v {a} {k})", if *arith { ">>s" } else { ">>u" })
}
Node::RotC(a, k, left) => {
write!(f, "({} {a} {k})", if *left { "rotl" } else { "rotr" })
}
Node::RotV(a, k, left) => {
write!(f, "({}v {a} {k})", if *left { "rotl" } else { "rotr" })
}
Node::Compare(c, a, b) => {
let s = match c {
Cmp::Eq => "==",
Cmp::Ne => "!=",
Cmp::Ult => "<u",
Cmp::Ule => "<=u",
Cmp::Slt => "<s",
Cmp::Sle => "<=s",
};
write!(f, "({s} {a} {b})")
}
Node::Zext(a, w) => write!(f, "(zext{w} {a})"),
Node::Sext(a, w) => write!(f, "(sext{w} {a})"),
Node::Extract(a, hi, lo) => write!(f, "(ext[{hi}:{lo}] {a})"),
Node::Concat(a, b) => write!(f, "(cat {a} {b})"),
Node::Ite(c, a, b) => write!(f, "(ite {c} {a} {b})"),
}
}
}