1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Interface to random number generators in Rust.
13 //! This is an experimental library which lives underneath the standard library
14 //! in its dependency chain. This library is intended to define the interface
15 //! for random number generation and also provide utilities around doing so. It
16 //! is not recommended to use this library directly, but rather the official
17 //! interface through `std::rand`.
19 #![crate_name = "rand"]
20 #![crate_type = "rlib"]
21 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
22 html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
23 html_root_url = "https://doc.rust-lang.org/nightly/",
24 html_playground_url = "https://play.rust-lang.org/",
25 test(attr(deny(warnings))))]
27 #![deny(missing_debug_implementations)]
29 #![unstable(feature = "rand",
30 reason = "use `rand` from crates.io",
32 #![feature(core_intrinsics)]
33 #![feature(staged_api)]
34 #![feature(iterator_step_by)]
35 #![feature(custom_attribute)]
36 #![feature(specialization)]
37 #![allow(unused_attributes)]
39 #![cfg_attr(not(test), feature(core_float))] // only necessary for no_std
40 #![cfg_attr(test, feature(test, rand))]
51 use core::marker::PhantomData;
53 pub use isaac::{Isaac64Rng, IsaacRng};
54 pub use chacha::ChaChaRng;
56 use distributions::{IndependentSample, Range};
57 use distributions::range::SampleRange;
60 const RAND_BENCH_N: u64 = 100;
62 pub mod distributions;
68 // Temporary trait to implement a few floating-point routines
69 // needed by librand; this is necessary because librand doesn't
70 // depend on libstd. This will go away when librand is integrated
73 trait FloatMath: Sized {
76 fn sqrt(self) -> Self;
77 fn powf(self, n: Self) -> Self;
80 impl FloatMath for f64 {
83 unsafe { intrinsics::expf64(self) }
88 unsafe { intrinsics::logf64(self) }
92 fn powf(self, n: f64) -> f64 {
93 unsafe { intrinsics::powf64(self, n) }
97 fn sqrt(self) -> f64 {
101 unsafe { intrinsics::sqrtf64(self) }
106 /// A type that can be randomly generated using an `Rng`.
108 pub trait Rand: Sized {
109 /// Generates a random instance of this type using the specified source of
111 fn rand<R: Rng>(rng: &mut R) -> Self;
114 /// A random number generator.
115 pub trait Rng: Sized {
116 /// Return the next random u32.
118 /// This rarely needs to be called directly, prefer `r.gen()` to
120 // FIXME #7771: Should be implemented in terms of next_u64
121 fn next_u32(&mut self) -> u32;
123 /// Return the next random u64.
125 /// By default this is implemented in terms of `next_u32`. An
126 /// implementation of this trait must provide at least one of
127 /// these two methods. Similarly to `next_u32`, this rarely needs
128 /// to be called directly, prefer `r.gen()` to `r.next_u64()`.
129 fn next_u64(&mut self) -> u64 {
130 ((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
133 /// Return the next random f32 selected from the half-open
134 /// interval `[0, 1)`.
136 /// By default this is implemented in terms of `next_u32`, but a
137 /// random number generator which can generate numbers satisfying
138 /// the requirements directly can overload this for performance.
139 /// It is required that the return value lies in `[0, 1)`.
141 /// See `Closed01` for the closed interval `[0,1]`, and
142 /// `Open01` for the open interval `(0,1)`.
143 fn next_f32(&mut self) -> f32 {
144 const MANTISSA_BITS: usize = 24;
145 const IGNORED_BITS: usize = 8;
146 const SCALE: f32 = (1u64 << MANTISSA_BITS) as f32;
148 // using any more than `MANTISSA_BITS` bits will
149 // cause (e.g.) 0xffff_ffff to correspond to 1
150 // exactly, so we need to drop some (8 for f32, 11
151 // for f64) to guarantee the open end.
152 (self.next_u32() >> IGNORED_BITS) as f32 / SCALE
155 /// Return the next random f64 selected from the half-open
156 /// interval `[0, 1)`.
158 /// By default this is implemented in terms of `next_u64`, but a
159 /// random number generator which can generate numbers satisfying
160 /// the requirements directly can overload this for performance.
161 /// It is required that the return value lies in `[0, 1)`.
163 /// See `Closed01` for the closed interval `[0,1]`, and
164 /// `Open01` for the open interval `(0,1)`.
165 fn next_f64(&mut self) -> f64 {
166 const MANTISSA_BITS: usize = 53;
167 const IGNORED_BITS: usize = 11;
168 const SCALE: f64 = (1u64 << MANTISSA_BITS) as f64;
170 (self.next_u64() >> IGNORED_BITS) as f64 / SCALE
173 /// Fill `dest` with random data.
175 /// This has a default implementation in terms of `next_u64` and
176 /// `next_u32`, but should be overridden by implementations that
177 /// offer a more efficient solution than just calling those
178 /// methods repeatedly.
180 /// This method does *not* have a requirement to bear any fixed
181 /// relationship to the other methods, for example, it does *not*
182 /// have to result in the same output as progressively filling
183 /// `dest` with `self.gen::<u8>()`, and any such behaviour should
184 /// not be relied upon.
186 /// This method should guarantee that `dest` is entirely filled
187 /// with new data, and may panic if this is impossible
188 /// (e.g. reading past the end of a file that is being used as the
189 /// source of randomness).
190 fn fill_bytes(&mut self, dest: &mut [u8]) {
191 // this could, in theory, be done by transmuting dest to a
192 // [u64], but this is (1) likely to be undefined behaviour for
193 // LLVM, (2) has to be very careful about alignment concerns,
194 // (3) adds more `unsafe` that needs to be checked, (4)
195 // probably doesn't give much performance gain if
196 // optimisations are on.
201 // we could micro-optimise here by generating a u32 if
202 // we only need a few more bytes to fill the vector
204 num = self.next_u64();
208 *byte = (num & 0xff) as u8;
214 /// Return a random value of a `Rand` type.
216 fn gen<T: Rand>(&mut self) -> T {
220 /// Return an iterator that will yield an infinite number of randomly
222 fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> {
225 _marker: PhantomData,
229 /// Generate a random value in the range [`low`, `high`).
231 /// This is a convenience wrapper around
232 /// `distributions::Range`. If this function will be called
233 /// repeatedly with the same arguments, one should use `Range`, as
234 /// that will amortize the computations that allow for perfect
235 /// uniformity, as they only happen on initialization.
239 /// Panics if `low >= high`.
240 fn gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T {
241 assert!(low < high, "Rng.gen_range called with low >= high");
242 Range::new(low, high).ind_sample(self)
245 /// Return a bool with a 1 in n chance of true
246 fn gen_weighted_bool(&mut self, n: usize) -> bool {
247 n <= 1 || self.gen_range(0, n) == 0
250 /// Return an iterator of random characters from the set A-Z,a-z,0-9.
251 fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> {
252 AsciiGenerator { rng: self }
255 /// Return a random element from `values`.
257 /// Return `None` if `values` is empty.
258 fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
259 if values.is_empty() {
262 Some(&values[self.gen_range(0, values.len())])
266 /// Shuffle a mutable slice in place.
267 fn shuffle<T>(&mut self, values: &mut [T]) {
268 let mut i = values.len();
270 // invariant: elements with index >= i have been locked in place.
272 // lock element i in place.
273 values.swap(i, self.gen_range(0, i + 1));
278 /// Iterator which will generate a stream of random items.
280 /// This iterator is created via the `gen_iter` method on `Rng`.
281 pub struct Generator<'a, T, R: 'a> {
283 _marker: PhantomData<T>,
286 impl<'a, T: Rand, R: Rng> Iterator for Generator<'a, T, R> {
289 fn next(&mut self) -> Option<T> {
294 impl<'a, T, R: fmt::Debug> fmt::Debug for Generator<'a, T, R> {
295 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
296 f.debug_struct("Generator")
297 .field("rng", &self.rng)
302 /// Iterator which will continuously generate random ascii characters.
304 /// This iterator is created via the `gen_ascii_chars` method on `Rng`.
305 pub struct AsciiGenerator<'a, R: 'a> {
309 impl<'a, R: Rng> Iterator for AsciiGenerator<'a, R> {
312 fn next(&mut self) -> Option<char> {
313 const GEN_ASCII_STR_CHARSET: &'static [u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
314 abcdefghijklmnopqrstuvwxyz\
316 Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char)
320 impl<'a, R: fmt::Debug> fmt::Debug for AsciiGenerator<'a, R> {
321 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
322 f.debug_struct("AsciiGenerator")
323 .field("rng", &self.rng)
328 /// A random number generator that can be explicitly seeded to produce
329 /// the same stream of randomness multiple times.
330 pub trait SeedableRng<Seed>: Rng {
331 /// Reseed an RNG with the given seed.
332 fn reseed(&mut self, _: Seed);
334 /// Create a new RNG with the given seed.
335 fn from_seed(seed: Seed) -> Self;
338 /// An Xorshift[1] random number
341 /// The Xorshift algorithm is not suitable for cryptographic purposes
342 /// but is very fast. If you do not know for sure that it fits your
343 /// requirements, use a more secure one such as `IsaacRng` or `OsRng`.
345 /// [1]: Marsaglia, George (July 2003). ["Xorshift
346 /// RNGs"](http://www.jstatsoft.org/v08/i14/paper). *Journal of
347 /// Statistical Software*. Vol. 8 (Issue 14).
348 #[derive(Clone, Debug)]
349 pub struct XorShiftRng {
357 /// Creates a new XorShiftRng instance which is not seeded.
359 /// The initial values of this RNG are constants, so all generators created
360 /// by this function will yield the same stream of random numbers. It is
361 /// highly recommended that this is created through `SeedableRng` instead of
363 pub fn new_unseeded() -> XorShiftRng {
373 impl Rng for XorShiftRng {
375 fn next_u32(&mut self) -> u32 {
377 let t = x ^ (x << 11);
382 self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
387 impl SeedableRng<[u32; 4]> for XorShiftRng {
388 /// Reseed an XorShiftRng. This will panic if `seed` is entirely 0.
389 fn reseed(&mut self, seed: [u32; 4]) {
390 assert!(!seed.iter().all(|&x| x == 0),
391 "XorShiftRng.reseed called with an all zero seed.");
399 /// Create a new XorShiftRng. This will panic if `seed` is entirely 0.
400 fn from_seed(seed: [u32; 4]) -> XorShiftRng {
401 assert!(!seed.iter().all(|&x| x == 0),
402 "XorShiftRng::from_seed called with an all zero seed.");
413 impl Rand for XorShiftRng {
414 fn rand<R: Rng>(rng: &mut R) -> XorShiftRng {
415 let mut tuple: (u32, u32, u32, u32) = rng.gen();
416 while tuple == (0, 0, 0, 0) {
419 let (x, y, z, w) = tuple;
429 /// A wrapper for generating floating point numbers uniformly in the
430 /// open interval `(0,1)` (not including either endpoint).
432 /// Use `Closed01` for the closed interval `[0,1]`, and the default
433 /// `Rand` implementation for `f32` and `f64` for the half-open
435 pub struct Open01<F>(pub F);
437 impl<F: fmt::Debug> fmt::Debug for Open01<F> {
438 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
439 f.debug_tuple("Open01")
445 /// A wrapper for generating floating point numbers uniformly in the
446 /// closed interval `[0,1]` (including both endpoints).
448 /// Use `Open01` for the closed interval `(0,1)`, and the default
449 /// `Rand` implementation of `f32` and `f64` for the half-open
451 pub struct Closed01<F>(pub F);
453 impl<F: fmt::Debug> fmt::Debug for Closed01<F> {
454 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
455 f.debug_tuple("Closed01")
463 use std::__rand as rand;
465 pub struct MyRng<R> {
469 impl<R: rand::Rng> ::Rng for MyRng<R> {
470 fn next_u32(&mut self) -> u32 {
471 rand::Rng::next_u32(&mut self.inner)
475 pub fn rng() -> MyRng<rand::ThreadRng> {
476 MyRng { inner: rand::thread_rng() }
479 pub fn weak_rng() -> MyRng<rand::ThreadRng> {
480 MyRng { inner: rand::thread_rng() }