fixed_bigint/
patch_num_traits.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// These should be in num_traits
16pub trait OverflowingShl: Sized {
17    fn overflowing_shl(self, rhs: u32) -> (Self, bool);
18}
19pub trait OverflowingShr: Sized {
20    fn overflowing_shr(self, rhs: u32) -> (Self, bool);
21}
22
23macro_rules! overflowing_shift_impl {
24    ($trait_name:ident, $method:ident, $t:ty) => {
25        impl $trait_name for $t {
26            #[inline]
27            fn $method(self, rhs: u32) -> ($t, bool) {
28                <$t>::$method(self, rhs)
29            }
30        }
31    };
32}
33
34overflowing_shift_impl!(OverflowingShl, overflowing_shl, u8);
35overflowing_shift_impl!(OverflowingShl, overflowing_shl, u16);
36overflowing_shift_impl!(OverflowingShl, overflowing_shl, u32);
37overflowing_shift_impl!(OverflowingShl, overflowing_shl, u64);
38
39overflowing_shift_impl!(OverflowingShr, overflowing_shr, u8);
40overflowing_shift_impl!(OverflowingShr, overflowing_shr, u16);
41overflowing_shift_impl!(OverflowingShr, overflowing_shr, u32);
42overflowing_shift_impl!(OverflowingShr, overflowing_shr, u64);
43
44/// Widening multiplication for extended precision arithmetic.
45///
46/// Multiplies two values and returns the full double-width result as (low, high).
47/// This is the non-const version that delegates to [`ConstWideningMul`] implementations.
48///
49/// [`ConstWideningMul`]: crate::const_numtraits::ConstWideningMul
50pub trait WideningMul: Sized {
51    /// Calculates the complete product `self * rhs` without overflow.
52    ///
53    /// Returns `(low, high)` where the full result is `high * 2^BITS + low`.
54    fn widening_mul(self, rhs: Self) -> (Self, Self);
55}
56
57macro_rules! widening_mul_impl {
58    ($t:ty, $double:ty, $bits:expr) => {
59        impl WideningMul for $t {
60            #[inline]
61            fn widening_mul(self, rhs: Self) -> (Self, Self) {
62                let product = (self as $double) * (rhs as $double);
63                (product as $t, (product >> $bits) as $t)
64            }
65        }
66    };
67}
68
69widening_mul_impl!(u8, u16, 8);
70widening_mul_impl!(u16, u32, 16);
71widening_mul_impl!(u32, u64, 32);
72widening_mul_impl!(u64, u128, 64);
73
74/// Carrying multiplication for extended precision arithmetic.
75///
76/// Provides multiply-accumulate operations returning double-width results.
77/// This is the non-const version that delegates to [`ConstCarryingMul`] implementations.
78///
79/// [`ConstCarryingMul`]: crate::const_numtraits::ConstCarryingMul
80pub trait CarryingMul: Sized {
81    /// Calculates `self * rhs + carry`, returning `(low, high)`.
82    ///
83    /// The result fits in double-width (2 * BITS) since
84    /// `MAX * MAX + MAX < (MAX+1)^2 = 2^(2*BITS)`.
85    fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);
86
87    /// Calculates `self * rhs + addend + carry`, returning `(low, high)`.
88    ///
89    /// The result fits in double-width (2 * BITS) since
90    /// `MAX * MAX + MAX + MAX < (MAX+1)^2 = 2^(2*BITS)`.
91    fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self);
92}
93
94macro_rules! carrying_mul_impl {
95    ($t:ty, $double:ty, $bits:expr) => {
96        impl CarryingMul for $t {
97            #[inline]
98            fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
99                let product = (self as $double) * (rhs as $double) + (carry as $double);
100                (product as $t, (product >> $bits) as $t)
101            }
102
103            #[inline]
104            fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self) {
105                let product =
106                    (self as $double) * (rhs as $double) + (addend as $double) + (carry as $double);
107                (product as $t, (product >> $bits) as $t)
108            }
109        }
110    };
111}
112
113carrying_mul_impl!(u8, u16, 8);
114carrying_mul_impl!(u16, u32, 16);
115carrying_mul_impl!(u32, u64, 32);
116carrying_mul_impl!(u64, u128, 64);
fixed_bigint/patch_num_traits.rs

fixed_bigint/
patch_num_traits.rs
