zinc_utils/
mul_by_scalar.rs

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

zinc_utils/
mul_by_scalar.rs
