src/librand/lib.rs

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