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