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