decaf377/fields/fq/u32/
wrapper.rs

1use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
2
3use super::{
4    super::{B, N_32, N_64, N_8},
5    fiat,
6};
7
8const N: usize = N_32;
9
10#[derive(Copy, Clone)]
11pub struct Fq(fiat::FqMontgomeryDomainFieldElement);
12
13impl PartialEq for Fq {
14    fn eq(&self, other: &Self) -> bool {
15        match (self.is_sentinel(), other.is_sentinel()) {
16            (true, true) => true,
17            (true, false) => false,
18            (false, true) => false,
19            (false, false) => {
20                let sub = self.sub(other);
21                let mut check_word = 0;
22                fiat::fq_nonzero(&mut check_word, &sub.0 .0);
23                check_word == 0
24            }
25        }
26    }
27}
28
29impl Eq for Fq {}
30
31impl zeroize::Zeroize for Fq {
32    fn zeroize(&mut self) {
33        self.0 .0.zeroize()
34    }
35}
36
37impl Fq {
38    pub(crate) fn from_le_limbs(limbs: [u64; N_64]) -> Fq {
39        let limbs = {
40            let mut out = [0u32; N];
41            for i in 0..N_64 {
42                out[2 * i] = (limbs[i] & 0xFFFF_FFFF_FFFF_FFFF) as u32;
43                out[2 * i + 1] = (limbs[i] >> 32) as u32;
44            }
45            out
46        };
47        let x_non_monty = fiat::FqNonMontgomeryDomainFieldElement(limbs);
48        let mut x = fiat::FqMontgomeryDomainFieldElement([0; N]);
49        fiat::fq_to_montgomery(&mut x, &x_non_monty);
50        Self(x)
51    }
52
53    pub(crate) fn from_raw_bytes(bytes: &[u8; N_8]) -> Fq {
54        let mut x_non_montgomery = fiat::FqNonMontgomeryDomainFieldElement([0; N]);
55        let mut x = fiat::FqMontgomeryDomainFieldElement([0; N]);
56
57        fiat::fq_from_bytes(&mut x_non_montgomery.0, &bytes);
58        fiat::fq_to_montgomery(&mut x, &x_non_montgomery);
59
60        Self(x)
61    }
62
63    pub(crate) fn to_le_limbs(&self) -> [u64; N_64] {
64        debug_assert!(!self.is_sentinel());
65
66        let mut x_non_montgomery = fiat::FqNonMontgomeryDomainFieldElement([0; N]);
67        fiat::fq_from_montgomery(&mut x_non_montgomery, &self.0);
68        let limbs = x_non_montgomery.0;
69        let mut out = [0u64; N_64];
70        for i in 0..N_64 {
71            out[i] = (limbs[2 * i] as u64) | ((limbs[2 * i + 1] as u64) << 32);
72        }
73        out
74    }
75
76    pub fn to_bytes_le(&self) -> [u8; N_8] {
77        debug_assert!(!self.is_sentinel());
78
79        let mut bytes = [0u8; N_8];
80        let mut x_non_montgomery = fiat::FqNonMontgomeryDomainFieldElement([0; N]);
81        fiat::fq_from_montgomery(&mut x_non_montgomery, &self.0);
82        fiat::fq_to_bytes(&mut bytes, &x_non_montgomery.0);
83        bytes
84    }
85
86    const fn from_montgomery_limbs_backend(limbs: [u32; N]) -> Fq {
87        Self(fiat::FqMontgomeryDomainFieldElement(limbs))
88    }
89
90    /// Instantiate a constant field element from its montgomery limbs.
91    ///
92    /// This should only be used if you are familiar with the internals of the library.
93    pub const fn from_montgomery_limbs(limbs: [u64; N_64]) -> Fq {
94        Self(fiat::FqMontgomeryDomainFieldElement([
95            limbs[0] as u32,
96            (limbs[0] >> 32) as u32,
97            limbs[1] as u32,
98            (limbs[1] >> 32) as u32,
99            limbs[2] as u32,
100            (limbs[2] >> 32) as u32,
101            limbs[3] as u32,
102            (limbs[3] >> 32) as u32,
103        ]))
104    }
105
106    pub const ZERO: Self = Self(fiat::FqMontgomeryDomainFieldElement([0; N]));
107
108    pub const ONE: Self = Self(fiat::FqMontgomeryDomainFieldElement([
109        4294967283, 2099019775, 1879048178, 1918366991, 1361842158, 383260021, 733715101, 223074866,
110    ]));
111    ///
112    /// A sentinel value which exists only to not be equal to any other field element.
113    ///
114    /// Operations involving this element are undefined.
115    pub const SENTINEL: Self = Self::from_montgomery_limbs([u64::MAX; N_64]);
116
117    fn is_sentinel(&self) -> bool {
118        self.0 .0 == Self::SENTINEL.0 .0
119    }
120
121    pub fn square(&self) -> Fq {
122        debug_assert!(!self.is_sentinel());
123
124        let mut result = fiat::FqMontgomeryDomainFieldElement([0; N]);
125        fiat::fq_square(&mut result, &self.0);
126        Self(result)
127    }
128
129    pub fn inverse(&self) -> Option<Self> {
130        debug_assert!(!self.is_sentinel());
131
132        if self == &Self::ZERO {
133            return None;
134        }
135
136        const I: usize = (49 * B + 57) / 17;
137
138        let mut a = fiat::FqNonMontgomeryDomainFieldElement([0; N]);
139        fiat::fq_from_montgomery(&mut a, &self.0);
140        let mut d = 1;
141        let mut f: [u32; N + 1] = [0u32; N + 1];
142        fiat::fq_msat(&mut f);
143        let mut g: [u32; N + 1] = [0u32; N + 1];
144        let mut v: [u32; N] = [0u32; N];
145        let mut r: [u32; N] = Self::ONE.0 .0;
146        let mut i = 0;
147        let mut j = 0;
148
149        while j < N {
150            g[j] = a[j];
151            j += 1;
152        }
153
154        let mut out1: u32 = 0;
155        let mut out2: [u32; N + 1] = [0; N + 1];
156        let mut out3: [u32; N + 1] = [0; N + 1];
157        let mut out4: [u32; N] = [0; N];
158        let mut out5: [u32; N] = [0; N];
159        let mut out6: u32 = 0;
160        let mut out7: [u32; N + 1] = [0; N + 1];
161        let mut out8: [u32; N + 1] = [0; N + 1];
162        let mut out9: [u32; N] = [0; N];
163        let mut out10: [u32; N] = [0; N];
164
165        while i < I - I % 2 {
166            fiat::fq_divstep(
167                &mut out1, &mut out2, &mut out3, &mut out4, &mut out5, d, &f, &g, &v, &r,
168            );
169            fiat::fq_divstep(
170                &mut out6, &mut out7, &mut out8, &mut out9, &mut out10, out1, &out2, &out3, &out4,
171                &out5,
172            );
173            d = out6;
174            f = out7;
175            g = out8;
176            v = out9;
177            r = out10;
178            i += 2;
179        }
180
181        if I % 2 != 0 {
182            fiat::fq_divstep(
183                &mut out1, &mut out2, &mut out3, &mut out4, &mut out5, d, &f, &g, &v, &r,
184            );
185            v = out4;
186            f = out2;
187        }
188
189        let s = ((f[f.len() - 1] >> (32 - 1)) & 1) as u8;
190        let mut neg = fiat::FqMontgomeryDomainFieldElement([0; N]);
191        fiat::fq_opp(&mut neg, &fiat::FqMontgomeryDomainFieldElement(v));
192
193        let mut v_prime: [u32; N] = [0u32; N];
194        fiat::fq_selectznz(&mut v_prime, s, &v, &neg.0);
195
196        let mut pre_comp: [u32; N] = [0u32; N];
197        fiat::fq_divstep_precomp(&mut pre_comp);
198
199        let mut result = fiat::FqMontgomeryDomainFieldElement([0; N]);
200        fiat::fq_mul(
201            &mut result,
202            &fiat::FqMontgomeryDomainFieldElement(v_prime),
203            &fiat::FqMontgomeryDomainFieldElement(pre_comp),
204        );
205
206        Some(Fq(result))
207    }
208
209    pub fn add(self, other: &Fq) -> Fq {
210        debug_assert!(!self.is_sentinel() && !other.is_sentinel());
211
212        let mut result = fiat::FqMontgomeryDomainFieldElement([0; N]);
213        fiat::fq_add(&mut result, &self.0, &other.0);
214        Fq(result)
215    }
216
217    pub fn sub(self, other: &Fq) -> Fq {
218        debug_assert!(!self.is_sentinel() && !other.is_sentinel());
219
220        let mut result = fiat::FqMontgomeryDomainFieldElement([0; N]);
221        fiat::fq_sub(&mut result, &self.0, &other.0);
222        Fq(result)
223    }
224
225    pub fn mul(self, other: &Fq) -> Fq {
226        debug_assert!(!self.is_sentinel() && !other.is_sentinel());
227
228        let mut result = fiat::FqMontgomeryDomainFieldElement([0; N]);
229        fiat::fq_mul(&mut result, &self.0, &other.0);
230        Fq(result)
231    }
232
233    pub fn neg(self) -> Fq {
234        debug_assert!(!self.is_sentinel());
235
236        let mut result = fiat::FqMontgomeryDomainFieldElement([0; N]);
237        fiat::fq_opp(&mut result, &self.0);
238        Fq(result)
239    }
240}
241
242impl ConditionallySelectable for Fq {
243    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
244        let mut out = [0u32; 8];
245        for i in 0..8 {
246            out[i] = u32::conditional_select(&a.0 .0[i], &b.0 .0[i], choice);
247        }
248        Self(fiat::FqMontgomeryDomainFieldElement(out))
249    }
250}
251
252impl ConstantTimeEq for Fq {
253    fn ct_eq(&self, other: &Fq) -> Choice {
254        self.0 .0.ct_eq(&other.0 .0)
255    }
256}
decaf377/fields/fq/u32/wrapper.rs

decaf377/fields/fq/u32/
wrapper.rs
