snarkvm_utilities/biginteger/
bigint_384.rs

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