use crate::{Bv, Solver};
pub const BABY_BEAR: u32 = 0x7800_0001;
#[derive(Clone, Debug)]
pub struct Fp {
v: Bv,
}
impl Fp {
pub const WIDTH: u32 = 32;
pub fn bits(&self) -> &Bv {
&self.v
}
pub fn into_bits(self) -> Bv {
self.v
}
pub fn var(s: &mut Solver, name: &str) -> Fp {
Fp {
v: s.var(name, Self::WIDTH),
}
}
pub fn val(x: u32) -> Fp {
assert!(x < BABY_BEAR, "field constant {x} is not canonical");
Fp {
v: Bv::val(x as u64, Self::WIDTH),
}
}
pub fn add(&self, rhs: &Fp) -> Fp {
let sum = self.v.add(&rhs.v);
let p = Bv::val(BABY_BEAR as u64, Self::WIDTH);
Fp {
v: Bv::ite(&sum.uge(&p), &sum.sub(&p), &sum),
}
}
pub fn sub(&self, rhs: &Fp) -> Fp {
let d = self.v.sub(&rhs.v);
let p = Bv::val(BABY_BEAR as u64, Self::WIDTH);
Fp {
v: Bv::ite(&self.v.uge(&rhs.v), &d, &d.add(&p)),
}
}
pub fn mul(&self, rhs: &Fp) -> Fp {
let prod = self.v.zext(64).mul(&rhs.v.zext(64));
let r = prod.urem(&Bv::val(BABY_BEAR as u64, 64));
Fp {
v: r.extract(Self::WIDTH - 1, 0),
}
}
pub fn is_canonical(&self) -> Bv {
self.v.ult(&Bv::val(BABY_BEAR as u64, Self::WIDTH))
}
pub fn eq(&self, rhs: &Fp) -> Bv {
self.v.eq(&rhs.v)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::Solution;
#[test]
fn add_sub_mul_known_values() {
let mut s = Solver::new().with_max_clauses(300_000);
let a = Fp::val(1_000_000_000);
let b = Fp::val(1_000_000_000);
let c = Fp::val(3);
s.assert(a.add(&b).eq(&Fp::val(2_000_000_000)));
s.assert(Fp::val(BABY_BEAR - 1).add(&Fp::val(1)).eq(&Fp::val(0)));
s.assert(Fp::val(0).sub(&Fp::val(1)).eq(&Fp::val(BABY_BEAR - 1)));
s.assert(c.mul(&Fp::val(4)).eq(&Fp::val(12)));
s.assert(
Fp::val(BABY_BEAR - 1)
.mul(&Fp::val(BABY_BEAR - 1))
.eq(&Fp::val(1)),
);
match s.check() {
Solution::Sat(_) => {}
other => panic!("expected SAT, got {other:?}"),
}
}
#[test]
fn mul_is_commutative() {
let mut s = Solver::new().with_max_clauses(300_000);
let a = Fp::var(&mut s, "a");
let b = Fp::var(&mut s, "b");
s.assert(a.is_canonical());
s.assert(b.is_canonical());
s.assert(a.mul(&b).eq(&b.mul(&a)).not());
match s.check() {
Solution::Unsat => {}
other => panic!("expected UNSAT (mul commutes), got {other:?}"),
}
}
#[test]
fn field_op_air_does_not_force_canonical_result() {
use crate::{Bv, Solution, Solver};
let mut s = Solver::new();
let m = BABY_BEAR as u64;
let a = s.var("a", 32);
let b = s.var("b", 32);
let result = s.var("result", 32);
let carry = s.var("carry", 32);
let m32 = Bv::val(m, 32);
let m64 = Bv::val(m, 64);
s.assert(a.ult(&m32));
s.assert(b.ult(&m32));
let prod = a.zext(64).mul(&b.zext(64));
let rhs = result.zext(64).add(&carry.zext(64).mul(&m64));
s.assert(prod.eq(&rhs));
s.assert(result.uge(&m32));
match s.check() {
Solution::Sat(model) => {
let a = model.get("a").unwrap();
let b = model.get("b").unwrap();
let result = model.get("result").unwrap();
let carry = model.get("carry").unwrap();
assert!(a < m && b < m, "operand premise violated");
assert_eq!(
a as u128 * b as u128,
result as u128 + carry as u128 * m as u128,
"AIR equation violated"
);
assert!(result >= m, "result should be non-canonical (>= M)");
eprintln!(
"SAT: a={a}, b={b}, result={result} (M={m}), carry={carry} \
-> field_op AIR accepts a non-canonical result"
);
}
Solution::Unsat => panic!("expected SAT: the AIR must admit a non-canonical result"),
Solution::Unknown => panic!("solver gave up (budget/clause cap)"),
}
}
}