/rust/registry/src/index.crates.io-1949cf8c6b5b557f/crypto-bigint-0.7.10/src/int/mul.rs

Source
//! [`Int`] multiplication operations.

use crate::{
    Checked, CheckedMul, Choice, Concat, CtOption, Int, Mul, MulAssign, Uint, WrappingMul,
};

impl<const LIMBS: usize> Int<LIMBS> {
    /// Compute "wide" multiplication as a 3-tuple `(lo, hi, negate)`.
    /// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
    /// corresponding to the sizes of the operands; `negate` indicates whether the result should be
    /// negated when converted from [`Uint`] to [`Int`].
    ///
    /// Note: even if `negate` is truthy, the magnitude might be zero!
    #[deprecated(since = "0.7.0", note = "please use `widening_mul` instead")]
    #[must_use]
    pub const fn split_mul<const RHS_LIMBS: usize>(
        &self,
        rhs: &Int<RHS_LIMBS>,
    ) -> (Uint<{ LIMBS }>, Uint<{ RHS_LIMBS }>, Choice) {
        self.widening_mul(rhs)
    }

    /// Compute "wide" multiplication as a 3-tuple `(lo, hi, negate)`.
    /// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
    /// corresponding to the sizes of the operands; `negate` indicates whether the result should be
    /// negated when converted from [`Uint`] to [`Int`].
    ///
    /// Note: even if `negate` is truthy, the magnitude might be zero!
    #[inline]
    #[must_use]
    pub const fn widening_mul<const RHS_LIMBS: usize>(
        &self,
        rhs: &Int<RHS_LIMBS>,
    ) -> (Uint<{ LIMBS }>, Uint<{ RHS_LIMBS }>, Choice) {
        // Step 1: split operands into their signs and magnitudes.
        let (lhs_abs, lhs_sgn) = self.abs_sign();
        let (rhs_abs, rhs_sgn) = rhs.abs_sign();

        // Step 2: multiply the magnitudes
        let (lo, hi) = lhs_abs.widening_mul(&rhs_abs);

        // Step 3. Determine if the result should be negated.
        // This should be done if and only if lhs and rhs have opposing signs.
        // Note: if either operand is zero, the resulting magnitude will also be zero. Negating
        // zero, however, still yields zero, so having a truthy `negate` in that scenario is OK.
        let negate = lhs_sgn.xor(rhs_sgn);

        (lo, hi, negate)
    }

    /// Multiply `self` by `rhs`, returning a concatenated "wide" result.
    #[inline]
    #[must_use]
    pub const fn concatenating_mul<const RHS_LIMBS: usize, const WIDE_LIMBS: usize>(
        &self,
        rhs: &Int<RHS_LIMBS>,
    ) -> Int<WIDE_LIMBS>
    where
        Uint<LIMBS>: Concat<RHS_LIMBS, Output = Uint<WIDE_LIMBS>>,
    {
        let (lhs_abs, lhs_sign) = self.abs_sign();
        let (rhs_abs, rhs_sign) = rhs.abs_sign();
        let product_abs = lhs_abs.concatenating_mul(&rhs_abs);
        let product_sign = lhs_sign.xor(rhs_sign);

        // always fits
        Int::from_bits(product_abs.wrapping_neg_if(product_sign))
    }

    /// Multiply `self` by `rhs`, returning a `CtOption` which is `is_some` only if
    /// overflow did not occur.
    #[must_use]
    pub const fn checked_mul<const RHS_LIMBS: usize>(
        &self,
        rhs: &Int<RHS_LIMBS>,
    ) -> CtOption<Self> {
        let (abs_lhs, lhs_sgn) = self.abs_sign();
        let (abs_rhs, rhs_sgn) = rhs.abs_sign();
        let maybe_res = abs_lhs.checked_mul(&abs_rhs);
        Self::new_from_abs_opt_sign(maybe_res, lhs_sgn.xor(rhs_sgn))
    }

    /// Multiply `self` by `rhs`, saturating at the numeric bounds instead of overflowing.
    #[must_use]
    pub const fn saturating_mul<const RHS_LIMBS: usize>(&self, rhs: &Int<RHS_LIMBS>) -> Self {
        let (abs_lhs, lhs_sgn) = self.abs_sign();
        let (abs_rhs, rhs_sgn) = rhs.abs_sign();
        let maybe_res = abs_lhs.checked_mul(&abs_rhs);
        let is_neg = lhs_sgn.xor(rhs_sgn);
        let bound = Self::select(&Self::MAX, &Self::MIN, is_neg);
        ctutils::unwrap_or!(
            Self::new_from_abs_opt_sign(maybe_res, is_neg),
            bound,
            Self::select
        )
    }

    /// Multiply `self` by `rhs`, wrapping the result in case of overflow.
    /// This is equivalent to `(self * rhs) % (Uint::<LIMBS>::MAX + 1)`.
    #[inline]
    #[must_use]
    pub const fn wrapping_mul<const RHS_LIMBS: usize>(&self, rhs: &Int<RHS_LIMBS>) -> Self {
        if RHS_LIMBS >= LIMBS {
            Self(self.0.wrapping_mul(&rhs.0))
        } else {
            let (abs_rhs, rhs_sgn) = rhs.abs_sign();
            Self(self.0.wrapping_mul(&abs_rhs).wrapping_neg_if(rhs_sgn))
        }
    }
}

/// Squaring operations.
impl<const LIMBS: usize> Int<LIMBS> {
    /// Square self, returning a concatenated "wide" result.
    #[must_use]
    pub fn concatenating_square<const WIDE_LIMBS: usize>(&self) -> Uint<WIDE_LIMBS>
    where
        Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
    {
        self.abs().concatenating_square()
    }

    /// Square self, checking that the result fits in the original [`Uint`] size.
    #[must_use]
    pub fn checked_square(&self) -> CtOption<Uint<LIMBS>> {
        self.abs().checked_square()
    }

    /// Perform wrapping square, discarding overflow.
    #[must_use]
    pub const fn wrapping_square(&self) -> Uint<LIMBS> {
        self.abs().wrapping_square()
    }

    /// Perform saturating squaring, returning `MAX` on overflow.
    #[must_use]
    pub const fn saturating_square(&self) -> Uint<LIMBS> {
        self.abs().saturating_square()
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedMul<Int<RHS_LIMBS>> for Int<LIMBS> {
    #[inline]
    fn checked_mul(&self, rhs: &Int<RHS_LIMBS>) -> CtOption<Self> {
        self.checked_mul(rhs)
    }
}

impl<const LIMBS: usize> WrappingMul for Int<LIMBS> {
    fn wrapping_mul(&self, v: &Self) -> Self {
        self.wrapping_mul(v)
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Int<RHS_LIMBS>> for Int<LIMBS> {
    type Output = Int<LIMBS>;

    fn mul(self, rhs: Int<RHS_LIMBS>) -> Self {
        self.mul(&rhs)
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Int<RHS_LIMBS>> for Int<LIMBS> {
    type Output = Int<LIMBS>;

    fn mul(self, rhs: &Int<RHS_LIMBS>) -> Self {
        (&self).mul(rhs)
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Int<RHS_LIMBS>> for &Int<LIMBS> {
    type Output = Int<LIMBS>;

    fn mul(self, rhs: Int<RHS_LIMBS>) -> Self::Output {
        self.mul(&rhs)
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Int<RHS_LIMBS>> for &Int<LIMBS> {
    type Output = Int<LIMBS>;

    fn mul(self, rhs: &Int<RHS_LIMBS>) -> Self::Output {
        self.checked_mul(rhs)
            .expect("attempted to multiply with overflow")
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> MulAssign<Int<RHS_LIMBS>> for Int<LIMBS> {
    fn mul_assign(&mut self, rhs: Int<RHS_LIMBS>) {
        *self = self.mul(&rhs);
    }
}

impl<const LIMBS: usize, const RHS_LIMBS: usize> MulAssign<&Int<RHS_LIMBS>> for Int<LIMBS> {
    fn mul_assign(&mut self, rhs: &Int<RHS_LIMBS>) {
        *self = self.mul(rhs);
    }
}

impl<const LIMBS: usize> MulAssign<Checked<Int<LIMBS>>> for Checked<Int<LIMBS>> {
    fn mul_assign(&mut self, other: Checked<Int<LIMBS>>) {
        *self = *self * other;
    }
}

impl<const LIMBS: usize> MulAssign<&Checked<Int<LIMBS>>> for Checked<Int<LIMBS>> {
    fn mul_assign(&mut self, other: &Checked<Int<LIMBS>>) {
        *self = *self * other;
    }
}

#[cfg(test)]
#[allow(clippy::cast_possible_wrap)]
mod tests {
    use crate::{I64, I128, I256, Int, U64, U128, U256};

    #[test]
    #[allow(clippy::init_numbered_fields)]
    fn test_checked_mul() {
        let min_plus_one = Int {
            0: I128::MIN.0.wrapping_add(&I128::ONE.0),
        };

        // lhs = min

        let result = I128::MIN.checked_mul(&I128::MIN);
        assert!(bool::from(result.is_none()));

        let result = I128::MIN.checked_mul(&I128::MINUS_ONE);
        assert!(bool::from(result.is_none()));

        let result = I128::MIN.checked_mul(&I128::ZERO);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::MIN.checked_mul(&I128::ONE);
        assert_eq!(result.unwrap(), I128::MIN);

        let result = I128::MIN.checked_mul(&I128::MAX);
        assert!(bool::from(result.is_none()));

        // lhs = -1

        let result = I128::MINUS_ONE.checked_mul(&I128::MIN);
        assert!(bool::from(result.is_none()));

        let result = I128::MINUS_ONE.checked_mul(&I128::MINUS_ONE);
        assert_eq!(result.unwrap(), I128::ONE);

        let result = I128::MINUS_ONE.checked_mul(&I128::ZERO);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::MINUS_ONE.checked_mul(&I128::ONE);
        assert_eq!(result.unwrap(), I128::MINUS_ONE);

        let result = I128::MINUS_ONE.checked_mul(&I128::MAX);
        assert_eq!(result.unwrap(), min_plus_one);

        // lhs = 0

        let result = I128::ZERO.checked_mul(&I128::MIN);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::ZERO.checked_mul(&I128::MINUS_ONE);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::ZERO.checked_mul(&I128::ZERO);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::ZERO.checked_mul(&I128::ONE);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::ZERO.checked_mul(&I128::MAX);
        assert_eq!(result.unwrap(), I128::ZERO);

        // lhs = 1

        let result = I128::ONE.checked_mul(&I128::MIN);
        assert_eq!(result.unwrap(), I128::MIN);

        let result = I128::ONE.checked_mul(&I128::MINUS_ONE);
        assert_eq!(result.unwrap(), I128::MINUS_ONE);

        let result = I128::ONE.checked_mul(&I128::ZERO);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::ONE.checked_mul(&I128::ONE);
        assert_eq!(result.unwrap(), I128::ONE);

        let result = I128::ONE.checked_mul(&I128::MAX);
        assert_eq!(result.unwrap(), I128::MAX);

        // lhs = max

        let result = I128::MAX.checked_mul(&I128::MIN);
        assert!(bool::from(result.is_none()));

        let result = I128::MAX.checked_mul(&I128::MINUS_ONE);
        assert_eq!(result.unwrap(), min_plus_one);

        let result = I128::MAX.checked_mul(&I128::ZERO);
        assert_eq!(result.unwrap(), I128::ZERO);

        let result = I128::MAX.checked_mul(&I128::ONE);
        assert_eq!(result.unwrap(), I128::MAX);

        let result = I128::MAX.checked_mul(&I128::MAX);
        assert!(bool::from(result.is_none()));
    }

    #[test]
    fn test_wrapping_mul() {
        // wrapping
        let a = 0xFFFFFFFB7B63198EF870DF1F90D9BD9Eu128 as i128;
        let b = 0xF20C29FA87B356AA3B4C05C4F9C24B4Au128 as i128;
        let z = 0xAA700D354D6CF4EE881F8FF8093A19ACu128 as i128;
        assert_eq!(a.wrapping_mul(b), z);
        assert_eq!(
            I128::from_i128(a).wrapping_mul(&I128::from_i128(b)),
            I128::from_i128(z)
        );

        // no wrapping
        let c = -12345i64;
        assert_eq!(
            I128::from_i128(a).wrapping_mul(&I128::from_i64(c)),
            I128::from_i128(a.wrapping_mul(i128::from(c)))
        );

        // overflow into MSB
        let a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFu128 as i128;
        assert!(!a.is_negative() && a.wrapping_mul(a).is_negative());

        // core case
        assert_eq!(i8::MAX.wrapping_mul(2), -2);
        assert_eq!(i64::MAX.wrapping_mul(2), -2);
        assert_eq!(
            I128::MAX.wrapping_mul(&I128::from_i64(2i64)),
            I128::from_i64(-2i64)
        );

        let x = -197044252290277702i64;
        let y = -2631691865753118366;
        let z = -2988283350644101836;
        assert_eq!(x.wrapping_mul(y), z);
        assert_eq!(
            I64::from_i64(x).wrapping_mul(&I64::from_i64(y)),
            I64::from_i64(z)
        );

        let x = -86027672844719838068326470675019902915i128;
        let y = -21188806580823612823777395451044967239i128;
        let z = 11054120842379932838712398402517374997i128;
        assert_eq!(x.wrapping_mul(y), z);
        assert_eq!(
            I128::from_i128(x).wrapping_mul(&I128::from_i128(y)),
            I128::from_i128(z)
        );
    }

    #[test]
    fn test_wrapping_mul_mixed() {
        let a = U64::from_u64(0x0011223344556677);
        let b = U128::from_u128(0x8899aabbccddeeff_8899aabbccddeeff);
        let expected = a.as_int().concatenating_mul(b.as_int());
        assert_eq!(a.as_int().wrapping_mul(b.as_int()), expected.resize());
        assert_eq!(b.as_int().wrapping_mul(a.as_int()), expected.resize());
        assert_eq!(
            a.as_int().wrapping_neg().wrapping_mul(b.as_int()),
            expected.wrapping_neg().resize()
        );
        assert_eq!(
            a.as_int().wrapping_mul(&b.as_int().wrapping_neg()),
            expected.wrapping_neg().resize()
        );
        assert_eq!(
            b.as_int().wrapping_neg().wrapping_mul(a.as_int()),
            expected.wrapping_neg().resize()
        );
        assert_eq!(
            b.as_int().wrapping_mul(&a.as_int().wrapping_neg()),
            expected.wrapping_neg().resize()
        );
        assert_eq!(
            a.as_int()
                .wrapping_neg()
                .wrapping_mul(&b.as_int().wrapping_neg()),
            expected.resize()
        );
        assert_eq!(
            b.as_int()
                .wrapping_neg()
                .wrapping_mul(&a.as_int().wrapping_neg()),
            expected.resize()
        );
    }

    #[test]
    fn test_saturating_mul() {
        // wrapping
        let a = 0xFFFFFFFB7B63198EF870DF1F90D9BD9Eu128 as i128;
        let b = 0xF20C29FA87B356AA3B4C05C4F9C24B4Au128 as i128;
        assert_eq!(a.saturating_mul(b), i128::MAX);
        assert_eq!(
            I128::from_i128(a).saturating_mul(&I128::from_i128(b)),
            I128::MAX
        );

        // no wrapping
        let c = -12345i64;
        assert_eq!(
            I128::from_i128(a).saturating_mul(&I128::from_i64(c)),
            I128::from_i128(a.saturating_mul(i128::from(c)))
        );

        // core case
        assert_eq!(i8::MAX.saturating_mul(2), i8::MAX);
        assert_eq!(i8::MAX.saturating_mul(-2), i8::MIN);
        assert_eq!(i64::MAX.saturating_mul(2), i64::MAX);
        assert_eq!(i64::MAX.saturating_mul(-2), i64::MIN);
        assert_eq!(I128::MAX.saturating_mul(&I128::from_i64(2i64)), I128::MAX);
        assert_eq!(I128::MAX.saturating_mul(&I128::from_i64(-2i64)), I128::MIN);

        let x = -197044252290277702i64;
        let y = -2631691865753118366;
        assert_eq!(x.saturating_mul(y), i64::MAX);
        assert_eq!(I64::from_i64(x).saturating_mul(&I64::from_i64(y)), I64::MAX);

        let x = -86027672844719838068326470675019902915i128;
        let y = 21188806580823612823777395451044967239i128;
        assert_eq!(x.saturating_mul(y), i128::MIN);
        assert_eq!(x.saturating_mul(-y), i128::MAX);
        assert_eq!(
            I128::from_i128(x).saturating_mul(&I128::from_i128(y)),
            I128::MIN
        );
        assert_eq!(
            I128::from_i128(x).saturating_mul(&I128::from_i128(-y)),
            I128::MAX
        );
    }

    #[test]
    fn test_concatenating_mul() {
        assert_eq!(
            I128::MIN.concatenating_mul(&I128::MIN),
            I256::from_be_hex("4000000000000000000000000000000000000000000000000000000000000000")
        );
        assert_eq!(
            I128::MIN.concatenating_mul(&I128::MINUS_ONE),
            I256::from_be_hex("0000000000000000000000000000000080000000000000000000000000000000")
        );
        assert_eq!(I128::MIN.concatenating_mul(&I128::ZERO), I256::ZERO);
        assert_eq!(
            I128::MIN.concatenating_mul(&I128::ONE),
            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
        );
        assert_eq!(
            I128::MIN.concatenating_mul(&I128::MAX),
            I256::from_be_hex("C000000000000000000000000000000080000000000000000000000000000000")
        );

        assert_eq!(
            I128::MINUS_ONE.concatenating_mul(&I128::MIN),
            I256::from_be_hex("0000000000000000000000000000000080000000000000000000000000000000")
        );
        assert_eq!(
            I128::MINUS_ONE.concatenating_mul(&I128::MINUS_ONE),
            I256::ONE
        );
        assert_eq!(I128::MINUS_ONE.concatenating_mul(&I128::ZERO), I256::ZERO);
        assert_eq!(
            I128::MINUS_ONE.concatenating_mul(&I128::ONE),
            I256::MINUS_ONE
        );
        assert_eq!(
            I128::MINUS_ONE.concatenating_mul(&I128::MAX),
            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000001")
        );

        assert_eq!(I128::ZERO.concatenating_mul(&I128::MIN), I256::ZERO);
        assert_eq!(I128::ZERO.concatenating_mul(&I128::MINUS_ONE), I256::ZERO);
        assert_eq!(I128::ZERO.concatenating_mul(&I128::ZERO), I256::ZERO);
        assert_eq!(I128::ZERO.concatenating_mul(&I128::ONE), I256::ZERO);
        assert_eq!(I128::ZERO.concatenating_mul(&I128::MAX), I256::ZERO);

        assert_eq!(
            I128::ONE.concatenating_mul(&I128::MIN),
            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
        );
        assert_eq!(
            I128::ONE.concatenating_mul(&I128::MINUS_ONE),
            I256::MINUS_ONE
        );
        assert_eq!(I128::ONE.concatenating_mul(&I128::ZERO), I256::ZERO);
        assert_eq!(I128::ONE.concatenating_mul(&I128::ONE), I256::ONE);
        assert_eq!(
            I128::ONE.concatenating_mul(&I128::MAX),
            I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
        );

        assert_eq!(
            I128::MAX.concatenating_mul(&I128::MIN),
            I256::from_be_hex("C000000000000000000000000000000080000000000000000000000000000000")
        );
        assert_eq!(
            I128::MAX.concatenating_mul(&I128::MINUS_ONE),
            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000001")
        );
        assert_eq!(I128::MAX.concatenating_mul(&I128::ZERO), I256::ZERO);
        assert_eq!(
            I128::MAX.concatenating_mul(&I128::ONE),
            I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
        );
        assert_eq!(
            I128::MAX.concatenating_mul(&I128::MAX),
            I256::from_be_hex("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000001")
        );
    }

    #[test]
    fn test_concatenating_square() {
        let res = I128::from_i64(i64::MIN).concatenating_square();
        assert_eq!(
            res,
            U256::from_be_hex("0000000000000000000000000000000040000000000000000000000000000000")
        );

        let x: I128 = I128::MINUS_ONE << 64;
        let res = x.concatenating_square();
        assert_eq!(
            res,
            U256::from_be_hex("0000000000000000000000000000000100000000000000000000000000000000")
        );
    }

    #[test]
    fn test_checked_square() {
        let res = I128::from_i64(i64::MIN).checked_square();
        assert!(res.is_some().to_bool());
        assert_eq!(
            res.unwrap(),
            U128::from_be_hex("40000000000000000000000000000000")
        );

        let x: I128 = I128::MINUS_ONE << 64;
        let res = x.checked_square();
        assert!(res.is_none().to_bool());
    }

    #[test]
    fn test_wrapping_square() {
        let res = I128::from_i64(i64::MIN).wrapping_square();
        assert_eq!(res, U128::from_be_hex("40000000000000000000000000000000"));

        let x: I128 = I128::MINUS_ONE << 64;
        let res = x.wrapping_square();
        assert_eq!(res, U128::ZERO);

        let x: I128 = I128::from_i64(i64::MAX);
        let res = x.wrapping_square();
        assert_eq!(res, U128::from_be_hex("3FFFFFFFFFFFFFFF0000000000000001"));
    }

    #[test]
    fn test_saturating_square() {
        assert_eq!(
            I128::from_i64(i64::MIN).saturating_square(),
            U128::from_be_hex("40000000000000000000000000000000")
        );
        let x: I128 = I128::MINUS_ONE << 64;
        assert_eq!(x.saturating_square(), U128::MAX);
    }
}

Coverage Report

Created: 2026-11-12 06:16

Line	Count	Source
1		//! [`Int`] multiplication operations.
2
3		use crate::{
4		Checked, CheckedMul, Choice, Concat, CtOption, Int, Mul, MulAssign, Uint, WrappingMul,
5		};
6
7		impl<const LIMBS: usize> Int<LIMBS> {
8		/// Compute "wide" multiplication as a 3-tuple `(lo, hi, negate)`.
9		/// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
10		/// corresponding to the sizes of the operands; `negate` indicates whether the result should be
11		/// negated when converted from [`Uint`] to [`Int`].
12		///
13		/// Note: even if `negate` is truthy, the magnitude might be zero!
14		#[deprecated(since = "0.7.0", note = "please use `widening_mul` instead")]
15		#[must_use]
16	0	pub const fn split_mul<const RHS_LIMBS: usize>(
17	0	&self,
18	0	rhs: &Int<RHS_LIMBS>,
19	0	) -> (Uint<{ LIMBS }>, Uint<{ RHS_LIMBS }>, Choice) {
20	0	self.widening_mul(rhs)
21	0	}
22
23		/// Compute "wide" multiplication as a 3-tuple `(lo, hi, negate)`.
24		/// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
25		/// corresponding to the sizes of the operands; `negate` indicates whether the result should be
26		/// negated when converted from [`Uint`] to [`Int`].
27		///
28		/// Note: even if `negate` is truthy, the magnitude might be zero!
29		#[inline]
30		#[must_use]
31	0	pub const fn widening_mul<const RHS_LIMBS: usize>(
32	0	&self,
33	0	rhs: &Int<RHS_LIMBS>,
34	0	) -> (Uint<{ LIMBS }>, Uint<{ RHS_LIMBS }>, Choice) {
35		// Step 1: split operands into their signs and magnitudes.
36	0	let (lhs_abs, lhs_sgn) = self.abs_sign();
37	0	let (rhs_abs, rhs_sgn) = rhs.abs_sign();
38
39		// Step 2: multiply the magnitudes
40	0	let (lo, hi) = lhs_abs.widening_mul(&rhs_abs);
41
42		// Step 3. Determine if the result should be negated.
43		// This should be done if and only if lhs and rhs have opposing signs.
44		// Note: if either operand is zero, the resulting magnitude will also be zero. Negating
45		// zero, however, still yields zero, so having a truthy `negate` in that scenario is OK.
46	0	let negate = lhs_sgn.xor(rhs_sgn);
47
48	0	(lo, hi, negate)
49	0	}
50
51		/// Multiply `self` by `rhs`, returning a concatenated "wide" result.
52		#[inline]
53		#[must_use]
54	0	pub const fn concatenating_mul<const RHS_LIMBS: usize, const WIDE_LIMBS: usize>(
55	0	&self,
56	0	rhs: &Int<RHS_LIMBS>,
57	0	) -> Int<WIDE_LIMBS>
58	0	where
59	0	Uint<LIMBS>: Concat<RHS_LIMBS, Output = Uint<WIDE_LIMBS>>,
60		{
61	0	let (lhs_abs, lhs_sign) = self.abs_sign();
62	0	let (rhs_abs, rhs_sign) = rhs.abs_sign();
63	0	let product_abs = lhs_abs.concatenating_mul(&rhs_abs);
64	0	let product_sign = lhs_sign.xor(rhs_sign);
65
66		// always fits
67	0	Int::from_bits(product_abs.wrapping_neg_if(product_sign))
68	0	}
69
70		/// Multiply `self` by `rhs`, returning a `CtOption` which is `is_some` only if
71		/// overflow did not occur.
72		#[must_use]
73	0	pub const fn checked_mul<const RHS_LIMBS: usize>(
74	0	&self,
75	0	rhs: &Int<RHS_LIMBS>,
76	0	) -> CtOption<Self> {
77	0	let (abs_lhs, lhs_sgn) = self.abs_sign();
78	0	let (abs_rhs, rhs_sgn) = rhs.abs_sign();
79	0	let maybe_res = abs_lhs.checked_mul(&abs_rhs);
80	0	Self::new_from_abs_opt_sign(maybe_res, lhs_sgn.xor(rhs_sgn))
81	0	}
82
83		/// Multiply `self` by `rhs`, saturating at the numeric bounds instead of overflowing.
84		#[must_use]
85	0	pub const fn saturating_mul<const RHS_LIMBS: usize>(&self, rhs: &Int<RHS_LIMBS>) -> Self {
86	0	let (abs_lhs, lhs_sgn) = self.abs_sign();
87	0	let (abs_rhs, rhs_sgn) = rhs.abs_sign();
88	0	let maybe_res = abs_lhs.checked_mul(&abs_rhs);
89	0	let is_neg = lhs_sgn.xor(rhs_sgn);
90	0	let bound = Self::select(&Self::MAX, &Self::MIN, is_neg);
91	0	ctutils::unwrap_or!(
92	0	Self::new_from_abs_opt_sign(maybe_res, is_neg),
93		bound,
94		Self::select
95		)
96	0	}
97
98		/// Multiply `self` by `rhs`, wrapping the result in case of overflow.
99		/// This is equivalent to `(self * rhs) % (Uint::<LIMBS>::MAX + 1)`.
100		#[inline]
101		#[must_use]
102	0	pub const fn wrapping_mul<const RHS_LIMBS: usize>(&self, rhs: &Int<RHS_LIMBS>) -> Self {
103	0	if RHS_LIMBS >= LIMBS {
104	0	Self(self.0.wrapping_mul(&rhs.0))
105		} else {
106	0	let (abs_rhs, rhs_sgn) = rhs.abs_sign();
107	0	Self(self.0.wrapping_mul(&abs_rhs).wrapping_neg_if(rhs_sgn))
108		}
109	0	}
110		}
111
112		/// Squaring operations.
113		impl<const LIMBS: usize> Int<LIMBS> {
114		/// Square self, returning a concatenated "wide" result.
115		#[must_use]
116	0	pub fn concatenating_square<const WIDE_LIMBS: usize>(&self) -> Uint<WIDE_LIMBS>
117	0	where
118	0	Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
119		{
120	0	self.abs().concatenating_square()
121	0	}
122
123		/// Square self, checking that the result fits in the original [`Uint`] size.
124		#[must_use]
125	0	pub fn checked_square(&self) -> CtOption<Uint<LIMBS>> {
126	0	self.abs().checked_square()
127	0	}
128
129		/// Perform wrapping square, discarding overflow.
130		#[must_use]
131	0	pub const fn wrapping_square(&self) -> Uint<LIMBS> {
132	0	self.abs().wrapping_square()
133	0	}
134
135		/// Perform saturating squaring, returning `MAX` on overflow.
136		#[must_use]
137	0	pub const fn saturating_square(&self) -> Uint<LIMBS> {
138	0	self.abs().saturating_square()
139	0	}
140		}
141
142		impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedMul<Int<RHS_LIMBS>> for Int<LIMBS> {
143		#[inline]
144	0	fn checked_mul(&self, rhs: &Int<RHS_LIMBS>) -> CtOption<Self> {
145	0	self.checked_mul(rhs)
146	0	}
147		}
148
149		impl<const LIMBS: usize> WrappingMul for Int<LIMBS> {
150	0	fn wrapping_mul(&self, v: &Self) -> Self {
151	0	self.wrapping_mul(v)
152	0	}
153		}
154
155		impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Int<RHS_LIMBS>> for Int<LIMBS> {
156		type Output = Int<LIMBS>;
157
158	0	fn mul(self, rhs: Int<RHS_LIMBS>) -> Self {
159	0	self.mul(&rhs)
160	0	}
161		}
162
163		impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Int<RHS_LIMBS>> for Int<LIMBS> {
164		type Output = Int<LIMBS>;
165
166	0	fn mul(self, rhs: &Int<RHS_LIMBS>) -> Self {
167	0	(&self).mul(rhs)
168	0	}
169		}
170
171		impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Int<RHS_LIMBS>> for &Int<LIMBS> {
172		type Output = Int<LIMBS>;
173
174	0	fn mul(self, rhs: Int<RHS_LIMBS>) -> Self::Output {
175	0	self.mul(&rhs)
176	0	}
177		}
178
179		impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Int<RHS_LIMBS>> for &Int<LIMBS> {
180		type Output = Int<LIMBS>;
181
182	0	fn mul(self, rhs: &Int<RHS_LIMBS>) -> Self::Output {
183	0	self.checked_mul(rhs)
184	0	.expect("attempted to multiply with overflow")
185	0	}
186		}
187
188		impl<const LIMBS: usize, const RHS_LIMBS: usize> MulAssign<Int<RHS_LIMBS>> for Int<LIMBS> {
189	0	fn mul_assign(&mut self, rhs: Int<RHS_LIMBS>) {
190	0	*self = self.mul(&rhs);
191	0	}
192		}
193
194		impl<const LIMBS: usize, const RHS_LIMBS: usize> MulAssign<&Int<RHS_LIMBS>> for Int<LIMBS> {
195	0	fn mul_assign(&mut self, rhs: &Int<RHS_LIMBS>) {
196	0	*self = self.mul(rhs);
197	0	}
198		}
199
200		impl<const LIMBS: usize> MulAssign<Checked<Int<LIMBS>>> for Checked<Int<LIMBS>> {
201	0	fn mul_assign(&mut self, other: Checked<Int<LIMBS>>) {
202	0	self = self * other;
203	0	}
204		}
205
206		impl<const LIMBS: usize> MulAssign<&Checked<Int<LIMBS>>> for Checked<Int<LIMBS>> {
207	0	fn mul_assign(&mut self, other: &Checked<Int<LIMBS>>) {
208	0	self = self * other;
209	0	}
210		}
211
212		#[cfg(test)]
213		#[allow(clippy::cast_possible_wrap)]
214		mod tests {
215		use crate::{I64, I128, I256, Int, U64, U128, U256};
216
217		#[test]
218		#[allow(clippy::init_numbered_fields)]
219		fn test_checked_mul() {
220		let min_plus_one = Int {
221		0: I128::MIN.0.wrapping_add(&I128::ONE.0),
222		};
223
224		// lhs = min
225
226		let result = I128::MIN.checked_mul(&I128::MIN);
227		assert!(bool::from(result.is_none()));
228
229		let result = I128::MIN.checked_mul(&I128::MINUS_ONE);
230		assert!(bool::from(result.is_none()));
231
232		let result = I128::MIN.checked_mul(&I128::ZERO);
233		assert_eq!(result.unwrap(), I128::ZERO);
234
235		let result = I128::MIN.checked_mul(&I128::ONE);
236		assert_eq!(result.unwrap(), I128::MIN);
237
238		let result = I128::MIN.checked_mul(&I128::MAX);
239		assert!(bool::from(result.is_none()));
240
241		// lhs = -1
242
243		let result = I128::MINUS_ONE.checked_mul(&I128::MIN);
244		assert!(bool::from(result.is_none()));
245
246		let result = I128::MINUS_ONE.checked_mul(&I128::MINUS_ONE);
247		assert_eq!(result.unwrap(), I128::ONE);
248
249		let result = I128::MINUS_ONE.checked_mul(&I128::ZERO);
250		assert_eq!(result.unwrap(), I128::ZERO);
251
252		let result = I128::MINUS_ONE.checked_mul(&I128::ONE);
253		assert_eq!(result.unwrap(), I128::MINUS_ONE);
254
255		let result = I128::MINUS_ONE.checked_mul(&I128::MAX);
256		assert_eq!(result.unwrap(), min_plus_one);
257
258		// lhs = 0
259
260		let result = I128::ZERO.checked_mul(&I128::MIN);
261		assert_eq!(result.unwrap(), I128::ZERO);
262
263		let result = I128::ZERO.checked_mul(&I128::MINUS_ONE);
264		assert_eq!(result.unwrap(), I128::ZERO);
265
266		let result = I128::ZERO.checked_mul(&I128::ZERO);
267		assert_eq!(result.unwrap(), I128::ZERO);
268
269		let result = I128::ZERO.checked_mul(&I128::ONE);
270		assert_eq!(result.unwrap(), I128::ZERO);
271
272		let result = I128::ZERO.checked_mul(&I128::MAX);
273		assert_eq!(result.unwrap(), I128::ZERO);
274
275		// lhs = 1
276
277		let result = I128::ONE.checked_mul(&I128::MIN);
278		assert_eq!(result.unwrap(), I128::MIN);
279
280		let result = I128::ONE.checked_mul(&I128::MINUS_ONE);
281		assert_eq!(result.unwrap(), I128::MINUS_ONE);
282
283		let result = I128::ONE.checked_mul(&I128::ZERO);
284		assert_eq!(result.unwrap(), I128::ZERO);
285
286		let result = I128::ONE.checked_mul(&I128::ONE);
287		assert_eq!(result.unwrap(), I128::ONE);
288
289		let result = I128::ONE.checked_mul(&I128::MAX);
290		assert_eq!(result.unwrap(), I128::MAX);
291
292		// lhs = max
293
294		let result = I128::MAX.checked_mul(&I128::MIN);
295		assert!(bool::from(result.is_none()));
296
297		let result = I128::MAX.checked_mul(&I128::MINUS_ONE);
298		assert_eq!(result.unwrap(), min_plus_one);
299
300		let result = I128::MAX.checked_mul(&I128::ZERO);
301		assert_eq!(result.unwrap(), I128::ZERO);
302
303		let result = I128::MAX.checked_mul(&I128::ONE);
304		assert_eq!(result.unwrap(), I128::MAX);
305
306		let result = I128::MAX.checked_mul(&I128::MAX);
307		assert!(bool::from(result.is_none()));
308		}
309
310		#[test]
311		fn test_wrapping_mul() {
312		// wrapping
313		let a = 0xFFFFFFFB7B63198EF870DF1F90D9BD9Eu128 as i128;
314		let b = 0xF20C29FA87B356AA3B4C05C4F9C24B4Au128 as i128;
315		let z = 0xAA700D354D6CF4EE881F8FF8093A19ACu128 as i128;
316		assert_eq!(a.wrapping_mul(b), z);
317		assert_eq!(
318		I128::from_i128(a).wrapping_mul(&I128::from_i128(b)),
319		I128::from_i128(z)
320		);
321
322		// no wrapping
323		let c = -12345i64;
324		assert_eq!(
325		I128::from_i128(a).wrapping_mul(&I128::from_i64(c)),
326		I128::from_i128(a.wrapping_mul(i128::from(c)))
327		);
328
329		// overflow into MSB
330		let a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFu128 as i128;
331		assert!(!a.is_negative() && a.wrapping_mul(a).is_negative());
332
333		// core case
334		assert_eq!(i8::MAX.wrapping_mul(2), -2);
335		assert_eq!(i64::MAX.wrapping_mul(2), -2);
336		assert_eq!(
337		I128::MAX.wrapping_mul(&I128::from_i64(2i64)),
338		I128::from_i64(-2i64)
339		);
340
341		let x = -197044252290277702i64;
342		let y = -2631691865753118366;
343		let z = -2988283350644101836;
344		assert_eq!(x.wrapping_mul(y), z);
345		assert_eq!(
346		I64::from_i64(x).wrapping_mul(&I64::from_i64(y)),
347		I64::from_i64(z)
348		);
349
350		let x = -86027672844719838068326470675019902915i128;
351		let y = -21188806580823612823777395451044967239i128;
352		let z = 11054120842379932838712398402517374997i128;
353		assert_eq!(x.wrapping_mul(y), z);
354		assert_eq!(
355		I128::from_i128(x).wrapping_mul(&I128::from_i128(y)),
356		I128::from_i128(z)
357		);
358		}
359
360		#[test]
361		fn test_wrapping_mul_mixed() {
362		let a = U64::from_u64(0x0011223344556677);
363		let b = U128::from_u128(0x8899aabbccddeeff_8899aabbccddeeff);
364		let expected = a.as_int().concatenating_mul(b.as_int());
365		assert_eq!(a.as_int().wrapping_mul(b.as_int()), expected.resize());
366		assert_eq!(b.as_int().wrapping_mul(a.as_int()), expected.resize());
367		assert_eq!(
368		a.as_int().wrapping_neg().wrapping_mul(b.as_int()),
369		expected.wrapping_neg().resize()
370		);
371		assert_eq!(
372		a.as_int().wrapping_mul(&b.as_int().wrapping_neg()),
373		expected.wrapping_neg().resize()
374		);
375		assert_eq!(
376		b.as_int().wrapping_neg().wrapping_mul(a.as_int()),
377		expected.wrapping_neg().resize()
378		);
379		assert_eq!(
380		b.as_int().wrapping_mul(&a.as_int().wrapping_neg()),
381		expected.wrapping_neg().resize()
382		);
383		assert_eq!(
384		a.as_int()
385		.wrapping_neg()
386		.wrapping_mul(&b.as_int().wrapping_neg()),
387		expected.resize()
388		);
389		assert_eq!(
390		b.as_int()
391		.wrapping_neg()
392		.wrapping_mul(&a.as_int().wrapping_neg()),
393		expected.resize()
394		);
395		}
396
397		#[test]
398		fn test_saturating_mul() {
399		// wrapping
400		let a = 0xFFFFFFFB7B63198EF870DF1F90D9BD9Eu128 as i128;
401		let b = 0xF20C29FA87B356AA3B4C05C4F9C24B4Au128 as i128;
402		assert_eq!(a.saturating_mul(b), i128::MAX);
403		assert_eq!(
404		I128::from_i128(a).saturating_mul(&I128::from_i128(b)),
405		I128::MAX
406		);
407
408		// no wrapping
409		let c = -12345i64;
410		assert_eq!(
411		I128::from_i128(a).saturating_mul(&I128::from_i64(c)),
412		I128::from_i128(a.saturating_mul(i128::from(c)))
413		);
414
415		// core case
416		assert_eq!(i8::MAX.saturating_mul(2), i8::MAX);
417		assert_eq!(i8::MAX.saturating_mul(-2), i8::MIN);
418		assert_eq!(i64::MAX.saturating_mul(2), i64::MAX);
419		assert_eq!(i64::MAX.saturating_mul(-2), i64::MIN);
420		assert_eq!(I128::MAX.saturating_mul(&I128::from_i64(2i64)), I128::MAX);
421		assert_eq!(I128::MAX.saturating_mul(&I128::from_i64(-2i64)), I128::MIN);
422
423		let x = -197044252290277702i64;
424		let y = -2631691865753118366;
425		assert_eq!(x.saturating_mul(y), i64::MAX);
426		assert_eq!(I64::from_i64(x).saturating_mul(&I64::from_i64(y)), I64::MAX);
427
428		let x = -86027672844719838068326470675019902915i128;
429		let y = 21188806580823612823777395451044967239i128;
430		assert_eq!(x.saturating_mul(y), i128::MIN);
431		assert_eq!(x.saturating_mul(-y), i128::MAX);
432		assert_eq!(
433		I128::from_i128(x).saturating_mul(&I128::from_i128(y)),
434		I128::MIN
435		);
436		assert_eq!(
437		I128::from_i128(x).saturating_mul(&I128::from_i128(-y)),
438		I128::MAX
439		);
440		}
441
442		#[test]
443		fn test_concatenating_mul() {
444		assert_eq!(
445		I128::MIN.concatenating_mul(&I128::MIN),
446		I256::from_be_hex("4000000000000000000000000000000000000000000000000000000000000000")
447		);
448		assert_eq!(
449		I128::MIN.concatenating_mul(&I128::MINUS_ONE),
450		I256::from_be_hex("0000000000000000000000000000000080000000000000000000000000000000")
451		);
452		assert_eq!(I128::MIN.concatenating_mul(&I128::ZERO), I256::ZERO);
453		assert_eq!(
454		I128::MIN.concatenating_mul(&I128::ONE),
455		I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
456		);
457		assert_eq!(
458		I128::MIN.concatenating_mul(&I128::MAX),
459		I256::from_be_hex("C000000000000000000000000000000080000000000000000000000000000000")
460		);
461
462		assert_eq!(
463		I128::MINUS_ONE.concatenating_mul(&I128::MIN),
464		I256::from_be_hex("0000000000000000000000000000000080000000000000000000000000000000")
465		);
466		assert_eq!(
467		I128::MINUS_ONE.concatenating_mul(&I128::MINUS_ONE),
468		I256::ONE
469		);
470		assert_eq!(I128::MINUS_ONE.concatenating_mul(&I128::ZERO), I256::ZERO);
471		assert_eq!(
472		I128::MINUS_ONE.concatenating_mul(&I128::ONE),
473		I256::MINUS_ONE
474		);
475		assert_eq!(
476		I128::MINUS_ONE.concatenating_mul(&I128::MAX),
477		I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000001")
478		);
479
480		assert_eq!(I128::ZERO.concatenating_mul(&I128::MIN), I256::ZERO);
481		assert_eq!(I128::ZERO.concatenating_mul(&I128::MINUS_ONE), I256::ZERO);
482		assert_eq!(I128::ZERO.concatenating_mul(&I128::ZERO), I256::ZERO);
483		assert_eq!(I128::ZERO.concatenating_mul(&I128::ONE), I256::ZERO);
484		assert_eq!(I128::ZERO.concatenating_mul(&I128::MAX), I256::ZERO);
485
486		assert_eq!(
487		I128::ONE.concatenating_mul(&I128::MIN),
488		I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
489		);
490		assert_eq!(
491		I128::ONE.concatenating_mul(&I128::MINUS_ONE),
492		I256::MINUS_ONE
493		);
494		assert_eq!(I128::ONE.concatenating_mul(&I128::ZERO), I256::ZERO);
495		assert_eq!(I128::ONE.concatenating_mul(&I128::ONE), I256::ONE);
496		assert_eq!(
497		I128::ONE.concatenating_mul(&I128::MAX),
498		I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
499		);
500
501		assert_eq!(
502		I128::MAX.concatenating_mul(&I128::MIN),
503		I256::from_be_hex("C000000000000000000000000000000080000000000000000000000000000000")
504		);
505		assert_eq!(
506		I128::MAX.concatenating_mul(&I128::MINUS_ONE),
507		I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000001")
508		);
509		assert_eq!(I128::MAX.concatenating_mul(&I128::ZERO), I256::ZERO);
510		assert_eq!(
511		I128::MAX.concatenating_mul(&I128::ONE),
512		I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
513		);
514		assert_eq!(
515		I128::MAX.concatenating_mul(&I128::MAX),
516		I256::from_be_hex("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000001")
517		);
518		}
519
520		#[test]
521		fn test_concatenating_square() {
522		let res = I128::from_i64(i64::MIN).concatenating_square();
523		assert_eq!(
524		res,
525		U256::from_be_hex("0000000000000000000000000000000040000000000000000000000000000000")
526		);
527
528		let x: I128 = I128::MINUS_ONE << 64;
529		let res = x.concatenating_square();
530		assert_eq!(
531		res,
532		U256::from_be_hex("0000000000000000000000000000000100000000000000000000000000000000")
533		);
534		}
535
536		#[test]
537		fn test_checked_square() {
538		let res = I128::from_i64(i64::MIN).checked_square();
539		assert!(res.is_some().to_bool());
540		assert_eq!(
541		res.unwrap(),
542		U128::from_be_hex("40000000000000000000000000000000")
543		);
544
545		let x: I128 = I128::MINUS_ONE << 64;
546		let res = x.checked_square();
547		assert!(res.is_none().to_bool());
548		}
549
550		#[test]
551		fn test_wrapping_square() {
552		let res = I128::from_i64(i64::MIN).wrapping_square();
553		assert_eq!(res, U128::from_be_hex("40000000000000000000000000000000"));
554
555		let x: I128 = I128::MINUS_ONE << 64;
556		let res = x.wrapping_square();
557		assert_eq!(res, U128::ZERO);
558
559		let x: I128 = I128::from_i64(i64::MAX);
560		let res = x.wrapping_square();
561		assert_eq!(res, U128::from_be_hex("3FFFFFFFFFFFFFFF0000000000000001"));
562		}
563
564		#[test]
565		fn test_saturating_square() {
566		assert_eq!(
567		I128::from_i64(i64::MIN).saturating_square(),
568		U128::from_be_hex("40000000000000000000000000000000")
569		);
570		let x: I128 = I128::MINUS_ONE << 64;
571		assert_eq!(x.saturating_square(), U128::MAX);
572		}
573		}