zinc_utils/
mul_by_scalar.rs

1use crate::from_ref::FromRef;
2use crypto_primitives::{boolean::Boolean, crypto_bigint_int::Int};
3use num_traits::{CheckedMul, ConstZero};
4
5pub trait MulByScalar<Rhs, Out = Self>: Sized {
6    /// Multiplies the current element by a scalar from the right (usually - a
7    /// coefficient to obtain a linear combination).
8    /// Returns `None` if the multiplication would overflow.
9    fn mul_by_scalar<const CHECK: bool>(&self, rhs: Rhs) -> Option<Out>;
10}
11
12macro_rules! impl_mul_by_scalar_for_primitives {
13    ($($t:ty),*) => {
14        $(
15            impl MulByScalar<&$t> for $t {
16                #[allow(clippy::arithmetic_side_effects)] // By design
17                fn mul_by_scalar<const CHECK: bool>(&self, rhs: &$t) -> Option<Self> {
18                    if CHECK {
19                        self.checked_mul(rhs)
20                    } else {
21                        Some(self * rhs)
22                    }
23                }
24            }
25        )*
26    };
27}
28
29impl_mul_by_scalar_for_primitives!(i8, i16, i32, i64, i128);
30
31impl<const LIMBS: usize, const LIMBS2: usize> MulByScalar<&Int<LIMBS2>> for Int<LIMBS> {
32    #[allow(clippy::arithmetic_side_effects)] // By design
33    fn mul_by_scalar<const CHECK: bool>(&self, rhs: &Int<LIMBS2>) -> Option<Self> {
34        if LIMBS < LIMBS2 {
35            return None; // Cannot multiply if the left operand has fewer limbs than the right
36        }
37        if CHECK {
38            self.checked_mul(&rhs.resize())
39        } else {
40            // Make use of an optimized wrapping_mul in the crypto-bigint library.
41            Some(widening_wrapping_mul(self, rhs))
42        }
43    }
44}
45
46macro_rules! impl_mul_int_by_primitive_scalar {
47    ($(($t:ty, $rhs_limbs:expr)),*) => {
48        $(
49            impl<const LIMBS: usize, const LIMBS2: usize> MulByScalar<&$t, Int<LIMBS2>> for Int<LIMBS> {
50                #[allow(clippy::arithmetic_side_effects)] // By design
51                fn mul_by_scalar<const CHECK: bool>(&self, rhs: &$t) -> Option<Int<LIMBS2>> {
52                    const {
53                        assert!(LIMBS <= LIMBS2, "Cannot multiply if the left operand has more limbs than the output");
54                    }
55                    if CHECK {
56                        let rhs: Int<LIMBS2> = Int::from_ref(rhs);
57                        rhs.checked_mul(&self.resize())
58                    } else {
59                        let rhs_short: Int<{ $rhs_limbs }> = Int::from(*rhs);
60                        Some(widening_wrapping_mul(&self.resize::<LIMBS2>(), &rhs_short))
61                    }
62                }
63            }
64        )*
65    };
66}
67
68impl_mul_int_by_primitive_scalar!(
69    (i8, crypto_bigint::U64::LIMBS),
70    (i16, crypto_bigint::U64::LIMBS),
71    (i32, crypto_bigint::U64::LIMBS),
72    (i64, crypto_bigint::U64::LIMBS),
73    (i128, crypto_bigint::U128::LIMBS)
74);
75
76impl<T> MulByScalar<&Boolean> for T
77where
78    T: Clone + ConstZero + From<Boolean>,
79{
80    fn mul_by_scalar<const CHECK: bool>(&self, rhs: &Boolean) -> Option<Self> {
81        Some(if rhs.into_inner() {
82            self.clone()
83        } else {
84            ConstZero::ZERO
85        })
86    }
87}
88
89impl MulByScalar<&i64, i128> for i32 {
90    #[inline(always)]
91    #[allow(clippy::arithmetic_side_effects)] // Not possible to overflow since we are widening the result to i128
92    fn mul_by_scalar<const CHECK: bool>(&self, rhs: &i64) -> Option<i128> {
93        Some(i128::from(*self) * i128::from(*rhs))
94    }
95}
96
97impl MulByScalar<&i64> for i128 {
98    #[inline(always)]
99    #[allow(clippy::arithmetic_side_effects)] // By design
100    fn mul_by_scalar<const CHECK: bool>(&self, rhs: &i64) -> Option<i128> {
101        let rhs = i128::from(*rhs);
102        if CHECK {
103            self.checked_mul(&rhs)
104        } else {
105            Some(self * rhs)
106        }
107    }
108}
109
110impl MulByScalar<&i64, i128> for i64 {
111    #[inline(always)]
112    #[allow(clippy::arithmetic_side_effects)] // Not possible to overflow since we are widening the result to i128
113    fn mul_by_scalar<const CHECK: bool>(&self, rhs: &i64) -> Option<i128> {
114        Some(i128::from(*self) * i128::from(*rhs))
115    }
116}
117
118/// Helper function, make use of the crypto-bigint inner workings in order to
119/// multiply two ints of different number of limbs in `O(LIMBS_1 * LIMBS_2)`
120/// rather than in `O(MAX_LIMBS^2)` time.
121fn widening_wrapping_mul<const LIMBS: usize, const LIMBS2: usize>(
122    lhs: &Int<LIMBS>,
123    rhs: &Int<LIMBS2>,
124) -> Int<LIMBS> {
125    Int::new(lhs.inner().wrapping_mul(rhs.inner()))
126}
zinc_utils/mul_by_scalar.rs

zinc_utils/
mul_by_scalar.rs
