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    #[inline]
179    fn widening_mul(self, rhs: Self) -> (Self, Self) {
180        <Self as ConstWideningMul>::widening_mul(self, rhs)
181    }
182}
183
184/// Non-const carrying multiplication that delegates to ConstCarryingMul.
185impl<T: ConstMachineWord + ConstCarryingAdd + ConstBorrowingSub + MachineWord, const N: usize>
186    CarryingMul for FixedUInt<T, N>
187{
188    #[inline]
189    fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
190        <Self as ConstCarryingMul>::carrying_mul(self, rhs, carry)
191    }
192
193    #[inline]
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#[cfg(test)]
200mod tests {
201    use super::*;
202
203    type U16 = FixedUInt<u8, 2>;
204    type U32 = FixedUInt<u8, 4>;
205
206    c0nst::c0nst! {
207        pub c0nst fn const_carrying_add<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize>(
208            a: FixedUInt<T, N>,
209            b: FixedUInt<T, N>,
210            carry: bool,
211        ) -> (FixedUInt<T, N>, bool) {
212            ConstCarryingAdd::carrying_add(a, b, carry)
213        }
214
215        pub c0nst fn const_borrowing_sub<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize>(
216            a: FixedUInt<T, N>,
217            b: FixedUInt<T, N>,
218            borrow: bool,
219        ) -> (FixedUInt<T, N>, bool) {
220            ConstBorrowingSub::borrowing_sub(a, b, borrow)
221        }
222
223        pub c0nst fn const_widening_mul<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize>(
224            a: FixedUInt<T, N>,
225            b: FixedUInt<T, N>,
226        ) -> (FixedUInt<T, N>, FixedUInt<T, N>) {
227            ConstWideningMul::widening_mul(a, b)
228        }
229
230        pub c0nst fn const_carrying_mul<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize>(
231            a: FixedUInt<T, N>,
232            b: FixedUInt<T, N>,
233            carry: FixedUInt<T, N>,
234        ) -> (FixedUInt<T, N>, FixedUInt<T, N>) {
235            ConstCarryingMul::carrying_mul(a, b, carry)
236        }
237
238        pub c0nst fn const_carrying_mul_add<T: [c0nst] ConstMachineWord + [c0nst] ConstCarryingAdd + [c0nst] ConstBorrowingSub + MachineWord, const N: usize>(
239            a: FixedUInt<T, N>,
240            b: FixedUInt<T, N>,
241            addend: FixedUInt<T, N>,
242            carry: FixedUInt<T, N>,
243        ) -> (FixedUInt<T, N>, FixedUInt<T, N>) {
244            ConstCarryingMul::carrying_mul_add(a, b, addend, carry)
245        }
246    }
247
248    #[test]
249    fn test_carrying_add_no_carry() {
250        let a = U16::from(100u8);
251        let b = U16::from(50u8);
252
253        // Without carry in
254        let (sum, carry_out) = const_carrying_add(a, b, false);
255        assert_eq!(sum, U16::from(150u8));
256        assert!(!carry_out);
257
258        // With carry in
259        let (sum, carry_out) = const_carrying_add(a, b, true);
260        assert_eq!(sum, U16::from(151u8));
261        assert!(!carry_out);
262    }
263
264    #[test]
265    fn test_carrying_add_with_overflow() {
266        let max = U16::from(0xFFFFu16);
267        let one = U16::from(1u8);
268
269        // max + 0 with carry = max + 1 = 0 with carry out
270        let (sum, carry_out) = const_carrying_add(max, U16::from(0u8), true);
271        assert_eq!(sum, U16::from(0u8));
272        assert!(carry_out);
273
274        // max + 1 = 0 with carry out
275        let (sum, carry_out) = const_carrying_add(max, one, false);
276        assert_eq!(sum, U16::from(0u8));
277        assert!(carry_out);
278
279        // max + max = 0xFFFE with carry out
280        let (sum, carry_out) = const_carrying_add(max, max, false);
281        assert_eq!(sum, U16::from(0xFFFEu16));
282        assert!(carry_out);
283    }
284
285    #[test]
286    fn test_borrowing_sub_no_borrow() {
287        let a = U16::from(150u8);
288        let b = U16::from(50u8);
289
290        // Without borrow in
291        let (diff, borrow_out) = const_borrowing_sub(a, b, false);
292        assert_eq!(diff, U16::from(100u8));
293        assert!(!borrow_out);
294
295        // With borrow in
296        let (diff, borrow_out) = const_borrowing_sub(a, b, true);
297        assert_eq!(diff, U16::from(99u8));
298        assert!(!borrow_out);
299    }
300
301    #[test]
302    fn test_borrowing_sub_with_underflow() {
303        let zero = U16::from(0u8);
304        let one = U16::from(1u8);
305
306        // 0 - 1 = 0xFFFF with borrow out
307        let (diff, borrow_out) = const_borrowing_sub(zero, one, false);
308        assert_eq!(diff, U16::from(0xFFFFu16));
309        assert!(borrow_out);
310
311        // 0 - 0 with borrow = 0xFFFF with borrow out
312        let (diff, borrow_out) = const_borrowing_sub(zero, zero, true);
313        assert_eq!(diff, U16::from(0xFFFFu16));
314        assert!(borrow_out);
315
316        // 1 - 1 with borrow = 0xFFFF with borrow out
317        let (diff, borrow_out) = const_borrowing_sub(one, one, true);
318        assert_eq!(diff, U16::from(0xFFFFu16));
319        assert!(borrow_out);
320    }
321
322    #[test]
323    fn test_widening_mul() {
324        // 100 * 100 = 10000 (fits in 16 bits, high = 0)
325        let a = U16::from(100u8);
326        let (lo, hi) = const_widening_mul(a, a);
327        assert_eq!(lo, U16::from(10000u16));
328        assert_eq!(hi, U16::from(0u8));
329
330        // 256 * 256 = 65536 = 0x10000 (low = 0, high = 1)
331        let b = U16::from(256u16);
332        let (lo, hi) = const_widening_mul(b, b);
333        assert_eq!(lo, U16::from(0u8));
334        assert_eq!(hi, U16::from(1u8));
335
336        // 0xFFFF * 0xFFFF = 0xFFFE0001
337        let max = U16::from(0xFFFFu16);
338        let (lo, hi) = const_widening_mul(max, max);
339        assert_eq!(lo, U16::from(0x0001u16)); // low 16 bits of 0xFFFE0001
340        assert_eq!(hi, U16::from(0xFFFEu16)); // high 16 bits of 0xFFFE0001
341    }
342
343    #[test]
344    fn test_widening_mul_larger() {
345        // Test with 32-bit type (U32 = FixedUInt<u8, 4>)
346        let a = U32::from(0x10000u32); // 2^16
347        let b = U32::from(0x10000u32); // 2^16
348        let (lo, hi) = const_widening_mul(a, b);
349        // 2^16 * 2^16 = 2^32 = 0x100000000
350        // low 32 bits = 0, high 32 bits = 1
351        assert_eq!(lo, U32::from(0u8));
352        assert_eq!(hi, U32::from(1u8));
353    }
354
355    #[test]
356    fn test_carrying_mul() {
357        let a = U16::from(100u8);
358        let b = U16::from(100u8);
359        let carry = U16::from(5u8);
360
361        // 100 * 100 + 5 = 10005
362        let (lo, hi) = const_carrying_mul(a, b, carry);
363        assert_eq!(lo, U16::from(10005u16));
364        assert_eq!(hi, U16::from(0u8));
365
366        // With larger carry that causes overflow in low part
367        let max = U16::from(0xFFFFu16);
368        let one = U16::from(1u8);
369        // 1 * 1 + 0xFFFF = 0x10000 = (0, 1)
370        let (lo, hi) = const_carrying_mul(one, one, max);
371        assert_eq!(lo, U16::from(0u8));
372        assert_eq!(hi, U16::from(1u8));
373    }
374
375    #[test]
376    fn test_carrying_mul_add() {
377        let a = U16::from(100u8);
378        let b = U16::from(100u8);
379        let addend = U16::from(10u8);
380        let carry = U16::from(5u8);
381
382        // 100 * 100 + 10 + 5 = 10015
383        let (lo, hi) = const_carrying_mul_add(a, b, addend, carry);
384        assert_eq!(lo, U16::from(10015u16));
385        assert_eq!(hi, U16::from(0u8));
386    }
387
388    #[test]
389    fn test_carrying_mul_add_double_overflow() {
390        // Test case where both addend and carry cause overflow
391        let max = U16::from(0xFFFFu16);
392        let one = U16::from(1u8);
393
394        // 1 * 1 + 0xFFFF + 0xFFFF = 1 + 0x1FFFE = 0x1FFFF = (0xFFFF, 1)
395        let (lo, hi) = const_carrying_mul_add(one, one, max, max);
396        assert_eq!(lo, U16::from(0xFFFFu16));
397        assert_eq!(hi, U16::from(1u8));
398    }
399
400    #[test]
401    fn test_const_context() {
402        #[cfg(feature = "nightly")]
403        {
404            const A: U16 = FixedUInt { array: [100, 0] };
405            const B: U16 = FixedUInt { array: [50, 0] };
406
407            // Test carrying_add in const context
408            const ADD_RESULT: (U16, bool) = const_carrying_add(A, B, false);
409            assert_eq!(ADD_RESULT.0, U16::from(150u8));
410            assert!(!ADD_RESULT.1);
411
412            const ADD_WITH_CARRY: (U16, bool) = const_carrying_add(A, B, true);
413            assert_eq!(ADD_WITH_CARRY.0, U16::from(151u8));
414
415            // Test borrowing_sub in const context
416            const SUB_RESULT: (U16, bool) = const_borrowing_sub(A, B, false);
417            assert_eq!(SUB_RESULT.0, U16::from(50u8));
418            assert!(!SUB_RESULT.1);
419
420            // Test widening_mul in const context
421            const C: U16 = FixedUInt { array: [0, 1] }; // 256
422            const MUL_RESULT: (U16, U16) = const_widening_mul(C, C);
423            assert_eq!(MUL_RESULT.0, U16::from(0u8)); // 256*256 = 65536, low = 0
424            assert_eq!(MUL_RESULT.1, U16::from(1u8)); // high = 1
425        }
426    }
427
428    /// Polymorphic test: verify widening_mul produces identical results across
429    /// different word layouts for the same values.
430    #[test]
431    fn test_widening_mul_polymorphic() {
432        // Generic test function following crate pattern
433        fn test_widening<T>(a: T, b: T, expected_lo: T, expected_hi: T)
434        where
435            T: ConstWideningMul
436                + ConstCarryingAdd
437                + ConstBorrowingSub
438                + Eq
439                + core::fmt::Debug
440                + Copy,
441        {
442            let (lo, hi) = ConstWideningMul::widening_mul(a, b);
443            assert_eq!(lo, expected_lo, "lo mismatch");
444            assert_eq!(hi, expected_hi, "hi mismatch");
445        }
446
447        // Test 1: 256 * 256 = 65536
448        // As u16 (FixedUInt<u8, 2>): 16-bit overflow, 256*256 = 0x10000 = (lo=0, hi=1)
449        test_widening(
450            U16::from(256u16),
451            U16::from(256u16),
452            U16::from(0u16),
453            U16::from(1u16),
454        );
455
456        // As u32 (FixedUInt<u8, 4>): fits in 32 bits, so lo=65536, hi=0
457        test_widening(
458            U32::from(256u32),
459            U32::from(256u32),
460            U32::from(65536u32),
461            U32::from(0u32),
462        );
463
464        // Test 2: 0xFFFF * 0xFFFF = 0xFFFE0001
465        test_widening(
466            U16::from(0xFFFFu16),
467            U16::from(0xFFFFu16),
468            U16::from(0x0001u16),
469            U16::from(0xFFFEu16),
470        );
471
472        // Test 3: 0xFFFFFFFF * 2 = 0x1_FFFFFFFE (tests carry across word boundary)
473        test_widening(
474            U32::from(0xFFFFFFFFu32),
475            U32::from(2u32),
476            U32::from(0xFFFFFFFEu32),
477            U32::from(1u32),
478        );
479    }
480
481    /// Polymorphic test for carrying_mul_add with edge cases.
482    #[test]
483    fn test_carrying_mul_add_polymorphic() {
484        fn test_cma<T>(a: T, b: T, addend: T, carry: T, expected_lo: T, expected_hi: T)
485        where
486            T: ConstCarryingMul + Eq + core::fmt::Debug + Copy,
487        {
488            let (lo, hi) = ConstCarryingMul::carrying_mul_add(a, b, addend, carry);
489            assert_eq!(lo, expected_lo, "lo mismatch");
490            assert_eq!(hi, expected_hi, "hi mismatch");
491        }
492
493        // Test: max * max + max + max = 0xFFFF * 0xFFFF + 0xFFFF + 0xFFFF
494        //     = 0xFFFE0001 + 0x1FFFE = 0xFFFFFFFF
495        // lo = 0xFFFF, hi = 0xFFFF
496        let max16 = U16::from(0xFFFFu16);
497        test_cma(
498            max16,
499            max16,
500            max16,
501            max16,
502            U16::from(0xFFFFu16),
503            U16::from(0xFFFFu16),
504        );
505
506        // Same test with different layout (U32 = FixedUInt<u8, 4>)
507        let max32 = U32::from(0xFFFFFFFFu32);
508        let zero32 = U32::from(0u32);
509        // max * 1 + 0 + max = max + max = 2*max = 0x1_FFFFFFFE
510        test_cma(
511            max32,
512            U32::from(1u32),
513            zero32,
514            max32,
515            U32::from(0xFFFFFFFEu32),
516            U32::from(1u32),
517        );
518    }
519
520    /// Test the non-const WideningMul trait for primitives and FixedUInt.
521    #[test]
522    fn test_widening_mul_trait() {
523        // Test primitive types via WideningMul trait
524        assert_eq!(WideningMul::widening_mul(255u8, 255u8), (1, 254)); // 0xFE01
525        assert_eq!(
526            WideningMul::widening_mul(0xFFFFu16, 0xFFFFu16),
527            (0x0001, 0xFFFE)
528        );
529        assert_eq!(
530            WideningMul::widening_mul(0xFFFF_FFFFu32, 2u32),
531            (0xFFFF_FFFE, 1)
532        );
533        assert_eq!(
534            WideningMul::widening_mul(0xFFFF_FFFF_FFFF_FFFFu64, 2u64),
535            (0xFFFF_FFFF_FFFF_FFFE, 1)
536        );
537
538        // Test FixedUInt via WideningMul trait
539        let a = U16::from(0xFFFFu16);
540        let (lo, hi) = WideningMul::widening_mul(a, a);
541        assert_eq!(lo, U16::from(0x0001u16));
542        assert_eq!(hi, U16::from(0xFFFEu16));
543
544        // Verify WideningMul produces same result as ConstWideningMul
545        let b = U32::from(0x1234_5678u32);
546        let c = U32::from(0x9ABC_DEF0u32);
547        let (lo_trait, hi_trait) = WideningMul::widening_mul(b, c);
548        let (lo_const, hi_const) = ConstWideningMul::widening_mul(b, c);
549        assert_eq!(lo_trait, lo_const);
550        assert_eq!(hi_trait, hi_const);
551    }
552
553    /// Test the non-const CarryingMul trait for primitives and FixedUInt.
554    #[test]
555    fn test_carrying_mul_trait() {
556        // Test primitive types via CarryingMul trait
557        // 10 * 10 + 5 = 105
558        assert_eq!(CarryingMul::carrying_mul(10u8, 10u8, 5u8), (105, 0));
559        // 255 * 255 + 255 = 65280 = 0xFF00
560        assert_eq!(CarryingMul::carrying_mul(255u8, 255u8, 255u8), (0, 255));
561
562        // Test carrying_mul_add: 10 * 10 + 3 + 2 = 105
563        assert_eq!(
564            CarryingMul::carrying_mul_add(10u8, 10u8, 3u8, 2u8),
565            (105, 0)
566        );
567        // 255 * 255 + 255 + 255 = 65535 = 0xFFFF
568        assert_eq!(
569            CarryingMul::carrying_mul_add(255u8, 255u8, 255u8, 255u8),
570            (255, 255)
571        );
572
573        // Test FixedUInt via CarryingMul trait
574        let a = U16::from(100u8);
575        let b = U16::from(100u8);
576        let carry = U16::from(5u8);
577        let (lo, hi) = CarryingMul::carrying_mul(a, b, carry);
578        assert_eq!(lo, U16::from(10005u16)); // 100 * 100 + 5 = 10005
579        assert_eq!(hi, U16::from(0u8));
580
581        // Verify CarryingMul produces same result as ConstCarryingMul
582        let x = U32::from(0x1234u32);
583        let y = U32::from(0x5678u32);
584        let c = U32::from(0xABCDu32);
585        let (lo_trait, hi_trait) = CarryingMul::carrying_mul(x, y, c);
586        let (lo_const, hi_const) = ConstCarryingMul::carrying_mul(x, y, c);
587        assert_eq!(lo_trait, lo_const);
588        assert_eq!(hi_trait, hi_const);
589
590        // Test carrying_mul_add for FixedUInt
591        let addend = U32::from(0x9999u32);
592        let (lo_trait, hi_trait) = CarryingMul::carrying_mul_add(x, y, addend, c);
593        let (lo_const, hi_const) = ConstCarryingMul::carrying_mul_add(x, y, addend, c);
594        assert_eq!(lo_trait, lo_const);
595        assert_eq!(hi_trait, hi_const);
596    }
597}
fixed_bigint/fixeduint/extended_precision_impl.rs

fixed_bigint/fixeduint/
extended_precision_impl.rs
