/rust/registry/src/index.crates.io-1949cf8c6b5b557f/bnum-0.12.1/src/buint/mul.rs

Source
use crate::digit;

macro_rules! mul {
    ($BUint: ident, $BInt: ident, $Digit: ident) => {
        impl<const N: usize> $BUint<N> {
            #[inline]
            pub(super) const fn long_mul(self, rhs: Self) -> (Self, bool) {
                let mut overflow = false;
                let mut out = Self::ZERO;
                let mut carry: $Digit;

                let mut i = 0;
                while i < N {
                    carry = 0;
                    let mut j = 0;
                    while j < N {
                        let index = i + j;
                        if index < N {
                            let (prod, c) = digit::$Digit::carrying_mul(
                                self.digits[i],
                                rhs.digits[j],
                                carry,
                                out.digits[index],
                            );
                            out.digits[index] = prod;
                            carry = c;
                        } else if self.digits[i] != 0 && rhs.digits[j] != 0 {
                            overflow = true;
                            break;
                        }
                        j += 1;
                    }
                    if carry != 0 {
                        overflow = true;
                    }
                    i += 1;
                }
                (out, overflow)
            }
        }
    }
}

// fn karatsuba<const N: usize>(a: BUintD8<N>, b: BUintD8<N>, start_index: usize, end_index: usize) -> BUintD8<N> {
//     if a.last_digit_index() == 0 {
//         return b * a.digits[0];
//     }
//     if b.last_digit_index() == 0 {
//         return a * b.digits[0];
//     }
//     let mid_index = (start_index + end_index) / 2; // TODO: replace this with midpoint
//     let z2 = karatsuba(a, b, mid_index, end_index);
//     let z0 = karatsuba(a, b, end_index, mid_index);
//     // let d1 = abs_diff(x0, x1);
//     // let d2 = abs_diff(y0, y1);
//     // 
//     // let a = karatsuba((x0 - x1)(y1 - y0))
//     // let z1 = a + z2

//     todo!()
// }

// fn karat_widening(x: &mut [u8], y: &mut [u8]) -> (&mut [u8], &mut [u8]) {
//     debug_assert_eq!(x.len(), y.len());
//     if x.len() == 1 {
//         let (a, b) = (x[0], y[0]);
//         let (c, d) = a.widening_mul(b);
//         x[0] = c;
//         y[0] = d;
//         return (x, y);
//     }
//     let m = x.len().div_ceil(2); // midpoint index
//     let (x0, x1) = x.split_at_mut(m);
//     let (y0, y1) = y.split_at_mut(m);
//     let (a1karat_widening(x1, y1);
//     karat_widening(x0, y0);
// }

crate::macro_impl!(mul);

Coverage Report

Created: 2026-07-13 08:11

Line	Count	Source
1		use crate::digit;
2
3		macro_rules! mul {
4		($BUint: ident, $BInt: ident, $Digit: ident) => {
5		impl<const N: usize> $BUint<N> {
6		#[inline]
7	0	pub(super) const fn long_mul(self, rhs: Self) -> (Self, bool) {
8	0	let mut overflow = false;
9	0	let mut out = Self::ZERO;
10		let mut carry: $Digit;
11
12	0	let mut i = 0;
13	0	while i < N {
14	0	carry = 0;
15	0	let mut j = 0;
16	0	while j < N {
17	0	let index = i + j;
18	0	if index < N {
19	0	let (prod, c) = digit::$Digit::carrying_mul(
20	0	self.digits[i],
21	0	rhs.digits[j],
22	0	carry,
23	0	out.digits[index],
24	0	);
25	0	out.digits[index] = prod;
26	0	carry = c;
27	0	} else if self.digits[i] != 0 && rhs.digits[j] != 0 {
28	0	overflow = true;
29	0	break;
30	0	}
31	0	j += 1;
32		}
33	0	if carry != 0 {
34	0	overflow = true;
35	0	}
36	0	i += 1;
37		}
38	0	(out, overflow)
39	0	} Unexecuted instantiation: <bnum::buint::BUint<16>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<17>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<2>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<3>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<4>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<5>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<6>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<7>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<8>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<9>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<10>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<11>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<12>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<13>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<14>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<15>>::long_mul Unexecuted instantiation: <bnum::buint::BUint<_>>::long_mul Unexecuted instantiation: <bnum::buint::BUintD16<_>>::long_mul Unexecuted instantiation: <bnum::buint::BUintD8<_>>::long_mul Unexecuted instantiation: <bnum::buint::BUintD32<_>>::long_mul
40		}
41		}
42		}
43
44		// fn karatsuba<const N: usize>(a: BUintD8<N>, b: BUintD8<N>, start_index: usize, end_index: usize) -> BUintD8<N> {
45		// if a.last_digit_index() == 0 {
46		// return b * a.digits[0];
47		// }
48		// if b.last_digit_index() == 0 {
49		// return a * b.digits[0];
50		// }
51		// let mid_index = (start_index + end_index) / 2; // TODO: replace this with midpoint
52		// let z2 = karatsuba(a, b, mid_index, end_index);
53		// let z0 = karatsuba(a, b, end_index, mid_index);
54		// // let d1 = abs_diff(x0, x1);
55		// // let d2 = abs_diff(y0, y1);
56		// //
57		// // let a = karatsuba((x0 - x1)(y1 - y0))
58		// // let z1 = a + z2
59
60		// todo!()
61		// }
62
63		// fn karat_widening(x: &mut [u8], y: &mut [u8]) -> (&mut [u8], &mut [u8]) {
64		// debug_assert_eq!(x.len(), y.len());
65		// if x.len() == 1 {
66		// let (a, b) = (x[0], y[0]);
67		// let (c, d) = a.widening_mul(b);
68		// x[0] = c;
69		// y[0] = d;
70		// return (x, y);
71		// }
72		// let m = x.len().div_ceil(2); // midpoint index
73		// let (x0, x1) = x.split_at_mut(m);
74		// let (y0, y1) = y.split_at_mut(m);
75		// let (a1karat_widening(x1, y1);
76		// karat_widening(x0, y0);
77		// }
78
79		crate::macro_impl!(mul);