1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the deltavm 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  
 16  use crate::{FromBits, FromBytes, ToBits, ToBytes, rand::Uniform};
 17  
 18  use num_bigint::BigUint;
 19  use std::fmt::{Debug, Display};
 20  
 21  mod bigint_256;
 22  pub use bigint_256::*;
 23  
 24  mod bigint_384;
 25  pub use bigint_384::*;
 26  
 27  #[cfg(test)]
 28  mod tests;
 29  
 30  /// This defines a `BigInteger`, a smart wrapper around a
 31  /// sequence of `u64` limbs, least-significant digit first.
 32  pub 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  
 99  pub 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  }