Upgrade num-bigint to 0.4.4 am: 80ddf53de8emu-34-2-dev

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/num-bigint/+/2946385

Change-Id: I53ecfbf5b6d26aa68bde139f4761850b38638ec1
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>

1 files changed, 55 insertions, 19 deletions

diff --git a/src/biguint/convert.rs b/src/biguint/convert.rs
index 5cf05cb..f19bc75 100644
--- a/src/biguint/convert.rs
+++ b/src/biguint/convert.rs
@@ -1,3 +1,6 @@
+// This uses stdlib features higher than the MSRV
+#![allow(clippy::manual_range_contains)] // 1.35
+
 use super::{biguint_from_vec, BigUint, ToBigUint};
 
 use super::addition::add2;
@@ -17,7 +20,7 @@ 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};
+use num_traits::{FromPrimitive, Num, One, PrimInt, ToPrimitive, Zero};
 
 /// Find last set bit
 /// fls(0) == 0, fls(u32::MAX) == 32
@@ -102,14 +105,20 @@ 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));
 
+    // Estimate how big the result will be, so we can pre-allocate it.
     #[cfg(feature = "std")]
-    let radix_log2 = f64::from(radix).log2();
+    let big_digits = {
+        let radix_log2 = f64::from(radix).log2();
+        let bits = radix_log2 * v.len() as f64;
+        (bits / big_digit::BITS as f64).ceil()
+    };
     #[cfg(not(feature = "std"))]
-    let radix_log2 = ilog2(radix.next_power_of_two()) as f64;
+    let big_digits = {
+        let radix_log2 = ilog2(radix.next_power_of_two()) as usize;
+        let bits = radix_log2 * v.len();
+        (bits / big_digit::BITS as usize) + 1
+    };
 
-    // 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);
@@ -281,19 +290,31 @@ fn high_bits_to_u64(v: &BigUint) -> u64 {
                 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;
+                if bits_want != 0 {
+                    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;
                 }
-                // 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;
+                // Implement round-to-odd: If any lower bits are 1, set LSB to 1
+                // so that rounding again to floating point value using
+                // nearest-ties-to-even is correct.
+                //
+                // See: https://en.wikipedia.org/wiki/Rounding#Rounding_to_prepare_for_shorter_precision
+
+                if digit_bits - bits_want != 0 {
+                    // XXX Conversion is useless if already 64-bit.
+                    #[allow(clippy::useless_conversion)]
+                    let masked = u64::from(*d) << (64 - (digit_bits - bits_want) as u32);
+                    ret |= (masked != 0) as u64;
                 }
+
+                ret_bits += bits_want;
+                bits -= bits_want;
             }
 
             ret
@@ -572,6 +593,16 @@ impl_to_biguint!(u128, FromPrimitive::from_u128);
 impl_to_biguint!(f32, FromPrimitive::from_f32);
 impl_to_biguint!(f64, FromPrimitive::from_f64);
 
+impl From<bool> for BigUint {
+    fn from(x: bool) -> Self {
+        if x {
+            One::one()
+        } else {
+            Zero::zero()
+        }
+    }
+}
+
 // 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);
@@ -647,12 +678,17 @@ 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();
+    let radix_digits = {
+        let radix_log2 = f64::from(radix).log2();
+        ((u.bits() as f64) / radix_log2).ceil()
+    };
     #[cfg(not(feature = "std"))]
-    let radix_log2 = ilog2(radix) as f64;
+    let radix_digits = {
+        let radix_log2 = ilog2(radix) as usize;
+        ((u.bits() as usize) / radix_log2) + 1
+    };
 
     // 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();