crypto_bigint/modular/bingcd/
extension.rs

1use crate::{Choice, CtOption, Int, Limb, Uint};
2
3pub(crate) struct ExtendedUint<const LIMBS: usize, const EXTENSION_LIMBS: usize>(
4    Uint<LIMBS>,
5    Uint<EXTENSION_LIMBS>,
6);
7
8impl<const LIMBS: usize, const EXTRA: usize> ExtendedUint<LIMBS, EXTRA> {
9    /// Construct an [`ExtendedUint`] from the product of a [`Uint<LIMBS>`] and an [`Uint<EXTRA>`].
10    ///
11    /// Assumes the top bit of the product is not set.
12    #[inline]
13    pub const fn from_product(lhs: Uint<LIMBS>, rhs: Uint<EXTRA>) -> Self {
14        let (lo, hi) = lhs.widening_mul(&rhs);
15        ExtendedUint(lo, hi)
16    }
17
18    /// Wrapping multiply `self` with `rhs`
19    pub const fn wrapping_mul<const RHS_LIMBS: usize>(&self, rhs: &Uint<RHS_LIMBS>) -> Self {
20        let (lo, hi) = self.0.widening_mul(rhs);
21        let hi = self.1.wrapping_mul(rhs).wrapping_add(&hi.resize::<EXTRA>());
22        Self(lo, hi)
23    }
24
25    /// Interpret `self` as an [`ExtendedInt`]
26    #[inline]
27    pub const fn as_extended_int(&self) -> ExtendedInt<LIMBS, EXTRA> {
28        ExtendedInt(self.0, self.1)
29    }
30
31    /// Whether this form is `Self::ZERO`.
32    #[inline]
33    pub const fn is_zero(&self) -> Choice {
34        self.0.is_nonzero().not().and(self.1.is_nonzero().not())
35    }
36
37    /// Drop the extension.
38    #[inline]
39    pub const fn checked_drop_extension(&self) -> CtOption<Uint<LIMBS>> {
40        CtOption::new(self.0, self.1.is_nonzero().not())
41    }
42
43    /// Construction the binary negation of `self`, i.e., map `self` to `!self + 1`.
44    ///
45    /// Note: maps `0` to itself.
46    #[inline]
47    pub const fn wrapping_neg(&self) -> Self {
48        let (lhs, carry) = self.0.carrying_neg();
49        let mut rhs = self.1.not();
50        rhs = Uint::select(&rhs, &rhs.wrapping_add(&Uint::ONE), carry);
51        Self(lhs, rhs)
52    }
53
54    /// Negate `self` if `negate` is truthy. Otherwise returns `self`.
55    #[inline]
56    pub const fn wrapping_neg_if(&self, negate: Choice) -> Self {
57        let neg = self.wrapping_neg();
58        Self(
59            Uint::select(&self.0, &neg.0, negate),
60            Uint::select(&self.1, &neg.1, negate),
61        )
62    }
63
64    /// Shift `self` right by `shift` bits.
65    ///
66    /// # Panics
67    /// - if `shift ≥ UPPER_BOUND`.
68    #[inline]
69    #[allow(clippy::cast_possible_truncation)]
70    pub const fn bounded_shr<const UPPER_BOUND: u32>(&self, shift: u32) -> Self {
71        assert!(shift < UPPER_BOUND && UPPER_BOUND <= Uint::<EXTRA>::BITS);
72
73        let hi = self.1.bounded_shr(shift, UPPER_BOUND);
74        let carry = self.1.unbounded_shl(Uint::<EXTRA>::BITS - shift);
75        let mut lo = self.0.bounded_shr(shift, UPPER_BOUND);
76
77        // Apply carry
78        let limb_diff = LIMBS.saturating_sub(EXTRA) as u32;
79        // safe to vartime; shr_vartime is variable in the value of shift only. Since this shift
80        // is a public constant, the constant time property of this algorithm is not impacted.
81        let carry = carry
82            .resize::<LIMBS>()
83            .unbounded_shl_by_limbs_vartime(limb_diff);
84        lo = lo.bitxor(&carry);
85
86        Self(lo, hi)
87    }
88
89    /// Shift `self` right by `shift` bits.
90    ///
91    /// # Panics
92    /// - if `shift ≥ Uint::<EXTRA>::BITS`.
93    #[inline]
94    #[allow(clippy::cast_possible_truncation)]
95    pub const fn shr_vartime(&self, shift: u32) -> Self {
96        debug_assert!(shift <= Uint::<EXTRA>::BITS);
97
98        let hi = self.1.shr_vartime(shift);
99        let carry = self.1.unbounded_shl_vartime(Uint::<EXTRA>::BITS - shift);
100        let mut lo = self.0.shr_vartime(shift);
101
102        // Apply carry
103        let limb_diff = LIMBS.saturating_sub(EXTRA) as u32;
104        // safe to vartime; shr_vartime is variable in the value of shift only. Since this shift
105        // is a public constant, the constant time property of this algorithm is not impacted.
106        let carry = carry
107            .resize::<LIMBS>()
108            .unbounded_shl_by_limbs_vartime(limb_diff);
109        lo = lo.bitxor(&carry);
110
111        Self(lo, hi)
112    }
113}
114
115#[derive(Debug, PartialEq, Clone, Copy)]
116pub(crate) struct ExtendedInt<const LIMBS: usize, const EXTENSION_LIMBS: usize>(
117    Uint<LIMBS>,
118    Uint<EXTENSION_LIMBS>,
119);
120
121impl<const LIMBS: usize, const EXTRA: usize> ExtendedInt<LIMBS, EXTRA> {
122    pub(super) const ZERO: Self = Self(Uint::ZERO, Uint::ZERO);
123    pub(super) const ONE: Self = Self(Uint::ONE, Uint::ZERO);
124
125    /// Construct an [`ExtendedInt`] from the product of a [`Uint<LIMBS>`] and a [`Uint<EXTRA>`].
126    ///
127    /// Assumes the top bit of the product is not set.
128    #[inline]
129    pub const fn from_product(lhs: Uint<LIMBS>, rhs: Uint<EXTRA>) -> Self {
130        ExtendedUint::from_product(lhs, rhs).as_extended_int()
131    }
132
133    /// Wrapping multiply `self` with `rhs`, which is passed as a
134    pub(crate) const fn wrapping_mul<const RHS_LIMBS: usize>(
135        &self,
136        rhs: (&Uint<RHS_LIMBS>, &Choice),
137    ) -> Self {
138        let (abs_self, self_is_negative) = self.abs_sign();
139        let (abs_rhs, rhs_is_negative) = rhs;
140        let mut abs_val = abs_self.wrapping_mul(abs_rhs);
141
142        // Make sure the top bit of `abs_val` is not set
143        abs_val.1 = abs_val.1.bitand(Int::<EXTRA>::SIGN_MASK.not().as_uint());
144
145        let val_is_negative = self_is_negative.xor(*rhs_is_negative);
146        abs_val.wrapping_neg_if(val_is_negative).as_extended_int()
147    }
148
149    /// Interpret this as an [`ExtendedUint`].
150    #[inline]
151    pub const fn as_extended_uint(&self) -> ExtendedUint<LIMBS, EXTRA> {
152        ExtendedUint(self.0, self.1)
153    }
154
155    /// Return the negation of `self` if `negate` is truthy. Otherwise, return `self`.
156    #[inline]
157    pub const fn wrapping_neg_if(&self, negate: Choice) -> Self {
158        self.as_extended_uint()
159            .wrapping_neg_if(negate)
160            .as_extended_int()
161    }
162
163    #[inline]
164    pub(crate) const fn wrapping_add(&self, rhs: &Self) -> Self {
165        let (lo, carry) = self.0.carrying_add(&rhs.0, Limb::ZERO);
166        let (hi, _) = self.1.carrying_add(&rhs.1, carry);
167        Self(lo, hi)
168    }
169
170    /// Compute `self - rhs`, wrapping any underflow.
171    #[inline]
172    pub const fn wrapping_sub(&self, rhs: &Self) -> Self {
173        let (lo, borrow) = self.0.borrowing_sub(&rhs.0, Limb::ZERO);
174        let (hi, _) = self.1.borrowing_sub(&rhs.1, borrow);
175        Self(lo, hi)
176    }
177
178    /// Returns the absolute value and sign of `self`, without the extension.
179    #[inline]
180    pub const fn dropped_abs_sign(&self) -> (Uint<LIMBS>, Choice) {
181        let (abs, sgn) = self.abs_sign();
182        (abs.0, sgn)
183    }
184
185    /// Decompose `self` into is absolute value and signum.
186    #[inline]
187    pub const fn abs_sign(&self) -> (ExtendedUint<LIMBS, EXTRA>, Choice) {
188        let is_negative = self.1.as_int().is_negative();
189        (
190            self.wrapping_neg_if(is_negative).as_extended_uint(),
191            is_negative,
192        )
193    }
194
195    /// Divide self by `2^k`, rounding towards zero.
196    ///
197    /// # Panics
198    /// - if `k ≥ UPPER_BOUND`.
199    #[inline]
200    pub const fn bounded_div_2k<const UPPER_BOUND: u32>(&self, k: u32) -> Self {
201        let (abs, sgn) = self.abs_sign();
202        abs.bounded_shr::<UPPER_BOUND>(k)
203            .wrapping_neg_if(sgn)
204            .as_extended_int()
205    }
206
207    /// Divide self by `2^k`, rounding towards zero.
208    #[inline]
209    pub const fn div_2k_vartime(&self, k: u32) -> Self {
210        let (abs, sgn) = self.abs_sign();
211        abs.shr_vartime(k).wrapping_neg_if(sgn).as_extended_int()
212    }
213}
214
215#[cfg(test)]
216mod tests {
217    use super::ExtendedUint;
218    use crate::{U64, Uint};
219
220    impl<const LIMBS: usize, const EXTRA: usize> ExtendedUint<LIMBS, EXTRA> {
221        /// Decompose `self` into the bottom and top limbs.
222        #[inline]
223        const fn as_elements(&self) -> (Uint<LIMBS>, Uint<EXTRA>) {
224            (self.0, self.1)
225        }
226    }
227
228    const A: ExtendedUint<{ U64::LIMBS }, { U64::LIMBS }> = ExtendedUint::from_product(
229        U64::from_u64(68146184546341u64),
230        U64::from_u64(873817114763u64),
231    );
232    const B: ExtendedUint<{ U64::LIMBS }, { U64::LIMBS }> = ExtendedUint::from_product(
233        U64::from_u64(7772181434148543u64),
234        U64::from_u64(6665138352u64),
235    );
236
237    #[test]
238    fn bounded_shr() {
239        let a = ExtendedUint::<4, 2>(Uint::ZERO, Uint::MAX);
240        let actual = a.bounded_shr::<32>(20);
241        assert_eq!(
242            actual.as_elements(),
243            (Uint::MAX.shl(Uint::<4>::BITS - 20), Uint::MAX.shr(20)),
244        );
245    }
246
247    #[test]
248    fn test_from_product() {
249        assert_eq!(
250            A.as_elements(),
251            (U64::from(13454091406951429143u64), U64::from(3228065u64))
252        );
253        assert_eq!(
254            B.as_elements(),
255            (U64::from(1338820589698724688u64), U64::from(2808228u64))
256        );
257    }
258
259    #[test]
260    fn test_wrapping_sub() {
261        assert_eq!(
262            A.as_extended_int()
263                .wrapping_sub(&B.as_extended_int())
264                .as_extended_uint()
265                .as_elements(),
266            (U64::from(12115270817252704455u64), U64::from(419837u64))
267        );
268    }
269}
crypto_bigint/modular/bingcd/extension.rs

crypto_bigint/modular/bingcd/
extension.rs
