snarkvm_utilities/biginteger/
bigint_256.rs

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

snarkvm_utilities/biginteger/
bigint_256.rs
