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

primitives/algebra/field/binary/
gf2.rs
