spongefish_circuit/
expr.rs

1//! Linear expressions over wires: `x * a + y * b + z`.
2
3use alloc::vec::Vec;
4use core::ops::{Add, Mul};
5
6use spongefish::Unit;
7
8use crate::allocator::FieldVar;
9
10/// The arithmetic a value type needs to appear in a linear equation.
11///
12/// [`Unit`] supplies zero and cloning; this adds one, addition, and
13/// multiplication, which is what evaluating `Σ weight_i · value_i` and giving
14/// a bare wire the weight one require.
15///
16/// The integer units form the Boolean ring: addition is XOR, multiplication
17/// is AND, and one is all ones. A weight is then a bit mask and an equation
18/// is an XOR relation between masked wires, which is what a statement about
19/// a byte-oriented permutation needs. A field unit uses its field arithmetic.
20#[allow(clippy::return_self_not_must_use)]
21pub trait Ring: Unit + PartialEq {
22    /// The multiplicative identity.
23    const ONE: Self;
24
25    fn add(self, other: Self) -> Self;
26
27    fn mul(self, other: Self) -> Self;
28}
29
30macro_rules! impl_boolean_ring {
31    ($($t:ty),*) => {$(
32        impl Ring for $t {
33            const ONE: Self = !0;
34
35            fn add(self, other: Self) -> Self {
36                self ^ other
37            }
38
39            fn mul(self, other: Self) -> Self {
40                self & other
41            }
42        }
43    )*};
44}
45
46impl_boolean_ring!(u8, u32, u64, u128);
47
48/// A wire scaled by a constant: `weight · var`.
49#[derive(Clone, Debug, PartialEq, Eq)]
50pub struct Weighted<T> {
51    pub var: FieldVar,
52    pub weight: T,
53}
54
55/// A linear combination of wires, the left-hand side of a
56/// [`LinearEquation`][crate::permutation::LinearEquation].
57#[derive(Clone, Debug, PartialEq, Eq)]
58pub struct Sum<T>(Vec<Weighted<T>>);
59
60impl<T> Sum<T> {
61    /// The terms of the sum, in the order they were added.
62    pub fn terms(&self) -> &[Weighted<T>] {
63        &self.0
64    }
65}
66
67impl<T> Default for Sum<T> {
68    fn default() -> Self {
69        Self(Vec::new())
70    }
71}
72
73impl<T> From<Weighted<T>> for Sum<T> {
74    fn from(term: Weighted<T>) -> Self {
75        Self(alloc::vec![term])
76    }
77}
78
79/// A bare wire is the term `1 · var`.
80impl<T: Ring> From<FieldVar> for Weighted<T> {
81    fn from(var: FieldVar) -> Self {
82        Self {
83            var,
84            weight: T::ONE,
85        }
86    }
87}
88
89impl<T: Ring> From<FieldVar> for Sum<T> {
90    fn from(var: FieldVar) -> Self {
91        Weighted::from(var).into()
92    }
93}
94
95impl<T, U: Into<Weighted<T>>> FromIterator<U> for Sum<T> {
96    fn from_iter<I: IntoIterator<Item = U>>(iter: I) -> Self {
97        Self(iter.into_iter().map(Into::into).collect())
98    }
99}
100
101impl<T, U: Into<Self>> core::iter::Sum<U> for Sum<T> {
102    fn sum<I: IntoIterator<Item = U>>(iter: I) -> Self {
103        iter.into_iter().fold(Self::default(), |acc, rhs| acc + rhs)
104    }
105}
106
107impl<T> Mul<T> for FieldVar {
108    type Output = Weighted<T>;
109
110    fn mul(self, weight: T) -> Weighted<T> {
111        Weighted { var: self, weight }
112    }
113}
114
115impl<T: Ring> Mul<T> for Weighted<T> {
116    type Output = Self;
117
118    fn mul(self, rhs: T) -> Self {
119        Self {
120            var: self.var,
121            weight: Ring::mul(self.weight, rhs),
122        }
123    }
124}
125
126impl<T, Rhs: Into<Self>> Add<Rhs> for Sum<T> {
127    type Output = Self;
128
129    fn add(mut self, rhs: Rhs) -> Self {
130        self.0.extend(rhs.into().0);
131        self
132    }
133}
134
135impl<T, Rhs: Into<Sum<T>>> Add<Rhs> for Weighted<T> {
136    type Output = Sum<T>;
137
138    fn add(self, rhs: Rhs) -> Sum<T> {
139        Sum::from(self) + rhs
140    }
141}
142
143// A wire on the left of `+` needs the right-hand side to name `T`, so
144// `a + b * w` and `a + sum` work while `a + b` alone does not: give one
145// term a weight, or collect the wires with `Sum::from_iter`.
146impl<T: Ring> Add<Weighted<T>> for FieldVar {
147    type Output = Sum<T>;
148
149    fn add(self, rhs: Weighted<T>) -> Sum<T> {
150        Sum::from(self) + rhs
151    }
152}
153
154impl<T: Ring> Add<Sum<T>> for FieldVar {
155    type Output = Sum<T>;
156
157    fn add(self, rhs: Sum<T>) -> Sum<T> {
158        Sum::from(self) + rhs
159    }
160}
spongefish_circuit/expr.rs

spongefish_circuit/
expr.rs
