proof_of_sql/base/math/
i256.rs

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

proof_of_sql/base/math/
i256.rs
