nanvm_lib/vm/bigint/
mul.rs

1use super::MAX_WORDS;
2use crate::{
3    common::sized_index::SizedIndex,
4    vm::{Any, BigInt, IVm, error},
5};
6
7use std::ops::Mul;
8
9// BigInt's Mul is implemented here, not under impls, because it needs private BigInt's stuff.
10/// `*`, or the `RangeError` of a product longer than `MAX_WORDS` words, as
11/// `<<` throws for a shift that long.
12impl<A: IVm> Mul for BigInt<A> {
13    type Output = Result<Self, Any<A>>;
14
15    fn mul(self, rhs: Self) -> Self::Output {
16        if self.is_zero() || rhs.is_zero() {
17            return Ok(Self::default());
18        }
19
20        let lhs_max = self.length() - 1;
21        let rhs_max = rhs.length() - 1;
22
23        // The product has `lhs + rhs` words or one fewer, so this refuses
24        // before anything is allocated every product that is surely past the
25        // limit, and bounds the buffer below by `MAX_WORDS + 1` words (128
26        // KiB). The product of that many words is checked again once it is
27        // normalized.
28        if u64::from(lhs_max) + u64::from(rhs_max) + 1 > MAX_WORDS {
29            return Err(error::bigint_too_large());
30        }
31
32        // TODO: 1. Implement Karatsuba multiplication for large numbers.
33        //       2. For 'value', create mutable BigInt instead of Vec<u64>.
34        //       3. Ask self, _rhs for mutable access and operate in-place on one of them (if available).
35        let total_max = lhs_max + rhs_max + 1;
36        let mut value: Vec<u64> = Vec::new();
37        if value.try_reserve_exact((total_max + 1) as usize).is_err() {
38            return Err(error::bigint_too_large());
39        }
40        value.resize((total_max + 1) as usize, 0);
41        let mut i: u32 = 0;
42        while i < total_max {
43            let mut j = i.saturating_sub(rhs_max);
44            let max = if i < lhs_max { i } else { lhs_max };
45            while j <= max {
46                value = Self::add_to_vec(value, i, self[j] as u128 * rhs[i - j] as u128);
47                j += 1;
48            }
49            i += 1;
50        }
51
52        Self::normalize_new(self.sign() * rhs.sign(), value).within_limit()
53    }
54}
55
56impl<A: IVm> BigInt<A> {
57    /// `self * base + digit`, or the `RangeError` of a result longer than
58    /// `MAX_WORDS` words: the step a digit string is read by. A product just
59    /// under the limit plus a digit carries one word past, so the sum is
60    /// checked as well as the product.
61    pub(crate) fn mul_add(self, base: Self, digit: u64) -> Result<Self, Any<A>> {
62        (self * base)? + Self::from(digit)
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use crate::vm::{
69        bigint::test_util::{T, int, pow2},
70        error,
71    };
72
73    #[test]
74    fn sign_combinations() {
75        assert_eq!(int(3) * int(5), Ok(int(15)));
76        assert_eq!(int(-3) * int(5), Ok(int(-15)));
77        assert_eq!(int(3) * int(-5), Ok(int(-15)));
78        assert_eq!(int(-3) * int(-5), Ok(int(15)));
79    }
80
81    /// The carry `mul_add` exists for: `2^1048576 − 1` is 16384 words, so
82    /// times one it passes `*`, and plus one it is 16385. The step refuses it;
83    /// with the digit zero it is the same number and passes.
84    #[test]
85    fn mul_add_checks_its_sum() {
86        let ones = (pow2(1_048_575) + (pow2(1_048_575) - int(1)).unwrap()).unwrap();
87        assert_eq!(ones.clone().mul_add(int(1), 0), Ok(ones.clone()));
88        assert_eq!(ones.mul_add(int(1), 1), Err(error::bigint_too_large()));
89    }
90
91    #[test]
92    fn zero_operand() {
93        assert_eq!(int(3) * int(0), Ok(T::default()));
94        assert_eq!(int(0) * int(-3), Ok(T::default()));
95    }
96
97    /// A product of exactly `MAX_WORDS` words, 16384, is a product: `2^62`
98    /// is one word, `2^1048513` is 16383, and their product is
99    /// `2^1048575`. The operands are lopsided to keep the work small.
100    #[test]
101    fn product_at_the_limit() {
102        assert_eq!(pow2(62) * pow2(1_048_513), Ok(pow2(1_048_575)));
103        assert_eq!(-pow2(62) * pow2(1_048_513), Ok(-pow2(1_048_575)));
104    }
105
106    /// One word more is `RangeError`, whichever of the two checks sees it.
107    /// `2^63` times `2^1048513` passes the first, which looks at the operands'
108    /// lengths, and is refused by the second once its 16385 words are known.
109    /// `2^64` (two words) times `2^1048575` (16384) is refused by the first,
110    /// before anything is allocated.
111    #[test]
112    fn product_past_the_limit() {
113        let refused = Err(error::bigint_too_large());
114        assert_eq!(pow2(63) * pow2(1_048_513), refused);
115        assert_eq!(-pow2(63) * pow2(1_048_513), refused);
116        assert_eq!(pow2(64) * pow2(1_048_575), refused);
117    }
118}
nanvm_lib/vm/bigint/mul.rs

nanvm_lib/vm/bigint/
mul.rs
