crypto_bigint/modular/bingcd/
compact.rs

1/// Constructing a compact representation of a [`Uint`]
2use crate::{Limb, Uint};
3
4impl<const LIMBS: usize> Uint<LIMBS> {
5    /// Construct a [Uint] containing the bits in `self` in the range `[idx, idx + length)`.
6    ///
7    /// Assumes `length ≤ Uint::<SECTION_LIMBS>::BITS` and `idx + length ≤ Self::BITS`.
8    ///
9    /// Executes in time variable in `length` only.
10    #[inline(always)]
11    #[allow(clippy::cast_possible_truncation)]
12    pub(super) const fn section_vartime_length<const SECTION_LIMBS: usize>(
13        &self,
14        idx: u32,
15        length: u32,
16    ) -> Uint<SECTION_LIMBS> {
17        debug_assert!(length <= Uint::<SECTION_LIMBS>::BITS);
18        debug_assert!(idx + length <= Self::BITS);
19
20        if LIMBS > SECTION_LIMBS {
21            let (shr_limbs, shr_bits) = (idx >> Limb::LOG2_BITS, idx & (Limb::BITS - 1));
22            // shift into the lower SECTION_LIMBS+1 limbs
23            let buf = self.bounded_shr_by_limbs(shr_limbs, LIMBS as u32);
24            // shift the lower SECTION_LIMBS limbs by the remaining bits and carry the high bits
25            buf.resize::<SECTION_LIMBS>()
26                .shr_limb_with_carry(
27                    shr_bits,
28                    buf.limbs[SECTION_LIMBS].unbounded_shl(Limb::BITS - shr_bits),
29                )
30                .0
31                .restrict_bits(length)
32        } else {
33            self.shr(idx)
34                .resize::<SECTION_LIMBS>()
35                .restrict_bits(length)
36        }
37    }
38
39    /// Construct a [Uint] containing the bits in `self` in the range `[idx, idx + length)`.
40    ///
41    /// Assumes `length ≤ Uint::<SECTION_LIMBS>::BITS` and `idx + length ≤ Self::BITS`.
42    ///
43    /// Executes in time variable in `idx` and `length`.
44    #[inline(always)]
45    pub(super) const fn section_vartime<const SECTION_LIMBS: usize>(
46        &self,
47        idx: u32,
48        length: u32,
49    ) -> Uint<SECTION_LIMBS> {
50        debug_assert!(length <= Uint::<SECTION_LIMBS>::BITS);
51        debug_assert!(idx + length <= Self::BITS);
52
53        self.shr_vartime(idx)
54            .resize::<SECTION_LIMBS>()
55            .restrict_bits(length)
56    }
57
58    /// Compact `self` to a form containing the concatenation of its bit ranges `[0, K)`
59    /// and `[n-K, n)`.
60    ///
61    /// Assumes `K ≤ Uint::<SUMMARY_LIMBS>::BITS`, `n ≤ Self::BITS` and `n ≥ 2K`.
62    #[inline(always)]
63    pub(super) const fn compact<const K: u32, const SUMMARY_LIMBS: usize>(
64        &self,
65        n: u32,
66    ) -> Uint<SUMMARY_LIMBS> {
67        debug_assert!(K <= Uint::<SUMMARY_LIMBS>::BITS);
68        debug_assert!(n <= Self::BITS);
69        debug_assert!(n >= 2 * K);
70
71        // safe to vartime; this function is vartime in length only, which is a public constant
72        let hi = self.section_vartime_length(n - K, K);
73        // safe to vartime; this function is vartime in idx and length only, which are both public
74        // constants
75        let lo = self.section_vartime(0, K);
76        // safe to vartime; shl_vartime is variable in the value of shift only. Since this shift
77        // is a public constant, the constant time property of this algorithm is not impacted.
78        hi.shl_vartime(K).bitxor(&lo)
79    }
80
81    /// Vartime equivalent of [`Self::compact`].
82    #[inline(always)]
83    pub(crate) const fn compact_vartime<const K: u32, const SUMMARY_LIMBS: usize>(
84        &self,
85        n: u32,
86    ) -> Uint<SUMMARY_LIMBS> {
87        debug_assert!(K <= Uint::<SUMMARY_LIMBS>::BITS);
88        debug_assert!(n <= Self::BITS);
89        debug_assert!(n >= 2 * K);
90
91        // safe to vartime; this function is vartime in length only, which is a public constant
92        let hi = self.section_vartime(n - K, K);
93        // safe to vartime; this function is vartime in idx and length only, which are both public
94        // constants
95        let lo = self.section_vartime(0, K);
96        // safe to vartime; shl_vartime is variable in the value of shift only. Since this shift
97        // is a public constant, the constant time property of this algorithm is not impacted.
98        hi.shl_vartime(K).bitxor(&lo)
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use crate::{U128, U256};
105
106    #[test]
107    fn test_compact() {
108        let val =
109            U256::from_be_hex("CFCF1535CEBE19BBF289933AB8645189397450A32BFEC57579FB7EB14E27D101");
110        let target = U128::from_be_hex("BBF289933AB8645179FB7EB14E27D101");
111
112        let compact = val.compact::<64, { U128::LIMBS }>(200);
113        assert_eq!(compact, target);
114    }
115
116    #[test]
117    fn test_compact_vartime() {
118        let val =
119            U256::from_be_hex("1971BC6285D8CBA9640AA3B3B9C01EF4186D1EBE9A17393A9E43586E0EBAED5B");
120        let target = U128::from_be_hex("A9640AA3B3B9C01E9E43586E0EBAED5B");
121
122        let compact = val.compact_vartime::<64, { U128::LIMBS }>(200);
123        assert_eq!(compact, target);
124    }
125}
crypto_bigint/modular/bingcd/compact.rs

crypto_bigint/modular/bingcd/
compact.rs
