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) -> Array<Self::Subfield, Self::Degree> {
159        Array([*self])
160    }
161
162    fn from_subfield_elements(elems: Array<Self::Subfield, Self::Degree>) -> Self {
163        elems[0]
164    }
165
166    fn to_le_bytes(&self) -> Array<u8, Self::FieldBytesSize> {
167        [self.0].into()
168    }
169
170    fn from_le_bytes(bytes: &[u8]) -> Option<Self> {
171        bytes
172            .first()
173            .and_then(|&byte| if byte <= 1 { Some(Self(byte)) } else { None })
174    }
175
176    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self {
177        self * other
178    }
179
180    fn generator() -> Self {
181        Self::ONE
182    }
183}
184
185impl Random for Gf2 {
186    fn random(mut rng: impl CryptoRngCore) -> Gf2 {
187        let mut tmp = [0u8; 1];
188        rng.fill_bytes(&mut tmp);
189        Gf2(tmp[0] & 1)
190    }
191}
192
193// === Field traits implementations === //
194
195impl ConditionallySelectable for Gf2 {
196    #[inline]
197    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
198        Gf2(u8::conditional_select(&a.0, &b.0, choice))
199    }
200}
201
202impl ConstantTimeEq for Gf2 {
203    #[inline]
204    fn ct_eq(&self, other: &Self) -> Choice {
205        self.0.ct_eq(&other.0)
206    }
207}
208
209#[macros::op_variants(borrowed)]
210impl Neg for Gf2 {
211    type Output = Gf2;
212
213    #[inline]
214    fn neg(self) -> Self::Output {
215        self
216    }
217}
218
219#[macros::op_variants(owned, borrowed, flipped_commutative)]
220impl Add<&Gf2> for Gf2 {
221    type Output = Gf2;
222
223    #[inline]
224    #[allow(clippy::suspicious_arithmetic_impl)]
225    fn add(self, rhs: &Gf2) -> Self::Output {
226        Gf2(self.0 ^ rhs.0)
227    }
228}
229
230#[macros::op_variants(owned)]
231impl AddAssign<&Gf2> for Gf2 {
232    #[inline]
233    fn add_assign(&mut self, rhs: &Gf2) {
234        *self = *self + rhs;
235    }
236}
237
238#[macros::op_variants(owned, borrowed, flipped_commutative)]
239impl Sub<&Gf2> for Gf2 {
240    type Output = Gf2;
241
242    #[inline]
243    #[allow(clippy::suspicious_arithmetic_impl)]
244    fn sub(self, rhs: &Gf2) -> Self::Output {
245        self + rhs
246    }
247}
248
249#[macros::op_variants(owned)]
250impl SubAssign<&Gf2> for Gf2 {
251    #[inline]
252    fn sub_assign(&mut self, rhs: &Gf2) {
253        *self = *self - rhs;
254    }
255}
256
257#[macros::op_variants(owned, borrowed, flipped_commutative)]
258impl Mul<&Gf2> for Gf2 {
259    type Output = Gf2;
260
261    #[inline]
262    #[allow(clippy::suspicious_arithmetic_impl)]
263    fn mul(self, rhs: &Gf2) -> Self::Output {
264        Gf2(self.0 & rhs.0)
265    }
266}
267#[macros::op_variants(owned)]
268impl<'a> MulAssign<&'a Gf2> for Gf2 {
269    #[inline]
270    fn mul_assign(&mut self, rhs: &'a Gf2) {
271        *self = *self * rhs;
272    }
273}
274
275impl Sum for Gf2 {
276    #[inline]
277    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
278        iter.fold(Gf2::ZERO, |a, b| a + b)
279    }
280}
281
282impl<'a> Sum<&'a Gf2> for Gf2 {
283    #[inline]
284    fn sum<I: Iterator<Item = &'a Gf2>>(iter: I) -> Self {
285        iter.fold(Gf2::ZERO, |a, b| a + b)
286    }
287}
288
289impl Product for Gf2 {
290    #[inline]
291    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
292        iter.fold(Gf2::ONE, |a, b| a * b)
293    }
294}
295
296impl<'a> Product<&'a Gf2> for Gf2 {
297    #[inline]
298    fn product<I: Iterator<Item = &'a Gf2>>(iter: I) -> Self {
299        iter.fold(Gf2::ONE, |a, b| a * b)
300    }
301}
302
303impl From<Gf2> for bool {
304    fn from(value: Gf2) -> Self {
305        value.0 == 1
306    }
307}
308
309impl From<&Gf2> for bool {
310    fn from(value: &Gf2) -> Self {
311        value.0 == 1
312    }
313}
314
315impl From<bool> for Gf2 {
316    fn from(value: bool) -> Self {
317        Gf2(value.into())
318    }
319}
320
321impl From<&bool> for Gf2 {
322    fn from(value: &bool) -> Self {
323        (*value).into()
324    }
325}
326
327impl From<u8> for Gf2 {
328    fn from(val: u8) -> Self {
329        Gf2(val & 1)
330    }
331}
332
333impl From<Gf2> for u8 {
334    fn from(value: Gf2) -> Self {
335        value.0
336    }
337}
338
339impl From<&Gf2> for u64 {
340    fn from(value: &Gf2) -> Self {
341        value.0 as u64
342    }
343}
344
345impl From<u64> for Gf2 {
346    fn from(val: u64) -> Self {
347        Gf2((val & 1) as u8)
348    }
349}
350
351impl From<u128> for Gf2 {
352    fn from(val: u128) -> Self {
353        Gf2((val & 1) as u8)
354    }
355}
356
357impl From<Choice> for Gf2 {
358    fn from(value: Choice) -> Self {
359        Gf2(value.unwrap_u8())
360    }
361}
362
363impl From<&Choice> for Gf2 {
364    fn from(value: &Choice) -> Self {
365        (*value).into()
366    }
367}
368
369impl From<Gf2> for Choice {
370    fn from(value: Gf2) -> Self {
371        value.0.into()
372    }
373}
374
375impl From<&Gf2> for Choice {
376    fn from(value: &Gf2) -> Self {
377        value.0.into()
378    }
379}
380
381impl FromUniformBytes for Gf2 {
382    type UniformBytes = U1;
383
384    fn from_uniform_bytes(bytes: &Array<u8, Self::UniformBytes>) -> Self {
385        Gf2(bytes[0] & 1)
386    }
387}
388
389impl AsRef<[u8]> for Gf2 {
390    fn as_ref(&self) -> &[u8] {
391        unsafe {
392            std::slice::from_raw_parts(self as *const Gf2 as *const u8, std::mem::size_of::<Gf2>())
393        }
394    }
395}
primitives/algebra/field/binary/gf2.rs

primitives/algebra/field/binary/
gf2.rs
