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

snarkvm_utilities/biginteger/
bigint_384.rs
