compiler_builtins/int/
big.rs

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 UnsignedInt = 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 UnsignedInt = 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 = [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 = [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 = [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 = [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}
compiler_builtins/int/big.rs

compiler_builtins/int/
big.rs
