Merging upstream version 1.72.1+dfsg1.

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

1 files changed, 119 insertions, 86 deletions

diff --git a/vendor/crypto-bigint/benches/bench.rs b/vendor/crypto-bigint/benches/bench.rs
index e04778053..8be5f5928 100644
--- a/vendor/crypto-bigint/benches/bench.rs
+++ b/vendor/crypto-bigint/benches/bench.rs
@@ -1,115 +1,148 @@
 use criterion::{
-    criterion_group, criterion_main, measurement::Measurement, BenchmarkGroup, Criterion,
+    criterion_group, criterion_main, measurement::Measurement, BatchSize, BenchmarkGroup, Criterion,
 };
 use crypto_bigint::{
     modular::runtime_mod::{DynResidue, DynResidueParams},
-    NonZero, Random, Reciprocal, Uint, U256,
+    Limb, NonZero, Random, Reciprocal, U128, U256,
 };
 use rand_core::OsRng;
 
-fn bench_division<'a, M: Measurement>(group: &mut BenchmarkGroup<'a, M>) {
-    const TEST_SET: usize = 10;
-    let xs = (0..TEST_SET)
-        .map(|_| Uint::<4>::random(&mut OsRng))
-        .collect::<Vec<_>>();
-    let ys = (0..TEST_SET)
-        .map(|_| NonZero::new(Uint::<2>::ZERO.concat(&Uint::<2>::random(&mut OsRng))).unwrap())
-        .collect::<Vec<_>>();
-    group.bench_function("div/rem, 4/2, full size", |b| {
-        b.iter(|| {
-            xs.iter()
-                .zip(ys.iter())
-                .map(|(x, y)| x.div_rem(y))
-                .for_each(drop)
-        })
+fn bench_division<M: Measurement>(group: &mut BenchmarkGroup<'_, M>) {
+    group.bench_function("div/rem, U256/U128, full size", |b| {
+        b.iter_batched(
+            || {
+                let x = U256::random(&mut OsRng);
+                let y_half = U128::random(&mut OsRng);
+                let y: U256 = (y_half, U128::ZERO).into();
+                (x, NonZero::new(y).unwrap())
+            },
+            |(x, y)| x.div_rem(&y),
+            BatchSize::SmallInput,
+        )
     });
 
-    group.bench_function("rem, 4/2, full size", |b| {
-        b.iter(|| {
-            xs.iter()
-                .zip(ys.iter())
-                .map(|(x, y)| x.rem(y))
-                .for_each(drop)
-        })
+    group.bench_function("rem, U256/U128, full size", |b| {
+        b.iter_batched(
+            || {
+                let x = U256::random(&mut OsRng);
+                let y_half = U128::random(&mut OsRng);
+                let y: U256 = (y_half, U128::ZERO).into();
+                (x, NonZero::new(y).unwrap())
+            },
+            |(x, y)| x.rem(&y),
+            BatchSize::SmallInput,
+        )
     });
 
-    let ys = (0..TEST_SET)
-        .map(|_| Uint::<1>::random(&mut OsRng))
-        .collect::<Vec<_>>();
-    let ys_full = ys
-        .iter()
-        .map(|y| NonZero::new(Uint::<4>::from(y.as_limbs()[0])).unwrap())
-        .collect::<Vec<_>>();
-    let ys_limb = ys
-        .iter()
-        .map(|y| NonZero::new(y.as_limbs()[0]).unwrap())
-        .collect::<Vec<_>>();
-    group.bench_function("div/rem, 4/1, full size", |b| {
-        b.iter(|| {
-            xs.iter()
-                .zip(ys_full.iter())
-                .map(|(x, y)| x.div_rem(y))
-                .for_each(drop)
-        })
+    group.bench_function("div/rem, U256/Limb, full size", |b| {
+        b.iter_batched(
+            || {
+                let x = U256::random(&mut OsRng);
+                let y_small = Limb::random(&mut OsRng);
+                let y = U256::from_word(y_small.0);
+                (x, NonZero::new(y).unwrap())
+            },
+            |(x, y)| x.div_rem(&y),
+            BatchSize::SmallInput,
+        )
     });
-    group.bench_function("div/rem, 4/1, single limb", |b| {
-        b.iter(|| {
-            xs.iter()
-                .zip(ys_limb.iter())
-                .map(|(x, y)| x.div_rem_limb(*y))
-                .for_each(drop)
-        })
+
+    group.bench_function("div/rem, U256/Limb, single limb", |b| {
+        b.iter_batched(
+            || {
+                let x = U256::random(&mut OsRng);
+                let y = Limb::random(&mut OsRng);
+                (x, NonZero::new(y).unwrap())
+            },
+            |(x, y)| x.div_rem_limb(y),
+            BatchSize::SmallInput,
+        )
     });
 
-    let reciprocals = ys_limb
-        .iter()
-        .map(|y| Reciprocal::new(**y))
-        .collect::<Vec<_>>();
-    group.bench_function("div/rem, 4/1, single limb with reciprocal", |b| {
-        b.iter(|| {
-            xs.iter()
-                .zip(reciprocals.iter())
-                .map(|(x, r)| x.div_rem_limb_with_reciprocal(r))
-                .for_each(drop)
-        })
+    group.bench_function("div/rem, U256/Limb, single limb with reciprocal", |b| {
+        b.iter_batched(
+            || {
+                let x = U256::random(&mut OsRng);
+                let y = Limb::random(&mut OsRng);
+                let r = Reciprocal::new(y);
+                (x, r)
+            },
+            |(x, r)| x.div_rem_limb_with_reciprocal(&r),
+            BatchSize::SmallInput,
+        )
     });
 }
 
-fn bench_modpow<'a, M: Measurement>(group: &mut BenchmarkGroup<'a, M>) {
-    const TEST_SET: usize = 10;
-    let xs = (0..TEST_SET)
-        .map(|_| U256::random(&mut OsRng))
-        .collect::<Vec<_>>();
-    let moduli = (0..TEST_SET)
-        .map(|_| U256::random(&mut OsRng) | U256::ONE)
-        .collect::<Vec<_>>();
-    let powers = (0..TEST_SET)
-        .map(|_| U256::random(&mut OsRng) | (U256::ONE << (U256::BITS - 1)))
-        .collect::<Vec<_>>();
+fn bench_montgomery_ops<M: Measurement>(group: &mut BenchmarkGroup<'_, M>) {
+    let params = DynResidueParams::new(&(U256::random(&mut OsRng) | U256::ONE));
+    group.bench_function("multiplication, U256*U256", |b| {
+        b.iter_batched(
+            || {
+                let x = DynResidue::new(&U256::random(&mut OsRng), params);
+                let y = DynResidue::new(&U256::random(&mut OsRng), params);
+                (x, y)
+            },
+            |(x, y)| x * y,
+            BatchSize::SmallInput,
+        )
+    });
+
+    let m = U256::random(&mut OsRng) | U256::ONE;
+    let params = DynResidueParams::new(&m);
+    group.bench_function("modpow, U256^U256", |b| {
+        b.iter_batched(
+            || {
+                let x = U256::random(&mut OsRng);
+                let x_m = DynResidue::new(&x, params);
+                let p = U256::random(&mut OsRng) | (U256::ONE << (U256::BITS - 1));
+                (x_m, p)
+            },
+            |(x, p)| x.pow(&p),
+            BatchSize::SmallInput,
+        )
+    });
+}
 
-    let params = moduli.iter().map(DynResidueParams::new).collect::<Vec<_>>();
-    let xs_m = xs
-        .iter()
-        .zip(params.iter())
-        .map(|(x, p)| DynResidue::new(x, *p))
-        .collect::<Vec<_>>();
+fn bench_montgomery_conversion<M: Measurement>(group: &mut BenchmarkGroup<'_, M>) {
+    group.bench_function("DynResidueParams creation", |b| {
+        b.iter_batched(
+            || U256::random(&mut OsRng) | U256::ONE,
+            |modulus| DynResidueParams::new(&modulus),
+            BatchSize::SmallInput,
+        )
+    });
 
-    group.bench_function("modpow, 4^4", |b| {
-        b.iter(|| {
-            xs_m.iter()
-                .zip(powers.iter())
-                .map(|(x, p)| x.pow(p))
-                .for_each(drop)
-        })
+    let params = DynResidueParams::new(&(U256::random(&mut OsRng) | U256::ONE));
+    group.bench_function("DynResidue creation", |b| {
+        b.iter_batched(
+            || U256::random(&mut OsRng),
+            |x| DynResidue::new(&x, params),
+            BatchSize::SmallInput,
+        )
+    });
+
+    let params = DynResidueParams::new(&(U256::random(&mut OsRng) | U256::ONE));
+    group.bench_function("DynResidue retrieve", |b| {
+        b.iter_batched(
+            || DynResidue::new(&U256::random(&mut OsRng), params),
+            |x| x.retrieve(),
+            BatchSize::SmallInput,
+        )
     });
 }
 
 fn bench_wrapping_ops(c: &mut Criterion) {
     let mut group = c.benchmark_group("wrapping ops");
     bench_division(&mut group);
-    bench_modpow(&mut group);
     group.finish();
 }
 
-criterion_group!(benches, bench_wrapping_ops);
+fn bench_montgomery(c: &mut Criterion) {
+    let mut group = c.benchmark_group("Montgomery arithmetic");
+    bench_montgomery_conversion(&mut group);
+    bench_montgomery_ops(&mut group);
+    group.finish();
+}
+
+criterion_group!(benches, bench_wrapping_ops, bench_montgomery);
 criterion_main!(benches);