src/librand/lib.rs

   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.
   4 //
   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.
  10
  11 //! Interface to random number generators in Rust.
  12 //!
  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`.
  18
  19 // Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364)
  20 #![cfg_attr(stage0, feature(custom_attribute))]
  21 #![crate_name = "rand"]
  22 #![crate_type = "rlib"]
  23 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
  24        html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
  25        html_root_url = "http://doc.rust-lang.org/nightly/",
  26        html_playground_url = "http://play.rust-lang.org/")]
  27 #![no_std]
  28 #![staged_api]
  29 #![unstable(feature = "rand",
  30             reason = "use `rand` from crates.io")]
  31 #![feature(core_float)]
  32 #![feature(core_slice_ext)]
  33 #![feature(no_std)]
  34 #![feature(num_bits_bytes)]
  35 #![feature(staged_api)]
  36 #![feature(step_by)]
  37 #![cfg_attr(stage0, feature(core, core_prelude))]
  38
  39 #![cfg_attr(test, feature(test, rand, rustc_private, iter_order))]
  40
  41 #![allow(deprecated)]
  42
  43 #[cfg(stage0)] #[macro_use] extern crate core;
  44
  45 #[cfg(test)] #[macro_use] extern crate std;
  46 #[cfg(test)] #[macro_use] extern crate log;
  47
  48 #[cfg(stage0)]
  49 use core::prelude::v1::*;
  50
  51 use core::marker::PhantomData;
  52
  53 pub use isaac::{IsaacRng, Isaac64Rng};
  54 pub use chacha::ChaChaRng;
  55
  56 use distributions::{Range, IndependentSample};
  57 use distributions::range::SampleRange;
  58
  59 #[cfg(test)]
  60 const RAND_BENCH_N: u64 = 100;
  61
  62 pub mod distributions;
  63 pub mod isaac;
  64 pub mod chacha;
  65 pub mod reseeding;
  66 mod rand_impls;
  67
  68 /// A type that can be randomly generated using an `Rng`.
  69 #[doc(hidden)]
  70 pub trait Rand : Sized {
  71     /// Generates a random instance of this type using the specified source of
  72     /// randomness.
  73     fn rand<R: Rng>(rng: &mut R) -> Self;
  74 }
  75
  76 /// A random number generator.
  77 pub trait Rng : Sized {
  78     /// Return the next random u32.
  79     ///
  80     /// This rarely needs to be called directly, prefer `r.gen()` to
  81     /// `r.next_u32()`.
  82     // FIXME #7771: Should be implemented in terms of next_u64
  83     fn next_u32(&mut self) -> u32;
  84
  85     /// Return the next random u64.
  86     ///
  87     /// By default this is implemented in terms of `next_u32`. An
  88     /// implementation of this trait must provide at least one of
  89     /// these two methods. Similarly to `next_u32`, this rarely needs
  90     /// to be called directly, prefer `r.gen()` to `r.next_u64()`.
  91     fn next_u64(&mut self) -> u64 {
  92         ((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
  93     }
  94
  95     /// Return the next random f32 selected from the half-open
  96     /// interval `[0, 1)`.
  97     ///
  98     /// By default this is implemented in terms of `next_u32`, but a
  99     /// random number generator which can generate numbers satisfying
 100     /// the requirements directly can overload this for performance.
 101     /// It is required that the return value lies in `[0, 1)`.
 102     ///
 103     /// See `Closed01` for the closed interval `[0,1]`, and
 104     /// `Open01` for the open interval `(0,1)`.
 105     fn next_f32(&mut self) -> f32 {
 106         const MANTISSA_BITS: usize = 24;
 107         const IGNORED_BITS: usize = 8;
 108         const SCALE: f32 = (1u64 << MANTISSA_BITS) as f32;
 109
 110         // using any more than `MANTISSA_BITS` bits will
 111         // cause (e.g.) 0xffff_ffff to correspond to 1
 112         // exactly, so we need to drop some (8 for f32, 11
 113         // for f64) to guarantee the open end.
 114         (self.next_u32() >> IGNORED_BITS) as f32 / SCALE
 115     }
 116
 117     /// Return the next random f64 selected from the half-open
 118     /// interval `[0, 1)`.
 119     ///
 120     /// By default this is implemented in terms of `next_u64`, but a
 121     /// random number generator which can generate numbers satisfying
 122     /// the requirements directly can overload this for performance.
 123     /// It is required that the return value lies in `[0, 1)`.
 124     ///
 125     /// See `Closed01` for the closed interval `[0,1]`, and
 126     /// `Open01` for the open interval `(0,1)`.
 127     fn next_f64(&mut self) -> f64 {
 128         const MANTISSA_BITS: usize = 53;
 129         const IGNORED_BITS: usize = 11;
 130         const SCALE: f64 = (1u64 << MANTISSA_BITS) as f64;
 131
 132         (self.next_u64() >> IGNORED_BITS) as f64 / SCALE
 133     }
 134
 135     /// Fill `dest` with random data.
 136     ///
 137     /// This has a default implementation in terms of `next_u64` and
 138     /// `next_u32`, but should be overridden by implementations that
 139     /// offer a more efficient solution than just calling those
 140     /// methods repeatedly.
 141     ///
 142     /// This method does *not* have a requirement to bear any fixed
 143     /// relationship to the other methods, for example, it does *not*
 144     /// have to result in the same output as progressively filling
 145     /// `dest` with `self.gen::<u8>()`, and any such behaviour should
 146     /// not be relied upon.
 147     ///
 148     /// This method should guarantee that `dest` is entirely filled
 149     /// with new data, and may panic if this is impossible
 150     /// (e.g. reading past the end of a file that is being used as the
 151     /// source of randomness).
 152     fn fill_bytes(&mut self, dest: &mut [u8]) {
 153         // this could, in theory, be done by transmuting dest to a
 154         // [u64], but this is (1) likely to be undefined behaviour for
 155         // LLVM, (2) has to be very careful about alignment concerns,
 156         // (3) adds more `unsafe` that needs to be checked, (4)
 157         // probably doesn't give much performance gain if
 158         // optimisations are on.
 159         let mut count = 0;
 160         let mut num = 0;
 161         for byte in dest {
 162             if count == 0 {
 163                 // we could micro-optimise here by generating a u32 if
 164                 // we only need a few more bytes to fill the vector
 165                 // (i.e. at most 4).
 166                 num = self.next_u64();
 167                 count = 8;
 168             }
 169
 170             *byte = (num & 0xff) as u8;
 171             num >>= 8;
 172             count -= 1;
 173         }
 174     }
 175
 176     /// Return a random value of a `Rand` type.
 177     #[inline(always)]
 178     fn gen<T: Rand>(&mut self) -> T {
 179         Rand::rand(self)
 180     }
 181
 182     /// Return an iterator that will yield an infinite number of randomly
 183     /// generated items.
 184     fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> {
 185         Generator { rng: self, _marker: PhantomData }
 186     }
 187
 188     /// Generate a random value in the range [`low`, `high`).
 189     ///
 190     /// This is a convenience wrapper around
 191     /// `distributions::Range`. If this function will be called
 192     /// repeatedly with the same arguments, one should use `Range`, as
 193     /// that will amortize the computations that allow for perfect
 194     /// uniformity, as they only happen on initialization.
 195     ///
 196     /// # Panics
 197     ///
 198     /// Panics if `low >= high`.
 199     fn gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T {
 200         assert!(low < high, "Rng.gen_range called with low >= high");
 201         Range::new(low, high).ind_sample(self)
 202     }
 203
 204     /// Return a bool with a 1 in n chance of true
 205     fn gen_weighted_bool(&mut self, n: usize) -> bool {
 206         n <= 1 || self.gen_range(0, n) == 0
 207     }
 208
 209     /// Return an iterator of random characters from the set A-Z,a-z,0-9.
 210     fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> {
 211         AsciiGenerator { rng: self }
 212     }
 213
 214     /// Return a random element from `values`.
 215     ///
 216     /// Return `None` if `values` is empty.
 217     fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
 218         if values.is_empty() {
 219             None
 220         } else {
 221             Some(&values[self.gen_range(0, values.len())])
 222         }
 223     }
 224
 225     /// Shuffle a mutable slice in place.
 226     fn shuffle<T>(&mut self, values: &mut [T]) {
 227         let mut i = values.len();
 228         while i >= 2 {
 229             // invariant: elements with index >= i have been locked in place.
 230             i -= 1;
 231             // lock element i in place.
 232             values.swap(i, self.gen_range(0, i + 1));
 233         }
 234     }
 235 }
 236
 237 /// Iterator which will generate a stream of random items.
 238 ///
 239 /// This iterator is created via the `gen_iter` method on `Rng`.
 240 pub struct Generator<'a, T, R:'a> {
 241     rng: &'a mut R,
 242     _marker: PhantomData<T>
 243 }
 244
 245 impl<'a, T: Rand, R: Rng> Iterator for Generator<'a, T, R> {
 246     type Item = T;
 247
 248     fn next(&mut self) -> Option<T> {
 249         Some(self.rng.gen())
 250     }
 251 }
 252
 253 /// Iterator which will continuously generate random ascii characters.
 254 ///
 255 /// This iterator is created via the `gen_ascii_chars` method on `Rng`.
 256 pub struct AsciiGenerator<'a, R:'a> {
 257     rng: &'a mut R,
 258 }
 259
 260 impl<'a, R: Rng> Iterator for AsciiGenerator<'a, R> {
 261     type Item = char;
 262
 263     fn next(&mut self) -> Option<char> {
 264         const GEN_ASCII_STR_CHARSET: &'static [u8] =
 265             b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
 266               abcdefghijklmnopqrstuvwxyz\
 267               0123456789";
 268         Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char)
 269     }
 270 }
 271
 272 /// A random number generator that can be explicitly seeded to produce
 273 /// the same stream of randomness multiple times.
 274 pub trait SeedableRng<Seed>: Rng {
 275     /// Reseed an RNG with the given seed.
 276     fn reseed(&mut self, Seed);
 277
 278     /// Create a new RNG with the given seed.
 279     fn from_seed(seed: Seed) -> Self;
 280 }
 281
 282 /// An Xorshift[1] random number
 283 /// generator.
 284 ///
 285 /// The Xorshift algorithm is not suitable for cryptographic purposes
 286 /// but is very fast. If you do not know for sure that it fits your
 287 /// requirements, use a more secure one such as `IsaacRng` or `OsRng`.
 288 ///
 289 /// [1]: Marsaglia, George (July 2003). ["Xorshift
 290 /// RNGs"](http://www.jstatsoft.org/v08/i14/paper). *Journal of
 291 /// Statistical Software*. Vol. 8 (Issue 14).
 292 #[derive(Clone)]
 293 pub struct XorShiftRng {
 294     x: u32,
 295     y: u32,
 296     z: u32,
 297     w: u32,
 298 }
 299
 300 impl XorShiftRng {
 301     /// Creates a new XorShiftRng instance which is not seeded.
 302     ///
 303     /// The initial values of this RNG are constants, so all generators created
 304     /// by this function will yield the same stream of random numbers. It is
 305     /// highly recommended that this is created through `SeedableRng` instead of
 306     /// this function
 307     pub fn new_unseeded() -> XorShiftRng {
 308         XorShiftRng {
 309             x: 0x193a6754,
 310             y: 0xa8a7d469,
 311             z: 0x97830e05,
 312             w: 0x113ba7bb,
 313         }
 314     }
 315 }
 316
 317 impl Rng for XorShiftRng {
 318     #[inline]
 319     fn next_u32(&mut self) -> u32 {
 320         let x = self.x;
 321         let t = x ^ (x << 11);
 322         self.x = self.y;
 323         self.y = self.z;
 324         self.z = self.w;
 325         let w = self.w;
 326         self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
 327         self.w
 328     }
 329 }
 330
 331 impl SeedableRng<[u32; 4]> for XorShiftRng {
 332     /// Reseed an XorShiftRng. This will panic if `seed` is entirely 0.
 333     fn reseed(&mut self, seed: [u32; 4]) {
 334         assert!(!seed.iter().all(|&x| x == 0),
 335                 "XorShiftRng.reseed called with an all zero seed.");
 336
 337         self.x = seed[0];
 338         self.y = seed[1];
 339         self.z = seed[2];
 340         self.w = seed[3];
 341     }
 342
 343     /// Create a new XorShiftRng. This will panic if `seed` is entirely 0.
 344     fn from_seed(seed: [u32; 4]) -> XorShiftRng {
 345         assert!(!seed.iter().all(|&x| x == 0),
 346                 "XorShiftRng::from_seed called with an all zero seed.");
 347
 348         XorShiftRng {
 349             x: seed[0],
 350             y: seed[1],
 351             z: seed[2],
 352             w: seed[3]
 353         }
 354     }
 355 }
 356
 357 impl Rand for XorShiftRng {
 358     fn rand<R: Rng>(rng: &mut R) -> XorShiftRng {
 359         let mut tuple: (u32, u32, u32, u32) = rng.gen();
 360         while tuple == (0, 0, 0, 0) {
 361             tuple = rng.gen();
 362         }
 363         let (x, y, z, w) = tuple;
 364         XorShiftRng { x: x, y: y, z: z, w: w }
 365     }
 366 }
 367
 368 /// A wrapper for generating floating point numbers uniformly in the
 369 /// open interval `(0,1)` (not including either endpoint).
 370 ///
 371 /// Use `Closed01` for the closed interval `[0,1]`, and the default
 372 /// `Rand` implementation for `f32` and `f64` for the half-open
 373 /// `[0,1)`.
 374 pub struct Open01<F>(pub F);
 375
 376 /// A wrapper for generating floating point numbers uniformly in the
 377 /// closed interval `[0,1]` (including both endpoints).
 378 ///
 379 /// Use `Open01` for the closed interval `(0,1)`, and the default
 380 /// `Rand` implementation of `f32` and `f64` for the half-open
 381 /// `[0,1)`.
 382 pub struct Closed01<F>(pub F);
 383
 384 #[cfg(test)]
 385 mod test {
 386     use std::__rand as rand;
 387
 388     pub struct MyRng<R> { inner: R }
 389
 390     impl<R: rand::Rng> ::Rng for MyRng<R> {
 391         fn next_u32(&mut self) -> u32 {
 392             rand::Rng::next_u32(&mut self.inner)
 393         }
 394     }
 395
 396     pub fn rng() -> MyRng<rand::ThreadRng> {
 397         MyRng { inner: rand::thread_rng() }
 398     }
 399
 400     pub fn weak_rng() -> MyRng<rand::ThreadRng> {
 401         MyRng { inner: rand::thread_rng() }
 402     }
 403 }