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) -> ~str {
 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) as char)
 270         }
 271         s.into_owned()
 272     }
 273
 274     /// Choose an item randomly, failing if `values` is empty.
 275     fn choose<T: Clone>(&mut self, values: &[T]) -> T {
 276         self.choose_option(values).expect("Rng.choose: `values` is empty").clone()
 277     }
 278
 279     /// Choose `Some(&item)` randomly, returning `None` if values is
 280     /// empty.
 281     ///
 282     /// # Example
 283     ///
 284     /// ```rust
 285     /// use rand::{task_rng, Rng};
 286     ///
 287     /// let choices = [1, 2, 4, 8, 16, 32];
 288     /// let mut rng = task_rng();
 289     /// println!("{:?}", rng.choose_option(choices));
 290     /// println!("{:?}", rng.choose_option(choices.slice_to(0)));
 291     /// ```
 292     fn choose_option<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
 293         if values.is_empty() {
 294             None
 295         } else {
 296             Some(&values[self.gen_range(0u, values.len())])
 297         }
 298     }
 299
 300     /// Shuffle a mutable slice in place.
 301     ///
 302     /// # Example
 303     ///
 304     /// ```rust
 305     /// use rand::{task_rng, Rng};
 306     ///
 307     /// let mut rng = task_rng();
 308     /// let mut y = [1,2,3];
 309     /// rng.shuffle(y);
 310     /// println!("{}", y.as_slice());
 311     /// rng.shuffle(y);
 312     /// println!("{}", y.as_slice());
 313     /// ```
 314     fn shuffle<T>(&mut self, values: &mut [T]) {
 315         let mut i = values.len();
 316         while i >= 2u {
 317             // invariant: elements with index >= i have been locked in place.
 318             i -= 1u;
 319             // lock element i in place.
 320             values.swap(i, self.gen_range(0u, i + 1u));
 321         }
 322     }
 323
 324     /// Shuffle a mutable slice in place.
 325     #[deprecated="renamed to `.shuffle`"]
 326     fn shuffle_mut<T>(&mut self, values: &mut [T]) {
 327         self.shuffle(values)
 328     }
 329
 330     /// Randomly sample up to `n` elements from an iterator.
 331     ///
 332     /// # Example
 333     ///
 334     /// ```rust
 335     /// use rand::{task_rng, Rng};
 336     ///
 337     /// let mut rng = task_rng();
 338     /// let sample = rng.sample(range(1, 100), 5);
 339     /// println!("{}", sample);
 340     /// ```
 341     fn sample<A, T: Iterator<A>>(&mut self, iter: T, n: uint) -> Vec<A> {
 342         let mut reservoir = Vec::with_capacity(n);
 343         for (i, elem) in iter.enumerate() {
 344             if i < n {
 345                 reservoir.push(elem);
 346                 continue
 347             }
 348
 349             let k = self.gen_range(0, i + 1);
 350             if k < reservoir.len() {
 351                 *reservoir.get_mut(k) = elem
 352             }
 353         }
 354         reservoir
 355     }
 356 }
 357
 358 /// A random number generator that can be explicitly seeded to produce
 359 /// the same stream of randomness multiple times.
 360 pub trait SeedableRng<Seed>: Rng {
 361     /// Reseed an RNG with the given seed.
 362     ///
 363     /// # Example
 364     ///
 365     /// ```rust
 366     /// use rand::{Rng, SeedableRng, StdRng};
 367     ///
 368     /// let mut rng: StdRng = SeedableRng::from_seed(&[1, 2, 3, 4]);
 369     /// println!("{}", rng.gen::<f64>());
 370     /// rng.reseed([5, 6, 7, 8]);
 371     /// println!("{}", rng.gen::<f64>());
 372     /// ```
 373     fn reseed(&mut self, Seed);
 374
 375     /// Create a new RNG with the given seed.
 376     ///
 377     /// # Example
 378     ///
 379     /// ```rust
 380     /// use rand::{Rng, SeedableRng, StdRng};
 381     ///
 382     /// let mut rng: StdRng = SeedableRng::from_seed(&[1, 2, 3, 4]);
 383     /// println!("{}", rng.gen::<f64>());
 384     /// ```
 385     fn from_seed(seed: Seed) -> Self;
 386 }
 387
 388 /// Create a random number generator with a default algorithm and seed.
 389 ///
 390 /// It returns the strongest `Rng` algorithm currently implemented in
 391 /// pure Rust. If you require a specifically seeded `Rng` for
 392 /// consistency over time you should pick one algorithm and create the
 393 /// `Rng` yourself.
 394 ///
 395 /// This is a very expensive operation as it has to read randomness
 396 /// from the operating system and use this in an expensive seeding
 397 /// operation. If one does not require high performance generation of
 398 /// random numbers, `task_rng` and/or `random` may be more
 399 /// appropriate.
 400 #[deprecated="use `task_rng` or `StdRng::new`"]
 401 pub fn rng() -> StdRng {
 402     StdRng::new().unwrap()
 403 }
 404
 405 /// The standard RNG. This is designed to be efficient on the current
 406 /// platform.
 407 #[cfg(not(target_word_size="64"))]
 408 pub struct StdRng { rng: IsaacRng }
 409
 410 /// The standard RNG. This is designed to be efficient on the current
 411 /// platform.
 412 #[cfg(target_word_size="64")]
 413 pub struct StdRng { rng: Isaac64Rng }
 414
 415 impl StdRng {
 416     /// Create a randomly seeded instance of `StdRng`.
 417     ///
 418     /// This is a very expensive operation as it has to read
 419     /// randomness from the operating system and use this in an
 420     /// expensive seeding operation. If one is only generating a small
 421     /// number of random numbers, or doesn't need the utmost speed for
 422     /// generating each number, `task_rng` and/or `random` may be more
 423     /// appropriate.
 424     ///
 425     /// Reading the randomness from the OS may fail, and any error is
 426     /// propagated via the `IoResult` return value.
 427     #[cfg(not(target_word_size="64"))]
 428     pub fn new() -> IoResult<StdRng> {
 429         IsaacRng::new().map(|r| StdRng { rng: r })
 430     }
 431     /// Create a randomly seeded instance of `StdRng`.
 432     ///
 433     /// This is a very expensive operation as it has to read
 434     /// randomness from the operating system and use this in an
 435     /// expensive seeding operation. If one is only generating a small
 436     /// number of random numbers, or doesn't need the utmost speed for
 437     /// generating each number, `task_rng` and/or `random` may be more
 438     /// appropriate.
 439     ///
 440     /// Reading the randomness from the OS may fail, and any error is
 441     /// propagated via the `IoResult` return value.
 442     #[cfg(target_word_size="64")]
 443     pub fn new() -> IoResult<StdRng> {
 444         Isaac64Rng::new().map(|r| StdRng { rng: r })
 445     }
 446 }
 447
 448 impl Rng for StdRng {
 449     #[inline]
 450     fn next_u32(&mut self) -> u32 {
 451         self.rng.next_u32()
 452     }
 453
 454     #[inline]
 455     fn next_u64(&mut self) -> u64 {
 456         self.rng.next_u64()
 457     }
 458 }
 459
 460 impl<'a> SeedableRng<&'a [uint]> for StdRng {
 461     fn reseed(&mut self, seed: &'a [uint]) {
 462         // the internal RNG can just be seeded from the above
 463         // randomness.
 464         self.rng.reseed(unsafe {mem::transmute(seed)})
 465     }
 466
 467     fn from_seed(seed: &'a [uint]) -> StdRng {
 468         StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
 469     }
 470 }
 471
 472 /// Create a weak random number generator with a default algorithm and seed.
 473 ///
 474 /// It returns the fastest `Rng` algorithm currently available in Rust without
 475 /// consideration for cryptography or security. If you require a specifically
 476 /// seeded `Rng` for consistency over time you should pick one algorithm and
 477 /// create the `Rng` yourself.
 478 ///
 479 /// This will read randomness from the operating system to seed the
 480 /// generator.
 481 pub fn weak_rng() -> XorShiftRng {
 482     match XorShiftRng::new() {
 483         Ok(r) => r,
 484         Err(e) => fail!("weak_rng: failed to create seeded RNG: {}", e)
 485     }
 486 }
 487
 488 /// An Xorshift[1] random number
 489 /// generator.
 490 ///
 491 /// The Xorshift algorithm is not suitable for cryptographic purposes
 492 /// but is very fast. If you do not know for sure that it fits your
 493 /// requirements, use a more secure one such as `IsaacRng` or `OSRng`.
 494 ///
 495 /// [1]: Marsaglia, George (July 2003). ["Xorshift
 496 /// RNGs"](http://www.jstatsoft.org/v08/i14/paper). *Journal of
 497 /// Statistical Software*. Vol. 8 (Issue 14).
 498 pub struct XorShiftRng {
 499     x: u32,
 500     y: u32,
 501     z: u32,
 502     w: u32,
 503 }
 504
 505 impl Rng for XorShiftRng {
 506     #[inline]
 507     fn next_u32(&mut self) -> u32 {
 508         let x = self.x;
 509         let t = x ^ (x << 11);
 510         self.x = self.y;
 511         self.y = self.z;
 512         self.z = self.w;
 513         let w = self.w;
 514         self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
 515         self.w
 516     }
 517 }
 518
 519 impl SeedableRng<[u32, .. 4]> for XorShiftRng {
 520     /// Reseed an XorShiftRng. This will fail if `seed` is entirely 0.
 521     fn reseed(&mut self, seed: [u32, .. 4]) {
 522         assert!(!seed.iter().all(|&x| x == 0),
 523                 "XorShiftRng.reseed called with an all zero seed.");
 524
 525         self.x = seed[0];
 526         self.y = seed[1];
 527         self.z = seed[2];
 528         self.w = seed[3];
 529     }
 530
 531     /// Create a new XorShiftRng. This will fail if `seed` is entirely 0.
 532     fn from_seed(seed: [u32, .. 4]) -> XorShiftRng {
 533         assert!(!seed.iter().all(|&x| x == 0),
 534                 "XorShiftRng::from_seed called with an all zero seed.");
 535
 536         XorShiftRng {
 537             x: seed[0],
 538             y: seed[1],
 539             z: seed[2],
 540             w: seed[3]
 541         }
 542     }
 543 }
 544
 545 impl XorShiftRng {
 546     /// Create an xor shift random number generator with a random seed.
 547     pub fn new() -> IoResult<XorShiftRng> {
 548         let mut s = [0u8, ..16];
 549         let mut r = try!(OSRng::new());
 550         loop {
 551             r.fill_bytes(s);
 552
 553             if !s.iter().all(|x| *x == 0) {
 554                 break;
 555             }
 556         }
 557         let s: [u32, ..4] = unsafe { mem::transmute(s) };
 558         Ok(SeedableRng::from_seed(s))
 559     }
 560 }
 561
 562 /// Controls how the task-local RNG is reseeded.
 563 struct TaskRngReseeder;
 564
 565 impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
 566     fn reseed(&mut self, rng: &mut StdRng) {
 567         *rng = match StdRng::new() {
 568             Ok(r) => r,
 569             Err(e) => fail!("could not reseed task_rng: {}", e)
 570         }
 571     }
 572 }
 573 static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
 574 type TaskRngInner = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
 575 /// The task-local RNG.
 576 pub struct TaskRng {
 577     // This points into TLS (specifically, it points to the endpoint
 578     // of a Box stored in TLS, to make it robust against TLS moving
 579     // things internally) and so this struct cannot be legally
 580     // transferred between tasks *and* it's unsafe to deallocate the
 581     // RNG other than when a task is finished.
 582     //
 583     // The use of unsafe code here is OK if the invariants above are
 584     // satisfied; and it allows us to avoid (unnecessarily) using a
 585     // GC'd or RC'd pointer.
 586     rng: *mut TaskRngInner,
 587     marker: marker::NoSend,
 588 }
 589
 590 /// Retrieve the lazily-initialized task-local random number
 591 /// generator, seeded by the system. Intended to be used in method
 592 /// chaining style, e.g. `task_rng().gen::<int>()`.
 593 ///
 594 /// The RNG provided will reseed itself from the operating system
 595 /// after generating a certain amount of randomness.
 596 ///
 597 /// The internal RNG used is platform and architecture dependent, even
 598 /// if the operating system random number generator is rigged to give
 599 /// the same sequence always. If absolute consistency is required,
 600 /// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
 601 pub fn task_rng() -> TaskRng {
 602     // used to make space in TLS for a random number generator
 603     local_data_key!(TASK_RNG_KEY: Box<TaskRngInner>)
 604
 605     match TASK_RNG_KEY.get() {
 606         None => {
 607             let r = match StdRng::new() {
 608                 Ok(r) => r,
 609                 Err(e) => fail!("could not initialize task_rng: {}", e)
 610             };
 611             let mut rng = box reseeding::ReseedingRng::new(r,
 612                                                         TASK_RNG_RESEED_THRESHOLD,
 613                                                         TaskRngReseeder);
 614             let ptr = &mut *rng as *mut TaskRngInner;
 615
 616             TASK_RNG_KEY.replace(Some(rng));
 617
 618             TaskRng { rng: ptr, marker: marker::NoSend }
 619         }
 620         Some(rng) => TaskRng {
 621             rng: &**rng as *_ as *mut TaskRngInner,
 622             marker: marker::NoSend
 623         }
 624     }
 625 }
 626
 627 impl Rng for TaskRng {
 628     fn next_u32(&mut self) -> u32 {
 629         unsafe { (*self.rng).next_u32() }
 630     }
 631
 632     fn next_u64(&mut self) -> u64 {
 633         unsafe { (*self.rng).next_u64() }
 634     }
 635
 636     #[inline]
 637     fn fill_bytes(&mut self, bytes: &mut [u8]) {
 638         unsafe { (*self.rng).fill_bytes(bytes) }
 639     }
 640 }
 641
 642 /// Generate a random value using the task-local random number
 643 /// generator.
 644 ///
 645 /// # Example
 646 ///
 647 /// ```rust
 648 /// use rand::random;
 649 ///
 650 /// if random() {
 651 ///     let x = random();
 652 ///     println!("{}", 2u * x);
 653 /// } else {
 654 ///     println!("{}", random::<f64>());
 655 /// }
 656 /// ```
 657 #[inline]
 658 pub fn random<T: Rand>() -> T {
 659     task_rng().gen()
 660 }
 661
 662 /// A wrapper for generating floating point numbers uniformly in the
 663 /// open interval `(0,1)` (not including either endpoint).
 664 ///
 665 /// Use `Closed01` for the closed interval `[0,1]`, and the default
 666 /// `Rand` implementation for `f32` and `f64` for the half-open
 667 /// `[0,1)`.
 668 ///
 669 /// # Example
 670 /// ```rust
 671 /// use rand::{random, Open01};
 672 ///
 673 /// let Open01(val) = random::<Open01<f32>>();
 674 /// println!("f32 from (0,1): {}", val);
 675 /// ```
 676 pub struct Open01<F>(pub F);
 677
 678 /// A wrapper for generating floating point numbers uniformly in the
 679 /// closed interval `[0,1]` (including both endpoints).
 680 ///
 681 /// Use `Open01` for the closed interval `(0,1)`, and the default
 682 /// `Rand` implementation of `f32` and `f64` for the half-open
 683 /// `[0,1)`.
 684 ///
 685 /// # Example
 686 /// ```rust
 687 /// use rand::{random, Closed01};
 688 ///
 689 /// let Closed01(val) = random::<Closed01<f32>>();
 690 /// println!("f32 from [0,1]: {}", val);
 691 /// ```
 692 pub struct Closed01<F>(pub F);
 693
 694 #[cfg(test)]
 695 mod test {
 696     use super::{Rng, task_rng, random, SeedableRng, StdRng};
 697
 698     struct ConstRng { i: u64 }
 699     impl Rng for ConstRng {
 700         fn next_u32(&mut self) -> u32 { self.i as u32 }
 701         fn next_u64(&mut self) -> u64 { self.i }
 702
 703         // no fill_bytes on purpose
 704     }
 705
 706     #[test]
 707     fn test_fill_bytes_default() {
 708         let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
 709
 710         // check every remainder mod 8, both in small and big vectors.
 711         let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
 712                        80, 81, 82, 83, 84, 85, 86, 87];
 713         for &n in lengths.iter() {
 714             let mut v = Vec::from_elem(n, 0u8);
 715             r.fill_bytes(v.as_mut_slice());
 716
 717             // use this to get nicer error messages.
 718             for (i, &byte) in v.iter().enumerate() {
 719                 if byte == 0 {
 720                     fail!("byte {} of {} is zero", i, n)
 721                 }
 722             }
 723         }
 724     }
 725
 726     #[test]
 727     fn test_gen_range() {
 728         let mut r = task_rng();
 729         for _ in range(0, 1000) {
 730             let a = r.gen_range(-3i, 42);
 731             assert!(a >= -3 && a < 42);
 732             assert_eq!(r.gen_range(0, 1), 0);
 733             assert_eq!(r.gen_range(-12, -11), -12);
 734         }
 735
 736         for _ in range(0, 1000) {
 737             let a = r.gen_range(10, 42);
 738             assert!(a >= 10 && a < 42);
 739             assert_eq!(r.gen_range(0, 1), 0);
 740             assert_eq!(r.gen_range(3_000_000u, 3_000_001), 3_000_000);
 741         }
 742
 743     }
 744
 745     #[test]
 746     #[should_fail]
 747     fn test_gen_range_fail_int() {
 748         let mut r = task_rng();
 749         r.gen_range(5i, -2);
 750     }
 751
 752     #[test]
 753     #[should_fail]
 754     fn test_gen_range_fail_uint() {
 755         let mut r = task_rng();
 756         r.gen_range(5u, 2u);
 757     }
 758
 759     #[test]
 760     fn test_gen_f64() {
 761         let mut r = task_rng();
 762         let a = r.gen::<f64>();
 763         let b = r.gen::<f64>();
 764         debug!("{:?}", (a, b));
 765     }
 766
 767     #[test]
 768     fn test_gen_weighted_bool() {
 769         let mut r = task_rng();
 770         assert_eq!(r.gen_weighted_bool(0u), true);
 771         assert_eq!(r.gen_weighted_bool(1u), true);
 772     }
 773
 774     #[test]
 775     fn test_gen_ascii_str() {
 776         let mut r = task_rng();
 777         debug!("{}", r.gen_ascii_str(10u));
 778         debug!("{}", r.gen_ascii_str(10u));
 779         debug!("{}", r.gen_ascii_str(10u));
 780         assert_eq!(r.gen_ascii_str(0u).len(), 0u);
 781         assert_eq!(r.gen_ascii_str(10u).len(), 10u);
 782         assert_eq!(r.gen_ascii_str(16u).len(), 16u);
 783     }
 784
 785     #[test]
 786     fn test_gen_vec() {
 787         let mut r = task_rng();
 788         assert_eq!(r.gen_vec::<u8>(0u).len(), 0u);
 789         assert_eq!(r.gen_vec::<u8>(10u).len(), 10u);
 790         assert_eq!(r.gen_vec::<f64>(16u).len(), 16u);
 791     }
 792
 793     #[test]
 794     fn test_choose() {
 795         let mut r = task_rng();
 796         assert_eq!(r.choose([1, 1, 1]), 1);
 797     }
 798
 799     #[test]
 800     fn test_choose_option() {
 801         let mut r = task_rng();
 802         let v: &[int] = &[];
 803         assert!(r.choose_option(v).is_none());
 804
 805         let i = 1;
 806         let v = [1,1,1];
 807         assert_eq!(r.choose_option(v), Some(&i));
 808     }
 809
 810     #[test]
 811     fn test_shuffle() {
 812         let mut r = task_rng();
 813         let empty: &mut [int] = &mut [];
 814         r.shuffle(empty);
 815         let mut one = [1];
 816         r.shuffle(one);
 817         assert_eq!(one.as_slice(), &[1]);
 818
 819         let mut two = [1, 2];
 820         r.shuffle(two);
 821         assert!(two == [1, 2] || two == [2, 1]);
 822
 823         let mut x = [1, 1, 1];
 824         r.shuffle(x);
 825         assert_eq!(x.as_slice(), &[1, 1, 1]);
 826     }
 827
 828     #[test]
 829     fn test_task_rng() {
 830         let mut r = task_rng();
 831         r.gen::<int>();
 832         let mut v = [1, 1, 1];
 833         r.shuffle(v);
 834         assert_eq!(v.as_slice(), &[1, 1, 1]);
 835         assert_eq!(r.gen_range(0u, 1u), 0u);
 836     }
 837
 838     #[test]
 839     fn test_random() {
 840         // not sure how to test this aside from just getting some values
 841         let _n : uint = random();
 842         let _f : f32 = random();
 843         let _o : Option<Option<i8>> = random();
 844         let _many : ((),
 845                      (Box<uint>,
 846                       @int,
 847                       Box<Option<Box<(@u32, Box<(@bool,)>)>>>),
 848                      (u8, i8, u16, i16, u32, i32, u64, i64),
 849                      (f32, (f64, (f64,)))) = random();
 850     }
 851
 852     #[test]
 853     fn test_sample() {
 854         let min_val = 1;
 855         let max_val = 100;
 856
 857         let mut r = task_rng();
 858         let vals = range(min_val, max_val).collect::<Vec<int>>();
 859         let small_sample = r.sample(vals.iter(), 5);
 860         let large_sample = r.sample(vals.iter(), vals.len() + 5);
 861
 862         assert_eq!(small_sample.len(), 5);
 863         assert_eq!(large_sample.len(), vals.len());
 864
 865         assert!(small_sample.iter().all(|e| {
 866             **e >= min_val && **e <= max_val
 867         }));
 868     }
 869
 870     #[test]
 871     fn test_std_rng_seeded() {
 872         let s = task_rng().gen_vec::<uint>(256);
 873         let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
 874         let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
 875         assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
 876     }
 877
 878     #[test]
 879     fn test_std_rng_reseed() {
 880         let s = task_rng().gen_vec::<uint>(256);
 881         let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
 882         let string1 = r.gen_ascii_str(100);
 883
 884         r.reseed(s.as_slice());
 885
 886         let string2 = r.gen_ascii_str(100);
 887         assert_eq!(string1, string2);
 888     }
 889 }
 890
 891 #[cfg(test)]
 892 static RAND_BENCH_N: u64 = 100;
 893
 894 #[cfg(test)]
 895 mod bench {
 896     extern crate test;
 897     use self::test::Bencher;
 898     use {XorShiftRng, StdRng, IsaacRng, Isaac64Rng, Rng, RAND_BENCH_N};
 899     use std::mem::size_of;
 900
 901     #[bench]
 902     fn rand_xorshift(b: &mut Bencher) {
 903         let mut rng = XorShiftRng::new().unwrap();
 904         b.iter(|| {
 905             for _ in range(0, RAND_BENCH_N) {
 906                 rng.gen::<uint>();
 907             }
 908         });
 909         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 910     }
 911
 912     #[bench]
 913     fn rand_isaac(b: &mut Bencher) {
 914         let mut rng = IsaacRng::new().unwrap();
 915         b.iter(|| {
 916             for _ in range(0, RAND_BENCH_N) {
 917                 rng.gen::<uint>();
 918             }
 919         });
 920         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 921     }
 922
 923     #[bench]
 924     fn rand_isaac64(b: &mut Bencher) {
 925         let mut rng = Isaac64Rng::new().unwrap();
 926         b.iter(|| {
 927             for _ in range(0, RAND_BENCH_N) {
 928                 rng.gen::<uint>();
 929             }
 930         });
 931         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 932     }
 933
 934     #[bench]
 935     fn rand_std(b: &mut Bencher) {
 936         let mut rng = StdRng::new().unwrap();
 937         b.iter(|| {
 938             for _ in range(0, RAND_BENCH_N) {
 939                 rng.gen::<uint>();
 940             }
 941         });
 942         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 943     }
 944
 945     #[bench]
 946     fn rand_shuffle_100(b: &mut Bencher) {
 947         let mut rng = XorShiftRng::new().unwrap();
 948         let x : &mut[uint] = [1,..100];
 949         b.iter(|| {
 950             rng.shuffle(x);
 951         })
 952     }
 953 }