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, add_with_carry, sub_with_borrow};
21use crate::machineword::ConstMachineWord;
22use const_num_traits::{
23    BorrowingSub, Bounded, CarryingAdd, CarryingMul, Personality, PersonalityTag, PrimInt, Zero,
24};
25
26c0nst::c0nst! {
27    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> CarryingAdd for FixedUInt<T, N, P> {
28        type Output = FixedUInt<T, N, P>;
29        fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool) {
30            let (array, carry_out) = add_with_carry(&self.array, &rhs.array, carry);
31            (Self::from_array(array), carry_out)
32        }
33    }
34
35    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> BorrowingSub for FixedUInt<T, N, P> {
36        type Output = 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    // `WideningMul` for FixedUInt is intentionally NOT implemented.
58    // `WideningMul::Wide` is a single double-width primitive (e.g.
59    // `Wide = u16` for `u8`); fixed-width-generic `FixedUInt<N>` has
60    // no `FixedUInt<2N>` to be `Wide` without `generic_const_exprs`.
61    // The schoolbook full product is exposed through `CarryingMul`
62    // below, which returns `(low, high)` natively.
63
64    /// Schoolbook full product `self * rhs` returning the 2N-word result
65    /// split into two N-word halves `(low, high)`. Private helper shared
66    /// between `CarryingMul::carrying_mul` and `carrying_mul_add`.
67    c0nst fn schoolbook_mul<
68        T: [c0nst] ConstMachineWord + MachineWord,
69        const N: usize, P: Personality,
70    >(
71        a: FixedUInt<T, N, P>, b: FixedUInt<T, N, P>,
72    ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>)
73    where
74        <T as ConstMachineWord>::ConstDoubleWord: [c0nst] PrimInt,
75    {
76        // External `WideningMul` on T returns a single wide-int
77        // (`<u8 as WideningMul>::Wide = u16`), not a `(lo, hi)` tuple.
78        // We compute the per-limb wide product via the
79        // `ConstMachineWord` double-word path and split into two T
80        // halves with a mask + shift.
81        let word_bits = core::mem::size_of::<T>() * 8;
82        let t_max_dw = <T as ConstMachineWord>::to_double(<T as Bounded>::max_value());
83        let mut result_low = [<T as Zero>::zero(); N];
84        let mut result_high = [<T as Zero>::zero(); N];
85
86        let mut i = 0usize;
87        while i < N {
88            let mut j = 0usize;
89            while j < N {
90                let pos = i + j;
91                let op1_dw = <T as ConstMachineWord>::to_double(a.array[i]);
92                let op2_dw = <T as ConstMachineWord>::to_double(b.array[j]);
93                let prod_dw = op1_dw * op2_dw;
94                let mul_lo = <T as ConstMachineWord>::from_double(prod_dw & t_max_dw);
95                let mul_hi = <T as ConstMachineWord>::from_double(prod_dw >> word_bits);
96
97                // Add the 2-word product (mul_hi, mul_lo) at position pos.
98                let cur0 = get_at(&result_low, &result_high, pos);
99                let (sum0, c0) = CarryingAdd::carrying_add(cur0, mul_lo, false);
100                set_at(&mut result_low, &mut result_high, pos, sum0);
101
102                let cur1 = get_at(&result_low, &result_high, pos + 1);
103                let (sum1, c1) = CarryingAdd::carrying_add(cur1, mul_hi, c0);
104                set_at(&mut result_low, &mut result_high, pos + 1, sum1);
105
106                // Propagate any remaining carry. Personality-dispatched:
107                // Nct keeps the fast early-exit (the tail is the
108                // inner-inner Montgomery loop and matters for verify-side
109                // throughput); Ct iterates the full tail unconditionally
110                // so loop length depends only on the public counters.
111                let mut carry = c1;
112                let mut p = pos + 2;
113                match P::TAG {
114                    PersonalityTag::Nct => {
115                        while carry && p < 2 * N {
116                            let cur = get_at(&result_low, &result_high, p);
117                            let (sum, c) = CarryingAdd::carrying_add(cur, T::zero(), true);
118                            set_at(&mut result_low, &mut result_high, p, sum);
119                            carry = c;
120                            p += 1;
121                        }
122                    }
123                    PersonalityTag::Ct => {
124                        while p < 2 * N {
125                            let cur = get_at(&result_low, &result_high, p);
126                            let (sum, c) = CarryingAdd::carrying_add(cur, T::zero(), carry);
127                            set_at(&mut result_low, &mut result_high, p, sum);
128                            carry = c;
129                            p += 1;
130                        }
131                    }
132                }
133
134                j += 1;
135            }
136            i += 1;
137        }
138
139        (FixedUInt::from_array(result_low), FixedUInt::from_array(result_high))
140    }
141
142    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> CarryingMul for FixedUInt<T, N, P>
143    where
144        <T as ConstMachineWord>::ConstDoubleWord: [c0nst] PrimInt,
145    {
146        type Unsigned = Self;
147        type Output = FixedUInt<T, N, P>;
148        fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
149            // Full product + add carry to low half, propagate to high.
150            let (lo, hi) = schoolbook_mul(self, rhs);
151
152            let (lo2, c) = add_with_carry(&lo.array, &carry.array, false);
153            let zeros = [T::zero(); N];
154            let (hi2, _) = add_with_carry(&hi.array, &zeros, c);
155
156            (Self::from_array(lo2), Self::from_array(hi2))
157        }
158
159        fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self) {
160            // Full product + add addend + add carry.
161            let (lo, hi) = schoolbook_mul(self, rhs);
162
163            let (lo2, c1) = add_with_carry(&lo.array, &carry.array, false);
164            let (lo3, c2) = add_with_carry(&lo2, &addend.array, false);
165
166            // Both c1 and c2 can be true; add each carry to hi separately.
167            let zeros = [T::zero(); N];
168            let (hi2, _) = add_with_carry(&hi.array, &zeros, c1);
169            let (hi3, _) = add_with_carry(&hi2, &zeros, c2);
170
171            (Self::from_array(lo3), Self::from_array(hi3))
172        }
173    }
174
175    // --- Reference-receiver bigint-helper impls -----------------------------
176
177    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> CarryingAdd for &FixedUInt<T, N, P> {
178        type Output = FixedUInt<T, N, P>;
179        fn carrying_add(self, rhs: Self, carry: bool) -> (FixedUInt<T, N, P>, bool) {
180            <FixedUInt<T, N, P> as CarryingAdd>::carrying_add(FixedUInt::from_array(self.array), FixedUInt::from_array(rhs.array), carry)
181        }
182    }
183
184    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> BorrowingSub for &FixedUInt<T, N, P> {
185        type Output = FixedUInt<T, N, P>;
186        fn borrowing_sub(self, rhs: Self, borrow: bool) -> (FixedUInt<T, N, P>, bool) {
187            <FixedUInt<T, N, P> as BorrowingSub>::borrowing_sub(FixedUInt::from_array(self.array), FixedUInt::from_array(rhs.array), borrow)
188        }
189    }
190
191    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> CarryingMul for &FixedUInt<T, N, P>
192    where
193        <T as ConstMachineWord>::ConstDoubleWord: [c0nst] PrimInt,
194    {
195        type Unsigned = FixedUInt<T, N, P>;
196        type Output = FixedUInt<T, N, P>;
197        fn carrying_mul(self, rhs: Self, carry: Self) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
198            <FixedUInt<T, N, P> as CarryingMul>::carrying_mul(FixedUInt::from_array(self.array), FixedUInt::from_array(rhs.array), FixedUInt::from_array(carry.array))
199        }
200        fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>) {
201            <FixedUInt<T, N, P> as CarryingMul>::carrying_mul_add(FixedUInt::from_array(self.array), FixedUInt::from_array(rhs.array), FixedUInt::from_array(addend.array), FixedUInt::from_array(carry.array))
202        }
203    }
204}
205
206#[cfg(test)]
207mod tests {
208    use super::*;
209
210    type U16 = FixedUInt<u8, 2>;
211    type U32 = FixedUInt<u8, 4>;
212
213    c0nst::c0nst! {
214        pub c0nst fn const_carrying_add<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
215            a: FixedUInt<T, N, P>,
216            b: FixedUInt<T, N, P>,
217            carry: bool,
218        ) -> (FixedUInt<T, N, P>, bool) {
219            CarryingAdd::carrying_add(a, b, carry)
220        }
221
222        pub c0nst fn const_borrowing_sub<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
223            a: FixedUInt<T, N, P>,
224            b: FixedUInt<T, N, P>,
225            borrow: bool,
226        ) -> (FixedUInt<T, N, P>, bool) {
227            BorrowingSub::borrowing_sub(a, b, borrow)
228        }
229
230        /// Full `(low, high)` product via `CarryingMul` with a zero
231        /// carry — `FixedUInt` doesn't implement `WideningMul`.
232        pub c0nst fn const_widening_mul<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
233            a: FixedUInt<T, N, P>,
234            b: FixedUInt<T, N, P>,
235        ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>)
236        where
237            <T as ConstMachineWord>::ConstDoubleWord: [c0nst] PrimInt,
238        {
239            CarryingMul::carrying_mul(a, b, <FixedUInt<T, N, P> as Zero>::zero())
240        }
241
242        pub c0nst fn const_carrying_mul<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
243            a: FixedUInt<T, N, P>,
244            b: FixedUInt<T, N, P>,
245            carry: FixedUInt<T, N, P>,
246        ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>)
247        where
248            <T as ConstMachineWord>::ConstDoubleWord: [c0nst] PrimInt,
249        {
250            CarryingMul::carrying_mul(a, b, carry)
251        }
252
253        pub c0nst fn const_carrying_mul_add<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
254            a: FixedUInt<T, N, P>,
255            b: FixedUInt<T, N, P>,
256            addend: FixedUInt<T, N, P>,
257            carry: FixedUInt<T, N, P>,
258        ) -> (FixedUInt<T, N, P>, FixedUInt<T, N, P>)
259        where
260            <T as ConstMachineWord>::ConstDoubleWord: [c0nst] PrimInt,
261        {
262            CarryingMul::carrying_mul_add(a, b, addend, carry)
263        }
264    }
265
266    #[test]
267    fn test_carrying_add_no_carry() {
268        let a = U16::from(100u8);
269        let b = U16::from(50u8);
270
271        // Without carry in
272        let (sum, carry_out) = const_carrying_add(a, b, false);
273        assert_eq!(sum, U16::from(150u8));
274        assert!(!carry_out);
275
276        // With carry in
277        let (sum, carry_out) = const_carrying_add(a, b, true);
278        assert_eq!(sum, U16::from(151u8));
279        assert!(!carry_out);
280    }
281
282    #[test]
283    fn test_carrying_add_with_overflow() {
284        let max = U16::from(0xFFFFu16);
285        let one = U16::from(1u8);
286
287        // max + 0 with carry = max + 1 = 0 with carry out
288        let (sum, carry_out) = const_carrying_add(max, U16::from(0u8), true);
289        assert_eq!(sum, U16::from(0u8));
290        assert!(carry_out);
291
292        // max + 1 = 0 with carry out
293        let (sum, carry_out) = const_carrying_add(max, one, false);
294        assert_eq!(sum, U16::from(0u8));
295        assert!(carry_out);
296
297        // max + max = 0xFFFE with carry out
298        let (sum, carry_out) = const_carrying_add(max, max, false);
299        assert_eq!(sum, U16::from(0xFFFEu16));
300        assert!(carry_out);
301    }
302
303    #[test]
304    fn test_borrowing_sub_no_borrow() {
305        let a = U16::from(150u8);
306        let b = U16::from(50u8);
307
308        // Without borrow in
309        let (diff, borrow_out) = const_borrowing_sub(a, b, false);
310        assert_eq!(diff, U16::from(100u8));
311        assert!(!borrow_out);
312
313        // With borrow in
314        let (diff, borrow_out) = const_borrowing_sub(a, b, true);
315        assert_eq!(diff, U16::from(99u8));
316        assert!(!borrow_out);
317    }
318
319    #[test]
320    fn test_borrowing_sub_with_underflow() {
321        let zero = U16::from(0u8);
322        let one = U16::from(1u8);
323
324        // 0 - 1 = 0xFFFF with borrow out
325        let (diff, borrow_out) = const_borrowing_sub(zero, one, false);
326        assert_eq!(diff, U16::from(0xFFFFu16));
327        assert!(borrow_out);
328
329        // 0 - 0 with borrow = 0xFFFF with borrow out
330        let (diff, borrow_out) = const_borrowing_sub(zero, zero, true);
331        assert_eq!(diff, U16::from(0xFFFFu16));
332        assert!(borrow_out);
333
334        // 1 - 1 with borrow = 0xFFFF with borrow out
335        let (diff, borrow_out) = const_borrowing_sub(one, one, true);
336        assert_eq!(diff, U16::from(0xFFFFu16));
337        assert!(borrow_out);
338    }
339
340    #[test]
341    fn test_widening_mul() {
342        // 100 * 100 = 10000 (fits in 16 bits, high = 0)
343        let a = U16::from(100u8);
344        let (lo, hi) = const_widening_mul(a, a);
345        assert_eq!(lo, U16::from(10000u16));
346        assert_eq!(hi, U16::from(0u8));
347
348        // 256 * 256 = 65536 = 0x10000 (low = 0, high = 1)
349        let b = U16::from(256u16);
350        let (lo, hi) = const_widening_mul(b, b);
351        assert_eq!(lo, U16::from(0u8));
352        assert_eq!(hi, U16::from(1u8));
353
354        // 0xFFFF * 0xFFFF = 0xFFFE0001
355        let max = U16::from(0xFFFFu16);
356        let (lo, hi) = const_widening_mul(max, max);
357        assert_eq!(lo, U16::from(0x0001u16)); // low 16 bits of 0xFFFE0001
358        assert_eq!(hi, U16::from(0xFFFEu16)); // high 16 bits of 0xFFFE0001
359    }
360
361    #[test]
362    fn test_widening_mul_larger() {
363        // Test with 32-bit type (U32 = FixedUInt<u8, 4>)
364        let a = U32::from(0x10000u32); // 2^16
365        let b = U32::from(0x10000u32); // 2^16
366        let (lo, hi) = const_widening_mul(a, b);
367        // 2^16 * 2^16 = 2^32 = 0x100000000
368        // low 32 bits = 0, high 32 bits = 1
369        assert_eq!(lo, U32::from(0u8));
370        assert_eq!(hi, U32::from(1u8));
371    }
372
373    #[test]
374    fn test_carrying_mul() {
375        let a = U16::from(100u8);
376        let b = U16::from(100u8);
377        let carry = U16::from(5u8);
378
379        // 100 * 100 + 5 = 10005
380        let (lo, hi) = const_carrying_mul(a, b, carry);
381        assert_eq!(lo, U16::from(10005u16));
382        assert_eq!(hi, U16::from(0u8));
383
384        // With larger carry that causes overflow in low part
385        let max = U16::from(0xFFFFu16);
386        let one = U16::from(1u8);
387        // 1 * 1 + 0xFFFF = 0x10000 = (0, 1)
388        let (lo, hi) = const_carrying_mul(one, one, max);
389        assert_eq!(lo, U16::from(0u8));
390        assert_eq!(hi, U16::from(1u8));
391    }
392
393    #[test]
394    fn test_carrying_mul_add() {
395        let a = U16::from(100u8);
396        let b = U16::from(100u8);
397        let addend = U16::from(10u8);
398        let carry = U16::from(5u8);
399
400        // 100 * 100 + 10 + 5 = 10015
401        let (lo, hi) = const_carrying_mul_add(a, b, addend, carry);
402        assert_eq!(lo, U16::from(10015u16));
403        assert_eq!(hi, U16::from(0u8));
404    }
405
406    #[test]
407    fn test_carrying_mul_add_double_overflow() {
408        // Test case where both addend and carry cause overflow
409        let max = U16::from(0xFFFFu16);
410        let one = U16::from(1u8);
411
412        // 1 * 1 + 0xFFFF + 0xFFFF = 1 + 0x1FFFE = 0x1FFFF = (0xFFFF, 1)
413        let (lo, hi) = const_carrying_mul_add(one, one, max, max);
414        assert_eq!(lo, U16::from(0xFFFFu16));
415        assert_eq!(hi, U16::from(1u8));
416    }
417
418    #[test]
419    fn test_const_context() {
420        #[cfg(feature = "nightly")]
421        {
422            const A: U16 = FixedUInt::from_array([100, 0]);
423            const B: U16 = FixedUInt::from_array([50, 0]);
424
425            // Test carrying_add in const context
426            const ADD_RESULT: (U16, bool) = const_carrying_add(A, B, false);
427            assert_eq!(ADD_RESULT.0, U16::from(150u8));
428            assert!(!ADD_RESULT.1);
429
430            const ADD_WITH_CARRY: (U16, bool) = const_carrying_add(A, B, true);
431            assert_eq!(ADD_WITH_CARRY.0, U16::from(151u8));
432
433            // Test borrowing_sub in const context
434            const SUB_RESULT: (U16, bool) = const_borrowing_sub(A, B, false);
435            assert_eq!(SUB_RESULT.0, U16::from(50u8));
436            assert!(!SUB_RESULT.1);
437
438            // Test widening_mul in const context
439            const C: U16 = FixedUInt::from_array([0, 1]); // 256
440            const MUL_RESULT: (U16, U16) = const_widening_mul(C, C);
441            assert_eq!(MUL_RESULT.0, U16::from(0u8)); // 256*256 = 65536, low = 0
442            assert_eq!(MUL_RESULT.1, U16::from(1u8)); // high = 1
443        }
444    }
445
446    /// Polymorphic test: verify widening_mul produces identical results across
447    /// different word layouts for the same values.
448    #[test]
449    fn test_widening_mul_polymorphic() {
450        // Generic test function following crate pattern
451        fn test_widening<T>(a: T, b: T, expected_lo: T, expected_hi: T)
452        where
453            T: CarryingMul<Unsigned = T, Output = T>
454                + CarryingAdd
455                + BorrowingSub
456                + Eq
457                + core::fmt::Debug
458                + Copy
459                + Zero,
460        {
461            let (lo, hi) = CarryingMul::carrying_mul(a, b, <T as Zero>::zero());
462            assert_eq!(lo, expected_lo, "lo mismatch");
463            assert_eq!(hi, expected_hi, "hi mismatch");
464        }
465
466        // Test 1: 256 * 256 = 65536
467        // As u16 (FixedUInt<u8, 2>): 16-bit overflow, 256*256 = 0x10000 = (lo=0, hi=1)
468        test_widening(
469            U16::from(256u16),
470            U16::from(256u16),
471            U16::from(0u16),
472            U16::from(1u16),
473        );
474
475        // As u32 (FixedUInt<u8, 4>): fits in 32 bits, so lo=65536, hi=0
476        test_widening(
477            U32::from(256u32),
478            U32::from(256u32),
479            U32::from(65536u32),
480            U32::from(0u32),
481        );
482
483        // Test 2: 0xFFFF * 0xFFFF = 0xFFFE0001
484        test_widening(
485            U16::from(0xFFFFu16),
486            U16::from(0xFFFFu16),
487            U16::from(0x0001u16),
488            U16::from(0xFFFEu16),
489        );
490
491        // Test 3: 0xFFFFFFFF * 2 = 0x1_FFFFFFFE (tests carry across word boundary)
492        test_widening(
493            U32::from(0xFFFFFFFFu32),
494            U32::from(2u32),
495            U32::from(0xFFFFFFFEu32),
496            U32::from(1u32),
497        );
498    }
499
500    /// Polymorphic test for carrying_mul_add with edge cases.
501    #[test]
502    fn test_carrying_mul_add_polymorphic() {
503        fn test_cma<T>(a: T, b: T, addend: T, carry: T, expected_lo: T, expected_hi: T)
504        where
505            T: CarryingMul<Unsigned = T, Output = T> + Eq + core::fmt::Debug + Copy,
506        {
507            let (lo, hi) = CarryingMul::carrying_mul_add(a, b, addend, carry);
508            assert_eq!(lo, expected_lo, "lo mismatch");
509            assert_eq!(hi, expected_hi, "hi mismatch");
510        }
511
512        // Test: max * max + max + max = 0xFFFF * 0xFFFF + 0xFFFF + 0xFFFF
513        //     = 0xFFFE0001 + 0x1FFFE = 0xFFFFFFFF
514        // lo = 0xFFFF, hi = 0xFFFF
515        let max16 = U16::from(0xFFFFu16);
516        test_cma(
517            max16,
518            max16,
519            max16,
520            max16,
521            U16::from(0xFFFFu16),
522            U16::from(0xFFFFu16),
523        );
524
525        // Same test with different layout (U32 = FixedUInt<u8, 4>)
526        let max32 = U32::from(0xFFFFFFFFu32);
527        let zero32 = U32::from(0u32);
528        // max * 1 + 0 + max = max + max = 2*max = 0x1_FFFFFFFE
529        test_cma(
530            max32,
531            U32::from(1u32),
532            zero32,
533            max32,
534            U32::from(0xFFFFFFFEu32),
535            U32::from(1u32),
536        );
537    }
538
539    /// `CarryingMul::carrying_mul` full-product on primitives and FixedUInt.
540    #[test]
541    fn test_carrying_mul_full_product() {
542        assert_eq!(CarryingMul::carrying_mul(255u8, 255u8, 0u8), (1, 254)); // 0xFE01
543        assert_eq!(
544            CarryingMul::carrying_mul(0xFFFFu16, 0xFFFFu16, 0u16),
545            (0x0001, 0xFFFE)
546        );
547        assert_eq!(
548            CarryingMul::carrying_mul(0xFFFF_FFFFu32, 2u32, 0u32),
549            (0xFFFF_FFFE, 1)
550        );
551        assert_eq!(
552            CarryingMul::carrying_mul(0xFFFF_FFFF_FFFF_FFFFu64, 2u64, 0u64),
553            (0xFFFF_FFFF_FFFF_FFFE, 1)
554        );
555
556        let a = U16::from(0xFFFFu16);
557        let (lo, hi) = CarryingMul::carrying_mul(a, a, <U16 as Zero>::zero());
558        assert_eq!(lo, U16::from(0x0001u16));
559        assert_eq!(hi, U16::from(0xFFFEu16));
560    }
561
562    /// `CarryingMul::carrying_mul` / `carrying_mul_add` for primitives and
563    /// FixedUInt, cross-checked against the free const-fn path.
564    #[test]
565    fn test_carrying_mul_trait() {
566        assert_eq!(CarryingMul::carrying_mul(10u8, 10u8, 5u8), (105, 0));
567        assert_eq!(CarryingMul::carrying_mul(255u8, 255u8, 255u8), (0, 255));
568        assert_eq!(
569            CarryingMul::carrying_mul_add(10u8, 10u8, 3u8, 2u8),
570            (105, 0)
571        );
572        assert_eq!(
573            CarryingMul::carrying_mul_add(255u8, 255u8, 255u8, 255u8),
574            (255, 255)
575        );
576
577        let a = U16::from(100u8);
578        let b = U16::from(100u8);
579        let carry = U16::from(5u8);
580        let (lo, hi) = CarryingMul::carrying_mul(a, b, carry);
581        assert_eq!(lo, U16::from(10005u16));
582        assert_eq!(hi, U16::from(0u8));
583
584        // Trait method and free const-fn must agree on FixedUInt.
585        let x = U32::from(0x1234u32);
586        let y = U32::from(0x5678u32);
587        let c = U32::from(0xABCDu32);
588        assert_eq!(
589            CarryingMul::carrying_mul(x, y, c),
590            const_carrying_mul(x, y, c),
591        );
592        let addend = U32::from(0x9999u32);
593        assert_eq!(
594            CarryingMul::carrying_mul_add(x, y, addend, c),
595            const_carrying_mul_add(x, y, addend, c),
596        );
597    }
598}
fixed_bigint/fixeduint/extended_precision_impl.rs

fixed_bigint/fixeduint/
extended_precision_impl.rs
