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