From fd091b04316db9dc5fafadbd6bdbe60b127408a9 Mon Sep 17 00:00:00 2001 From: Daniel Mueller Date: Thu, 2 Jan 2020 08:32:06 -0800 Subject: Update nitrokey crate to 0.4.0 This change finally updates the version of the nitrokey crate that we consume to 0.4.0. Along with that we update rand_core, one of its dependencies, to 0.5.1. Further more we add cfg-if in version 0.1.10 and getrandom in version 0.1.13, both of which are now new (non-development) dependencies. Import subrepo nitrokey/:nitrokey at e81057037e9b4f370b64c0a030a725bc6bdfb870 Import subrepo cfg-if/:cfg-if at 4484a6faf816ff8058088ad857b0c6bb2f4b02b2 Import subrepo getrandom/:getrandom at d661aa7e1b8cc80b47dabe3d2135b3b47d2858af Import subrepo rand/:rand at d877ed528248b52d947e0484364a4e1ae59ca502 --- rand/src/seq/index.rs | 145 ++++++++++++++++++++++++++++++-------------------- 1 file changed, 88 insertions(+), 57 deletions(-) (limited to 'rand/src/seq/index.rs') diff --git a/rand/src/seq/index.rs b/rand/src/seq/index.rs index 3d4df3a..22a5733 100644 --- a/rand/src/seq/index.rs +++ b/rand/src/seq/index.rs @@ -6,18 +6,18 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -//! Index sampling +//! Low-level API for sampling indices #[cfg(feature="alloc")] use core::slice; #[cfg(feature="std")] use std::vec; -#[cfg(all(feature="alloc", not(feature="std")))] use alloc::vec::{self, Vec}; +#[cfg(all(feature="alloc", not(feature="std")))] use crate::alloc::vec::{self, Vec}; // BTreeMap is not as fast in tests, but better than nothing. #[cfg(feature="std")] use std::collections::{HashSet}; -#[cfg(all(feature="alloc", not(feature="std")))] use alloc::collections::BTreeSet; +#[cfg(all(feature="alloc", not(feature="std")))] use crate::alloc::collections::BTreeSet; -#[cfg(feature="alloc")] use distributions::{Distribution, Uniform}; -use Rng; +#[cfg(feature="alloc")] use crate::distributions::{Distribution, Uniform, uniform::SampleUniform}; +use crate::Rng; /// A vector of indices. /// @@ -30,25 +30,37 @@ pub enum IndexVec { impl IndexVec { /// Returns the number of indices + #[inline] pub fn len(&self) -> usize { - match self { - &IndexVec::U32(ref v) => v.len(), - &IndexVec::USize(ref v) => v.len(), + match *self { + IndexVec::U32(ref v) => v.len(), + IndexVec::USize(ref v) => v.len(), + } + } + + /// Returns `true` if the length is 0. + #[inline] + pub fn is_empty(&self) -> bool { + match *self { + IndexVec::U32(ref v) => v.is_empty(), + IndexVec::USize(ref v) => v.is_empty(), } } /// Return the value at the given `index`. /// - /// (Note: we cannot implement `std::ops::Index` because of lifetime + /// (Note: we cannot implement [`std::ops::Index`] because of lifetime /// restrictions.) + #[inline] pub fn index(&self, index: usize) -> usize { - match self { - &IndexVec::U32(ref v) => v[index] as usize, - &IndexVec::USize(ref v) => v[index], + match *self { + IndexVec::U32(ref v) => v[index] as usize, + IndexVec::USize(ref v) => v[index], } } /// Return result as a `Vec`. Conversion may or may not be trivial. + #[inline] pub fn into_vec(self) -> Vec { match self { IndexVec::U32(v) => v.into_iter().map(|i| i as usize).collect(), @@ -57,14 +69,16 @@ impl IndexVec { } /// Iterate over the indices as a sequence of `usize` values - pub fn iter<'a>(&'a self) -> IndexVecIter<'a> { - match self { - &IndexVec::U32(ref v) => IndexVecIter::U32(v.iter()), - &IndexVec::USize(ref v) => IndexVecIter::USize(v.iter()), + #[inline] + pub fn iter(&self) -> IndexVecIter<'_> { + match *self { + IndexVec::U32(ref v) => IndexVecIter::U32(v.iter()), + IndexVec::USize(ref v) => IndexVecIter::USize(v.iter()), } } /// Convert into an iterator over the indices as a sequence of `usize` values + #[inline] pub fn into_iter(self) -> IndexVecIntoIter { match self { IndexVec::U32(v) => IndexVecIntoIter::U32(v.into_iter()), @@ -88,12 +102,14 @@ impl PartialEq for IndexVec { } impl From> for IndexVec { + #[inline] fn from(v: Vec) -> Self { IndexVec::U32(v) } } impl From> for IndexVec { + #[inline] fn from(v: Vec) -> Self { IndexVec::USize(v) } @@ -108,18 +124,20 @@ pub enum IndexVecIter<'a> { impl<'a> Iterator for IndexVecIter<'a> { type Item = usize; + #[inline] fn next(&mut self) -> Option { use self::IndexVecIter::*; - match self { - &mut U32(ref mut iter) => iter.next().map(|i| *i as usize), - &mut USize(ref mut iter) => iter.next().cloned(), + match *self { + U32(ref mut iter) => iter.next().map(|i| *i as usize), + USize(ref mut iter) => iter.next().cloned(), } } + #[inline] fn size_hint(&self) -> (usize, Option) { - match self { - &IndexVecIter::U32(ref v) => v.size_hint(), - &IndexVecIter::USize(ref v) => v.size_hint(), + match *self { + IndexVecIter::U32(ref v) => v.size_hint(), + IndexVecIter::USize(ref v) => v.size_hint(), } } } @@ -136,19 +154,21 @@ pub enum IndexVecIntoIter { impl Iterator for IndexVecIntoIter { type Item = usize; + #[inline] fn next(&mut self) -> Option { use self::IndexVecIntoIter::*; - match self { - &mut U32(ref mut v) => v.next().map(|i| i as usize), - &mut USize(ref mut v) => v.next(), + match *self { + U32(ref mut v) => v.next().map(|i| i as usize), + USize(ref mut v) => v.next(), } } + #[inline] fn size_hint(&self) -> (usize, Option) { use self::IndexVecIntoIter::*; - match self { - &U32(ref v) => v.size_hint(), - &USize(ref v) => v.size_hint(), + match *self { + U32(ref v) => v.size_hint(), + USize(ref v) => v.size_hint(), } } } @@ -173,14 +193,13 @@ impl ExactSizeIterator for IndexVecIntoIter {} /// Note that performance is significantly better over `u32` indices than over /// `u64` indices. Because of this we hide the underlying type behind an /// abstraction, `IndexVec`. -/// +/// /// If an allocation-free `no_std` function is required, it is suggested /// to adapt the internal `sample_floyd` implementation. /// /// Panics if `amount > length`. pub fn sample(rng: &mut R, length: usize, amount: usize) -> IndexVec - where R: Rng + ?Sized, -{ +where R: Rng + ?Sized { if amount > length { panic!("`amount` of samples must be less than or equal to `length`"); } @@ -213,9 +232,7 @@ pub fn sample(rng: &mut R, length: usize, amount: usize) -> IndexVec if (length as f32) < C[j] * (amount as f32) { sample_inplace(rng, length, amount) } else { - // note: could have a specific u32 impl, but I'm lazy and - // generics don't have usable conversions - sample_rejection(rng, length as usize, amount as usize) + sample_rejection(rng, length, amount) } } } @@ -227,8 +244,7 @@ pub fn sample(rng: &mut R, length: usize, amount: usize) -> IndexVec /// /// This implementation uses `O(amount)` memory and `O(amount^2)` time. fn sample_floyd(rng: &mut R, length: u32, amount: u32) -> IndexVec - where R: Rng + ?Sized, -{ +where R: Rng + ?Sized { // For small amount we use Floyd's fully-shuffled variant. For larger // amounts this is slow due to Vec::insert performance, so we shuffle // afterwards. Benchmarks show little overhead from extra logic. @@ -243,11 +259,9 @@ fn sample_floyd(rng: &mut R, length: u32, amount: u32) -> IndexVec indices.insert(pos, j); continue; } - } else { - if indices.contains(&t) { - indices.push(j); - continue; - } + } else if indices.contains(&t) { + indices.push(j); + continue; } indices.push(t); } @@ -274,8 +288,7 @@ fn sample_floyd(rng: &mut R, length: u32, amount: u32) -> IndexVec /// /// Set-up is `O(length)` time and memory and shuffling is `O(amount)` time. fn sample_inplace(rng: &mut R, length: u32, amount: u32) -> IndexVec - where R: Rng + ?Sized, -{ +where R: Rng + ?Sized { debug_assert!(amount <= length); let mut indices: Vec = Vec::with_capacity(length as usize); indices.extend(0..length); @@ -288,21 +301,36 @@ fn sample_inplace(rng: &mut R, length: u32, amount: u32) -> IndexVec IndexVec::from(indices) } +trait UInt: Copy + PartialOrd + Ord + PartialEq + Eq + SampleUniform + core::hash::Hash { + fn zero() -> Self; + fn as_usize(self) -> usize; +} +impl UInt for u32 { + #[inline] fn zero() -> Self { 0 } + #[inline] fn as_usize(self) -> usize { self as usize } +} +impl UInt for usize { + #[inline] fn zero() -> Self { 0 } + #[inline] fn as_usize(self) -> usize { self } +} + /// Randomly sample exactly `amount` indices from `0..length`, using rejection /// sampling. -/// +/// /// Since `amount <<< length` there is a low chance of a random sample in /// `0..length` being a duplicate. We test for duplicates and resample where /// necessary. The algorithm is `O(amount)` time and memory. -fn sample_rejection(rng: &mut R, length: usize, amount: usize) -> IndexVec - where R: Rng + ?Sized, -{ +/// +/// This function is generic over X primarily so that results are value-stable +/// over 32-bit and 64-bit platforms. +fn sample_rejection(rng: &mut R, length: X, amount: X) -> IndexVec +where R: Rng + ?Sized, IndexVec: From> { debug_assert!(amount < length); - #[cfg(feature="std")] let mut cache = HashSet::with_capacity(amount); + #[cfg(feature="std")] let mut cache = HashSet::with_capacity(amount.as_usize()); #[cfg(not(feature="std"))] let mut cache = BTreeSet::new(); - let distr = Uniform::new(0, length); - let mut indices = Vec::with_capacity(amount); - for _ in 0..amount { + let distr = Uniform::new(X::zero(), length); + let mut indices = Vec::with_capacity(amount.as_usize()); + for _ in 0..amount.as_usize() { let mut pos = distr.sample(rng); while !cache.insert(pos) { pos = distr.sample(rng); @@ -310,30 +338,32 @@ fn sample_rejection(rng: &mut R, length: usize, amount: usize) -> IndexVec indices.push(pos); } - debug_assert_eq!(indices.len(), amount); + debug_assert_eq!(indices.len(), amount.as_usize()); IndexVec::from(indices) } #[cfg(test)] mod test { + #[cfg(feature="std")] use std::vec; + #[cfg(all(feature="alloc", not(feature="std")))] use crate::alloc::vec; use super::*; #[test] fn test_sample_boundaries() { - let mut r = ::test::rng(404); + let mut r = crate::test::rng(404); assert_eq!(sample_inplace(&mut r, 0, 0).len(), 0); assert_eq!(sample_inplace(&mut r, 1, 0).len(), 0); assert_eq!(sample_inplace(&mut r, 1, 1).into_vec(), vec![0]); - assert_eq!(sample_rejection(&mut r, 1, 0).len(), 0); + assert_eq!(sample_rejection(&mut r, 1u32, 0).len(), 0); assert_eq!(sample_floyd(&mut r, 0, 0).len(), 0); assert_eq!(sample_floyd(&mut r, 1, 0).len(), 0); assert_eq!(sample_floyd(&mut r, 1, 1).into_vec(), vec![0]); // These algorithms should be fast with big numbers. Test average. - let sum: usize = sample_rejection(&mut r, 1 << 25, 10) + let sum: usize = sample_rejection(&mut r, 1 << 25, 10u32) .into_iter().sum(); assert!(1 << 25 < sum && sum < (1 << 25) * 25); @@ -343,8 +373,9 @@ mod test { } #[test] + #[cfg(not(miri))] // Miri is too slow fn test_sample_alg() { - let seed_rng = ::test::rng; + let seed_rng = crate::test::rng; // We can't test which algorithm is used directly, but Floyd's alg // should produce different results from the others. (Also, `inplace` @@ -371,7 +402,7 @@ mod test { // A large length and larger amount should use cache let (length, amount): (usize, usize) = (1<<20, 600); let v1 = sample(&mut seed_rng(422), length, amount); - let v2 = sample_rejection(&mut seed_rng(422), length, amount); + let v2 = sample_rejection(&mut seed_rng(422), length as u32, amount as u32); assert!(v1.iter().all(|e| e < length)); assert_eq!(v1, v2); } -- cgit v1.2.1