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

fixed_bigint/fixeduint/
extended_precision_impl.rs
