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    type Output;
52    /// Calculates the complete product `self * rhs` without overflow.
53    ///
54    /// Returns `(low, high)` where the full result is `high * 2^BITS + low`.
55    fn widening_mul(self, rhs: Self) -> (Self::Output, Self::Output);
56}
57
58macro_rules! widening_mul_impl {
59    ($t:ty, $double:ty, $bits:expr) => {
60        impl WideningMul for $t {
61            type Output = Self;
62            fn widening_mul(self, rhs: Self) -> (Self, Self) {
63                let product = (self as $double) * (rhs as $double);
64                (product as $t, (product >> $bits) as $t)
65            }
66        }
67        impl WideningMul for &$t {
68            type Output = $t;
69            fn widening_mul(self, rhs: Self) -> ($t, $t) {
70                <$t as WideningMul>::widening_mul(*self, *rhs)
71            }
72        }
73    };
74}
75
76widening_mul_impl!(u8, u16, 8);
77widening_mul_impl!(u16, u32, 16);
78widening_mul_impl!(u32, u64, 32);
79widening_mul_impl!(u64, u128, 64);
80
81/// Carrying multiplication for extended precision arithmetic.
82///
83/// Provides multiply-accumulate operations returning double-width results.
84/// This is the non-const version that delegates to [`ConstCarryingMul`] implementations.
85///
86/// [`ConstCarryingMul`]: crate::const_numtraits::ConstCarryingMul
87pub trait CarryingMul: Sized {
88    type Output;
89    /// Calculates `self * rhs + carry`, returning `(low, high)`.
90    ///
91    /// The result fits in double-width (2 * BITS) since
92    /// `MAX * MAX + MAX < (MAX+1)^2 = 2^(2*BITS)`.
93    fn carrying_mul(self, rhs: Self, carry: Self) -> (Self::Output, Self::Output);
94
95    /// Calculates `self * rhs + addend + carry`, returning `(low, high)`.
96    ///
97    /// The result fits in double-width (2 * BITS) since
98    /// `MAX * MAX + MAX + MAX < (MAX+1)^2 = 2^(2*BITS)`.
99    fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self)
100        -> (Self::Output, Self::Output);
101}
102
103macro_rules! carrying_mul_impl {
104    ($t:ty, $double:ty, $bits:expr) => {
105        impl CarryingMul for $t {
106            type Output = Self;
107            fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
108                let product = (self as $double) * (rhs as $double) + (carry as $double);
109                (product as $t, (product >> $bits) as $t)
110            }
111
112            fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self) {
113                let product =
114                    (self as $double) * (rhs as $double) + (addend as $double) + (carry as $double);
115                (product as $t, (product >> $bits) as $t)
116            }
117        }
118        impl CarryingMul for &$t {
119            type Output = $t;
120            fn carrying_mul(self, rhs: Self, carry: Self) -> ($t, $t) {
121                <$t as CarryingMul>::carrying_mul(*self, *rhs, *carry)
122            }
123            fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> ($t, $t) {
124                <$t as CarryingMul>::carrying_mul_add(*self, *rhs, *addend, *carry)
125            }
126        }
127    };
128}
129
130carrying_mul_impl!(u8, u16, 8);
131carrying_mul_impl!(u16, u32, 16);
132carrying_mul_impl!(u32, u64, 32);
133carrying_mul_impl!(u64, u128, 64);
fixed_bigint/patch_num_traits.rs

fixed_bigint/
patch_num_traits.rs
