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