summaryrefslogtreecommitdiffstats
path: root/third_party/rust/num-bigint/tests
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/num-bigint/tests')
-rw-r--r--third_party/rust/num-bigint/tests/bigint.rs1193
-rw-r--r--third_party/rust/num-bigint/tests/bigint_bitwise.rs181
-rw-r--r--third_party/rust/num-bigint/tests/bigint_scalar.rs145
-rw-r--r--third_party/rust/num-bigint/tests/biguint.rs1713
-rw-r--r--third_party/rust/num-bigint/tests/biguint_scalar.rs109
-rw-r--r--third_party/rust/num-bigint/tests/consts/mod.rs56
-rw-r--r--third_party/rust/num-bigint/tests/macros/mod.rs70
-rw-r--r--third_party/rust/num-bigint/tests/modpow.rs150
-rw-r--r--third_party/rust/num-bigint/tests/quickcheck.rs317
-rw-r--r--third_party/rust/num-bigint/tests/rand.rs324
-rw-r--r--third_party/rust/num-bigint/tests/roots.rs186
-rw-r--r--third_party/rust/num-bigint/tests/serde.rs103
-rw-r--r--third_party/rust/num-bigint/tests/torture.rs43
13 files changed, 4590 insertions, 0 deletions
diff --git a/third_party/rust/num-bigint/tests/bigint.rs b/third_party/rust/num-bigint/tests/bigint.rs
new file mode 100644
index 0000000000..911bff0020
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/bigint.rs
@@ -0,0 +1,1193 @@
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+#[cfg(feature = "rand")]
+extern crate rand;
+
+use num_bigint::BigUint;
+use num_bigint::Sign::{Minus, NoSign, Plus};
+use num_bigint::{BigInt, ToBigInt};
+
+use std::cmp::Ordering::{Equal, Greater, Less};
+use std::collections::hash_map::RandomState;
+use std::hash::{BuildHasher, Hash, Hasher};
+use std::iter::repeat;
+use std::ops::Neg;
+use std::{f32, f64};
+#[cfg(has_i128)]
+use std::{i128, u128};
+use std::{i16, i32, i64, i8, isize};
+use std::{u16, u32, u64, u8, usize};
+
+use num_integer::Integer;
+use num_traits::{Float, FromPrimitive, Num, One, Pow, Signed, ToPrimitive, Zero};
+
+mod consts;
+use consts::*;
+
+#[macro_use]
+mod macros;
+
+#[test]
+fn test_from_bytes_be() {
+ fn check(s: &str, result: &str) {
+ assert_eq!(
+ BigInt::from_bytes_be(Plus, s.as_bytes()),
+ BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
+ );
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("AB", "16706");
+ check("Hello world!", "22405534230753963835153736737");
+ assert_eq!(BigInt::from_bytes_be(Plus, &[]), Zero::zero());
+ assert_eq!(BigInt::from_bytes_be(Minus, &[]), Zero::zero());
+}
+
+#[test]
+fn test_to_bytes_be() {
+ fn check(s: &str, result: &str) {
+ let b = BigInt::parse_bytes(result.as_bytes(), 10).unwrap();
+ let (sign, v) = b.to_bytes_be();
+ assert_eq!((Plus, s.as_bytes()), (sign, &*v));
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("AB", "16706");
+ check("Hello world!", "22405534230753963835153736737");
+ let b: BigInt = Zero::zero();
+ assert_eq!(b.to_bytes_be(), (NoSign, vec![0]));
+
+ // Test with leading/trailing zero bytes and a full BigDigit of value 0
+ let b = BigInt::from_str_radix("00010000000000000200", 16).unwrap();
+ assert_eq!(b.to_bytes_be(), (Plus, vec![1, 0, 0, 0, 0, 0, 0, 2, 0]));
+}
+
+#[test]
+fn test_from_bytes_le() {
+ fn check(s: &str, result: &str) {
+ assert_eq!(
+ BigInt::from_bytes_le(Plus, s.as_bytes()),
+ BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
+ );
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("BA", "16706");
+ check("!dlrow olleH", "22405534230753963835153736737");
+ assert_eq!(BigInt::from_bytes_le(Plus, &[]), Zero::zero());
+ assert_eq!(BigInt::from_bytes_le(Minus, &[]), Zero::zero());
+}
+
+#[test]
+fn test_to_bytes_le() {
+ fn check(s: &str, result: &str) {
+ let b = BigInt::parse_bytes(result.as_bytes(), 10).unwrap();
+ let (sign, v) = b.to_bytes_le();
+ assert_eq!((Plus, s.as_bytes()), (sign, &*v));
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("BA", "16706");
+ check("!dlrow olleH", "22405534230753963835153736737");
+ let b: BigInt = Zero::zero();
+ assert_eq!(b.to_bytes_le(), (NoSign, vec![0]));
+
+ // Test with leading/trailing zero bytes and a full BigDigit of value 0
+ let b = BigInt::from_str_radix("00010000000000000200", 16).unwrap();
+ assert_eq!(b.to_bytes_le(), (Plus, vec![0, 2, 0, 0, 0, 0, 0, 0, 1]));
+}
+
+#[test]
+fn test_to_signed_bytes_le() {
+ fn check(s: &str, result: Vec<u8>) {
+ assert_eq!(
+ BigInt::parse_bytes(s.as_bytes(), 10)
+ .unwrap()
+ .to_signed_bytes_le(),
+ result
+ );
+ }
+
+ check("0", vec![0]);
+ check("32767", vec![0xff, 0x7f]);
+ check("-1", vec![0xff]);
+ check("16777216", vec![0, 0, 0, 1]);
+ check("-100", vec![156]);
+ check("-8388608", vec![0, 0, 0x80]);
+ check("-192", vec![0x40, 0xff]);
+ check("128", vec![0x80, 0])
+}
+
+#[test]
+fn test_from_signed_bytes_le() {
+ fn check(s: &[u8], result: &str) {
+ assert_eq!(
+ BigInt::from_signed_bytes_le(s),
+ BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
+ );
+ }
+
+ check(&[], "0");
+ check(&[0], "0");
+ check(&[0; 10], "0");
+ check(&[0xff, 0x7f], "32767");
+ check(&[0xff], "-1");
+ check(&[0, 0, 0, 1], "16777216");
+ check(&[156], "-100");
+ check(&[0, 0, 0x80], "-8388608");
+ check(&[0xff; 10], "-1");
+ check(&[0x40, 0xff], "-192");
+}
+
+#[test]
+fn test_to_signed_bytes_be() {
+ fn check(s: &str, result: Vec<u8>) {
+ assert_eq!(
+ BigInt::parse_bytes(s.as_bytes(), 10)
+ .unwrap()
+ .to_signed_bytes_be(),
+ result
+ );
+ }
+
+ check("0", vec![0]);
+ check("32767", vec![0x7f, 0xff]);
+ check("-1", vec![255]);
+ check("16777216", vec![1, 0, 0, 0]);
+ check("-100", vec![156]);
+ check("-8388608", vec![128, 0, 0]);
+ check("-192", vec![0xff, 0x40]);
+ check("128", vec![0, 0x80]);
+}
+
+#[test]
+fn test_from_signed_bytes_be() {
+ fn check(s: &[u8], result: &str) {
+ assert_eq!(
+ BigInt::from_signed_bytes_be(s),
+ BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
+ );
+ }
+
+ check(&[], "0");
+ check(&[0], "0");
+ check(&[0; 10], "0");
+ check(&[127, 255], "32767");
+ check(&[255], "-1");
+ check(&[1, 0, 0, 0], "16777216");
+ check(&[156], "-100");
+ check(&[128, 0, 0], "-8388608");
+ check(&[255; 10], "-1");
+ check(&[0xff, 0x40], "-192");
+}
+
+#[test]
+fn test_signed_bytes_be_round_trip() {
+ for i in -0x1FFFF..0x20000 {
+ let n = BigInt::from(i);
+ assert_eq!(n, BigInt::from_signed_bytes_be(&n.to_signed_bytes_be()));
+ }
+}
+
+#[test]
+fn test_signed_bytes_le_round_trip() {
+ for i in -0x1FFFF..0x20000 {
+ let n = BigInt::from(i);
+ assert_eq!(n, BigInt::from_signed_bytes_le(&n.to_signed_bytes_le()));
+ }
+}
+
+#[test]
+fn test_cmp() {
+ let vs: [&[u32]; 4] = [&[2 as u32], &[1, 1], &[2, 1], &[1, 1, 1]];
+ let mut nums = Vec::new();
+ for s in vs.iter().rev() {
+ nums.push(BigInt::from_slice(Minus, *s));
+ }
+ nums.push(Zero::zero());
+ nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
+
+ for (i, ni) in nums.iter().enumerate() {
+ for (j0, nj) in nums[i..].iter().enumerate() {
+ let j = i + j0;
+ if i == j {
+ assert_eq!(ni.cmp(nj), Equal);
+ assert_eq!(nj.cmp(ni), Equal);
+ assert_eq!(ni, nj);
+ assert!(!(ni != nj));
+ assert!(ni <= nj);
+ assert!(ni >= nj);
+ assert!(!(ni < nj));
+ assert!(!(ni > nj));
+ } else {
+ assert_eq!(ni.cmp(nj), Less);
+ assert_eq!(nj.cmp(ni), Greater);
+
+ assert!(!(ni == nj));
+ assert!(ni != nj);
+
+ assert!(ni <= nj);
+ assert!(!(ni >= nj));
+ assert!(ni < nj);
+ assert!(!(ni > nj));
+
+ assert!(!(nj <= ni));
+ assert!(nj >= ni);
+ assert!(!(nj < ni));
+ assert!(nj > ni);
+ }
+ }
+ }
+}
+
+fn hash<T: Hash>(x: &T) -> u64 {
+ let mut hasher = <RandomState as BuildHasher>::Hasher::new();
+ x.hash(&mut hasher);
+ hasher.finish()
+}
+
+#[test]
+fn test_hash() {
+ let a = BigInt::new(NoSign, vec![]);
+ let b = BigInt::new(NoSign, vec![0]);
+ let c = BigInt::new(Plus, vec![1]);
+ let d = BigInt::new(Plus, vec![1, 0, 0, 0, 0, 0]);
+ let e = BigInt::new(Plus, vec![0, 0, 0, 0, 0, 1]);
+ let f = BigInt::new(Minus, vec![1]);
+ assert!(hash(&a) == hash(&b));
+ assert!(hash(&b) != hash(&c));
+ assert!(hash(&c) == hash(&d));
+ assert!(hash(&d) != hash(&e));
+ assert!(hash(&c) != hash(&f));
+}
+
+#[test]
+fn test_convert_i64() {
+ fn check(b1: BigInt, i: i64) {
+ let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
+ assert!(b1 == b2);
+ assert!(b1.to_i64().unwrap() == i);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(i64::MIN.to_bigint().unwrap(), i64::MIN);
+ check(i64::MAX.to_bigint().unwrap(), i64::MAX);
+
+ assert_eq!((i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(), None);
+
+ assert_eq!(
+ BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i64(),
+ None
+ );
+
+ assert_eq!(
+ BigInt::from_biguint(Minus, BigUint::new(vec![1, 0, 0, 1 << 31])).to_i64(),
+ None
+ );
+
+ assert_eq!(
+ BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i64(),
+ None
+ );
+}
+
+#[test]
+#[cfg(has_i128)]
+fn test_convert_i128() {
+ fn check(b1: BigInt, i: i128) {
+ let b2: BigInt = FromPrimitive::from_i128(i).unwrap();
+ assert!(b1 == b2);
+ assert!(b1.to_i128().unwrap() == i);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(i128::MIN.to_bigint().unwrap(), i128::MIN);
+ check(i128::MAX.to_bigint().unwrap(), i128::MAX);
+
+ assert_eq!((i128::MAX as u128 + 1).to_bigint().unwrap().to_i128(), None);
+
+ assert_eq!(
+ BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i128(),
+ None
+ );
+
+ assert_eq!(
+ BigInt::from_biguint(Minus, BigUint::new(vec![1, 0, 0, 1 << 31])).to_i128(),
+ None
+ );
+
+ assert_eq!(
+ BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i128(),
+ None
+ );
+}
+
+#[test]
+fn test_convert_u64() {
+ fn check(b1: BigInt, u: u64) {
+ let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
+ assert!(b1 == b2);
+ assert!(b1.to_u64().unwrap() == u);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(u64::MIN.to_bigint().unwrap(), u64::MIN);
+ check(u64::MAX.to_bigint().unwrap(), u64::MAX);
+
+ assert_eq!(
+ BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u64(),
+ None
+ );
+
+ let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
+ assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
+ assert_eq!(
+ BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u64(),
+ None
+ );
+}
+
+#[test]
+#[cfg(has_i128)]
+fn test_convert_u128() {
+ fn check(b1: BigInt, u: u128) {
+ let b2: BigInt = FromPrimitive::from_u128(u).unwrap();
+ assert!(b1 == b2);
+ assert!(b1.to_u128().unwrap() == u);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(u128::MIN.to_bigint().unwrap(), u128::MIN);
+ check(u128::MAX.to_bigint().unwrap(), u128::MAX);
+
+ assert_eq!(
+ BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u128(),
+ None
+ );
+
+ let max_value: BigUint = FromPrimitive::from_u128(u128::MAX).unwrap();
+ assert_eq!(BigInt::from_biguint(Minus, max_value).to_u128(), None);
+ assert_eq!(
+ BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u128(),
+ None
+ );
+}
+
+#[test]
+fn test_convert_f32() {
+ fn check(b1: &BigInt, f: f32) {
+ let b2 = BigInt::from_f32(f).unwrap();
+ assert_eq!(b1, &b2);
+ assert_eq!(b1.to_f32().unwrap(), f);
+ let neg_b1 = -b1;
+ let neg_b2 = BigInt::from_f32(-f).unwrap();
+ assert_eq!(neg_b1, neg_b2);
+ assert_eq!(neg_b1.to_f32().unwrap(), -f);
+ }
+
+ check(&BigInt::zero(), 0.0);
+ check(&BigInt::one(), 1.0);
+ check(&BigInt::from(u16::MAX), 2.0.powi(16) - 1.0);
+ check(&BigInt::from(1u64 << 32), 2.0.powi(32));
+ check(&BigInt::from_slice(Plus, &[0, 0, 1]), 2.0.powi(64));
+ check(
+ &((BigInt::one() << 100) + (BigInt::one() << 123)),
+ 2.0.powi(100) + 2.0.powi(123),
+ );
+ check(&(BigInt::one() << 127), 2.0.powi(127));
+ check(&(BigInt::from((1u64 << 24) - 1) << (128 - 24)), f32::MAX);
+
+ // keeping all 24 digits with the bits at different offsets to the BigDigits
+ let x: u32 = 0b00000000101111011111011011011101;
+ let mut f = x as f32;
+ let mut b = BigInt::from(x);
+ for _ in 0..64 {
+ check(&b, f);
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // this number when rounded to f64 then f32 isn't the same as when rounded straight to f32
+ let mut n: i64 = 0b0000000000111111111111111111111111011111111111111111111111111111;
+ assert!((n as f64) as f32 != n as f32);
+ assert_eq!(BigInt::from(n).to_f32(), Some(n as f32));
+ n = -n;
+ assert!((n as f64) as f32 != n as f32);
+ assert_eq!(BigInt::from(n).to_f32(), Some(n as f32));
+
+ // test rounding up with the bits at different offsets to the BigDigits
+ let mut f = ((1u64 << 25) - 1) as f32;
+ let mut b = BigInt::from(1u64 << 25);
+ for _ in 0..64 {
+ assert_eq!(b.to_f32(), Some(f));
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // rounding
+ assert_eq!(
+ BigInt::from_f32(-f32::consts::PI),
+ Some(BigInt::from(-3i32))
+ );
+ assert_eq!(BigInt::from_f32(-f32::consts::E), Some(BigInt::from(-2i32)));
+ assert_eq!(BigInt::from_f32(-0.99999), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f32(-0.5), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f32(-0.0), Some(BigInt::zero()));
+ assert_eq!(
+ BigInt::from_f32(f32::MIN_POSITIVE / 2.0),
+ Some(BigInt::zero())
+ );
+ assert_eq!(BigInt::from_f32(f32::MIN_POSITIVE), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f32(0.5), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f32(0.99999), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f32(f32::consts::E), Some(BigInt::from(2u32)));
+ assert_eq!(BigInt::from_f32(f32::consts::PI), Some(BigInt::from(3u32)));
+
+ // special float values
+ assert_eq!(BigInt::from_f32(f32::NAN), None);
+ assert_eq!(BigInt::from_f32(f32::INFINITY), None);
+ assert_eq!(BigInt::from_f32(f32::NEG_INFINITY), None);
+
+ // largest BigInt that will round to a finite f32 value
+ let big_num = (BigInt::one() << 128) - BigInt::one() - (BigInt::one() << (128 - 25));
+ assert_eq!(big_num.to_f32(), Some(f32::MAX));
+ assert_eq!((&big_num + BigInt::one()).to_f32(), None);
+ assert_eq!((-&big_num).to_f32(), Some(f32::MIN));
+ assert_eq!(((-&big_num) - BigInt::one()).to_f32(), None);
+
+ assert_eq!(((BigInt::one() << 128) - BigInt::one()).to_f32(), None);
+ assert_eq!((BigInt::one() << 128).to_f32(), None);
+ assert_eq!((-((BigInt::one() << 128) - BigInt::one())).to_f32(), None);
+ assert_eq!((-(BigInt::one() << 128)).to_f32(), None);
+}
+
+#[test]
+fn test_convert_f64() {
+ fn check(b1: &BigInt, f: f64) {
+ let b2 = BigInt::from_f64(f).unwrap();
+ assert_eq!(b1, &b2);
+ assert_eq!(b1.to_f64().unwrap(), f);
+ let neg_b1 = -b1;
+ let neg_b2 = BigInt::from_f64(-f).unwrap();
+ assert_eq!(neg_b1, neg_b2);
+ assert_eq!(neg_b1.to_f64().unwrap(), -f);
+ }
+
+ check(&BigInt::zero(), 0.0);
+ check(&BigInt::one(), 1.0);
+ check(&BigInt::from(u32::MAX), 2.0.powi(32) - 1.0);
+ check(&BigInt::from(1u64 << 32), 2.0.powi(32));
+ check(&BigInt::from_slice(Plus, &[0, 0, 1]), 2.0.powi(64));
+ check(
+ &((BigInt::one() << 100) + (BigInt::one() << 152)),
+ 2.0.powi(100) + 2.0.powi(152),
+ );
+ check(&(BigInt::one() << 1023), 2.0.powi(1023));
+ check(&(BigInt::from((1u64 << 53) - 1) << (1024 - 53)), f64::MAX);
+
+ // keeping all 53 digits with the bits at different offsets to the BigDigits
+ let x: u64 = 0b0000000000011110111110110111111101110111101111011111011011011101;
+ let mut f = x as f64;
+ let mut b = BigInt::from(x);
+ for _ in 0..128 {
+ check(&b, f);
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // test rounding up with the bits at different offsets to the BigDigits
+ let mut f = ((1u64 << 54) - 1) as f64;
+ let mut b = BigInt::from(1u64 << 54);
+ for _ in 0..128 {
+ assert_eq!(b.to_f64(), Some(f));
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // rounding
+ assert_eq!(
+ BigInt::from_f64(-f64::consts::PI),
+ Some(BigInt::from(-3i32))
+ );
+ assert_eq!(BigInt::from_f64(-f64::consts::E), Some(BigInt::from(-2i32)));
+ assert_eq!(BigInt::from_f64(-0.99999), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f64(-0.5), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f64(-0.0), Some(BigInt::zero()));
+ assert_eq!(
+ BigInt::from_f64(f64::MIN_POSITIVE / 2.0),
+ Some(BigInt::zero())
+ );
+ assert_eq!(BigInt::from_f64(f64::MIN_POSITIVE), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f64(0.5), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f64(0.99999), Some(BigInt::zero()));
+ assert_eq!(BigInt::from_f64(f64::consts::E), Some(BigInt::from(2u32)));
+ assert_eq!(BigInt::from_f64(f64::consts::PI), Some(BigInt::from(3u32)));
+
+ // special float values
+ assert_eq!(BigInt::from_f64(f64::NAN), None);
+ assert_eq!(BigInt::from_f64(f64::INFINITY), None);
+ assert_eq!(BigInt::from_f64(f64::NEG_INFINITY), None);
+
+ // largest BigInt that will round to a finite f64 value
+ let big_num = (BigInt::one() << 1024) - BigInt::one() - (BigInt::one() << (1024 - 54));
+ assert_eq!(big_num.to_f64(), Some(f64::MAX));
+ assert_eq!((&big_num + BigInt::one()).to_f64(), None);
+ assert_eq!((-&big_num).to_f64(), Some(f64::MIN));
+ assert_eq!(((-&big_num) - BigInt::one()).to_f64(), None);
+
+ assert_eq!(((BigInt::one() << 1024) - BigInt::one()).to_f64(), None);
+ assert_eq!((BigInt::one() << 1024).to_f64(), None);
+ assert_eq!((-((BigInt::one() << 1024) - BigInt::one())).to_f64(), None);
+ assert_eq!((-(BigInt::one() << 1024)).to_f64(), None);
+}
+
+#[test]
+fn test_convert_to_biguint() {
+ fn check(n: BigInt, ans_1: BigUint) {
+ assert_eq!(n.to_biguint().unwrap(), ans_1);
+ assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
+ }
+ let zero: BigInt = Zero::zero();
+ let unsigned_zero: BigUint = Zero::zero();
+ let positive = BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3]));
+ let negative = -&positive;
+
+ check(zero, unsigned_zero);
+ check(positive, BigUint::new(vec![1, 2, 3]));
+
+ assert_eq!(negative.to_biguint(), None);
+}
+
+#[test]
+fn test_convert_from_uint() {
+ macro_rules! check {
+ ($ty:ident, $max:expr) => {
+ assert_eq!(BigInt::from($ty::zero()), BigInt::zero());
+ assert_eq!(BigInt::from($ty::one()), BigInt::one());
+ assert_eq!(BigInt::from($ty::MAX - $ty::one()), $max - BigInt::one());
+ assert_eq!(BigInt::from($ty::MAX), $max);
+ };
+ }
+
+ check!(u8, BigInt::from_slice(Plus, &[u8::MAX as u32]));
+ check!(u16, BigInt::from_slice(Plus, &[u16::MAX as u32]));
+ check!(u32, BigInt::from_slice(Plus, &[u32::MAX]));
+ check!(u64, BigInt::from_slice(Plus, &[u32::MAX, u32::MAX]));
+ #[cfg(has_i128)]
+ check!(
+ u128,
+ BigInt::from_slice(Plus, &[u32::MAX, u32::MAX, u32::MAX, u32::MAX])
+ );
+ check!(usize, BigInt::from(usize::MAX as u64));
+}
+
+#[test]
+fn test_convert_from_int() {
+ macro_rules! check {
+ ($ty:ident, $min:expr, $max:expr) => {
+ assert_eq!(BigInt::from($ty::MIN), $min);
+ assert_eq!(BigInt::from($ty::MIN + $ty::one()), $min + BigInt::one());
+ assert_eq!(BigInt::from(-$ty::one()), -BigInt::one());
+ assert_eq!(BigInt::from($ty::zero()), BigInt::zero());
+ assert_eq!(BigInt::from($ty::one()), BigInt::one());
+ assert_eq!(BigInt::from($ty::MAX - $ty::one()), $max - BigInt::one());
+ assert_eq!(BigInt::from($ty::MAX), $max);
+ };
+ }
+
+ check!(
+ i8,
+ BigInt::from_slice(Minus, &[1 << 7]),
+ BigInt::from_slice(Plus, &[i8::MAX as u32])
+ );
+ check!(
+ i16,
+ BigInt::from_slice(Minus, &[1 << 15]),
+ BigInt::from_slice(Plus, &[i16::MAX as u32])
+ );
+ check!(
+ i32,
+ BigInt::from_slice(Minus, &[1 << 31]),
+ BigInt::from_slice(Plus, &[i32::MAX as u32])
+ );
+ check!(
+ i64,
+ BigInt::from_slice(Minus, &[0, 1 << 31]),
+ BigInt::from_slice(Plus, &[u32::MAX, i32::MAX as u32])
+ );
+ #[cfg(has_i128)]
+ check!(
+ i128,
+ BigInt::from_slice(Minus, &[0, 0, 0, 1 << 31]),
+ BigInt::from_slice(Plus, &[u32::MAX, u32::MAX, u32::MAX, i32::MAX as u32])
+ );
+ check!(
+ isize,
+ BigInt::from(isize::MIN as i64),
+ BigInt::from(isize::MAX as i64)
+ );
+}
+
+#[test]
+fn test_convert_from_biguint() {
+ assert_eq!(BigInt::from(BigUint::zero()), BigInt::zero());
+ assert_eq!(BigInt::from(BigUint::one()), BigInt::one());
+ assert_eq!(
+ BigInt::from(BigUint::from_slice(&[1, 2, 3])),
+ BigInt::from_slice(Plus, &[1, 2, 3])
+ );
+}
+
+#[test]
+fn test_add() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let (na, nb, nc) = (-&a, -&b, -&c);
+
+ assert_op!(a + b == c);
+ assert_op!(b + a == c);
+ assert_op!(c + na == b);
+ assert_op!(c + nb == a);
+ assert_op!(a + nc == nb);
+ assert_op!(b + nc == na);
+ assert_op!(na + nb == nc);
+ assert_op!(a + na == Zero::zero());
+
+ assert_assign_op!(a += b == c);
+ assert_assign_op!(b += a == c);
+ assert_assign_op!(c += na == b);
+ assert_assign_op!(c += nb == a);
+ assert_assign_op!(a += nc == nb);
+ assert_assign_op!(b += nc == na);
+ assert_assign_op!(na += nb == nc);
+ assert_assign_op!(a += na == Zero::zero());
+ }
+}
+
+#[test]
+fn test_sub() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let (na, nb, nc) = (-&a, -&b, -&c);
+
+ assert_op!(c - a == b);
+ assert_op!(c - b == a);
+ assert_op!(nb - a == nc);
+ assert_op!(na - b == nc);
+ assert_op!(b - na == c);
+ assert_op!(a - nb == c);
+ assert_op!(nc - na == nb);
+ assert_op!(a - a == Zero::zero());
+
+ assert_assign_op!(c -= a == b);
+ assert_assign_op!(c -= b == a);
+ assert_assign_op!(nb -= a == nc);
+ assert_assign_op!(na -= b == nc);
+ assert_assign_op!(b -= na == c);
+ assert_assign_op!(a -= nb == c);
+ assert_assign_op!(nc -= na == nb);
+ assert_assign_op!(a -= a == Zero::zero());
+ }
+}
+
+#[test]
+fn test_mul() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let (na, nb, nc) = (-&a, -&b, -&c);
+
+ assert_op!(a * b == c);
+ assert_op!(b * a == c);
+ assert_op!(na * nb == c);
+
+ assert_op!(na * b == nc);
+ assert_op!(nb * a == nc);
+
+ assert_assign_op!(a *= b == c);
+ assert_assign_op!(b *= a == c);
+ assert_assign_op!(na *= nb == c);
+
+ assert_assign_op!(na *= b == nc);
+ assert_assign_op!(nb *= a == nc);
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let d = BigInt::from_slice(Plus, d_vec);
+
+ assert!(a == &b * &c + &d);
+ assert!(a == &c * &b + &d);
+ }
+}
+
+#[test]
+fn test_div_mod_floor() {
+ fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
+ let (d, m) = a.div_mod_floor(b);
+ if !m.is_zero() {
+ assert_eq!(m.sign(), b.sign());
+ }
+ assert!(m.abs() <= b.abs());
+ assert!(*a == b * &d + &m);
+ assert!(d == *ans_d);
+ assert!(m == *ans_m);
+ }
+
+ fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
+ if m.is_zero() {
+ check_sub(a, b, d, m);
+ check_sub(a, &b.neg(), &d.neg(), m);
+ check_sub(&a.neg(), b, &d.neg(), m);
+ check_sub(&a.neg(), &b.neg(), d, m);
+ } else {
+ let one: BigInt = One::one();
+ check_sub(a, b, d, m);
+ check_sub(a, &b.neg(), &(d.neg() - &one), &(m - b));
+ check_sub(&a.neg(), b, &(d.neg() - &one), &(b - m));
+ check_sub(&a.neg(), &b.neg(), d, &m.neg());
+ }
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ if !a.is_zero() {
+ check(&c, &a, &b, &Zero::zero());
+ }
+ if !b.is_zero() {
+ check(&c, &b, &a, &Zero::zero());
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let d = BigInt::from_slice(Plus, d_vec);
+
+ if !b.is_zero() {
+ check(&a, &b, &c, &d);
+ }
+ }
+}
+
+#[test]
+fn test_div_rem() {
+ fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
+ let (q, r) = a.div_rem(b);
+ if !r.is_zero() {
+ assert_eq!(r.sign(), a.sign());
+ }
+ assert!(r.abs() <= b.abs());
+ assert!(*a == b * &q + &r);
+ assert!(q == *ans_q);
+ assert!(r == *ans_r);
+
+ let (a, b, ans_q, ans_r) = (a.clone(), b.clone(), ans_q.clone(), ans_r.clone());
+ assert_op!(a / b == ans_q);
+ assert_op!(a % b == ans_r);
+ assert_assign_op!(a /= b == ans_q);
+ assert_assign_op!(a %= b == ans_r);
+ }
+
+ fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
+ check_sub(a, b, q, r);
+ check_sub(a, &b.neg(), &q.neg(), r);
+ check_sub(&a.neg(), b, &q.neg(), &r.neg());
+ check_sub(&a.neg(), &b.neg(), q, &r.neg());
+ }
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ if !a.is_zero() {
+ check(&c, &a, &b, &Zero::zero());
+ }
+ if !b.is_zero() {
+ check(&c, &b, &a, &Zero::zero());
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let d = BigInt::from_slice(Plus, d_vec);
+
+ if !b.is_zero() {
+ check(&a, &b, &c, &d);
+ }
+ }
+}
+
+#[test]
+fn test_checked_add() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ assert!(a.checked_add(&b).unwrap() == c);
+ assert!(b.checked_add(&a).unwrap() == c);
+ assert!(c.checked_add(&(-&a)).unwrap() == b);
+ assert!(c.checked_add(&(-&b)).unwrap() == a);
+ assert!(a.checked_add(&(-&c)).unwrap() == (-&b));
+ assert!(b.checked_add(&(-&c)).unwrap() == (-&a));
+ assert!((-&a).checked_add(&(-&b)).unwrap() == (-&c));
+ assert!(a.checked_add(&(-&a)).unwrap() == Zero::zero());
+ }
+}
+
+#[test]
+fn test_checked_sub() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ assert!(c.checked_sub(&a).unwrap() == b);
+ assert!(c.checked_sub(&b).unwrap() == a);
+ assert!((-&b).checked_sub(&a).unwrap() == (-&c));
+ assert!((-&a).checked_sub(&b).unwrap() == (-&c));
+ assert!(b.checked_sub(&(-&a)).unwrap() == c);
+ assert!(a.checked_sub(&(-&b)).unwrap() == c);
+ assert!((-&c).checked_sub(&(-&a)).unwrap() == (-&b));
+ assert!(a.checked_sub(&a).unwrap() == Zero::zero());
+ }
+}
+
+#[test]
+fn test_checked_mul() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ assert!(a.checked_mul(&b).unwrap() == c);
+ assert!(b.checked_mul(&a).unwrap() == c);
+
+ assert!((-&a).checked_mul(&b).unwrap() == -&c);
+ assert!((-&b).checked_mul(&a).unwrap() == -&c);
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let d = BigInt::from_slice(Plus, d_vec);
+
+ assert!(a == b.checked_mul(&c).unwrap() + &d);
+ assert!(a == c.checked_mul(&b).unwrap() + &d);
+ }
+}
+#[test]
+fn test_checked_div() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ if !a.is_zero() {
+ assert!(c.checked_div(&a).unwrap() == b);
+ assert!((-&c).checked_div(&(-&a)).unwrap() == b);
+ assert!((-&c).checked_div(&a).unwrap() == -&b);
+ }
+ if !b.is_zero() {
+ assert!(c.checked_div(&b).unwrap() == a);
+ assert!((-&c).checked_div(&(-&b)).unwrap() == a);
+ assert!((-&c).checked_div(&b).unwrap() == -&a);
+ }
+
+ assert!(c.checked_div(&Zero::zero()).is_none());
+ assert!((-&c).checked_div(&Zero::zero()).is_none());
+ }
+}
+
+#[test]
+fn test_gcd() {
+ fn check(a: isize, b: isize, c: isize) {
+ let big_a: BigInt = FromPrimitive::from_isize(a).unwrap();
+ let big_b: BigInt = FromPrimitive::from_isize(b).unwrap();
+ let big_c: BigInt = FromPrimitive::from_isize(c).unwrap();
+
+ assert_eq!(big_a.gcd(&big_b), big_c);
+ }
+
+ check(10, 2, 2);
+ check(10, 3, 1);
+ check(0, 3, 3);
+ check(3, 3, 3);
+ check(56, 42, 14);
+ check(3, -3, 3);
+ check(-6, 3, 3);
+ check(-4, -2, 2);
+}
+
+#[test]
+fn test_lcm() {
+ fn check(a: isize, b: isize, c: isize) {
+ let big_a: BigInt = FromPrimitive::from_isize(a).unwrap();
+ let big_b: BigInt = FromPrimitive::from_isize(b).unwrap();
+ let big_c: BigInt = FromPrimitive::from_isize(c).unwrap();
+
+ assert_eq!(big_a.lcm(&big_b), big_c);
+ }
+
+ check(0, 0, 0);
+ check(1, 0, 0);
+ check(0, 1, 0);
+ check(1, 1, 1);
+ check(-1, 1, 1);
+ check(1, -1, 1);
+ check(-1, -1, 1);
+ check(8, 9, 72);
+ check(11, 5, 55);
+}
+
+#[test]
+fn test_abs_sub() {
+ let zero: BigInt = Zero::zero();
+ let one: BigInt = One::one();
+ assert_eq!((-&one).abs_sub(&one), zero);
+ let one: BigInt = One::one();
+ let zero: BigInt = Zero::zero();
+ assert_eq!(one.abs_sub(&one), zero);
+ let one: BigInt = One::one();
+ let zero: BigInt = Zero::zero();
+ assert_eq!(one.abs_sub(&zero), one);
+ let one: BigInt = One::one();
+ let two: BigInt = FromPrimitive::from_isize(2).unwrap();
+ assert_eq!(one.abs_sub(&-&one), two);
+}
+
+#[test]
+fn test_from_str_radix() {
+ fn check(s: &str, ans: Option<isize>) {
+ let ans = ans.map(|n| {
+ let x: BigInt = FromPrimitive::from_isize(n).unwrap();
+ x
+ });
+ assert_eq!(BigInt::from_str_radix(s, 10).ok(), ans);
+ }
+ check("10", Some(10));
+ check("1", Some(1));
+ check("0", Some(0));
+ check("-1", Some(-1));
+ check("-10", Some(-10));
+ check("+10", Some(10));
+ check("--7", None);
+ check("++5", None);
+ check("+-9", None);
+ check("-+3", None);
+ check("Z", None);
+ check("_", None);
+
+ // issue 10522, this hit an edge case that caused it to
+ // attempt to allocate a vector of size (-1u) == huge.
+ let x: BigInt = format!("1{}", repeat("0").take(36).collect::<String>())
+ .parse()
+ .unwrap();
+ let _y = x.to_string();
+}
+
+#[test]
+fn test_lower_hex() {
+ let a = BigInt::parse_bytes(b"A", 16).unwrap();
+ let hello = BigInt::parse_bytes("-22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:x}", a), "a");
+ assert_eq!(format!("{:x}", hello), "-48656c6c6f20776f726c6421");
+ assert_eq!(format!("{:♥>+#8x}", a), "♥♥♥♥+0xa");
+}
+
+#[test]
+fn test_upper_hex() {
+ let a = BigInt::parse_bytes(b"A", 16).unwrap();
+ let hello = BigInt::parse_bytes("-22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:X}", a), "A");
+ assert_eq!(format!("{:X}", hello), "-48656C6C6F20776F726C6421");
+ assert_eq!(format!("{:♥>+#8X}", a), "♥♥♥♥+0xA");
+}
+
+#[test]
+fn test_binary() {
+ let a = BigInt::parse_bytes(b"A", 16).unwrap();
+ let hello = BigInt::parse_bytes("-224055342307539".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:b}", a), "1010");
+ assert_eq!(
+ format!("{:b}", hello),
+ "-110010111100011011110011000101101001100011010011"
+ );
+ assert_eq!(format!("{:♥>+#8b}", a), "♥+0b1010");
+}
+
+#[test]
+fn test_octal() {
+ let a = BigInt::parse_bytes(b"A", 16).unwrap();
+ let hello = BigInt::parse_bytes("-22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:o}", a), "12");
+ assert_eq!(format!("{:o}", hello), "-22062554330674403566756233062041");
+ assert_eq!(format!("{:♥>+#8o}", a), "♥♥♥+0o12");
+}
+
+#[test]
+fn test_display() {
+ let a = BigInt::parse_bytes(b"A", 16).unwrap();
+ let hello = BigInt::parse_bytes("-22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{}", a), "10");
+ assert_eq!(format!("{}", hello), "-22405534230753963835153736737");
+ assert_eq!(format!("{:♥>+#8}", a), "♥♥♥♥♥+10");
+}
+
+#[test]
+fn test_neg() {
+ assert!(-BigInt::new(Plus, vec![1, 1, 1]) == BigInt::new(Minus, vec![1, 1, 1]));
+ assert!(-BigInt::new(Minus, vec![1, 1, 1]) == BigInt::new(Plus, vec![1, 1, 1]));
+ let zero: BigInt = Zero::zero();
+ assert_eq!(-&zero, zero);
+}
+
+#[test]
+fn test_negative_shr() {
+ assert_eq!(BigInt::from(-1) >> 1, BigInt::from(-1));
+ assert_eq!(BigInt::from(-2) >> 1, BigInt::from(-1));
+ assert_eq!(BigInt::from(-3) >> 1, BigInt::from(-2));
+ assert_eq!(BigInt::from(-3) >> 2, BigInt::from(-1));
+}
+
+#[test]
+#[cfg(feature = "rand")]
+fn test_random_shr() {
+ use rand::distributions::Standard;
+ use rand::Rng;
+ let mut rng = rand::thread_rng();
+
+ for p in rng.sample_iter::<i64, _>(&Standard).take(1000) {
+ let big = BigInt::from(p);
+ let bigger = &big << 1000;
+ assert_eq!(&bigger >> 1000, big);
+ for i in 0..64 {
+ let answer = BigInt::from(p >> i);
+ assert_eq!(&big >> i, answer);
+ assert_eq!(&bigger >> (1000 + i), answer);
+ }
+ }
+}
+
+#[test]
+fn test_iter_sum() {
+ let result: BigInt = FromPrimitive::from_isize(-1234567).unwrap();
+ let data: Vec<BigInt> = vec![
+ FromPrimitive::from_i32(-1000000).unwrap(),
+ FromPrimitive::from_i32(-200000).unwrap(),
+ FromPrimitive::from_i32(-30000).unwrap(),
+ FromPrimitive::from_i32(-4000).unwrap(),
+ FromPrimitive::from_i32(-500).unwrap(),
+ FromPrimitive::from_i32(-60).unwrap(),
+ FromPrimitive::from_i32(-7).unwrap(),
+ ];
+
+ assert_eq!(result, data.iter().sum());
+ assert_eq!(result, data.into_iter().sum());
+}
+
+#[test]
+fn test_iter_product() {
+ let data: Vec<BigInt> = vec![
+ FromPrimitive::from_i32(1001).unwrap(),
+ FromPrimitive::from_i32(-1002).unwrap(),
+ FromPrimitive::from_i32(1003).unwrap(),
+ FromPrimitive::from_i32(-1004).unwrap(),
+ FromPrimitive::from_i32(1005).unwrap(),
+ ];
+ let result = data.get(0).unwrap()
+ * data.get(1).unwrap()
+ * data.get(2).unwrap()
+ * data.get(3).unwrap()
+ * data.get(4).unwrap();
+
+ assert_eq!(result, data.iter().product());
+ assert_eq!(result, data.into_iter().product());
+}
+
+#[test]
+fn test_iter_sum_generic() {
+ let result: BigInt = FromPrimitive::from_isize(-1234567).unwrap();
+ let data = vec![-1000000, -200000, -30000, -4000, -500, -60, -7];
+
+ assert_eq!(result, data.iter().sum());
+ assert_eq!(result, data.into_iter().sum());
+}
+
+#[test]
+fn test_iter_product_generic() {
+ let data = vec![1001, -1002, 1003, -1004, 1005];
+ let result = data[0].to_bigint().unwrap()
+ * data[1].to_bigint().unwrap()
+ * data[2].to_bigint().unwrap()
+ * data[3].to_bigint().unwrap()
+ * data[4].to_bigint().unwrap();
+
+ assert_eq!(result, data.iter().product());
+ assert_eq!(result, data.into_iter().product());
+}
+
+#[test]
+fn test_pow() {
+ let one = BigInt::from(1i32);
+ let two = BigInt::from(2i32);
+ let four = BigInt::from(4i32);
+ let eight = BigInt::from(8i32);
+ let minus_two = BigInt::from(-2i32);
+ macro_rules! check {
+ ($t:ty) => {
+ assert_eq!(two.pow(0 as $t), one);
+ assert_eq!(two.pow(1 as $t), two);
+ assert_eq!(two.pow(2 as $t), four);
+ assert_eq!(two.pow(3 as $t), eight);
+ assert_eq!(two.pow(&(3 as $t)), eight);
+ assert_eq!(minus_two.pow(0 as $t), one, "-2^0");
+ assert_eq!(minus_two.pow(1 as $t), minus_two, "-2^1");
+ assert_eq!(minus_two.pow(2 as $t), four, "-2^2");
+ assert_eq!(minus_two.pow(3 as $t), -&eight, "-2^3");
+ };
+ }
+ check!(u8);
+ check!(u16);
+ check!(u32);
+ check!(u64);
+ check!(usize);
+}
diff --git a/third_party/rust/num-bigint/tests/bigint_bitwise.rs b/third_party/rust/num-bigint/tests/bigint_bitwise.rs
new file mode 100644
index 0000000000..cc0c493cb5
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/bigint_bitwise.rs
@@ -0,0 +1,181 @@
+extern crate num_bigint;
+extern crate num_traits;
+
+use num_bigint::{BigInt, Sign, ToBigInt};
+use num_traits::ToPrimitive;
+use std::{i32, i64, u32};
+
+enum ValueVec {
+ N,
+ P(&'static [u32]),
+ M(&'static [u32]),
+}
+
+use ValueVec::*;
+
+impl ToBigInt for ValueVec {
+ fn to_bigint(&self) -> Option<BigInt> {
+ match self {
+ &N => Some(BigInt::from_slice(Sign::NoSign, &[])),
+ &P(s) => Some(BigInt::from_slice(Sign::Plus, s)),
+ &M(s) => Some(BigInt::from_slice(Sign::Minus, s)),
+ }
+ }
+}
+
+// a, !a
+const NOT_VALUES: &'static [(ValueVec, ValueVec)] = &[
+ (N, M(&[1])),
+ (P(&[1]), M(&[2])),
+ (P(&[2]), M(&[3])),
+ (P(&[!0 - 2]), M(&[!0 - 1])),
+ (P(&[!0 - 1]), M(&[!0])),
+ (P(&[!0]), M(&[0, 1])),
+ (P(&[0, 1]), M(&[1, 1])),
+ (P(&[1, 1]), M(&[2, 1])),
+];
+
+// a, b, a & b, a | b, a ^ b
+const BITWISE_VALUES: &'static [(ValueVec, ValueVec, ValueVec, ValueVec, ValueVec)] = &[
+ (N, N, N, N, N),
+ (N, P(&[1]), N, P(&[1]), P(&[1])),
+ (N, P(&[!0]), N, P(&[!0]), P(&[!0])),
+ (N, P(&[0, 1]), N, P(&[0, 1]), P(&[0, 1])),
+ (N, M(&[1]), N, M(&[1]), M(&[1])),
+ (N, M(&[!0]), N, M(&[!0]), M(&[!0])),
+ (N, M(&[0, 1]), N, M(&[0, 1]), M(&[0, 1])),
+ (P(&[1]), P(&[!0]), P(&[1]), P(&[!0]), P(&[!0 - 1])),
+ (P(&[!0]), P(&[!0]), P(&[!0]), P(&[!0]), N),
+ (P(&[!0]), P(&[1, 1]), P(&[1]), P(&[!0, 1]), P(&[!0 - 1, 1])),
+ (P(&[1]), M(&[!0]), P(&[1]), M(&[!0]), M(&[0, 1])),
+ (P(&[!0]), M(&[1]), P(&[!0]), M(&[1]), M(&[0, 1])),
+ (P(&[!0]), M(&[!0]), P(&[1]), M(&[1]), M(&[2])),
+ (P(&[!0]), M(&[1, 1]), P(&[!0]), M(&[1, 1]), M(&[0, 2])),
+ (P(&[1, 1]), M(&[!0]), P(&[1, 1]), M(&[!0]), M(&[0, 2])),
+ (M(&[1]), M(&[!0]), M(&[!0]), M(&[1]), P(&[!0 - 1])),
+ (M(&[!0]), M(&[!0]), M(&[!0]), M(&[!0]), N),
+ (M(&[!0]), M(&[1, 1]), M(&[!0, 1]), M(&[1]), P(&[!0 - 1, 1])),
+];
+
+const I32_MIN: i64 = i32::MIN as i64;
+const I32_MAX: i64 = i32::MAX as i64;
+const U32_MAX: i64 = u32::MAX as i64;
+
+// some corner cases
+const I64_VALUES: &'static [i64] = &[
+ i64::MIN,
+ i64::MIN + 1,
+ i64::MIN + 2,
+ i64::MIN + 3,
+ -U32_MAX - 3,
+ -U32_MAX - 2,
+ -U32_MAX - 1,
+ -U32_MAX,
+ -U32_MAX + 1,
+ -U32_MAX + 2,
+ -U32_MAX + 3,
+ I32_MIN - 3,
+ I32_MIN - 2,
+ I32_MIN - 1,
+ I32_MIN,
+ I32_MIN + 1,
+ I32_MIN + 2,
+ I32_MIN + 3,
+ -3,
+ -2,
+ -1,
+ 0,
+ 1,
+ 2,
+ 3,
+ I32_MAX - 3,
+ I32_MAX - 2,
+ I32_MAX - 1,
+ I32_MAX,
+ I32_MAX + 1,
+ I32_MAX + 2,
+ I32_MAX + 3,
+ U32_MAX - 3,
+ U32_MAX - 2,
+ U32_MAX - 1,
+ U32_MAX,
+ U32_MAX + 1,
+ U32_MAX + 2,
+ U32_MAX + 3,
+ i64::MAX - 3,
+ i64::MAX - 2,
+ i64::MAX - 1,
+ i64::MAX,
+];
+
+#[test]
+fn test_not() {
+ for &(ref a, ref not) in NOT_VALUES.iter() {
+ let a = a.to_bigint().unwrap();
+ let not = not.to_bigint().unwrap();
+
+ // sanity check for tests that fit in i64
+ if let (Some(prim_a), Some(prim_not)) = (a.to_i64(), not.to_i64()) {
+ assert_eq!(!prim_a, prim_not);
+ }
+
+ assert_eq!(!a.clone(), not, "!{:x}", a);
+ assert_eq!(!not.clone(), a, "!{:x}", not);
+ }
+}
+
+#[test]
+fn test_not_i64() {
+ for &prim_a in I64_VALUES.iter() {
+ let a = prim_a.to_bigint().unwrap();
+ let not = (!prim_a).to_bigint().unwrap();
+ assert_eq!(!a.clone(), not, "!{:x}", a);
+ }
+}
+
+#[test]
+fn test_bitwise() {
+ for &(ref a, ref b, ref and, ref or, ref xor) in BITWISE_VALUES.iter() {
+ let a = a.to_bigint().unwrap();
+ let b = b.to_bigint().unwrap();
+ let and = and.to_bigint().unwrap();
+ let or = or.to_bigint().unwrap();
+ let xor = xor.to_bigint().unwrap();
+
+ // sanity check for tests that fit in i64
+ if let (Some(prim_a), Some(prim_b)) = (a.to_i64(), b.to_i64()) {
+ if let Some(prim_and) = and.to_i64() {
+ assert_eq!(prim_a & prim_b, prim_and);
+ }
+ if let Some(prim_or) = or.to_i64() {
+ assert_eq!(prim_a | prim_b, prim_or);
+ }
+ if let Some(prim_xor) = xor.to_i64() {
+ assert_eq!(prim_a ^ prim_b, prim_xor);
+ }
+ }
+
+ assert_eq!(a.clone() & &b, and, "{:x} & {:x}", a, b);
+ assert_eq!(b.clone() & &a, and, "{:x} & {:x}", b, a);
+ assert_eq!(a.clone() | &b, or, "{:x} | {:x}", a, b);
+ assert_eq!(b.clone() | &a, or, "{:x} | {:x}", b, a);
+ assert_eq!(a.clone() ^ &b, xor, "{:x} ^ {:x}", a, b);
+ assert_eq!(b.clone() ^ &a, xor, "{:x} ^ {:x}", b, a);
+ }
+}
+
+#[test]
+fn test_bitwise_i64() {
+ for &prim_a in I64_VALUES.iter() {
+ let a = prim_a.to_bigint().unwrap();
+ for &prim_b in I64_VALUES.iter() {
+ let b = prim_b.to_bigint().unwrap();
+ let and = (prim_a & prim_b).to_bigint().unwrap();
+ let or = (prim_a | prim_b).to_bigint().unwrap();
+ let xor = (prim_a ^ prim_b).to_bigint().unwrap();
+ assert_eq!(a.clone() & &b, and, "{:x} & {:x}", a, b);
+ assert_eq!(a.clone() | &b, or, "{:x} | {:x}", a, b);
+ assert_eq!(a.clone() ^ &b, xor, "{:x} ^ {:x}", a, b);
+ }
+ }
+}
diff --git a/third_party/rust/num-bigint/tests/bigint_scalar.rs b/third_party/rust/num-bigint/tests/bigint_scalar.rs
new file mode 100644
index 0000000000..ae9a6d7aa2
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/bigint_scalar.rs
@@ -0,0 +1,145 @@
+extern crate num_bigint;
+extern crate num_traits;
+
+use num_bigint::BigInt;
+use num_bigint::Sign::Plus;
+use num_traits::{Signed, ToPrimitive, Zero};
+
+use std::ops::Neg;
+
+mod consts;
+use consts::*;
+
+#[macro_use]
+mod macros;
+
+#[test]
+fn test_scalar_add() {
+ fn check(x: &BigInt, y: &BigInt, z: &BigInt) {
+ let (x, y, z) = (x.clone(), y.clone(), z.clone());
+ assert_signed_scalar_op!(x + y == z);
+ }
+
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let (na, nb, nc) = (-&a, -&b, -&c);
+
+ check(&a, &b, &c);
+ check(&b, &a, &c);
+ check(&c, &na, &b);
+ check(&c, &nb, &a);
+ check(&a, &nc, &nb);
+ check(&b, &nc, &na);
+ check(&na, &nb, &nc);
+ check(&a, &na, &Zero::zero());
+ }
+}
+
+#[test]
+fn test_scalar_sub() {
+ fn check(x: &BigInt, y: &BigInt, z: &BigInt) {
+ let (x, y, z) = (x.clone(), y.clone(), z.clone());
+ assert_signed_scalar_op!(x - y == z);
+ }
+
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let (na, nb, nc) = (-&a, -&b, -&c);
+
+ check(&c, &a, &b);
+ check(&c, &b, &a);
+ check(&nb, &a, &nc);
+ check(&na, &b, &nc);
+ check(&b, &na, &c);
+ check(&a, &nb, &c);
+ check(&nc, &na, &nb);
+ check(&a, &a, &Zero::zero());
+ }
+}
+
+#[test]
+fn test_scalar_mul() {
+ fn check(x: &BigInt, y: &BigInt, z: &BigInt) {
+ let (x, y, z) = (x.clone(), y.clone(), z.clone());
+ assert_signed_scalar_op!(x * y == z);
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let (na, nb, nc) = (-&a, -&b, -&c);
+
+ check(&a, &b, &c);
+ check(&b, &a, &c);
+ check(&na, &nb, &c);
+
+ check(&na, &b, &nc);
+ check(&nb, &a, &nc);
+ }
+}
+
+#[test]
+fn test_scalar_div_rem() {
+ fn check_sub(a: &BigInt, b: u32, ans_q: &BigInt, ans_r: &BigInt) {
+ let (q, r) = (a / b, a % b);
+ if !r.is_zero() {
+ assert_eq!(r.sign(), a.sign());
+ }
+ assert!(r.abs() <= From::from(b));
+ assert!(*a == b * &q + &r);
+ assert!(q == *ans_q);
+ assert!(r == *ans_r);
+
+ let (a, b, ans_q, ans_r) = (a.clone(), b.clone(), ans_q.clone(), ans_r.clone());
+ assert_op!(a / b == ans_q);
+ assert_op!(a % b == ans_r);
+
+ if b <= i32::max_value() as u32 {
+ let nb = -(b as i32);
+ assert_op!(a / nb == -ans_q.clone());
+ assert_op!(a % nb == ans_r);
+ }
+ }
+
+ fn check(a: &BigInt, b: u32, q: &BigInt, r: &BigInt) {
+ check_sub(a, b, q, r);
+ check_sub(&a.neg(), b, &q.neg(), &r.neg());
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ if a_vec.len() == 1 && a_vec[0] != 0 {
+ let a = a_vec[0];
+ check(&c, a, &b, &Zero::zero());
+ }
+
+ if b_vec.len() == 1 && b_vec[0] != 0 {
+ let b = b_vec[0];
+ check(&c, b, &a, &Zero::zero());
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let d = BigInt::from_slice(Plus, d_vec);
+
+ if b_vec.len() == 1 && b_vec[0] != 0 {
+ let b = b_vec[0];
+ check(&a, b, &c, &d);
+ }
+ }
+}
diff --git a/third_party/rust/num-bigint/tests/biguint.rs b/third_party/rust/num-bigint/tests/biguint.rs
new file mode 100644
index 0000000000..1e23aa17f9
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/biguint.rs
@@ -0,0 +1,1713 @@
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+
+use num_bigint::Sign::Plus;
+use num_bigint::{BigInt, ToBigInt};
+use num_bigint::{BigUint, ToBigUint};
+use num_integer::Integer;
+
+use std::cmp::Ordering::{Equal, Greater, Less};
+use std::collections::hash_map::RandomState;
+use std::hash::{BuildHasher, Hash, Hasher};
+use std::i64;
+use std::iter::repeat;
+use std::str::FromStr;
+use std::{f32, f64};
+#[cfg(has_i128)]
+use std::{i128, u128};
+use std::{u16, u32, u64, u8, usize};
+
+use num_traits::{
+ CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Float, FromPrimitive, Num, One, Pow,
+ ToPrimitive, Zero,
+};
+
+mod consts;
+use consts::*;
+
+#[macro_use]
+mod macros;
+
+#[test]
+fn test_from_bytes_be() {
+ fn check(s: &str, result: &str) {
+ assert_eq!(
+ BigUint::from_bytes_be(s.as_bytes()),
+ BigUint::parse_bytes(result.as_bytes(), 10).unwrap()
+ );
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("AB", "16706");
+ check("Hello world!", "22405534230753963835153736737");
+ assert_eq!(BigUint::from_bytes_be(&[]), Zero::zero());
+}
+
+#[test]
+fn test_to_bytes_be() {
+ fn check(s: &str, result: &str) {
+ let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
+ assert_eq!(b.to_bytes_be(), s.as_bytes());
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("AB", "16706");
+ check("Hello world!", "22405534230753963835153736737");
+ let b: BigUint = Zero::zero();
+ assert_eq!(b.to_bytes_be(), [0]);
+
+ // Test with leading/trailing zero bytes and a full BigDigit of value 0
+ let b = BigUint::from_str_radix("00010000000000000200", 16).unwrap();
+ assert_eq!(b.to_bytes_be(), [1, 0, 0, 0, 0, 0, 0, 2, 0]);
+}
+
+#[test]
+fn test_from_bytes_le() {
+ fn check(s: &str, result: &str) {
+ assert_eq!(
+ BigUint::from_bytes_le(s.as_bytes()),
+ BigUint::parse_bytes(result.as_bytes(), 10).unwrap()
+ );
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("BA", "16706");
+ check("!dlrow olleH", "22405534230753963835153736737");
+ assert_eq!(BigUint::from_bytes_le(&[]), Zero::zero());
+}
+
+#[test]
+fn test_to_bytes_le() {
+ fn check(s: &str, result: &str) {
+ let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
+ assert_eq!(b.to_bytes_le(), s.as_bytes());
+ }
+ check("A", "65");
+ check("AA", "16705");
+ check("BA", "16706");
+ check("!dlrow olleH", "22405534230753963835153736737");
+ let b: BigUint = Zero::zero();
+ assert_eq!(b.to_bytes_le(), [0]);
+
+ // Test with leading/trailing zero bytes and a full BigDigit of value 0
+ let b = BigUint::from_str_radix("00010000000000000200", 16).unwrap();
+ assert_eq!(b.to_bytes_le(), [0, 2, 0, 0, 0, 0, 0, 0, 1]);
+}
+
+#[test]
+fn test_cmp() {
+ let data: [&[_]; 7] = [&[], &[1], &[2], &[!0], &[0, 1], &[2, 1], &[1, 1, 1]];
+ let data: Vec<BigUint> = data.iter().map(|v| BigUint::from_slice(*v)).collect();
+ for (i, ni) in data.iter().enumerate() {
+ for (j0, nj) in data[i..].iter().enumerate() {
+ let j = j0 + i;
+ if i == j {
+ assert_eq!(ni.cmp(nj), Equal);
+ assert_eq!(nj.cmp(ni), Equal);
+ assert_eq!(ni, nj);
+ assert!(!(ni != nj));
+ assert!(ni <= nj);
+ assert!(ni >= nj);
+ assert!(!(ni < nj));
+ assert!(!(ni > nj));
+ } else {
+ assert_eq!(ni.cmp(nj), Less);
+ assert_eq!(nj.cmp(ni), Greater);
+
+ assert!(!(ni == nj));
+ assert!(ni != nj);
+
+ assert!(ni <= nj);
+ assert!(!(ni >= nj));
+ assert!(ni < nj);
+ assert!(!(ni > nj));
+
+ assert!(!(nj <= ni));
+ assert!(nj >= ni);
+ assert!(!(nj < ni));
+ assert!(nj > ni);
+ }
+ }
+ }
+}
+
+fn hash<T: Hash>(x: &T) -> u64 {
+ let mut hasher = <RandomState as BuildHasher>::Hasher::new();
+ x.hash(&mut hasher);
+ hasher.finish()
+}
+
+#[test]
+fn test_hash() {
+ use hash;
+
+ let a = BigUint::new(vec![]);
+ let b = BigUint::new(vec![0]);
+ let c = BigUint::new(vec![1]);
+ let d = BigUint::new(vec![1, 0, 0, 0, 0, 0]);
+ let e = BigUint::new(vec![0, 0, 0, 0, 0, 1]);
+ assert!(hash(&a) == hash(&b));
+ assert!(hash(&b) != hash(&c));
+ assert!(hash(&c) == hash(&d));
+ assert!(hash(&d) != hash(&e));
+}
+
+// LEFT, RIGHT, AND, OR, XOR
+const BIT_TESTS: &'static [(
+ &'static [u32],
+ &'static [u32],
+ &'static [u32],
+ &'static [u32],
+ &'static [u32],
+)] = &[
+ (&[], &[], &[], &[], &[]),
+ (&[1, 0, 1], &[1, 1], &[1], &[1, 1, 1], &[0, 1, 1]),
+ (&[1, 0, 1], &[0, 1, 1], &[0, 0, 1], &[1, 1, 1], &[1, 1]),
+ (
+ &[268, 482, 17],
+ &[964, 54],
+ &[260, 34],
+ &[972, 502, 17],
+ &[712, 468, 17],
+ ),
+];
+
+#[test]
+fn test_bitand() {
+ for elm in BIT_TESTS {
+ let (a_vec, b_vec, c_vec, _, _) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert_op!(a & b == c);
+ assert_op!(b & a == c);
+ assert_assign_op!(a &= b == c);
+ assert_assign_op!(b &= a == c);
+ }
+}
+
+#[test]
+fn test_bitor() {
+ for elm in BIT_TESTS {
+ let (a_vec, b_vec, _, c_vec, _) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert_op!(a | b == c);
+ assert_op!(b | a == c);
+ assert_assign_op!(a |= b == c);
+ assert_assign_op!(b |= a == c);
+ }
+}
+
+#[test]
+fn test_bitxor() {
+ for elm in BIT_TESTS {
+ let (a_vec, b_vec, _, _, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert_op!(a ^ b == c);
+ assert_op!(b ^ a == c);
+ assert_op!(a ^ c == b);
+ assert_op!(c ^ a == b);
+ assert_op!(b ^ c == a);
+ assert_op!(c ^ b == a);
+ assert_assign_op!(a ^= b == c);
+ assert_assign_op!(b ^= a == c);
+ assert_assign_op!(a ^= c == b);
+ assert_assign_op!(c ^= a == b);
+ assert_assign_op!(b ^= c == a);
+ assert_assign_op!(c ^= b == a);
+ }
+}
+
+#[test]
+fn test_shl() {
+ fn check(s: &str, shift: usize, ans: &str) {
+ let opt_biguint = BigUint::from_str_radix(s, 16).ok();
+ let mut bu_assign = opt_biguint.unwrap();
+ let bu = (bu_assign.clone() << shift).to_str_radix(16);
+ assert_eq!(bu, ans);
+ bu_assign <<= shift;
+ assert_eq!(bu_assign.to_str_radix(16), ans);
+ }
+
+ check("0", 3, "0");
+ check("1", 3, "8");
+
+ check(
+ "1\
+ 0000\
+ 0000\
+ 0000\
+ 0001\
+ 0000\
+ 0000\
+ 0000\
+ 0001",
+ 3,
+ "8\
+ 0000\
+ 0000\
+ 0000\
+ 0008\
+ 0000\
+ 0000\
+ 0000\
+ 0008",
+ );
+ check(
+ "1\
+ 0000\
+ 0001\
+ 0000\
+ 0001",
+ 2,
+ "4\
+ 0000\
+ 0004\
+ 0000\
+ 0004",
+ );
+ check(
+ "1\
+ 0001\
+ 0001",
+ 1,
+ "2\
+ 0002\
+ 0002",
+ );
+
+ check(
+ "\
+ 4000\
+ 0000\
+ 0000\
+ 0000",
+ 3,
+ "2\
+ 0000\
+ 0000\
+ 0000\
+ 0000",
+ );
+ check(
+ "4000\
+ 0000",
+ 2,
+ "1\
+ 0000\
+ 0000",
+ );
+ check(
+ "4000",
+ 2,
+ "1\
+ 0000",
+ );
+
+ check(
+ "4000\
+ 0000\
+ 0000\
+ 0000",
+ 67,
+ "2\
+ 0000\
+ 0000\
+ 0000\
+ 0000\
+ 0000\
+ 0000\
+ 0000\
+ 0000",
+ );
+ check(
+ "4000\
+ 0000",
+ 35,
+ "2\
+ 0000\
+ 0000\
+ 0000\
+ 0000",
+ );
+ check(
+ "4000",
+ 19,
+ "2\
+ 0000\
+ 0000",
+ );
+
+ check(
+ "fedc\
+ ba98\
+ 7654\
+ 3210\
+ fedc\
+ ba98\
+ 7654\
+ 3210",
+ 4,
+ "f\
+ edcb\
+ a987\
+ 6543\
+ 210f\
+ edcb\
+ a987\
+ 6543\
+ 2100",
+ );
+ check(
+ "88887777666655554444333322221111",
+ 16,
+ "888877776666555544443333222211110000",
+ );
+}
+
+#[test]
+fn test_shr() {
+ fn check(s: &str, shift: usize, ans: &str) {
+ let opt_biguint = BigUint::from_str_radix(s, 16).ok();
+ let mut bu_assign = opt_biguint.unwrap();
+ let bu = (bu_assign.clone() >> shift).to_str_radix(16);
+ assert_eq!(bu, ans);
+ bu_assign >>= shift;
+ assert_eq!(bu_assign.to_str_radix(16), ans);
+ }
+
+ check("0", 3, "0");
+ check("f", 3, "1");
+
+ check(
+ "1\
+ 0000\
+ 0000\
+ 0000\
+ 0001\
+ 0000\
+ 0000\
+ 0000\
+ 0001",
+ 3,
+ "2000\
+ 0000\
+ 0000\
+ 0000\
+ 2000\
+ 0000\
+ 0000\
+ 0000",
+ );
+ check(
+ "1\
+ 0000\
+ 0001\
+ 0000\
+ 0001",
+ 2,
+ "4000\
+ 0000\
+ 4000\
+ 0000",
+ );
+ check(
+ "1\
+ 0001\
+ 0001",
+ 1,
+ "8000\
+ 8000",
+ );
+
+ check(
+ "2\
+ 0000\
+ 0000\
+ 0000\
+ 0001\
+ 0000\
+ 0000\
+ 0000\
+ 0001",
+ 67,
+ "4000\
+ 0000\
+ 0000\
+ 0000",
+ );
+ check(
+ "2\
+ 0000\
+ 0001\
+ 0000\
+ 0001",
+ 35,
+ "4000\
+ 0000",
+ );
+ check(
+ "2\
+ 0001\
+ 0001",
+ 19,
+ "4000",
+ );
+
+ check(
+ "1\
+ 0000\
+ 0000\
+ 0000\
+ 0000",
+ 1,
+ "8000\
+ 0000\
+ 0000\
+ 0000",
+ );
+ check(
+ "1\
+ 0000\
+ 0000",
+ 1,
+ "8000\
+ 0000",
+ );
+ check(
+ "1\
+ 0000",
+ 1,
+ "8000",
+ );
+ check(
+ "f\
+ edcb\
+ a987\
+ 6543\
+ 210f\
+ edcb\
+ a987\
+ 6543\
+ 2100",
+ 4,
+ "fedc\
+ ba98\
+ 7654\
+ 3210\
+ fedc\
+ ba98\
+ 7654\
+ 3210",
+ );
+
+ check(
+ "888877776666555544443333222211110000",
+ 16,
+ "88887777666655554444333322221111",
+ );
+}
+
+// `DoubleBigDigit` size dependent
+#[test]
+fn test_convert_i64() {
+ fn check(b1: BigUint, i: i64) {
+ let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
+ assert_eq!(b1, b2);
+ assert_eq!(b1.to_i64().unwrap(), i);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(i64::MAX.to_biguint().unwrap(), i64::MAX);
+
+ check(BigUint::new(vec![]), 0);
+ check(BigUint::new(vec![1]), 1);
+ check(BigUint::new(vec![N1]), (1 << 32) - 1);
+ check(BigUint::new(vec![0, 1]), 1 << 32);
+ check(BigUint::new(vec![N1, N1 >> 1]), i64::MAX);
+
+ assert_eq!(i64::MIN.to_biguint(), None);
+ assert_eq!(BigUint::new(vec![N1, N1]).to_i64(), None);
+ assert_eq!(BigUint::new(vec![0, 0, 1]).to_i64(), None);
+ assert_eq!(BigUint::new(vec![N1, N1, N1]).to_i64(), None);
+}
+
+#[test]
+#[cfg(has_i128)]
+fn test_convert_i128() {
+ fn check(b1: BigUint, i: i128) {
+ let b2: BigUint = FromPrimitive::from_i128(i).unwrap();
+ assert_eq!(b1, b2);
+ assert_eq!(b1.to_i128().unwrap(), i);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(i128::MAX.to_biguint().unwrap(), i128::MAX);
+
+ check(BigUint::new(vec![]), 0);
+ check(BigUint::new(vec![1]), 1);
+ check(BigUint::new(vec![N1]), (1 << 32) - 1);
+ check(BigUint::new(vec![0, 1]), 1 << 32);
+ check(BigUint::new(vec![N1, N1, N1, N1 >> 1]), i128::MAX);
+
+ assert_eq!(i128::MIN.to_biguint(), None);
+ assert_eq!(BigUint::new(vec![N1, N1, N1, N1]).to_i128(), None);
+ assert_eq!(BigUint::new(vec![0, 0, 0, 0, 1]).to_i128(), None);
+ assert_eq!(BigUint::new(vec![N1, N1, N1, N1, N1]).to_i128(), None);
+}
+
+// `DoubleBigDigit` size dependent
+#[test]
+fn test_convert_u64() {
+ fn check(b1: BigUint, u: u64) {
+ let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
+ assert_eq!(b1, b2);
+ assert_eq!(b1.to_u64().unwrap(), u);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(u64::MIN.to_biguint().unwrap(), u64::MIN);
+ check(u64::MAX.to_biguint().unwrap(), u64::MAX);
+
+ check(BigUint::new(vec![]), 0);
+ check(BigUint::new(vec![1]), 1);
+ check(BigUint::new(vec![N1]), (1 << 32) - 1);
+ check(BigUint::new(vec![0, 1]), 1 << 32);
+ check(BigUint::new(vec![N1, N1]), u64::MAX);
+
+ assert_eq!(BigUint::new(vec![0, 0, 1]).to_u64(), None);
+ assert_eq!(BigUint::new(vec![N1, N1, N1]).to_u64(), None);
+}
+
+#[test]
+#[cfg(has_i128)]
+fn test_convert_u128() {
+ fn check(b1: BigUint, u: u128) {
+ let b2: BigUint = FromPrimitive::from_u128(u).unwrap();
+ assert_eq!(b1, b2);
+ assert_eq!(b1.to_u128().unwrap(), u);
+ }
+
+ check(Zero::zero(), 0);
+ check(One::one(), 1);
+ check(u128::MIN.to_biguint().unwrap(), u128::MIN);
+ check(u128::MAX.to_biguint().unwrap(), u128::MAX);
+
+ check(BigUint::new(vec![]), 0);
+ check(BigUint::new(vec![1]), 1);
+ check(BigUint::new(vec![N1]), (1 << 32) - 1);
+ check(BigUint::new(vec![0, 1]), 1 << 32);
+ check(BigUint::new(vec![N1, N1, N1, N1]), u128::MAX);
+
+ assert_eq!(BigUint::new(vec![0, 0, 0, 0, 1]).to_u128(), None);
+ assert_eq!(BigUint::new(vec![N1, N1, N1, N1, N1]).to_u128(), None);
+}
+
+#[test]
+fn test_convert_f32() {
+ fn check(b1: &BigUint, f: f32) {
+ let b2 = BigUint::from_f32(f).unwrap();
+ assert_eq!(b1, &b2);
+ assert_eq!(b1.to_f32().unwrap(), f);
+ }
+
+ check(&BigUint::zero(), 0.0);
+ check(&BigUint::one(), 1.0);
+ check(&BigUint::from(u16::MAX), 2.0.powi(16) - 1.0);
+ check(&BigUint::from(1u64 << 32), 2.0.powi(32));
+ check(&BigUint::from_slice(&[0, 0, 1]), 2.0.powi(64));
+ check(
+ &((BigUint::one() << 100) + (BigUint::one() << 123)),
+ 2.0.powi(100) + 2.0.powi(123),
+ );
+ check(&(BigUint::one() << 127), 2.0.powi(127));
+ check(&(BigUint::from((1u64 << 24) - 1) << (128 - 24)), f32::MAX);
+
+ // keeping all 24 digits with the bits at different offsets to the BigDigits
+ let x: u32 = 0b00000000101111011111011011011101;
+ let mut f = x as f32;
+ let mut b = BigUint::from(x);
+ for _ in 0..64 {
+ check(&b, f);
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // this number when rounded to f64 then f32 isn't the same as when rounded straight to f32
+ let n: u64 = 0b0000000000111111111111111111111111011111111111111111111111111111;
+ assert!((n as f64) as f32 != n as f32);
+ assert_eq!(BigUint::from(n).to_f32(), Some(n as f32));
+
+ // test rounding up with the bits at different offsets to the BigDigits
+ let mut f = ((1u64 << 25) - 1) as f32;
+ let mut b = BigUint::from(1u64 << 25);
+ for _ in 0..64 {
+ assert_eq!(b.to_f32(), Some(f));
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // rounding
+ assert_eq!(BigUint::from_f32(-1.0), None);
+ assert_eq!(BigUint::from_f32(-0.99999), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f32(-0.5), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f32(-0.0), Some(BigUint::zero()));
+ assert_eq!(
+ BigUint::from_f32(f32::MIN_POSITIVE / 2.0),
+ Some(BigUint::zero())
+ );
+ assert_eq!(BigUint::from_f32(f32::MIN_POSITIVE), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f32(0.5), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f32(0.99999), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f32(f32::consts::E), Some(BigUint::from(2u32)));
+ assert_eq!(
+ BigUint::from_f32(f32::consts::PI),
+ Some(BigUint::from(3u32))
+ );
+
+ // special float values
+ assert_eq!(BigUint::from_f32(f32::NAN), None);
+ assert_eq!(BigUint::from_f32(f32::INFINITY), None);
+ assert_eq!(BigUint::from_f32(f32::NEG_INFINITY), None);
+ assert_eq!(BigUint::from_f32(f32::MIN), None);
+
+ // largest BigUint that will round to a finite f32 value
+ let big_num = (BigUint::one() << 128) - BigUint::one() - (BigUint::one() << (128 - 25));
+ assert_eq!(big_num.to_f32(), Some(f32::MAX));
+ assert_eq!((big_num + BigUint::one()).to_f32(), None);
+
+ assert_eq!(((BigUint::one() << 128) - BigUint::one()).to_f32(), None);
+ assert_eq!((BigUint::one() << 128).to_f32(), None);
+}
+
+#[test]
+fn test_convert_f64() {
+ fn check(b1: &BigUint, f: f64) {
+ let b2 = BigUint::from_f64(f).unwrap();
+ assert_eq!(b1, &b2);
+ assert_eq!(b1.to_f64().unwrap(), f);
+ }
+
+ check(&BigUint::zero(), 0.0);
+ check(&BigUint::one(), 1.0);
+ check(&BigUint::from(u32::MAX), 2.0.powi(32) - 1.0);
+ check(&BigUint::from(1u64 << 32), 2.0.powi(32));
+ check(&BigUint::from_slice(&[0, 0, 1]), 2.0.powi(64));
+ check(
+ &((BigUint::one() << 100) + (BigUint::one() << 152)),
+ 2.0.powi(100) + 2.0.powi(152),
+ );
+ check(&(BigUint::one() << 1023), 2.0.powi(1023));
+ check(&(BigUint::from((1u64 << 53) - 1) << (1024 - 53)), f64::MAX);
+
+ // keeping all 53 digits with the bits at different offsets to the BigDigits
+ let x: u64 = 0b0000000000011110111110110111111101110111101111011111011011011101;
+ let mut f = x as f64;
+ let mut b = BigUint::from(x);
+ for _ in 0..128 {
+ check(&b, f);
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // test rounding up with the bits at different offsets to the BigDigits
+ let mut f = ((1u64 << 54) - 1) as f64;
+ let mut b = BigUint::from(1u64 << 54);
+ for _ in 0..128 {
+ assert_eq!(b.to_f64(), Some(f));
+ f *= 2.0;
+ b = b << 1;
+ }
+
+ // rounding
+ assert_eq!(BigUint::from_f64(-1.0), None);
+ assert_eq!(BigUint::from_f64(-0.99999), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f64(-0.5), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f64(-0.0), Some(BigUint::zero()));
+ assert_eq!(
+ BigUint::from_f64(f64::MIN_POSITIVE / 2.0),
+ Some(BigUint::zero())
+ );
+ assert_eq!(BigUint::from_f64(f64::MIN_POSITIVE), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f64(0.5), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f64(0.99999), Some(BigUint::zero()));
+ assert_eq!(BigUint::from_f64(f64::consts::E), Some(BigUint::from(2u32)));
+ assert_eq!(
+ BigUint::from_f64(f64::consts::PI),
+ Some(BigUint::from(3u32))
+ );
+
+ // special float values
+ assert_eq!(BigUint::from_f64(f64::NAN), None);
+ assert_eq!(BigUint::from_f64(f64::INFINITY), None);
+ assert_eq!(BigUint::from_f64(f64::NEG_INFINITY), None);
+ assert_eq!(BigUint::from_f64(f64::MIN), None);
+
+ // largest BigUint that will round to a finite f64 value
+ let big_num = (BigUint::one() << 1024) - BigUint::one() - (BigUint::one() << (1024 - 54));
+ assert_eq!(big_num.to_f64(), Some(f64::MAX));
+ assert_eq!((big_num + BigUint::one()).to_f64(), None);
+
+ assert_eq!(((BigInt::one() << 1024) - BigInt::one()).to_f64(), None);
+ assert_eq!((BigUint::one() << 1024).to_f64(), None);
+}
+
+#[test]
+fn test_convert_to_bigint() {
+ fn check(n: BigUint, ans: BigInt) {
+ assert_eq!(n.to_bigint().unwrap(), ans);
+ assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
+ }
+ check(Zero::zero(), Zero::zero());
+ check(
+ BigUint::new(vec![1, 2, 3]),
+ BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3])),
+ );
+}
+
+#[test]
+fn test_convert_from_uint() {
+ macro_rules! check {
+ ($ty:ident, $max:expr) => {
+ assert_eq!(BigUint::from($ty::zero()), BigUint::zero());
+ assert_eq!(BigUint::from($ty::one()), BigUint::one());
+ assert_eq!(BigUint::from($ty::MAX - $ty::one()), $max - BigUint::one());
+ assert_eq!(BigUint::from($ty::MAX), $max);
+ };
+ }
+
+ check!(u8, BigUint::from_slice(&[u8::MAX as u32]));
+ check!(u16, BigUint::from_slice(&[u16::MAX as u32]));
+ check!(u32, BigUint::from_slice(&[u32::MAX]));
+ check!(u64, BigUint::from_slice(&[u32::MAX, u32::MAX]));
+ #[cfg(has_i128)]
+ check!(
+ u128,
+ BigUint::from_slice(&[u32::MAX, u32::MAX, u32::MAX, u32::MAX])
+ );
+ check!(usize, BigUint::from(usize::MAX as u64));
+}
+
+#[test]
+fn test_add() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert_op!(a + b == c);
+ assert_op!(b + a == c);
+ assert_assign_op!(a += b == c);
+ assert_assign_op!(b += a == c);
+ }
+}
+
+#[test]
+fn test_sub() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert_op!(c - a == b);
+ assert_op!(c - b == a);
+ assert_assign_op!(c -= a == b);
+ assert_assign_op!(c -= b == a);
+ }
+}
+
+#[test]
+#[should_panic]
+fn test_sub_fail_on_underflow() {
+ let (a, b): (BigUint, BigUint) = (Zero::zero(), One::one());
+ let _ = a - b;
+}
+
+#[test]
+fn test_mul() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert_op!(a * b == c);
+ assert_op!(b * a == c);
+ assert_assign_op!(a *= b == c);
+ assert_assign_op!(b *= a == c);
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+ let d = BigUint::from_slice(d_vec);
+
+ assert!(a == &b * &c + &d);
+ assert!(a == &c * &b + &d);
+ }
+}
+
+#[test]
+fn test_div_rem() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ if !a.is_zero() {
+ assert_op!(c / a == b);
+ assert_op!(c % a == Zero::zero());
+ assert_assign_op!(c /= a == b);
+ assert_assign_op!(c %= a == Zero::zero());
+ assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
+ }
+ if !b.is_zero() {
+ assert_op!(c / b == a);
+ assert_op!(c % b == Zero::zero());
+ assert_assign_op!(c /= b == a);
+ assert_assign_op!(c %= b == Zero::zero());
+ assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+ let d = BigUint::from_slice(d_vec);
+
+ if !b.is_zero() {
+ assert_op!(a / b == c);
+ assert_op!(a % b == d);
+ assert_assign_op!(a /= b == c);
+ assert_assign_op!(a %= b == d);
+ assert!(a.div_rem(&b) == (c, d));
+ }
+ }
+}
+
+#[test]
+fn test_checked_add() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert!(a.checked_add(&b).unwrap() == c);
+ assert!(b.checked_add(&a).unwrap() == c);
+ }
+}
+
+#[test]
+fn test_checked_sub() {
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert!(c.checked_sub(&a).unwrap() == b);
+ assert!(c.checked_sub(&b).unwrap() == a);
+
+ if a > c {
+ assert!(a.checked_sub(&c).is_none());
+ }
+ if b > c {
+ assert!(b.checked_sub(&c).is_none());
+ }
+ }
+}
+
+#[test]
+fn test_checked_mul() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ assert!(a.checked_mul(&b).unwrap() == c);
+ assert!(b.checked_mul(&a).unwrap() == c);
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+ let d = BigUint::from_slice(d_vec);
+
+ assert!(a == b.checked_mul(&c).unwrap() + &d);
+ assert!(a == c.checked_mul(&b).unwrap() + &d);
+ }
+}
+
+#[test]
+fn test_mul_overflow() {
+ /* Test for issue #187 - overflow due to mac3 incorrectly sizing temporary */
+ let s = "531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502232636710047537552105951370000796528760829212940754539968588340162273730474622005920097370111";
+ let a: BigUint = s.parse().unwrap();
+ let b = a.clone();
+ let _ = a.checked_mul(&b);
+}
+
+#[test]
+fn test_checked_div() {
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ if !a.is_zero() {
+ assert!(c.checked_div(&a).unwrap() == b);
+ }
+ if !b.is_zero() {
+ assert!(c.checked_div(&b).unwrap() == a);
+ }
+
+ assert!(c.checked_div(&Zero::zero()).is_none());
+ }
+}
+
+#[test]
+fn test_gcd() {
+ fn check(a: usize, b: usize, c: usize) {
+ let big_a: BigUint = FromPrimitive::from_usize(a).unwrap();
+ let big_b: BigUint = FromPrimitive::from_usize(b).unwrap();
+ let big_c: BigUint = FromPrimitive::from_usize(c).unwrap();
+
+ assert_eq!(big_a.gcd(&big_b), big_c);
+ }
+
+ check(10, 2, 2);
+ check(10, 3, 1);
+ check(0, 3, 3);
+ check(3, 3, 3);
+ check(56, 42, 14);
+}
+
+#[test]
+fn test_lcm() {
+ fn check(a: usize, b: usize, c: usize) {
+ let big_a: BigUint = FromPrimitive::from_usize(a).unwrap();
+ let big_b: BigUint = FromPrimitive::from_usize(b).unwrap();
+ let big_c: BigUint = FromPrimitive::from_usize(c).unwrap();
+
+ assert_eq!(big_a.lcm(&big_b), big_c);
+ }
+
+ check(0, 0, 0);
+ check(1, 0, 0);
+ check(0, 1, 0);
+ check(1, 1, 1);
+ check(8, 9, 72);
+ check(11, 5, 55);
+ check(99, 17, 1683);
+}
+
+#[test]
+fn test_is_even() {
+ let one: BigUint = FromStr::from_str("1").unwrap();
+ let two: BigUint = FromStr::from_str("2").unwrap();
+ let thousand: BigUint = FromStr::from_str("1000").unwrap();
+ let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
+ let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
+ assert!(one.is_odd());
+ assert!(two.is_even());
+ assert!(thousand.is_even());
+ assert!(big.is_even());
+ assert!(bigger.is_odd());
+ assert!((&one << 64).is_even());
+ assert!(((&one << 64) + one).is_odd());
+}
+
+fn to_str_pairs() -> Vec<(BigUint, Vec<(u32, String)>)> {
+ let bits = 32;
+ vec![
+ (
+ Zero::zero(),
+ vec![(2, "0".to_string()), (3, "0".to_string())],
+ ),
+ (
+ BigUint::from_slice(&[0xff]),
+ vec![
+ (2, "11111111".to_string()),
+ (3, "100110".to_string()),
+ (4, "3333".to_string()),
+ (5, "2010".to_string()),
+ (6, "1103".to_string()),
+ (7, "513".to_string()),
+ (8, "377".to_string()),
+ (9, "313".to_string()),
+ (10, "255".to_string()),
+ (11, "212".to_string()),
+ (12, "193".to_string()),
+ (13, "168".to_string()),
+ (14, "143".to_string()),
+ (15, "120".to_string()),
+ (16, "ff".to_string()),
+ ],
+ ),
+ (
+ BigUint::from_slice(&[0xfff]),
+ vec![
+ (2, "111111111111".to_string()),
+ (4, "333333".to_string()),
+ (16, "fff".to_string()),
+ ],
+ ),
+ (
+ BigUint::from_slice(&[1, 2]),
+ vec![
+ (
+ 2,
+ format!("10{}1", repeat("0").take(bits - 1).collect::<String>()),
+ ),
+ (
+ 4,
+ format!("2{}1", repeat("0").take(bits / 2 - 1).collect::<String>()),
+ ),
+ (
+ 10,
+ match bits {
+ 64 => "36893488147419103233".to_string(),
+ 32 => "8589934593".to_string(),
+ 16 => "131073".to_string(),
+ _ => panic!(),
+ },
+ ),
+ (
+ 16,
+ format!("2{}1", repeat("0").take(bits / 4 - 1).collect::<String>()),
+ ),
+ ],
+ ),
+ (
+ BigUint::from_slice(&[1, 2, 3]),
+ vec![
+ (
+ 2,
+ format!(
+ "11{}10{}1",
+ repeat("0").take(bits - 2).collect::<String>(),
+ repeat("0").take(bits - 1).collect::<String>()
+ ),
+ ),
+ (
+ 4,
+ format!(
+ "3{}2{}1",
+ repeat("0").take(bits / 2 - 1).collect::<String>(),
+ repeat("0").take(bits / 2 - 1).collect::<String>()
+ ),
+ ),
+ (
+ 8,
+ match bits {
+ 64 => "14000000000000000000004000000000000000000001".to_string(),
+ 32 => "6000000000100000000001".to_string(),
+ 16 => "140000400001".to_string(),
+ _ => panic!(),
+ },
+ ),
+ (
+ 10,
+ match bits {
+ 64 => "1020847100762815390427017310442723737601".to_string(),
+ 32 => "55340232229718589441".to_string(),
+ 16 => "12885032961".to_string(),
+ _ => panic!(),
+ },
+ ),
+ (
+ 16,
+ format!(
+ "3{}2{}1",
+ repeat("0").take(bits / 4 - 1).collect::<String>(),
+ repeat("0").take(bits / 4 - 1).collect::<String>()
+ ),
+ ),
+ ],
+ ),
+ ]
+}
+
+#[test]
+fn test_to_str_radix() {
+ let r = to_str_pairs();
+ for num_pair in r.iter() {
+ let &(ref n, ref rs) = num_pair;
+ for str_pair in rs.iter() {
+ let &(ref radix, ref str) = str_pair;
+ assert_eq!(n.to_str_radix(*radix), *str);
+ }
+ }
+}
+
+#[test]
+fn test_from_and_to_radix() {
+ const GROUND_TRUTH: &'static [(&'static [u8], u32, &'static [u8])] = &[
+ (b"0", 42, &[0]),
+ (
+ b"ffffeeffbb",
+ 2,
+ &[
+ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ ],
+ ),
+ (
+ b"ffffeeffbb",
+ 3,
+ &[
+ 2, 2, 1, 1, 2, 1, 1, 2, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 1,
+ ],
+ ),
+ (
+ b"ffffeeffbb",
+ 4,
+ &[3, 2, 3, 2, 3, 3, 3, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3],
+ ),
+ (
+ b"ffffeeffbb",
+ 5,
+ &[0, 4, 3, 3, 1, 4, 2, 4, 1, 4, 4, 2, 3, 0, 0, 1, 2, 1],
+ ),
+ (
+ b"ffffeeffbb",
+ 6,
+ &[5, 5, 4, 5, 5, 0, 0, 1, 2, 5, 3, 0, 1, 0, 2, 2],
+ ),
+ (
+ b"ffffeeffbb",
+ 7,
+ &[4, 2, 3, 6, 0, 1, 6, 1, 6, 2, 0, 3, 2, 4, 1],
+ ),
+ (
+ b"ffffeeffbb",
+ 8,
+ &[3, 7, 6, 7, 7, 5, 3, 7, 7, 7, 7, 7, 7, 1],
+ ),
+ (b"ffffeeffbb", 9, &[8, 4, 5, 7, 0, 0, 3, 2, 0, 3, 0, 8, 3]),
+ (b"ffffeeffbb", 10, &[5, 9, 5, 3, 1, 5, 0, 1, 5, 9, 9, 0, 1]),
+ (b"ffffeeffbb", 11, &[10, 7, 6, 5, 2, 0, 3, 3, 3, 4, 9, 3]),
+ (b"ffffeeffbb", 12, &[11, 8, 5, 10, 1, 10, 3, 1, 1, 9, 5, 1]),
+ (b"ffffeeffbb", 13, &[0, 5, 7, 4, 6, 5, 6, 11, 8, 12, 7]),
+ (b"ffffeeffbb", 14, &[11, 4, 4, 11, 8, 4, 6, 0, 3, 11, 3]),
+ (b"ffffeeffbb", 15, &[5, 11, 13, 2, 1, 10, 2, 0, 9, 13, 1]),
+ (b"ffffeeffbb", 16, &[11, 11, 15, 15, 14, 14, 15, 15, 15, 15]),
+ (b"ffffeeffbb", 17, &[0, 2, 14, 12, 2, 14, 8, 10, 4, 9]),
+ (b"ffffeeffbb", 18, &[17, 15, 5, 13, 10, 16, 16, 13, 9, 5]),
+ (b"ffffeeffbb", 19, &[14, 13, 2, 8, 9, 0, 1, 14, 7, 3]),
+ (b"ffffeeffbb", 20, &[15, 19, 3, 14, 0, 17, 19, 18, 2, 2]),
+ (b"ffffeeffbb", 21, &[11, 5, 4, 13, 5, 18, 9, 1, 8, 1]),
+ (b"ffffeeffbb", 22, &[21, 3, 7, 21, 15, 12, 17, 0, 20]),
+ (b"ffffeeffbb", 23, &[21, 21, 6, 9, 10, 7, 21, 0, 14]),
+ (b"ffffeeffbb", 24, &[11, 10, 19, 14, 22, 11, 17, 23, 9]),
+ (b"ffffeeffbb", 25, &[20, 18, 21, 22, 21, 14, 3, 5, 7]),
+ (b"ffffeeffbb", 26, &[13, 15, 24, 11, 17, 6, 23, 6, 5]),
+ (b"ffffeeffbb", 27, &[17, 16, 7, 0, 21, 0, 3, 24, 3]),
+ (b"ffffeeffbb", 28, &[11, 16, 11, 15, 14, 18, 13, 25, 2]),
+ (b"ffffeeffbb", 29, &[6, 8, 7, 19, 14, 13, 21, 5, 2]),
+ (b"ffffeeffbb", 30, &[5, 13, 18, 11, 10, 7, 8, 20, 1]),
+ (b"ffffeeffbb", 31, &[22, 26, 15, 19, 8, 27, 29, 8, 1]),
+ (b"ffffeeffbb", 32, &[27, 29, 31, 29, 30, 31, 31, 31]),
+ (b"ffffeeffbb", 33, &[32, 20, 27, 12, 1, 12, 26, 25]),
+ (b"ffffeeffbb", 34, &[17, 9, 16, 33, 13, 25, 31, 20]),
+ (b"ffffeeffbb", 35, &[25, 32, 2, 25, 11, 4, 3, 17]),
+ (b"ffffeeffbb", 36, &[35, 34, 5, 6, 32, 3, 1, 14]),
+ (b"ffffeeffbb", 37, &[16, 21, 18, 4, 33, 19, 21, 11]),
+ (b"ffffeeffbb", 38, &[33, 25, 19, 29, 20, 6, 23, 9]),
+ (b"ffffeeffbb", 39, &[26, 27, 29, 23, 16, 18, 0, 8]),
+ (b"ffffeeffbb", 40, &[35, 39, 30, 11, 16, 17, 28, 6]),
+ (b"ffffeeffbb", 41, &[36, 30, 9, 18, 12, 19, 26, 5]),
+ (b"ffffeeffbb", 42, &[11, 34, 37, 27, 1, 13, 32, 4]),
+ (b"ffffeeffbb", 43, &[3, 24, 11, 2, 10, 40, 1, 4]),
+ (b"ffffeeffbb", 44, &[43, 12, 40, 32, 3, 23, 19, 3]),
+ (b"ffffeeffbb", 45, &[35, 38, 44, 18, 22, 18, 42, 2]),
+ (b"ffffeeffbb", 46, &[21, 45, 18, 41, 17, 2, 24, 2]),
+ (b"ffffeeffbb", 47, &[37, 37, 11, 12, 6, 0, 8, 2]),
+ (b"ffffeeffbb", 48, &[11, 41, 40, 43, 5, 43, 41, 1]),
+ (b"ffffeeffbb", 49, &[18, 45, 7, 13, 20, 21, 30, 1]),
+ (b"ffffeeffbb", 50, &[45, 21, 5, 34, 21, 18, 20, 1]),
+ (b"ffffeeffbb", 51, &[17, 6, 26, 22, 38, 24, 11, 1]),
+ (b"ffffeeffbb", 52, &[39, 33, 38, 30, 46, 31, 3, 1]),
+ (b"ffffeeffbb", 53, &[31, 7, 44, 23, 9, 32, 49]),
+ (b"ffffeeffbb", 54, &[17, 35, 8, 37, 31, 18, 44]),
+ (b"ffffeeffbb", 55, &[10, 52, 9, 48, 36, 39, 39]),
+ (b"ffffeeffbb", 56, &[11, 50, 51, 22, 25, 36, 35]),
+ (b"ffffeeffbb", 57, &[14, 55, 12, 43, 20, 3, 32]),
+ (b"ffffeeffbb", 58, &[35, 18, 45, 56, 9, 51, 28]),
+ (b"ffffeeffbb", 59, &[51, 28, 20, 26, 55, 3, 26]),
+ (b"ffffeeffbb", 60, &[35, 6, 27, 46, 58, 33, 23]),
+ (b"ffffeeffbb", 61, &[58, 7, 6, 54, 49, 20, 21]),
+ (b"ffffeeffbb", 62, &[53, 59, 3, 14, 10, 22, 19]),
+ (b"ffffeeffbb", 63, &[53, 50, 23, 4, 56, 36, 17]),
+ (b"ffffeeffbb", 64, &[59, 62, 47, 59, 63, 63, 15]),
+ (b"ffffeeffbb", 65, &[0, 53, 39, 4, 40, 37, 14]),
+ (b"ffffeeffbb", 66, &[65, 59, 39, 1, 64, 19, 13]),
+ (b"ffffeeffbb", 67, &[35, 14, 19, 16, 25, 10, 12]),
+ (b"ffffeeffbb", 68, &[51, 38, 63, 50, 15, 8, 11]),
+ (b"ffffeeffbb", 69, &[44, 45, 18, 58, 68, 12, 10]),
+ (b"ffffeeffbb", 70, &[25, 51, 0, 60, 13, 24, 9]),
+ (b"ffffeeffbb", 71, &[54, 30, 9, 65, 28, 41, 8]),
+ (b"ffffeeffbb", 72, &[35, 35, 55, 54, 17, 64, 7]),
+ (b"ffffeeffbb", 73, &[34, 4, 48, 40, 27, 19, 7]),
+ (b"ffffeeffbb", 74, &[53, 47, 4, 56, 36, 51, 6]),
+ (b"ffffeeffbb", 75, &[20, 56, 10, 72, 24, 13, 6]),
+ (b"ffffeeffbb", 76, &[71, 31, 52, 60, 48, 53, 5]),
+ (b"ffffeeffbb", 77, &[32, 73, 14, 63, 15, 21, 5]),
+ (b"ffffeeffbb", 78, &[65, 13, 17, 32, 64, 68, 4]),
+ (b"ffffeeffbb", 79, &[37, 56, 2, 56, 25, 41, 4]),
+ (b"ffffeeffbb", 80, &[75, 59, 37, 41, 43, 15, 4]),
+ (b"ffffeeffbb", 81, &[44, 68, 0, 21, 27, 72, 3]),
+ (b"ffffeeffbb", 82, &[77, 35, 2, 74, 46, 50, 3]),
+ (b"ffffeeffbb", 83, &[52, 51, 19, 76, 10, 30, 3]),
+ (b"ffffeeffbb", 84, &[11, 80, 19, 19, 76, 10, 3]),
+ (b"ffffeeffbb", 85, &[0, 82, 20, 14, 68, 77, 2]),
+ (b"ffffeeffbb", 86, &[3, 12, 78, 37, 62, 61, 2]),
+ (b"ffffeeffbb", 87, &[35, 12, 20, 8, 52, 46, 2]),
+ (b"ffffeeffbb", 88, &[43, 6, 54, 42, 30, 32, 2]),
+ (b"ffffeeffbb", 89, &[49, 52, 85, 21, 80, 18, 2]),
+ (b"ffffeeffbb", 90, &[35, 64, 78, 24, 18, 6, 2]),
+ (b"ffffeeffbb", 91, &[39, 17, 83, 63, 17, 85, 1]),
+ (b"ffffeeffbb", 92, &[67, 22, 85, 79, 75, 74, 1]),
+ (b"ffffeeffbb", 93, &[53, 60, 39, 29, 4, 65, 1]),
+ (b"ffffeeffbb", 94, &[37, 89, 2, 72, 76, 55, 1]),
+ (b"ffffeeffbb", 95, &[90, 74, 89, 9, 9, 47, 1]),
+ (b"ffffeeffbb", 96, &[59, 20, 46, 35, 81, 38, 1]),
+ (b"ffffeeffbb", 97, &[94, 87, 60, 71, 3, 31, 1]),
+ (b"ffffeeffbb", 98, &[67, 22, 63, 50, 62, 23, 1]),
+ (b"ffffeeffbb", 99, &[98, 6, 69, 12, 61, 16, 1]),
+ (b"ffffeeffbb", 100, &[95, 35, 51, 10, 95, 9, 1]),
+ (b"ffffeeffbb", 101, &[87, 27, 7, 8, 62, 3, 1]),
+ (b"ffffeeffbb", 102, &[17, 3, 32, 79, 59, 99]),
+ (b"ffffeeffbb", 103, &[30, 22, 90, 0, 87, 94]),
+ (b"ffffeeffbb", 104, &[91, 68, 87, 68, 38, 90]),
+ (b"ffffeeffbb", 105, &[95, 80, 54, 73, 15, 86]),
+ (b"ffffeeffbb", 106, &[31, 30, 24, 16, 17, 82]),
+ (b"ffffeeffbb", 107, &[51, 50, 10, 12, 42, 78]),
+ (b"ffffeeffbb", 108, &[71, 71, 96, 78, 89, 74]),
+ (b"ffffeeffbb", 109, &[33, 18, 93, 22, 50, 71]),
+ (b"ffffeeffbb", 110, &[65, 53, 57, 88, 29, 68]),
+ (b"ffffeeffbb", 111, &[53, 93, 67, 90, 27, 65]),
+ (b"ffffeeffbb", 112, &[11, 109, 96, 65, 43, 62]),
+ (b"ffffeeffbb", 113, &[27, 23, 106, 56, 76, 59]),
+ (b"ffffeeffbb", 114, &[71, 84, 31, 112, 11, 57]),
+ (b"ffffeeffbb", 115, &[90, 22, 1, 56, 76, 54]),
+ (b"ffffeeffbb", 116, &[35, 38, 98, 57, 40, 52]),
+ (b"ffffeeffbb", 117, &[26, 113, 115, 62, 17, 50]),
+ (b"ffffeeffbb", 118, &[51, 14, 5, 18, 7, 48]),
+ (b"ffffeeffbb", 119, &[102, 31, 110, 108, 8, 46]),
+ (b"ffffeeffbb", 120, &[35, 93, 96, 50, 22, 44]),
+ (b"ffffeeffbb", 121, &[87, 61, 2, 36, 47, 42]),
+ (b"ffffeeffbb", 122, &[119, 64, 1, 22, 83, 40]),
+ (b"ffffeeffbb", 123, &[77, 119, 32, 90, 6, 39]),
+ (b"ffffeeffbb", 124, &[115, 122, 31, 79, 62, 37]),
+ (b"ffffeeffbb", 125, &[95, 108, 47, 74, 3, 36]),
+ (b"ffffeeffbb", 126, &[53, 25, 116, 39, 78, 34]),
+ (b"ffffeeffbb", 127, &[22, 23, 125, 67, 35, 33]),
+ (b"ffffeeffbb", 128, &[59, 127, 59, 127, 127, 31]),
+ (b"ffffeeffbb", 129, &[89, 36, 1, 59, 100, 30]),
+ (b"ffffeeffbb", 130, &[65, 91, 123, 89, 79, 29]),
+ (b"ffffeeffbb", 131, &[58, 72, 39, 63, 65, 28]),
+ (b"ffffeeffbb", 132, &[131, 62, 92, 82, 57, 27]),
+ (b"ffffeeffbb", 133, &[109, 31, 51, 123, 55, 26]),
+ (b"ffffeeffbb", 134, &[35, 74, 21, 27, 60, 25]),
+ (b"ffffeeffbb", 135, &[125, 132, 49, 37, 70, 24]),
+ (b"ffffeeffbb", 136, &[51, 121, 117, 133, 85, 23]),
+ (b"ffffeeffbb", 137, &[113, 60, 135, 22, 107, 22]),
+ (b"ffffeeffbb", 138, &[113, 91, 73, 93, 133, 21]),
+ (b"ffffeeffbb", 139, &[114, 75, 102, 51, 26, 21]),
+ (b"ffffeeffbb", 140, &[95, 25, 35, 16, 62, 20]),
+ (b"ffffeeffbb", 141, &[131, 137, 16, 110, 102, 19]),
+ (b"ffffeeffbb", 142, &[125, 121, 108, 34, 6, 19]),
+ (b"ffffeeffbb", 143, &[65, 78, 138, 55, 55, 18]),
+ (b"ffffeeffbb", 144, &[107, 125, 121, 15, 109, 17]),
+ (b"ffffeeffbb", 145, &[35, 13, 122, 42, 22, 17]),
+ (b"ffffeeffbb", 146, &[107, 38, 103, 123, 83, 16]),
+ (b"ffffeeffbb", 147, &[116, 96, 71, 98, 2, 16]),
+ (b"ffffeeffbb", 148, &[127, 23, 75, 99, 71, 15]),
+ (b"ffffeeffbb", 149, &[136, 110, 53, 114, 144, 14]),
+ (b"ffffeeffbb", 150, &[95, 140, 133, 130, 71, 14]),
+ (b"ffffeeffbb", 151, &[15, 50, 29, 137, 0, 14]),
+ (b"ffffeeffbb", 152, &[147, 15, 89, 121, 83, 13]),
+ (b"ffffeeffbb", 153, &[17, 87, 93, 72, 17, 13]),
+ (b"ffffeeffbb", 154, &[109, 113, 3, 133, 106, 12]),
+ (b"ffffeeffbb", 155, &[115, 141, 120, 139, 44, 12]),
+ (b"ffffeeffbb", 156, &[143, 45, 4, 82, 140, 11]),
+ (b"ffffeeffbb", 157, &[149, 92, 15, 106, 82, 11]),
+ (b"ffffeeffbb", 158, &[37, 107, 79, 46, 26, 11]),
+ (b"ffffeeffbb", 159, &[137, 37, 146, 51, 130, 10]),
+ (b"ffffeeffbb", 160, &[155, 69, 29, 115, 77, 10]),
+ (b"ffffeeffbb", 161, &[67, 98, 46, 68, 26, 10]),
+ (b"ffffeeffbb", 162, &[125, 155, 60, 63, 138, 9]),
+ (b"ffffeeffbb", 163, &[96, 43, 118, 93, 90, 9]),
+ (b"ffffeeffbb", 164, &[159, 99, 123, 152, 43, 9]),
+ (b"ffffeeffbb", 165, &[65, 17, 1, 69, 163, 8]),
+ (b"ffffeeffbb", 166, &[135, 108, 25, 165, 119, 8]),
+ (b"ffffeeffbb", 167, &[165, 116, 164, 103, 77, 8]),
+ (b"ffffeeffbb", 168, &[11, 166, 67, 44, 36, 8]),
+ (b"ffffeeffbb", 169, &[65, 59, 71, 149, 164, 7]),
+ (b"ffffeeffbb", 170, &[85, 83, 26, 76, 126, 7]),
+ (b"ffffeeffbb", 171, &[71, 132, 140, 157, 88, 7]),
+ (b"ffffeeffbb", 172, &[3, 6, 127, 47, 52, 7]),
+ (b"ffffeeffbb", 173, &[122, 66, 53, 83, 16, 7]),
+ (b"ffffeeffbb", 174, &[35, 6, 5, 88, 155, 6]),
+ (b"ffffeeffbb", 175, &[95, 20, 84, 56, 122, 6]),
+ (b"ffffeeffbb", 176, &[43, 91, 57, 159, 89, 6]),
+ (b"ffffeeffbb", 177, &[110, 127, 54, 40, 58, 6]),
+ (b"ffffeeffbb", 178, &[49, 115, 43, 47, 27, 6]),
+ (b"ffffeeffbb", 179, &[130, 91, 4, 178, 175, 5]),
+ (b"ffffeeffbb", 180, &[35, 122, 109, 70, 147, 5]),
+ (b"ffffeeffbb", 181, &[94, 94, 4, 79, 119, 5]),
+ (b"ffffeeffbb", 182, &[39, 54, 66, 19, 92, 5]),
+ (b"ffffeeffbb", 183, &[119, 2, 143, 69, 65, 5]),
+ (b"ffffeeffbb", 184, &[67, 57, 90, 44, 39, 5]),
+ (b"ffffeeffbb", 185, &[90, 63, 141, 123, 13, 5]),
+ (b"ffffeeffbb", 186, &[53, 123, 172, 119, 174, 4]),
+ (b"ffffeeffbb", 187, &[153, 21, 68, 28, 151, 4]),
+ (b"ffffeeffbb", 188, &[131, 138, 94, 32, 128, 4]),
+ (b"ffffeeffbb", 189, &[179, 121, 156, 130, 105, 4]),
+ (b"ffffeeffbb", 190, &[185, 179, 164, 131, 83, 4]),
+ (b"ffffeeffbb", 191, &[118, 123, 37, 31, 62, 4]),
+ (b"ffffeeffbb", 192, &[59, 106, 83, 16, 41, 4]),
+ (b"ffffeeffbb", 193, &[57, 37, 47, 86, 20, 4]),
+ (b"ffffeeffbb", 194, &[191, 140, 63, 45, 0, 4]),
+ (b"ffffeeffbb", 195, &[65, 169, 83, 84, 175, 3]),
+ (b"ffffeeffbb", 196, &[67, 158, 64, 6, 157, 3]),
+ (b"ffffeeffbb", 197, &[121, 26, 167, 3, 139, 3]),
+ (b"ffffeeffbb", 198, &[197, 151, 165, 75, 121, 3]),
+ (b"ffffeeffbb", 199, &[55, 175, 36, 22, 104, 3]),
+ (b"ffffeeffbb", 200, &[195, 167, 162, 38, 87, 3]),
+ (b"ffffeeffbb", 201, &[35, 27, 136, 124, 70, 3]),
+ (b"ffffeeffbb", 202, &[87, 64, 153, 76, 54, 3]),
+ (b"ffffeeffbb", 203, &[151, 191, 14, 94, 38, 3]),
+ (b"ffffeeffbb", 204, &[119, 103, 135, 175, 22, 3]),
+ (b"ffffeeffbb", 205, &[200, 79, 123, 115, 7, 3]),
+ (b"ffffeeffbb", 206, &[133, 165, 202, 115, 198, 2]),
+ (b"ffffeeffbb", 207, &[44, 153, 193, 175, 184, 2]),
+ (b"ffffeeffbb", 208, &[91, 190, 125, 86, 171, 2]),
+ (b"ffffeeffbb", 209, &[109, 151, 34, 53, 158, 2]),
+ (b"ffffeeffbb", 210, &[95, 40, 171, 74, 145, 2]),
+ (b"ffffeeffbb", 211, &[84, 195, 162, 150, 132, 2]),
+ (b"ffffeeffbb", 212, &[31, 15, 59, 68, 120, 2]),
+ (b"ffffeeffbb", 213, &[125, 57, 127, 36, 108, 2]),
+ (b"ffffeeffbb", 214, &[51, 132, 2, 55, 96, 2]),
+ (b"ffffeeffbb", 215, &[175, 133, 177, 122, 84, 2]),
+ (b"ffffeeffbb", 216, &[179, 35, 78, 23, 73, 2]),
+ (b"ffffeeffbb", 217, &[53, 101, 208, 186, 61, 2]),
+ (b"ffffeeffbb", 218, &[33, 9, 214, 179, 50, 2]),
+ (b"ffffeeffbb", 219, &[107, 147, 175, 217, 39, 2]),
+ (b"ffffeeffbb", 220, &[175, 81, 179, 79, 29, 2]),
+ (b"ffffeeffbb", 221, &[0, 76, 95, 204, 18, 2]),
+ (b"ffffeeffbb", 222, &[53, 213, 16, 150, 8, 2]),
+ (b"ffffeeffbb", 223, &[158, 161, 42, 136, 221, 1]),
+ (b"ffffeeffbb", 224, &[123, 54, 52, 162, 212, 1]),
+ (b"ffffeeffbb", 225, &[170, 43, 151, 2, 204, 1]),
+ (b"ffffeeffbb", 226, &[27, 68, 224, 105, 195, 1]),
+ (b"ffffeeffbb", 227, &[45, 69, 157, 20, 187, 1]),
+ (b"ffffeeffbb", 228, &[71, 213, 64, 199, 178, 1]),
+ (b"ffffeeffbb", 229, &[129, 203, 66, 186, 170, 1]),
+ (b"ffffeeffbb", 230, &[205, 183, 57, 208, 162, 1]),
+ (b"ffffeeffbb", 231, &[32, 50, 164, 33, 155, 1]),
+ (b"ffffeeffbb", 232, &[35, 135, 53, 123, 147, 1]),
+ (b"ffffeeffbb", 233, &[209, 47, 89, 13, 140, 1]),
+ (b"ffffeeffbb", 234, &[143, 56, 175, 168, 132, 1]),
+ (b"ffffeeffbb", 235, &[225, 157, 216, 121, 125, 1]),
+ (b"ffffeeffbb", 236, &[51, 66, 119, 105, 118, 1]),
+ (b"ffffeeffbb", 237, &[116, 150, 26, 119, 111, 1]),
+ (b"ffffeeffbb", 238, &[221, 15, 87, 162, 104, 1]),
+ (b"ffffeeffbb", 239, &[234, 155, 214, 234, 97, 1]),
+ (b"ffffeeffbb", 240, &[155, 46, 84, 96, 91, 1]),
+ (b"ffffeeffbb", 241, &[187, 48, 90, 225, 84, 1]),
+ (b"ffffeeffbb", 242, &[87, 212, 151, 140, 78, 1]),
+ (b"ffffeeffbb", 243, &[206, 22, 189, 81, 72, 1]),
+ (b"ffffeeffbb", 244, &[119, 93, 122, 48, 66, 1]),
+ (b"ffffeeffbb", 245, &[165, 224, 117, 40, 60, 1]),
+ (b"ffffeeffbb", 246, &[77, 121, 100, 57, 54, 1]),
+ (b"ffffeeffbb", 247, &[52, 128, 242, 98, 48, 1]),
+ (b"ffffeeffbb", 248, &[115, 247, 224, 164, 42, 1]),
+ (b"ffffeeffbb", 249, &[218, 127, 223, 5, 37, 1]),
+ (b"ffffeeffbb", 250, &[95, 54, 168, 118, 31, 1]),
+ (b"ffffeeffbb", 251, &[121, 204, 240, 3, 26, 1]),
+ (b"ffffeeffbb", 252, &[179, 138, 123, 162, 20, 1]),
+ (b"ffffeeffbb", 253, &[21, 50, 1, 91, 15, 1]),
+ (b"ffffeeffbb", 254, &[149, 11, 63, 40, 10, 1]),
+ (b"ffffeeffbb", 255, &[170, 225, 247, 9, 5, 1]),
+ (b"ffffeeffbb", 256, &[187, 255, 238, 255, 255]),
+ ];
+
+ for &(bigint, radix, inbaseradix_le) in GROUND_TRUTH.iter() {
+ let bigint = BigUint::parse_bytes(bigint, 16).unwrap();
+ // to_radix_le
+ assert_eq!(bigint.to_radix_le(radix), inbaseradix_le);
+ // to_radix_be
+ let mut inbase_be = bigint.to_radix_be(radix);
+ inbase_be.reverse(); // now le
+ assert_eq!(inbase_be, inbaseradix_le);
+ // from_radix_le
+ assert_eq!(
+ BigUint::from_radix_le(inbaseradix_le, radix).unwrap(),
+ bigint
+ );
+ // from_radix_be
+ let mut inbaseradix_be = Vec::from(inbaseradix_le);
+ inbaseradix_be.reverse();
+ assert_eq!(
+ BigUint::from_radix_be(&inbaseradix_be, radix).unwrap(),
+ bigint
+ );
+ }
+
+ assert!(BigUint::from_radix_le(&[10, 100, 10], 50).is_none());
+}
+
+#[test]
+fn test_from_str_radix() {
+ let r = to_str_pairs();
+ for num_pair in r.iter() {
+ let &(ref n, ref rs) = num_pair;
+ for str_pair in rs.iter() {
+ let &(ref radix, ref str) = str_pair;
+ assert_eq!(n, &BigUint::from_str_radix(str, *radix).unwrap());
+ }
+ }
+
+ let zed = BigUint::from_str_radix("Z", 10).ok();
+ assert_eq!(zed, None);
+ let blank = BigUint::from_str_radix("_", 2).ok();
+ assert_eq!(blank, None);
+ let blank_one = BigUint::from_str_radix("_1", 2).ok();
+ assert_eq!(blank_one, None);
+ let plus_one = BigUint::from_str_radix("+1", 10).ok();
+ assert_eq!(plus_one, Some(BigUint::from_slice(&[1])));
+ let plus_plus_one = BigUint::from_str_radix("++1", 10).ok();
+ assert_eq!(plus_plus_one, None);
+ let minus_one = BigUint::from_str_radix("-1", 10).ok();
+ assert_eq!(minus_one, None);
+ let zero_plus_two = BigUint::from_str_radix("0+2", 10).ok();
+ assert_eq!(zero_plus_two, None);
+ let three = BigUint::from_str_radix("1_1", 2).ok();
+ assert_eq!(three, Some(BigUint::from_slice(&[3])));
+ let ff = BigUint::from_str_radix("1111_1111", 2).ok();
+ assert_eq!(ff, Some(BigUint::from_slice(&[0xff])));
+}
+
+#[test]
+fn test_all_str_radix() {
+ #[allow(deprecated, unused_imports)]
+ use std::ascii::AsciiExt;
+
+ let n = BigUint::new((0..10).collect());
+ for radix in 2..37 {
+ let s = n.to_str_radix(radix);
+ let x = BigUint::from_str_radix(&s, radix);
+ assert_eq!(x.unwrap(), n);
+
+ let s = s.to_ascii_uppercase();
+ let x = BigUint::from_str_radix(&s, radix);
+ assert_eq!(x.unwrap(), n);
+ }
+}
+
+#[test]
+fn test_lower_hex() {
+ let a = BigUint::parse_bytes(b"A", 16).unwrap();
+ let hello = BigUint::parse_bytes("22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:x}", a), "a");
+ assert_eq!(format!("{:x}", hello), "48656c6c6f20776f726c6421");
+ assert_eq!(format!("{:♥>+#8x}", a), "♥♥♥♥+0xa");
+}
+
+#[test]
+fn test_upper_hex() {
+ let a = BigUint::parse_bytes(b"A", 16).unwrap();
+ let hello = BigUint::parse_bytes("22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:X}", a), "A");
+ assert_eq!(format!("{:X}", hello), "48656C6C6F20776F726C6421");
+ assert_eq!(format!("{:♥>+#8X}", a), "♥♥♥♥+0xA");
+}
+
+#[test]
+fn test_binary() {
+ let a = BigUint::parse_bytes(b"A", 16).unwrap();
+ let hello = BigUint::parse_bytes("224055342307539".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:b}", a), "1010");
+ assert_eq!(
+ format!("{:b}", hello),
+ "110010111100011011110011000101101001100011010011"
+ );
+ assert_eq!(format!("{:♥>+#8b}", a), "♥+0b1010");
+}
+
+#[test]
+fn test_octal() {
+ let a = BigUint::parse_bytes(b"A", 16).unwrap();
+ let hello = BigUint::parse_bytes("22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{:o}", a), "12");
+ assert_eq!(format!("{:o}", hello), "22062554330674403566756233062041");
+ assert_eq!(format!("{:♥>+#8o}", a), "♥♥♥+0o12");
+}
+
+#[test]
+fn test_display() {
+ let a = BigUint::parse_bytes(b"A", 16).unwrap();
+ let hello = BigUint::parse_bytes("22405534230753963835153736737".as_bytes(), 10).unwrap();
+
+ assert_eq!(format!("{}", a), "10");
+ assert_eq!(format!("{}", hello), "22405534230753963835153736737");
+ assert_eq!(format!("{:♥>+#8}", a), "♥♥♥♥♥+10");
+}
+
+#[test]
+fn test_factor() {
+ fn factor(n: usize) -> BigUint {
+ let mut f: BigUint = One::one();
+ for i in 2..n + 1 {
+ // FIXME(#5992): assignment operator overloads
+ // f *= FromPrimitive::from_usize(i);
+ let bu: BigUint = FromPrimitive::from_usize(i).unwrap();
+ f = f * bu;
+ }
+ return f;
+ }
+
+ fn check(n: usize, s: &str) {
+ let n = factor(n);
+ let ans = match BigUint::from_str_radix(s, 10) {
+ Ok(x) => x,
+ Err(_) => panic!(),
+ };
+ assert_eq!(n, ans);
+ }
+
+ check(3, "6");
+ check(10, "3628800");
+ check(20, "2432902008176640000");
+ check(30, "265252859812191058636308480000000");
+}
+
+#[test]
+fn test_bits() {
+ assert_eq!(BigUint::new(vec![0, 0, 0, 0]).bits(), 0);
+ let n: BigUint = FromPrimitive::from_usize(0).unwrap();
+ assert_eq!(n.bits(), 0);
+ let n: BigUint = FromPrimitive::from_usize(1).unwrap();
+ assert_eq!(n.bits(), 1);
+ let n: BigUint = FromPrimitive::from_usize(3).unwrap();
+ assert_eq!(n.bits(), 2);
+ let n: BigUint = BigUint::from_str_radix("4000000000", 16).unwrap();
+ assert_eq!(n.bits(), 39);
+ let one: BigUint = One::one();
+ assert_eq!((one << 426).bits(), 427);
+}
+
+#[test]
+fn test_iter_sum() {
+ let result: BigUint = FromPrimitive::from_isize(1234567).unwrap();
+ let data: Vec<BigUint> = vec![
+ FromPrimitive::from_u32(1000000).unwrap(),
+ FromPrimitive::from_u32(200000).unwrap(),
+ FromPrimitive::from_u32(30000).unwrap(),
+ FromPrimitive::from_u32(4000).unwrap(),
+ FromPrimitive::from_u32(500).unwrap(),
+ FromPrimitive::from_u32(60).unwrap(),
+ FromPrimitive::from_u32(7).unwrap(),
+ ];
+
+ assert_eq!(result, data.iter().sum());
+ assert_eq!(result, data.into_iter().sum());
+}
+
+#[test]
+fn test_iter_product() {
+ let data: Vec<BigUint> = vec![
+ FromPrimitive::from_u32(1001).unwrap(),
+ FromPrimitive::from_u32(1002).unwrap(),
+ FromPrimitive::from_u32(1003).unwrap(),
+ FromPrimitive::from_u32(1004).unwrap(),
+ FromPrimitive::from_u32(1005).unwrap(),
+ ];
+ let result = data.get(0).unwrap()
+ * data.get(1).unwrap()
+ * data.get(2).unwrap()
+ * data.get(3).unwrap()
+ * data.get(4).unwrap();
+
+ assert_eq!(result, data.iter().product());
+ assert_eq!(result, data.into_iter().product());
+}
+
+#[test]
+fn test_iter_sum_generic() {
+ let result: BigUint = FromPrimitive::from_isize(1234567).unwrap();
+ let data = vec![1000000_u32, 200000, 30000, 4000, 500, 60, 7];
+
+ assert_eq!(result, data.iter().sum());
+ assert_eq!(result, data.into_iter().sum());
+}
+
+#[test]
+fn test_iter_product_generic() {
+ let data = vec![1001_u32, 1002, 1003, 1004, 1005];
+ let result = data[0].to_biguint().unwrap()
+ * data[1].to_biguint().unwrap()
+ * data[2].to_biguint().unwrap()
+ * data[3].to_biguint().unwrap()
+ * data[4].to_biguint().unwrap();
+
+ assert_eq!(result, data.iter().product());
+ assert_eq!(result, data.into_iter().product());
+}
+
+#[test]
+fn test_pow() {
+ let one = BigUint::from(1u32);
+ let two = BigUint::from(2u32);
+ let four = BigUint::from(4u32);
+ let eight = BigUint::from(8u32);
+ let tentwentyfour = BigUint::from(1024u32);
+ let twentyfourtyeight = BigUint::from(2048u32);
+ macro_rules! check {
+ ($t:ty) => {
+ assert_eq!(two.pow(0 as $t), one);
+ assert_eq!(two.pow(1 as $t), two);
+ assert_eq!(two.pow(2 as $t), four);
+ assert_eq!(two.pow(3 as $t), eight);
+ assert_eq!(two.pow(10 as $t), tentwentyfour);
+ assert_eq!(two.pow(11 as $t), twentyfourtyeight);
+ assert_eq!(two.pow(&(11 as $t)), twentyfourtyeight);
+ };
+ }
+ check!(u8);
+ check!(u16);
+ check!(u32);
+ check!(u64);
+ check!(usize);
+ #[cfg(has_i128)]
+ check!(u128);
+}
diff --git a/third_party/rust/num-bigint/tests/biguint_scalar.rs b/third_party/rust/num-bigint/tests/biguint_scalar.rs
new file mode 100644
index 0000000000..fb8fbf0357
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/biguint_scalar.rs
@@ -0,0 +1,109 @@
+extern crate num_bigint;
+extern crate num_traits;
+
+use num_bigint::BigUint;
+use num_traits::{ToPrimitive, Zero};
+
+mod consts;
+use consts::*;
+
+#[macro_use]
+mod macros;
+
+#[test]
+fn test_scalar_add() {
+ fn check(x: &BigUint, y: &BigUint, z: &BigUint) {
+ let (x, y, z) = (x.clone(), y.clone(), z.clone());
+ assert_unsigned_scalar_op!(x + y == z);
+ }
+
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ check(&a, &b, &c);
+ check(&b, &a, &c);
+ }
+}
+
+#[test]
+fn test_scalar_sub() {
+ fn check(x: &BigUint, y: &BigUint, z: &BigUint) {
+ let (x, y, z) = (x.clone(), y.clone(), z.clone());
+ assert_unsigned_scalar_op!(x - y == z);
+ }
+
+ for elm in SUM_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ check(&c, &a, &b);
+ check(&c, &b, &a);
+ }
+}
+
+#[test]
+fn test_scalar_mul() {
+ fn check(x: &BigUint, y: &BigUint, z: &BigUint) {
+ let (x, y, z) = (x.clone(), y.clone(), z.clone());
+ assert_unsigned_scalar_op!(x * y == z);
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ check(&a, &b, &c);
+ check(&b, &a, &c);
+ }
+}
+
+#[test]
+fn test_scalar_rem_noncommutative() {
+ assert_eq!(5u8 % BigUint::from(7u8), 5u8.into());
+ assert_eq!(BigUint::from(5u8) % 7u8, 5u8.into());
+}
+
+#[test]
+fn test_scalar_div_rem() {
+ fn check(x: &BigUint, y: &BigUint, z: &BigUint, r: &BigUint) {
+ let (x, y, z, r) = (x.clone(), y.clone(), z.clone(), r.clone());
+ assert_unsigned_scalar_op!(x / y == z);
+ assert_unsigned_scalar_op!(x % y == r);
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ if !a.is_zero() {
+ check(&c, &a, &b, &Zero::zero());
+ }
+
+ if !b.is_zero() {
+ check(&c, &b, &a, &Zero::zero());
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+ let d = BigUint::from_slice(d_vec);
+
+ if !b.is_zero() {
+ check(&a, &b, &c, &d);
+ assert_unsigned_scalar_op!(a / b == c);
+ assert_unsigned_scalar_op!(a % b == d);
+ }
+ }
+}
diff --git a/third_party/rust/num-bigint/tests/consts/mod.rs b/third_party/rust/num-bigint/tests/consts/mod.rs
new file mode 100644
index 0000000000..87805d5e24
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/consts/mod.rs
@@ -0,0 +1,56 @@
+#![allow(unused)]
+
+pub const N1: u32 = -1i32 as u32;
+pub const N2: u32 = -2i32 as u32;
+
+pub const SUM_TRIPLES: &'static [(&'static [u32], &'static [u32], &'static [u32])] = &[
+ (&[], &[], &[]),
+ (&[], &[1], &[1]),
+ (&[1], &[1], &[2]),
+ (&[1], &[1, 1], &[2, 1]),
+ (&[1], &[N1], &[0, 1]),
+ (&[1], &[N1, N1], &[0, 0, 1]),
+ (&[N1, N1], &[N1, N1], &[N2, N1, 1]),
+ (&[1, 1, 1], &[N1, N1], &[0, 1, 2]),
+ (&[2, 2, 1], &[N1, N2], &[1, 1, 2]),
+ (&[1, 2, 2, 1], &[N1, N2], &[0, 1, 3, 1]),
+];
+
+pub const M: u32 = ::std::u32::MAX;
+pub const MUL_TRIPLES: &'static [(&'static [u32], &'static [u32], &'static [u32])] = &[
+ (&[], &[], &[]),
+ (&[], &[1], &[]),
+ (&[2], &[], &[]),
+ (&[1], &[1], &[1]),
+ (&[2], &[3], &[6]),
+ (&[1], &[1, 1, 1], &[1, 1, 1]),
+ (&[1, 2, 3], &[3], &[3, 6, 9]),
+ (&[1, 1, 1], &[N1], &[N1, N1, N1]),
+ (&[1, 2, 3], &[N1], &[N1, N2, N2, 2]),
+ (&[1, 2, 3, 4], &[N1], &[N1, N2, N2, N2, 3]),
+ (&[N1], &[N1], &[1, N2]),
+ (&[N1, N1], &[N1], &[1, N1, N2]),
+ (&[N1, N1, N1], &[N1], &[1, N1, N1, N2]),
+ (&[N1, N1, N1, N1], &[N1], &[1, N1, N1, N1, N2]),
+ (&[M / 2 + 1], &[2], &[0, 1]),
+ (&[0, M / 2 + 1], &[2], &[0, 0, 1]),
+ (&[1, 2], &[1, 2, 3], &[1, 4, 7, 6]),
+ (&[N1, N1], &[N1, N1, N1], &[1, 0, N1, N2, N1]),
+ (&[N1, N1, N1], &[N1, N1, N1, N1], &[1, 0, 0, N1, N2, N1, N1]),
+ (&[0, 0, 1], &[1, 2, 3], &[0, 0, 1, 2, 3]),
+ (&[0, 0, 1], &[0, 0, 0, 1], &[0, 0, 0, 0, 0, 1]),
+];
+
+pub const DIV_REM_QUADRUPLES: &'static [(
+ &'static [u32],
+ &'static [u32],
+ &'static [u32],
+ &'static [u32],
+)] = &[
+ (&[1], &[2], &[], &[1]),
+ (&[3], &[2], &[1], &[1]),
+ (&[1, 1], &[2], &[M / 2 + 1], &[1]),
+ (&[1, 1, 1], &[2], &[M / 2 + 1, M / 2 + 1], &[1]),
+ (&[0, 1], &[N1], &[1], &[1]),
+ (&[N1, N1], &[N2], &[2, 1], &[3]),
+];
diff --git a/third_party/rust/num-bigint/tests/macros/mod.rs b/third_party/rust/num-bigint/tests/macros/mod.rs
new file mode 100644
index 0000000000..d848b29b35
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/macros/mod.rs
@@ -0,0 +1,70 @@
+#![allow(unused)]
+
+/// Assert that an op works for all val/ref combinations
+macro_rules! assert_op {
+ ($left:ident $op:tt $right:ident == $expected:expr) => {
+ assert_eq!((&$left) $op (&$right), $expected);
+ assert_eq!((&$left) $op $right.clone(), $expected);
+ assert_eq!($left.clone() $op (&$right), $expected);
+ assert_eq!($left.clone() $op $right.clone(), $expected);
+ };
+}
+
+/// Assert that an assign-op works for all val/ref combinations
+macro_rules! assert_assign_op {
+ ($left:ident $op:tt $right:ident == $expected:expr) => {{
+ let mut left = $left.clone();
+ assert_eq!({ left $op &$right; left}, $expected);
+
+ let mut left = $left.clone();
+ assert_eq!({ left $op $right.clone(); left}, $expected);
+ }};
+}
+
+/// Assert that an op works for scalar left or right
+macro_rules! assert_scalar_op {
+ (($($to:ident),*) $left:ident $op:tt $right:ident == $expected:expr) => {
+ $(
+ if let Some(left) = $left.$to() {
+ assert_op!(left $op $right == $expected);
+ }
+ if let Some(right) = $right.$to() {
+ assert_op!($left $op right == $expected);
+ }
+ )*
+ };
+}
+
+#[cfg(not(has_i128))]
+macro_rules! assert_unsigned_scalar_op {
+ ($left:ident $op:tt $right:ident == $expected:expr) => {
+ assert_scalar_op!((to_u8, to_u16, to_u32, to_u64, to_usize)
+ $left $op $right == $expected);
+ };
+}
+
+#[cfg(has_i128)]
+macro_rules! assert_unsigned_scalar_op {
+ ($left:ident $op:tt $right:ident == $expected:expr) => {
+ assert_scalar_op!((to_u8, to_u16, to_u32, to_u64, to_usize, to_u128)
+ $left $op $right == $expected);
+ };
+}
+
+#[cfg(not(has_i128))]
+macro_rules! assert_signed_scalar_op {
+ ($left:ident $op:tt $right:ident == $expected:expr) => {
+ assert_scalar_op!((to_u8, to_u16, to_u32, to_u64, to_usize,
+ to_i8, to_i16, to_i32, to_i64, to_isize)
+ $left $op $right == $expected);
+ };
+}
+
+#[cfg(has_i128)]
+macro_rules! assert_signed_scalar_op {
+ ($left:ident $op:tt $right:ident == $expected:expr) => {
+ assert_scalar_op!((to_u8, to_u16, to_u32, to_u64, to_usize, to_u128,
+ to_i8, to_i16, to_i32, to_i64, to_isize, to_i128)
+ $left $op $right == $expected);
+ };
+}
diff --git a/third_party/rust/num-bigint/tests/modpow.rs b/third_party/rust/num-bigint/tests/modpow.rs
new file mode 100644
index 0000000000..b7a992c863
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/modpow.rs
@@ -0,0 +1,150 @@
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+
+static BIG_B: &'static str = "\
+ efac3c0a_0de55551_fee0bfe4_67fa017a_1a898fa1_6ca57cb1\
+ ca9e3248_cacc09a9_b99d6abc_38418d0f_82ae4238_d9a68832\
+ aadec7c1_ac5fed48_7a56a71b_67ac59d5_afb28022_20d9592d\
+ 247c4efc_abbd9b75_586088ee_1dc00dc4_232a8e15_6e8191dd\
+ 675b6ae0_c80f5164_752940bc_284b7cee_885c1e10_e495345b\
+ 8fbe9cfd_e5233fe1_19459d0b_d64be53c_27de5a02_a829976b\
+ 33096862_82dad291_bd38b6a9_be396646_ddaf8039_a2573c39\
+ 1b14e8bc_2cb53e48_298c047e_d9879e9c_5a521076_f0e27df3\
+ 990e1659_d3d8205b_6443ebc0_9918ebee_6764f668_9f2b2be3\
+ b59cbc76_d76d0dfc_d737c3ec_0ccf9c00_ad0554bf_17e776ad\
+ b4edf9cc_6ce540be_76229093_5c53893b";
+
+static BIG_E: &'static str = "\
+ be0e6ea6_08746133_e0fbc1bf_82dba91e_e2b56231_a81888d2\
+ a833a1fc_f7ff002a_3c486a13_4f420bf3_a5435be9_1a5c8391\
+ 774d6e6c_085d8357_b0c97d4d_2bb33f7c_34c68059_f78d2541\
+ eacc8832_426f1816_d3be001e_b69f9242_51c7708e_e10efe98\
+ 449c9a4a_b55a0f23_9d797410_515da00d_3ea07970_4478a2ca\
+ c3d5043c_bd9be1b4_6dce479d_4302d344_84a939e6_0ab5ada7\
+ 12ae34b2_30cc473c_9f8ee69d_2cac5970_29f5bf18_bc8203e4\
+ f3e895a2_13c94f1e_24c73d77_e517e801_53661fdd_a2ce9e47\
+ a73dd7f8_2f2adb1e_3f136bf7_8ae5f3b8_08730de1_a4eff678\
+ e77a06d0_19a522eb_cbefba2a_9caf7736_b157c5c6_2d192591\
+ 17946850_2ddb1822_117b68a0_32f7db88";
+
+// This modulus is the prime from the 2048-bit MODP DH group:
+// https://tools.ietf.org/html/rfc3526#section-3
+static BIG_M: &'static str = "\
+ FFFFFFFF_FFFFFFFF_C90FDAA2_2168C234_C4C6628B_80DC1CD1\
+ 29024E08_8A67CC74_020BBEA6_3B139B22_514A0879_8E3404DD\
+ EF9519B3_CD3A431B_302B0A6D_F25F1437_4FE1356D_6D51C245\
+ E485B576_625E7EC6_F44C42E9_A637ED6B_0BFF5CB6_F406B7ED\
+ EE386BFB_5A899FA5_AE9F2411_7C4B1FE6_49286651_ECE45B3D\
+ C2007CB8_A163BF05_98DA4836_1C55D39A_69163FA8_FD24CF5F\
+ 83655D23_DCA3AD96_1C62F356_208552BB_9ED52907_7096966D\
+ 670C354E_4ABC9804_F1746C08_CA18217C_32905E46_2E36CE3B\
+ E39E772C_180E8603_9B2783A2_EC07A28F_B5C55DF0_6F4C52C9\
+ DE2BCBF6_95581718_3995497C_EA956AE5_15D22618_98FA0510\
+ 15728E5A_8AACAA68_FFFFFFFF_FFFFFFFF";
+
+static BIG_R: &'static str = "\
+ a1468311_6e56edc9_7a98228b_5e924776_0dd7836e_caabac13\
+ eda5373b_4752aa65_a1454850_40dc770e_30aa8675_6be7d3a8\
+ 9d3085e4_da5155cf_b451ef62_54d0da61_cf2b2c87_f495e096\
+ 055309f7_77802bbb_37271ba8_1313f1b5_075c75d1_024b6c77\
+ fdb56f17_b05bce61_e527ebfd_2ee86860_e9907066_edd526e7\
+ 93d289bf_6726b293_41b0de24_eff82424_8dfd374b_4ec59542\
+ 35ced2b2_6b195c90_10042ffb_8f58ce21_bc10ec42_64fda779\
+ d352d234_3d4eaea6_a86111ad_a37e9555_43ca78ce_2885bed7\
+ 5a30d182_f1cf6834_dc5b6e27_1a41ac34_a2e91e11_33363ff0\
+ f88a7b04_900227c9_f6e6d06b_7856b4bb_4e354d61_060db6c8\
+ 109c4735_6e7db425_7b5d74c7_0b709508";
+
+mod biguint {
+ use num_bigint::BigUint;
+ use num_integer::Integer;
+ use num_traits::Num;
+
+ fn check_modpow<T: Into<BigUint>>(b: T, e: T, m: T, r: T) {
+ let b: BigUint = b.into();
+ let e: BigUint = e.into();
+ let m: BigUint = m.into();
+ let r: BigUint = r.into();
+
+ assert_eq!(b.modpow(&e, &m), r);
+
+ let even_m = &m << 1;
+ let even_modpow = b.modpow(&e, &even_m);
+ assert!(even_modpow < even_m);
+ assert_eq!(even_modpow.mod_floor(&m), r);
+ }
+
+ #[test]
+ fn test_modpow() {
+ check_modpow::<u32>(1, 0, 11, 1);
+ check_modpow::<u32>(0, 15, 11, 0);
+ check_modpow::<u32>(3, 7, 11, 9);
+ check_modpow::<u32>(5, 117, 19, 1);
+ }
+
+ #[test]
+ fn test_modpow_big() {
+ let b = BigUint::from_str_radix(super::BIG_B, 16).unwrap();
+ let e = BigUint::from_str_radix(super::BIG_E, 16).unwrap();
+ let m = BigUint::from_str_radix(super::BIG_M, 16).unwrap();
+ let r = BigUint::from_str_radix(super::BIG_R, 16).unwrap();
+
+ assert_eq!(b.modpow(&e, &m), r);
+
+ let even_m = &m << 1;
+ let even_modpow = b.modpow(&e, &even_m);
+ assert!(even_modpow < even_m);
+ assert_eq!(even_modpow % m, r);
+ }
+}
+
+mod bigint {
+ use num_bigint::BigInt;
+ use num_integer::Integer;
+ use num_traits::{Num, One, Signed, Zero};
+
+ fn check_modpow<T: Into<BigInt>>(b: T, e: T, m: T, r: T) {
+ fn check(b: &BigInt, e: &BigInt, m: &BigInt, r: &BigInt) {
+ assert_eq!(&b.modpow(e, m), r);
+
+ let even_m = m << 1;
+ let even_modpow = b.modpow(e, m);
+ assert!(even_modpow.abs() < even_m.abs());
+ assert_eq!(&even_modpow.mod_floor(&m), r);
+
+ // the sign of the result follows the modulus like `mod_floor`, not `rem`
+ assert_eq!(b.modpow(&BigInt::one(), m), b.mod_floor(m));
+ }
+
+ let b: BigInt = b.into();
+ let e: BigInt = e.into();
+ let m: BigInt = m.into();
+ let r: BigInt = r.into();
+
+ let neg_r = if r.is_zero() { BigInt::zero() } else { &m - &r };
+
+ check(&b, &e, &m, &r);
+ check(&-&b, &e, &m, &neg_r);
+ check(&b, &e, &-&m, &-neg_r);
+ check(&-b, &e, &-m, &-r);
+ }
+
+ #[test]
+ fn test_modpow() {
+ check_modpow(1, 0, 11, 1);
+ check_modpow(0, 15, 11, 0);
+ check_modpow(3, 7, 11, 9);
+ check_modpow(5, 117, 19, 1);
+ }
+
+ #[test]
+ fn test_modpow_big() {
+ let b = BigInt::from_str_radix(super::BIG_B, 16).unwrap();
+ let e = BigInt::from_str_radix(super::BIG_E, 16).unwrap();
+ let m = BigInt::from_str_radix(super::BIG_M, 16).unwrap();
+ let r = BigInt::from_str_radix(super::BIG_R, 16).unwrap();
+
+ check_modpow(b, e, m, r);
+ }
+}
diff --git a/third_party/rust/num-bigint/tests/quickcheck.rs b/third_party/rust/num-bigint/tests/quickcheck.rs
new file mode 100644
index 0000000000..6bb251fa90
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/quickcheck.rs
@@ -0,0 +1,317 @@
+#![cfg(feature = "quickcheck")]
+#![cfg(feature = "quickcheck_macros")]
+
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+
+extern crate quickcheck;
+#[macro_use]
+extern crate quickcheck_macros;
+
+use num_bigint::{BigInt, BigUint};
+use num_traits::{Num, One, Pow, Zero};
+use quickcheck::{QuickCheck, StdThreadGen, TestResult};
+
+#[quickcheck]
+fn quickcheck_unsigned_eq_reflexive(a: BigUint) -> bool {
+ a == a
+}
+
+#[quickcheck]
+fn quickcheck_signed_eq_reflexive(a: BigInt) -> bool {
+ a == a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_eq_symmetric(a: BigUint, b: BigUint) -> bool {
+ if a == b {
+ b == a
+ } else {
+ b != a
+ }
+}
+
+#[quickcheck]
+fn quickcheck_signed_eq_symmetric(a: BigInt, b: BigInt) -> bool {
+ if a == b {
+ b == a
+ } else {
+ b != a
+ }
+}
+
+#[test]
+fn quickcheck_arith_primitive() {
+ let gen = StdThreadGen::new(usize::max_value());
+ let mut qc = QuickCheck::with_gen(gen);
+
+ fn test_unsigned_add_primitive(a: usize, b: usize) -> TestResult {
+ let actual = BigUint::from(a) + BigUint::from(b);
+ match a.checked_add(b) {
+ None => TestResult::discard(),
+ Some(expected) => TestResult::from_bool(BigUint::from(expected) == actual),
+ }
+ }
+
+ fn test_signed_add_primitive(a: isize, b: isize) -> TestResult {
+ let actual = BigInt::from(a) + BigInt::from(b);
+ match a.checked_add(b) {
+ None => TestResult::discard(),
+ Some(expected) => TestResult::from_bool(BigInt::from(expected) == actual),
+ }
+ }
+
+ fn test_unsigned_mul_primitive(a: u64, b: u64) -> bool {
+ //maximum value of u64 means no overflow
+ BigUint::from(a as u128 * b as u128) == BigUint::from(a) * BigUint::from(b)
+ }
+
+ fn test_signed_mul_primitive(a: i64, b: i64) -> bool {
+ //maximum value of i64 means no overflow
+ BigInt::from(a as i128 * b as i128) == BigInt::from(a) * BigInt::from(b)
+ }
+
+ fn test_unsigned_sub_primitive(a: u128, b: u128) -> bool {
+ if b < a {
+ BigUint::from(a - b) == BigUint::from(a) - BigUint::from(b)
+ } else {
+ BigUint::from(b - a) == BigUint::from(b) - BigUint::from(a)
+ }
+ }
+
+ fn test_signed_sub_primitive(a: i128, b: i128) -> bool {
+ if b < a {
+ BigInt::from(a - b) == BigInt::from(a) - BigInt::from(b)
+ } else {
+ BigInt::from(b - a) == BigInt::from(b) - BigInt::from(a)
+ }
+ }
+
+ fn test_unsigned_div_primitive(a: u128, b: u128) -> TestResult {
+ if b == 0 {
+ TestResult::discard()
+ } else {
+ TestResult::from_bool(BigUint::from(a / b) == BigUint::from(a) / BigUint::from(b))
+ }
+ }
+
+ fn test_signed_div_primitive(a: i128, b: i128) -> TestResult {
+ if b == 0 {
+ TestResult::discard()
+ } else {
+ TestResult::from_bool(BigInt::from(a / b) == BigInt::from(a) / BigInt::from(b))
+ }
+ }
+
+ qc.quickcheck(test_unsigned_add_primitive as fn(usize, usize) -> TestResult);
+ qc.quickcheck(test_signed_add_primitive as fn(isize, isize) -> TestResult);
+ qc.quickcheck(test_unsigned_mul_primitive as fn(u64, u64) -> bool);
+ qc.quickcheck(test_signed_mul_primitive as fn(i64, i64) -> bool);
+ qc.quickcheck(test_unsigned_sub_primitive as fn(u128, u128) -> bool);
+ qc.quickcheck(test_signed_sub_primitive as fn(i128, i128) -> bool);
+ qc.quickcheck(test_unsigned_div_primitive as fn(u128, u128) -> TestResult);
+ qc.quickcheck(test_signed_div_primitive as fn(i128, i128) -> TestResult);
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_add_commutative(a: BigUint, b: BigUint) -> bool {
+ &a + &b == b + a
+}
+
+#[quickcheck]
+fn quickcheck_signed_add_commutative(a: BigInt, b: BigInt) -> bool {
+ &a + &b == b + a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_add_zero(a: BigUint) -> bool {
+ a == &a + BigUint::zero()
+}
+
+#[quickcheck]
+fn quickcheck_signed_add_zero(a: BigInt) -> bool {
+ a == &a + BigInt::zero()
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_add_associative(a: BigUint, b: BigUint, c: BigUint) -> bool {
+ (&a + &b) + &c == a + (b + c)
+}
+
+#[quickcheck]
+fn quickcheck_signed_add_associative(a: BigInt, b: BigInt, c: BigInt) -> bool {
+ (&a + &b) + &c == a + (b + c)
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_mul_zero(a: BigUint) -> bool {
+ a * BigUint::zero() == BigUint::zero()
+}
+
+#[quickcheck]
+fn quickcheck_signed_mul_zero(a: BigInt) -> bool {
+ a * BigInt::zero() == BigInt::zero()
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_mul_one(a: BigUint) -> bool {
+ &a * BigUint::one() == a
+}
+
+#[quickcheck]
+fn quickcheck_signed_mul_one(a: BigInt) -> bool {
+ &a * BigInt::one() == a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_mul_commutative(a: BigUint, b: BigUint) -> bool {
+ &a * &b == b * a
+}
+
+#[quickcheck]
+fn quickcheck_signed_mul_commutative(a: BigInt, b: BigInt) -> bool {
+ &a * &b == b * a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_mul_associative(a: BigUint, b: BigUint, c: BigUint) -> bool {
+ (&a * &b) * &c == a * (b * c)
+}
+
+#[quickcheck]
+fn quickcheck_signed_mul_associative(a: BigInt, b: BigInt, c: BigInt) -> bool {
+ (&a * &b) * &c == a * (b * c)
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_distributive(a: BigUint, b: BigUint, c: BigUint) -> bool {
+ &a * (&b + &c) == &a * b + a * c
+}
+
+#[quickcheck]
+fn quickcheck_signed_distributive(a: BigInt, b: BigInt, c: BigInt) -> bool {
+ &a * (&b + &c) == &a * b + a * c
+}
+
+#[quickcheck]
+///Tests that exactly one of a<b a>b a=b is true
+fn quickcheck_unsigned_ge_le_eq_mut_exclusive(a: BigUint, b: BigUint) -> bool {
+ let gt_lt_eq = vec![a > b, a < b, a == b];
+ gt_lt_eq
+ .iter()
+ .fold(0, |acc, e| if *e { acc + 1 } else { acc })
+ == 1
+}
+
+#[quickcheck]
+///Tests that exactly one of a<b a>b a=b is true
+fn quickcheck_signed_ge_le_eq_mut_exclusive(a: BigInt, b: BigInt) -> bool {
+ let gt_lt_eq = vec![a > b, a < b, a == b];
+ gt_lt_eq
+ .iter()
+ .fold(0, |acc, e| if *e { acc + 1 } else { acc })
+ == 1
+}
+
+#[quickcheck]
+/// Tests correctness of subtraction assuming addition is correct
+fn quickcheck_unsigned_sub(a: BigUint, b: BigUint) -> bool {
+ if b < a {
+ &a - &b + b == a
+ } else {
+ &b - &a + a == b
+ }
+}
+
+#[quickcheck]
+/// Tests correctness of subtraction assuming addition is correct
+fn quickcheck_signed_sub(a: BigInt, b: BigInt) -> bool {
+ if b < a {
+ &a - &b + b == a
+ } else {
+ &b - &a + a == b
+ }
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_pow_zero(a: BigUint) -> bool {
+ a.pow(0_u32) == BigUint::one()
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_pow_one(a: BigUint) -> bool {
+ a.pow(1_u32) == a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_sqrt(a: BigUint) -> bool {
+ (&a * &a).sqrt() == a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_cbrt(a: BigUint) -> bool {
+ (&a * &a * &a).cbrt() == a
+}
+
+#[quickcheck]
+fn quickcheck_signed_cbrt(a: BigInt) -> bool {
+ (&a * &a * &a).cbrt() == a
+}
+
+#[quickcheck]
+fn quickcheck_unsigned_conversion(a: BigUint, radix: u8) -> TestResult {
+ let radix = radix as u32;
+ if radix > 36 || radix < 2 {
+ return TestResult::discard();
+ }
+ let string = a.to_str_radix(radix);
+ TestResult::from_bool(a == BigUint::from_str_radix(&string, radix).unwrap())
+}
+
+#[quickcheck]
+fn quickcheck_signed_conversion(a: BigInt, radix: u8) -> TestResult {
+ let radix = radix as u32;
+ if radix > 36 || radix < 2 {
+ return TestResult::discard();
+ }
+ let string = a.to_str_radix(radix);
+ TestResult::from_bool(a == BigInt::from_str_radix(&string, radix).unwrap())
+}
+
+#[test]
+fn quicktest_shift() {
+ let gen = StdThreadGen::new(usize::max_value());
+ let mut qc = QuickCheck::with_gen(gen);
+
+ fn test_shr_unsigned(a: u64, shift: u8) -> TestResult {
+ let shift = (shift % 64) as usize; //shift at most 64 bits
+ let big_a = BigUint::from(a);
+ TestResult::from_bool(BigUint::from(a >> shift) == big_a >> shift)
+ }
+
+ fn test_shr_signed(a: i64, shift: u8) -> TestResult {
+ let shift = (shift % 64) as usize; //shift at most 64 bits
+ let big_a = BigInt::from(a);
+ TestResult::from_bool(BigInt::from(a >> shift) == big_a >> shift)
+ }
+
+ fn test_shl_unsigned(a: u32, shift: u8) -> TestResult {
+ let shift = (shift % 32) as usize; //shift at most 32 bits
+ let a = a as u64; //leave room for the shifted bits
+ let big_a = BigUint::from(a);
+ TestResult::from_bool(BigUint::from(a >> shift) == big_a >> shift)
+ }
+
+ fn test_shl_signed(a: i32, shift: u8) -> TestResult {
+ let shift = (shift % 32) as usize;
+ let a = a as u64; //leave room for the shifted bits
+ let big_a = BigInt::from(a);
+ TestResult::from_bool(BigInt::from(a >> shift) == big_a >> shift)
+ }
+
+ qc.quickcheck(test_shr_unsigned as fn(u64, u8) -> TestResult);
+ qc.quickcheck(test_shr_signed as fn(i64, u8) -> TestResult);
+ qc.quickcheck(test_shl_unsigned as fn(u32, u8) -> TestResult);
+ qc.quickcheck(test_shl_signed as fn(i32, u8) -> TestResult);
+}
diff --git a/third_party/rust/num-bigint/tests/rand.rs b/third_party/rust/num-bigint/tests/rand.rs
new file mode 100644
index 0000000000..666b764d79
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/rand.rs
@@ -0,0 +1,324 @@
+#![cfg(feature = "rand")]
+
+extern crate num_bigint;
+extern crate num_traits;
+extern crate rand;
+
+mod biguint {
+ use num_bigint::{BigUint, RandBigInt, RandomBits};
+ use num_traits::Zero;
+ use rand::distributions::Uniform;
+ use rand::thread_rng;
+ use rand::{Rng, SeedableRng};
+
+ #[test]
+ fn test_rand() {
+ let mut rng = thread_rng();
+ let n: BigUint = rng.gen_biguint(137);
+ assert!(n.bits() <= 137);
+ assert!(rng.gen_biguint(0).is_zero());
+ }
+
+ #[test]
+ fn test_rand_bits() {
+ let mut rng = thread_rng();
+ let n: BigUint = rng.sample(&RandomBits::new(137));
+ assert!(n.bits() <= 137);
+ let z: BigUint = rng.sample(&RandomBits::new(0));
+ assert!(z.is_zero());
+ }
+
+ #[test]
+ fn test_rand_range() {
+ let mut rng = thread_rng();
+
+ for _ in 0..10 {
+ assert_eq!(
+ rng.gen_biguint_range(&BigUint::from(236u32), &BigUint::from(237u32)),
+ BigUint::from(236u32)
+ );
+ }
+
+ let l = BigUint::from(403469000u32 + 2352);
+ let u = BigUint::from(403469000u32 + 3513);
+ for _ in 0..1000 {
+ let n: BigUint = rng.gen_biguint_below(&u);
+ assert!(n < u);
+
+ let n: BigUint = rng.gen_biguint_range(&l, &u);
+ assert!(n >= l);
+ assert!(n < u);
+ }
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_zero_rand_range() {
+ thread_rng().gen_biguint_range(&BigUint::from(54u32), &BigUint::from(54u32));
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_negative_rand_range() {
+ let mut rng = thread_rng();
+ let l = BigUint::from(2352u32);
+ let u = BigUint::from(3513u32);
+ // Switching u and l should fail:
+ let _n: BigUint = rng.gen_biguint_range(&u, &l);
+ }
+
+ #[test]
+ fn test_rand_uniform() {
+ let mut rng = thread_rng();
+
+ let tiny = Uniform::new(BigUint::from(236u32), BigUint::from(237u32));
+ for _ in 0..10 {
+ assert_eq!(rng.sample(&tiny), BigUint::from(236u32));
+ }
+
+ let l = BigUint::from(403469000u32 + 2352);
+ let u = BigUint::from(403469000u32 + 3513);
+ let below = Uniform::new(BigUint::zero(), u.clone());
+ let range = Uniform::new(l.clone(), u.clone());
+ for _ in 0..1000 {
+ let n: BigUint = rng.sample(&below);
+ assert!(n < u);
+
+ let n: BigUint = rng.sample(&range);
+ assert!(n >= l);
+ assert!(n < u);
+ }
+ }
+
+ fn seeded_value_stability<R: SeedableRng + RandBigInt>(expected: &[&str]) {
+ let mut seed = <R::Seed>::default();
+ for (i, x) in seed.as_mut().iter_mut().enumerate() {
+ *x = (i as u8).wrapping_mul(191);
+ }
+ let mut rng = R::from_seed(seed);
+ for (i, &s) in expected.iter().enumerate() {
+ let n: BigUint = s.parse().unwrap();
+ let r = rng.gen_biguint((1 << i) + i);
+ assert_eq!(n, r);
+ }
+ }
+
+ #[test]
+ fn test_chacha_value_stability() {
+ const EXPECTED: &[&str] = &[
+ "0",
+ "0",
+ "52",
+ "84",
+ "23780",
+ "86502865016",
+ "187057847319509867386",
+ "34045731223080904464438757488196244981910",
+ "23813754422987836414755953516143692594193066497413249270287126597896871975915808",
+ "57401636903146945411652549098818446911814352529449356393690984105383482703074355\
+ 67088360974672291353736011718191813678720755501317478656550386324355699624671",
+ ];
+ use rand::prng::ChaChaRng;
+ seeded_value_stability::<ChaChaRng>(EXPECTED);
+ }
+
+ #[test]
+ fn test_isaac_value_stability() {
+ const EXPECTED: &[&str] = &[
+ "1",
+ "4",
+ "3",
+ "649",
+ "89116",
+ "7730042024",
+ "20773149082453254949",
+ "35999009049239918667571895439206839620281",
+ "10191757312714088681302309313551624007714035309632506837271600807524767413673006",
+ "37805949268912387809989378008822038725134260145886913321084097194957861133272558\
+ 43458183365174899239251448892645546322463253898288141861183340823194379722556",
+ ];
+ use rand::prng::IsaacRng;
+ seeded_value_stability::<IsaacRng>(EXPECTED);
+ }
+
+ #[test]
+ fn test_xorshift_value_stability() {
+ const EXPECTED: &[&str] = &[
+ "1",
+ "0",
+ "37",
+ "395",
+ "181116",
+ "122718231117",
+ "1068467172329355695001",
+ "28246925743544411614293300167064395633287",
+ "12750053187017853048648861493745244146555950255549630854523304068318587267293038",
+ "53041498719137109355568081064978196049094604705283682101683207799515709404788873\
+ 53417136457745727045473194367732849819278740266658219147356315674940229288531",
+ ];
+ use rand::prng::XorShiftRng;
+ seeded_value_stability::<XorShiftRng>(EXPECTED);
+ }
+}
+
+mod bigint {
+ use num_bigint::{BigInt, RandBigInt, RandomBits};
+ use num_traits::Zero;
+ use rand::distributions::Uniform;
+ use rand::thread_rng;
+ use rand::{Rng, SeedableRng};
+
+ #[test]
+ fn test_rand() {
+ let mut rng = thread_rng();
+ let n: BigInt = rng.gen_bigint(137);
+ assert!(n.bits() <= 137);
+ assert!(rng.gen_bigint(0).is_zero());
+ }
+
+ #[test]
+ fn test_rand_bits() {
+ let mut rng = thread_rng();
+ let n: BigInt = rng.sample(&RandomBits::new(137));
+ assert!(n.bits() <= 137);
+ let z: BigInt = rng.sample(&RandomBits::new(0));
+ assert!(z.is_zero());
+ }
+
+ #[test]
+ fn test_rand_range() {
+ let mut rng = thread_rng();
+
+ for _ in 0..10 {
+ assert_eq!(
+ rng.gen_bigint_range(&BigInt::from(236), &BigInt::from(237)),
+ BigInt::from(236)
+ );
+ }
+
+ fn check(l: BigInt, u: BigInt) {
+ let mut rng = thread_rng();
+ for _ in 0..1000 {
+ let n: BigInt = rng.gen_bigint_range(&l, &u);
+ assert!(n >= l);
+ assert!(n < u);
+ }
+ }
+ let l: BigInt = BigInt::from(403469000 + 2352);
+ let u: BigInt = BigInt::from(403469000 + 3513);
+ check(l.clone(), u.clone());
+ check(-l.clone(), u.clone());
+ check(-u.clone(), -l.clone());
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_zero_rand_range() {
+ thread_rng().gen_bigint_range(&BigInt::from(54), &BigInt::from(54));
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_negative_rand_range() {
+ let mut rng = thread_rng();
+ let l = BigInt::from(2352);
+ let u = BigInt::from(3513);
+ // Switching u and l should fail:
+ let _n: BigInt = rng.gen_bigint_range(&u, &l);
+ }
+
+ #[test]
+ fn test_rand_uniform() {
+ let mut rng = thread_rng();
+
+ let tiny = Uniform::new(BigInt::from(236u32), BigInt::from(237u32));
+ for _ in 0..10 {
+ assert_eq!(rng.sample(&tiny), BigInt::from(236u32));
+ }
+
+ fn check(l: BigInt, u: BigInt) {
+ let mut rng = thread_rng();
+ let range = Uniform::new(l.clone(), u.clone());
+ for _ in 0..1000 {
+ let n: BigInt = rng.sample(&range);
+ assert!(n >= l);
+ assert!(n < u);
+ }
+ }
+ let l: BigInt = BigInt::from(403469000 + 2352);
+ let u: BigInt = BigInt::from(403469000 + 3513);
+ check(l.clone(), u.clone());
+ check(-l.clone(), u.clone());
+ check(-u.clone(), -l.clone());
+ }
+
+ fn seeded_value_stability<R: SeedableRng + RandBigInt>(expected: &[&str]) {
+ let mut seed = <R::Seed>::default();
+ for (i, x) in seed.as_mut().iter_mut().enumerate() {
+ *x = (i as u8).wrapping_mul(191);
+ }
+ let mut rng = R::from_seed(seed);
+ for (i, &s) in expected.iter().enumerate() {
+ let n: BigInt = s.parse().unwrap();
+ let r = rng.gen_bigint((1 << i) + i);
+ assert_eq!(n, r);
+ }
+ }
+
+ #[test]
+ fn test_chacha_value_stability() {
+ const EXPECTED: &[&str] = &[
+ "0",
+ "-6",
+ "-1",
+ "1321",
+ "-147247",
+ "8486373526",
+ "-272736656290199720696",
+ "2731152629387534140535423510744221288522",
+ "-28820024790651190394679732038637785320661450462089347915910979466834461433196572",
+ "501454570554170484799723603981439288209930393334472085317977614690773821680884844\
+ 8530978478667288338327570972869032358120588620346111979053742269317702532328",
+ ];
+ use rand::prng::ChaChaRng;
+ seeded_value_stability::<ChaChaRng>(EXPECTED);
+ }
+
+ #[test]
+ fn test_isaac_value_stability() {
+ const EXPECTED: &[&str] = &[
+ "1",
+ "0",
+ "5",
+ "113",
+ "-132240",
+ "-36348760761",
+ "-365690596708430705434",
+ "-14090753008246284277803606722552430292432",
+ "-26313941628626248579319341019368550803676255307056857978955881718727601479436059",
+ "-14563174552421101848999036239003801073335703811160945137332228646111920972691151\
+ 88341090358094331641182310792892459091016794928947242043358702692294695845817",
+ ];
+ use rand::prng::IsaacRng;
+ seeded_value_stability::<IsaacRng>(EXPECTED);
+ }
+
+ #[test]
+ fn test_xorshift_value_stability() {
+ const EXPECTED: &[&str] = &[
+ "-1",
+ "-4",
+ "11",
+ "-1802",
+ "966495",
+ "-62592045703",
+ "-602281783447192077116",
+ "-34335811410223060575607987996861632509125",
+ "29156580925282215857325937227200350542000244609280383263289720243118706105351199",
+ "49920038676141573457451407325930326489996232208489690499754573826911037849083623\
+ 24546142615325187412887314466195222441945661833644117700809693098722026764846",
+ ];
+ use rand::prng::XorShiftRng;
+ seeded_value_stability::<XorShiftRng>(EXPECTED);
+ }
+}
diff --git a/third_party/rust/num-bigint/tests/roots.rs b/third_party/rust/num-bigint/tests/roots.rs
new file mode 100644
index 0000000000..39201fa928
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/roots.rs
@@ -0,0 +1,186 @@
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+
+#[cfg(feature = "rand")]
+extern crate rand;
+
+mod biguint {
+ use num_bigint::BigUint;
+ use num_traits::{One, Pow, Zero};
+ use std::{i32, u32};
+
+ fn check<T: Into<BigUint>>(x: T, n: u32) {
+ let x: BigUint = x.into();
+ let root = x.nth_root(n);
+ println!("check {}.nth_root({}) = {}", x, n, root);
+
+ if n == 2 {
+ assert_eq!(root, x.sqrt())
+ } else if n == 3 {
+ assert_eq!(root, x.cbrt())
+ }
+
+ let lo = root.pow(n);
+ assert!(lo <= x);
+ assert_eq!(lo.nth_root(n), root);
+ if !lo.is_zero() {
+ assert_eq!((&lo - 1u32).nth_root(n), &root - 1u32);
+ }
+
+ let hi = (&root + 1u32).pow(n);
+ assert!(hi > x);
+ assert_eq!(hi.nth_root(n), &root + 1u32);
+ assert_eq!((&hi - 1u32).nth_root(n), root);
+ }
+
+ #[test]
+ fn test_sqrt() {
+ check(99u32, 2);
+ check(100u32, 2);
+ check(120u32, 2);
+ }
+
+ #[test]
+ fn test_cbrt() {
+ check(8u32, 3);
+ check(26u32, 3);
+ }
+
+ #[test]
+ fn test_nth_root() {
+ check(0u32, 1);
+ check(10u32, 1);
+ check(100u32, 4);
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_nth_root_n_is_zero() {
+ check(4u32, 0);
+ }
+
+ #[test]
+ fn test_nth_root_big() {
+ let x = BigUint::from(123_456_789_u32);
+ let expected = BigUint::from(6u32);
+
+ assert_eq!(x.nth_root(10), expected);
+ check(x, 10);
+ }
+
+ #[test]
+ fn test_nth_root_googol() {
+ let googol = BigUint::from(10u32).pow(100u32);
+
+ // perfect divisors of 100
+ for &n in &[2, 4, 5, 10, 20, 25, 50, 100] {
+ let expected = BigUint::from(10u32).pow(100u32 / n);
+ assert_eq!(googol.nth_root(n), expected);
+ check(googol.clone(), n);
+ }
+ }
+
+ #[test]
+ fn test_nth_root_twos() {
+ const EXP: u32 = 12;
+ const LOG2: usize = 1 << EXP;
+ let x = BigUint::one() << LOG2;
+
+ // the perfect divisors are just powers of two
+ for exp in 1..EXP + 1 {
+ let n = 2u32.pow(exp);
+ let expected = BigUint::one() << (LOG2 / n as usize);
+ assert_eq!(x.nth_root(n), expected);
+ check(x.clone(), n);
+ }
+
+ // degenerate cases should return quickly
+ assert!(x.nth_root(x.bits() as u32).is_one());
+ assert!(x.nth_root(i32::MAX as u32).is_one());
+ assert!(x.nth_root(u32::MAX).is_one());
+ }
+
+ #[cfg(feature = "rand")]
+ #[test]
+ fn test_roots_rand() {
+ use num_bigint::RandBigInt;
+ use rand::distributions::Uniform;
+ use rand::{thread_rng, Rng};
+
+ let mut rng = thread_rng();
+ let bit_range = Uniform::new(0, 2048);
+ let sample_bits: Vec<_> = rng.sample_iter(&bit_range).take(100).collect();
+ for bits in sample_bits {
+ let x = rng.gen_biguint(bits);
+ for n in 2..11 {
+ check(x.clone(), n);
+ }
+ check(x.clone(), 100);
+ }
+ }
+
+ #[test]
+ fn test_roots_rand1() {
+ // A random input that found regressions
+ let s = "575981506858479247661989091587544744717244516135539456183849\
+ 986593934723426343633698413178771587697273822147578889823552\
+ 182702908597782734558103025298880194023243541613924361007059\
+ 353344183590348785832467726433749431093350684849462759540710\
+ 026019022227591412417064179299354183441181373862905039254106\
+ 4781867";
+ let x: BigUint = s.parse().unwrap();
+
+ check(x.clone(), 2);
+ check(x.clone(), 3);
+ check(x.clone(), 10);
+ check(x.clone(), 100);
+ }
+}
+
+mod bigint {
+ use num_bigint::BigInt;
+ use num_traits::{Pow, Signed};
+
+ fn check(x: i64, n: u32) {
+ let big_x = BigInt::from(x);
+ let res = big_x.nth_root(n);
+
+ if n == 2 {
+ assert_eq!(&res, &big_x.sqrt())
+ } else if n == 3 {
+ assert_eq!(&res, &big_x.cbrt())
+ }
+
+ if big_x.is_negative() {
+ assert!(res.pow(n) >= big_x);
+ assert!((res - 1u32).pow(n) < big_x);
+ } else {
+ assert!(res.pow(n) <= big_x);
+ assert!((res + 1u32).pow(n) > big_x);
+ }
+ }
+
+ #[test]
+ fn test_nth_root() {
+ check(-100, 3);
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_nth_root_x_neg_n_even() {
+ check(-100, 4);
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_sqrt_x_neg() {
+ check(-4, 2);
+ }
+
+ #[test]
+ fn test_cbrt() {
+ check(8, 3);
+ check(-8, 3);
+ }
+}
diff --git a/third_party/rust/num-bigint/tests/serde.rs b/third_party/rust/num-bigint/tests/serde.rs
new file mode 100644
index 0000000000..0f3d4868ed
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/serde.rs
@@ -0,0 +1,103 @@
+//! Test serialization and deserialization of `BigUint` and `BigInt`
+//!
+//! The serialized formats should not change, even if we change our
+//! internal representation, because we want to preserve forward and
+//! backward compatibility of serialized data!
+
+#![cfg(feature = "serde")]
+
+extern crate num_bigint;
+extern crate num_traits;
+extern crate serde_test;
+
+use num_bigint::{BigInt, BigUint};
+use num_traits::{One, Zero};
+use serde_test::{assert_tokens, Token};
+
+#[test]
+fn biguint_zero() {
+ let tokens = [Token::Seq { len: Some(0) }, Token::SeqEnd];
+ assert_tokens(&BigUint::zero(), &tokens);
+}
+
+#[test]
+fn bigint_zero() {
+ let tokens = [
+ Token::Tuple { len: 2 },
+ Token::I8(0),
+ Token::Seq { len: Some(0) },
+ Token::SeqEnd,
+ Token::TupleEnd,
+ ];
+ assert_tokens(&BigInt::zero(), &tokens);
+}
+
+#[test]
+fn biguint_one() {
+ let tokens = [Token::Seq { len: Some(1) }, Token::U32(1), Token::SeqEnd];
+ assert_tokens(&BigUint::one(), &tokens);
+}
+
+#[test]
+fn bigint_one() {
+ let tokens = [
+ Token::Tuple { len: 2 },
+ Token::I8(1),
+ Token::Seq { len: Some(1) },
+ Token::U32(1),
+ Token::SeqEnd,
+ Token::TupleEnd,
+ ];
+ assert_tokens(&BigInt::one(), &tokens);
+}
+
+#[test]
+fn bigint_negone() {
+ let tokens = [
+ Token::Tuple { len: 2 },
+ Token::I8(-1),
+ Token::Seq { len: Some(1) },
+ Token::U32(1),
+ Token::SeqEnd,
+ Token::TupleEnd,
+ ];
+ assert_tokens(&-BigInt::one(), &tokens);
+}
+
+// Generated independently from python `hex(factorial(100))`
+const FACTORIAL_100: &'static [u32] = &[
+ 0x00000000, 0x00000000, 0x00000000, 0x2735c61a, 0xee8b02ea, 0xb3b72ed2, 0x9420c6ec, 0x45570cca,
+ 0xdf103917, 0x943a321c, 0xeb21b5b2, 0x66ef9a70, 0xa40d16e9, 0x28d54bbd, 0xdc240695, 0x964ec395,
+ 0x1b30,
+];
+
+#[test]
+fn biguint_factorial_100() {
+ let n: BigUint = (1u8..101).product();
+
+ let mut tokens = vec![];
+ tokens.push(Token::Seq {
+ len: Some(FACTORIAL_100.len()),
+ });
+ tokens.extend(FACTORIAL_100.iter().map(|&u| Token::U32(u)));
+ tokens.push(Token::SeqEnd);
+
+ assert_tokens(&n, &tokens);
+}
+
+#[test]
+fn bigint_factorial_100() {
+ let n: BigInt = (1i8..101).product();
+
+ let mut tokens = vec![];
+ tokens.push(Token::Tuple { len: 2 });
+ tokens.push(Token::I8(1));
+ tokens.push(Token::Seq {
+ len: Some(FACTORIAL_100.len()),
+ });
+ tokens.extend(FACTORIAL_100.iter().map(|&u| Token::U32(u)));
+ tokens.push(Token::SeqEnd);
+ tokens.push(Token::TupleEnd);
+
+ assert_tokens(&n, &tokens);
+}
diff --git a/third_party/rust/num-bigint/tests/torture.rs b/third_party/rust/num-bigint/tests/torture.rs
new file mode 100644
index 0000000000..4f073d31d9
--- /dev/null
+++ b/third_party/rust/num-bigint/tests/torture.rs
@@ -0,0 +1,43 @@
+#![cfg(feature = "rand")]
+
+extern crate num_bigint;
+extern crate num_traits;
+extern crate rand;
+
+use num_bigint::RandBigInt;
+use num_traits::Zero;
+use rand::prelude::*;
+
+fn test_mul_divide_torture_count(count: usize) {
+ let bits_max = 1 << 12;
+ let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
+ let mut rng = SmallRng::from_seed(seed);
+
+ for _ in 0..count {
+ // Test with numbers of random sizes:
+ let xbits = rng.gen_range(0, bits_max);
+ let ybits = rng.gen_range(0, bits_max);
+
+ let x = rng.gen_biguint(xbits);
+ let y = rng.gen_biguint(ybits);
+
+ if x.is_zero() || y.is_zero() {
+ continue;
+ }
+
+ let prod = &x * &y;
+ assert_eq!(&prod / &x, y);
+ assert_eq!(&prod / &y, x);
+ }
+}
+
+#[test]
+fn test_mul_divide_torture() {
+ test_mul_divide_torture_count(1000);
+}
+
+#[test]
+#[ignore]
+fn test_mul_divide_torture_long() {
+ test_mul_divide_torture_count(1000000);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-05 14:26:18 +0000