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