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