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 /*!
  12 Utilities for random number generation
  13
  14 The key functions are `random()` and `Rng::gen()`. These are polymorphic
  15 and so can be used to generate any type that implements `Rand`. Type inference
  16 means that often a simple call to `rand::random()` or `rng.gen()` will
  17 suffice, but sometimes an annotation is required, e.g. `rand::random::<f64>()`.
  18
  19 See the `distributions` submodule for sampling random numbers from
  20 distributions like normal and exponential.
  21
  22 # Task-local RNG
  23
  24 There is built-in support for a RNG associated with each task stored
  25 in task-local storage. This RNG can be accessed via `task_rng`, or
  26 used implicitly via `random`. This RNG is normally randomly seeded
  27 from an operating-system source of randomness, e.g. `/dev/urandom` on
  28 Unix systems, and will automatically reseed itself from this source
  29 after generating 32 KiB of random data.
  30
  31 # Cryptographic security
  32
  33 An application that requires an entropy source for cryptographic purposes
  34 must use `OSRng`, which reads randomness from the source that the operating
  35 system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on Windows).
  36 The other random number generators provided by this module are not suitable
  37 for such purposes.
  38
  39 *Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`.
  40 This module uses `/dev/urandom` for the following reasons:
  41
  42 -   On Linux, `/dev/random` may block if entropy pool is empty; `/dev/urandom` will not block.
  43     This does not mean that `/dev/random` provides better output than
  44     `/dev/urandom`; the kernel internally runs a cryptographically secure pseudorandom
  45     number generator (CSPRNG) based on entropy pool for random number generation,
  46     so the "quality" of `/dev/random` is not better than `/dev/urandom` in most cases.
  47     However, this means that `/dev/urandom` can yield somewhat predictable randomness
  48     if the entropy pool is very small, such as immediately after first booting.
  49     If an application likely to be run soon after first booting, or on a system with very
  50     few entropy sources, one should consider using `/dev/random` via `ReaderRng`.
  51 -   On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no difference
  52     between the two sources. (Also note that, on some systems e.g. FreeBSD, both `/dev/random`
  53     and `/dev/urandom` may block once if the CSPRNG has not seeded yet.)
  54
  55 # Examples
  56
  57 ```rust
  58 use rand::Rng;
  59
  60 let mut rng = rand::task_rng();
  61 if rng.gen() { // bool
  62     println!("int: {}, uint: {}", rng.gen::<int>(), rng.gen::<uint>())
  63 }
  64 ```
  65
  66 ```rust
  67 let tuple_ptr = rand::random::<Box<(f64, char)>>();
  68 println!("{:?}", tuple_ptr)
  69 ```
  70 */
  71
  72 #![crate_id = "rand#0.11.0-pre"]
  73 #![license = "MIT/ASL2"]
  74 #![crate_type = "dylib"]
  75 #![crate_type = "rlib"]
  76 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
  77        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  78        html_root_url = "http://static.rust-lang.org/doc/master")]
  79
  80 #![feature(macro_rules, managed_boxes, phase)]
  81 #![deny(deprecated_owned_vector)]
  82
  83 #[cfg(test)]
  84 #[phase(syntax, link)] extern crate log;
  85
  86 use std::io::IoResult;
  87 use std::kinds::marker;
  88 use std::mem;
  89 use std::strbuf::StrBuf;
  90
  91 pub use isaac::{IsaacRng, Isaac64Rng};
  92 pub use os::OSRng;
  93
  94 use distributions::{Range, IndependentSample};
  95 use distributions::range::SampleRange;
  96
  97 pub mod distributions;
  98 pub mod isaac;
  99 pub mod os;
 100 pub mod reader;
 101 pub mod reseeding;
 102 mod rand_impls;
 103
 104 /// A type that can be randomly generated using an `Rng`.
 105 pub trait Rand {
 106     /// Generates a random instance of this type using the specified source of
 107     /// randomness.
 108     fn rand<R: Rng>(rng: &mut R) -> Self;
 109 }
 110
 111 /// A random number generator.
 112 pub trait Rng {
 113     /// Return the next random u32.
 114     ///
 115     /// This rarely needs to be called directly, prefer `r.gen()` to
 116     /// `r.next_u32()`.
 117     // FIXME #7771: Should be implemented in terms of next_u64
 118     fn next_u32(&mut self) -> u32;
 119
 120     /// Return the next random u64.
 121     ///
 122     /// By default this is implemented in terms of `next_u32`. An
 123     /// implementation of this trait must provide at least one of
 124     /// these two methods. Similarly to `next_u32`, this rarely needs
 125     /// to be called directly, prefer `r.gen()` to `r.next_u64()`.
 126     fn next_u64(&mut self) -> u64 {
 127         (self.next_u32() as u64 << 32) | (self.next_u32() as u64)
 128     }
 129
 130     /// Fill `dest` with random data.
 131     ///
 132     /// This has a default implementation in terms of `next_u64` and
 133     /// `next_u32`, but should be overridden by implementations that
 134     /// offer a more efficient solution than just calling those
 135     /// methods repeatedly.
 136     ///
 137     /// This method does *not* have a requirement to bear any fixed
 138     /// relationship to the other methods, for example, it does *not*
 139     /// have to result in the same output as progressively filling
 140     /// `dest` with `self.gen::<u8>()`, and any such behaviour should
 141     /// not be relied upon.
 142     ///
 143     /// This method should guarantee that `dest` is entirely filled
 144     /// with new data, and may fail if this is impossible
 145     /// (e.g. reading past the end of a file that is being used as the
 146     /// source of randomness).
 147     ///
 148     /// # Example
 149     ///
 150     /// ```rust
 151     /// use rand::{task_rng, Rng};
 152     ///
 153     /// let mut v = [0u8, .. 13579];
 154     /// task_rng().fill_bytes(v);
 155     /// println!("{:?}", v);
 156     /// ```
 157     fn fill_bytes(&mut self, dest: &mut [u8]) {
 158         // this could, in theory, be done by transmuting dest to a
 159         // [u64], but this is (1) likely to be undefined behaviour for
 160         // LLVM, (2) has to be very careful about alignment concerns,
 161         // (3) adds more `unsafe` that needs to be checked, (4)
 162         // probably doesn't give much performance gain if
 163         // optimisations are on.
 164         let mut count = 0;
 165         let mut num = 0;
 166         for byte in dest.mut_iter() {
 167             if count == 0 {
 168                 // we could micro-optimise here by generating a u32 if
 169                 // we only need a few more bytes to fill the vector
 170                 // (i.e. at most 4).
 171                 num = self.next_u64();
 172                 count = 8;
 173             }
 174
 175             *byte = (num & 0xff) as u8;
 176             num >>= 8;
 177             count -= 1;
 178         }
 179     }
 180
 181     /// Return a random value of a `Rand` type.
 182     ///
 183     /// # Example
 184     ///
 185     /// ```rust
 186     /// use rand::{task_rng, Rng};
 187     ///
 188     /// let mut rng = task_rng();
 189     /// let x: uint = rng.gen();
 190     /// println!("{}", x);
 191     /// println!("{:?}", rng.gen::<(f64, bool)>());
 192     /// ```
 193     #[inline(always)]
 194     fn gen<T: Rand>(&mut self) -> T {
 195         Rand::rand(self)
 196     }
 197
 198     /// Return a random vector of the specified length.
 199     ///
 200     /// # Example
 201     ///
 202     /// ```rust
 203     /// use rand::{task_rng, Rng};
 204     ///
 205     /// let mut rng = task_rng();
 206     /// let x: Vec<uint> = rng.gen_vec(10);
 207     /// println!("{}", x);
 208     /// println!("{}", rng.gen_vec::<(f64, bool)>(5));
 209     /// ```
 210     fn gen_vec<T: Rand>(&mut self, len: uint) -> Vec<T> {
 211         Vec::from_fn(len, |_| self.gen())
 212     }
 213
 214     /// Generate a random value in the range [`low`, `high`). Fails if
 215     /// `low >= high`.
 216     ///
 217     /// This is a convenience wrapper around
 218     /// `distributions::Range`. If this function will be called
 219     /// repeatedly with the same arguments, one should use `Range`, as
 220     /// that will amortize the computations that allow for perfect
 221     /// uniformity, as they only happen on initialization.
 222     ///
 223     /// # Example
 224     ///
 225     /// ```rust
 226     /// use rand::{task_rng, Rng};
 227     ///
 228     /// let mut rng = task_rng();
 229     /// let n: uint = rng.gen_range(0u, 10);
 230     /// println!("{}", n);
 231     /// let m: f64 = rng.gen_range(-40.0, 1.3e5);
 232     /// println!("{}", m);
 233     /// ```
 234     fn gen_range<T: Ord + 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 rand::{task_rng, Rng};
 245     ///
 246     /// let mut rng = task_rng();
 247     /// println!("{:b}", rng.gen_weighted_bool(3));
 248     /// ```
 249     fn gen_weighted_bool(&mut self, n: uint) -> bool {
 250         n == 0 || self.gen_range(0, n) == 0
 251     }
 252
 253     /// Return a random string of the specified length composed of
 254     /// A-Z,a-z,0-9.
 255     ///
 256     /// # Example
 257     ///
 258     /// ```rust
 259     /// use rand::{task_rng, Rng};
 260     ///
 261     /// println!("{}", task_rng().gen_ascii_str(10));
 262     /// ```
 263     fn gen_ascii_str(&mut self, len: uint) -> StrBuf {
 264         static GEN_ASCII_STR_CHARSET: &'static [u8] = bytes!("ABCDEFGHIJKLMNOPQRSTUVWXYZ\
 265                                                              abcdefghijklmnopqrstuvwxyz\
 266                                                              0123456789");
 267         let mut s = StrBuf::with_capacity(len);
 268         for _ in range(0, len) {
 269             s.push_char(*self.choose(GEN_ASCII_STR_CHARSET).unwrap() as char)
 270         }
 271         s
 272     }
 273
 274     /// Return a random element from `values`.
 275     ///
 276     /// Return `None` if `values` is empty.
 277     ///
 278     /// # Example
 279     ///
 280     /// ```
 281     /// use rand::{task_rng, Rng};
 282     ///
 283     /// let choices = [1, 2, 4, 8, 16, 32];
 284     /// let mut rng = task_rng();
 285     /// println!("{}", rng.choose(choices));
 286     /// assert_eq!(rng.choose(choices.slice_to(0)), None);
 287     /// ```
 288     fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
 289         if values.is_empty() {
 290             None
 291         } else {
 292             Some(&values[self.gen_range(0u, values.len())])
 293         }
 294     }
 295
 296     /// Deprecated name for `choose()`.
 297     #[deprecated = "replaced by .choose()"]
 298     fn choose_option<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
 299         self.choose(values)
 300     }
 301
 302     /// Shuffle a mutable slice in place.
 303     ///
 304     /// # Example
 305     ///
 306     /// ```rust
 307     /// use rand::{task_rng, Rng};
 308     ///
 309     /// let mut rng = task_rng();
 310     /// let mut y = [1,2,3];
 311     /// rng.shuffle(y);
 312     /// println!("{}", y.as_slice());
 313     /// rng.shuffle(y);
 314     /// println!("{}", y.as_slice());
 315     /// ```
 316     fn shuffle<T>(&mut self, values: &mut [T]) {
 317         let mut i = values.len();
 318         while i >= 2u {
 319             // invariant: elements with index >= i have been locked in place.
 320             i -= 1u;
 321             // lock element i in place.
 322             values.swap(i, self.gen_range(0u, i + 1u));
 323         }
 324     }
 325
 326     /// Shuffle a mutable slice in place.
 327     #[deprecated="renamed to `.shuffle`"]
 328     fn shuffle_mut<T>(&mut self, values: &mut [T]) {
 329         self.shuffle(values)
 330     }
 331
 332     /// Randomly sample up to `n` elements from an iterator.
 333     ///
 334     /// # Example
 335     ///
 336     /// ```rust
 337     /// use rand::{task_rng, Rng};
 338     ///
 339     /// let mut rng = task_rng();
 340     /// let sample = rng.sample(range(1, 100), 5);
 341     /// println!("{}", sample);
 342     /// ```
 343     fn sample<A, T: Iterator<A>>(&mut self, iter: T, n: uint) -> Vec<A> {
 344         let mut reservoir = Vec::with_capacity(n);
 345         for (i, elem) in iter.enumerate() {
 346             if i < n {
 347                 reservoir.push(elem);
 348                 continue
 349             }
 350
 351             let k = self.gen_range(0, i + 1);
 352             if k < reservoir.len() {
 353                 *reservoir.get_mut(k) = elem
 354             }
 355         }
 356         reservoir
 357     }
 358 }
 359
 360 /// A random number generator that can be explicitly seeded to produce
 361 /// the same stream of randomness multiple times.
 362 pub trait SeedableRng<Seed>: Rng {
 363     /// Reseed an RNG with the given seed.
 364     ///
 365     /// # Example
 366     ///
 367     /// ```rust
 368     /// use rand::{Rng, SeedableRng, StdRng};
 369     ///
 370     /// let mut rng: StdRng = SeedableRng::from_seed(&[1, 2, 3, 4]);
 371     /// println!("{}", rng.gen::<f64>());
 372     /// rng.reseed([5, 6, 7, 8]);
 373     /// println!("{}", rng.gen::<f64>());
 374     /// ```
 375     fn reseed(&mut self, Seed);
 376
 377     /// Create a new RNG with the given seed.
 378     ///
 379     /// # Example
 380     ///
 381     /// ```rust
 382     /// use rand::{Rng, SeedableRng, StdRng};
 383     ///
 384     /// let mut rng: StdRng = SeedableRng::from_seed(&[1, 2, 3, 4]);
 385     /// println!("{}", rng.gen::<f64>());
 386     /// ```
 387     fn from_seed(seed: Seed) -> Self;
 388 }
 389
 390 /// Create a random number generator with a default algorithm and seed.
 391 ///
 392 /// It returns the strongest `Rng` algorithm currently implemented in
 393 /// pure Rust. If you require a specifically seeded `Rng` for
 394 /// consistency over time you should pick one algorithm and create the
 395 /// `Rng` yourself.
 396 ///
 397 /// This is a very expensive operation as it has to read randomness
 398 /// from the operating system and use this in an expensive seeding
 399 /// operation. If one does not require high performance generation of
 400 /// random numbers, `task_rng` and/or `random` may be more
 401 /// appropriate.
 402 #[deprecated="use `task_rng` or `StdRng::new`"]
 403 pub fn rng() -> StdRng {
 404     StdRng::new().unwrap()
 405 }
 406
 407 /// The standard RNG. This is designed to be efficient on the current
 408 /// platform.
 409 #[cfg(not(target_word_size="64"))]
 410 pub struct StdRng { rng: IsaacRng }
 411
 412 /// The standard RNG. This is designed to be efficient on the current
 413 /// platform.
 414 #[cfg(target_word_size="64")]
 415 pub struct StdRng { rng: Isaac64Rng }
 416
 417 impl StdRng {
 418     /// Create a randomly seeded instance of `StdRng`.
 419     ///
 420     /// This is a very expensive operation as it has to read
 421     /// randomness from the operating system and use this in an
 422     /// expensive seeding operation. If one is only generating a small
 423     /// number of random numbers, or doesn't need the utmost speed for
 424     /// generating each number, `task_rng` and/or `random` may be more
 425     /// appropriate.
 426     ///
 427     /// Reading the randomness from the OS may fail, and any error is
 428     /// propagated via the `IoResult` return value.
 429     #[cfg(not(target_word_size="64"))]
 430     pub fn new() -> IoResult<StdRng> {
 431         IsaacRng::new().map(|r| StdRng { rng: r })
 432     }
 433     /// Create a randomly seeded instance of `StdRng`.
 434     ///
 435     /// This is a very expensive operation as it has to read
 436     /// randomness from the operating system and use this in an
 437     /// expensive seeding operation. If one is only generating a small
 438     /// number of random numbers, or doesn't need the utmost speed for
 439     /// generating each number, `task_rng` and/or `random` may be more
 440     /// appropriate.
 441     ///
 442     /// Reading the randomness from the OS may fail, and any error is
 443     /// propagated via the `IoResult` return value.
 444     #[cfg(target_word_size="64")]
 445     pub fn new() -> IoResult<StdRng> {
 446         Isaac64Rng::new().map(|r| StdRng { rng: r })
 447     }
 448 }
 449
 450 impl Rng for StdRng {
 451     #[inline]
 452     fn next_u32(&mut self) -> u32 {
 453         self.rng.next_u32()
 454     }
 455
 456     #[inline]
 457     fn next_u64(&mut self) -> u64 {
 458         self.rng.next_u64()
 459     }
 460 }
 461
 462 impl<'a> SeedableRng<&'a [uint]> for StdRng {
 463     fn reseed(&mut self, seed: &'a [uint]) {
 464         // the internal RNG can just be seeded from the above
 465         // randomness.
 466         self.rng.reseed(unsafe {mem::transmute(seed)})
 467     }
 468
 469     fn from_seed(seed: &'a [uint]) -> StdRng {
 470         StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
 471     }
 472 }
 473
 474 /// Create a weak random number generator with a default algorithm and seed.
 475 ///
 476 /// It returns the fastest `Rng` algorithm currently available in Rust without
 477 /// consideration for cryptography or security. If you require a specifically
 478 /// seeded `Rng` for consistency over time you should pick one algorithm and
 479 /// create the `Rng` yourself.
 480 ///
 481 /// This will read randomness from the operating system to seed the
 482 /// generator.
 483 pub fn weak_rng() -> XorShiftRng {
 484     match XorShiftRng::new() {
 485         Ok(r) => r,
 486         Err(e) => fail!("weak_rng: failed to create seeded RNG: {}", e)
 487     }
 488 }
 489
 490 /// An Xorshift[1] random number
 491 /// generator.
 492 ///
 493 /// The Xorshift algorithm is not suitable for cryptographic purposes
 494 /// but is very fast. If you do not know for sure that it fits your
 495 /// requirements, use a more secure one such as `IsaacRng` or `OSRng`.
 496 ///
 497 /// [1]: Marsaglia, George (July 2003). ["Xorshift
 498 /// RNGs"](http://www.jstatsoft.org/v08/i14/paper). *Journal of
 499 /// Statistical Software*. Vol. 8 (Issue 14).
 500 pub struct XorShiftRng {
 501     x: u32,
 502     y: u32,
 503     z: u32,
 504     w: u32,
 505 }
 506
 507 impl Rng for XorShiftRng {
 508     #[inline]
 509     fn next_u32(&mut self) -> u32 {
 510         let x = self.x;
 511         let t = x ^ (x << 11);
 512         self.x = self.y;
 513         self.y = self.z;
 514         self.z = self.w;
 515         let w = self.w;
 516         self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
 517         self.w
 518     }
 519 }
 520
 521 impl SeedableRng<[u32, .. 4]> for XorShiftRng {
 522     /// Reseed an XorShiftRng. This will fail if `seed` is entirely 0.
 523     fn reseed(&mut self, seed: [u32, .. 4]) {
 524         assert!(!seed.iter().all(|&x| x == 0),
 525                 "XorShiftRng.reseed called with an all zero seed.");
 526
 527         self.x = seed[0];
 528         self.y = seed[1];
 529         self.z = seed[2];
 530         self.w = seed[3];
 531     }
 532
 533     /// Create a new XorShiftRng. This will fail if `seed` is entirely 0.
 534     fn from_seed(seed: [u32, .. 4]) -> XorShiftRng {
 535         assert!(!seed.iter().all(|&x| x == 0),
 536                 "XorShiftRng::from_seed called with an all zero seed.");
 537
 538         XorShiftRng {
 539             x: seed[0],
 540             y: seed[1],
 541             z: seed[2],
 542             w: seed[3]
 543         }
 544     }
 545 }
 546
 547 impl XorShiftRng {
 548     /// Create an xor shift random number generator with a random seed.
 549     pub fn new() -> IoResult<XorShiftRng> {
 550         let mut s = [0u8, ..16];
 551         let mut r = try!(OSRng::new());
 552         loop {
 553             r.fill_bytes(s);
 554
 555             if !s.iter().all(|x| *x == 0) {
 556                 break;
 557             }
 558         }
 559         let s: [u32, ..4] = unsafe { mem::transmute(s) };
 560         Ok(SeedableRng::from_seed(s))
 561     }
 562 }
 563
 564 /// Controls how the task-local RNG is reseeded.
 565 struct TaskRngReseeder;
 566
 567 impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
 568     fn reseed(&mut self, rng: &mut StdRng) {
 569         *rng = match StdRng::new() {
 570             Ok(r) => r,
 571             Err(e) => fail!("could not reseed task_rng: {}", e)
 572         }
 573     }
 574 }
 575 static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
 576 type TaskRngInner = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
 577 /// The task-local RNG.
 578 pub struct TaskRng {
 579     // This points into TLS (specifically, it points to the endpoint
 580     // of a Box stored in TLS, to make it robust against TLS moving
 581     // things internally) and so this struct cannot be legally
 582     // transferred between tasks *and* it's unsafe to deallocate the
 583     // RNG other than when a task is finished.
 584     //
 585     // The use of unsafe code here is OK if the invariants above are
 586     // satisfied; and it allows us to avoid (unnecessarily) using a
 587     // GC'd or RC'd pointer.
 588     rng: *mut TaskRngInner,
 589     marker: marker::NoSend,
 590 }
 591
 592 /// Retrieve the lazily-initialized task-local random number
 593 /// generator, seeded by the system. Intended to be used in method
 594 /// chaining style, e.g. `task_rng().gen::<int>()`.
 595 ///
 596 /// The RNG provided will reseed itself from the operating system
 597 /// after generating a certain amount of randomness.
 598 ///
 599 /// The internal RNG used is platform and architecture dependent, even
 600 /// if the operating system random number generator is rigged to give
 601 /// the same sequence always. If absolute consistency is required,
 602 /// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
 603 pub fn task_rng() -> TaskRng {
 604     // used to make space in TLS for a random number generator
 605     local_data_key!(TASK_RNG_KEY: Box<TaskRngInner>)
 606
 607     match TASK_RNG_KEY.get() {
 608         None => {
 609             let r = match StdRng::new() {
 610                 Ok(r) => r,
 611                 Err(e) => fail!("could not initialize task_rng: {}", e)
 612             };
 613             let mut rng = box reseeding::ReseedingRng::new(r,
 614                                                         TASK_RNG_RESEED_THRESHOLD,
 615                                                         TaskRngReseeder);
 616             let ptr = &mut *rng as *mut TaskRngInner;
 617
 618             TASK_RNG_KEY.replace(Some(rng));
 619
 620             TaskRng { rng: ptr, marker: marker::NoSend }
 621         }
 622         Some(rng) => TaskRng {
 623             rng: &**rng as *_ as *mut TaskRngInner,
 624             marker: marker::NoSend
 625         }
 626     }
 627 }
 628
 629 impl Rng for TaskRng {
 630     fn next_u32(&mut self) -> u32 {
 631         unsafe { (*self.rng).next_u32() }
 632     }
 633
 634     fn next_u64(&mut self) -> u64 {
 635         unsafe { (*self.rng).next_u64() }
 636     }
 637
 638     #[inline]
 639     fn fill_bytes(&mut self, bytes: &mut [u8]) {
 640         unsafe { (*self.rng).fill_bytes(bytes) }
 641     }
 642 }
 643
 644 /// Generate a random value using the task-local random number
 645 /// generator.
 646 ///
 647 /// # Example
 648 ///
 649 /// ```rust
 650 /// use rand::random;
 651 ///
 652 /// if random() {
 653 ///     let x = random();
 654 ///     println!("{}", 2u * x);
 655 /// } else {
 656 ///     println!("{}", random::<f64>());
 657 /// }
 658 /// ```
 659 #[inline]
 660 pub fn random<T: Rand>() -> T {
 661     task_rng().gen()
 662 }
 663
 664 /// A wrapper for generating floating point numbers uniformly in the
 665 /// open interval `(0,1)` (not including either endpoint).
 666 ///
 667 /// Use `Closed01` for the closed interval `[0,1]`, and the default
 668 /// `Rand` implementation for `f32` and `f64` for the half-open
 669 /// `[0,1)`.
 670 ///
 671 /// # Example
 672 /// ```rust
 673 /// use rand::{random, Open01};
 674 ///
 675 /// let Open01(val) = random::<Open01<f32>>();
 676 /// println!("f32 from (0,1): {}", val);
 677 /// ```
 678 pub struct Open01<F>(pub F);
 679
 680 /// A wrapper for generating floating point numbers uniformly in the
 681 /// closed interval `[0,1]` (including both endpoints).
 682 ///
 683 /// Use `Open01` for the closed interval `(0,1)`, and the default
 684 /// `Rand` implementation of `f32` and `f64` for the half-open
 685 /// `[0,1)`.
 686 ///
 687 /// # Example
 688 /// ```rust
 689 /// use rand::{random, Closed01};
 690 ///
 691 /// let Closed01(val) = random::<Closed01<f32>>();
 692 /// println!("f32 from [0,1]: {}", val);
 693 /// ```
 694 pub struct Closed01<F>(pub F);
 695
 696 #[cfg(test)]
 697 mod test {
 698     use super::{Rng, task_rng, random, SeedableRng, StdRng};
 699
 700     struct ConstRng { i: u64 }
 701     impl Rng for ConstRng {
 702         fn next_u32(&mut self) -> u32 { self.i as u32 }
 703         fn next_u64(&mut self) -> u64 { self.i }
 704
 705         // no fill_bytes on purpose
 706     }
 707
 708     #[test]
 709     fn test_fill_bytes_default() {
 710         let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
 711
 712         // check every remainder mod 8, both in small and big vectors.
 713         let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
 714                        80, 81, 82, 83, 84, 85, 86, 87];
 715         for &n in lengths.iter() {
 716             let mut v = Vec::from_elem(n, 0u8);
 717             r.fill_bytes(v.as_mut_slice());
 718
 719             // use this to get nicer error messages.
 720             for (i, &byte) in v.iter().enumerate() {
 721                 if byte == 0 {
 722                     fail!("byte {} of {} is zero", i, n)
 723                 }
 724             }
 725         }
 726     }
 727
 728     #[test]
 729     fn test_gen_range() {
 730         let mut r = task_rng();
 731         for _ in range(0, 1000) {
 732             let a = r.gen_range(-3i, 42);
 733             assert!(a >= -3 && a < 42);
 734             assert_eq!(r.gen_range(0, 1), 0);
 735             assert_eq!(r.gen_range(-12, -11), -12);
 736         }
 737
 738         for _ in range(0, 1000) {
 739             let a = r.gen_range(10, 42);
 740             assert!(a >= 10 && a < 42);
 741             assert_eq!(r.gen_range(0, 1), 0);
 742             assert_eq!(r.gen_range(3_000_000u, 3_000_001), 3_000_000);
 743         }
 744
 745     }
 746
 747     #[test]
 748     #[should_fail]
 749     fn test_gen_range_fail_int() {
 750         let mut r = task_rng();
 751         r.gen_range(5i, -2);
 752     }
 753
 754     #[test]
 755     #[should_fail]
 756     fn test_gen_range_fail_uint() {
 757         let mut r = task_rng();
 758         r.gen_range(5u, 2u);
 759     }
 760
 761     #[test]
 762     fn test_gen_f64() {
 763         let mut r = task_rng();
 764         let a = r.gen::<f64>();
 765         let b = r.gen::<f64>();
 766         debug!("{:?}", (a, b));
 767     }
 768
 769     #[test]
 770     fn test_gen_weighted_bool() {
 771         let mut r = task_rng();
 772         assert_eq!(r.gen_weighted_bool(0u), true);
 773         assert_eq!(r.gen_weighted_bool(1u), true);
 774     }
 775
 776     #[test]
 777     fn test_gen_ascii_str() {
 778         let mut r = task_rng();
 779         debug!("{}", r.gen_ascii_str(10u));
 780         debug!("{}", r.gen_ascii_str(10u));
 781         debug!("{}", r.gen_ascii_str(10u));
 782         assert_eq!(r.gen_ascii_str(0u).len(), 0u);
 783         assert_eq!(r.gen_ascii_str(10u).len(), 10u);
 784         assert_eq!(r.gen_ascii_str(16u).len(), 16u);
 785     }
 786
 787     #[test]
 788     fn test_gen_vec() {
 789         let mut r = task_rng();
 790         assert_eq!(r.gen_vec::<u8>(0u).len(), 0u);
 791         assert_eq!(r.gen_vec::<u8>(10u).len(), 10u);
 792         assert_eq!(r.gen_vec::<f64>(16u).len(), 16u);
 793     }
 794
 795     #[test]
 796     fn test_choose() {
 797         let mut r = task_rng();
 798         assert_eq!(r.choose([1, 1, 1]).map(|&x|x), Some(1));
 799
 800         let v: &[int] = &[];
 801         assert_eq!(r.choose(v), None);
 802     }
 803
 804     #[test]
 805     fn test_shuffle() {
 806         let mut r = task_rng();
 807         let empty: &mut [int] = &mut [];
 808         r.shuffle(empty);
 809         let mut one = [1];
 810         r.shuffle(one);
 811         assert_eq!(one.as_slice(), &[1]);
 812
 813         let mut two = [1, 2];
 814         r.shuffle(two);
 815         assert!(two == [1, 2] || two == [2, 1]);
 816
 817         let mut x = [1, 1, 1];
 818         r.shuffle(x);
 819         assert_eq!(x.as_slice(), &[1, 1, 1]);
 820     }
 821
 822     #[test]
 823     fn test_task_rng() {
 824         let mut r = task_rng();
 825         r.gen::<int>();
 826         let mut v = [1, 1, 1];
 827         r.shuffle(v);
 828         assert_eq!(v.as_slice(), &[1, 1, 1]);
 829         assert_eq!(r.gen_range(0u, 1u), 0u);
 830     }
 831
 832     #[test]
 833     fn test_random() {
 834         // not sure how to test this aside from just getting some values
 835         let _n : uint = random();
 836         let _f : f32 = random();
 837         let _o : Option<Option<i8>> = random();
 838         let _many : ((),
 839                      (Box<uint>,
 840                       @int,
 841                       Box<Option<Box<(@u32, Box<(@bool,)>)>>>),
 842                      (u8, i8, u16, i16, u32, i32, u64, i64),
 843                      (f32, (f64, (f64,)))) = random();
 844     }
 845
 846     #[test]
 847     fn test_sample() {
 848         let min_val = 1;
 849         let max_val = 100;
 850
 851         let mut r = task_rng();
 852         let vals = range(min_val, max_val).collect::<Vec<int>>();
 853         let small_sample = r.sample(vals.iter(), 5);
 854         let large_sample = r.sample(vals.iter(), vals.len() + 5);
 855
 856         assert_eq!(small_sample.len(), 5);
 857         assert_eq!(large_sample.len(), vals.len());
 858
 859         assert!(small_sample.iter().all(|e| {
 860             **e >= min_val && **e <= max_val
 861         }));
 862     }
 863
 864     #[test]
 865     fn test_std_rng_seeded() {
 866         let s = task_rng().gen_vec::<uint>(256);
 867         let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
 868         let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
 869         assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
 870     }
 871
 872     #[test]
 873     fn test_std_rng_reseed() {
 874         let s = task_rng().gen_vec::<uint>(256);
 875         let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
 876         let string1 = r.gen_ascii_str(100);
 877
 878         r.reseed(s.as_slice());
 879
 880         let string2 = r.gen_ascii_str(100);
 881         assert_eq!(string1, string2);
 882     }
 883 }
 884
 885 #[cfg(test)]
 886 static RAND_BENCH_N: u64 = 100;
 887
 888 #[cfg(test)]
 889 mod bench {
 890     extern crate test;
 891     use self::test::Bencher;
 892     use {XorShiftRng, StdRng, IsaacRng, Isaac64Rng, Rng, RAND_BENCH_N};
 893     use std::mem::size_of;
 894
 895     #[bench]
 896     fn rand_xorshift(b: &mut Bencher) {
 897         let mut rng = XorShiftRng::new().unwrap();
 898         b.iter(|| {
 899             for _ in range(0, RAND_BENCH_N) {
 900                 rng.gen::<uint>();
 901             }
 902         });
 903         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 904     }
 905
 906     #[bench]
 907     fn rand_isaac(b: &mut Bencher) {
 908         let mut rng = IsaacRng::new().unwrap();
 909         b.iter(|| {
 910             for _ in range(0, RAND_BENCH_N) {
 911                 rng.gen::<uint>();
 912             }
 913         });
 914         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 915     }
 916
 917     #[bench]
 918     fn rand_isaac64(b: &mut Bencher) {
 919         let mut rng = Isaac64Rng::new().unwrap();
 920         b.iter(|| {
 921             for _ in range(0, RAND_BENCH_N) {
 922                 rng.gen::<uint>();
 923             }
 924         });
 925         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 926     }
 927
 928     #[bench]
 929     fn rand_std(b: &mut Bencher) {
 930         let mut rng = StdRng::new().unwrap();
 931         b.iter(|| {
 932             for _ in range(0, RAND_BENCH_N) {
 933                 rng.gen::<uint>();
 934             }
 935         });
 936         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 937     }
 938
 939     #[bench]
 940     fn rand_shuffle_100(b: &mut Bencher) {
 941         let mut rng = XorShiftRng::new().unwrap();
 942         let x : &mut[uint] = [1,..100];
 943         b.iter(|| {
 944             rng.shuffle(x);
 945         })
 946     }
 947 }