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