src/libstd/rand.rs

   1 // Copyright 2012 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 Random number generation.
  13
  14 The key functions are `random()` and `RngUtil::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::<float>()`.
  18
  19 See the `distributions` submodule for sampling random numbers from
  20 distributions like normal and exponential.
  21
  22 # Examples
  23
  24 ~~~ {.rust}
  25 use std::rand;
  26 use std::rand::RngUtil;
  27
  28 fn main() {
  29     let mut rng = rand::rng();
  30     if rng.gen() { // bool
  31         printfln!("int: %d, uint: %u", rng.gen(), rng.gen())
  32     }
  33 }
  34 ~~~
  35
  36 ~~~ {.rust}
  37 use std::rand;
  38
  39 fn main () {
  40     let tuple_ptr = rand::random::<~(f64, char)>();
  41     printfln!(tuple_ptr)
  42 }
  43 ~~~
  44 */
  45
  46 use cast;
  47 use clone::Clone;
  48 use cmp;
  49 use container::Container;
  50 use int;
  51 use iterator::{Iterator, range};
  52 use local_data;
  53 use num;
  54 use prelude::*;
  55 use str;
  56 use sys;
  57 use u32;
  58 use uint;
  59 use util;
  60 use vec;
  61 use libc::size_t;
  62
  63 #[path="rand/distributions.rs"]
  64 pub mod distributions;
  65
  66 /// A type that can be randomly generated using an Rng
  67 pub trait Rand {
  68     /// Generates a random instance of this type using the specified source of
  69     /// randomness
  70     fn rand<R: Rng>(rng: &mut R) -> Self;
  71 }
  72
  73 impl Rand for int {
  74     #[inline]
  75     fn rand<R: Rng>(rng: &mut R) -> int {
  76         if int::bits == 32 {
  77             rng.next() as int
  78         } else {
  79             rng.gen::<i64>() as int
  80         }
  81     }
  82 }
  83
  84 impl Rand for i8 {
  85     #[inline]
  86     fn rand<R: Rng>(rng: &mut R) -> i8 {
  87         rng.next() as i8
  88     }
  89 }
  90
  91 impl Rand for i16 {
  92     #[inline]
  93     fn rand<R: Rng>(rng: &mut R) -> i16 {
  94         rng.next() as i16
  95     }
  96 }
  97
  98 impl Rand for i32 {
  99     #[inline]
 100     fn rand<R: Rng>(rng: &mut R) -> i32 {
 101         rng.next() as i32
 102     }
 103 }
 104
 105 impl Rand for i64 {
 106     #[inline]
 107     fn rand<R: Rng>(rng: &mut R) -> i64 {
 108         (rng.next() as i64 << 32) | rng.next() as i64
 109     }
 110 }
 111
 112 impl Rand for uint {
 113     #[inline]
 114     fn rand<R: Rng>(rng: &mut R) -> uint {
 115         if uint::bits == 32 {
 116             rng.next() as uint
 117         } else {
 118             rng.gen::<u64>() as uint
 119         }
 120     }
 121 }
 122
 123 impl Rand for u8 {
 124     #[inline]
 125     fn rand<R: Rng>(rng: &mut R) -> u8 {
 126         rng.next() as u8
 127     }
 128 }
 129
 130 impl Rand for u16 {
 131     #[inline]
 132     fn rand<R: Rng>(rng: &mut R) -> u16 {
 133         rng.next() as u16
 134     }
 135 }
 136
 137 impl Rand for u32 {
 138     #[inline]
 139     fn rand<R: Rng>(rng: &mut R) -> u32 {
 140         rng.next()
 141     }
 142 }
 143
 144 impl Rand for u64 {
 145     #[inline]
 146     fn rand<R: Rng>(rng: &mut R) -> u64 {
 147         (rng.next() as u64 << 32) | rng.next() as u64
 148     }
 149 }
 150
 151 impl Rand for float {
 152     #[inline]
 153     fn rand<R: Rng>(rng: &mut R) -> float {
 154         rng.gen::<f64>() as float
 155     }
 156 }
 157
 158 impl Rand for f32 {
 159     #[inline]
 160     fn rand<R: Rng>(rng: &mut R) -> f32 {
 161         rng.gen::<f64>() as f32
 162     }
 163 }
 164
 165 static SCALE : f64 = (u32::max_value as f64) + 1.0f64;
 166 impl Rand for f64 {
 167     #[inline]
 168     fn rand<R: Rng>(rng: &mut R) -> f64 {
 169         let u1 = rng.next() as f64;
 170         let u2 = rng.next() as f64;
 171         let u3 = rng.next() as f64;
 172
 173         ((u1 / SCALE + u2) / SCALE + u3) / SCALE
 174     }
 175 }
 176
 177 impl Rand for char {
 178     #[inline]
 179     fn rand<R: Rng>(rng: &mut R) -> char {
 180         rng.next() as char
 181     }
 182 }
 183
 184 impl Rand for bool {
 185     #[inline]
 186     fn rand<R: Rng>(rng: &mut R) -> bool {
 187         rng.next() & 1u32 == 1u32
 188     }
 189 }
 190
 191 macro_rules! tuple_impl {
 192     // use variables to indicate the arity of the tuple
 193     ($($tyvar:ident),* ) => {
 194         // the trailing commas are for the 1 tuple
 195         impl<
 196             $( $tyvar : Rand ),*
 197             > Rand for ( $( $tyvar ),* , ) {
 198
 199             #[inline]
 200             fn rand<R: Rng>(_rng: &mut R) -> ( $( $tyvar ),* , ) {
 201                 (
 202                     // use the $tyvar's to get the appropriate number of
 203                     // repeats (they're not actually needed)
 204                     $(
 205                         _rng.gen::<$tyvar>()
 206                     ),*
 207                     ,
 208                 )
 209             }
 210         }
 211     }
 212 }
 213
 214 impl Rand for () {
 215     #[inline]
 216     fn rand<R: Rng>(_: &mut R) -> () { () }
 217 }
 218 tuple_impl!{A}
 219 tuple_impl!{A, B}
 220 tuple_impl!{A, B, C}
 221 tuple_impl!{A, B, C, D}
 222 tuple_impl!{A, B, C, D, E}
 223 tuple_impl!{A, B, C, D, E, F}
 224 tuple_impl!{A, B, C, D, E, F, G}
 225 tuple_impl!{A, B, C, D, E, F, G, H}
 226 tuple_impl!{A, B, C, D, E, F, G, H, I}
 227 tuple_impl!{A, B, C, D, E, F, G, H, I, J}
 228
 229 impl<T:Rand> Rand for Option<T> {
 230     #[inline]
 231     fn rand<R: Rng>(rng: &mut R) -> Option<T> {
 232         if rng.gen() {
 233             Some(rng.gen())
 234         } else {
 235             None
 236         }
 237     }
 238 }
 239
 240 impl<T: Rand> Rand for ~T {
 241     #[inline]
 242     fn rand<R: Rng>(rng: &mut R) -> ~T { ~rng.gen() }
 243 }
 244
 245 impl<T: Rand + 'static> Rand for @T {
 246     #[inline]
 247     fn rand<R: Rng>(rng: &mut R) -> @T { @rng.gen() }
 248 }
 249
 250 #[abi = "cdecl"]
 251 pub mod rustrt {
 252     use libc::size_t;
 253
 254     extern {
 255         pub fn rand_seed_size() -> size_t;
 256         pub fn rand_gen_seed(buf: *mut u8, sz: size_t);
 257     }
 258 }
 259
 260 /// A random number generator
 261 pub trait Rng {
 262     /// Return the next random integer
 263     fn next(&mut self) -> u32;
 264 }
 265
 266 /// A value with a particular weight compared to other values
 267 pub struct Weighted<T> {
 268     /// The numerical weight of this item
 269     weight: uint,
 270     /// The actual item which is being weighted
 271     item: T,
 272 }
 273
 274 /// Helper functions attached to the Rng type
 275 pub trait RngUtil {
 276     /// Return a random value of a Rand type
 277     fn gen<T:Rand>(&mut self) -> T;
 278     /**
 279      * Return a int randomly chosen from the range [start, end),
 280      * failing if start >= end
 281      */
 282     fn gen_int_range(&mut self, start: int, end: int) -> int;
 283     /**
 284      * Return a uint randomly chosen from the range [start, end),
 285      * failing if start >= end
 286      */
 287     fn gen_uint_range(&mut self, start: uint, end: uint) -> uint;
 288     /**
 289      * Return a char randomly chosen from chars, failing if chars is empty
 290      */
 291     fn gen_char_from(&mut self, chars: &str) -> char;
 292     /**
 293      * Return a bool with a 1 in n chance of true
 294      *
 295      * # Example
 296      *
 297      * ~~~ {.rust}
 298      *
 299      * use std::rand;
 300      * use std::rand::RngUtil;
 301      *
 302      * fn main() {
 303      *     let mut rng = rand::rng();
 304      *     printfln!("%b", rng.gen_weighted_bool(3));
 305      * }
 306      * ~~~
 307      */
 308     fn gen_weighted_bool(&mut self, n: uint) -> bool;
 309     /**
 310      * Return a random string of the specified length composed of A-Z,a-z,0-9
 311      *
 312      * # Example
 313      *
 314      * ~~~ {.rust}
 315      *
 316      * use std::rand;
 317      * use std::rand::RngUtil;
 318      *
 319      * fn main() {
 320      *     let mut rng = rand::rng();
 321      *     println(rng.gen_str(8));
 322      * }
 323      * ~~~
 324      */
 325     fn gen_str(&mut self, len: uint) -> ~str;
 326     /**
 327      * Return a random byte string of the specified length
 328      *
 329      * # Example
 330      *
 331      * ~~~ {.rust}
 332      *
 333      * use std::rand;
 334      * use std::rand::RngUtil;
 335      *
 336      * fn main() {
 337      *     let mut rng = rand::rng();
 338      *     printfln!(rng.gen_bytes(8));
 339      * }
 340      * ~~~
 341      */
 342     fn gen_bytes(&mut self, len: uint) -> ~[u8];
 343     /**
 344      * Choose an item randomly, failing if values is empty
 345      *
 346      * # Example
 347      *
 348      * ~~~ {.rust}
 349      *
 350      * use std::rand;
 351      * use std::rand::RngUtil;
 352      *
 353      * fn main() {
 354      *     let mut rng = rand::rng();
 355      *     printfln!("%d", rng.choose([1,2,4,8,16,32]));
 356      * }
 357      * ~~~
 358      */
 359     fn choose<T:Clone>(&mut self, values: &[T]) -> T;
 360     /// Choose Some(item) randomly, returning None if values is empty
 361     fn choose_option<T:Clone>(&mut self, values: &[T]) -> Option<T>;
 362     /**
 363      * Choose an item respecting the relative weights, failing if the sum of
 364      * the weights is 0
 365      *
 366      * # Example
 367      *
 368      * ~~~ {.rust}
 369      *
 370      * use std::rand;
 371      * use std::rand::RngUtil;
 372      *
 373      * fn main() {
 374      *     let mut rng = rand::rng();
 375      *     let x = [rand::Weighted {weight: 4, item: 'a'},
 376      *              rand::Weighted {weight: 2, item: 'b'},
 377      *              rand::Weighted {weight: 2, item: 'c'}];
 378      *     printfln!("%c", rng.choose_weighted(x));
 379      * }
 380      * ~~~
 381      */
 382     fn choose_weighted<T:Clone>(&mut self, v : &[Weighted<T>]) -> T;
 383     /**
 384      * Choose Some(item) respecting the relative weights, returning none if
 385      * the sum of the weights is 0
 386      *
 387      * # Example
 388      *
 389      * ~~~ {.rust}
 390      *
 391      * use std::rand;
 392      * use std::rand::RngUtil;
 393      *
 394      * fn main() {
 395      *     let mut rng = rand::rng();
 396      *     let x = [rand::Weighted {weight: 4, item: 'a'},
 397      *              rand::Weighted {weight: 2, item: 'b'},
 398      *              rand::Weighted {weight: 2, item: 'c'}];
 399      *     printfln!(rng.choose_weighted_option(x));
 400      * }
 401      * ~~~
 402      */
 403     fn choose_weighted_option<T:Clone>(&mut self, v: &[Weighted<T>])
 404                                      -> Option<T>;
 405     /**
 406      * Return a vec containing copies of the items, in order, where
 407      * the weight of the item determines how many copies there are
 408      *
 409      * # Example
 410      *
 411      * ~~~ {.rust}
 412      *
 413      * use std::rand;
 414      * use std::rand::RngUtil;
 415      *
 416      * fn main() {
 417      *     let mut rng = rand::rng();
 418      *     let x = [rand::Weighted {weight: 4, item: 'a'},
 419      *              rand::Weighted {weight: 2, item: 'b'},
 420      *              rand::Weighted {weight: 2, item: 'c'}];
 421      *     printfln!(rng.weighted_vec(x));
 422      * }
 423      * ~~~
 424      */
 425     fn weighted_vec<T:Clone>(&mut self, v: &[Weighted<T>]) -> ~[T];
 426     /**
 427      * Shuffle a vec
 428      *
 429      * # Example
 430      *
 431      * ~~~ {.rust}
 432      *
 433      * use std::rand;
 434      * use std::rand::RngUtil;
 435      *
 436      * fn main() {
 437      *     let mut rng = rand::rng();
 438      *     printfln!(rng.shuffle([1,2,3]));
 439      * }
 440      * ~~~
 441      */
 442     fn shuffle<T:Clone>(&mut self, values: &[T]) -> ~[T];
 443     /**
 444      * Shuffle a mutable vec in place
 445      *
 446      * # Example
 447      *
 448      * ~~~ {.rust}
 449      *
 450      * use std::rand;
 451      * use std::rand::RngUtil;
 452      *
 453      * fn main() {
 454      *     let mut rng = rand::rng();
 455      *     let mut y = [1,2,3];
 456      *     rng.shuffle_mut(y);
 457      *     printfln!(y);
 458      *     rng.shuffle_mut(y);
 459      *     printfln!(y);
 460      * }
 461      * ~~~
 462      */
 463     fn shuffle_mut<T>(&mut self, values: &mut [T]);
 464
 465     /**
 466      * Sample up to `n` values from an iterator.
 467      *
 468      * # Example
 469      *
 470      * ~~~ {.rust}
 471      *
 472      * use std::rand;
 473      * use std::rand::RngUtil;
 474      *
 475      * fn main() {
 476      *     let mut rng = rand::rng();
 477      *     let vals = range(1, 100).to_owned_vec();
 478      *     let sample = rng.sample(vals.iter(), 5);
 479      *     printfln!(sample);
 480      * }
 481      * ~~~
 482      */
 483     fn sample<A, T: Iterator<A>>(&mut self, iter: T, n: uint) -> ~[A];
 484 }
 485
 486 /// Extension methods for random number generators
 487 impl<R: Rng> RngUtil for R {
 488     /// Return a random value for a Rand type
 489     #[inline]
 490     fn gen<T: Rand>(&mut self) -> T {
 491         Rand::rand(self)
 492     }
 493
 494     /**
 495      * Return an int randomly chosen from the range [start, end),
 496      * failing if start >= end
 497      */
 498     fn gen_int_range(&mut self, start: int, end: int) -> int {
 499         assert!(start < end);
 500         start + num::abs(self.gen::<int>() % (end - start))
 501     }
 502
 503     /**
 504      * Return a uint randomly chosen from the range [start, end),
 505      * failing if start >= end
 506      */
 507     fn gen_uint_range(&mut self, start: uint, end: uint) -> uint {
 508         assert!(start < end);
 509         start + (self.gen::<uint>() % (end - start))
 510     }
 511
 512     /**
 513      * Return a char randomly chosen from chars, failing if chars is empty
 514      */
 515     fn gen_char_from(&mut self, chars: &str) -> char {
 516         assert!(!chars.is_empty());
 517         let mut cs = ~[];
 518         for c in chars.iter() { cs.push(c) }
 519         self.choose(cs)
 520     }
 521
 522     /// Return a bool with a 1-in-n chance of true
 523     fn gen_weighted_bool(&mut self, n: uint) -> bool {
 524         if n == 0u {
 525             true
 526         } else {
 527             self.gen_uint_range(1u, n + 1u) == 1u
 528         }
 529     }
 530
 531     /**
 532      * Return a random string of the specified length composed of A-Z,a-z,0-9
 533      */
 534     fn gen_str(&mut self, len: uint) -> ~str {
 535         let charset = ~"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
 536                        abcdefghijklmnopqrstuvwxyz\
 537                        0123456789";
 538         let mut s = ~"";
 539         let mut i = 0u;
 540         while (i < len) {
 541             s = s + str::from_char(self.gen_char_from(charset));
 542             i += 1u;
 543         }
 544         s
 545     }
 546
 547     /// Return a random byte string of the specified length
 548     fn gen_bytes(&mut self, len: uint) -> ~[u8] {
 549         do vec::from_fn(len) |_i| {
 550             self.gen()
 551         }
 552     }
 553
 554     /// Choose an item randomly, failing if values is empty
 555     fn choose<T:Clone>(&mut self, values: &[T]) -> T {
 556         self.choose_option(values).unwrap()
 557     }
 558
 559     /// Choose Some(item) randomly, returning None if values is empty
 560     fn choose_option<T:Clone>(&mut self, values: &[T]) -> Option<T> {
 561         if values.is_empty() {
 562             None
 563         } else {
 564             Some(values[self.gen_uint_range(0u, values.len())].clone())
 565         }
 566     }
 567     /**
 568      * Choose an item respecting the relative weights, failing if the sum of
 569      * the weights is 0
 570      */
 571     fn choose_weighted<T:Clone>(&mut self, v: &[Weighted<T>]) -> T {
 572         self.choose_weighted_option(v).unwrap()
 573     }
 574
 575     /**
 576      * Choose Some(item) respecting the relative weights, returning none if
 577      * the sum of the weights is 0
 578      */
 579     fn choose_weighted_option<T:Clone>(&mut self, v: &[Weighted<T>])
 580                                        -> Option<T> {
 581         let mut total = 0u;
 582         for item in v.iter() {
 583             total += item.weight;
 584         }
 585         if total == 0u {
 586             return None;
 587         }
 588         let chosen = self.gen_uint_range(0u, total);
 589         let mut so_far = 0u;
 590         for item in v.iter() {
 591             so_far += item.weight;
 592             if so_far > chosen {
 593                 return Some(item.item.clone());
 594             }
 595         }
 596         util::unreachable();
 597     }
 598
 599     /**
 600      * Return a vec containing copies of the items, in order, where
 601      * the weight of the item determines how many copies there are
 602      */
 603     fn weighted_vec<T:Clone>(&mut self, v: &[Weighted<T>]) -> ~[T] {
 604         let mut r = ~[];
 605         for item in v.iter() {
 606             for _ in range(0u, item.weight) {
 607                 r.push(item.item.clone());
 608             }
 609         }
 610         r
 611     }
 612
 613     /// Shuffle a vec
 614     fn shuffle<T:Clone>(&mut self, values: &[T]) -> ~[T] {
 615         let mut m = values.to_owned();
 616         self.shuffle_mut(m);
 617         m
 618     }
 619
 620     /// Shuffle a mutable vec in place
 621     fn shuffle_mut<T>(&mut self, values: &mut [T]) {
 622         let mut i = values.len();
 623         while i >= 2u {
 624             // invariant: elements with index >= i have been locked in place.
 625             i -= 1u;
 626             // lock element i in place.
 627             values.swap(i, self.gen_uint_range(0u, i + 1u));
 628         }
 629     }
 630
 631     /// Randomly sample up to `n` elements from an iterator
 632     fn sample<A, T: Iterator<A>>(&mut self, iter: T, n: uint) -> ~[A] {
 633         let mut reservoir : ~[A] = vec::with_capacity(n);
 634         for (i, elem) in iter.enumerate() {
 635             if i < n {
 636                 reservoir.push(elem);
 637                 loop
 638             }
 639
 640             let k = self.gen_uint_range(0, i + 1);
 641             if k < reservoir.len() {
 642                 reservoir[k] = elem
 643             }
 644         }
 645         reservoir
 646     }
 647 }
 648
 649 /// Create a random number generator with a default algorithm and seed.
 650 ///
 651 /// It returns the cryptographically-safest `Rng` algorithm currently
 652 /// available in Rust. If you require a specifically seeded `Rng` for
 653 /// consistency over time you should pick one algorithm and create the
 654 /// `Rng` yourself.
 655 pub fn rng() -> IsaacRng {
 656     IsaacRng::new()
 657 }
 658
 659 /// Create a weak random number generator with a default algorithm and seed.
 660 ///
 661 /// It returns the fastest `Rng` algorithm currently available in Rust without
 662 /// consideration for cryptography or security. If you require a specifically
 663 /// seeded `Rng` for consistency over time you should pick one algorithm and
 664 /// create the `Rng` yourself.
 665 pub fn weak_rng() -> XorShiftRng {
 666     XorShiftRng::new()
 667 }
 668
 669 static RAND_SIZE_LEN: u32 = 8;
 670 static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN;
 671
 672 /// A random number generator that uses the [ISAAC
 673 /// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29).
 674 ///
 675 /// The ISAAC algorithm is suitable for cryptographic purposes.
 676 pub struct IsaacRng {
 677     priv cnt: u32,
 678     priv rsl: [u32, .. RAND_SIZE],
 679     priv mem: [u32, .. RAND_SIZE],
 680     priv a: u32,
 681     priv b: u32,
 682     priv c: u32
 683 }
 684
 685 impl IsaacRng {
 686     /// Create an ISAAC random number generator with a random seed.
 687     pub fn new() -> IsaacRng {
 688         IsaacRng::new_seeded(seed())
 689     }
 690
 691     /// Create an ISAAC random number generator with a seed. This can be any
 692     /// length, although the maximum number of bytes used is 1024 and any more
 693     /// will be silently ignored. A generator constructed with a given seed
 694     /// will generate the same sequence of values as all other generators
 695     /// constructed with the same seed.
 696     pub fn new_seeded(seed: &[u8]) -> IsaacRng {
 697         let mut rng = IsaacRng {
 698             cnt: 0,
 699             rsl: [0, .. RAND_SIZE],
 700             mem: [0, .. RAND_SIZE],
 701             a: 0, b: 0, c: 0
 702         };
 703
 704         let array_size = sys::size_of_val(&rng.rsl);
 705         let copy_length = cmp::min(array_size, seed.len());
 706
 707         // manually create a &mut [u8] slice of randrsl to copy into.
 708         let dest = unsafe { cast::transmute((&mut rng.rsl, array_size)) };
 709         vec::bytes::copy_memory(dest, seed, copy_length);
 710         rng.init(true);
 711         rng
 712     }
 713
 714     /// Create an ISAAC random number generator using the default
 715     /// fixed seed.
 716     pub fn new_unseeded() -> IsaacRng {
 717         let mut rng = IsaacRng {
 718             cnt: 0,
 719             rsl: [0, .. RAND_SIZE],
 720             mem: [0, .. RAND_SIZE],
 721             a: 0, b: 0, c: 0
 722         };
 723         rng.init(false);
 724         rng
 725     }
 726
 727     /// Initialises `self`. If `use_rsl` is true, then use the current value
 728     /// of `rsl` as a seed, otherwise construct one algorithmically (not
 729     /// randomly).
 730     fn init(&mut self, use_rsl: bool) {
 731         let mut a = 0x9e3779b9;
 732         let mut b = a;
 733         let mut c = a;
 734         let mut d = a;
 735         let mut e = a;
 736         let mut f = a;
 737         let mut g = a;
 738         let mut h = a;
 739
 740         macro_rules! mix(
 741             () => {{
 742                 a^=b<<11; d+=a; b+=c;
 743                 b^=c>>2;  e+=b; c+=d;
 744                 c^=d<<8;  f+=c; d+=e;
 745                 d^=e>>16; g+=d; e+=f;
 746                 e^=f<<10; h+=e; f+=g;
 747                 f^=g>>4;  a+=f; g+=h;
 748                 g^=h<<8;  b+=g; h+=a;
 749                 h^=a>>9;  c+=h; a+=b;
 750             }}
 751         );
 752
 753         do 4.times { mix!(); }
 754
 755         if use_rsl {
 756             macro_rules! memloop (
 757                 ($arr:expr) => {{
 758                     do u32::range_step(0, RAND_SIZE, 8) |i| {
 759                         a+=$arr[i  ]; b+=$arr[i+1];
 760                         c+=$arr[i+2]; d+=$arr[i+3];
 761                         e+=$arr[i+4]; f+=$arr[i+5];
 762                         g+=$arr[i+6]; h+=$arr[i+7];
 763                         mix!();
 764                         self.mem[i  ]=a; self.mem[i+1]=b;
 765                         self.mem[i+2]=c; self.mem[i+3]=d;
 766                         self.mem[i+4]=e; self.mem[i+5]=f;
 767                         self.mem[i+6]=g; self.mem[i+7]=h;
 768                         true
 769                     };
 770                 }}
 771             );
 772
 773             memloop!(self.rsl);
 774             memloop!(self.mem);
 775         } else {
 776             do u32::range_step(0, RAND_SIZE, 8) |i| {
 777                 mix!();
 778                 self.mem[i  ]=a; self.mem[i+1]=b;
 779                 self.mem[i+2]=c; self.mem[i+3]=d;
 780                 self.mem[i+4]=e; self.mem[i+5]=f;
 781                 self.mem[i+6]=g; self.mem[i+7]=h;
 782                 true
 783             };
 784         }
 785
 786         self.isaac();
 787     }
 788
 789     /// Refills the output buffer (`self.rsl`)
 790     #[inline]
 791     fn isaac(&mut self) {
 792         self.c += 1;
 793         // abbreviations
 794         let mut a = self.a;
 795         let mut b = self.b + self.c;
 796
 797         static MIDPOINT: uint = RAND_SIZE as uint / 2;
 798
 799         macro_rules! ind (($x:expr) => {
 800             self.mem[($x >> 2) & (RAND_SIZE - 1)]
 801         });
 802         macro_rules! rngstep(
 803             ($j:expr, $shift:expr) => {{
 804                 let base = base + $j;
 805                 let mix = if $shift < 0 {
 806                     a >> -$shift as uint
 807                 } else {
 808                     a << $shift as uint
 809                 };
 810
 811                 let x = self.mem[base  + mr_offset];
 812                 a = (a ^ mix) + self.mem[base + m2_offset];
 813                 let y = ind!(x) + a + b;
 814                 self.mem[base + mr_offset] = y;
 815
 816                 b = ind!(y >> RAND_SIZE_LEN) + x;
 817                 self.rsl[base + mr_offset] = b;
 818             }}
 819         );
 820
 821         let r = [(0, MIDPOINT), (MIDPOINT, 0)];
 822         for &(mr_offset, m2_offset) in r.iter() {
 823             do uint::range_step(0, MIDPOINT, 4) |base| {
 824                 rngstep!(0, 13);
 825                 rngstep!(1, -6);
 826                 rngstep!(2, 2);
 827                 rngstep!(3, -16);
 828                 true
 829             };
 830         }
 831
 832         self.a = a;
 833         self.b = b;
 834         self.cnt = RAND_SIZE;
 835     }
 836 }
 837
 838 impl Rng for IsaacRng {
 839     #[inline]
 840     fn next(&mut self) -> u32 {
 841         if self.cnt == 0 {
 842             // make some more numbers
 843             self.isaac();
 844         }
 845         self.cnt -= 1;
 846         self.rsl[self.cnt]
 847     }
 848 }
 849
 850 /// An [Xorshift random number
 851 /// generator](http://en.wikipedia.org/wiki/Xorshift).
 852 ///
 853 /// The Xorshift algorithm is not suitable for cryptographic purposes
 854 /// but is very fast. If you do not know for sure that it fits your
 855 /// requirements, use a more secure one such as `IsaacRng`.
 856 pub struct XorShiftRng {
 857     priv x: u32,
 858     priv y: u32,
 859     priv z: u32,
 860     priv w: u32,
 861 }
 862
 863 impl Rng for XorShiftRng {
 864     #[inline]
 865     fn next(&mut self) -> u32 {
 866         let x = self.x;
 867         let t = x ^ (x << 11);
 868         self.x = self.y;
 869         self.y = self.z;
 870         self.z = self.w;
 871         let w = self.w;
 872         self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
 873         self.w
 874     }
 875 }
 876
 877 impl XorShiftRng {
 878     /// Create an xor shift random number generator with a random seed.
 879     pub fn new() -> XorShiftRng {
 880         #[fixed_stack_segment]; #[inline(never)];
 881
 882         // generate seeds the same way as seed(), except we have a spceific size
 883         let mut s = [0u8, ..16];
 884         loop {
 885             do s.as_mut_buf |p, sz| {
 886                 unsafe {
 887                     rustrt::rand_gen_seed(p, sz as size_t);
 888                 }
 889             }
 890             if !s.iter().all(|x| *x == 0) {
 891                 break;
 892             }
 893         }
 894         let s: &[u32, ..4] = unsafe { cast::transmute(&s) };
 895         XorShiftRng::new_seeded(s[0], s[1], s[2], s[3])
 896     }
 897
 898     /**
 899      * Create a random number generator using the specified seed. A generator
 900      * constructed with a given seed will generate the same sequence of values
 901      * as all other generators constructed with the same seed.
 902      */
 903     pub fn new_seeded(x: u32, y: u32, z: u32, w: u32) -> XorShiftRng {
 904         XorShiftRng {
 905             x: x,
 906             y: y,
 907             z: z,
 908             w: w,
 909         }
 910     }
 911 }
 912
 913 /// Create a new random seed.
 914 pub fn seed() -> ~[u8] {
 915     #[fixed_stack_segment]; #[inline(never)];
 916
 917     unsafe {
 918         let n = rustrt::rand_seed_size() as uint;
 919         let mut s = vec::from_elem(n, 0_u8);
 920         do s.as_mut_buf |p, sz| {
 921             rustrt::rand_gen_seed(p, sz as size_t)
 922         }
 923         s
 924     }
 925 }
 926
 927 // used to make space in TLS for a random number generator
 928 static tls_rng_state: local_data::Key<@@mut IsaacRng> = &local_data::Key;
 929
 930 /**
 931  * Gives back a lazily initialized task-local random number generator,
 932  * seeded by the system. Intended to be used in method chaining style, ie
 933  * `task_rng().gen::<int>()`.
 934  */
 935 #[inline]
 936 pub fn task_rng() -> @mut IsaacRng {
 937     let r = local_data::get(tls_rng_state, |k| k.map(|&k| *k));
 938     match r {
 939         None => {
 940             let rng = @@mut IsaacRng::new_seeded(seed());
 941             local_data::set(tls_rng_state, rng);
 942             *rng
 943         }
 944         Some(rng) => *rng
 945     }
 946 }
 947
 948 // Allow direct chaining with `task_rng`
 949 impl<R: Rng> Rng for @mut R {
 950     #[inline]
 951     fn next(&mut self) -> u32 {
 952         (**self).next()
 953     }
 954 }
 955
 956 /**
 957  * Returns a random value of a Rand type, using the task's random number
 958  * generator.
 959  */
 960 #[inline]
 961 pub fn random<T: Rand>() -> T {
 962     task_rng().gen()
 963 }
 964
 965 #[cfg(test)]
 966 mod test {
 967     use iterator::{Iterator, range};
 968     use option::{Option, Some};
 969     use super::*;
 970
 971     #[test]
 972     fn test_rng_seeded() {
 973         let seed = seed();
 974         let mut ra = IsaacRng::new_seeded(seed);
 975         let mut rb = IsaacRng::new_seeded(seed);
 976         assert_eq!(ra.gen_str(100u), rb.gen_str(100u));
 977     }
 978
 979     #[test]
 980     fn test_rng_seeded_custom_seed() {
 981         // much shorter than generated seeds which are 1024 bytes
 982         let seed = [2u8, 32u8, 4u8, 32u8, 51u8];
 983         let mut ra = IsaacRng::new_seeded(seed);
 984         let mut rb = IsaacRng::new_seeded(seed);
 985         assert_eq!(ra.gen_str(100u), rb.gen_str(100u));
 986     }
 987
 988     #[test]
 989     fn test_rng_seeded_custom_seed2() {
 990         let seed = [2u8, 32u8, 4u8, 32u8, 51u8];
 991         let mut ra = IsaacRng::new_seeded(seed);
 992         // Regression test that isaac is actually using the above vector
 993         let r = ra.next();
 994         error!("%?", r);
 995         assert!(r == 890007737u32 // on x86_64
 996                      || r == 2935188040u32); // on x86
 997     }
 998
 999     #[test]
1000     fn test_gen_int_range() {
1001         let mut r = rng();
1002         let a = r.gen_int_range(-3, 42);
1003         assert!(a >= -3 && a < 42);
1004         assert_eq!(r.gen_int_range(0, 1), 0);
1005         assert_eq!(r.gen_int_range(-12, -11), -12);
1006     }
1007
1008     #[test]
1009     #[should_fail]
1010     #[ignore(cfg(windows))]
1011     fn test_gen_int_from_fail() {
1012         let mut r = rng();
1013         r.gen_int_range(5, -2);
1014     }
1015
1016     #[test]
1017     fn test_gen_uint_range() {
1018         let mut r = rng();
1019         let a = r.gen_uint_range(3u, 42u);
1020         assert!(a >= 3u && a < 42u);
1021         assert_eq!(r.gen_uint_range(0u, 1u), 0u);
1022         assert_eq!(r.gen_uint_range(12u, 13u), 12u);
1023     }
1024
1025     #[test]
1026     #[should_fail]
1027     #[ignore(cfg(windows))]
1028     fn test_gen_uint_range_fail() {
1029         let mut r = rng();
1030         r.gen_uint_range(5u, 2u);
1031     }
1032
1033     #[test]
1034     fn test_gen_float() {
1035         let mut r = rng();
1036         let a = r.gen::<float>();
1037         let b = r.gen::<float>();
1038         debug!((a, b));
1039     }
1040
1041     #[test]
1042     fn test_gen_weighted_bool() {
1043         let mut r = rng();
1044         assert_eq!(r.gen_weighted_bool(0u), true);
1045         assert_eq!(r.gen_weighted_bool(1u), true);
1046     }
1047
1048     #[test]
1049     fn test_gen_str() {
1050         let mut r = rng();
1051         debug!(r.gen_str(10u));
1052         debug!(r.gen_str(10u));
1053         debug!(r.gen_str(10u));
1054         assert_eq!(r.gen_str(0u).len(), 0u);
1055         assert_eq!(r.gen_str(10u).len(), 10u);
1056         assert_eq!(r.gen_str(16u).len(), 16u);
1057     }
1058
1059     #[test]
1060     fn test_gen_bytes() {
1061         let mut r = rng();
1062         assert_eq!(r.gen_bytes(0u).len(), 0u);
1063         assert_eq!(r.gen_bytes(10u).len(), 10u);
1064         assert_eq!(r.gen_bytes(16u).len(), 16u);
1065     }
1066
1067     #[test]
1068     fn test_choose() {
1069         let mut r = rng();
1070         assert_eq!(r.choose([1, 1, 1]), 1);
1071     }
1072
1073     #[test]
1074     fn test_choose_option() {
1075         let mut r = rng();
1076         let x: Option<int> = r.choose_option([]);
1077         assert!(x.is_none());
1078         assert_eq!(r.choose_option([1, 1, 1]), Some(1));
1079     }
1080
1081     #[test]
1082     fn test_choose_weighted() {
1083         let mut r = rng();
1084         assert!(r.choose_weighted([
1085             Weighted { weight: 1u, item: 42 },
1086         ]) == 42);
1087         assert!(r.choose_weighted([
1088             Weighted { weight: 0u, item: 42 },
1089             Weighted { weight: 1u, item: 43 },
1090         ]) == 43);
1091     }
1092
1093     #[test]
1094     fn test_choose_weighted_option() {
1095         let mut r = rng();
1096         assert!(r.choose_weighted_option([
1097             Weighted { weight: 1u, item: 42 },
1098         ]) == Some(42));
1099         assert!(r.choose_weighted_option([
1100             Weighted { weight: 0u, item: 42 },
1101             Weighted { weight: 1u, item: 43 },
1102         ]) == Some(43));
1103         let v: Option<int> = r.choose_weighted_option([]);
1104         assert!(v.is_none());
1105     }
1106
1107     #[test]
1108     fn test_weighted_vec() {
1109         let mut r = rng();
1110         let empty: ~[int] = ~[];
1111         assert_eq!(r.weighted_vec([]), empty);
1112         assert!(r.weighted_vec([
1113             Weighted { weight: 0u, item: 3u },
1114             Weighted { weight: 1u, item: 2u },
1115             Weighted { weight: 2u, item: 1u },
1116         ]) == ~[2u, 1u, 1u]);
1117     }
1118
1119     #[test]
1120     fn test_shuffle() {
1121         let mut r = rng();
1122         let empty: ~[int] = ~[];
1123         assert_eq!(r.shuffle([]), empty);
1124         assert_eq!(r.shuffle([1, 1, 1]), ~[1, 1, 1]);
1125     }
1126
1127     #[test]
1128     fn test_task_rng() {
1129         let mut r = task_rng();
1130         r.gen::<int>();
1131         assert_eq!(r.shuffle([1, 1, 1]), ~[1, 1, 1]);
1132         assert_eq!(r.gen_uint_range(0u, 1u), 0u);
1133     }
1134
1135     #[test]
1136     fn test_random() {
1137         // not sure how to test this aside from just getting some values
1138         let _n : uint = random();
1139         let _f : f32 = random();
1140         let _o : Option<Option<i8>> = random();
1141         let _many : ((),
1142                      (~uint, @int, ~Option<~(@char, ~(@bool,))>),
1143                      (u8, i8, u16, i16, u32, i32, u64, i64),
1144                      (f32, (f64, (float,)))) = random();
1145     }
1146
1147     #[test]
1148     fn compare_isaac_implementation() {
1149         #[fixed_stack_segment]; #[inline(never)];
1150
1151         // This is to verify that the implementation of the ISAAC rng is
1152         // correct (i.e. matches the output of the upstream implementation,
1153         // which is in the runtime)
1154         use libc::size_t;
1155
1156         #[abi = "cdecl"]
1157         mod rustrt {
1158             use libc::size_t;
1159
1160             #[allow(non_camel_case_types)] // runtime type
1161             pub enum rust_rng {}
1162
1163             extern {
1164                 pub fn rand_new_seeded(buf: *u8, sz: size_t) -> *rust_rng;
1165                 pub fn rand_next(rng: *rust_rng) -> u32;
1166                 pub fn rand_free(rng: *rust_rng);
1167             }
1168         }
1169
1170         // run against several seeds
1171         do 10.times {
1172             unsafe {
1173                 let seed = super::seed();
1174                 let rt_rng = do seed.as_imm_buf |p, sz| {
1175                     rustrt::rand_new_seeded(p, sz as size_t)
1176                 };
1177                 let mut rng = IsaacRng::new_seeded(seed);
1178
1179                 do 10000.times {
1180                     assert_eq!(rng.next(), rustrt::rand_next(rt_rng));
1181                 }
1182                 rustrt::rand_free(rt_rng);
1183             }
1184         }
1185     }
1186
1187     #[test]
1188     fn test_sample() {
1189         let MIN_VAL = 1;
1190         let MAX_VAL = 100;
1191
1192         let mut r = rng();
1193         let vals = range(MIN_VAL, MAX_VAL).to_owned_vec();
1194         let small_sample = r.sample(vals.iter(), 5);
1195         let large_sample = r.sample(vals.iter(), vals.len() + 5);
1196
1197         assert_eq!(small_sample.len(), 5);
1198         assert_eq!(large_sample.len(), vals.len());
1199
1200         assert!(small_sample.iter().all(|e| {
1201             **e >= MIN_VAL && **e <= MAX_VAL
1202         }));
1203     }
1204 }
1205
1206 #[cfg(test)]
1207 mod bench {
1208     use extra::test::BenchHarness;
1209     use rand::*;
1210     use sys::size_of;
1211
1212     #[bench]
1213     fn rand_xorshift(bh: &mut BenchHarness) {
1214         let mut rng = XorShiftRng::new();
1215         do bh.iter {
1216             rng.gen::<uint>();
1217         }
1218         bh.bytes = size_of::<uint>() as u64;
1219     }
1220
1221     #[bench]
1222     fn rand_isaac(bh: &mut BenchHarness) {
1223         let mut rng = IsaacRng::new();
1224         do bh.iter {
1225             rng.gen::<uint>();
1226         }
1227         bh.bytes = size_of::<uint>() as u64;
1228     }
1229
1230     #[bench]
1231     fn rand_shuffle_100(bh: &mut BenchHarness) {
1232         let mut rng = XorShiftRng::new();
1233         let x : &mut[uint] = [1,..100];
1234         do bh.iter {
1235             rng.shuffle_mut(x);
1236         }
1237     }
1238 }