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: u128, carry: bool) = self.lo.overflowing_add(rhs.lo);
130 let hi: u128 = 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}
258