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