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

snarkvm_utilities/biginteger/
bigint_384.rs
