diff options
Diffstat (limited to 'vendor/rand/src/lib.rs')
| -rw-r--r-- | vendor/rand/src/lib.rs | 1220 |
1 files changed, 1220 insertions, 0 deletions
diff --git a/vendor/rand/src/lib.rs b/vendor/rand/src/lib.rs new file mode 100644 index 0000000..696ff6f --- /dev/null +++ b/vendor/rand/src/lib.rs @@ -0,0 +1,1220 @@ +// Copyright 2013-2017 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Utilities for random number generation +//! +//! The key functions are `random()` and `Rng::gen()`. These are polymorphic and +//! so can be used to generate any type that implements `Rand`. Type inference +//! means that often a simple call to `rand::random()` or `rng.gen()` will +//! suffice, but sometimes an annotation is required, e.g. +//! `rand::random::<f64>()`. +//! +//! See the `distributions` submodule for sampling random numbers from +//! distributions like normal and exponential. +//! +//! # Usage +//! +//! This crate is [on crates.io](https://crates.io/crates/rand) and can be +//! used by adding `rand` to the dependencies in your project's `Cargo.toml`. +//! +//! ```toml +//! [dependencies] +//! rand = "0.4" +//! ``` +//! +//! and this to your crate root: +//! +//! ```rust +//! extern crate rand; +//! ``` +//! +//! # Thread-local RNG +//! +//! There is built-in support for a RNG associated with each thread stored +//! in thread-local storage. This RNG can be accessed via `thread_rng`, or +//! used implicitly via `random`. This RNG is normally randomly seeded +//! from an operating-system source of randomness, e.g. `/dev/urandom` on +//! Unix systems, and will automatically reseed itself from this source +//! after generating 32 KiB of random data. +//! +//! # Cryptographic security +//! +//! An application that requires an entropy source for cryptographic purposes +//! must use `OsRng`, which reads randomness from the source that the operating +//! system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on +//! Windows). +//! The other random number generators provided by this module are not suitable +//! for such purposes. +//! +//! *Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`. +//! This module uses `/dev/urandom` for the following reasons: +//! +//! - On Linux, `/dev/random` may block if entropy pool is empty; +//! `/dev/urandom` will not block. This does not mean that `/dev/random` +//! provides better output than `/dev/urandom`; the kernel internally runs a +//! cryptographically secure pseudorandom number generator (CSPRNG) based on +//! entropy pool for random number generation, so the "quality" of +//! `/dev/random` is not better than `/dev/urandom` in most cases. However, +//! this means that `/dev/urandom` can yield somewhat predictable randomness +//! if the entropy pool is very small, such as immediately after first +//! booting. Linux 3.17 added the `getrandom(2)` system call which solves +//! the issue: it blocks if entropy pool is not initialized yet, but it does +//! not block once initialized. `OsRng` tries to use `getrandom(2)` if +//! available, and use `/dev/urandom` fallback if not. If an application +//! does not have `getrandom` and likely to be run soon after first booting, +//! or on a system with very few entropy sources, one should consider using +//! `/dev/random` via `ReadRng`. +//! - On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no +//! difference between the two sources. (Also note that, on some systems +//! e.g. FreeBSD, both `/dev/random` and `/dev/urandom` may block once if +//! the CSPRNG has not seeded yet.) +//! +//! # Examples +//! +//! ```rust +//! use rand::Rng; +//! +//! let mut rng = rand::thread_rng(); +//! if rng.gen() { // random bool +//! println!("i32: {}, u32: {}", rng.gen::<i32>(), rng.gen::<u32>()) +//! } +//! ``` +//! +//! ```rust +//! let tuple = rand::random::<(f64, char)>(); +//! println!("{:?}", tuple) +//! ``` +//! +//! ## Monte Carlo estimation of π +//! +//! For this example, imagine we have a square with sides of length 2 and a unit +//! circle, both centered at the origin. Since the area of a unit circle is π, +//! we have: +//! +//! ```text +//! (area of unit circle) / (area of square) = π / 4 +//! ``` +//! +//! So if we sample many points randomly from the square, roughly π / 4 of them +//! should be inside the circle. +//! +//! We can use the above fact to estimate the value of π: pick many points in +//! the square at random, calculate the fraction that fall within the circle, +//! and multiply this fraction by 4. +//! +//! ``` +//! use rand::distributions::{IndependentSample, Range}; +//! +//! fn main() { +//! let between = Range::new(-1f64, 1.); +//! let mut rng = rand::thread_rng(); +//! +//! let total = 1_000_000; +//! let mut in_circle = 0; +//! +//! for _ in 0..total { +//! let a = between.ind_sample(&mut rng); +//! let b = between.ind_sample(&mut rng); +//! if a*a + b*b <= 1. { +//! in_circle += 1; +//! } +//! } +//! +//! // prints something close to 3.14159... +//! println!("{}", 4. * (in_circle as f64) / (total as f64)); +//! } +//! ``` +//! +//! ## Monty Hall Problem +//! +//! This is a simulation of the [Monty Hall Problem][]: +//! +//! > Suppose you're on a game show, and you're given the choice of three doors: +//! > Behind one door is a car; behind the others, goats. You pick a door, say +//! > No. 1, and the host, who knows what's behind the doors, opens another +//! > door, say No. 3, which has a goat. He then says to you, "Do you want to +//! > pick door No. 2?" Is it to your advantage to switch your choice? +//! +//! The rather unintuitive answer is that you will have a 2/3 chance of winning +//! if you switch and a 1/3 chance of winning if you don't, so it's better to +//! switch. +//! +//! This program will simulate the game show and with large enough simulation +//! steps it will indeed confirm that it is better to switch. +//! +//! [Monty Hall Problem]: http://en.wikipedia.org/wiki/Monty_Hall_problem +//! +//! ``` +//! use rand::Rng; +//! use rand::distributions::{IndependentSample, Range}; +//! +//! struct SimulationResult { +//! win: bool, +//! switch: bool, +//! } +//! +//! // Run a single simulation of the Monty Hall problem. +//! fn simulate<R: Rng>(random_door: &Range<u32>, rng: &mut R) +//! -> SimulationResult { +//! let car = random_door.ind_sample(rng); +//! +//! // This is our initial choice +//! let mut choice = random_door.ind_sample(rng); +//! +//! // The game host opens a door +//! let open = game_host_open(car, choice, rng); +//! +//! // Shall we switch? +//! let switch = rng.gen(); +//! if switch { +//! choice = switch_door(choice, open); +//! } +//! +//! SimulationResult { win: choice == car, switch: switch } +//! } +//! +//! // Returns the door the game host opens given our choice and knowledge of +//! // where the car is. The game host will never open the door with the car. +//! fn game_host_open<R: Rng>(car: u32, choice: u32, rng: &mut R) -> u32 { +//! let choices = free_doors(&[car, choice]); +//! rand::seq::sample_slice(rng, &choices, 1)[0] +//! } +//! +//! // Returns the door we switch to, given our current choice and +//! // the open door. There will only be one valid door. +//! fn switch_door(choice: u32, open: u32) -> u32 { +//! free_doors(&[choice, open])[0] +//! } +//! +//! fn free_doors(blocked: &[u32]) -> Vec<u32> { +//! (0..3).filter(|x| !blocked.contains(x)).collect() +//! } +//! +//! fn main() { +//! // The estimation will be more accurate with more simulations +//! let num_simulations = 10000; +//! +//! let mut rng = rand::thread_rng(); +//! let random_door = Range::new(0, 3); +//! +//! let (mut switch_wins, mut switch_losses) = (0, 0); +//! let (mut keep_wins, mut keep_losses) = (0, 0); +//! +//! println!("Running {} simulations...", num_simulations); +//! for _ in 0..num_simulations { +//! let result = simulate(&random_door, &mut rng); +//! +//! match (result.win, result.switch) { +//! (true, true) => switch_wins += 1, +//! (true, false) => keep_wins += 1, +//! (false, true) => switch_losses += 1, +//! (false, false) => keep_losses += 1, +//! } +//! } +//! +//! let total_switches = switch_wins + switch_losses; +//! let total_keeps = keep_wins + keep_losses; +//! +//! println!("Switched door {} times with {} wins and {} losses", +//! total_switches, switch_wins, switch_losses); +//! +//! println!("Kept our choice {} times with {} wins and {} losses", +//! total_keeps, keep_wins, keep_losses); +//! +//! // With a large number of simulations, the values should converge to +//! // 0.667 and 0.333 respectively. +//! println!("Estimated chance to win if we switch: {}", +//! switch_wins as f32 / total_switches as f32); +//! println!("Estimated chance to win if we don't: {}", +//! keep_wins as f32 / total_keeps as f32); +//! } +//! ``` + +#![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png", + html_favicon_url = "https://www.rust-lang.org/favicon.ico", + html_root_url = "https://docs.rs/rand/0.4")] + +#![deny(missing_debug_implementations)] + +#![cfg_attr(not(feature="std"), no_std)] +#![cfg_attr(all(feature="alloc", not(feature="std")), feature(alloc))] +#![cfg_attr(feature = "i128_support", feature(i128_type, i128))] + +#[cfg(feature="std")] extern crate std as core; +#[cfg(all(feature = "alloc", not(feature="std")))] extern crate alloc; + +#[cfg(target_env = "sgx")] +extern crate rdrand; + +#[cfg(target_env = "sgx")] +extern crate rand_core; + +use core::marker; +use core::mem; +#[cfg(feature="std")] use std::cell::RefCell; +#[cfg(feature="std")] use std::io; +#[cfg(feature="std")] use std::rc::Rc; + +// external rngs +pub use jitter::JitterRng; +#[cfg(feature="std")] pub use os::OsRng; + +// pseudo rngs +pub use isaac::{IsaacRng, Isaac64Rng}; +pub use chacha::ChaChaRng; +pub use prng::XorShiftRng; + +// local use declarations +#[cfg(target_pointer_width = "32")] +use prng::IsaacRng as IsaacWordRng; +#[cfg(target_pointer_width = "64")] +use prng::Isaac64Rng as IsaacWordRng; + +use distributions::{Range, IndependentSample}; +use distributions::range::SampleRange; + +// public modules +pub mod distributions; +pub mod jitter; +#[cfg(feature="std")] pub mod os; +#[cfg(feature="std")] pub mod read; +pub mod reseeding; +#[cfg(any(feature="std", feature = "alloc"))] pub mod seq; + +// These tiny modules are here to avoid API breakage, probably only temporarily +pub mod chacha { + //! The ChaCha random number generator. + pub use prng::ChaChaRng; +} +pub mod isaac { + //! The ISAAC random number generator. + pub use prng::{IsaacRng, Isaac64Rng}; +} + +// private modules +mod rand_impls; +mod prng; + + +/// A type that can be randomly generated using an `Rng`. +/// +/// ## Built-in Implementations +/// +/// This crate implements `Rand` for various primitive types. Assuming the +/// provided `Rng` is well-behaved, these implementations generate values with +/// the following ranges and distributions: +/// +/// * Integers (`i32`, `u32`, `isize`, `usize`, etc.): Uniformly distributed +/// over all values of the type. +/// * `char`: Uniformly distributed over all Unicode scalar values, i.e. all +/// code points in the range `0...0x10_FFFF`, except for the range +/// `0xD800...0xDFFF` (the surrogate code points). This includes +/// unassigned/reserved code points. +/// * `bool`: Generates `false` or `true`, each with probability 0.5. +/// * Floating point types (`f32` and `f64`): Uniformly distributed in the +/// half-open range `[0, 1)`. (The [`Open01`], [`Closed01`], [`Exp1`], and +/// [`StandardNormal`] wrapper types produce floating point numbers with +/// alternative ranges or distributions.) +/// +/// [`Open01`]: struct.Open01.html +/// [`Closed01`]: struct.Closed01.html +/// [`Exp1`]: distributions/exponential/struct.Exp1.html +/// [`StandardNormal`]: distributions/normal/struct.StandardNormal.html +/// +/// The following aggregate types also implement `Rand` as long as their +/// component types implement it: +/// +/// * Tuples and arrays: Each element of the tuple or array is generated +/// independently, using its own `Rand` implementation. +/// * `Option<T>`: Returns `None` with probability 0.5; otherwise generates a +/// random `T` and returns `Some(T)`. +pub trait Rand : Sized { + /// Generates a random instance of this type using the specified source of + /// randomness. + fn rand<R: Rng>(rng: &mut R) -> Self; +} + +/// A random number generator. +pub trait Rng { + /// Return the next random u32. + /// + /// This rarely needs to be called directly, prefer `r.gen()` to + /// `r.next_u32()`. + // FIXME #rust-lang/rfcs#628: Should be implemented in terms of next_u64 + fn next_u32(&mut self) -> u32; + + /// Return the next random u64. + /// + /// By default this is implemented in terms of `next_u32`. An + /// implementation of this trait must provide at least one of + /// these two methods. Similarly to `next_u32`, this rarely needs + /// to be called directly, prefer `r.gen()` to `r.next_u64()`. + fn next_u64(&mut self) -> u64 { + ((self.next_u32() as u64) << 32) | (self.next_u32() as u64) + } + + /// Return the next random f32 selected from the half-open + /// interval `[0, 1)`. + /// + /// This uses a technique described by Saito and Matsumoto at + /// MCQMC'08. Given that the IEEE floating point numbers are + /// uniformly distributed over [1,2), we generate a number in + /// this range and then offset it onto the range [0,1). Our + /// choice of bits (masking v. shifting) is arbitrary and + /// should be immaterial for high quality generators. For low + /// quality generators (ex. LCG), prefer bitshifting due to + /// correlation between sequential low order bits. + /// + /// See: + /// A PRNG specialized in double precision floating point numbers using + /// an affine transition + /// + /// * <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/dSFMT.pdf> + /// * <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/dSFMT-slide-e.pdf> + /// + /// By default this is implemented in terms of `next_u32`, but a + /// random number generator which can generate numbers satisfying + /// the requirements directly can overload this for performance. + /// It is required that the return value lies in `[0, 1)`. + /// + /// See `Closed01` for the closed interval `[0,1]`, and + /// `Open01` for the open interval `(0,1)`. + fn next_f32(&mut self) -> f32 { + const UPPER_MASK: u32 = 0x3F800000; + const LOWER_MASK: u32 = 0x7FFFFF; + let tmp = UPPER_MASK | (self.next_u32() & LOWER_MASK); + let result: f32 = unsafe { mem::transmute(tmp) }; + result - 1.0 + } + + /// Return the next random f64 selected from the half-open + /// interval `[0, 1)`. + /// + /// By default this is implemented in terms of `next_u64`, but a + /// random number generator which can generate numbers satisfying + /// the requirements directly can overload this for performance. + /// It is required that the return value lies in `[0, 1)`. + /// + /// See `Closed01` for the closed interval `[0,1]`, and + /// `Open01` for the open interval `(0,1)`. + fn next_f64(&mut self) -> f64 { + const UPPER_MASK: u64 = 0x3FF0000000000000; + const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF; + let tmp = UPPER_MASK | (self.next_u64() & LOWER_MASK); + let result: f64 = unsafe { mem::transmute(tmp) }; + result - 1.0 + } + + /// Fill `dest` with random data. + /// + /// This has a default implementation in terms of `next_u64` and + /// `next_u32`, but should be overridden by implementations that + /// offer a more efficient solution than just calling those + /// methods repeatedly. + /// + /// This method does *not* have a requirement to bear any fixed + /// relationship to the other methods, for example, it does *not* + /// have to result in the same output as progressively filling + /// `dest` with `self.gen::<u8>()`, and any such behaviour should + /// not be relied upon. + /// + /// This method should guarantee that `dest` is entirely filled + /// with new data, and may panic if this is impossible + /// (e.g. reading past the end of a file that is being used as the + /// source of randomness). + /// + /// # Example + /// + /// ```rust + /// use rand::{thread_rng, Rng}; + /// + /// let mut v = [0u8; 13579]; + /// thread_rng().fill_bytes(&mut v); + /// println!("{:?}", &v[..]); + /// ``` + fn fill_bytes(&mut self, dest: &mut [u8]) { + // this could, in theory, be done by transmuting dest to a + // [u64], but this is (1) likely to be undefined behaviour for + // LLVM, (2) has to be very careful about alignment concerns, + // (3) adds more `unsafe` that needs to be checked, (4) + // probably doesn't give much performance gain if + // optimisations are on. + let mut count = 0; + let mut num = 0; + for byte in dest.iter_mut() { + if count == 0 { + // we could micro-optimise here by generating a u32 if + // we only need a few more bytes to fill the vector + // (i.e. at most 4). + num = self.next_u64(); + count = 8; + } + + *byte = (num & 0xff) as u8; + num >>= 8; + count -= 1; + } + } + + /// Return a random value of a `Rand` type. + /// + /// # Example + /// + /// ```rust + /// use rand::{thread_rng, Rng}; + /// + /// let mut rng = thread_rng(); + /// let x: u32 = rng.gen(); + /// println!("{}", x); + /// println!("{:?}", rng.gen::<(f64, bool)>()); + /// ``` + #[inline(always)] + fn gen<T: Rand>(&mut self) -> T where Self: Sized { + Rand::rand(self) + } + + /// Return an iterator that will yield an infinite number of randomly + /// generated items. + /// + /// # Example + /// + /// ``` + /// use rand::{thread_rng, Rng}; + /// + /// let mut rng = thread_rng(); + /// let x = rng.gen_iter::<u32>().take(10).collect::<Vec<u32>>(); + /// println!("{:?}", x); + /// println!("{:?}", rng.gen_iter::<(f64, bool)>().take(5) + /// .collect::<Vec<(f64, bool)>>()); + /// ``` + fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> where Self: Sized { + Generator { rng: self, _marker: marker::PhantomData } + } + + /// Generate a random value in the range [`low`, `high`). + /// + /// This is a convenience wrapper around + /// `distributions::Range`. If this function will be called + /// repeatedly with the same arguments, one should use `Range`, as + /// that will amortize the computations that allow for perfect + /// uniformity, as they only happen on initialization. + /// + /// # Panics + /// + /// Panics if `low >= high`. + /// + /// # Example + /// + /// ```rust + /// use rand::{thread_rng, Rng}; + /// + /// let mut rng = thread_rng(); + /// let n: u32 = rng.gen_range(0, 10); + /// println!("{}", n); + /// let m: f64 = rng.gen_range(-40.0f64, 1.3e5f64); + /// println!("{}", m); + /// ``` + fn gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T where Self: Sized { + assert!(low < high, "Rng.gen_range called with low >= high"); + Range::new(low, high).ind_sample(self) + } + + /// Return a bool with a 1 in n chance of true + /// + /// # Example + /// + /// ```rust + /// use rand::{thread_rng, Rng}; + /// + /// let mut rng = thread_rng(); + /// println!("{}", rng.gen_weighted_bool(3)); + /// ``` + fn gen_weighted_bool(&mut self, n: u32) -> bool where Self: Sized { + n <= 1 || self.gen_range(0, n) == 0 + } + + /// Return an iterator of random characters from the set A-Z,a-z,0-9. + /// + /// # Example + /// + /// ```rust + /// use rand::{thread_rng, Rng}; + /// + /// let s: String = thread_rng().gen_ascii_chars().take(10).collect(); + /// println!("{}", s); + /// ``` + fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> where Self: Sized { + AsciiGenerator { rng: self } + } + + /// Return a random element from `values`. + /// + /// Return `None` if `values` is empty. + /// + /// # Example + /// + /// ``` + /// use rand::{thread_rng, Rng}; + /// + /// let choices = [1, 2, 4, 8, 16, 32]; + /// let mut rng = thread_rng(); + /// println!("{:?}", rng.choose(&choices)); + /// assert_eq!(rng.choose(&choices[..0]), None); + /// ``` + fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> where Self: Sized { + if values.is_empty() { + None + } else { + Some(&values[self.gen_range(0, values.len())]) + } + } + + /// Return a mutable pointer to a random element from `values`. + /// + /// Return `None` if `values` is empty. + fn choose_mut<'a, T>(&mut self, values: &'a mut [T]) -> Option<&'a mut T> where Self: Sized { + if values.is_empty() { + None + } else { + let len = values.len(); + Some(&mut values[self.gen_range(0, len)]) + } + } + + /// Shuffle a mutable slice in place. + /// + /// This applies Durstenfeld's algorithm for the [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) + /// which produces an unbiased permutation. + /// + /// # Example + /// + /// ```rust + /// use rand::{thread_rng, Rng}; + /// + /// let mut rng = thread_rng(); + /// let mut y = [1, 2, 3]; + /// rng.shuffle(&mut y); + /// println!("{:?}", y); + /// rng.shuffle(&mut y); + /// println!("{:?}", y); + /// ``` + fn shuffle<T>(&mut self, values: &mut [T]) where Self: Sized { + let mut i = values.len(); + while i >= 2 { + // invariant: elements with index >= i have been locked in place. + i -= 1; + // lock element i in place. + values.swap(i, self.gen_range(0, i + 1)); + } + } +} + +impl<'a, R: ?Sized> Rng for &'a mut R where R: Rng { + fn next_u32(&mut self) -> u32 { + (**self).next_u32() + } + + fn next_u64(&mut self) -> u64 { + (**self).next_u64() + } + + fn next_f32(&mut self) -> f32 { + (**self).next_f32() + } + + fn next_f64(&mut self) -> f64 { + (**self).next_f64() + } + + fn fill_bytes(&mut self, dest: &mut [u8]) { + (**self).fill_bytes(dest) + } +} + +#[cfg(feature="std")] +impl<R: ?Sized> Rng for Box<R> where R: Rng { + fn next_u32(&mut self) -> u32 { + (**self).next_u32() + } + + fn next_u64(&mut self) -> u64 { + (**self).next_u64() + } + + fn next_f32(&mut self) -> f32 { + (**self).next_f32() + } + + fn next_f64(&mut self) -> f64 { + (**self).next_f64() + } + + fn fill_bytes(&mut self, dest: &mut [u8]) { + (**self).fill_bytes(dest) + } +} + +/// Iterator which will generate a stream of random items. +/// +/// This iterator is created via the [`gen_iter`] method on [`Rng`]. +/// +/// [`gen_iter`]: trait.Rng.html#method.gen_iter +/// [`Rng`]: trait.Rng.html +#[derive(Debug)] +pub struct Generator<'a, T, R:'a> { + rng: &'a mut R, + _marker: marker::PhantomData<fn() -> T>, +} + +impl<'a, T: Rand, R: Rng> Iterator for Generator<'a, T, R> { + type Item = T; + + fn next(&mut self) -> Option<T> { + Some(self.rng.gen()) + } +} + +/// Iterator which will continuously generate random ascii characters. +/// +/// This iterator is created via the [`gen_ascii_chars`] method on [`Rng`]. +/// +/// [`gen_ascii_chars`]: trait.Rng.html#method.gen_ascii_chars +/// [`Rng`]: trait.Rng.html +#[derive(Debug)] +pub struct AsciiGenerator<'a, R:'a> { + rng: &'a mut R, +} + +impl<'a, R: Rng> Iterator for AsciiGenerator<'a, R> { + type Item = char; + + fn next(&mut self) -> Option<char> { + const GEN_ASCII_STR_CHARSET: &'static [u8] = + b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\ + abcdefghijklmnopqrstuvwxyz\ + 0123456789"; + Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char) + } +} + +/// A random number generator that can be explicitly seeded to produce +/// the same stream of randomness multiple times. +pub trait SeedableRng<Seed>: Rng { + /// Reseed an RNG with the given seed. + /// + /// # Example + /// + /// ```rust + /// use rand::{Rng, SeedableRng, StdRng}; + /// + /// let seed: &[_] = &[1, 2, 3, 4]; + /// let mut rng: StdRng = SeedableRng::from_seed(seed); + /// println!("{}", rng.gen::<f64>()); + /// rng.reseed(&[5, 6, 7, 8]); + /// println!("{}", rng.gen::<f64>()); + /// ``` + fn reseed(&mut self, Seed); + + /// Create a new RNG with the given seed. + /// + /// # Example + /// + /// ```rust + /// use rand::{Rng, SeedableRng, StdRng}; + /// + /// let seed: &[_] = &[1, 2, 3, 4]; + /// let mut rng: StdRng = SeedableRng::from_seed(seed); + /// println!("{}", rng.gen::<f64>()); + /// ``` + fn from_seed(seed: Seed) -> Self; +} + +/// A wrapper for generating floating point numbers uniformly in the +/// open interval `(0,1)` (not including either endpoint). +/// +/// Use `Closed01` for the closed interval `[0,1]`, and the default +/// `Rand` implementation for `f32` and `f64` for the half-open +/// `[0,1)`. +/// +/// # Example +/// ```rust +/// use rand::{random, Open01}; +/// +/// let Open01(val) = random::<Open01<f32>>(); +/// println!("f32 from (0,1): {}", val); +/// ``` +#[derive(Debug)] +pub struct Open01<F>(pub F); + +/// A wrapper for generating floating point numbers uniformly in the +/// closed interval `[0,1]` (including both endpoints). +/// +/// Use `Open01` for the closed interval `(0,1)`, and the default +/// `Rand` implementation of `f32` and `f64` for the half-open +/// `[0,1)`. +/// +/// # Example +/// +/// ```rust +/// use rand::{random, Closed01}; +/// +/// let Closed01(val) = random::<Closed01<f32>>(); +/// println!("f32 from [0,1]: {}", val); +/// ``` +#[derive(Debug)] +pub struct Closed01<F>(pub F); + +/// The standard RNG. This is designed to be efficient on the current +/// platform. +#[derive(Copy, Clone, Debug)] +pub struct StdRng { + rng: IsaacWordRng, +} + +impl StdRng { + /// Create a randomly seeded instance of `StdRng`. + /// + /// This is a very expensive operation as it has to read + /// randomness from the operating system and use this in an + /// expensive seeding operation. If one is only generating a small + /// number of random numbers, or doesn't need the utmost speed for + /// generating each number, `thread_rng` and/or `random` may be more + /// appropriate. + /// + /// Reading the randomness from the OS may fail, and any error is + /// propagated via the `io::Result` return value. + #[cfg(feature="std")] + pub fn new() -> io::Result<StdRng> { + match OsRng::new() { + Ok(mut r) => Ok(StdRng { rng: r.gen() }), + Err(e1) => { + match JitterRng::new() { + Ok(mut r) => Ok(StdRng { rng: r.gen() }), + Err(_) => { + Err(e1) + } + } + } + } + } +} + +impl Rng for StdRng { + #[inline] + fn next_u32(&mut self) -> u32 { + self.rng.next_u32() + } + + #[inline] + fn next_u64(&mut self) -> u64 { + self.rng.next_u64() + } +} + +impl<'a> SeedableRng<&'a [usize]> for StdRng { + fn reseed(&mut self, seed: &'a [usize]) { + // the internal RNG can just be seeded from the above + // randomness. + self.rng.reseed(unsafe {mem::transmute(seed)}) + } + + fn from_seed(seed: &'a [usize]) -> StdRng { + StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) } + } +} + +/// Create a weak random number generator with a default algorithm and seed. +/// +/// It returns the fastest `Rng` algorithm currently available in Rust without +/// consideration for cryptography or security. If you require a specifically +/// seeded `Rng` for consistency over time you should pick one algorithm and +/// create the `Rng` yourself. +/// +/// This will seed the generator with randomness from thread_rng. +#[cfg(feature="std")] +pub fn weak_rng() -> XorShiftRng { + thread_rng().gen() +} + +/// Controls how the thread-local RNG is reseeded. +#[cfg(feature="std")] +#[derive(Debug)] +struct ThreadRngReseeder; + +#[cfg(feature="std")] +impl reseeding::Reseeder<StdRng> for ThreadRngReseeder { + fn reseed(&mut self, rng: &mut StdRng) { + match StdRng::new() { + Ok(r) => *rng = r, + Err(e) => panic!("No entropy available: {}", e), + } + } +} +#[cfg(feature="std")] +const THREAD_RNG_RESEED_THRESHOLD: u64 = 32_768; +#[cfg(feature="std")] +type ThreadRngInner = reseeding::ReseedingRng<StdRng, ThreadRngReseeder>; + +/// The thread-local RNG. +#[cfg(feature="std")] +#[derive(Clone, Debug)] +pub struct ThreadRng { + rng: Rc<RefCell<ThreadRngInner>>, +} + +/// Retrieve the lazily-initialized thread-local random number +/// generator, seeded by the system. Intended to be used in method +/// chaining style, e.g. `thread_rng().gen::<i32>()`. +/// +/// After generating a certain amount of randomness, the RNG will reseed itself +/// from the operating system or, if the operating system RNG returns an error, +/// a seed based on the current system time. +/// +/// The internal RNG used is platform and architecture dependent, even +/// if the operating system random number generator is rigged to give +/// the same sequence always. If absolute consistency is required, +/// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`. +#[cfg(feature="std")] +pub fn thread_rng() -> ThreadRng { + // used to make space in TLS for a random number generator + thread_local!(static THREAD_RNG_KEY: Rc<RefCell<ThreadRngInner>> = { + let r = match StdRng::new() { + Ok(r) => r, + Err(e) => panic!("No entropy available: {}", e), + }; + let rng = reseeding::ReseedingRng::new(r, + THREAD_RNG_RESEED_THRESHOLD, + ThreadRngReseeder); + Rc::new(RefCell::new(rng)) + }); + + ThreadRng { rng: THREAD_RNG_KEY.with(|t| t.clone()) } +} + +#[cfg(feature="std")] +impl Rng for ThreadRng { + fn next_u32(&mut self) -> u32 { + self.rng.borrow_mut().next_u32() + } + + fn next_u64(&mut self) -> u64 { + self.rng.borrow_mut().next_u64() + } + + #[inline] + fn fill_bytes(&mut self, bytes: &mut [u8]) { + self.rng.borrow_mut().fill_bytes(bytes) + } +} + +/// Generates a random value using the thread-local random number generator. +/// +/// `random()` can generate various types of random things, and so may require +/// type hinting to generate the specific type you want. +/// +/// This function uses the thread local random number generator. This means +/// that if you're calling `random()` in a loop, caching the generator can +/// increase performance. An example is shown below. +/// +/// # Examples +/// +/// ``` +/// let x = rand::random::<u8>(); +/// println!("{}", x); +/// +/// let y = rand::random::<f64>(); +/// println!("{}", y); +/// +/// if rand::random() { // generates a boolean +/// println!("Better lucky than good!"); +/// } +/// ``` +/// +/// Caching the thread local random number generator: +/// +/// ``` +/// use rand::Rng; +/// +/// let mut v = vec![1, 2, 3]; +/// +/// for x in v.iter_mut() { +/// *x = rand::random() +/// } +/// +/// // can be made faster by caching thread_rng +/// +/// let mut rng = rand::thread_rng(); +/// +/// for x in v.iter_mut() { +/// *x = rng.gen(); +/// } +/// ``` +#[cfg(feature="std")] +#[inline] +pub fn random<T: Rand>() -> T { + thread_rng().gen() +} + +/// DEPRECATED: use `seq::sample_iter` instead. +/// +/// Randomly sample up to `amount` elements from a finite iterator. +/// The order of elements in the sample is not random. +/// +/// # Example +/// +/// ```rust +/// use rand::{thread_rng, sample}; +/// +/// let mut rng = thread_rng(); +/// let sample = sample(&mut rng, 1..100, 5); +/// println!("{:?}", sample); +/// ``` +#[cfg(feature="std")] +#[inline(always)] +#[deprecated(since="0.4.0", note="renamed to seq::sample_iter")] +pub fn sample<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Vec<T> + where I: IntoIterator<Item=T>, + R: Rng, +{ + // the legacy sample didn't care whether amount was met + seq::sample_iter(rng, iterable, amount) + .unwrap_or_else(|e| e) +} + +#[cfg(test)] +mod test { + use super::{Rng, thread_rng, random, SeedableRng, StdRng, weak_rng}; + use std::iter::repeat; + + pub struct MyRng<R> { inner: R } + + impl<R: Rng> Rng for MyRng<R> { + fn next_u32(&mut self) -> u32 { + fn next<T: Rng>(t: &mut T) -> u32 { + t.next_u32() + } + next(&mut self.inner) + } + } + + pub fn rng() -> MyRng<::ThreadRng> { + MyRng { inner: ::thread_rng() } + } + + struct ConstRng { i: u64 } + impl Rng for ConstRng { + fn next_u32(&mut self) -> u32 { self.i as u32 } + fn next_u64(&mut self) -> u64 { self.i } + + // no fill_bytes on purpose + } + + pub fn iter_eq<I, J>(i: I, j: J) -> bool + where I: IntoIterator, + J: IntoIterator<Item=I::Item>, + I::Item: Eq + { + // make sure the iterators have equal length + let mut i = i.into_iter(); + let mut j = j.into_iter(); + loop { + match (i.next(), j.next()) { + (Some(ref ei), Some(ref ej)) if ei == ej => { } + (None, None) => return true, + _ => return false, + } + } + } + + #[test] + fn test_fill_bytes_default() { + let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 }; + + // check every remainder mod 8, both in small and big vectors. + let lengths = [0, 1, 2, 3, 4, 5, 6, 7, + 80, 81, 82, 83, 84, 85, 86, 87]; + for &n in lengths.iter() { + let mut v = repeat(0u8).take(n).collect::<Vec<_>>(); + r.fill_bytes(&mut v); + + // use this to get nicer error messages. + for (i, &byte) in v.iter().enumerate() { + if byte == 0 { + panic!("byte {} of {} is zero", i, n) + } + } + } + } + + #[test] + fn test_gen_range() { + let mut r = thread_rng(); + for _ in 0..1000 { + let a = r.gen_range(-3, 42); + assert!(a >= -3 && a < 42); + assert_eq!(r.gen_range(0, 1), 0); + assert_eq!(r.gen_range(-12, -11), -12); + } + + for _ in 0..1000 { + let a = r.gen_range(10, 42); + assert!(a >= 10 && a < 42); + assert_eq!(r.gen_range(0, 1), 0); + assert_eq!(r.gen_range(3_000_000, 3_000_001), 3_000_000); + } + + } + + #[test] + #[should_panic] + fn test_gen_range_panic_int() { + let mut r = thread_rng(); + r.gen_range(5, -2); + } + + #[test] + #[should_panic] + fn test_gen_range_panic_usize() { + let mut r = thread_rng(); + r.gen_range(5, 2); + } + + #[test] + fn test_gen_weighted_bool() { + let mut r = thread_rng(); + assert_eq!(r.gen_weighted_bool(0), true); + assert_eq!(r.gen_weighted_bool(1), true); + } + + #[test] + fn test_gen_ascii_str() { + let mut r = thread_rng(); + assert_eq!(r.gen_ascii_chars().take(0).count(), 0); + assert_eq!(r.gen_ascii_chars().take(10).count(), 10); + assert_eq!(r.gen_ascii_chars().take(16).count(), 16); + } + + #[test] + fn test_gen_vec() { + let mut r = thread_rng(); + assert_eq!(r.gen_iter::<u8>().take(0).count(), 0); + assert_eq!(r.gen_iter::<u8>().take(10).count(), 10); + assert_eq!(r.gen_iter::<f64>().take(16).count(), 16); + } + + #[test] + fn test_choose() { + let mut r = thread_rng(); + assert_eq!(r.choose(&[1, 1, 1]).map(|&x|x), Some(1)); + + let v: &[isize] = &[]; + assert_eq!(r.choose(v), None); + } + + #[test] + fn test_shuffle() { + let mut r = thread_rng(); + let empty: &mut [isize] = &mut []; + r.shuffle(empty); + let mut one = [1]; + r.shuffle(&mut one); + let b: &[_] = &[1]; + assert_eq!(one, b); + + let mut two = [1, 2]; + r.shuffle(&mut two); + assert!(two == [1, 2] || two == [2, 1]); + + let mut x = [1, 1, 1]; + r.shuffle(&mut x); + let b: &[_] = &[1, 1, 1]; + assert_eq!(x, b); + } + + #[test] + fn test_thread_rng() { + let mut r = thread_rng(); + r.gen::<i32>(); + let mut v = [1, 1, 1]; + r.shuffle(&mut v); + let b: &[_] = &[1, 1, 1]; + assert_eq!(v, b); + assert_eq!(r.gen_range(0, 1), 0); + } + + #[test] + fn test_rng_trait_object() { + let mut rng = thread_rng(); + { + let mut r = &mut rng as &mut Rng; + r.next_u32(); + (&mut r).gen::<i32>(); + let mut v = [1, 1, 1]; + (&mut r).shuffle(&mut v); + let b: &[_] = &[1, 1, 1]; + assert_eq!(v, b); + assert_eq!((&mut r).gen_range(0, 1), 0); + } + { + let mut r = Box::new(rng) as Box<Rng>; + r.next_u32(); + r.gen::<i32>(); + let mut v = [1, 1, 1]; + r.shuffle(&mut v); + let b: &[_] = &[1, 1, 1]; + assert_eq!(v, b); + assert_eq!(r.gen_range(0, 1), 0); + } + } + + #[test] + fn test_random() { + // not sure how to test this aside from just getting some values + let _n : usize = random(); + let _f : f32 = random(); + let _o : Option<Option<i8>> = random(); + let _many : ((), + (usize, + isize, + Option<(u32, (bool,))>), + (u8, i8, u16, i16, u32, i32, u64, i64), + (f32, (f64, (f64,)))) = random(); + } + + #[test] + fn test_std_rng_seeded() { + let s = thread_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>(); + let mut ra: StdRng = SeedableRng::from_seed(&s[..]); + let mut rb: StdRng = SeedableRng::from_seed(&s[..]); + assert!(iter_eq(ra.gen_ascii_chars().take(100), + rb.gen_ascii_chars().take(100))); + } + + #[test] + fn test_std_rng_reseed() { + let s = thread_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>(); + let mut r: StdRng = SeedableRng::from_seed(&s[..]); + let string1 = r.gen_ascii_chars().take(100).collect::<String>(); + + r.reseed(&s); + + let string2 = r.gen_ascii_chars().take(100).collect::<String>(); + assert_eq!(string1, string2); + } + + #[test] + fn test_weak_rng() { + let s = weak_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>(); + let mut ra: StdRng = SeedableRng::from_seed(&s[..]); + let mut rb: StdRng = SeedableRng::from_seed(&s[..]); + assert!(iter_eq(ra.gen_ascii_chars().take(100), + rb.gen_ascii_chars().take(100))); + } +} |