fixed_bigint/heapless/
num_integer_impl.rs

1//! `num_integer::Integer` for `HeaplessBigInt<T, CAP, Nct>`.
2//!
3//! Nct-only, mirroring `FixedUInt`. `div_floor`/`mod_floor`/`div_rem` are the
4//! unsigned div/rem (floor == truncating); `gcd` is Stein's binary algorithm;
5//! `lcm` = `a / gcd(a, b) * b`. `is_even`/`is_odd` delegate to the O(1)
6//! `Parity` LSB check. Everything resolves at the operand width `max(len)`.
7
8use super::HeaplessBigInt;
9use crate::MachineWord;
10use const_num_traits::{CarryingMul, Nct, One, PrimBits, Zero};
11
12impl<T, const CAP: usize> num_integer::Integer for HeaplessBigInt<T, CAP, Nct>
13where
14    T: MachineWord + CarryingMul<Unsigned = T, Output = T>,
15{
16    fn div_floor(&self, other: &Self) -> Self {
17        *self / *other
18    }
19
20    fn mod_floor(&self, other: &Self) -> Self {
21        *self % *other
22    }
23
24    fn gcd(&self, other: &Self) -> Self {
25        // Stein's (binary) GCD. Heapless `>>` narrows `len`, so the running
26        // values shrink as they're stripped of factors of two — that's
27        // value-correct (comparisons are value-based). The result is pinned to
28        // the operand width `max(len)`: widen before the final `<< shift` so no
29        // bit is lost and the width matches FixedUInt<k>.
30        let width = core::cmp::max(self.len(), other.len());
31        let mut m = *self;
32        let mut n = *other;
33        let zero = <Self as Zero>::zero();
34        if m == zero || n == zero {
35            return m | n; // already at max(len) via BitOr
36        }
37
38        // Common factors of two, then strip each value to odd.
39        let shift = PrimBits::trailing_zeros(m | n);
40        m = m >> (PrimBits::trailing_zeros(m) as usize);
41        n = n >> (PrimBits::trailing_zeros(n) as usize);
42
43        while m != n {
44            if m > n {
45                m -= n;
46                m = m >> (PrimBits::trailing_zeros(m) as usize);
47            } else {
48                n -= m;
49                n = n >> (PrimBits::trailing_zeros(n) as usize);
50            }
51        }
52        m.widened(width) << (shift as usize)
53    }
54
55    fn lcm(&self, other: &Self) -> Self {
56        if <Self as Zero>::is_zero(self) && <Self as Zero>::is_zero(other) {
57            // Zero at the operand width, not the minimal-width `zero()`.
58            return <Self as Zero>::zero().widened(core::cmp::max(self.len(), other.len()));
59        }
60        let gcd = self.gcd(other);
61        *self * (*other / gcd)
62    }
63
64    fn is_multiple_of(&self, other: &Self) -> bool {
65        // Guard the zero divisor (as num_integer's primitive impls do): 0 is a
66        // multiple of 0, nothing else is — no `% 0` panic.
67        if <Self as Zero>::is_zero(other) {
68            return <Self as Zero>::is_zero(self);
69        }
70        *self % *other == <Self as Zero>::zero()
71    }
72
73    fn is_even(&self) -> bool {
74        // O(1) LSB check, like FixedUInt. `len == 0` (zero) is even; otherwise
75        // `len > 0` guarantees `limbs[0]` exists.
76        self.len == 0 || self.limbs[0] & <T as One>::one() == <T as Zero>::zero()
77    }
78
79    fn is_odd(&self) -> bool {
80        !self.is_even()
81    }
82
83    fn div_rem(&self, other: &Self) -> (Self, Self) {
84        // Inherent div_rem (single pass); resolves over `&self`, so it's the
85        // inherent method, not this trait one.
86        self.div_rem(other)
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93    use num_integer::Integer;
94
95    type H = HeaplessBigInt<u32, 8, Nct>; // 256-bit CAP
96
97    #[test]
98    fn gcd_preserves_operand_width() {
99        // Two len-2 (64-bit) values in a CAP-8 carrier. Stein's `>>` narrows
100        // the running values, but the result is pinned to the operand width
101        // (len 2), not the narrow gcd magnitude — matching FixedUInt<u32, 2>.
102        let a = H::from_le_bytes(&12u64.to_le_bytes()); // len 2
103        let b = H::from_le_bytes(&18u64.to_le_bytes()); // len 2
104        let g = a.gcd(&b);
105        assert_eq!(g.len(), 2, "gcd resolves at the operand width");
106        assert_eq!(g.limbs[0], 6);
107        assert_eq!(g.limbs[1], 0);
108    }
109
110    #[test]
111    fn gcd_lcm_multi_limb() {
112        // 64-bit powers of two spanning 2 u32 limbs.
113        let a = H::from_le_bytes(&0x1_0000_0000u64.to_le_bytes()); // 2^32
114        let b = H::from_le_bytes(&0x1_8000_0000u64.to_le_bytes()); // 3·2^31
115        assert_eq!(a.gcd(&b), H::from_le_bytes(&0x8000_0000u64.to_le_bytes())); // 2^31
116        // lcm(2^32, 3·2^31) = 3·2^32
117        assert_eq!(a.lcm(&b), H::from_le_bytes(&0x3_0000_0000u64.to_le_bytes()));
118    }
119
120    #[test]
121    fn is_multiple_of_zero_divisor_no_panic() {
122        // num_integer contract: is_multiple_of(&0) is a predicate, not a panic.
123        let zero = H::from_le_bytes(&0u32.to_le_bytes());
124        let five = H::from_le_bytes(&5u32.to_le_bytes());
125        assert!(zero.is_multiple_of(&zero)); // 0 is a multiple of 0
126        assert!(!five.is_multiple_of(&zero)); // 5 is not
127    }
128
129    #[test]
130    fn lcm_of_zeros_keeps_operand_width() {
131        // lcm(0, 0) = 0 at the operand width, not the minimal len-0 zero.
132        let z = H::from_le_bytes(&0u64.to_le_bytes()); // len 2 (8 zero bytes)
133        assert_eq!(z.len(), 2);
134        assert_eq!(z.lcm(&z).len(), 2);
135    }
136}
fixed_bigint/heapless/num_integer_impl.rs

fixed_bigint/heapless/
num_integer_impl.rs
