Adding upstream version 110.0.1.upstream/110.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 760 insertions, 0 deletions

diff --git a/third_party/rust/num-integer/benches/average.rs b/third_party/rust/num-integer/benches/average.rs
new file mode 100644
index 0000000000..649078c39d
--- /dev/null
+++ b/third_party/rust/num-integer/benches/average.rs
@@ -0,0 +1,414 @@
+//! Benchmark sqrt and cbrt
+
+#![feature(test)]
+
+extern crate num_integer;
+extern crate num_traits;
+extern crate test;
+
+use num_integer::Integer;
+use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
+use std::cmp::{max, min};
+use std::fmt::Debug;
+use test::{black_box, Bencher};
+
+// --- Utilities for RNG ----------------------------------------------------
+
+trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+// Simple PRNG so we don't have to worry about rand compatibility
+fn lcg<T>(x: T) -> T
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+{
+    // LCG parameters from Numerical Recipes
+    // (but we're applying it to arbitrary sizes)
+    const LCG_A: u32 = 1664525;
+    const LCG_C: u32 = 1013904223;
+    x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
+}
+
+// --- Alt. Implementations -------------------------------------------------
+
+trait NaiveAverage {
+    fn naive_average_ceil(&self, other: &Self) -> Self;
+    fn naive_average_floor(&self, other: &Self) -> Self;
+}
+
+trait UncheckedAverage {
+    fn unchecked_average_ceil(&self, other: &Self) -> Self;
+    fn unchecked_average_floor(&self, other: &Self) -> Self;
+}
+
+trait ModuloAverage {
+    fn modulo_average_ceil(&self, other: &Self) -> Self;
+    fn modulo_average_floor(&self, other: &Self) -> Self;
+}
+
+macro_rules! naive_average {
+    ($T:ident) => {
+        impl super::NaiveAverage for $T {
+            fn naive_average_floor(&self, other: &$T) -> $T {
+                match self.checked_add(*other) {
+                    Some(z) => Integer::div_floor(&z, &2),
+                    None => {
+                        if self > other {
+                            let diff = self - other;
+                            other + Integer::div_floor(&diff, &2)
+                        } else {
+                            let diff = other - self;
+                            self + Integer::div_floor(&diff, &2)
+                        }
+                    }
+                }
+            }
+            fn naive_average_ceil(&self, other: &$T) -> $T {
+                match self.checked_add(*other) {
+                    Some(z) => Integer::div_ceil(&z, &2),
+                    None => {
+                        if self > other {
+                            let diff = self - other;
+                            self - Integer::div_floor(&diff, &2)
+                        } else {
+                            let diff = other - self;
+                            other - Integer::div_floor(&diff, &2)
+                        }
+                    }
+                }
+            }
+        }
+    };
+}
+
+macro_rules! unchecked_average {
+    ($T:ident) => {
+        impl super::UncheckedAverage for $T {
+            fn unchecked_average_floor(&self, other: &$T) -> $T {
+                self.wrapping_add(*other) / 2
+            }
+            fn unchecked_average_ceil(&self, other: &$T) -> $T {
+                (self.wrapping_add(*other) / 2).wrapping_add(1)
+            }
+        }
+    };
+}
+
+macro_rules! modulo_average {
+    ($T:ident) => {
+        impl super::ModuloAverage for $T {
+            fn modulo_average_ceil(&self, other: &$T) -> $T {
+                let (q1, r1) = self.div_mod_floor(&2);
+                let (q2, r2) = other.div_mod_floor(&2);
+                q1 + q2 + (r1 | r2)
+            }
+            fn modulo_average_floor(&self, other: &$T) -> $T {
+                let (q1, r1) = self.div_mod_floor(&2);
+                let (q2, r2) = other.div_mod_floor(&2);
+                q1 + q2 + (r1 * r2)
+            }
+        }
+    };
+}
+
+// --- Bench functions ------------------------------------------------------
+
+fn bench_unchecked<T, F>(b: &mut Bencher, v: &[(T, T)], f: F)
+where
+    T: Integer + Debug + Copy,
+    F: Fn(&T, &T) -> T,
+{
+    b.iter(|| {
+        for (x, y) in v {
+            black_box(f(x, y));
+        }
+    });
+}
+
+fn bench_ceil<T, F>(b: &mut Bencher, v: &[(T, T)], f: F)
+where
+    T: Integer + Debug + Copy,
+    F: Fn(&T, &T) -> T,
+{
+    for &(i, j) in v {
+        let rt = f(&i, &j);
+        let (a, b) = (min(i, j), max(i, j));
+        // if both number are the same sign, check rt is in the middle
+        if (a < T::zero()) == (b < T::zero()) {
+            if (b - a).is_even() {
+                assert_eq!(rt - a, b - rt);
+            } else {
+                assert_eq!(rt - a, b - rt + T::one());
+            }
+        // if both number have a different sign,
+        } else {
+            if (a + b).is_even() {
+                assert_eq!(rt, (a + b) / (T::one() + T::one()))
+            } else {
+                assert_eq!(rt, (a + b + T::one()) / (T::one() + T::one()))
+            }
+        }
+    }
+    bench_unchecked(b, v, f);
+}
+
+fn bench_floor<T, F>(b: &mut Bencher, v: &[(T, T)], f: F)
+where
+    T: Integer + Debug + Copy,
+    F: Fn(&T, &T) -> T,
+{
+    for &(i, j) in v {
+        let rt = f(&i, &j);
+        let (a, b) = (min(i, j), max(i, j));
+        // if both number are the same sign, check rt is in the middle
+        if (a < T::zero()) == (b < T::zero()) {
+            if (b - a).is_even() {
+                assert_eq!(rt - a, b - rt);
+            } else {
+                assert_eq!(rt - a + T::one(), b - rt);
+            }
+        // if both number have a different sign,
+        } else {
+            if (a + b).is_even() {
+                assert_eq!(rt, (a + b) / (T::one() + T::one()))
+            } else {
+                assert_eq!(rt, (a + b - T::one()) / (T::one() + T::one()))
+            }
+        }
+    }
+    bench_unchecked(b, v, f);
+}
+
+// --- Bench implementation -------------------------------------------------
+
+macro_rules! bench_average {
+    ($($T:ident),*) => {$(
+        mod $T {
+            use test::Bencher;
+            use num_integer::{Average, Integer};
+            use super::{UncheckedAverage, NaiveAverage, ModuloAverage};
+            use super::{bench_ceil, bench_floor, bench_unchecked};
+
+            naive_average!($T);
+            unchecked_average!($T);
+            modulo_average!($T);
+
+            const SIZE: $T = 30;
+
+            fn overflowing() -> Vec<($T, $T)> {
+                (($T::max_value()-SIZE)..$T::max_value())
+                    .flat_map(|x| -> Vec<_> {
+                        (($T::max_value()-100)..($T::max_value()-100+SIZE))
+                            .map(|y| (x, y))
+                            .collect()
+                    })
+                    .collect()
+            }
+
+            fn small() -> Vec<($T, $T)> {
+                (0..SIZE)
+                   .flat_map(|x| -> Vec<_> {(0..SIZE).map(|y| (x, y)).collect()})
+                   .collect()
+            }
+
+            fn rand() -> Vec<($T, $T)> {
+                small()
+                    .into_iter()
+                    .map(|(x, y)| (super::lcg(x), super::lcg(y)))
+                    .collect()
+            }
+
+            mod ceil {
+
+                use super::*;
+
+                mod small {
+
+                    use super::*;
+
+                    #[bench]
+                    fn optimized(b: &mut Bencher) {
+                        let v = small();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn naive(b: &mut Bencher) {
+                        let v = small();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn unchecked(b: &mut Bencher) {
+                        let v = small();
+                        bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn modulo(b: &mut Bencher) {
+                        let v = small();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y));
+                    }
+                }
+
+                mod overflowing {
+
+                    use super::*;
+
+                    #[bench]
+                    fn optimized(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn naive(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn unchecked(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn modulo(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y));
+                    }
+                }
+
+                mod rand {
+
+                    use super::*;
+
+                    #[bench]
+                    fn optimized(b: &mut Bencher) {
+                        let v = rand();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn naive(b: &mut Bencher) {
+                        let v = rand();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn unchecked(b: &mut Bencher) {
+                        let v = rand();
+                        bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y));
+                    }
+
+                    #[bench]
+                    fn modulo(b: &mut Bencher) {
+                        let v = rand();
+                        bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y));
+                    }
+                }
+
+            }
+
+            mod floor {
+
+                use super::*;
+
+                mod small {
+
+                    use super::*;
+
+                    #[bench]
+                    fn optimized(b: &mut Bencher) {
+                        let v = small();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y));
+                    }
+
+                    #[bench]
+                    fn naive(b: &mut Bencher) {
+                        let v = small();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y));
+                    }
+
+                    #[bench]
+                    fn unchecked(b: &mut Bencher) {
+                        let v = small();
+                        bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y));
+                    }
+
+                    #[bench]
+                    fn modulo(b: &mut Bencher) {
+                        let v = small();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y));
+                    }
+                }
+
+                mod overflowing {
+
+                    use super::*;
+
+                    #[bench]
+                    fn optimized(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y));
+                    }
+
+                    #[bench]
+                    fn naive(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y));
+                    }
+
+                    #[bench]
+                    fn unchecked(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y));
+                    }
+
+                    #[bench]
+                    fn modulo(b: &mut Bencher) {
+                        let v = overflowing();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y));
+                    }
+                }
+
+                mod rand {
+
+                    use super::*;
+
+                    #[bench]
+                    fn optimized(b: &mut Bencher) {
+                        let v = rand();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y));
+                    }
+
+                    #[bench]
+                    fn naive(b: &mut Bencher) {
+                        let v = rand();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y));
+                    }
+
+                    #[bench]
+                    fn unchecked(b: &mut Bencher) {
+                        let v = rand();
+                        bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y));
+                    }
+
+                    #[bench]
+                    fn modulo(b: &mut Bencher) {
+                        let v = rand();
+                        bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y));
+                    }
+                }
+
+            }
+
+        }
+    )*}
+}
+
+bench_average!(i8, i16, i32, i64, i128, isize);
+bench_average!(u8, u16, u32, u64, u128, usize);
diff --git a/third_party/rust/num-integer/benches/gcd.rs b/third_party/rust/num-integer/benches/gcd.rs
new file mode 100644
index 0000000000..082d5ee09d
--- /dev/null
+++ b/third_party/rust/num-integer/benches/gcd.rs
@@ -0,0 +1,176 @@
+//! Benchmark comparing the current GCD implemtation against an older one.
+
+#![feature(test)]
+
+extern crate num_integer;
+extern crate num_traits;
+extern crate test;
+
+use num_integer::Integer;
+use num_traits::{AsPrimitive, Bounded, Signed};
+use test::{black_box, Bencher};
+
+trait GcdOld: Integer {
+    fn gcd_old(&self, other: &Self) -> Self;
+}
+
+macro_rules! impl_gcd_old_for_isize {
+    ($T:ty) => {
+        impl GcdOld for $T {
+            /// Calculates the Greatest Common Divisor (GCD) of the number and
+            /// `other`. The result is always positive.
+            #[inline]
+            fn gcd_old(&self, other: &Self) -> Self {
+                // Use Stein's algorithm
+                let mut m = *self;
+                let mut n = *other;
+                if m == 0 || n == 0 {
+                    return (m | n).abs();
+                }
+
+                // find common factors of 2
+                let shift = (m | n).trailing_zeros();
+
+                // The algorithm needs positive numbers, but the minimum value
+                // can't be represented as a positive one.
+                // It's also a power of two, so the gcd can be
+                // calculated by bitshifting in that case
+
+                // Assuming two's complement, the number created by the shift
+                // is positive for all numbers except gcd = abs(min value)
+                // The call to .abs() causes a panic in debug mode
+                if m == Self::min_value() || n == Self::min_value() {
+                    return (1 << shift).abs();
+                }
+
+                // guaranteed to be positive now, rest like unsigned algorithm
+                m = m.abs();
+                n = n.abs();
+
+                // divide n and m by 2 until odd
+                // m inside loop
+                n >>= n.trailing_zeros();
+
+                while m != 0 {
+                    m >>= m.trailing_zeros();
+                    if n > m {
+                        std::mem::swap(&mut n, &mut m)
+                    }
+                    m -= n;
+                }
+
+                n << shift
+            }
+        }
+    };
+}
+
+impl_gcd_old_for_isize!(i8);
+impl_gcd_old_for_isize!(i16);
+impl_gcd_old_for_isize!(i32);
+impl_gcd_old_for_isize!(i64);
+impl_gcd_old_for_isize!(isize);
+impl_gcd_old_for_isize!(i128);
+
+macro_rules! impl_gcd_old_for_usize {
+    ($T:ty) => {
+        impl GcdOld for $T {
+            /// Calculates the Greatest Common Divisor (GCD) of the number and
+            /// `other`. The result is always positive.
+            #[inline]
+            fn gcd_old(&self, other: &Self) -> Self {
+                // Use Stein's algorithm
+                let mut m = *self;
+                let mut n = *other;
+                if m == 0 || n == 0 {
+                    return m | n;
+                }
+
+                // find common factors of 2
+                let shift = (m | n).trailing_zeros();
+
+                // divide n and m by 2 until odd
+                // m inside loop
+                n >>= n.trailing_zeros();
+
+                while m != 0 {
+                    m >>= m.trailing_zeros();
+                    if n > m {
+                        std::mem::swap(&mut n, &mut m)
+                    }
+                    m -= n;
+                }
+
+                n << shift
+            }
+        }
+    };
+}
+
+impl_gcd_old_for_usize!(u8);
+impl_gcd_old_for_usize!(u16);
+impl_gcd_old_for_usize!(u32);
+impl_gcd_old_for_usize!(u64);
+impl_gcd_old_for_usize!(usize);
+impl_gcd_old_for_usize!(u128);
+
+/// Return an iterator that yields all Fibonacci numbers fitting into a u128.
+fn fibonacci() -> impl Iterator<Item = u128> {
+    (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| {
+        let tmp = *a;
+        *a = *b;
+        *b += tmp;
+        Some(*b)
+    })
+}
+
+fn run_bench<T: Integer + Bounded + Copy + 'static>(b: &mut Bencher, gcd: fn(&T, &T) -> T)
+where
+    T: AsPrimitive<u128>,
+    u128: AsPrimitive<T>,
+{
+    let max_value: u128 = T::max_value().as_();
+    let pairs: Vec<(T, T)> = fibonacci()
+        .collect::<Vec<_>>()
+        .windows(2)
+        .filter(|&pair| pair[0] <= max_value && pair[1] <= max_value)
+        .map(|pair| (pair[0].as_(), pair[1].as_()))
+        .collect();
+    b.iter(|| {
+        for &(ref m, ref n) in &pairs {
+            black_box(gcd(m, n));
+        }
+    });
+}
+
+macro_rules! bench_gcd {
+    ($T:ident) => {
+        mod $T {
+            use crate::{run_bench, GcdOld};
+            use num_integer::Integer;
+            use test::Bencher;
+
+            #[bench]
+            fn bench_gcd(b: &mut Bencher) {
+                run_bench(b, $T::gcd);
+            }
+
+            #[bench]
+            fn bench_gcd_old(b: &mut Bencher) {
+                run_bench(b, $T::gcd_old);
+            }
+        }
+    };
+}
+
+bench_gcd!(u8);
+bench_gcd!(u16);
+bench_gcd!(u32);
+bench_gcd!(u64);
+bench_gcd!(u128);
+
+bench_gcd!(i8);
+bench_gcd!(i16);
+bench_gcd!(i32);
+bench_gcd!(i64);
+bench_gcd!(i128);
diff --git a/third_party/rust/num-integer/benches/roots.rs b/third_party/rust/num-integer/benches/roots.rs
new file mode 100644
index 0000000000..7f672786a5
--- /dev/null
+++ b/third_party/rust/num-integer/benches/roots.rs
@@ -0,0 +1,170 @@
+//! Benchmark sqrt and cbrt
+
+#![feature(test)]
+
+extern crate num_integer;
+extern crate num_traits;
+extern crate test;
+
+use num_integer::Integer;
+use num_traits::checked_pow;
+use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
+use test::{black_box, Bencher};
+
+trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+fn bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32)
+where
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    // Pre-validate the results...
+    for i in v {
+        let rt = f(i);
+        if *i >= T::zero() {
+            let rt1 = rt + T::one();
+            assert!(rt.pow(n) <= *i);
+            if let Some(x) = checked_pow(rt1, n as usize) {
+                assert!(*i < x);
+            }
+        } else {
+            let rt1 = rt - T::one();
+            assert!(rt < T::zero());
+            assert!(*i <= rt.pow(n));
+            if let Some(x) = checked_pow(rt1, n as usize) {
+                assert!(x < *i);
+            }
+        };
+    }
+
+    // Now just run as fast as we can!
+    b.iter(|| {
+        for i in v {
+            black_box(f(i));
+        }
+    });
+}
+
+// Simple PRNG so we don't have to worry about rand compatibility
+fn lcg<T>(x: T) -> T
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+{
+    // LCG parameters from Numerical Recipes
+    // (but we're applying it to arbitrary sizes)
+    const LCG_A: u32 = 1664525;
+    const LCG_C: u32 = 1013904223;
+    x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
+}
+
+fn bench_rand<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let mut x: T = 3u32.as_();
+    let v: Vec<T> = (0..1000)
+        .map(|_| {
+            x = lcg(x);
+            x
+        })
+        .collect();
+    bench(b, &v, f, n);
+}
+
+fn bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let mut x: T = 3u32.as_();
+    let v: Vec<T> = (0..1000)
+        .map(|_| {
+            x = lcg(x);
+            while x < T::zero() {
+                x = lcg(x);
+            }
+            x
+        })
+        .collect();
+    bench(b, &v, f, n);
+}
+
+fn bench_small<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let v: Vec<T> = (0..1000).map(|i| i.as_()).collect();
+    bench(b, &v, f, n);
+}
+
+fn bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let v: Vec<T> = (0..1000)
+        .map(|i| i.as_().mod_floor(&T::max_value()))
+        .collect();
+    bench(b, &v, f, n);
+}
+
+macro_rules! bench_roots {
+    ($($T:ident),*) => {$(
+        mod $T {
+            use test::Bencher;
+            use num_integer::Roots;
+
+            #[bench]
+            fn sqrt_rand(b: &mut Bencher) {
+                ::bench_rand_pos(b, $T::sqrt, 2);
+            }
+
+            #[bench]
+            fn sqrt_small(b: &mut Bencher) {
+                ::bench_small_pos(b, $T::sqrt, 2);
+            }
+
+            #[bench]
+            fn cbrt_rand(b: &mut Bencher) {
+                ::bench_rand(b, $T::cbrt, 3);
+            }
+
+            #[bench]
+            fn cbrt_small(b: &mut Bencher) {
+                ::bench_small(b, $T::cbrt, 3);
+            }
+
+            #[bench]
+            fn fourth_root_rand(b: &mut Bencher) {
+                ::bench_rand_pos(b, |x: &$T| x.nth_root(4), 4);
+            }
+
+            #[bench]
+            fn fourth_root_small(b: &mut Bencher) {
+                ::bench_small_pos(b, |x: &$T| x.nth_root(4), 4);
+            }
+
+            #[bench]
+            fn fifth_root_rand(b: &mut Bencher) {
+                ::bench_rand(b, |x: &$T| x.nth_root(5), 5);
+            }
+
+            #[bench]
+            fn fifth_root_small(b: &mut Bencher) {
+                ::bench_small(b, |x: &$T| x.nth_root(5), 5);
+            }
+        }
+    )*}
+}
+
+bench_roots!(i8, i16, i32, i64, i128);
+bench_roots!(u8, u16, u32, u64, u128);