1//! Integers used for wide operations, larger than `u128`.
2
3#![allow(unused)]
4
5use crate::int::{DInt, HInt, Int, MinInt};
6use core::{fmt, ops};
7
8const WORD_LO_MASK: u64 = 0x00000000ffffffff;
9const WORD_HI_MASK: u64 = 0xffffffff00000000;
10const WORD_FULL_MASK: u64 = 0xffffffffffffffff;
11const U128_LO_MASK: u128 = u64::MAX as u128;
12const U128_HI_MASK: u128 = (u64::MAX as u128) << 64;
13
14/// A 256-bit unsigned integer represented as 4 64-bit limbs.
15///
16/// Each limb is a native-endian number, but the array is little-limb-endian.
17#[allow(non_camel_case_types)]
18#[derive(Clone, Copy, Debug, PartialEq, PartialOrd)]
19pub struct u256(pub [u64; 4]);
20
21impl u256 {
22 pub const MAX: Self = Self([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
23
24 /// Reinterpret as a signed integer
25 pub fn signed(self) -> i256 {
26 i256(self.0)
27 }
28}
29
30/// A 256-bit signed integer represented as 4 64-bit limbs.
31///
32/// Each limb is a native-endian number, but the array is little-limb-endian.
33#[allow(non_camel_case_types)]
34#[derive(Clone, Copy, Debug, PartialEq, PartialOrd)]
35pub struct i256(pub [u64; 4]);
36
37impl i256 {
38 /// Reinterpret as an unsigned integer
39 pub fn unsigned(self) -> u256 {
40 u256(self.0)
41 }
42}
43
44impl MinInt for u256 {
45 type OtherSign = i256;
46
47 type UnsignedInt = u256;
48
49 const SIGNED: bool = false;
50 const BITS: u32 = 256;
51 const ZERO: Self = Self([0u64; 4]);
52 const ONE: Self = Self([1, 0, 0, 0]);
53 const MIN: Self = Self([0u64; 4]);
54 const MAX: Self = Self([u64::MAX; 4]);
55}
56
57impl MinInt for i256 {
58 type OtherSign = u256;
59
60 type UnsignedInt = u256;
61
62 const SIGNED: bool = false;
63 const BITS: u32 = 256;
64 const ZERO: Self = Self([0u64; 4]);
65 const ONE: Self = Self([1, 0, 0, 0]);
66 const MIN: Self = Self([0, 0, 0, 1 << 63]);
67 const MAX: Self = Self([u64::MAX, u64::MAX, u64::MAX, u64::MAX << 1]);
68}
69
70macro_rules! impl_common {
71 ($ty:ty) => {
72 impl ops::BitOr for $ty {
73 type Output = Self;
74
75 fn bitor(mut self, rhs: Self) -> Self::Output {
76 self.0[0] |= rhs.0[0];
77 self.0[1] |= rhs.0[1];
78 self.0[2] |= rhs.0[2];
79 self.0[3] |= rhs.0[3];
80 self
81 }
82 }
83
84 impl ops::Not for $ty {
85 type Output = Self;
86
87 fn not(self) -> Self::Output {
88 Self([!self.0[0], !self.0[1], !self.0[2], !self.0[3]])
89 }
90 }
91
92 impl ops::Shl<u32> for $ty {
93 type Output = Self;
94
95 fn shl(self, rhs: u32) -> Self::Output {
96 unimplemented!("only used to meet trait bounds")
97 }
98 }
99 };
100}
101
102impl_common!(i256);
103impl_common!(u256);
104
105impl ops::Shr<u32> for u256 {
106 type Output = Self;
107
108 fn shr(self, rhs: u32) -> Self::Output {
109 assert!(rhs < Self::BITS, "attempted to shift right with overflow");
110
111 if rhs == 0 {
112 return self;
113 }
114
115 let mut ret = self;
116 let byte_shift = rhs / 64;
117 let bit_shift = rhs % 64;
118
119 for idx in 0..4 {
120 let base_idx = idx + byte_shift as usize;
121
122 let Some(base) = ret.0.get(base_idx) else {
123 ret.0[idx] = 0;
124 continue;
125 };
126
127 let mut new_val = base >> bit_shift;
128
129 if let Some(new) = ret.0.get(base_idx + 1) {
130 new_val |= new.overflowing_shl(64 - bit_shift).0;
131 }
132
133 ret.0[idx] = new_val;
134 }
135
136 ret
137 }
138}
139
140macro_rules! word {
141 (1, $val:expr) => {
142 (($val >> (32 * 3)) & Self::from(WORD_LO_MASK)) as u64
143 };
144 (2, $val:expr) => {
145 (($val >> (32 * 2)) & Self::from(WORD_LO_MASK)) as u64
146 };
147 (3, $val:expr) => {
148 (($val >> (32 * 1)) & Self::from(WORD_LO_MASK)) as u64
149 };
150 (4, $val:expr) => {
151 (($val >> (32 * 0)) & Self::from(WORD_LO_MASK)) as u64
152 };
153}
154
155impl HInt for u128 {
156 type D = u256;
157
158 fn widen(self) -> Self::D {
159 let w0 = self & u128::from(u64::MAX);
160 let w1 = (self >> u64::BITS) & u128::from(u64::MAX);
161 u256([w0 as u64, w1 as u64, 0, 0])
162 }
163
164 fn zero_widen(self) -> Self::D {
165 self.widen()
166 }
167
168 fn zero_widen_mul(self, rhs: Self) -> Self::D {
169 let product11: u64 = word!(1, self) * word!(1, rhs);
170 let product12: u64 = word!(1, self) * word!(2, rhs);
171 let product13: u64 = word!(1, self) * word!(3, rhs);
172 let product14: u64 = word!(1, self) * word!(4, rhs);
173 let product21: u64 = word!(2, self) * word!(1, rhs);
174 let product22: u64 = word!(2, self) * word!(2, rhs);
175 let product23: u64 = word!(2, self) * word!(3, rhs);
176 let product24: u64 = word!(2, self) * word!(4, rhs);
177 let product31: u64 = word!(3, self) * word!(1, rhs);
178 let product32: u64 = word!(3, self) * word!(2, rhs);
179 let product33: u64 = word!(3, self) * word!(3, rhs);
180 let product34: u64 = word!(3, self) * word!(4, rhs);
181 let product41: u64 = word!(4, self) * word!(1, rhs);
182 let product42: u64 = word!(4, self) * word!(2, rhs);
183 let product43: u64 = word!(4, self) * word!(3, rhs);
184 let product44: u64 = word!(4, self) * word!(4, rhs);
185
186 let sum0: u128 = u128::from(product44);
187 let sum1: u128 = u128::from(product34) + u128::from(product43);
188 let sum2: u128 = u128::from(product24) + u128::from(product33) + u128::from(product42);
189 let sum3: u128 = u128::from(product14)
190 + u128::from(product23)
191 + u128::from(product32)
192 + u128::from(product41);
193 let sum4: u128 = u128::from(product13) + u128::from(product22) + u128::from(product31);
194 let sum5: u128 = u128::from(product12) + u128::from(product21);
195 let sum6: u128 = u128::from(product11);
196
197 let r0: u128 =
198 (sum0 & u128::from(WORD_FULL_MASK)) + ((sum1 & u128::from(WORD_LO_MASK)) << 32);
199 let r1: u128 = (sum0 >> 64)
200 + ((sum1 >> 32) & u128::from(WORD_FULL_MASK))
201 + (sum2 & u128::from(WORD_FULL_MASK))
202 + ((sum3 << 32) & u128::from(WORD_HI_MASK));
203
204 let (lo, carry) = r0.overflowing_add(r1 << 64);
205 let hi = (r1 >> 64)
206 + (sum1 >> 96)
207 + (sum2 >> 64)
208 + (sum3 >> 32)
209 + sum4
210 + (sum5 << 32)
211 + (sum6 << 64)
212 + u128::from(carry);
213
214 u256([
215 (lo & U128_LO_MASK) as u64,
216 ((lo >> 64) & U128_LO_MASK) as u64,
217 (hi & U128_LO_MASK) as u64,
218 ((hi >> 64) & U128_LO_MASK) as u64,
219 ])
220 }
221
222 fn widen_mul(self, rhs: Self) -> Self::D {
223 self.zero_widen_mul(rhs)
224 }
225
226 fn widen_hi(self) -> Self::D {
227 self.widen() << <Self as MinInt>::BITS
228 }
229}
230
231impl HInt for i128 {
232 type D = i256;
233
234 fn widen(self) -> Self::D {
235 let mut ret = self.unsigned().zero_widen().signed();
236 if self.is_negative() {
237 ret.0[2] = u64::MAX;
238 ret.0[3] = u64::MAX;
239 }
240 ret
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 self.widen() << <Self as MinInt>::BITS
257 }
258}
259
260impl DInt for u256 {
261 type H = u128;
262
263 fn lo(self) -> Self::H {
264 let mut tmp: [u8; 16] = [0u8; 16];
265 tmp[..8].copy_from_slice(&self.0[0].to_le_bytes());
266 tmp[8..].copy_from_slice(&self.0[1].to_le_bytes());
267 u128::from_le_bytes(tmp)
268 }
269
270 fn hi(self) -> Self::H {
271 let mut tmp: [u8; 16] = [0u8; 16];
272 tmp[..8].copy_from_slice(&self.0[2].to_le_bytes());
273 tmp[8..].copy_from_slice(&self.0[3].to_le_bytes());
274 u128::from_le_bytes(tmp)
275 }
276}
277
278impl DInt for i256 {
279 type H = i128;
280
281 fn lo(self) -> Self::H {
282 let mut tmp: [u8; 16] = [0u8; 16];
283 tmp[..8].copy_from_slice(&self.0[0].to_le_bytes());
284 tmp[8..].copy_from_slice(&self.0[1].to_le_bytes());
285 i128::from_le_bytes(tmp)
286 }
287
288 fn hi(self) -> Self::H {
289 let mut tmp: [u8; 16] = [0u8; 16];
290 tmp[..8].copy_from_slice(&self.0[2].to_le_bytes());
291 tmp[8..].copy_from_slice(&self.0[3].to_le_bytes());
292 i128::from_le_bytes(tmp)
293 }
294}
295