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, Eq, Ord)]
15pub struct u256 {
16 pub hi: u128,
17 pub lo: 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 as i128,
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, Eq, Ord)]
39pub struct i256 {
40 pub hi: i128,
41 pub lo: 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 as u128,
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 = true;
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: u128::MIN,
82 hi: i128::MIN,
83 };
84 const MAX: Self = Self {
85 lo: u128::MAX,
86 hi: i128::MAX,
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::Add<Self> for $ty {
113 type Output = Self;
114
115 fn add(self, rhs: Self) -> Self::Output {
116 let (lo, carry) = self.lo.overflowing_add(rhs.lo);
117 let (hi, of) = Int::carrying_add(self.hi, rhs.hi, carry);
118 debug_assert!(!of, "attempt to add with overflow");
119 Self { lo, hi }
120 }
121 }
122
123 impl ops::Sub<Self> for $ty {
124 type Output = Self;
125
126 fn sub(self, rhs: Self) -> Self::Output {
127 let (lo, borrow) = self.lo.overflowing_sub(rhs.lo);
128 let (hi, of) = Int::borrowing_sub(self.hi, rhs.hi, borrow);
129 debug_assert!(!of, "attempt to subtract with overflow");
130 Self { lo, hi }
131 }
132 }
133
134 impl ops::Shl<u32> for $ty {
135 type Output = Self;
136
137 fn shl(mut self, rhs: u32) -> Self::Output {
138 debug_assert!(rhs < Self::BITS, "attempt to shift left with overflow");
139
140 let half_bits = Self::BITS / 2;
141 let low_mask = half_bits - 1;
142 let s = rhs & low_mask;
143
144 let lo = self.lo;
145 let hi = self.hi;
146
147 self.lo = lo << s;
148
149 if rhs & half_bits == 0 {
150 self.hi = (lo >> (low_mask ^ s) >> 1) as _;
151 self.hi |= hi << s;
152 } else {
153 self.hi = self.lo as _;
154 self.lo = 0;
155 }
156 self
157 }
158 }
159
160 impl ops::Shr<u32> for $ty {
161 type Output = Self;
162
163 fn shr(mut self, rhs: u32) -> Self::Output {
164 debug_assert!(rhs < Self::BITS, "attempt to shift right with overflow");
165
166 let half_bits = Self::BITS / 2;
167 let low_mask = half_bits - 1;
168 let s = rhs & low_mask;
169
170 let lo = self.lo;
171 let hi = self.hi;
172
173 self.hi = hi >> s;
174
175 #[allow(unused_comparisons)]
176 if rhs & half_bits == 0 {
177 self.lo = (hi << (low_mask ^ s) << 1) as _;
178 self.lo |= lo >> s;
179 } else {
180 self.lo = self.hi as _;
181 self.hi = if hi < 0 { !0 } else { 0 };
182 }
183 self
184 }
185 }
186 };
187}
188
189impl_common!(i256);
190impl_common!(u256);
191
192impl HInt for u128 {
193 type D = u256;
194
195 fn widen(self) -> Self::D {
196 u256 { lo: self, hi: 0 }
197 }
198
199 fn zero_widen(self) -> Self::D {
200 self.widen()
201 }
202
203 fn zero_widen_mul(self, rhs: Self) -> Self::D {
204 let l0 = self & U128_LO_MASK;
205 let l1 = rhs & U128_LO_MASK;
206 let h0 = self >> 64;
207 let h1 = rhs >> 64;
208
209 let p_ll: u128 = l0.overflowing_mul(l1).0;
210 let p_lh: u128 = l0.overflowing_mul(h1).0;
211 let p_hl: u128 = h0.overflowing_mul(l1).0;
212 let p_hh: u128 = h0.overflowing_mul(h1).0;
213
214 let s0 = p_hl + (p_ll >> 64);
215 let s1 = (p_ll & U128_LO_MASK) + (s0 << 64);
216 let s2 = p_lh + (s1 >> 64);
217
218 let lo = (p_ll & U128_LO_MASK) + (s2 << 64);
219 let hi = p_hh + (s0 >> 64) + (s2 >> 64);
220
221 u256 { lo, hi }
222 }
223
224 fn widen_mul(self, rhs: Self) -> Self::D {
225 self.zero_widen_mul(rhs)
226 }
227
228 fn widen_hi(self) -> Self::D {
229 u256 { lo: 0, hi: self }
230 }
231}
232
233impl HInt for i128 {
234 type D = i256;
235
236 fn widen(self) -> Self::D {
237 i256 {
238 lo: self as u128,
239 hi: if self < 0 { -1 } else { 0 },
240 }
241 }
242
243 fn zero_widen(self) -> Self::D {
244 self.unsigned().zero_widen().signed()
245 }
246
247 fn zero_widen_mul(self, rhs: Self) -> Self::D {
248 self.unsigned().zero_widen_mul(rhs.unsigned()).signed()
249 }
250
251 fn widen_mul(self, _rhs: Self) -> Self::D {
252 unimplemented!("signed i128 widening multiply is not used")
253 }
254
255 fn widen_hi(self) -> Self::D {
256 i256 { lo: 0, hi: self }
257 }
258}
259
260impl DInt for u256 {
261 type H = u128;
262
263 fn lo(self) -> Self::H {
264 self.lo
265 }
266
267 fn hi(self) -> Self::H {
268 self.hi
269 }
270}
271
272impl DInt for i256 {
273 type H = i128;
274
275 fn lo(self) -> Self::H {
276 self.lo as i128
277 }
278
279 fn hi(self) -> Self::H {
280 self.hi
281 }
282}
283