use super::Sign::{self, Minus, NoSign, Plus}; use super::{BigInt, ToBigInt}; use crate::std_alloc::Vec; #[cfg(has_try_from)] use crate::TryFromBigIntError; use crate::{BigUint, ParseBigIntError, ToBigUint}; use core::cmp::Ordering::{Equal, Greater, Less}; #[cfg(has_try_from)] use core::convert::TryFrom; use core::str::{self, FromStr}; use num_traits::{FromPrimitive, Num, One, ToPrimitive, Zero}; impl FromStr for BigInt { type Err = ParseBigIntError; #[inline] fn from_str(s: &str) -> Result { BigInt::from_str_radix(s, 10) } } impl Num for BigInt { type FromStrRadixErr = ParseBigIntError; /// Creates and initializes a [`BigInt`]. #[inline] fn from_str_radix(mut s: &str, radix: u32) -> Result { let sign = if s.starts_with('-') { let tail = &s[1..]; if !tail.starts_with('+') { s = tail } Minus } else { Plus }; let bu = BigUint::from_str_radix(s, radix)?; Ok(BigInt::from_biguint(sign, bu)) } } impl ToPrimitive for BigInt { #[inline] fn to_i64(&self) -> Option { match self.sign { Plus => self.data.to_i64(), NoSign => Some(0), Minus => { let n = self.data.to_u64()?; let m: u64 = 1 << 63; match n.cmp(&m) { Less => Some(-(n as i64)), Equal => Some(core::i64::MIN), Greater => None, } } } } #[inline] fn to_i128(&self) -> Option { match self.sign { Plus => self.data.to_i128(), NoSign => Some(0), Minus => { let n = self.data.to_u128()?; let m: u128 = 1 << 127; match n.cmp(&m) { Less => Some(-(n as i128)), Equal => Some(core::i128::MIN), Greater => None, } } } } #[inline] fn to_u64(&self) -> Option { match self.sign { Plus => self.data.to_u64(), NoSign => Some(0), Minus => None, } } #[inline] fn to_u128(&self) -> Option { match self.sign { Plus => self.data.to_u128(), NoSign => Some(0), Minus => None, } } #[inline] fn to_f32(&self) -> Option { let n = self.data.to_f32()?; Some(if self.sign == Minus { -n } else { n }) } #[inline] fn to_f64(&self) -> Option { let n = self.data.to_f64()?; Some(if self.sign == Minus { -n } else { n }) } } macro_rules! impl_try_from_bigint { ($T:ty, $to_ty:path) => { #[cfg(has_try_from)] impl TryFrom<&BigInt> for $T { type Error = TryFromBigIntError<()>; #[inline] fn try_from(value: &BigInt) -> Result<$T, TryFromBigIntError<()>> { $to_ty(value).ok_or(TryFromBigIntError::new(())) } } #[cfg(has_try_from)] impl TryFrom for $T { type Error = TryFromBigIntError; #[inline] fn try_from(value: BigInt) -> Result<$T, TryFromBigIntError> { <$T>::try_from(&value).map_err(|_| TryFromBigIntError::new(value)) } } }; } impl_try_from_bigint!(u8, ToPrimitive::to_u8); impl_try_from_bigint!(u16, ToPrimitive::to_u16); impl_try_from_bigint!(u32, ToPrimitive::to_u32); impl_try_from_bigint!(u64, ToPrimitive::to_u64); impl_try_from_bigint!(usize, ToPrimitive::to_usize); impl_try_from_bigint!(u128, ToPrimitive::to_u128); impl_try_from_bigint!(i8, ToPrimitive::to_i8); impl_try_from_bigint!(i16, ToPrimitive::to_i16); impl_try_from_bigint!(i32, ToPrimitive::to_i32); impl_try_from_bigint!(i64, ToPrimitive::to_i64); impl_try_from_bigint!(isize, ToPrimitive::to_isize); impl_try_from_bigint!(i128, ToPrimitive::to_i128); impl FromPrimitive for BigInt { #[inline] fn from_i64(n: i64) -> Option { Some(BigInt::from(n)) } #[inline] fn from_i128(n: i128) -> Option { Some(BigInt::from(n)) } #[inline] fn from_u64(n: u64) -> Option { Some(BigInt::from(n)) } #[inline] fn from_u128(n: u128) -> Option { Some(BigInt::from(n)) } #[inline] fn from_f64(n: f64) -> Option { if n >= 0.0 { BigUint::from_f64(n).map(BigInt::from) } else { let x = BigUint::from_f64(-n)?; Some(-BigInt::from(x)) } } } impl From for BigInt { #[inline] fn from(n: i64) -> Self { if n >= 0 { BigInt::from(n as u64) } else { let u = core::u64::MAX - (n as u64) + 1; BigInt { sign: Minus, data: BigUint::from(u), } } } } impl From for BigInt { #[inline] fn from(n: i128) -> Self { if n >= 0 { BigInt::from(n as u128) } else { let u = core::u128::MAX - (n as u128) + 1; BigInt { sign: Minus, data: BigUint::from(u), } } } } macro_rules! impl_bigint_from_int { ($T:ty) => { impl From<$T> for BigInt { #[inline] fn from(n: $T) -> Self { BigInt::from(n as i64) } } }; } impl_bigint_from_int!(i8); impl_bigint_from_int!(i16); impl_bigint_from_int!(i32); impl_bigint_from_int!(isize); impl From for BigInt { #[inline] fn from(n: u64) -> Self { if n > 0 { BigInt { sign: Plus, data: BigUint::from(n), } } else { BigInt::zero() } } } impl From for BigInt { #[inline] fn from(n: u128) -> Self { if n > 0 { BigInt { sign: Plus, data: BigUint::from(n), } } else { BigInt::zero() } } } macro_rules! impl_bigint_from_uint { ($T:ty) => { impl From<$T> for BigInt { #[inline] fn from(n: $T) -> Self { BigInt::from(n as u64) } } }; } impl_bigint_from_uint!(u8); impl_bigint_from_uint!(u16); impl_bigint_from_uint!(u32); impl_bigint_from_uint!(usize); impl From for BigInt { #[inline] fn from(n: BigUint) -> Self { if n.is_zero() { BigInt::zero() } else { BigInt { sign: Plus, data: n, } } } } impl ToBigInt for BigInt { #[inline] fn to_bigint(&self) -> Option { Some(self.clone()) } } impl ToBigInt for BigUint { #[inline] fn to_bigint(&self) -> Option { if self.is_zero() { Some(Zero::zero()) } else { Some(BigInt { sign: Plus, data: self.clone(), }) } } } impl ToBigUint for BigInt { #[inline] fn to_biguint(&self) -> Option { match self.sign() { Plus => Some(self.data.clone()), NoSign => Some(Zero::zero()), Minus => None, } } } #[cfg(has_try_from)] impl TryFrom<&BigInt> for BigUint { type Error = TryFromBigIntError<()>; #[inline] fn try_from(value: &BigInt) -> Result> { value .to_biguint() .ok_or_else(|| TryFromBigIntError::new(())) } } #[cfg(has_try_from)] impl TryFrom for BigUint { type Error = TryFromBigIntError; #[inline] fn try_from(value: BigInt) -> Result> { if value.sign() == Sign::Minus { Err(TryFromBigIntError::new(value)) } else { Ok(value.data) } } } macro_rules! impl_to_bigint { ($T:ty, $from_ty:path) => { impl ToBigInt for $T { #[inline] fn to_bigint(&self) -> Option { $from_ty(*self) } } }; } impl_to_bigint!(isize, FromPrimitive::from_isize); impl_to_bigint!(i8, FromPrimitive::from_i8); impl_to_bigint!(i16, FromPrimitive::from_i16); impl_to_bigint!(i32, FromPrimitive::from_i32); impl_to_bigint!(i64, FromPrimitive::from_i64); impl_to_bigint!(i128, FromPrimitive::from_i128); impl_to_bigint!(usize, FromPrimitive::from_usize); impl_to_bigint!(u8, FromPrimitive::from_u8); impl_to_bigint!(u16, FromPrimitive::from_u16); impl_to_bigint!(u32, FromPrimitive::from_u32); impl_to_bigint!(u64, FromPrimitive::from_u64); impl_to_bigint!(u128, FromPrimitive::from_u128); impl_to_bigint!(f32, FromPrimitive::from_f32); impl_to_bigint!(f64, FromPrimitive::from_f64); impl From for BigInt { fn from(x: bool) -> Self { if x { One::one() } else { Zero::zero() } } } #[inline] pub(super) fn from_signed_bytes_be(digits: &[u8]) -> BigInt { let sign = match digits.first() { Some(v) if *v > 0x7f => Sign::Minus, Some(_) => Sign::Plus, None => return BigInt::zero(), }; if sign == Sign::Minus { // two's-complement the content to retrieve the magnitude let mut digits = Vec::from(digits); twos_complement_be(&mut digits); BigInt::from_biguint(sign, BigUint::from_bytes_be(&digits)) } else { BigInt::from_biguint(sign, BigUint::from_bytes_be(digits)) } } #[inline] pub(super) fn from_signed_bytes_le(digits: &[u8]) -> BigInt { let sign = match digits.last() { Some(v) if *v > 0x7f => Sign::Minus, Some(_) => Sign::Plus, None => return BigInt::zero(), }; if sign == Sign::Minus { // two's-complement the content to retrieve the magnitude let mut digits = Vec::from(digits); twos_complement_le(&mut digits); BigInt::from_biguint(sign, BigUint::from_bytes_le(&digits)) } else { BigInt::from_biguint(sign, BigUint::from_bytes_le(digits)) } } #[inline] pub(super) fn to_signed_bytes_be(x: &BigInt) -> Vec { let mut bytes = x.data.to_bytes_be(); let first_byte = bytes.first().cloned().unwrap_or(0); if first_byte > 0x7f && !(first_byte == 0x80 && bytes.iter().skip(1).all(Zero::is_zero) && x.sign == Sign::Minus) { // msb used by magnitude, extend by 1 byte bytes.insert(0, 0); } if x.sign == Sign::Minus { twos_complement_be(&mut bytes); } bytes } #[inline] pub(super) fn to_signed_bytes_le(x: &BigInt) -> Vec { let mut bytes = x.data.to_bytes_le(); let last_byte = bytes.last().cloned().unwrap_or(0); if last_byte > 0x7f && !(last_byte == 0x80 && bytes.iter().rev().skip(1).all(Zero::is_zero) && x.sign == Sign::Minus) { // msb used by magnitude, extend by 1 byte bytes.push(0); } if x.sign == Sign::Minus { twos_complement_le(&mut bytes); } bytes } /// Perform in-place two's complement of the given binary representation, /// in little-endian byte order. #[inline] fn twos_complement_le(digits: &mut [u8]) { twos_complement(digits) } /// Perform in-place two's complement of the given binary representation /// in big-endian byte order. #[inline] fn twos_complement_be(digits: &mut [u8]) { twos_complement(digits.iter_mut().rev()) } /// Perform in-place two's complement of the given digit iterator /// starting from the least significant byte. #[inline] fn twos_complement<'a, I>(digits: I) where I: IntoIterator, { let mut carry = true; for d in digits { *d = !*d; if carry { *d = d.wrapping_add(1); carry = d.is_zero(); } } }