snarkvm_utilities/biginteger/
mod.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::{FromBits, FromBytes, ToBits, ToBytes, rand::Uniform};
17
18use num_bigint::BigUint;
19use std::fmt::{Debug, Display};
20
21mod bigint_256;
22pub use bigint_256::*;
23
24mod bigint_384;
25pub use bigint_384::*;
26
27#[cfg(test)]
28mod tests;
29
30/// This defines a `BigInteger`, a smart wrapper around a
31/// sequence of `u64` limbs, least-significant digit first.
32pub trait BigInteger:
33    ToBits
34    + FromBits
35    + ToBytes
36    + FromBytes
37    + Copy
38    + Clone
39    + Debug
40    + Default
41    + Display
42    + Eq
43    + Ord
44    + Send
45    + Sized
46    + Sync
47    + 'static
48    + Uniform
49    + AsMut<[u64]>
50    + AsRef<[u64]>
51    + From<u64>
52{
53    /// The number of limbs used in this BigInteger.
54    const NUM_LIMBS: usize;
55
56    /// Add another representation to this one, returning the carry bit.
57    fn add_nocarry(&mut self, other: &Self) -> bool;
58
59    /// Subtract another representation from this one, returning the borrow bit.
60    fn sub_noborrow(&mut self, other: &Self) -> bool;
61
62    /// Performs a leftwise bitshift of this number, effectively multiplying
63    /// it by 2. Overflow is ignored.
64    fn mul2(&mut self);
65
66    /// Performs a leftwise bitshift of this number by some amount.
67    fn muln(&mut self, amt: u32);
68
69    /// Performs a rightwise bitshift of this number, effectively dividing
70    /// it by 2.
71    fn div2(&mut self);
72
73    /// Performs a rightwise bitshift of this number by some amount.
74    fn divn(&mut self, amt: u32);
75
76    /// Returns true iff this number is odd.
77    fn is_odd(&self) -> bool;
78
79    /// Returns true if this number is even.
80    fn is_even(&self) -> bool;
81
82    /// Returns true if this number is zero.
83    fn is_zero(&self) -> bool;
84
85    /// Compute the number of bits needed to encode this number. Always a
86    /// multiple of 64.
87    fn num_bits(&self) -> u32;
88
89    /// Compute the `i`-th bit of `self`.
90    fn get_bit(&self, i: usize) -> bool;
91
92    /// Returns the BigUint representation.
93    fn to_biguint(&self) -> BigUint;
94
95    /// Returns a vector for wnaf.
96    fn find_wnaf(&self) -> Vec<i64>;
97}
98
99pub mod arithmetic {
100    /// set a = a + b + carry, and return the new carry value.
101    #[inline(always)]
102    pub fn adc(a: &mut u64, b: u64, carry: u64) -> u64 {
103        let tmp = u128::from(*a) + u128::from(b) + u128::from(carry);
104        *a = tmp as u64;
105        (tmp >> 64) as u64
106    }
107
108    /// set a = a - b - borrow, and return the new borrow value.
109    #[inline(always)]
110    pub fn sbb(a: &mut u64, b: u64, borrow: u64) -> u64 {
111        let tmp = (1u128 << 64) + u128::from(*a) - u128::from(b) - u128::from(borrow);
112        let carry = u64::from(tmp >> 64 == 0);
113        *a = tmp as u64;
114        carry
115    }
116
117    /// Calculate a + (b * c) + carry, returning the least significant digit
118    /// and setting carry to the most significant digit.
119    #[inline(always)]
120    pub fn mac_with_carry(a: u64, b: u64, c: u64, carry: &mut u64) -> u64 {
121        let tmp = (u128::from(a)) + u128::from(b) * u128::from(c) + u128::from(*carry);
122
123        *carry = (tmp >> 64) as u64;
124
125        tmp as u64
126    }
127
128    /// Calculate a + b * c, returning the lower 64 bits of the result and setting
129    /// `carry` to the upper 64 bits.
130    #[inline(always)]
131    pub fn mac(a: u64, b: u64, c: u64, carry: &mut u64) -> u64 {
132        let tmp = (u128::from(a)) + u128::from(b) * u128::from(c);
133
134        *carry = (tmp >> 64) as u64;
135
136        tmp as u64
137    }
138
139    /// Calculate a + b * c, discarding the lower 64 bits of the result and setting
140    /// `carry` to the upper 64 bits.
141    #[inline(always)]
142    pub fn mac_discard(a: u64, b: u64, c: u64, carry: &mut u64) {
143        let tmp = (u128::from(a)) + u128::from(b) * u128::from(c);
144
145        *carry = (tmp >> 64) as u64;
146    }
147}
snarkvm_utilities/biginteger/mod.rs

snarkvm_utilities/biginteger/
mod.rs
