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

2 files changed, 326 insertions, 340 deletions

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<usize>`. Conversion may or may not be trivial.
+    #[inline]
     pub fn into_vec(self) -> Vec<usize> {
         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<Vec<u32>> for IndexVec {
+    #[inline]
     fn from(v: Vec<u32>) -> Self {
         IndexVec::U32(v)
     }
 }
 
 impl From<Vec<usize>> for IndexVec {
+    #[inline]
     fn from(v: Vec<usize>) -> 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<usize> {
         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<usize>) {
-        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<Self::Item> {
         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<usize>) {
         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<R>(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<R>(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<R>(rng: &mut R, length: usize, amount: usize) -> IndexVec
 ///
 /// This implementation uses `O(amount)` memory and `O(amount^2)` time.
 fn sample_floyd<R>(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<R>(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<R>(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<R>(rng: &mut R, length: u32, amount: u32) -> IndexVec
-    where R: Rng + ?Sized,
-{
+where R: Rng + ?Sized {
     debug_assert!(amount <= length);
     let mut indices: Vec<u32> = Vec::with_capacity(length as usize);
     indices.extend(0..length);
@@ -288,21 +301,36 @@ fn sample_inplace<R>(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<R>(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<X: UInt, R>(rng: &mut R, length: X, amount: X) -> IndexVec
+where R: Rng + ?Sized, IndexVec: From<Vec<X>> {
     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<R>(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);
     }
diff --git a/rand/src/seq/mod.rs b/rand/src/seq/mod.rs
index 9959602..cec9bb1 100644
--- a/rand/src/seq/mod.rs
+++ b/rand/src/seq/mod.rs
@@ -6,25 +6,55 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! Functions for randomly accessing and sampling sequences.
+//! Sequence-related functionality
 //! 
-//! TODO: module doc
+//! This module provides:
+//! 
+//! *   [`seq::SliceRandom`] slice sampling and mutation
+//! *   [`seq::IteratorRandom`] iterator sampling
+//! *   [`seq::index::sample`] low-level API to choose multiple indices from
+//!     `0..length`
+//! 
+//! Also see:
+//! 
+//! *   [`distributions::weighted`] module which provides implementations of
+//!     weighted index sampling.
+//! 
+//! In order to make results reproducible across 32-64 bit architectures, all
+//! `usize` indices are sampled as a `u32` where possible (also providing a
+//! small performance boost in some cases).
 
 
 #[cfg(feature="alloc")] pub mod index;
 
 #[cfg(feature="alloc")] use core::ops::Index;
 
-#[cfg(all(feature="alloc", not(feature="std")))] use alloc::vec::Vec;
+#[cfg(all(feature="alloc", not(feature="std")))] use crate::alloc::vec::Vec;
 
-use Rng;
-#[cfg(feature="alloc")] use distributions::WeightedError;
-#[cfg(feature="alloc")] use distributions::uniform::{SampleUniform, SampleBorrow};
+use crate::Rng;
+#[cfg(feature="alloc")] use crate::distributions::WeightedError;
+#[cfg(feature="alloc")] use crate::distributions::uniform::{SampleUniform, SampleBorrow};
 
 /// Extension trait on slices, providing random mutation and sampling methods.
 /// 
-/// An implementation is provided for slices. This may also be implementable for
-/// other types.
+/// This trait is implemented on all `[T]` slice types, providing several
+/// methods for choosing and shuffling elements. You must `use` this trait:
+/// 
+/// ```
+/// use rand::seq::SliceRandom;
+/// 
+/// fn main() {
+///     let mut rng = rand::thread_rng();
+///     let mut bytes = "Hello, random!".to_string().into_bytes();
+///     bytes.shuffle(&mut rng);
+///     let str = String::from_utf8(bytes).unwrap();
+///     println!("{}", str);
+/// }
+/// ```
+/// Example output (non-deterministic):
+/// ```none
+/// l,nmroHado !le
+/// ```
 pub trait SliceRandom {
     /// The element type.
     type Item;
@@ -32,7 +62,7 @@ pub trait SliceRandom {
     /// Returns a reference to one random element of the slice, or `None` if the
     /// slice is empty.
     /// 
-    /// Depending on the implementation, complexity is expected to be `O(1)`.
+    /// For slices, complexity is `O(1)`.
     ///
     /// # Example
     ///
@@ -46,33 +76,33 @@ pub trait SliceRandom {
     /// assert_eq!(choices[..0].choose(&mut rng), None);
     /// ```
     fn choose<R>(&self, rng: &mut R) -> Option<&Self::Item>
-        where R: Rng + ?Sized;
+    where R: Rng + ?Sized;
 
     /// Returns a mutable reference to one random element of the slice, or
     /// `None` if the slice is empty.
-    /// 
-    /// Depending on the implementation, complexity is expected to be `O(1)`.
+    ///
+    /// For slices, complexity is `O(1)`.
     fn choose_mut<R>(&mut self, rng: &mut R) -> Option<&mut Self::Item>
-        where R: Rng + ?Sized;
+    where R: Rng + ?Sized;
 
-    /// Produces an iterator that chooses `amount` elements from the slice at
-    /// random without repeating any, and returns them in random order.
-    /// 
-    /// In case this API is not sufficiently flexible, use `index::sample` then
-    /// apply the indices to the slice.
-    /// 
-    /// Complexity is expected to be the same as `index::sample`.
-    /// 
+    /// Chooses `amount` elements from the slice at random, without repetition,
+    /// and in random order. The returned iterator is appropriate both for
+    /// collection into a `Vec` and filling an existing buffer (see example).
+    ///
+    /// In case this API is not sufficiently flexible, use [`index::sample`].
+    ///
+    /// For slices, complexity is the same as [`index::sample`].
+    ///
     /// # Example
     /// ```
     /// use rand::seq::SliceRandom;
-    /// 
+    ///
     /// let mut rng = &mut rand::thread_rng();
     /// let sample = "Hello, audience!".as_bytes();
-    /// 
+    ///
     /// // collect the results into a vector:
     /// let v: Vec<u8> = sample.choose_multiple(&mut rng, 3).cloned().collect();
-    /// 
+    ///
     /// // store in a buffer:
     /// let mut buf = [0u8; 5];
     /// for (b, slot) in sample.choose_multiple(&mut rng, buf.len()).zip(buf.iter_mut()) {
@@ -81,13 +111,18 @@ pub trait SliceRandom {
     /// ```
     #[cfg(feature = "alloc")]
     fn choose_multiple<R>(&self, rng: &mut R, amount: usize) -> SliceChooseIter<Self, Self::Item>
-        where R: Rng + ?Sized;
+    where R: Rng + ?Sized;
 
-    /// Similar to [`choose`], where the likelihood of each outcome may be
-    /// specified. The specified function `weight` maps items `x` to a relative
+    /// Similar to [`choose`], but where the likelihood of each outcome may be
+    /// specified.
+    /// 
+    /// The specified function `weight` maps each item `x` to a relative
     /// likelihood `weight(x)`. The probability of each item being selected is
     /// therefore `weight(x) / s`, where `s` is the sum of all `weight(x)`.
     ///
+    /// For slices of length `n`, complexity is `O(n)`.
+    /// See also [`choose_weighted_mut`], [`distributions::weighted`].
+    ///
     /// # Example
     ///
     /// ```
@@ -98,47 +133,59 @@ pub trait SliceRandom {
     /// // 50% chance to print 'a', 25% chance to print 'b', 25% chance to print 'c'
     /// println!("{:?}", choices.choose_weighted(&mut rng, |item| item.1).unwrap().0);
     /// ```
-    /// [`choose`]: trait.SliceRandom.html#method.choose
+    /// [`choose`]: SliceRandom::choose
+    /// [`choose_weighted_mut`]: SliceRandom::choose_weighted_mut
+    /// [`distributions::weighted`]: crate::distributions::weighted
     #[cfg(feature = "alloc")]
-    fn choose_weighted<R, F, B, X>(&self, rng: &mut R, weight: F) -> Result<&Self::Item, WeightedError>
-        where R: Rng + ?Sized,
-              F: Fn(&Self::Item) -> B,
-              B: SampleBorrow<X>,
-              X: SampleUniform +
-                 for<'a> ::core::ops::AddAssign<&'a X> +
-                 ::core::cmp::PartialOrd<X> +
-                 Clone +
-                 Default;
-
-    /// Similar to [`choose_mut`], where the likelihood of each outcome may be
-    /// specified. The specified function `weight` maps items `x` to a relative
+    fn choose_weighted<R, F, B, X>(
+        &self, rng: &mut R, weight: F,
+    ) -> Result<&Self::Item, WeightedError>
+    where
+        R: Rng + ?Sized,
+        F: Fn(&Self::Item) -> B,
+        B: SampleBorrow<X>,
+        X: SampleUniform
+            + for<'a> ::core::ops::AddAssign<&'a X>
+            + ::core::cmp::PartialOrd<X>
+            + Clone
+            + Default;
+
+    /// Similar to [`choose_mut`], but where the likelihood of each outcome may
+    /// be specified.
+    /// 
+    /// The specified function `weight` maps each item `x` to a relative
     /// likelihood `weight(x)`. The probability of each item being selected is
     /// therefore `weight(x) / s`, where `s` is the sum of all `weight(x)`.
     ///
-    /// See also [`choose_weighted`].
+    /// For slices of length `n`, complexity is `O(n)`.
+    /// See also [`choose_weighted`], [`distributions::weighted`].
     ///
-    /// [`choose_mut`]: trait.SliceRandom.html#method.choose_mut
-    /// [`choose_weighted`]: trait.SliceRandom.html#method.choose_weighted
+    /// [`choose_mut`]: SliceRandom::choose_mut
+    /// [`choose_weighted`]: SliceRandom::choose_weighted
+    /// [`distributions::weighted`]: crate::distributions::weighted
     #[cfg(feature = "alloc")]
-    fn choose_weighted_mut<R, F, B, X>(&mut self, rng: &mut R, weight: F) -> Result<&mut Self::Item, WeightedError>
-        where R: Rng + ?Sized,
-              F: Fn(&Self::Item) -> B,
-              B: SampleBorrow<X>,
-              X: SampleUniform +
-                 for<'a> ::core::ops::AddAssign<&'a X> +
-                 ::core::cmp::PartialOrd<X> +
-                 Clone +
-                 Default;
+    fn choose_weighted_mut<R, F, B, X>(
+        &mut self, rng: &mut R, weight: F,
+    ) -> Result<&mut Self::Item, WeightedError>
+    where
+        R: Rng + ?Sized,
+        F: Fn(&Self::Item) -> B,
+        B: SampleBorrow<X>,
+        X: SampleUniform
+            + for<'a> ::core::ops::AddAssign<&'a X>
+            + ::core::cmp::PartialOrd<X>
+            + Clone
+            + Default;
 
     /// Shuffle a mutable slice in place.
-    /// 
-    /// Depending on the implementation, complexity is expected to be `O(1)`.
+    ///
+    /// For slices of length `n`, complexity is `O(n)`.
     ///
     /// # Example
     ///
     /// ```
-    /// use rand::thread_rng;
     /// use rand::seq::SliceRandom;
+    /// use rand::thread_rng;
     ///
     /// let mut rng = thread_rng();
     /// let mut y = [1, 2, 3, 4, 5];
@@ -146,7 +193,8 @@ pub trait SliceRandom {
     /// y.shuffle(&mut rng);
     /// println!("Shuffled:   {:?}", y);
     /// ```
-    fn shuffle<R>(&mut self, rng: &mut R) where R: Rng + ?Sized;
+    fn shuffle<R>(&mut self, rng: &mut R)
+    where R: Rng + ?Sized;
 
     /// Shuffle a slice in place, but exit early.
     ///
@@ -164,47 +212,65 @@ pub trait SliceRandom {
     /// If `amount` is greater than the number of elements in the slice, this
     /// will perform a full shuffle.
     ///
-    /// Complexity is expected to be `O(m)` where `m = amount`.
-    fn partial_shuffle<R>(&mut self, rng: &mut R, amount: usize)
-        -> (&mut [Self::Item], &mut [Self::Item]) where R: Rng + ?Sized;
+    /// For slices, complexity is `O(m)` where `m = amount`.
+    fn partial_shuffle<R>(
+        &mut self, rng: &mut R, amount: usize,
+    ) -> (&mut [Self::Item], &mut [Self::Item])
+    where R: Rng + ?Sized;
 }
 
 /// Extension trait on iterators, providing random sampling methods.
+/// 
+/// This trait is implemented on all sized iterators, providing methods for
+/// choosing one or more elements. You must `use` this trait:
+/// 
+/// ```
+/// use rand::seq::IteratorRandom;
+/// 
+/// fn main() {
+///     let mut rng = rand::thread_rng();
+///     
+///     let faces = "😀😎😐😕😠😢";
+///     println!("I am {}!", faces.chars().choose(&mut rng).unwrap());
+/// }
+/// ```
+/// Example output (non-deterministic):
+/// ```none
+/// I am 😀!
+/// ```
 pub trait IteratorRandom: Iterator + Sized {
-    /// Choose one element at random from the iterator. If you have a slice,
-    /// it's significantly faster to call the [`choose`] or [`choose_mut`]
-    /// functions using the slice instead.
-    ///
-    /// Returns `None` if and only if the iterator is empty.
+    /// Choose one element at random from the iterator.
     /// 
-    /// Complexity is `O(n)`, where `n` is the length of the iterator.
-    /// This likely consumes multiple random numbers, but the exact number
-    /// is unspecified.
+    /// Returns `None` if and only if the iterator is empty.
     ///
-    /// [`choose`]: trait.SliceRandom.html#method.choose
-    /// [`choose_mut`]: trait.SliceRandom.html#method.choose_mut
+    /// This method uses [`Iterator::size_hint`] for optimisation. With an
+    /// accurate hint and where [`Iterator::nth`] is a constant-time operation
+    /// this method can offer `O(1)` performance. Where no size hint is
+    /// available, complexity is `O(n)` where `n` is the iterator length.
+    /// Partial hints (where `lower > 0`) also improve performance.
+    /// 
+    /// For slices, prefer [`SliceRandom::choose`] which guarantees `O(1)`
+    /// performance.
     fn choose<R>(mut self, rng: &mut R) -> Option<Self::Item>
-        where R: Rng + ?Sized
-    {
+    where R: Rng + ?Sized {
         let (mut lower, mut upper) = self.size_hint();
         let mut consumed = 0;
         let mut result = None;
 
         if upper == Some(lower) {
-            return if lower == 0 { None } else { self.nth(rng.gen_range(0, lower)) };
+            return if lower == 0 { None } else { self.nth(gen_index(rng, lower)) };
         }
 
         // Continue until the iterator is exhausted
         loop {
             if lower > 1 {
-                let ix = rng.gen_range(0, lower + consumed);
-                let skip;
-                if ix < lower {
+                let ix = gen_index(rng, lower + consumed);
+                let skip = if ix < lower {
                     result = self.nth(ix);
-                    skip = lower - (ix + 1);
+                    lower - (ix + 1)
                 } else {
-                    skip = lower;
-                }
+                    lower
+                };
                 if upper == Some(lower) {
                     return result;
                 }
@@ -230,21 +296,21 @@ pub trait IteratorRandom: Iterator + Sized {
         }
     }
 
-    /// Collects `amount` values at random from the iterator into a supplied
-    /// buffer.
-    /// 
+    /// Collects values at random from the iterator into a supplied buffer
+    /// until that buffer is filled.
+    ///
     /// Although the elements are selected randomly, the order of elements in
     /// the buffer is neither stable nor fully random. If random ordering is
     /// desired, shuffle the result.
-    /// 
-    /// Returns the number of elements added to the buffer. This equals `amount`
-    /// unless the iterator contains insufficient elements, in which case this
-    /// equals the number of elements available.
-    /// 
+    ///
+    /// Returns the number of elements added to the buffer. This equals the length
+    /// of the buffer unless the iterator contains insufficient elements, in which
+    /// case this equals the number of elements available.
+    ///
     /// Complexity is `O(n)` where `n` is the length of the iterator.
-    fn choose_multiple_fill<R>(mut self, rng: &mut R, buf: &mut [Self::Item])
-        -> usize where R: Rng + ?Sized
-    {
+    /// For slices, prefer [`SliceRandom::choose_multiple`].
+    fn choose_multiple_fill<R>(mut self, rng: &mut R, buf: &mut [Self::Item]) -> usize
+    where R: Rng + ?Sized {
         let amount = buf.len();
         let mut len = 0;
         while len < amount {
@@ -259,7 +325,7 @@ pub trait IteratorRandom: Iterator + Sized {
 
         // Continue, since the iterator was not exhausted
         for (i, elem) in self.enumerate() {
-            let k = rng.gen_range(0, i + 1 + amount);
+            let k = gen_index(rng, i + 1 + amount);
             if let Some(slot) = buf.get_mut(k) {
                 *slot = elem;
             }
@@ -274,16 +340,16 @@ pub trait IteratorRandom: Iterator + Sized {
     /// Although the elements are selected randomly, the order of elements in
     /// the buffer is neither stable nor fully random. If random ordering is
     /// desired, shuffle the result.
-    /// 
+    ///
     /// The length of the returned vector equals `amount` unless the iterator
     /// contains insufficient elements, in which case it equals the number of
     /// elements available.
-    /// 
+    ///
     /// Complexity is `O(n)` where `n` is the length of the iterator.
+    /// For slices, prefer [`SliceRandom::choose_multiple`].
     #[cfg(feature = "alloc")]
     fn choose_multiple<R>(mut self, rng: &mut R, amount: usize) -> Vec<Self::Item>
-        where R: Rng + ?Sized
-    {
+    where R: Rng + ?Sized {
         let mut reservoir = Vec::with_capacity(amount);
         reservoir.extend(self.by_ref().take(amount));
 
@@ -293,7 +359,7 @@ pub trait IteratorRandom: Iterator + Sized {
         // If the iterator stops once, then so do we.
         if reservoir.len() == amount {
             for (i, elem) in self.enumerate() {
-                let k = rng.gen_range(0, i + 1 + amount);
+                let k = gen_index(rng, i + 1 + amount);
                 if let Some(slot) = reservoir.get_mut(k) {
                     *slot = elem;
                 }
@@ -312,31 +378,27 @@ impl<T> SliceRandom for [T] {
     type Item = T;
 
     fn choose<R>(&self, rng: &mut R) -> Option<&Self::Item>
-        where R: Rng + ?Sized
-    {
+    where R: Rng + ?Sized {
         if self.is_empty() {
             None
         } else {
-            Some(&self[rng.gen_range(0, self.len())])
+            Some(&self[gen_index(rng, self.len())])
         }
     }
 
     fn choose_mut<R>(&mut self, rng: &mut R) -> Option<&mut Self::Item>
-        where R: Rng + ?Sized
-    {
+    where R: Rng + ?Sized {
         if self.is_empty() {
             None
         } else {
             let len = self.len();
-            Some(&mut self[rng.gen_range(0, len)])
+            Some(&mut self[gen_index(rng, len)])
         }
     }
 
     #[cfg(feature = "alloc")]
-    fn choose_multiple<R>(&self, rng: &mut R, amount: usize)
-        -> SliceChooseIter<Self, Self::Item>
-        where R: Rng + ?Sized
-    {
+    fn choose_multiple<R>(&self, rng: &mut R, amount: usize) -> SliceChooseIter<Self, Self::Item>
+    where R: Rng + ?Sized {
         let amount = ::core::cmp::min(amount, self.len());
         SliceChooseIter {
             slice: self,
@@ -346,57 +408,66 @@ impl<T> SliceRandom for [T] {
     }
 
     #[cfg(feature = "alloc")]
-    fn choose_weighted<R, F, B, X>(&self, rng: &mut R, weight: F) -> Result<&Self::Item, WeightedError>
-        where R: Rng + ?Sized,
-              F: Fn(&Self::Item) -> B,
-              B: SampleBorrow<X>,
-              X: SampleUniform +
-                 for<'a> ::core::ops::AddAssign<&'a X> +
-                 ::core::cmp::PartialOrd<X> +
-                 Clone +
-                 Default {
-        use distributions::{Distribution, WeightedIndex};
+    fn choose_weighted<R, F, B, X>(
+        &self, rng: &mut R, weight: F,
+    ) -> Result<&Self::Item, WeightedError>
+    where
+        R: Rng + ?Sized,
+        F: Fn(&Self::Item) -> B,
+        B: SampleBorrow<X>,
+        X: SampleUniform
+            + for<'a> ::core::ops::AddAssign<&'a X>
+            + ::core::cmp::PartialOrd<X>
+            + Clone
+            + Default,
+    {
+        use crate::distributions::{Distribution, WeightedIndex};
         let distr = WeightedIndex::new(self.iter().map(weight))?;
         Ok(&self[distr.sample(rng)])
     }
 
     #[cfg(feature = "alloc")]
-    fn choose_weighted_mut<R, F, B, X>(&mut self, rng: &mut R, weight: F) -> Result<&mut Self::Item, WeightedError>
-        where R: Rng + ?Sized,
-              F: Fn(&Self::Item) -> B,
-              B: SampleBorrow<X>,
-              X: SampleUniform +
-                 for<'a> ::core::ops::AddAssign<&'a X> +
-                 ::core::cmp::PartialOrd<X> +
-                 Clone +
-                 Default {
-        use distributions::{Distribution, WeightedIndex};
+    fn choose_weighted_mut<R, F, B, X>(
+        &mut self, rng: &mut R, weight: F,
+    ) -> Result<&mut Self::Item, WeightedError>
+    where
+        R: Rng + ?Sized,
+        F: Fn(&Self::Item) -> B,
+        B: SampleBorrow<X>,
+        X: SampleUniform
+            + for<'a> ::core::ops::AddAssign<&'a X>
+            + ::core::cmp::PartialOrd<X>
+            + Clone
+            + Default,
+    {
+        use crate::distributions::{Distribution, WeightedIndex};
         let distr = WeightedIndex::new(self.iter().map(weight))?;
         Ok(&mut self[distr.sample(rng)])
     }
 
-    fn shuffle<R>(&mut self, rng: &mut R) where R: Rng + ?Sized
-    {
+    fn shuffle<R>(&mut self, rng: &mut R)
+    where R: Rng + ?Sized {
         for i in (1..self.len()).rev() {
             // invariant: elements with index > i have been locked in place.
-            self.swap(i, rng.gen_range(0, i + 1));
+            self.swap(i, gen_index(rng, i + 1));
         }
     }
 
-    fn partial_shuffle<R>(&mut self, rng: &mut R, amount: usize)
-        -> (&mut [Self::Item], &mut [Self::Item]) where R: Rng + ?Sized
-    {
+    fn partial_shuffle<R>(
+        &mut self, rng: &mut R, amount: usize,
+    ) -> (&mut [Self::Item], &mut [Self::Item])
+    where R: Rng + ?Sized {
         // This applies Durstenfeld's algorithm for the
         // [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)
         // for an unbiased permutation, but exits early after choosing `amount`
         // elements.
-        
+
         let len = self.len();
         let end = if amount >= len { 0 } else { len - amount };
-        
+
         for i in (end..len).rev() {
             // invariant: elements with index > i have been locked in place.
-            self.swap(i, rng.gen_range(0, i + 1));
+            self.swap(i, gen_index(rng, i + 1));
         }
         let r = self.split_at_mut(end);
         (r.1, r.0)
@@ -406,8 +477,10 @@ impl<T> SliceRandom for [T] {
 impl<I> IteratorRandom for I where I: Iterator + Sized {}
 
 
-/// Iterator over multiple choices, as returned by [`SliceRandom::choose_multiple](
-/// trait.SliceRandom.html#method.choose_multiple).
+/// An iterator over multiple slice elements.
+/// 
+/// This struct is created by
+/// [`SliceRandom::choose_multiple`](trait.SliceRandom.html#tymethod.choose_multiple).
 #[cfg(feature = "alloc")]
 #[derive(Debug)]
 pub struct SliceChooseIter<'a, S: ?Sized + 'a, T: 'a> {
@@ -424,7 +497,7 @@ impl<'a, S: Index<usize, Output = T> + ?Sized + 'a, T: 'a> Iterator for SliceCho
         // TODO: investigate using SliceIndex::get_unchecked when stable
         self.indices.next().map(|i| &self.slice[i as usize])
     }
-    
+
     fn size_hint(&self) -> (usize, Option<usize>) {
         (self.indices.len(), Some(self.indices.len()))
     }
@@ -440,94 +513,39 @@ impl<'a, S: Index<usize, Output = T> + ?Sized + 'a, T: 'a> ExactSizeIterator
 }
 
 
-/// Randomly sample `amount` elements from a finite iterator.
-///
-/// Deprecated: use [`IteratorRandom::choose_multiple`] instead.
-/// 
-/// [`IteratorRandom::choose_multiple`]: trait.IteratorRandom.html#method.choose_multiple
-#[cfg(feature = "alloc")]
-#[deprecated(since="0.6.0", note="use IteratorRandom::choose_multiple instead")]
-pub fn sample_iter<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Result<Vec<T>, Vec<T>>
-    where I: IntoIterator<Item=T>,
-          R: Rng + ?Sized,
-{
-    use seq::IteratorRandom;
-    let iter = iterable.into_iter();
-    let result = iter.choose_multiple(rng, amount);
-    if result.len() == amount {
-        Ok(result)
+// Sample a number uniformly between 0 and `ubound`. Uses 32-bit sampling where
+// possible, primarily in order to produce the same output on 32-bit and 64-bit
+// platforms.
+#[inline]
+fn gen_index<R: Rng + ?Sized>(rng: &mut R, ubound: usize) -> usize {
+    if ubound <= (core::u32::MAX as usize) {
+        rng.gen_range(0, ubound as u32) as usize
     } else {
-        Err(result)
+        rng.gen_range(0, ubound)
     }
 }
 
-/// Randomly sample exactly `amount` values from `slice`.
-///
-/// The values are non-repeating and in random order.
-///
-/// This implementation uses `O(amount)` time and memory.
-///
-/// Panics if `amount > slice.len()`
-///
-/// Deprecated: use [`SliceRandom::choose_multiple`] instead.
-/// 
-/// [`SliceRandom::choose_multiple`]: trait.SliceRandom.html#method.choose_multiple
-#[cfg(feature = "alloc")]
-#[deprecated(since="0.6.0", note="use SliceRandom::choose_multiple instead")]
-pub fn sample_slice<R, T>(rng: &mut R, slice: &[T], amount: usize) -> Vec<T>
-    where R: Rng + ?Sized,
-          T: Clone
-{
-    let indices = index::sample(rng, slice.len(), amount).into_iter();
-
-    let mut out = Vec::with_capacity(amount);
-    out.extend(indices.map(|i| slice[i].clone()));
-    out
-}
-
-/// Randomly sample exactly `amount` references from `slice`.
-///
-/// The references are non-repeating and in random order.
-///
-/// This implementation uses `O(amount)` time and memory.
-///
-/// Panics if `amount > slice.len()`
-///
-/// Deprecated: use [`SliceRandom::choose_multiple`] instead.
-/// 
-/// [`SliceRandom::choose_multiple`]: trait.SliceRandom.html#method.choose_multiple
-#[cfg(feature = "alloc")]
-#[deprecated(since="0.6.0", note="use SliceRandom::choose_multiple instead")]
-pub fn sample_slice_ref<'a, R, T>(rng: &mut R, slice: &'a [T], amount: usize) -> Vec<&'a T>
-    where R: Rng + ?Sized
-{
-    let indices = index::sample(rng, slice.len(), amount).into_iter();
-
-    let mut out = Vec::with_capacity(amount);
-    out.extend(indices.map(|i| &slice[i]));
-    out
-}
 
 #[cfg(test)]
 mod test {
     use super::*;
-    #[cfg(feature = "alloc")] use {Rng, SeedableRng};
-    #[cfg(feature = "alloc")] use rngs::SmallRng;
+    #[cfg(feature = "alloc")] use crate::Rng;
     #[cfg(all(feature="alloc", not(feature="std")))]
     use alloc::vec::Vec;
 
     #[test]
     fn test_slice_choose() {
-        let mut r = ::test::rng(107);
+        let mut r = crate::test::rng(107);
         let chars = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n'];
         let mut chosen = [0i32; 14];
+        // The below all use a binomial distribution with n=1000, p=1/14.
+        // binocdf(40, 1000, 1/14) ~= 2e-5; 1-binocdf(106, ..) ~= 2e-5
         for _ in 0..1000 {
             let picked = *chars.choose(&mut r).unwrap();
             chosen[(picked as usize) - ('a' as usize)] += 1;
         }
         for count in chosen.iter() {
-            let err = *count - (1000 / (chars.len() as i32));
-            assert!(-20 <= err && err <= 20);
+            assert!(40 < *count && *count < 106);
         }
 
         chosen.iter_mut().for_each(|x| *x = 0);
@@ -535,8 +553,7 @@ mod test {
             *chosen.choose_mut(&mut r).unwrap() += 1;
         }
         for count in chosen.iter() {
-            let err = *count - (1000 / (chosen.len() as i32));
-            assert!(-20 <= err && err <= 20);
+            assert!(40 < *count && *count < 106);
         }
 
         let mut v: [isize; 0] = [];
@@ -597,8 +614,9 @@ mod test {
     }
 
     #[test]
+    #[cfg(not(miri))] // Miri is too slow
     fn test_iterator_choose() {
-        let r = &mut ::test::rng(109);
+        let r = &mut crate::test::rng(109);
         fn test_iter<R: Rng + ?Sized, Iter: Iterator<Item=usize> + Clone>(r: &mut R, iter: Iter) {
             let mut chosen = [0i32; 9];
             for _ in 0..1000 {
@@ -628,8 +646,9 @@ mod test {
     }
 
     #[test]
+    #[cfg(not(miri))] // Miri is too slow
     fn test_shuffle() {
-        let mut r = ::test::rng(108);
+        let mut r = crate::test::rng(108);
         let empty: &mut [isize] = &mut [];
         empty.shuffle(&mut r);
         let mut one = [1];
@@ -669,14 +688,16 @@ mod test {
             counts[permutation] += 1;
         }
         for count in counts.iter() {
-            let err = *count - 10000i32 / 24;
-            assert!(-50 <= err && err <= 50);
+            // Binomial(10000, 1/24) with average 416.667
+            // Octave: binocdf(n, 10000, 1/24)
+            // 99.9% chance samples lie within this range:
+            assert!(352 <= *count && *count <= 483, "count: {}", count);
         }
     }
     
     #[test]
     fn test_partial_shuffle() {
-        let mut r = ::test::rng(118);
+        let mut r = crate::test::rng(118);
         
         let mut empty: [u32; 0] = [];
         let res = empty.partial_shuffle(&mut r, 10);
@@ -696,7 +717,7 @@ mod test {
         let min_val = 1;
         let max_val = 100;
 
-        let mut r = ::test::rng(401);
+        let mut r = crate::test::rng(401);
         let vals = (min_val..max_val).collect::<Vec<i32>>();
         let small_sample = vals.iter().choose_multiple(&mut r, 5);
         let large_sample = vals.iter().choose_multiple(&mut r, vals.len() + 5);
@@ -713,75 +734,9 @@ mod test {
     
     #[test]
     #[cfg(feature = "alloc")]
-    #[allow(deprecated)]
-    fn test_sample_slice_boundaries() {
-        let empty: &[u8] = &[];
-
-        let mut r = ::test::rng(402);
-
-        // sample 0 items
-        assert_eq!(&sample_slice(&mut r, empty, 0)[..], [0u8; 0]);
-        assert_eq!(&sample_slice(&mut r, &[42, 2, 42], 0)[..], [0u8; 0]);
-
-        // sample 1 item
-        assert_eq!(&sample_slice(&mut r, &[42], 1)[..], [42]);
-        let v = sample_slice(&mut r, &[1, 42], 1)[0];
-        assert!(v == 1 || v == 42);
-
-        // sample "all" the items
-        let v = sample_slice(&mut r, &[42, 133], 2);
-        assert!(&v[..] == [42, 133] || v[..] == [133, 42]);
-
-        // Make sure lucky 777's aren't lucky
-        let slice = &[42, 777];
-        let mut num_42 = 0;
-        let total = 1000;
-        for _ in 0..total {
-            let v = sample_slice(&mut r, slice, 1);
-            assert_eq!(v.len(), 1);
-            let v = v[0];
-            assert!(v == 42 || v == 777);
-            if v == 42 {
-                num_42 += 1;
-            }
-        }
-        let ratio_42 = num_42 as f64 / 1000 as f64;
-        assert!(0.4 <= ratio_42 || ratio_42 <= 0.6, "{}", ratio_42);
-    }
-
-    #[test]
-    #[cfg(feature = "alloc")]
-    #[allow(deprecated)]
-    fn test_sample_slice() {
-        let seeded_rng = SmallRng::from_seed;
-
-        let mut r = ::test::rng(403);
-
-        for n in 1..20 {
-            let length = 5*n - 4;   // 1, 6, ...
-            let amount = r.gen_range(0, length);
-            let mut seed = [0u8; 16];
-            r.fill(&mut seed);
-
-            // assert the basics work
-            let regular = index::sample(&mut seeded_rng(seed), length, amount);
-            assert_eq!(regular.len(), amount);
-            assert!(regular.iter().all(|e| e < length));
-
-            // also test that sampling the slice works
-            let vec: Vec<u32> = (0..(length as u32)).collect();
-            let result = sample_slice(&mut seeded_rng(seed), &vec, amount);
-            assert_eq!(result, regular.iter().map(|i| i as u32).collect::<Vec<_>>());
-
-            let result = sample_slice_ref(&mut seeded_rng(seed), &vec, amount);
-            assert!(result.iter().zip(regular.iter()).all(|(i,j)| **i == j as u32));
-        }
-    }
-    
-    #[test]
-    #[cfg(feature = "alloc")]
+    #[cfg(not(miri))] // Miri is too slow
     fn test_weighted() {
-        let mut r = ::test::rng(406);
+        let mut r = crate::test::rng(406);
         const N_REPS: u32 = 3000;
         let weights = [1u32, 2, 3, 0, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7];
         let total_weight = weights.iter().sum::<u32>() as f32;
@@ -830,7 +785,7 @@ mod test {
         assert_eq!(empty_slice.choose_weighted(&mut r, |_| 1), Err(WeightedError::NoItem));
         assert_eq!(empty_slice.choose_weighted_mut(&mut r, |_| 1), Err(WeightedError::NoItem));
         assert_eq!(['x'].choose_weighted_mut(&mut r, |_| 0), Err(WeightedError::AllWeightsZero));
-        assert_eq!([0, -1].choose_weighted_mut(&mut r, |x| *x), Err(WeightedError::NegativeWeight));
-        assert_eq!([-1, 0].choose_weighted_mut(&mut r, |x| *x), Err(WeightedError::NegativeWeight));
+        assert_eq!([0, -1].choose_weighted_mut(&mut r, |x| *x), Err(WeightedError::InvalidWeight));
+        assert_eq!([-1, 0].choose_weighted_mut(&mut r, |x| *x), Err(WeightedError::InvalidWeight));
     }
 }