fixed_bigint/fixeduint/
extended_precision_impl.rs

1// Copyright 2021 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Extended precision arithmetic operations for FixedUInt.
16//!
17//! These operations expose carry/borrow inputs and outputs, and widening
18//! multiplication, useful for implementing arbitrary-precision arithmetic.
19
20use super::{add_with_carry, sub_with_borrow, FixedUInt, MachineWord};
21use crate::const_numtraits::{
22    ConstBorrowingSub, ConstCarryingAdd, ConstCarryingMul, ConstWideningMul,
23};
24use crate::machineword::ConstMachineWord;
25use crate::patch_num_traits::{CarryingMul, WideningMul};
26use crate::personality::{Personality, PersonalityTag};
27
28c0nst::c0nst! {
29    impl<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + MachineWord, const N: usize, P: Personality> c0nst ConstCarryingAdd for FixedUInt<T, N, P> {
30        fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool) {
31            let (array, carry_out) = add_with_carry(&self.array, &rhs.array, carry);
32            (Self::from_array(array), carry_out)
33        }
34    }
35
36    impl<T: [c0nst] ConstMachineWord + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality> c0nst ConstBorrowingSub for FixedUInt<T, N, P> {
37        fn borrowing_sub(self, rhs: Self, borrow: bool) -> (Self, bool) {
38            let (array, borrow_out) = sub_with_borrow(&self.array, &rhs.array, borrow);
39            (Self::from_array(array), borrow_out)
40        }
41    }
42
43    /// Helper: get value at position in 2N-word result (split into low/high).
44    c0nst fn get_at<T: [c0nst] ConstMachineWord, const N: usize>(
45        lo: &[T; N], hi: &[T; N], pos: usize
46    ) -> T {
47        if pos < N { lo[pos] } else if pos < 2 * N { hi[pos - N] } else { T::zero() }
48    }
49
50    /// Helper: set value at position in 2N-word result (split into low/high).
51    c0nst fn set_at<T: [c0nst] ConstMachineWord, const N: usize>(
52        lo: &mut [T; N], hi: &mut [T; N], pos: usize, val: T
53    ) {
54        if pos < N { lo[pos] = val; } else if pos < 2 * N { hi[pos - N] = val; }
55    }
56
57    impl<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality> c0nst ConstWideningMul for FixedUInt<T, N, P> {
58        fn widening_mul(self, rhs: Self) -> (Self, Self) {
59            // Schoolbook multiplication: for each (i,j), add the 2-word product a[i]*b[j]
60            // to result[i+j : i+j+2], propagating any carry upward.
61            let mut result_low = [T::zero(); N];
62            let mut result_high = [T::zero(); N];
63
64            let mut i = 0usize;
65            while i < N {
66                let mut j = 0usize;
67                while j < N {
68                    let pos = i + j;
69                    let (mul_lo, mul_hi) = ConstWideningMul::widening_mul(self.array[i], rhs.array[j]);
70
71                    // Add the 2-word product (mul_hi, mul_lo) at position pos.
72                    // Step 1: add mul_lo at pos
73                    let cur0 = get_at(&result_low, &result_high, pos);
74                    let (sum0, c0) = ConstCarryingAdd::carrying_add(cur0, mul_lo, false);
75                    set_at(&mut result_low, &mut result_high, pos, sum0);
76
77                    // Step 2: add mul_hi + carry at pos+1
78                    let cur1 = get_at(&result_low, &result_high, pos + 1);
79                    let (sum1, c1) = ConstCarryingAdd::carrying_add(cur1, mul_hi, c0);
80                    set_at(&mut result_low, &mut result_high, pos + 1, sum1);
81
82                    // Step 3: propagate any remaining carry. Dispatched on
83                    // personality so Nct keeps the original fast early-exit
84                    // (the tail is the inner-inner loop of Montgomery
85                    // multiplication and matters a lot for verify-side
86                    // throughput). Ct iterates the full tail unconditionally
87                    // so the loop length depends only on the public outer
88                    // counters i, j.
89                    let mut carry = c1;
90                    let mut p = pos + 2;
91                    match P::TAG {
92                        PersonalityTag::Nct => {
93                            while carry && p < 2 * N {
94                                let cur = get_at(&result_low, &result_high, p);
95                                let (sum, c) = ConstCarryingAdd::carrying_add(cur, T::zero(), true);
96                                set_at(&mut result_low, &mut result_high, p, sum);
97                                carry = c;
98                                p += 1;
99                            }
100                        }
101                        PersonalityTag::Ct => {
102                            while p < 2 * N {
103                                let cur = get_at(&result_low, &result_high, p);
104                                let (sum, c) = ConstCarryingAdd::carrying_add(cur, T::zero(), carry);
105                                set_at(&mut result_low, &mut result_high, p, sum);
106                                carry = c;
107                                p += 1;
108                            }
109                        }
110                    }
111
112                    j += 1;
113                }
114                i += 1;
115            }
116
117            (Self::from_array(result_low), Self::from_array(result_high))
118        }
119    }
120
121    impl<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality> c0nst ConstCarryingMul for FixedUInt<T, N, P> {
122        fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
123            // widening_mul + add carry to result
124            let (lo, hi) = ConstWideningMul::widening_mul(self, rhs);
125
126            // Add carry to lo, propagate overflow to hi using carry bit directly
127            let (lo2, c) = add_with_carry(&lo.array, &carry.array, false);
128
129            // Pass the carry bit directly instead of constructing a temporary array
130            let zeros = [T::zero(); N];
131            let (hi2, _) = add_with_carry(&hi.array, &zeros, c);
132
133            (Self::from_array(lo2), Self::from_array(hi2))
134        }
135
136        fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self) {
137            // widening_mul + add addend + add carry
138            let (lo, hi) = ConstWideningMul::widening_mul(self, rhs);
139
140            // Add carry to lo
141            let (lo2, c1) = add_with_carry(&lo.array, &carry.array, false);
142
143            // Add addend to lo2
144            let (lo3, c2) = add_with_carry(&lo2, &addend.array, false);
145
146            // Add carry bits to hi separately (both c1 and c2 can be true = need to add 2)
147            let zeros = [T::zero(); N];
148            let (hi2, _) = add_with_carry(&hi.array, &zeros, c1);
149            let (hi3, _) = add_with_carry(&hi2, &zeros, c2);
150
151            (Self::from_array(lo3), Self::from_array(hi3))
152        }
153    }
154}
155
156/// Non-const widening multiplication that delegates to ConstWideningMul.
157impl<
158        T: ConstMachineWord + ConstCarryingAdd + ConstBorrowingSub + MachineWord,
159        const N: usize,
160        P: Personality,
161    > WideningMul for FixedUInt<T, N, P>
162{
163    type Output = Self;
164    fn widening_mul(self, rhs: Self) -> (Self, Self) {
165        <Self as ConstWideningMul>::widening_mul(self, rhs)
166    }
167}
168
169/// Ref-based widening multiplication — allows calling with references.
170impl<
171        T: ConstMachineWord + ConstCarryingAdd + ConstBorrowingSub + MachineWord,
172        const N: usize,
173        P: Personality,
174    > WideningMul for &FixedUInt<T, N, P>
175{
176    type Output = FixedUInt<T, N, P>;
177    fn widening_mul(self, rhs: Self) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
178        <FixedUInt<T, N, P> as ConstWideningMul>::widening_mul(*self, *rhs)
179    }
180}
181
182/// Non-const carrying multiplication that delegates to ConstCarryingMul.
183impl<
184        T: ConstMachineWord + ConstCarryingAdd + ConstBorrowingSub + MachineWord,
185        const N: usize,
186        P: Personality,
187    > CarryingMul for FixedUInt<T, N, P>
188{
189    type Output = Self;
190    fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
191        <Self as ConstCarryingMul>::carrying_mul(self, rhs, carry)
192    }
193
194    fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self) {
195        <Self as ConstCarryingMul>::carrying_mul_add(self, rhs, addend, carry)
196    }
197}
198
199/// Ref-based carrying multiplication — allows calling with references.
200impl<
201        T: ConstMachineWord + ConstCarryingAdd + ConstBorrowingSub + MachineWord,
202        const N: usize,
203        P: Personality,
204    > CarryingMul for &FixedUInt<T, N, P>
205{
206    type Output = FixedUInt<T, N, P>;
207    fn carrying_mul(self, rhs: Self, carry: Self) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
208        <FixedUInt<T, N, P> as ConstCarryingMul>::carrying_mul(*self, *rhs, *carry)
209    }
210
211    fn carrying_mul_add(
212        self,
213        rhs: Self,
214        addend: Self,
215        carry: Self,
216    ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
217        <FixedUInt<T, N, P> as ConstCarryingMul>::carrying_mul_add(*self, *rhs, *addend, *carry)
218    }
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224
225    type U16 = FixedUInt<u8, 2>;
226    type U32 = FixedUInt<u8, 4>;
227
228    c0nst::c0nst! {
229        pub c0nst fn const_carrying_add<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality>(
230            a: FixedUInt<T, N, P>,
231            b: FixedUInt<T, N, P>,
232            carry: bool,
233        ) -> (FixedUInt<T, N, P>, bool) {
234            ConstCarryingAdd::carrying_add(a, b, carry)
235        }
236
237        pub c0nst fn const_borrowing_sub<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality>(
238            a: FixedUInt<T, N, P>,
239            b: FixedUInt<T, N, P>,
240            borrow: bool,
241        ) -> (FixedUInt<T, N, P>, bool) {
242            ConstBorrowingSub::borrowing_sub(a, b, borrow)
243        }
244
245        pub c0nst fn const_widening_mul<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality>(
246            a: FixedUInt<T, N, P>,
247            b: FixedUInt<T, N, P>,
248        ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
249            ConstWideningMul::widening_mul(a, b)
250        }
251
252        pub c0nst fn const_carrying_mul<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality>(
253            a: FixedUInt<T, N, P>,
254            b: FixedUInt<T, N, P>,
255            carry: FixedUInt<T, N, P>,
256        ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
257            ConstCarryingMul::carrying_mul(a, b, carry)
258        }
259
260        pub c0nst fn const_carrying_mul_add<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize, P: Personality>(
261            a: FixedUInt<T, N, P>,
262            b: FixedUInt<T, N, P>,
263            addend: FixedUInt<T, N, P>,
264            carry: FixedUInt<T, N, P>,
265        ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
266            ConstCarryingMul::carrying_mul_add(a, b, addend, carry)
267        }
268    }
269
270    #[test]
271    fn test_carrying_add_no_carry() {
272        let a = U16::from(100u8);
273        let b = U16::from(50u8);
274
275        // Without carry in
276        let (sum, carry_out) = const_carrying_add(a, b, false);
277        assert_eq!(sum, U16::from(150u8));
278        assert!(!carry_out);
279
280        // With carry in
281        let (sum, carry_out) = const_carrying_add(a, b, true);
282        assert_eq!(sum, U16::from(151u8));
283        assert!(!carry_out);
284    }
285
286    #[test]
287    fn test_carrying_add_with_overflow() {
288        let max = U16::from(0xFFFFu16);
289        let one = U16::from(1u8);
290
291        // max + 0 with carry = max + 1 = 0 with carry out
292        let (sum, carry_out) = const_carrying_add(max, U16::from(0u8), true);
293        assert_eq!(sum, U16::from(0u8));
294        assert!(carry_out);
295
296        // max + 1 = 0 with carry out
297        let (sum, carry_out) = const_carrying_add(max, one, false);
298        assert_eq!(sum, U16::from(0u8));
299        assert!(carry_out);
300
301        // max + max = 0xFFFE with carry out
302        let (sum, carry_out) = const_carrying_add(max, max, false);
303        assert_eq!(sum, U16::from(0xFFFEu16));
304        assert!(carry_out);
305    }
306
307    #[test]
308    fn test_borrowing_sub_no_borrow() {
309        let a = U16::from(150u8);
310        let b = U16::from(50u8);
311
312        // Without borrow in
313        let (diff, borrow_out) = const_borrowing_sub(a, b, false);
314        assert_eq!(diff, U16::from(100u8));
315        assert!(!borrow_out);
316
317        // With borrow in
318        let (diff, borrow_out) = const_borrowing_sub(a, b, true);
319        assert_eq!(diff, U16::from(99u8));
320        assert!(!borrow_out);
321    }
322
323    #[test]
324    fn test_borrowing_sub_with_underflow() {
325        let zero = U16::from(0u8);
326        let one = U16::from(1u8);
327
328        // 0 - 1 = 0xFFFF with borrow out
329        let (diff, borrow_out) = const_borrowing_sub(zero, one, false);
330        assert_eq!(diff, U16::from(0xFFFFu16));
331        assert!(borrow_out);
332
333        // 0 - 0 with borrow = 0xFFFF with borrow out
334        let (diff, borrow_out) = const_borrowing_sub(zero, zero, true);
335        assert_eq!(diff, U16::from(0xFFFFu16));
336        assert!(borrow_out);
337
338        // 1 - 1 with borrow = 0xFFFF with borrow out
339        let (diff, borrow_out) = const_borrowing_sub(one, one, true);
340        assert_eq!(diff, U16::from(0xFFFFu16));
341        assert!(borrow_out);
342    }
343
344    #[test]
345    fn test_widening_mul() {
346        // 100 * 100 = 10000 (fits in 16 bits, high = 0)
347        let a = U16::from(100u8);
348        let (lo, hi) = const_widening_mul(a, a);
349        assert_eq!(lo, U16::from(10000u16));
350        assert_eq!(hi, U16::from(0u8));
351
352        // 256 * 256 = 65536 = 0x10000 (low = 0, high = 1)
353        let b = U16::from(256u16);
354        let (lo, hi) = const_widening_mul(b, b);
355        assert_eq!(lo, U16::from(0u8));
356        assert_eq!(hi, U16::from(1u8));
357
358        // 0xFFFF * 0xFFFF = 0xFFFE0001
359        let max = U16::from(0xFFFFu16);
360        let (lo, hi) = const_widening_mul(max, max);
361        assert_eq!(lo, U16::from(0x0001u16)); // low 16 bits of 0xFFFE0001
362        assert_eq!(hi, U16::from(0xFFFEu16)); // high 16 bits of 0xFFFE0001
363    }
364
365    #[test]
366    fn test_widening_mul_larger() {
367        // Test with 32-bit type (U32 = FixedUInt<u8, 4>)
368        let a = U32::from(0x10000u32); // 2^16
369        let b = U32::from(0x10000u32); // 2^16
370        let (lo, hi) = const_widening_mul(a, b);
371        // 2^16 * 2^16 = 2^32 = 0x100000000
372        // low 32 bits = 0, high 32 bits = 1
373        assert_eq!(lo, U32::from(0u8));
374        assert_eq!(hi, U32::from(1u8));
375    }
376
377    #[test]
378    fn test_carrying_mul() {
379        let a = U16::from(100u8);
380        let b = U16::from(100u8);
381        let carry = U16::from(5u8);
382
383        // 100 * 100 + 5 = 10005
384        let (lo, hi) = const_carrying_mul(a, b, carry);
385        assert_eq!(lo, U16::from(10005u16));
386        assert_eq!(hi, U16::from(0u8));
387
388        // With larger carry that causes overflow in low part
389        let max = U16::from(0xFFFFu16);
390        let one = U16::from(1u8);
391        // 1 * 1 + 0xFFFF = 0x10000 = (0, 1)
392        let (lo, hi) = const_carrying_mul(one, one, max);
393        assert_eq!(lo, U16::from(0u8));
394        assert_eq!(hi, U16::from(1u8));
395    }
396
397    #[test]
398    fn test_carrying_mul_add() {
399        let a = U16::from(100u8);
400        let b = U16::from(100u8);
401        let addend = U16::from(10u8);
402        let carry = U16::from(5u8);
403
404        // 100 * 100 + 10 + 5 = 10015
405        let (lo, hi) = const_carrying_mul_add(a, b, addend, carry);
406        assert_eq!(lo, U16::from(10015u16));
407        assert_eq!(hi, U16::from(0u8));
408    }
409
410    #[test]
411    fn test_carrying_mul_add_double_overflow() {
412        // Test case where both addend and carry cause overflow
413        let max = U16::from(0xFFFFu16);
414        let one = U16::from(1u8);
415
416        // 1 * 1 + 0xFFFF + 0xFFFF = 1 + 0x1FFFE = 0x1FFFF = (0xFFFF, 1)
417        let (lo, hi) = const_carrying_mul_add(one, one, max, max);
418        assert_eq!(lo, U16::from(0xFFFFu16));
419        assert_eq!(hi, U16::from(1u8));
420    }
421
422    #[test]
423    fn test_const_context() {
424        #[cfg(feature = "nightly")]
425        {
426            const A: U16 = FixedUInt::from_array([100, 0]);
427            const B: U16 = FixedUInt::from_array([50, 0]);
428
429            // Test carrying_add in const context
430            const ADD_RESULT: (U16, bool) = const_carrying_add(A, B, false);
431            assert_eq!(ADD_RESULT.0, U16::from(150u8));
432            assert!(!ADD_RESULT.1);
433
434            const ADD_WITH_CARRY: (U16, bool) = const_carrying_add(A, B, true);
435            assert_eq!(ADD_WITH_CARRY.0, U16::from(151u8));
436
437            // Test borrowing_sub in const context
438            const SUB_RESULT: (U16, bool) = const_borrowing_sub(A, B, false);
439            assert_eq!(SUB_RESULT.0, U16::from(50u8));
440            assert!(!SUB_RESULT.1);
441
442            // Test widening_mul in const context
443            const C: U16 = FixedUInt::from_array([0, 1]); // 256
444            const MUL_RESULT: (U16, U16) = const_widening_mul(C, C);
445            assert_eq!(MUL_RESULT.0, U16::from(0u8)); // 256*256 = 65536, low = 0
446            assert_eq!(MUL_RESULT.1, U16::from(1u8)); // high = 1
447        }
448    }
449
450    /// Polymorphic test: verify widening_mul produces identical results across
451    /// different word layouts for the same values.
452    #[test]
453    fn test_widening_mul_polymorphic() {
454        // Generic test function following crate pattern
455        fn test_widening<T>(a: T, b: T, expected_lo: T, expected_hi: T)
456        where
457            T: ConstWideningMul
458                + ConstCarryingAdd
459                + ConstBorrowingSub
460                + Eq
461                + core::fmt::Debug
462                + Copy,
463        {
464            let (lo, hi) = ConstWideningMul::widening_mul(a, b);
465            assert_eq!(lo, expected_lo, "lo mismatch");
466            assert_eq!(hi, expected_hi, "hi mismatch");
467        }
468
469        // Test 1: 256 * 256 = 65536
470        // As u16 (FixedUInt<u8, 2>): 16-bit overflow, 256*256 = 0x10000 = (lo=0, hi=1)
471        test_widening(
472            U16::from(256u16),
473            U16::from(256u16),
474            U16::from(0u16),
475            U16::from(1u16),
476        );
477
478        // As u32 (FixedUInt<u8, 4>): fits in 32 bits, so lo=65536, hi=0
479        test_widening(
480            U32::from(256u32),
481            U32::from(256u32),
482            U32::from(65536u32),
483            U32::from(0u32),
484        );
485
486        // Test 2: 0xFFFF * 0xFFFF = 0xFFFE0001
487        test_widening(
488            U16::from(0xFFFFu16),
489            U16::from(0xFFFFu16),
490            U16::from(0x0001u16),
491            U16::from(0xFFFEu16),
492        );
493
494        // Test 3: 0xFFFFFFFF * 2 = 0x1_FFFFFFFE (tests carry across word boundary)
495        test_widening(
496            U32::from(0xFFFFFFFFu32),
497            U32::from(2u32),
498            U32::from(0xFFFFFFFEu32),
499            U32::from(1u32),
500        );
501    }
502
503    /// Polymorphic test for carrying_mul_add with edge cases.
504    #[test]
505    fn test_carrying_mul_add_polymorphic() {
506        fn test_cma<T>(a: T, b: T, addend: T, carry: T, expected_lo: T, expected_hi: T)
507        where
508            T: ConstCarryingMul + Eq + core::fmt::Debug + Copy,
509        {
510            let (lo, hi) = ConstCarryingMul::carrying_mul_add(a, b, addend, carry);
511            assert_eq!(lo, expected_lo, "lo mismatch");
512            assert_eq!(hi, expected_hi, "hi mismatch");
513        }
514
515        // Test: max * max + max + max = 0xFFFF * 0xFFFF + 0xFFFF + 0xFFFF
516        //     = 0xFFFE0001 + 0x1FFFE = 0xFFFFFFFF
517        // lo = 0xFFFF, hi = 0xFFFF
518        let max16 = U16::from(0xFFFFu16);
519        test_cma(
520            max16,
521            max16,
522            max16,
523            max16,
524            U16::from(0xFFFFu16),
525            U16::from(0xFFFFu16),
526        );
527
528        // Same test with different layout (U32 = FixedUInt<u8, 4>)
529        let max32 = U32::from(0xFFFFFFFFu32);
530        let zero32 = U32::from(0u32);
531        // max * 1 + 0 + max = max + max = 2*max = 0x1_FFFFFFFE
532        test_cma(
533            max32,
534            U32::from(1u32),
535            zero32,
536            max32,
537            U32::from(0xFFFFFFFEu32),
538            U32::from(1u32),
539        );
540    }
541
542    /// Test the non-const WideningMul trait for primitives and FixedUInt.
543    #[test]
544    fn test_widening_mul_trait() {
545        // Test primitive types via WideningMul trait
546        assert_eq!(WideningMul::widening_mul(255u8, 255u8), (1, 254)); // 0xFE01
547        assert_eq!(
548            WideningMul::widening_mul(0xFFFFu16, 0xFFFFu16),
549            (0x0001, 0xFFFE)
550        );
551        assert_eq!(
552            WideningMul::widening_mul(0xFFFF_FFFFu32, 2u32),
553            (0xFFFF_FFFE, 1)
554        );
555        assert_eq!(
556            WideningMul::widening_mul(0xFFFF_FFFF_FFFF_FFFFu64, 2u64),
557            (0xFFFF_FFFF_FFFF_FFFE, 1)
558        );
559
560        // Test FixedUInt via WideningMul trait
561        let a = U16::from(0xFFFFu16);
562        let (lo, hi) = WideningMul::widening_mul(a, a);
563        assert_eq!(lo, U16::from(0x0001u16));
564        assert_eq!(hi, U16::from(0xFFFEu16));
565
566        // Verify WideningMul produces same result as ConstWideningMul
567        let b = U32::from(0x1234_5678u32);
568        let c = U32::from(0x9ABC_DEF0u32);
569        let (lo_trait, hi_trait) = WideningMul::widening_mul(b, c);
570        let (lo_const, hi_const) = ConstWideningMul::widening_mul(b, c);
571        assert_eq!(lo_trait, lo_const);
572        assert_eq!(hi_trait, hi_const);
573    }
574
575    /// Test the non-const CarryingMul trait for primitives and FixedUInt.
576    #[test]
577    fn test_carrying_mul_trait() {
578        // Test primitive types via CarryingMul trait
579        // 10 * 10 + 5 = 105
580        assert_eq!(CarryingMul::carrying_mul(10u8, 10u8, 5u8), (105, 0));
581        // 255 * 255 + 255 = 65280 = 0xFF00
582        assert_eq!(CarryingMul::carrying_mul(255u8, 255u8, 255u8), (0, 255));
583
584        // Test carrying_mul_add: 10 * 10 + 3 + 2 = 105
585        assert_eq!(
586            CarryingMul::carrying_mul_add(10u8, 10u8, 3u8, 2u8),
587            (105, 0)
588        );
589        // 255 * 255 + 255 + 255 = 65535 = 0xFFFF
590        assert_eq!(
591            CarryingMul::carrying_mul_add(255u8, 255u8, 255u8, 255u8),
592            (255, 255)
593        );
594
595        // Test FixedUInt via CarryingMul trait
596        let a = U16::from(100u8);
597        let b = U16::from(100u8);
598        let carry = U16::from(5u8);
599        let (lo, hi) = CarryingMul::carrying_mul(a, b, carry);
600        assert_eq!(lo, U16::from(10005u16)); // 100 * 100 + 5 = 10005
601        assert_eq!(hi, U16::from(0u8));
602
603        // Verify CarryingMul produces same result as ConstCarryingMul
604        let x = U32::from(0x1234u32);
605        let y = U32::from(0x5678u32);
606        let c = U32::from(0xABCDu32);
607        let (lo_trait, hi_trait) = CarryingMul::carrying_mul(x, y, c);
608        let (lo_const, hi_const) = ConstCarryingMul::carrying_mul(x, y, c);
609        assert_eq!(lo_trait, lo_const);
610        assert_eq!(hi_trait, hi_const);
611
612        // Test carrying_mul_add for FixedUInt
613        let addend = U32::from(0x9999u32);
614        let (lo_trait, hi_trait) = CarryingMul::carrying_mul_add(x, y, addend, c);
615        let (lo_const, hi_const) = ConstCarryingMul::carrying_mul_add(x, y, addend, c);
616        assert_eq!(lo_trait, lo_const);
617        assert_eq!(hi_trait, hi_const);
618    }
619
620    /// Test ref-based WideningMul and CarryingMul impls.
621    #[test]
622    fn test_ref_based_mul_traits() {
623        // Primitives: ref should match value
624        assert_eq!(
625            WideningMul::widening_mul(&0xFFFFu16, &0xFFFFu16),
626            WideningMul::widening_mul(0xFFFFu16, 0xFFFFu16),
627        );
628        assert_eq!(
629            CarryingMul::carrying_mul(&255u8, &255u8, &255u8),
630            CarryingMul::carrying_mul(255u8, 255u8, 255u8),
631        );
632        assert_eq!(
633            CarryingMul::carrying_mul_add(&10u8, &10u8, &3u8, &2u8),
634            CarryingMul::carrying_mul_add(10u8, 10u8, 3u8, 2u8),
635        );
636
637        // FixedUInt: ref should match value
638        let a = U32::from(0x1234_5678u32);
639        let b = U32::from(0x9ABC_DEF0u32);
640        assert_eq!(
641            WideningMul::widening_mul(&a, &b),
642            WideningMul::widening_mul(a, b),
643        );
644
645        let carry = U16::from(5u8);
646        let x = U16::from(100u8);
647        assert_eq!(
648            CarryingMul::carrying_mul(&x, &x, &carry),
649            CarryingMul::carrying_mul(x, x, carry),
650        );
651        let addend = U16::from(10u8);
652        assert_eq!(
653            CarryingMul::carrying_mul_add(&x, &x, &addend, &carry),
654            CarryingMul::carrying_mul_add(x, x, addend, carry),
655        );
656    }
657}
fixed_bigint/fixeduint/extended_precision_impl.rs

fixed_bigint/fixeduint/
extended_precision_impl.rs
