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