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