primitives/algebra/field/binary/
gf2.rs

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

primitives/algebra/field/binary/
gf2.rs
