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

proof_of_sql/base/math/
i256.rs
