snarkvm_utilities/biginteger/
bigint_256.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use std::io::{Read, Result as IoResult, Write};
17
18use crate::{
19    FromBits,
20    FromBytes,
21    ToBits,
22    ToBytes,
23    biginteger::BigInteger,
24    bititerator::{BitIteratorBE, BitIteratorLE},
25};
26
27use anyhow::Result;
28use core::fmt::{Debug, Display};
29use num_bigint::BigUint;
30use rand::{
31    Rng,
32    distributions::{Distribution, Standard},
33};
34use zeroize::Zeroize;
35
36#[derive(Copy, Clone, PartialEq, Eq, Default, Hash, Zeroize)]
37pub struct BigInteger256(pub [u64; 4]);
38
39impl BigInteger256 {
40    pub const fn new(value: [u64; 4]) -> Self {
41        BigInteger256(value)
42    }
43}
44
45impl crate::biginteger::BigInteger for BigInteger256 {
46    const NUM_LIMBS: usize = 4;
47
48    #[inline]
49    fn add_nocarry(&mut self, other: &Self) -> bool {
50        #[cfg(target_arch = "x86_64")]
51        unsafe {
52            use core::arch::x86_64::_addcarry_u64;
53            let mut carry = 0;
54            carry = _addcarry_u64(carry, self.0[0], other.0[0], &mut self.0[0]);
55            carry = _addcarry_u64(carry, self.0[1], other.0[1], &mut self.0[1]);
56            carry = _addcarry_u64(carry, self.0[2], other.0[2], &mut self.0[2]);
57            carry = _addcarry_u64(carry, self.0[3], other.0[3], &mut self.0[3]);
58            carry != 0
59        }
60        #[cfg(not(target_arch = "x86_64"))]
61        {
62            let mut carry = 0;
63            carry = super::arithmetic::adc(&mut self.0[0], other.0[0], carry);
64            carry = super::arithmetic::adc(&mut self.0[1], other.0[1], carry);
65            carry = super::arithmetic::adc(&mut self.0[2], other.0[2], carry);
66            carry = super::arithmetic::adc(&mut self.0[3], other.0[3], carry);
67            carry != 0
68        }
69    }
70
71    #[inline]
72    fn sub_noborrow(&mut self, other: &Self) -> bool {
73        #[cfg(target_arch = "x86_64")]
74        unsafe {
75            use core::arch::x86_64::_subborrow_u64;
76            let mut borrow = 0;
77            borrow = _subborrow_u64(borrow, self.0[0], other.0[0], &mut self.0[0]);
78            borrow = _subborrow_u64(borrow, self.0[1], other.0[1], &mut self.0[1]);
79            borrow = _subborrow_u64(borrow, self.0[2], other.0[2], &mut self.0[2]);
80            borrow = _subborrow_u64(borrow, self.0[3], other.0[3], &mut self.0[3]);
81            borrow != 0
82        }
83        #[cfg(not(target_arch = "x86_64"))]
84        {
85            let mut borrow = 0;
86            borrow = super::arithmetic::sbb(&mut self.0[0], other.0[0], borrow);
87            borrow = super::arithmetic::sbb(&mut self.0[1], other.0[1], borrow);
88            borrow = super::arithmetic::sbb(&mut self.0[2], other.0[2], borrow);
89            borrow = super::arithmetic::sbb(&mut self.0[3], other.0[3], borrow);
90            borrow != 0
91        }
92    }
93
94    #[inline]
95    fn mul2(&mut self) {
96        let mut last = 0;
97        for i in &mut self.0 {
98            let tmp = *i >> 63;
99            *i <<= 1;
100            *i |= last;
101            last = tmp;
102        }
103    }
104
105    #[inline]
106    fn muln(&mut self, mut n: u32) {
107        if n >= 64 * 4 {
108            *self = Self::from(0);
109            return;
110        }
111        while n >= 64 {
112            let mut t = 0;
113            for i in &mut self.0 {
114                std::mem::swap(&mut t, i);
115            }
116            n -= 64;
117        }
118        if n > 0 {
119            let mut t = 0;
120            for i in &mut self.0 {
121                let t2 = *i >> (64 - n);
122                *i <<= n;
123                *i |= t;
124                t = t2;
125            }
126        }
127    }
128
129    #[inline]
130    fn div2(&mut self) {
131        let mut t = 0;
132        for i in self.0.iter_mut().rev() {
133            let t2 = *i << 63;
134            *i >>= 1;
135            *i |= t;
136            t = t2;
137        }
138    }
139
140    #[inline]
141    fn divn(&mut self, mut n: u32) {
142        if n >= 64 * 4 {
143            *self = Self::from(0);
144            return;
145        }
146        while n >= 64 {
147            let mut t = 0;
148            for i in self.0.iter_mut().rev() {
149                std::mem::swap(&mut t, i);
150            }
151            n -= 64;
152        }
153        if n > 0 {
154            let mut t = 0;
155            for i in self.0.iter_mut().rev() {
156                let t2 = *i << (64 - n);
157                *i >>= n;
158                *i |= t;
159                t = t2;
160            }
161        }
162    }
163
164    #[inline]
165    fn is_odd(&self) -> bool {
166        self.0[0] & 1 == 1
167    }
168
169    #[inline]
170    fn is_even(&self) -> bool {
171        !self.is_odd()
172    }
173
174    #[inline]
175    fn is_zero(&self) -> bool {
176        self.0.iter().all(|&e| e == 0)
177    }
178
179    #[inline]
180    fn num_bits(&self) -> u32 {
181        let mut ret = 4 * 64;
182        for i in self.0.iter().rev() {
183            let leading = i.leading_zeros();
184            ret -= leading;
185            if leading != 64 {
186                break;
187            }
188        }
189        ret
190    }
191
192    #[inline]
193    fn get_bit(&self, i: usize) -> bool {
194        if i >= 64 * 4 {
195            false
196        } else {
197            let limb = i / 64;
198            let bit = i - (64 * limb);
199            (self.0[limb] & (1 << bit)) != 0
200        }
201    }
202
203    #[inline]
204    fn to_biguint(&self) -> num_bigint::BigUint {
205        BigUint::from_bytes_le(&self.to_bytes_le().unwrap())
206    }
207
208    #[inline]
209    fn find_wnaf(&self) -> Vec<i64> {
210        let mut res = Vec::new();
211        let mut e = *self;
212        while !e.is_zero() {
213            let z: i64;
214            if e.is_odd() {
215                z = 2 - (e.0[0] % 4) as i64;
216                if z >= 0 {
217                    e.sub_noborrow(&Self::from(z as u64));
218                } else {
219                    e.add_nocarry(&Self::from((-z) as u64));
220                }
221            } else {
222                z = 0;
223            }
224            res.push(z);
225            e.div2();
226        }
227        res
228    }
229}
230
231impl ToBits for BigInteger256 {
232    #[doc = " Returns `self` as a boolean array in little-endian order, with trailing zeros."]
233    fn write_bits_le(&self, vec: &mut Vec<bool>) {
234        let iter = BitIteratorLE::new(self);
235        vec.reserve(iter.len());
236        vec.extend(iter);
237    }
238
239    #[doc = " Returns `self` as a boolean array in big-endian order, with leading zeros."]
240    fn write_bits_be(&self, vec: &mut Vec<bool>) {
241        let iter = BitIteratorBE::new(self);
242        vec.reserve(iter.len());
243        vec.extend(iter);
244    }
245}
246
247impl FromBits for BigInteger256 {
248    #[doc = " Returns a `BigInteger` by parsing a slice of bits in little-endian format"]
249    #[doc = " and transforms it into a slice of little-endian u64 elements."]
250    fn from_bits_le(bits: &[bool]) -> Result<Self> {
251        let mut res = Self::default();
252        for (i, bits64) in bits.chunks(64).enumerate() {
253            let mut acc: u64 = 0;
254            for bit in bits64.iter().rev() {
255                acc <<= 1;
256                acc += *bit as u64;
257            }
258            res.0[i] = acc;
259        }
260        Ok(res)
261    }
262
263    #[doc = " Returns a `BigInteger` by parsing a slice of bits in big-endian format"]
264    #[doc = " and transforms it into a slice of little-endian u64 elements."]
265    fn from_bits_be(bits: &[bool]) -> Result<Self> {
266        let mut res = Self::default();
267        for (i, bits64) in bits.rchunks(64).enumerate() {
268            let mut acc: u64 = 0;
269            for bit in bits64.iter() {
270                acc <<= 1;
271                acc += *bit as u64;
272            }
273            res.0[i] = acc;
274        }
275        Ok(res)
276    }
277}
278
279impl ToBytes for BigInteger256 {
280    #[inline]
281    fn write_le<W: Write>(&self, writer: W) -> IoResult<()> {
282        let mut arr = [0u8; 8 * 4];
283        for (i, num) in self.0.iter().enumerate() {
284            arr[i * 8..(i + 1) * 8].copy_from_slice(&num.to_le_bytes());
285        }
286        arr.write_le(writer)
287    }
288}
289
290impl FromBytes for BigInteger256 {
291    #[inline]
292    fn read_le<R: Read>(reader: R) -> IoResult<Self> {
293        <[u64; 4]>::read_le(reader).map(Self::new)
294    }
295}
296
297impl Debug for BigInteger256 {
298    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
299        for i in self.0.iter().rev() {
300            write!(f, "{:016X}", *i)?;
301        }
302        Ok(())
303    }
304}
305
306impl Display for BigInteger256 {
307    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
308        write!(f, "{}", self.to_biguint())
309    }
310}
311
312impl Ord for BigInteger256 {
313    #[inline]
314    #[allow(clippy::comparison_chain)]
315    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
316        for (a, b) in self.0.iter().rev().zip(other.0.iter().rev()) {
317            if a < b {
318                return std::cmp::Ordering::Less;
319            } else if a > b {
320                return std::cmp::Ordering::Greater;
321            }
322        }
323        std::cmp::Ordering::Equal
324    }
325}
326
327impl PartialOrd for BigInteger256 {
328    #[inline]
329    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
330        Some(self.cmp(other))
331    }
332}
333
334impl Distribution<BigInteger256> for Standard {
335    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInteger256 {
336        BigInteger256(rng.r#gen())
337    }
338}
339
340impl AsMut<[u64]> for BigInteger256 {
341    #[inline]
342    fn as_mut(&mut self) -> &mut [u64] {
343        &mut self.0
344    }
345}
346
347impl AsRef<[u64]> for BigInteger256 {
348    #[inline]
349    fn as_ref(&self) -> &[u64] {
350        &self.0
351    }
352}
353
354impl From<u64> for BigInteger256 {
355    #[inline]
356    fn from(val: u64) -> BigInteger256 {
357        let mut repr = Self::default();
358        repr.0[0] = val;
359        repr
360    }
361}
snarkvm_utilities/biginteger/bigint_256.rs

snarkvm_utilities/biginteger/
bigint_256.rs
