primitives/algebra/field/binary/
gf2.rs

1use core::iter::{Product, Sum};
2use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
3
4use ff::Field;
5use hybrid_array::Array;
6use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
7use typenum::U1;
8
9use crate::{
10    algebra::{
11        field::FieldExtension,
12        ops::{AccReduce, DefaultDotProduct, IntoWide, MulAccReduce, ReduceWide},
13        uniform_bytes::FromUniformBytes,
14    },
15    impl_borrow_variants,
16};
17
18// TODO: see if changing u8 to Choice makes more sense
19#[derive(
20    Clone, Copy, Debug, Eq, PartialEq, Hash, serde::Deserialize, serde::Serialize, Ord, PartialOrd,
21)]
22pub struct Gf2(pub(super) u8);
23
24impl Default for Gf2 {
25    fn default() -> Self {
26        Gf2::ZERO
27    }
28}
29
30impl IntoWide for Gf2 {
31    #[inline]
32    fn to_wide(&self) -> Gf2 {
33        *self
34    }
35
36    #[inline]
37    fn zero_wide() -> Gf2 {
38        Gf2::ZERO
39    }
40}
41
42impl ReduceWide for Gf2 {
43    fn reduce_mod_order(a: Self) -> Self {
44        a
45    }
46}
47
48// Dot product: Gf2 x Gf2
49impl MulAccReduce for Gf2 {
50    type WideType = Self;
51
52    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
53        acc.0 ^= a.0 & b.0;
54    }
55}
56
57impl DefaultDotProduct for Gf2 {}
58
59// Dot product: Gf2 x &Gf2
60impl<'a> MulAccReduce<Self, &'a Self> for Gf2 {
61    type WideType = Self;
62
63    fn mul_acc(acc: &mut Self::WideType, a: Self, b: &'a Self) {
64        acc.0 ^= a.0 & b.0;
65    }
66}
67
68impl DefaultDotProduct<Self, &Self> for Gf2 {}
69
70// Dot product: &Gf2 x Gf2
71impl<'a> MulAccReduce<&'a Self, Self> for Gf2 {
72    type WideType = Self;
73
74    fn mul_acc(acc: &mut Self::WideType, a: &'a Self, b: Self) {
75        acc.0 ^= a.0 & b.0;
76    }
77}
78
79impl DefaultDotProduct<&Self, Self> for Gf2 {}
80
81// Dot product: &Gf2 x &Gf2
82impl<'a, 'b> MulAccReduce<&'a Self, &'b Self> for Gf2 {
83    type WideType = Self;
84
85    fn mul_acc(acc: &mut Self::WideType, a: &'a Self, b: &'b Self) {
86        acc.0 ^= a.0 & b.0;
87    }
88}
89
90impl DefaultDotProduct<&Self, &Self> for Gf2 {}
91
92impl AccReduce for Gf2 {
93    type WideType = Gf2;
94
95    #[inline]
96    fn acc(acc: &mut Self::WideType, a: Self) {
97        acc.0 ^= a.0;
98    }
99}
100
101impl AccReduce<&Self> for Gf2 {
102    type WideType = Gf2;
103
104    #[inline]
105    fn acc(acc: &mut Self::WideType, a: &Self) {
106        acc.0 ^= a.0;
107    }
108}
109
110impl ff::Field for Gf2 {
111    const ZERO: Self = Self(0);
112    const ONE: Self = Self(1);
113
114    fn random(mut rng: impl rand::RngCore) -> Self {
115        let mut tmp = [0u8; 1];
116        rng.fill_bytes(&mut tmp);
117        Self(tmp[0] & 1)
118    }
119
120    fn square(&self) -> Self {
121        Self(self.0)
122    }
123
124    fn double(&self) -> Self {
125        Self::ZERO
126    }
127
128    fn invert(&self) -> CtOption<Self> {
129        unimplemented!()
130    }
131
132    fn sqrt_ratio(_num: &Self, _div: &Self) -> (Choice, Self) {
133        unimplemented!()
134    }
135}
136
137impl FieldExtension for Gf2 {
138    type Subfield = Self;
139
140    type Degree = U1;
141    type FieldBitSize = U1;
142    type FieldBytesSize = U1;
143
144    fn to_subfield_elements(&self) -> impl ExactSizeIterator<Item = Self::Subfield> {
145        std::iter::once(*self)
146    }
147
148    fn from_subfield_elements(elems: &[Self::Subfield]) -> Option<Self> {
149        if elems.len() == 1 {
150            elems.first().copied()
151        } else {
152            None
153        }
154    }
155
156    fn to_le_bytes(&self) -> impl IntoIterator<Item = u8> {
157        std::iter::once(self.0)
158    }
159
160    fn from_le_bytes(bytes: &[u8]) -> Option<Self> {
161        bytes
162            .first()
163            .and_then(|&byte| if byte <= 1 { Some(Self(byte)) } else { None })
164    }
165
166    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self {
167        self * other
168    }
169
170    fn generator() -> Self {
171        Self::ONE
172    }
173}
174
175// === Field traits implementations === //
176
177impl ConditionallySelectable for Gf2 {
178    #[inline]
179    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
180        Gf2(u8::conditional_select(&a.0, &b.0, choice))
181    }
182}
183
184impl ConstantTimeEq for Gf2 {
185    #[inline]
186    fn ct_eq(&self, other: &Self) -> Choice {
187        self.0.ct_eq(&other.0)
188    }
189}
190
191impl Neg for &Gf2 {
192    type Output = Gf2;
193
194    #[inline]
195    fn neg(self) -> Self::Output {
196        *self
197    }
198}
199impl_borrow_variants!(Gf2, Neg, neg, -, );
200
201impl Add<&Gf2> for &Gf2 {
202    type Output = Gf2;
203
204    #[inline]
205    #[allow(clippy::suspicious_arithmetic_impl)]
206    fn add(self, rhs: &Gf2) -> Self::Output {
207        Gf2(self.0 ^ rhs.0)
208    }
209}
210impl_borrow_variants!(Gf2, Add, add, +, Gf2, );
211
212impl AddAssign for Gf2 {
213    #[inline]
214    fn add_assign(&mut self, rhs: Self) {
215        *self = *self + rhs;
216    }
217}
218
219impl AddAssign<&Gf2> for Gf2 {
220    #[inline]
221    fn add_assign(&mut self, rhs: &Gf2) {
222        *self = *self + rhs;
223    }
224}
225
226impl Sub<&Gf2> for &Gf2 {
227    type Output = Gf2;
228
229    #[inline]
230    #[allow(clippy::suspicious_arithmetic_impl)]
231    fn sub(self, rhs: &Gf2) -> Self::Output {
232        self + rhs
233    }
234}
235impl_borrow_variants!(Gf2, Sub, sub, -, Gf2, );
236
237impl SubAssign for Gf2 {
238    #[inline]
239    fn sub_assign(&mut self, rhs: Self) {
240        *self = *self - rhs;
241    }
242}
243
244impl SubAssign<&Gf2> for Gf2 {
245    #[inline]
246    fn sub_assign(&mut self, rhs: &Gf2) {
247        *self = *self - rhs;
248    }
249}
250
251impl Mul<&Gf2> for &Gf2 {
252    type Output = Gf2;
253
254    #[inline]
255    #[allow(clippy::suspicious_arithmetic_impl)]
256    fn mul(self, rhs: &Gf2) -> Self::Output {
257        Gf2(self.0 & rhs.0)
258    }
259}
260impl_borrow_variants!(Gf2, Mul, mul, *, Gf2, );
261
262impl MulAssign for Gf2 {
263    #[inline]
264    fn mul_assign(&mut self, rhs: Gf2) {
265        *self = *self * rhs;
266    }
267}
268
269impl<'a> MulAssign<&'a Gf2> for Gf2 {
270    #[inline]
271    fn mul_assign(&mut self, rhs: &'a Gf2) {
272        *self = *self * rhs;
273    }
274}
275
276impl Sum for Gf2 {
277    #[inline]
278    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
279        iter.fold(Gf2::ZERO, |a, b| a + b)
280    }
281}
282
283impl<'a> Sum<&'a Gf2> for Gf2 {
284    #[inline]
285    fn sum<I: Iterator<Item = &'a Gf2>>(iter: I) -> Self {
286        iter.fold(Gf2::ZERO, |a, b| a + b)
287    }
288}
289
290impl Product for Gf2 {
291    #[inline]
292    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
293        iter.fold(Gf2::ONE, |a, b| a * b)
294    }
295}
296
297impl<'a> Product<&'a Gf2> for Gf2 {
298    #[inline]
299    fn product<I: Iterator<Item = &'a Gf2>>(iter: I) -> Self {
300        iter.fold(Gf2::ONE, |a, b| a * b)
301    }
302}
303
304impl From<Gf2> for bool {
305    fn from(value: Gf2) -> Self {
306        value.0 == 1
307    }
308}
309
310impl From<&Gf2> for bool {
311    fn from(value: &Gf2) -> Self {
312        value.0 == 1
313    }
314}
315
316impl From<bool> for Gf2 {
317    fn from(value: bool) -> Self {
318        Gf2(value.into())
319    }
320}
321
322impl From<&bool> for Gf2 {
323    fn from(value: &bool) -> Self {
324        (*value).into()
325    }
326}
327
328impl From<&Gf2> for u64 {
329    fn from(value: &Gf2) -> Self {
330        value.0 as u64
331    }
332}
333
334impl From<u64> for Gf2 {
335    fn from(val: u64) -> Self {
336        Gf2((val & 1) as u8)
337    }
338}
339
340impl From<u128> for Gf2 {
341    fn from(val: u128) -> Self {
342        Gf2((val & 1) as u8)
343    }
344}
345
346impl From<Choice> for Gf2 {
347    fn from(value: Choice) -> Self {
348        Gf2(value.unwrap_u8())
349    }
350}
351
352impl From<&Choice> for Gf2 {
353    fn from(value: &Choice) -> Self {
354        (*value).into()
355    }
356}
357
358impl From<Gf2> for Choice {
359    fn from(value: Gf2) -> Self {
360        value.0.into()
361    }
362}
363
364impl From<&Gf2> for Choice {
365    fn from(value: &Gf2) -> Self {
366        value.0.into()
367    }
368}
369
370impl FromUniformBytes for Gf2 {
371    type UniformBytes = U1;
372
373    fn from_uniform_bytes(bytes: &Array<u8, Self::UniformBytes>) -> Self {
374        Gf2(bytes[0] & 1)
375    }
376}
primitives/algebra/field/binary/gf2.rs

primitives/algebra/field/binary/
gf2.rs
