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