num-bigint 0.4.3

Big integer implementation for Rust
Documentation 
use super::{biguint_from_vec, BigUint, ToBigUint};

use super::addition::add2;
use super::division::div_rem_digit;
use super::multiplication::mac_with_carry;

use crate::big_digit::{self, BigDigit};
use crate::std_alloc::Vec;
use crate::ParseBigIntError;
#[cfg(has_try_from)]
use crate::TryFromBigIntError;

use core::cmp::Ordering::{Equal, Greater, Less};
#[cfg(has_try_from)]
use core::convert::TryFrom;
use core::mem;
use core::str::FromStr;
use num_integer::{Integer, Roots};
use num_traits::float::FloatCore;
use num_traits::{FromPrimitive, Num, PrimInt, ToPrimitive, Zero};

/// Find last set bit
/// fls(0) == 0, fls(u32::MAX) == 32
fn fls<T: PrimInt>(v: T) -> u8 {
    mem::size_of::<T>() as u8 * 8 - v.leading_zeros() as u8
}

fn ilog2<T: PrimInt>(v: T) -> u8 {
    fls(v) - 1
}

impl FromStr for BigUint {
    type Err = ParseBigIntError;

    #[inline]
    fn from_str(s: &str) -> Result<BigUint, ParseBigIntError> {
        BigUint::from_str_radix(s, 10)
    }
}

// Convert from a power of two radix (bits == ilog2(radix)) where bits evenly divides
// BigDigit::BITS
pub(super) fn from_bitwise_digits_le(v: &[u8], bits: u8) -> BigUint {
    debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits == 0);
    debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));

    let digits_per_big_digit = big_digit::BITS / bits;

    let data = v
        .chunks(digits_per_big_digit.into())
        .map(|chunk| {
            chunk
                .iter()
                .rev()
                .fold(0, |acc, &c| (acc << bits) | BigDigit::from(c))
        })
        .collect();

    biguint_from_vec(data)
}

// Convert from a power of two radix (bits == ilog2(radix)) where bits doesn't evenly divide
// BigDigit::BITS
fn from_inexact_bitwise_digits_le(v: &[u8], bits: u8) -> BigUint {
    debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits != 0);
    debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));

    let total_bits = (v.len() as u64).saturating_mul(bits.into());
    let big_digits = Integer::div_ceil(&total_bits, &big_digit::BITS.into())
        .to_usize()
        .unwrap_or(core::usize::MAX);
    let mut data = Vec::with_capacity(big_digits);

    let mut d = 0;
    let mut dbits = 0; // number of bits we currently have in d

    // walk v accumululating bits in d; whenever we accumulate big_digit::BITS in d, spit out a
    // big_digit:
    for &c in v {
        d |= BigDigit::from(c) << dbits;
        dbits += bits;

        if dbits >= big_digit::BITS {
            data.push(d);
            dbits -= big_digit::BITS;
            // if dbits was > big_digit::BITS, we dropped some of the bits in c (they couldn't fit
            // in d) - grab the bits we lost here:
            d = BigDigit::from(c) >> (bits - dbits);
        }
    }

    if dbits > 0 {
        debug_assert!(dbits < big_digit::BITS);
        data.push(d as BigDigit);
    }

    biguint_from_vec(data)
}

// Read little-endian radix digits
fn from_radix_digits_be(v: &[u8], radix: u32) -> BigUint {
    debug_assert!(!v.is_empty() && !radix.is_power_of_two());
    debug_assert!(v.iter().all(|&c| u32::from(c) < radix));

    #[cfg(feature = "std")]
    let radix_log2 = f64::from(radix).log2();
    #[cfg(not(feature = "std"))]
    let radix_log2 = ilog2(radix.next_power_of_two()) as f64;

    // Estimate how big the result will be, so we can pre-allocate it.
    let bits = radix_log2 * v.len() as f64;
    let big_digits = (bits / big_digit::BITS as f64).ceil();
    let mut data = Vec::with_capacity(big_digits.to_usize().unwrap_or(0));

    let (base, power) = get_radix_base(radix, big_digit::BITS);
    let radix = radix as BigDigit;

    let r = v.len() % power;
    let i = if r == 0 { power } else { r };
    let (head, tail) = v.split_at(i);

    let first = head
        .iter()
        .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
    data.push(first);

    debug_assert!(tail.len() % power == 0);
    for chunk in tail.chunks(power) {
        if data.last() != Some(&0) {
            data.push(0);
        }

        let mut carry = 0;
        for d in data.iter_mut() {
            *d = mac_with_carry(0, *d, base, &mut carry);
        }
        debug_assert!(carry == 0);

        let n = chunk
            .iter()
            .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
        add2(&mut data, &[n]);
    }

    biguint_from_vec(data)
}

pub(super) fn from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint> {
    assert!(
        2 <= radix && radix <= 256,
        "The radix must be within 2...256"
    );

    if buf.is_empty() {
        return Some(Zero::zero());
    }

    if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
        return None;
    }

    let res = if radix.is_power_of_two() {
        // Powers of two can use bitwise masks and shifting instead of multiplication
        let bits = ilog2(radix);
        let mut v = Vec::from(buf);
        v.reverse();
        if big_digit::BITS % bits == 0 {
            from_bitwise_digits_le(&v, bits)
        } else {
            from_inexact_bitwise_digits_le(&v, bits)
        }
    } else {
        from_radix_digits_be(buf, radix)
    };

    Some(res)
}

pub(super) fn from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint> {
    assert!(
        2 <= radix && radix <= 256,
        "The radix must be within 2...256"
    );

    if buf.is_empty() {
        return Some(Zero::zero());
    }

    if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
        return None;
    }

    let res = if radix.is_power_of_two() {
        // Powers of two can use bitwise masks and shifting instead of multiplication
        let bits = ilog2(radix);
        if big_digit::BITS % bits == 0 {
            from_bitwise_digits_le(buf, bits)
        } else {
            from_inexact_bitwise_digits_le(buf, bits)
        }
    } else {
        let mut v = Vec::from(buf);
        v.reverse();
        from_radix_digits_be(&v, radix)
    };

    Some(res)
}

impl Num for BigUint {
    type FromStrRadixErr = ParseBigIntError;

    /// Creates and initializes a `BigUint`.
    fn from_str_radix(s: &str, radix: u32) -> Result<BigUint, ParseBigIntError> {
        assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
        let mut s = s;
        if s.starts_with('+') {
            let tail = &s[1..];
            if !tail.starts_with('+') {
                s = tail
            }
        }

        if s.is_empty() {
            return Err(ParseBigIntError::empty());
        }

        if s.starts_with('_') {
            // Must lead with a real digit!
            return Err(ParseBigIntError::invalid());
        }

        // First normalize all characters to plain digit values
        let mut v = Vec::with_capacity(s.len());
        for b in s.bytes() {
            let d = match b {
                b'0'..=b'9' => b - b'0',
                b'a'..=b'z' => b - b'a' + 10,
                b'A'..=b'Z' => b - b'A' + 10,
                b'_' => continue,
                _ => core::u8::MAX,
            };
            if d < radix as u8 {
                v.push(d);
            } else {
                return Err(ParseBigIntError::invalid());
            }
        }

        let res = if radix.is_power_of_two() {
            // Powers of two can use bitwise masks and shifting instead of multiplication
            let bits = ilog2(radix);
            v.reverse();
            if big_digit::BITS % bits == 0 {
                from_bitwise_digits_le(&v, bits)
            } else {
                from_inexact_bitwise_digits_le(&v, bits)
            }
        } else {
            from_radix_digits_be(&v, radix)
        };
        Ok(res)
    }
}

fn high_bits_to_u64(v: &BigUint) -> u64 {
    match v.data.len() {
        0 => 0,
        1 => {
            // XXX Conversion is useless if already 64-bit.
            #[allow(clippy::useless_conversion)]
            let v0 = u64::from(v.data[0]);
            v0
        }
        _ => {
            let mut bits = v.bits();
            let mut ret = 0u64;
            let mut ret_bits = 0;

            for d in v.data.iter().rev() {
                let digit_bits = (bits - 1) % u64::from(big_digit::BITS) + 1;
                let bits_want = Ord::min(64 - ret_bits, digit_bits);

                if bits_want != 64 {
                    ret <<= bits_want;
                }
                // XXX Conversion is useless if already 64-bit.
                #[allow(clippy::useless_conversion)]
                let d0 = u64::from(*d) >> (digit_bits - bits_want);
                ret |= d0;
                ret_bits += bits_want;
                bits -= bits_want;

                if ret_bits == 64 {
                    break;
                }
            }

            ret
        }
    }
}

impl ToPrimitive for BigUint {
    #[inline]
    fn to_i64(&self) -> Option<i64> {
        self.to_u64().as_ref().and_then(u64::to_i64)
    }

    #[inline]
    fn to_i128(&self) -> Option<i128> {
        self.to_u128().as_ref().and_then(u128::to_i128)
    }

    #[allow(clippy::useless_conversion)]
    #[inline]
    fn to_u64(&self) -> Option<u64> {
        let mut ret: u64 = 0;
        let mut bits = 0;

        for i in self.data.iter() {
            if bits >= 64 {
                return None;
            }

            // XXX Conversion is useless if already 64-bit.
            ret += u64::from(*i) << bits;
            bits += big_digit::BITS;
        }

        Some(ret)
    }

    #[inline]
    fn to_u128(&self) -> Option<u128> {
        let mut ret: u128 = 0;
        let mut bits = 0;

        for i in self.data.iter() {
            if bits >= 128 {
                return None;
            }

            ret |= u128::from(*i) << bits;
            bits += big_digit::BITS;
        }

        Some(ret)
    }

    #[inline]
    fn to_f32(&self) -> Option<f32> {
        let mantissa = high_bits_to_u64(self);
        let exponent = self.bits() - u64::from(fls(mantissa));

        if exponent > core::f32::MAX_EXP as u64 {
            Some(core::f32::INFINITY)
        } else {
            Some((mantissa as f32) * 2.0f32.powi(exponent as i32))
        }
    }

    #[inline]
    fn to_f64(&self) -> Option<f64> {
        let mantissa = high_bits_to_u64(self);
        let exponent = self.bits() - u64::from(fls(mantissa));

        if exponent > core::f64::MAX_EXP as u64 {
            Some(core::f64::INFINITY)
        } else {
            Some((mantissa as f64) * 2.0f64.powi(exponent as i32))
        }
    }
}

macro_rules! impl_try_from_biguint {
    ($T:ty, $to_ty:path) => {
        #[cfg(has_try_from)]
        impl TryFrom<&BigUint> for $T {
            type Error = TryFromBigIntError<()>;

            #[inline]
            fn try_from(value: &BigUint) -> Result<$T, TryFromBigIntError<()>> {
                $to_ty(value).ok_or(TryFromBigIntError::new(()))
            }
        }

        #[cfg(has_try_from)]
        impl TryFrom<BigUint> for $T {
            type Error = TryFromBigIntError<BigUint>;

            #[inline]
            fn try_from(value: BigUint) -> Result<$T, TryFromBigIntError<BigUint>> {
                <$T>::try_from(&value).map_err(|_| TryFromBigIntError::new(value))
            }
        }
    };
}

impl_try_from_biguint!(u8, ToPrimitive::to_u8);
impl_try_from_biguint!(u16, ToPrimitive::to_u16);
impl_try_from_biguint!(u32, ToPrimitive::to_u32);
impl_try_from_biguint!(u64, ToPrimitive::to_u64);
impl_try_from_biguint!(usize, ToPrimitive::to_usize);
impl_try_from_biguint!(u128, ToPrimitive::to_u128);

impl_try_from_biguint!(i8, ToPrimitive::to_i8);
impl_try_from_biguint!(i16, ToPrimitive::to_i16);
impl_try_from_biguint!(i32, ToPrimitive::to_i32);
impl_try_from_biguint!(i64, ToPrimitive::to_i64);
impl_try_from_biguint!(isize, ToPrimitive::to_isize);
impl_try_from_biguint!(i128, ToPrimitive::to_i128);

impl FromPrimitive for BigUint {
    #[inline]
    fn from_i64(n: i64) -> Option<BigUint> {
        if n >= 0 {
            Some(BigUint::from(n as u64))
        } else {
            None
        }
    }

    #[inline]
    fn from_i128(n: i128) -> Option<BigUint> {
        if n >= 0 {
            Some(BigUint::from(n as u128))
        } else {
            None
        }
    }

    #[inline]
    fn from_u64(n: u64) -> Option<BigUint> {
        Some(BigUint::from(n))
    }

    #[inline]
    fn from_u128(n: u128) -> Option<BigUint> {
        Some(BigUint::from(n))
    }

    #[inline]
    fn from_f64(mut n: f64) -> Option<BigUint> {
        // handle NAN, INFINITY, NEG_INFINITY
        if !n.is_finite() {
            return None;
        }

        // match the rounding of casting from float to int
        n = n.trunc();

        // handle 0.x, -0.x
        if n.is_zero() {
            return Some(BigUint::zero());
        }

        let (mantissa, exponent, sign) = FloatCore::integer_decode(n);

        if sign == -1 {
            return None;
        }

        let mut ret = BigUint::from(mantissa);
        match exponent.cmp(&0) {
            Greater => ret <<= exponent as usize,
            Equal => {}
            Less => ret >>= (-exponent) as usize,
        }
        Some(ret)
    }
}

impl From<u64> for BigUint {
    #[inline]
    fn from(mut n: u64) -> Self {
        let mut ret: BigUint = Zero::zero();

        while n != 0 {
            ret.data.push(n as BigDigit);
            // don't overflow if BITS is 64:
            n = (n >> 1) >> (big_digit::BITS - 1);
        }

        ret
    }
}

impl From<u128> for BigUint {
    #[inline]
    fn from(mut n: u128) -> Self {
        let mut ret: BigUint = Zero::zero();

        while n != 0 {
            ret.data.push(n as BigDigit);
            n >>= big_digit::BITS;
        }

        ret
    }
}

macro_rules! impl_biguint_from_uint {
    ($T:ty) => {
        impl From<$T> for BigUint {
            #[inline]
            fn from(n: $T) -> Self {
                BigUint::from(n as u64)
            }
        }
    };
}

impl_biguint_from_uint!(u8);
impl_biguint_from_uint!(u16);
impl_biguint_from_uint!(u32);
impl_biguint_from_uint!(usize);

macro_rules! impl_biguint_try_from_int {
    ($T:ty, $from_ty:path) => {
        #[cfg(has_try_from)]
        impl TryFrom<$T> for BigUint {
            type Error = TryFromBigIntError<()>;

            #[inline]
            fn try_from(value: $T) -> Result<BigUint, TryFromBigIntError<()>> {
                $from_ty(value).ok_or(TryFromBigIntError::new(()))
            }
        }
    };
}

impl_biguint_try_from_int!(i8, FromPrimitive::from_i8);
impl_biguint_try_from_int!(i16, FromPrimitive::from_i16);
impl_biguint_try_from_int!(i32, FromPrimitive::from_i32);
impl_biguint_try_from_int!(i64, FromPrimitive::from_i64);
impl_biguint_try_from_int!(isize, FromPrimitive::from_isize);
impl_biguint_try_from_int!(i128, FromPrimitive::from_i128);

impl ToBigUint for BigUint {
    #[inline]
    fn to_biguint(&self) -> Option<BigUint> {
        Some(self.clone())
    }
}

macro_rules! impl_to_biguint {
    ($T:ty, $from_ty:path) => {
        impl ToBigUint for $T {
            #[inline]
            fn to_biguint(&self) -> Option<BigUint> {
                $from_ty(*self)
            }
        }
    };
}

impl_to_biguint!(isize, FromPrimitive::from_isize);
impl_to_biguint!(i8, FromPrimitive::from_i8);
impl_to_biguint!(i16, FromPrimitive::from_i16);
impl_to_biguint!(i32, FromPrimitive::from_i32);
impl_to_biguint!(i64, FromPrimitive::from_i64);
impl_to_biguint!(i128, FromPrimitive::from_i128);

impl_to_biguint!(usize, FromPrimitive::from_usize);
impl_to_biguint!(u8, FromPrimitive::from_u8);
impl_to_biguint!(u16, FromPrimitive::from_u16);
impl_to_biguint!(u32, FromPrimitive::from_u32);
impl_to_biguint!(u64, FromPrimitive::from_u64);
impl_to_biguint!(u128, FromPrimitive::from_u128);

impl_to_biguint!(f32, FromPrimitive::from_f32);
impl_to_biguint!(f64, FromPrimitive::from_f64);

// Extract bitwise digits that evenly divide BigDigit
pub(super) fn to_bitwise_digits_le(u: &BigUint, bits: u8) -> Vec<u8> {
    debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits == 0);

    let last_i = u.data.len() - 1;
    let mask: BigDigit = (1 << bits) - 1;
    let digits_per_big_digit = big_digit::BITS / bits;
    let digits = Integer::div_ceil(&u.bits(), &u64::from(bits))
        .to_usize()
        .unwrap_or(core::usize::MAX);
    let mut res = Vec::with_capacity(digits);

    for mut r in u.data[..last_i].iter().cloned() {
        for _ in 0..digits_per_big_digit {
            res.push((r & mask) as u8);
            r >>= bits;
        }
    }

    let mut r = u.data[last_i];
    while r != 0 {
        res.push((r & mask) as u8);
        r >>= bits;
    }

    res
}

// Extract bitwise digits that don't evenly divide BigDigit
fn to_inexact_bitwise_digits_le(u: &BigUint, bits: u8) -> Vec<u8> {
    debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits != 0);

    let mask: BigDigit = (1 << bits) - 1;
    let digits = Integer::div_ceil(&u.bits(), &u64::from(bits))
        .to_usize()
        .unwrap_or(core::usize::MAX);
    let mut res = Vec::with_capacity(digits);

    let mut r = 0;
    let mut rbits = 0;

    for c in &u.data {
        r |= *c << rbits;
        rbits += big_digit::BITS;

        while rbits >= bits {
            res.push((r & mask) as u8);
            r >>= bits;

            // r had more bits than it could fit - grab the bits we lost
            if rbits > big_digit::BITS {
                r = *c >> (big_digit::BITS - (rbits - bits));
            }

            rbits -= bits;
        }
    }

    if rbits != 0 {
        res.push(r as u8);
    }

    while let Some(&0) = res.last() {
        res.pop();
    }

    res
}

// Extract little-endian radix digits
#[inline(always)] // forced inline to get const-prop for radix=10
pub(super) fn to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8> {
    debug_assert!(!u.is_zero() && !radix.is_power_of_two());

    #[cfg(feature = "std")]
    let radix_log2 = f64::from(radix).log2();
    #[cfg(not(feature = "std"))]
    let radix_log2 = ilog2(radix) as f64;

    // Estimate how big the result will be, so we can pre-allocate it.
    let radix_digits = ((u.bits() as f64) / radix_log2).ceil();
    let mut res = Vec::with_capacity(radix_digits.to_usize().unwrap_or(0));

    let mut digits = u.clone();

    let (base, power) = get_radix_base(radix, big_digit::HALF_BITS);
    let radix = radix as BigDigit;

    // For very large numbers, the O(n²) loop of repeated `div_rem_digit` dominates the
    // performance. We can mitigate this by dividing into chunks of a larger base first.
    // The threshold for this was chosen by anecdotal performance measurements to
    // approximate where this starts to make a noticeable difference.
    if digits.data.len() >= 64 {
        let mut big_base = BigUint::from(base * base);
        let mut big_power = 2usize;

        // Choose a target base length near √n.
        let target_len = digits.data.len().sqrt();
        while big_base.data.len() < target_len {
            big_base = &big_base * &big_base;
            big_power *= 2;
        }

        // This outer loop will run approximately √n times.
        while digits > big_base {
            // This is still the dominating factor, with n digits divided by √n digits.
            let (q, mut big_r) = digits.div_rem(&big_base);
            digits = q;

            // This inner loop now has O(√n²)=O(n) behavior altogether.
            for _ in 0..big_power {
                let (q, mut r) = div_rem_digit(big_r, base);
                big_r = q;
                for _ in 0..power {
                    res.push((r % radix) as u8);
                    r /= radix;
                }
            }
        }
    }

    while digits.data.len() > 1 {
        let (q, mut r) = div_rem_digit(digits, base);
        for _ in 0..power {
            res.push((r % radix) as u8);
            r /= radix;
        }
        digits = q;
    }

    let mut r = digits.data[0];
    while r != 0 {
        res.push((r % radix) as u8);
        r /= radix;
    }

    res
}

pub(super) fn to_radix_le(u: &BigUint, radix: u32) -> Vec<u8> {
    if u.is_zero() {
        vec![0]
    } else if radix.is_power_of_two() {
        // Powers of two can use bitwise masks and shifting instead of division
        let bits = ilog2(radix);
        if big_digit::BITS % bits == 0 {
            to_bitwise_digits_le(u, bits)
        } else {
            to_inexact_bitwise_digits_le(u, bits)
        }
    } else if radix == 10 {
        // 10 is so common that it's worth separating out for const-propagation.
        // Optimizers can often turn constant division into a faster multiplication.
        to_radix_digits_le(u, 10)
    } else {
        to_radix_digits_le(u, radix)
    }
}

pub(crate) fn to_str_radix_reversed(u: &BigUint, radix: u32) -> Vec<u8> {
    assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");

    if u.is_zero() {
        return vec![b'0'];
    }

    let mut res = to_radix_le(u, radix);

    // Now convert everything to ASCII digits.
    for r in &mut res {
        debug_assert!(u32::from(*r) < radix);
        if *r < 10 {
            *r += b'0';
        } else {
            *r += b'a' - 10;
        }
    }
    res
}

/// Returns the greatest power of the radix for the given bit size
#[inline]
fn get_radix_base(radix: u32, bits: u8) -> (BigDigit, usize) {
    mod gen {
        include! { concat!(env!("OUT_DIR"), "/radix_bases.rs") }
    }

    debug_assert!(
        2 <= radix && radix <= 256,
        "The radix must be within 2...256"
    );
    debug_assert!(!radix.is_power_of_two());
    debug_assert!(bits <= big_digit::BITS);

    match bits {
        16 => {
            let (base, power) = gen::BASES_16[radix as usize];
            (base as BigDigit, power)
        }
        32 => {
            let (base, power) = gen::BASES_32[radix as usize];
            (base as BigDigit, power)
        }
        64 => {
            let (base, power) = gen::BASES_64[radix as usize];
            (base as BigDigit, power)
        }
        _ => panic!("Invalid bigdigit size"),
    }
}