bigint_384.rs
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::{ 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 }