snarkvm_utilities/biginteger/
bigint_384.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 BigInteger384(pub [u64; 6]);
37
38impl BigInteger384 {
39    pub const fn new(value: [u64; 6]) -> Self {
40        BigInteger384(value)
41    }
42}
43impl BigInteger for BigInteger384 {
44    const NUM_LIMBS: usize = 6;
45
46    #[inline]
47    fn add_nocarry(&mut self, other: &Self) -> bool {
48        #[cfg(target_arch = "x86_64")]
49        unsafe {
50            use core::arch::x86_64::_addcarry_u64;
51            let mut carry = 0;
52            carry = _addcarry_u64(carry, self.0[0], other.0[0], &mut self.0[0]);
53            carry = _addcarry_u64(carry, self.0[1], other.0[1], &mut self.0[1]);
54            carry = _addcarry_u64(carry, self.0[2], other.0[2], &mut self.0[2]);
55            carry = _addcarry_u64(carry, self.0[3], other.0[3], &mut self.0[3]);
56            carry = _addcarry_u64(carry, self.0[4], other.0[4], &mut self.0[4]);
57            carry = _addcarry_u64(carry, self.0[5], other.0[5], &mut self.0[5]);
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 = super::arithmetic::adc(&mut self.0[4], other.0[4], carry);
68            carry = super::arithmetic::adc(&mut self.0[5], other.0[5], carry);
69            carry != 0
70        }
71    }
72
73    #[inline]
74    fn sub_noborrow(&mut self, other: &Self) -> bool {
75        #[cfg(target_arch = "x86_64")]
76        unsafe {
77            use core::arch::x86_64::_subborrow_u64;
78            let mut borrow = 0;
79            borrow = _subborrow_u64(borrow, self.0[0], other.0[0], &mut self.0[0]);
80            borrow = _subborrow_u64(borrow, self.0[1], other.0[1], &mut self.0[1]);
81            borrow = _subborrow_u64(borrow, self.0[2], other.0[2], &mut self.0[2]);
82            borrow = _subborrow_u64(borrow, self.0[3], other.0[3], &mut self.0[3]);
83            borrow = _subborrow_u64(borrow, self.0[4], other.0[4], &mut self.0[4]);
84            borrow = _subborrow_u64(borrow, self.0[5], other.0[5], &mut self.0[5]);
85            borrow != 0
86        }
87        #[cfg(not(target_arch = "x86_64"))]
88        {
89            let mut borrow = 0;
90            borrow = super::arithmetic::sbb(&mut self.0[0], other.0[0], borrow);
91            borrow = super::arithmetic::sbb(&mut self.0[1], other.0[1], borrow);
92            borrow = super::arithmetic::sbb(&mut self.0[2], other.0[2], borrow);
93            borrow = super::arithmetic::sbb(&mut self.0[3], other.0[3], borrow);
94            borrow = super::arithmetic::sbb(&mut self.0[4], other.0[4], borrow);
95            borrow = super::arithmetic::sbb(&mut self.0[5], other.0[5], borrow);
96            borrow != 0
97        }
98    }
99
100    #[inline]
101    fn mul2(&mut self) {
102        let mut last = 0;
103        for i in &mut self.0 {
104            let tmp = *i >> 63;
105            *i <<= 1;
106            *i |= last;
107            last = tmp;
108        }
109    }
110
111    #[inline]
112    fn muln(&mut self, mut n: u32) {
113        if n >= 64 * 6 {
114            *self = Self::from(0);
115            return;
116        }
117        while n >= 64 {
118            let mut t = 0;
119            for i in &mut self.0 {
120                std::mem::swap(&mut t, i);
121            }
122            n -= 64;
123        }
124        if n > 0 {
125            let mut t = 0;
126            for i in &mut self.0 {
127                let t2 = *i >> (64 - n);
128                *i <<= n;
129                *i |= t;
130                t = t2;
131            }
132        }
133    }
134
135    #[inline]
136    fn div2(&mut self) {
137        let mut t = 0;
138        for i in self.0.iter_mut().rev() {
139            let t2 = *i << 63;
140            *i >>= 1;
141            *i |= t;
142            t = t2;
143        }
144    }
145
146    #[inline]
147    fn divn(&mut self, mut n: u32) {
148        if n >= 64 * 6 {
149            *self = Self::from(0);
150            return;
151        }
152        while n >= 64 {
153            let mut t = 0;
154            for i in self.0.iter_mut().rev() {
155                std::mem::swap(&mut t, i);
156            }
157            n -= 64;
158        }
159        if n > 0 {
160            let mut t = 0;
161            for i in self.0.iter_mut().rev() {
162                let t2 = *i << (64 - n);
163                *i >>= n;
164                *i |= t;
165                t = t2;
166            }
167        }
168    }
169
170    #[inline]
171    fn is_odd(&self) -> bool {
172        self.0[0] & 1 == 1
173    }
174
175    #[inline]
176    fn is_even(&self) -> bool {
177        !self.is_odd()
178    }
179
180    #[inline]
181    fn is_zero(&self) -> bool {
182        self.0.iter().all(|&e| e == 0)
183    }
184
185    #[inline]
186    fn num_bits(&self) -> u32 {
187        let mut ret = 6 * 64;
188        for i in self.0.iter().rev() {
189            let leading = i.leading_zeros();
190            ret -= leading;
191            if leading != 64 {
192                break;
193            }
194        }
195        ret
196    }
197
198    #[inline]
199    fn get_bit(&self, i: usize) -> bool {
200        if i >= 64 * 6 {
201            false
202        } else {
203            let limb = i / 64;
204            let bit = i - (64 * limb);
205            (self.0[limb] & (1 << bit)) != 0
206        }
207    }
208
209    #[inline]
210    fn to_biguint(&self) -> num_bigint::BigUint {
211        BigUint::from_bytes_le(&self.to_bytes_le().unwrap())
212    }
213
214    #[inline]
215    fn find_wnaf(&self) -> Vec<i64> {
216        let mut res = crate::vec::Vec::new();
217        let mut e = *self;
218        while !e.is_zero() {
219            let z: i64;
220            if e.is_odd() {
221                z = 2 - (e.0[0] % 4) as i64;
222                if z >= 0 {
223                    e.sub_noborrow(&Self::from(z as u64));
224                } else {
225                    e.add_nocarry(&Self::from((-z) as u64));
226                }
227            } else {
228                z = 0;
229            }
230            res.push(z);
231            e.div2();
232        }
233        res
234    }
235}
236impl ToBits for BigInteger384 {
237    #[doc = " Returns `self` as a boolean array in little-endian order, with trailing zeros."]
238    fn write_bits_le(&self, vec: &mut Vec<bool>) {
239        vec.extend(BitIteratorLE::new(self));
240    }
241
242    #[doc = " Returns `self` as a boolean array in big-endian order, with leading zeros."]
243    fn write_bits_be(&self, vec: &mut Vec<bool>) {
244        vec.extend(BitIteratorBE::new(self));
245    }
246}
247impl FromBits for BigInteger384 {
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}
278impl ToBytes for BigInteger384 {
279    #[inline]
280    fn write_le<W: Write>(&self, writer: W) -> IoResult<()> {
281        let mut arr = [0u8; 8 * 6];
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}
288impl FromBytes for BigInteger384 {
289    #[inline]
290    fn read_le<R: Read>(reader: R) -> IoResult<Self> {
291        <[u64; 6]>::read_le(reader).map(Self::new)
292    }
293}
294impl Debug for BigInteger384 {
295    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
296        for i in self.0.iter().rev() {
297            write!(f, "{:016X}", *i)?;
298        }
299        Ok(())
300    }
301}
302impl Display for BigInteger384 {
303    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
304        write!(f, "{}", self.to_biguint())
305    }
306}
307impl Ord for BigInteger384 {
308    #[inline]
309    #[allow(clippy::comparison_chain)]
310    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
311        for (a, b) in self.0.iter().rev().zip(other.0.iter().rev()) {
312            if a < b {
313                return std::cmp::Ordering::Less;
314            } else if a > b {
315                return std::cmp::Ordering::Greater;
316            }
317        }
318        std::cmp::Ordering::Equal
319    }
320}
321impl PartialOrd for BigInteger384 {
322    #[inline]
323    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
324        Some(self.cmp(other))
325    }
326}
327impl Distribution<BigInteger384> for Standard {
328    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInteger384 {
329        BigInteger384(rng.gen())
330    }
331}
332impl AsMut<[u64]> for BigInteger384 {
333    #[inline]
334    fn as_mut(&mut self) -> &mut [u64] {
335        &mut self.0
336    }
337}
338impl AsRef<[u64]> for BigInteger384 {
339    #[inline]
340    fn as_ref(&self) -> &[u64] {
341        &self.0
342    }
343}
344impl From<u64> for BigInteger384 {
345    #[inline]
346    fn from(val: u64) -> BigInteger384 {
347        let mut repr = Self::default();
348        repr.0[0] = val;
349        repr
350    }
351}
snarkvm_utilities/biginteger/bigint_384.rs

snarkvm_utilities/biginteger/
bigint_384.rs
