src/libstd/rand/mod.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 /*!
  12
  13 Utilities for random number generation
  14
  15 The key functions are `random()` and `Rng::gen()`. These are polymorphic
  16 and so can be used to generate any type that implements `Rand`. Type inference
  17 means that often a simple call to `rand::random()` or `rng.gen()` will
  18 suffice, but sometimes an annotation is required, e.g. `rand::random::<f64>()`.
  19
  20 See the `distributions` submodule for sampling random numbers from
  21 distributions like normal and exponential.
  22
  23 # Task-local RNG
  24
  25 There is built-in support for a RNG associated with each task stored
  26 in task-local storage. This RNG can be accessed via `task_rng`, or
  27 used implicitly via `random`. This RNG is normally randomly seeded
  28 from an operating-system source of randomness, e.g. `/dev/urandom` on
  29 Unix systems, and will automatically reseed itself from this source
  30 after generating 32 KiB of random data.
  31
  32 # Cryptographic security
  33
  34 An application that requires an entropy source for cryptographic purposes
  35 must use `OsRng`, which reads randomness from the source that the operating
  36 system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on Windows).
  37 The other random number generators provided by this module are not suitable
  38 for such purposes.
  39
  40 *Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`.
  41 This module uses `/dev/urandom` for the following reasons:
  42
  43 -   On Linux, `/dev/random` may block if entropy pool is empty; `/dev/urandom` will not block.
  44     This does not mean that `/dev/random` provides better output than
  45     `/dev/urandom`; the kernel internally runs a cryptographically secure pseudorandom
  46     number generator (CSPRNG) based on entropy pool for random number generation,
  47     so the "quality" of `/dev/random` is not better than `/dev/urandom` in most cases.
  48     However, this means that `/dev/urandom` can yield somewhat predictable randomness
  49     if the entropy pool is very small, such as immediately after first booting.
  50     If an application likely to be run soon after first booting, or on a system with very
  51     few entropy sources, one should consider using `/dev/random` via `ReaderRng`.
  52 -   On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no difference
  53     between the two sources. (Also note that, on some systems e.g. FreeBSD, both `/dev/random`
  54     and `/dev/urandom` may block once if the CSPRNG has not seeded yet.)
  55
  56 # Examples
  57
  58 ```rust
  59 use std::rand;
  60 use std::rand::Rng;
  61
  62 let mut rng = rand::task_rng();
  63 if rng.gen() { // random bool
  64     println!("int: {}, uint: {}", rng.gen::<int>(), rng.gen::<uint>())
  65 }
  66 ```
  67
  68 ```rust
  69 use std::rand;
  70
  71 let tuple = rand::random::<(f64, char)>();
  72 println!("{}", tuple)
  73 ```
  74 */
  75
  76 #![experimental]
  77
  78 use cell::RefCell;
  79 use clone::Clone;
  80 use io::IoResult;
  81 use iter::Iterator;
  82 use mem;
  83 use option::{Some, None};
  84 use rc::Rc;
  85 use result::{Ok, Err};
  86 use vec::Vec;
  87
  88 #[cfg(not(target_word_size="64"))]
  89 use IsaacWordRng = core_rand::IsaacRng;
  90 #[cfg(target_word_size="64")]
  91 use IsaacWordRng = core_rand::Isaac64Rng;
  92
  93 pub use core_rand::{Rand, Rng, SeedableRng, Open01, Closed01};
  94 pub use core_rand::{XorShiftRng, IsaacRng, Isaac64Rng};
  95 pub use core_rand::{distributions, reseeding};
  96 pub use rand::os::OsRng;
  97
  98 pub mod os;
  99 pub mod reader;
 100
 101 /// The standard RNG. This is designed to be efficient on the current
 102 /// platform.
 103 pub struct StdRng { rng: IsaacWordRng }
 104
 105 impl StdRng {
 106     /// Create a randomly seeded instance of `StdRng`.
 107     ///
 108     /// This is a very expensive operation as it has to read
 109     /// randomness from the operating system and use this in an
 110     /// expensive seeding operation. If one is only generating a small
 111     /// number of random numbers, or doesn't need the utmost speed for
 112     /// generating each number, `task_rng` and/or `random` may be more
 113     /// appropriate.
 114     ///
 115     /// Reading the randomness from the OS may fail, and any error is
 116     /// propagated via the `IoResult` return value.
 117     pub fn new() -> IoResult<StdRng> {
 118         OsRng::new().map(|mut r| StdRng { rng: r.gen() })
 119     }
 120 }
 121
 122 impl Rng for StdRng {
 123     #[inline]
 124     fn next_u32(&mut self) -> u32 {
 125         self.rng.next_u32()
 126     }
 127
 128     #[inline]
 129     fn next_u64(&mut self) -> u64 {
 130         self.rng.next_u64()
 131     }
 132 }
 133
 134 impl<'a> SeedableRng<&'a [uint]> for StdRng {
 135     fn reseed(&mut self, seed: &'a [uint]) {
 136         // the internal RNG can just be seeded from the above
 137         // randomness.
 138         self.rng.reseed(unsafe {mem::transmute(seed)})
 139     }
 140
 141     fn from_seed(seed: &'a [uint]) -> StdRng {
 142         StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
 143     }
 144 }
 145
 146 /// Create a weak random number generator with a default algorithm and seed.
 147 ///
 148 /// It returns the fastest `Rng` algorithm currently available in Rust without
 149 /// consideration for cryptography or security. If you require a specifically
 150 /// seeded `Rng` for consistency over time you should pick one algorithm and
 151 /// create the `Rng` yourself.
 152 ///
 153 /// This will read randomness from the operating system to seed the
 154 /// generator.
 155 pub fn weak_rng() -> XorShiftRng {
 156     match OsRng::new() {
 157         Ok(mut r) => r.gen(),
 158         Err(e) => fail!("weak_rng: failed to create seeded RNG: {}", e)
 159     }
 160 }
 161
 162 /// Controls how the task-local RNG is reseeded.
 163 struct TaskRngReseeder;
 164
 165 impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
 166     fn reseed(&mut self, rng: &mut StdRng) {
 167         *rng = match StdRng::new() {
 168             Ok(r) => r,
 169             Err(e) => fail!("could not reseed task_rng: {}", e)
 170         }
 171     }
 172 }
 173 static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
 174 type TaskRngInner = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
 175
 176 /// The task-local RNG.
 177 pub struct TaskRng {
 178     rng: Rc<RefCell<TaskRngInner>>,
 179 }
 180
 181 /// Retrieve the lazily-initialized task-local random number
 182 /// generator, seeded by the system. Intended to be used in method
 183 /// chaining style, e.g. `task_rng().gen::<int>()`.
 184 ///
 185 /// The RNG provided will reseed itself from the operating system
 186 /// after generating a certain amount of randomness.
 187 ///
 188 /// The internal RNG used is platform and architecture dependent, even
 189 /// if the operating system random number generator is rigged to give
 190 /// the same sequence always. If absolute consistency is required,
 191 /// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
 192 pub fn task_rng() -> TaskRng {
 193     // used to make space in TLS for a random number generator
 194     local_data_key!(TASK_RNG_KEY: Rc<RefCell<TaskRngInner>>)
 195
 196     match TASK_RNG_KEY.get() {
 197         None => {
 198             let r = match StdRng::new() {
 199                 Ok(r) => r,
 200                 Err(e) => fail!("could not initialize task_rng: {}", e)
 201             };
 202             let rng = reseeding::ReseedingRng::new(r,
 203                                                    TASK_RNG_RESEED_THRESHOLD,
 204                                                    TaskRngReseeder);
 205             let rng = Rc::new(RefCell::new(rng));
 206             TASK_RNG_KEY.replace(Some(rng.clone()));
 207
 208             TaskRng { rng: rng }
 209         }
 210         Some(rng) => TaskRng { rng: rng.clone() }
 211     }
 212 }
 213
 214 impl Rng for TaskRng {
 215     fn next_u32(&mut self) -> u32 {
 216         self.rng.borrow_mut().next_u32()
 217     }
 218
 219     fn next_u64(&mut self) -> u64 {
 220         self.rng.borrow_mut().next_u64()
 221     }
 222
 223     #[inline]
 224     fn fill_bytes(&mut self, bytes: &mut [u8]) {
 225         self.rng.borrow_mut().fill_bytes(bytes)
 226     }
 227 }
 228
 229 /// Generate a random value using the task-local random number
 230 /// generator.
 231 ///
 232 /// # Example
 233 ///
 234 /// ```rust
 235 /// use std::rand::random;
 236 ///
 237 /// if random() {
 238 ///     let x = random();
 239 ///     println!("{}", 2u * x);
 240 /// } else {
 241 ///     println!("{}", random::<f64>());
 242 /// }
 243 /// ```
 244 #[inline]
 245 pub fn random<T: Rand>() -> T {
 246     task_rng().gen()
 247 }
 248
 249 /// Randomly sample up to `amount` elements from an iterator.
 250 ///
 251 /// # Example
 252 ///
 253 /// ```rust
 254 /// use std::rand::{task_rng, sample};
 255 ///
 256 /// let mut rng = task_rng();
 257 /// let sample = sample(&mut rng, range(1i, 100), 5);
 258 /// println!("{}", sample);
 259 /// ```
 260 pub fn sample<T, I: Iterator<T>, R: Rng>(rng: &mut R,
 261                                          mut iter: I,
 262                                          amount: uint) -> Vec<T> {
 263     let mut reservoir: Vec<T> = iter.by_ref().take(amount).collect();
 264     for (i, elem) in iter.enumerate() {
 265         let k = rng.gen_range(0, i + 1 + amount);
 266         if k < amount {
 267             *reservoir.get_mut(k) = elem;
 268         }
 269     }
 270     return reservoir;
 271 }
 272
 273 #[cfg(test)]
 274 mod test {
 275     use prelude::*;
 276     use super::{Rng, task_rng, random, SeedableRng, StdRng, sample};
 277     use iter::order;
 278
 279     struct ConstRng { i: u64 }
 280     impl Rng for ConstRng {
 281         fn next_u32(&mut self) -> u32 { self.i as u32 }
 282         fn next_u64(&mut self) -> u64 { self.i }
 283
 284         // no fill_bytes on purpose
 285     }
 286
 287     #[test]
 288     fn test_fill_bytes_default() {
 289         let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
 290
 291         // check every remainder mod 8, both in small and big vectors.
 292         let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
 293                        80, 81, 82, 83, 84, 85, 86, 87];
 294         for &n in lengths.iter() {
 295             let mut v = Vec::from_elem(n, 0u8);
 296             r.fill_bytes(v.as_mut_slice());
 297
 298             // use this to get nicer error messages.
 299             for (i, &byte) in v.iter().enumerate() {
 300                 if byte == 0 {
 301                     fail!("byte {} of {} is zero", i, n)
 302                 }
 303             }
 304         }
 305     }
 306
 307     #[test]
 308     fn test_gen_range() {
 309         let mut r = task_rng();
 310         for _ in range(0u, 1000) {
 311             let a = r.gen_range(-3i, 42);
 312             assert!(a >= -3 && a < 42);
 313             assert_eq!(r.gen_range(0i, 1), 0);
 314             assert_eq!(r.gen_range(-12i, -11), -12);
 315         }
 316
 317         for _ in range(0u, 1000) {
 318             let a = r.gen_range(10i, 42);
 319             assert!(a >= 10 && a < 42);
 320             assert_eq!(r.gen_range(0i, 1), 0);
 321             assert_eq!(r.gen_range(3_000_000u, 3_000_001), 3_000_000);
 322         }
 323
 324     }
 325
 326     #[test]
 327     #[should_fail]
 328     fn test_gen_range_fail_int() {
 329         let mut r = task_rng();
 330         r.gen_range(5i, -2);
 331     }
 332
 333     #[test]
 334     #[should_fail]
 335     fn test_gen_range_fail_uint() {
 336         let mut r = task_rng();
 337         r.gen_range(5u, 2u);
 338     }
 339
 340     #[test]
 341     fn test_gen_f64() {
 342         let mut r = task_rng();
 343         let a = r.gen::<f64>();
 344         let b = r.gen::<f64>();
 345         debug!("{}", (a, b));
 346     }
 347
 348     #[test]
 349     fn test_gen_weighted_bool() {
 350         let mut r = task_rng();
 351         assert_eq!(r.gen_weighted_bool(0u), true);
 352         assert_eq!(r.gen_weighted_bool(1u), true);
 353     }
 354
 355     #[test]
 356     fn test_gen_ascii_str() {
 357         let mut r = task_rng();
 358         assert_eq!(r.gen_ascii_chars().take(0).count(), 0u);
 359         assert_eq!(r.gen_ascii_chars().take(10).count(), 10u);
 360         assert_eq!(r.gen_ascii_chars().take(16).count(), 16u);
 361     }
 362
 363     #[test]
 364     fn test_gen_vec() {
 365         let mut r = task_rng();
 366         assert_eq!(r.gen_iter::<u8>().take(0).count(), 0u);
 367         assert_eq!(r.gen_iter::<u8>().take(10).count(), 10u);
 368         assert_eq!(r.gen_iter::<f64>().take(16).count(), 16u);
 369     }
 370
 371     #[test]
 372     fn test_choose() {
 373         let mut r = task_rng();
 374         assert_eq!(r.choose([1i, 1, 1]).map(|&x|x), Some(1));
 375
 376         let v: &[int] = &[];
 377         assert_eq!(r.choose(v), None);
 378     }
 379
 380     #[test]
 381     fn test_shuffle() {
 382         let mut r = task_rng();
 383         let empty: &mut [int] = &mut [];
 384         r.shuffle(empty);
 385         let mut one = [1i];
 386         r.shuffle(one);
 387         assert_eq!(one.as_slice(), &[1]);
 388
 389         let mut two = [1i, 2];
 390         r.shuffle(two);
 391         assert!(two == [1, 2] || two == [2, 1]);
 392
 393         let mut x = [1i, 1, 1];
 394         r.shuffle(x);
 395         assert_eq!(x.as_slice(), &[1, 1, 1]);
 396     }
 397
 398     #[test]
 399     fn test_task_rng() {
 400         let mut r = task_rng();
 401         r.gen::<int>();
 402         let mut v = [1i, 1, 1];
 403         r.shuffle(v);
 404         assert_eq!(v.as_slice(), &[1, 1, 1]);
 405         assert_eq!(r.gen_range(0u, 1u), 0u);
 406     }
 407
 408     #[test]
 409     fn test_random() {
 410         // not sure how to test this aside from just getting some values
 411         let _n : uint = random();
 412         let _f : f32 = random();
 413         let _o : Option<Option<i8>> = random();
 414         let _many : ((),
 415                      (uint,
 416                       int,
 417                       Option<(u32, (bool,))>),
 418                      (u8, i8, u16, i16, u32, i32, u64, i64),
 419                      (f32, (f64, (f64,)))) = random();
 420     }
 421
 422     #[test]
 423     fn test_sample() {
 424         let min_val = 1i;
 425         let max_val = 100i;
 426
 427         let mut r = task_rng();
 428         let vals = range(min_val, max_val).collect::<Vec<int>>();
 429         let small_sample = sample(&mut r, vals.iter(), 5);
 430         let large_sample = sample(&mut r, vals.iter(), vals.len() + 5);
 431
 432         assert_eq!(small_sample.len(), 5);
 433         assert_eq!(large_sample.len(), vals.len());
 434
 435         assert!(small_sample.iter().all(|e| {
 436             **e >= min_val && **e <= max_val
 437         }));
 438     }
 439
 440     #[test]
 441     fn test_std_rng_seeded() {
 442         let s = task_rng().gen_iter::<uint>().take(256).collect::<Vec<uint>>();
 443         let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
 444         let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
 445         assert!(order::equals(ra.gen_ascii_chars().take(100),
 446                               rb.gen_ascii_chars().take(100)));
 447     }
 448
 449     #[test]
 450     fn test_std_rng_reseed() {
 451         let s = task_rng().gen_iter::<uint>().take(256).collect::<Vec<uint>>();
 452         let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
 453         let string1 = r.gen_ascii_chars().take(100).collect::<String>();
 454
 455         r.reseed(s.as_slice());
 456
 457         let string2 = r.gen_ascii_chars().take(100).collect::<String>();
 458         assert_eq!(string1, string2);
 459     }
 460 }
 461
 462 #[cfg(test)]
 463 static RAND_BENCH_N: u64 = 100;
 464
 465 #[cfg(test)]
 466 mod bench {
 467     extern crate test;
 468     use prelude::*;
 469
 470     use self::test::Bencher;
 471     use super::{XorShiftRng, StdRng, IsaacRng, Isaac64Rng, Rng, RAND_BENCH_N};
 472     use super::{OsRng, weak_rng};
 473     use mem::size_of;
 474
 475     #[bench]
 476     fn rand_xorshift(b: &mut Bencher) {
 477         let mut rng: XorShiftRng = OsRng::new().unwrap().gen();
 478         b.iter(|| {
 479             for _ in range(0, RAND_BENCH_N) {
 480                 rng.gen::<uint>();
 481             }
 482         });
 483         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 484     }
 485
 486     #[bench]
 487     fn rand_isaac(b: &mut Bencher) {
 488         let mut rng: IsaacRng = OsRng::new().unwrap().gen();
 489         b.iter(|| {
 490             for _ in range(0, RAND_BENCH_N) {
 491                 rng.gen::<uint>();
 492             }
 493         });
 494         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 495     }
 496
 497     #[bench]
 498     fn rand_isaac64(b: &mut Bencher) {
 499         let mut rng: Isaac64Rng = OsRng::new().unwrap().gen();
 500         b.iter(|| {
 501             for _ in range(0, RAND_BENCH_N) {
 502                 rng.gen::<uint>();
 503             }
 504         });
 505         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 506     }
 507
 508     #[bench]
 509     fn rand_std(b: &mut Bencher) {
 510         let mut rng = StdRng::new().unwrap();
 511         b.iter(|| {
 512             for _ in range(0, RAND_BENCH_N) {
 513                 rng.gen::<uint>();
 514             }
 515         });
 516         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 517     }
 518
 519     #[bench]
 520     fn rand_shuffle_100(b: &mut Bencher) {
 521         let mut rng = weak_rng();
 522         let x : &mut[uint] = [1,..100];
 523         b.iter(|| {
 524             rng.shuffle(x);
 525         })
 526     }
 527 }