proof_of_sql/base/math/
i256.rs

1use crate::base::scalar::Scalar;
2use ark_ff::BigInteger;
3use core::ops::Neg;
4use serde::{Deserialize, Serialize};
5
6/// A 256-bit data type with some conversions implemented that interpret it as a signed integer.
7///
8/// This should only implement conversions. If anything else is needed, we should strongly consider an alternative design.
9#[derive(Serialize, Deserialize, Debug, Eq, PartialEq, Clone, Copy)]
10pub struct I256([u64; 4]);
11
12impl Neg for I256 {
13    type Output = Self;
14    /// Computes the wrapping negative of the value. This could perhaps be more efficient.
15    fn neg(self) -> Self::Output {
16        let mut res = ark_ff::BigInt([0; 4]);
17        res.sub_with_borrow(&ark_ff::BigInt(self.0));
18        Self(res.0)
19    }
20}
21
22impl I256 {
23    /// Make an `I256` from its limbs.
24    #[must_use]
25    pub fn new(limbs: [u64; 4]) -> Self {
26        Self(limbs)
27    }
28    #[must_use]
29    /// Conversion into a [Scalar] type. The conversion handles negative values. In other words, `-1` maps to `-S::ONE`.
30    ///
31    /// NOTE: the behavior of this is undefined if the absolute value is larger than the modulus.
32    ///
33    /// NOTE: this is not a particularly efficient method. Please either refactor or avoid when performance matters.
34    pub fn into_scalar<S: Scalar>(self) -> S {
35        if self.0[3] & 0x8000_0000_0000_0000 == 0 {
36            self.0.into()
37        } else {
38            (Into::<S>::into(self.neg().0)).neg()
39        }
40    }
41
42    #[must_use]
43    /// Conversion from a [`num_bigint::BigInt`].
44    /// The conversion handles negative values and also wraps when the value is too large for an `I256`.
45    ///
46    /// NOTE: this is not a particularly efficient method. Please either refactor or avoid when performance matters.
47    pub fn from_num_bigint(value: &num_bigint::BigInt) -> Self {
48        let (sign, limbs_vec) = value.to_u64_digits();
49        let num_limbs = limbs_vec.len().min(4);
50        let mut limbs = [0u64; 4];
51        limbs[..num_limbs].copy_from_slice(&limbs_vec[..num_limbs]);
52        limbs[3] &= 0x7FFF_FFFF_FFFF_FFFF;
53        match sign {
54            num_bigint::Sign::Minus => Self(limbs).neg(),
55            num_bigint::Sign::Plus | num_bigint::Sign::NoSign => Self(limbs),
56        }
57    }
58}
59impl From<i32> for I256 {
60    fn from(value: i32) -> Self {
61        let abs = Self([value.unsigned_abs().into(), 0, 0, 0]);
62        if value >= 0 {
63            abs
64        } else {
65            abs.neg()
66        }
67    }
68}
69
70#[expect(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
71impl From<i128> for I256 {
72    fn from(value: i128) -> Self {
73        Self([
74            value as u64,
75            (value >> 64) as u64,
76            (value >> 127) as u64,
77            (value >> 127) as u64,
78        ])
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use crate::base::scalar::{test_scalar::TestScalar, MontScalar, Scalar};
86    use ark_ff::MontFp;
87    use num_bigint::BigInt;
88    use rand::{thread_rng, Rng};
89
90    const ZERO: I256 = I256([0, 0, 0, 0]);
91    const ONE: I256 = I256([1, 0, 0, 0]);
92    const TWO: I256 = I256([2, 0, 0, 0]);
93    const NEG_ONE: I256 = I256([
94        0xFFFF_FFFF_FFFF_FFFF,
95        0xFFFF_FFFF_FFFF_FFFF,
96        0xFFFF_FFFF_FFFF_FFFF,
97        0xFFFF_FFFF_FFFF_FFFF,
98    ]);
99    const NEG_TWO: I256 = I256([
100        0xFFFF_FFFF_FFFF_FFFE,
101        0xFFFF_FFFF_FFFF_FFFF,
102        0xFFFF_FFFF_FFFF_FFFF,
103        0xFFFF_FFFF_FFFF_FFFF,
104    ]);
105    const A_STR: &str =
106        "57896044618658097705508390768957273162799202909612615603626436559492530307074";
107    const A: I256 = I256([2, 0, 0, 0x7FFF_FFFF_FFFF_FFFF]);
108    const NEG_A: I256 = I256([
109        0xFFFF_FFFF_FFFF_FFFE,
110        0xFFFF_FFFF_FFFF_FFFF,
111        0xFFFF_FFFF_FFFF_FFFF,
112        0x8000_0000_0000_0000,
113    ]);
114    const B_STR: &str =
115        "44514458406356786875149426309623179975904669798901350226660343085647800511238";
116    const B: I256 = I256([
117        0x12DE_4D02_71BF_2B06,
118        0x2686_80A2_B415_EE31,
119        0xBCF3_35CF_A69C_DBE3,
120        0x626A_4A65_275E_1D88,
121    ]);
122    const NEG_B: I256 = I256([
123        0xED21_B2FD_8E40_D4FA,
124        0xD979_7F5D_4BEA_11CE,
125        0x430C_CA30_5963_241C,
126        0x9D95_B59A_D8A1_E277,
127    ]);
128    const C_STR: &str =
129        "452312848583266388373324160190187140051835877600158453279131187530910662656";
130    const C_SCALAR: TestScalar = MontScalar(MontFp!(
131        "452312848583266388373324160190187140051835877600158453279131187530910662656"
132    ));
133    const C: I256 = I256([
134        0x0000_0000_0000_0000,
135        0x0000_0000_0000_0000,
136        0x0000_0000_0000_0000,
137        0x0100_0000_0000_0000,
138    ]);
139    const NEG_C: I256 = I256([
140        0x0000_0000_0000_0000,
141        0x0000_0000_0000_0000,
142        0x0000_0000_0000_0000,
143        0xFF00_0000_0000_0000,
144    ]);
145    const MODULUS_MINUS_ONE: I256 = I256([
146        0x5812_631A_5CF5_D3EC,
147        0x14DE_F9DE_A2F7_9CD6,
148        0x0000_0000_0000_0000,
149        0x1000_0000_0000_0000,
150    ]);
151    const NEG_MODULUS_PLUS_ONE: I256 = I256([
152        0xa7ed_9ce5_a30a_2c14,
153        0xEB21_0621_5D08_6329,
154        0xFFFF_FFFF_FFFF_FFFF,
155        0xEFFF_FFFF_FFFF_FFFF,
156    ]);
157    const MODULUS_MINUS_TWO: I256 = I256([
158        0x5812_631A_5CF5_D3EB,
159        0x14DE_F9DE_A2F7_9CD6,
160        0x0000_0000_0000_0000,
161        0x1000_0000_0000_0000,
162    ]);
163    const NEG_MODULUS_PLUS_TWO: I256 = I256([
164        0xa7ed_9ce5_a30a_2c15,
165        0xEB21_0621_5D08_6329,
166        0xFFFF_FFFF_FFFF_FFFF,
167        0xEFFF_FFFF_FFFF_FFFF,
168    ]);
169
170    #[test]
171    fn we_can_compute_the_negative_of_i256() {
172        assert_eq!(ZERO.neg(), ZERO);
173        assert_eq!(ONE.neg(), NEG_ONE);
174        assert_eq!(NEG_ONE.neg(), ONE);
175        assert_eq!(TWO.neg(), NEG_TWO);
176        assert_eq!(NEG_TWO.neg(), TWO);
177        assert_eq!(A.neg(), NEG_A);
178        assert_eq!(NEG_A.neg(), A);
179        assert_eq!(B.neg(), NEG_B);
180        assert_eq!(NEG_B.neg(), B);
181        assert_eq!(C.neg(), NEG_C);
182        assert_eq!(NEG_C.neg(), C);
183        assert_eq!(MODULUS_MINUS_ONE.neg(), NEG_MODULUS_PLUS_ONE);
184        assert_eq!(NEG_MODULUS_PLUS_ONE.neg(), MODULUS_MINUS_ONE);
185        assert_eq!(MODULUS_MINUS_TWO.neg(), NEG_MODULUS_PLUS_TWO);
186        assert_eq!(NEG_MODULUS_PLUS_TWO.neg(), MODULUS_MINUS_TWO);
187
188        let mut rng = thread_rng();
189        for _ in 0..10 {
190            let x = I256([rng.gen(), rng.gen(), rng.gen(), rng.gen()]);
191            assert_eq!(x.neg().neg(), x);
192        }
193    }
194    #[test]
195    fn we_can_convert_i256_into_scalar() {
196        assert_eq!(ZERO.into_scalar::<TestScalar>(), TestScalar::ZERO);
197        assert_eq!(ONE.into_scalar::<TestScalar>(), TestScalar::ONE);
198        assert_eq!(NEG_ONE.into_scalar::<TestScalar>(), -TestScalar::ONE);
199        assert_eq!(TWO.into_scalar::<TestScalar>(), TestScalar::TWO);
200        assert_eq!(NEG_TWO.into_scalar::<TestScalar>(), -TestScalar::TWO);
201        assert_eq!(C.into_scalar::<TestScalar>(), C_SCALAR);
202        assert_eq!(NEG_C.into_scalar::<TestScalar>(), -C_SCALAR);
203        assert_eq!(
204            MODULUS_MINUS_ONE.into_scalar::<TestScalar>(),
205            -TestScalar::ONE
206        );
207        assert_eq!(
208            NEG_MODULUS_PLUS_ONE.into_scalar::<TestScalar>(),
209            TestScalar::ONE
210        );
211        assert_eq!(
212            MODULUS_MINUS_TWO.into_scalar::<TestScalar>(),
213            -TestScalar::TWO
214        );
215        assert_eq!(
216            NEG_MODULUS_PLUS_TWO.into_scalar::<TestScalar>(),
217            TestScalar::TWO
218        );
219
220        let mut rng = thread_rng();
221        for _ in 0..10 {
222            let x = I256([rng.gen(), rng.gen(), rng.gen(), rng.gen()]);
223            assert_eq!(
224                x.neg().into_scalar::<TestScalar>(),
225                -(x.into_scalar::<TestScalar>())
226            );
227        }
228    }
229    #[test]
230    fn we_can_convert_i256_from_num_bigint() {
231        assert_eq!(I256::from_num_bigint(&"0".parse().unwrap()), ZERO);
232        assert_eq!(I256::from_num_bigint(&"1".parse().unwrap()), ONE);
233        assert_eq!(I256::from_num_bigint(&"-1".parse().unwrap()), NEG_ONE);
234        assert_eq!(I256::from_num_bigint(&"2".parse().unwrap()), TWO);
235        assert_eq!(I256::from_num_bigint(&"-2".parse().unwrap()), NEG_TWO);
236        assert_eq!(I256::from_num_bigint(&A_STR.parse().unwrap()), A);
237        assert_eq!(
238            I256::from_num_bigint(&-A_STR.parse::<BigInt>().unwrap()),
239            NEG_A
240        );
241        assert_eq!(I256::from_num_bigint(&B_STR.parse().unwrap()), B);
242        assert_eq!(
243            I256::from_num_bigint(&-B_STR.parse::<BigInt>().unwrap()),
244            NEG_B
245        );
246        assert_eq!(I256::from_num_bigint(&C_STR.parse().unwrap()), C);
247        assert_eq!(
248            I256::from_num_bigint(&-C_STR.parse::<BigInt>().unwrap()),
249            NEG_C
250        );
251
252        let mut rng = thread_rng();
253        for _ in 0..10 {
254            let x =
255                (BigInt::from(rng.gen::<i128>().abs()) << 128) + BigInt::from(rng.gen::<u128>());
256            let y = &x + (BigInt::from(rng.gen::<u128>()) << 255);
257            assert_eq!(I256::from_num_bigint(&y), I256::from_num_bigint(&x));
258            assert_eq!(I256::from_num_bigint(&-&y), I256::from_num_bigint(&-x));
259            assert_eq!(I256::from_num_bigint(&y), I256::from_num_bigint(&-y).neg());
260        }
261    }
262    #[test]
263    fn we_can_convert_i256_from_i32() {
264        assert_eq!(I256::from(0), ZERO);
265        assert_eq!(I256::from(1), ONE);
266        assert_eq!(I256::from(-1), NEG_ONE);
267        assert_eq!(I256::from(2), TWO);
268        assert_eq!(I256::from(-2), NEG_TWO);
269    }
270    #[test]
271    fn we_can_convert_i256_between_type_compatibly() {
272        let mut rng = thread_rng();
273        for _ in 0..10 {
274            let int32: i32 = rng.gen();
275            let neg_int32 = -int32;
276            let scalar = TestScalar::from(int32);
277            let neg_scalar = -scalar;
278            let bigint = BigInt::from(int32);
279            let neg_bigint = -&bigint;
280            let int256_from_i32 = I256::from(int32);
281            let neg_int256_from_i32 = I256::from(neg_int32);
282            let int256_from_bigint = I256::from_num_bigint(&bigint);
283            let neg_int256_from_bigint = I256::from_num_bigint(&neg_bigint);
284            assert_eq!(int256_from_i32, int256_from_bigint);
285            assert_eq!(neg_int256_from_i32, neg_int256_from_bigint);
286            assert_eq!(neg_int256_from_i32, int256_from_i32.neg());
287            assert_eq!(int256_from_i32.into_scalar::<TestScalar>(), scalar);
288            assert_eq!(neg_int256_from_i32.into_scalar::<TestScalar>(), neg_scalar);
289        }
290    }
291
292    #[expect(clippy::cast_sign_loss)]
293    #[test]
294    fn test_i128_to_i256_conversion() {
295        // Test zero
296        assert_eq!(I256::from(0i128), ZERO);
297
298        // Test positive values
299        assert_eq!(I256::from(1i128), ONE);
300        assert_eq!(I256::from(2i128), TWO);
301
302        // Test negative values
303        assert_eq!(I256::from(-1i128), NEG_ONE);
304        assert_eq!(I256::from(-2i128), NEG_TWO);
305
306        // Test boundary values
307        assert_eq!(
308            I256::from(i128::MIN),
309            I256([0, 0x8000_0000_0000_0000, 0, 0]).neg()
310        );
311        assert_eq!(
312            I256::from(i128::MAX),
313            I256([0xFFFF_FFFF_FFFF_FFFF, 0x7FFF_FFFF_FFFF_FFFF, 0, 0])
314        );
315
316        // Test some random values
317        let test_values = [
318            42i128,
319            -42i128,
320            1_234_567_890i128,
321            -1_234_567_890i128,
322            i128::from(i64::MAX),
323            i128::from(i64::MIN),
324        ];
325
326        for &value in &test_values {
327            let converted = I256::from(value);
328            if value >= 0 {
329                assert_eq!(
330                    converted.0[0],
331                    (value as u128 & 0xFFFF_FFFF_FFFF_FFFF) as u64
332                );
333                assert_eq!(
334                    converted.0[1],
335                    ((value as u128 >> 64) & 0xFFFF_FFFF_FFFF_FFFF) as u64
336                );
337                assert_eq!(converted.0[2], 0);
338                assert_eq!(converted.0[3], 0);
339            } else {
340                let abs_value = value.unsigned_abs();
341                let expected = I256([
342                    (abs_value & 0xFFFF_FFFF_FFFF_FFFF) as u64,
343                    ((abs_value >> 64) & 0xFFFF_FFFF_FFFF_FFFF) as u64,
344                    0,
345                    0,
346                ])
347                .neg();
348                assert_eq!(converted, expected);
349            }
350        }
351    }
352}
proof_of_sql/base/math/i256.rs

proof_of_sql/base/math/
i256.rs
