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

fixed_bigint/fixeduint/
extended_precision_impl.rs
