libm/math/support/
big.rs

Help
1//! Integers used for wide operations, larger than `u128`.
2
3#[cfg(test)]
4mod tests;
5
6use core::ops;
7
8use super::{DInt, HInt, Int, MinInt};
9
10const U128_LO_MASK: u128 = u64::MAX as u128;
11
12/// A 256-bit unsigned integer represented as two 128-bit native-endian limbs.
13#[allow(non_camel_case_types)]
14#[derive(Clone, Copy, Debug, PartialEq, PartialOrd)]
15pub struct u256 {
16    pub lo: u128,
17    pub hi: u128,
18}
19
20impl u256 {
21    #[cfg(any(test, feature = "unstable-public-internals"))]
22    pub const MAX: Self = Self {
23        lo: u128::MAX,
24        hi: u128::MAX,
25    };
26
27    /// Reinterpret as a signed integer
28    pub fn signed(self) -> i256 {
29        i256 {
30            lo: self.lo,
31            hi: self.hi,
32        }
33    }
34}
35
36/// A 256-bit signed integer represented as two 128-bit native-endian limbs.
37#[allow(non_camel_case_types)]
38#[derive(Clone, Copy, Debug, PartialEq, PartialOrd)]
39pub struct i256 {
40    pub lo: u128,
41    pub hi: u128,
42}
43
44impl i256 {
45    /// Reinterpret as an unsigned integer
46    #[cfg(any(test, feature = "unstable-public-internals"))]
47    pub fn unsigned(self) -> u256 {
48        u256 {
49            lo: self.lo,
50            hi: self.hi,
51        }
52    }
53}
54
55impl MinInt for u256 {
56    type OtherSign = i256;
57
58    type Unsigned = u256;
59
60    const SIGNED: bool = false;
61    const BITS: u32 = 256;
62    const ZERO: Self = Self { lo: 0, hi: 0 };
63    const ONE: Self = Self { lo: 1, hi: 0 };
64    const MIN: Self = Self { lo: 0, hi: 0 };
65    const MAX: Self = Self {
66        lo: u128::MAX,
67        hi: u128::MAX,
68    };
69}
70
71impl MinInt for i256 {
72    type OtherSign = u256;
73
74    type Unsigned = u256;
75
76    const SIGNED: bool = false;
77    const BITS: u32 = 256;
78    const ZERO: Self = Self { lo: 0, hi: 0 };
79    const ONE: Self = Self { lo: 1, hi: 0 };
80    const MIN: Self = Self {
81        lo: 0,
82        hi: 1 << 127,
83    };
84    const MAX: Self = Self {
85        lo: u128::MAX,
86        hi: u128::MAX << 1,
87    };
88}
89
90macro_rules! impl_common {
91    ($ty:ty) => {
92        impl ops::BitOr for $ty {
93            type Output = Self;
94
95            fn bitor(mut self, rhs: Self) -> Self::Output {
96                self.lo |= rhs.lo;
97                self.hi |= rhs.hi;
98                self
99            }
100        }
101
102        impl ops::Not for $ty {
103            type Output = Self;
104
105            fn not(mut self) -> Self::Output {
106                self.lo = !self.lo;
107                self.hi = !self.hi;
108                self
109            }
110        }
111
112        impl ops::Shl<u32> for $ty {
113            type Output = Self;
114
115            fn shl(self, _rhs: u32) -> Self::Output {
116                unimplemented!("only used to meet trait bounds")
117            }
118        }
119    };
120}
121
122impl_common!(i256);
123impl_common!(u256);
124
125impl ops::Add<Self> for u256 {
126    type Output = Self;
127
128    fn add(self, rhs: Self) -> Self::Output {
129        let (lo, carry) = self.lo.overflowing_add(rhs.lo);
130        let hi = self.hi.wrapping_add(carry as u128).wrapping_add(rhs.hi);
131
132        Self { lo, hi }
133    }
134}
135
136impl ops::Shr<u32> for u256 {
137    type Output = Self;
138
139    fn shr(mut self, rhs: u32) -> Self::Output {
140        debug_assert!(rhs < Self::BITS, "attempted to shift right with overflow");
141        if rhs >= Self::BITS {
142            return Self::ZERO;
143        }
144
145        if rhs == 0 {
146            return self;
147        }
148
149        if rhs < 128 {
150            self.lo >>= rhs;
151            self.lo |= self.hi << (128 - rhs);
152        } else {
153            self.lo = self.hi >> (rhs - 128);
154        }
155
156        if rhs < 128 {
157            self.hi >>= rhs;
158        } else {
159            self.hi = 0;
160        }
161
162        self
163    }
164}
165
166impl HInt for u128 {
167    type D = u256;
168
169    fn widen(self) -> Self::D {
170        u256 { lo: self, hi: 0 }
171    }
172
173    fn zero_widen(self) -> Self::D {
174        self.widen()
175    }
176
177    fn zero_widen_mul(self, rhs: Self) -> Self::D {
178        let l0 = self & U128_LO_MASK;
179        let l1 = rhs & U128_LO_MASK;
180        let h0 = self >> 64;
181        let h1 = rhs >> 64;
182
183        let p_ll: u128 = l0.overflowing_mul(l1).0;
184        let p_lh: u128 = l0.overflowing_mul(h1).0;
185        let p_hl: u128 = h0.overflowing_mul(l1).0;
186        let p_hh: u128 = h0.overflowing_mul(h1).0;
187
188        let s0 = p_hl + (p_ll >> 64);
189        let s1 = (p_ll & U128_LO_MASK) + (s0 << 64);
190        let s2 = p_lh + (s1 >> 64);
191
192        let lo = (p_ll & U128_LO_MASK) + (s2 << 64);
193        let hi = p_hh + (s0 >> 64) + (s2 >> 64);
194
195        u256 { lo, hi }
196    }
197
198    fn widen_mul(self, rhs: Self) -> Self::D {
199        self.zero_widen_mul(rhs)
200    }
201
202    fn widen_hi(self) -> Self::D {
203        self.widen() << <Self as MinInt>::BITS
204    }
205}
206
207impl HInt for i128 {
208    type D = i256;
209
210    fn widen(self) -> Self::D {
211        let mut ret = self.unsigned().zero_widen().signed();
212        if self.is_negative() {
213            ret.hi = u128::MAX;
214        }
215        ret
216    }
217
218    fn zero_widen(self) -> Self::D {
219        self.unsigned().zero_widen().signed()
220    }
221
222    fn zero_widen_mul(self, rhs: Self) -> Self::D {
223        self.unsigned().zero_widen_mul(rhs.unsigned()).signed()
224    }
225
226    fn widen_mul(self, _rhs: Self) -> Self::D {
227        unimplemented!("signed i128 widening multiply is not used")
228    }
229
230    fn widen_hi(self) -> Self::D {
231        self.widen() << <Self as MinInt>::BITS
232    }
233}
234
235impl DInt for u256 {
236    type H = u128;
237
238    fn lo(self) -> Self::H {
239        self.lo
240    }
241
242    fn hi(self) -> Self::H {
243        self.hi
244    }
245}
246
247impl DInt for i256 {
248    type H = i128;
249
250    fn lo(self) -> Self::H {
251        self.lo as i128
252    }
253
254    fn hi(self) -> Self::H {
255        self.hi as i128
256    }
257}
libm/math/support/big.rs

libm/math/support/
big.rs
