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     pub 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 /// Extension methods for random number generators
 467 impl<R: Rng> RngUtil for R {
 468     /// Return a random value for a Rand type
 469     #[inline]
 470     fn gen<T: Rand>(&mut self) -> T {
 471         Rand::rand(self)
 472     }
 473
 474     /**
 475      * Return an int randomly chosen from the range [start, end),
 476      * failing if start >= end
 477      */
 478     fn gen_int_range(&mut self, start: int, end: int) -> int {
 479         assert!(start < end);
 480         start + num::abs(self.gen::<int>() % (end - start))
 481     }
 482
 483     /**
 484      * Return a uint randomly chosen from the range [start, end),
 485      * failing if start >= end
 486      */
 487     fn gen_uint_range(&mut self, start: uint, end: uint) -> uint {
 488         assert!(start < end);
 489         start + (self.gen::<uint>() % (end - start))
 490     }
 491
 492     /**
 493      * Return a char randomly chosen from chars, failing if chars is empty
 494      */
 495     fn gen_char_from(&mut self, chars: &str) -> char {
 496         assert!(!chars.is_empty());
 497         let mut cs = ~[];
 498         for c in chars.iter() { cs.push(c) }
 499         self.choose(cs)
 500     }
 501
 502     /// Return a bool with a 1-in-n chance of true
 503     fn gen_weighted_bool(&mut self, n: uint) -> bool {
 504         if n == 0u {
 505             true
 506         } else {
 507             self.gen_uint_range(1u, n + 1u) == 1u
 508         }
 509     }
 510
 511     /**
 512      * Return a random string of the specified length composed of A-Z,a-z,0-9
 513      */
 514     fn gen_str(&mut self, len: uint) -> ~str {
 515         let charset = ~"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
 516                        abcdefghijklmnopqrstuvwxyz\
 517                        0123456789";
 518         let mut s = ~"";
 519         let mut i = 0u;
 520         while (i < len) {
 521             s = s + str::from_char(self.gen_char_from(charset));
 522             i += 1u;
 523         }
 524         s
 525     }
 526
 527     /// Return a random byte string of the specified length
 528     fn gen_bytes(&mut self, len: uint) -> ~[u8] {
 529         do vec::from_fn(len) |_i| {
 530             self.gen()
 531         }
 532     }
 533
 534     /// Choose an item randomly, failing if values is empty
 535     fn choose<T:Clone>(&mut self, values: &[T]) -> T {
 536         self.choose_option(values).unwrap()
 537     }
 538
 539     /// Choose Some(item) randomly, returning None if values is empty
 540     fn choose_option<T:Clone>(&mut self, values: &[T]) -> Option<T> {
 541         if values.is_empty() {
 542             None
 543         } else {
 544             Some(values[self.gen_uint_range(0u, values.len())].clone())
 545         }
 546     }
 547     /**
 548      * Choose an item respecting the relative weights, failing if the sum of
 549      * the weights is 0
 550      */
 551     fn choose_weighted<T:Clone>(&mut self, v: &[Weighted<T>]) -> T {
 552         self.choose_weighted_option(v).unwrap()
 553     }
 554
 555     /**
 556      * Choose Some(item) respecting the relative weights, returning none if
 557      * the sum of the weights is 0
 558      */
 559     fn choose_weighted_option<T:Clone>(&mut self, v: &[Weighted<T>])
 560                                        -> Option<T> {
 561         let mut total = 0u;
 562         for item in v.iter() {
 563             total += item.weight;
 564         }
 565         if total == 0u {
 566             return None;
 567         }
 568         let chosen = self.gen_uint_range(0u, total);
 569         let mut so_far = 0u;
 570         for item in v.iter() {
 571             so_far += item.weight;
 572             if so_far > chosen {
 573                 return Some(item.item.clone());
 574             }
 575         }
 576         util::unreachable();
 577     }
 578
 579     /**
 580      * Return a vec containing copies of the items, in order, where
 581      * the weight of the item determines how many copies there are
 582      */
 583     fn weighted_vec<T:Clone>(&mut self, v: &[Weighted<T>]) -> ~[T] {
 584         let mut r = ~[];
 585         for item in v.iter() {
 586             for _ in range(0u, item.weight) {
 587                 r.push(item.item.clone());
 588             }
 589         }
 590         r
 591     }
 592
 593     /// Shuffle a vec
 594     fn shuffle<T:Clone>(&mut self, values: &[T]) -> ~[T] {
 595         let mut m = values.to_owned();
 596         self.shuffle_mut(m);
 597         m
 598     }
 599
 600     /// Shuffle a mutable vec in place
 601     fn shuffle_mut<T>(&mut self, values: &mut [T]) {
 602         let mut i = values.len();
 603         while i >= 2u {
 604             // invariant: elements with index >= i have been locked in place.
 605             i -= 1u;
 606             // lock element i in place.
 607             values.swap(i, self.gen_uint_range(0u, i + 1u));
 608         }
 609     }
 610 }
 611
 612 /// Create a random number generator with a default algorithm and seed.
 613 ///
 614 /// It returns the cryptographically-safest `Rng` algorithm currently
 615 /// available in Rust. If you require a specifically seeded `Rng` for
 616 /// consistency over time you should pick one algorithm and create the
 617 /// `Rng` yourself.
 618 pub fn rng() -> IsaacRng {
 619     IsaacRng::new()
 620 }
 621
 622 static RAND_SIZE_LEN: u32 = 8;
 623 static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN;
 624
 625 /// A random number generator that uses the [ISAAC
 626 /// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29).
 627 ///
 628 /// The ISAAC algorithm is suitable for cryptographic purposes.
 629 pub struct IsaacRng {
 630     priv cnt: u32,
 631     priv rsl: [u32, .. RAND_SIZE],
 632     priv mem: [u32, .. RAND_SIZE],
 633     priv a: u32,
 634     priv b: u32,
 635     priv c: u32
 636 }
 637
 638 impl IsaacRng {
 639     /// Create an ISAAC random number generator with a random seed.
 640     pub fn new() -> IsaacRng {
 641         IsaacRng::new_seeded(seed())
 642     }
 643
 644     /// Create an ISAAC random number generator with a seed. This can be any
 645     /// length, although the maximum number of bytes used is 1024 and any more
 646     /// will be silently ignored. A generator constructed with a given seed
 647     /// will generate the same sequence of values as all other generators
 648     /// constructed with the same seed.
 649     pub fn new_seeded(seed: &[u8]) -> IsaacRng {
 650         let mut rng = IsaacRng {
 651             cnt: 0,
 652             rsl: [0, .. RAND_SIZE],
 653             mem: [0, .. RAND_SIZE],
 654             a: 0, b: 0, c: 0
 655         };
 656
 657         let array_size = sys::size_of_val(&rng.rsl);
 658         let copy_length = cmp::min(array_size, seed.len());
 659
 660         // manually create a &mut [u8] slice of randrsl to copy into.
 661         let dest = unsafe { cast::transmute((&mut rng.rsl, array_size)) };
 662         vec::bytes::copy_memory(dest, seed, copy_length);
 663         rng.init(true);
 664         rng
 665     }
 666
 667     /// Create an ISAAC random number generator using the default
 668     /// fixed seed.
 669     pub fn new_unseeded() -> IsaacRng {
 670         let mut rng = IsaacRng {
 671             cnt: 0,
 672             rsl: [0, .. RAND_SIZE],
 673             mem: [0, .. RAND_SIZE],
 674             a: 0, b: 0, c: 0
 675         };
 676         rng.init(false);
 677         rng
 678     }
 679
 680     /// Initialises `self`. If `use_rsl` is true, then use the current value
 681     /// of `rsl` as a seed, otherwise construct one algorithmically (not
 682     /// randomly).
 683     fn init(&mut self, use_rsl: bool) {
 684         let mut a = 0x9e3779b9;
 685         let mut b = a;
 686         let mut c = a;
 687         let mut d = a;
 688         let mut e = a;
 689         let mut f = a;
 690         let mut g = a;
 691         let mut h = a;
 692
 693         macro_rules! mix(
 694             () => {{
 695                 a^=b<<11; d+=a; b+=c;
 696                 b^=c>>2;  e+=b; c+=d;
 697                 c^=d<<8;  f+=c; d+=e;
 698                 d^=e>>16; g+=d; e+=f;
 699                 e^=f<<10; h+=e; f+=g;
 700                 f^=g>>4;  a+=f; g+=h;
 701                 g^=h<<8;  b+=g; h+=a;
 702                 h^=a>>9;  c+=h; a+=b;
 703             }}
 704         );
 705
 706         do 4.times { mix!(); }
 707
 708         if use_rsl {
 709             macro_rules! memloop (
 710                 ($arr:expr) => {{
 711                     do u32::range_step(0, RAND_SIZE, 8) |i| {
 712                         a+=$arr[i  ]; b+=$arr[i+1];
 713                         c+=$arr[i+2]; d+=$arr[i+3];
 714                         e+=$arr[i+4]; f+=$arr[i+5];
 715                         g+=$arr[i+6]; h+=$arr[i+7];
 716                         mix!();
 717                         self.mem[i  ]=a; self.mem[i+1]=b;
 718                         self.mem[i+2]=c; self.mem[i+3]=d;
 719                         self.mem[i+4]=e; self.mem[i+5]=f;
 720                         self.mem[i+6]=g; self.mem[i+7]=h;
 721                         true
 722                     };
 723                 }}
 724             );
 725
 726             memloop!(self.rsl);
 727             memloop!(self.mem);
 728         } else {
 729             do u32::range_step(0, RAND_SIZE, 8) |i| {
 730                 mix!();
 731                 self.mem[i  ]=a; self.mem[i+1]=b;
 732                 self.mem[i+2]=c; self.mem[i+3]=d;
 733                 self.mem[i+4]=e; self.mem[i+5]=f;
 734                 self.mem[i+6]=g; self.mem[i+7]=h;
 735                 true
 736             };
 737         }
 738
 739         self.isaac();
 740     }
 741
 742     /// Refills the output buffer (`self.rsl`)
 743     #[inline]
 744     fn isaac(&mut self) {
 745         self.c += 1;
 746         // abbreviations
 747         let mut a = self.a;
 748         let mut b = self.b + self.c;
 749
 750         static MIDPOINT: uint = RAND_SIZE as uint / 2;
 751
 752         macro_rules! ind (($x:expr) => {
 753             self.mem[($x >> 2) & (RAND_SIZE - 1)]
 754         });
 755         macro_rules! rngstep(
 756             ($j:expr, $shift:expr) => {{
 757                 let base = base + $j;
 758                 let mix = if $shift < 0 {
 759                     a >> -$shift as uint
 760                 } else {
 761                     a << $shift as uint
 762                 };
 763
 764                 let x = self.mem[base  + mr_offset];
 765                 a = (a ^ mix) + self.mem[base + m2_offset];
 766                 let y = ind!(x) + a + b;
 767                 self.mem[base + mr_offset] = y;
 768
 769                 b = ind!(y >> RAND_SIZE_LEN) + x;
 770                 self.rsl[base + mr_offset] = b;
 771             }}
 772         );
 773
 774         let r = [(0, MIDPOINT), (MIDPOINT, 0)];
 775         for &(mr_offset, m2_offset) in r.iter() {
 776             do uint::range_step(0, MIDPOINT, 4) |base| {
 777                 rngstep!(0, 13);
 778                 rngstep!(1, -6);
 779                 rngstep!(2, 2);
 780                 rngstep!(3, -16);
 781                 true
 782             };
 783         }
 784
 785         self.a = a;
 786         self.b = b;
 787         self.cnt = RAND_SIZE;
 788     }
 789 }
 790
 791 impl Rng for IsaacRng {
 792     #[inline]
 793     fn next(&mut self) -> u32 {
 794         if self.cnt == 0 {
 795             // make some more numbers
 796             self.isaac();
 797         }
 798         self.cnt -= 1;
 799         self.rsl[self.cnt]
 800     }
 801 }
 802
 803 /// An [Xorshift random number
 804 /// generator](http://en.wikipedia.org/wiki/Xorshift).
 805 ///
 806 /// The Xorshift algorithm is not suitable for cryptographic purposes
 807 /// but is very fast. If you do not know for sure that it fits your
 808 /// requirements, use a more secure one such as `IsaacRng`.
 809 pub struct XorShiftRng {
 810     priv x: u32,
 811     priv y: u32,
 812     priv z: u32,
 813     priv w: u32,
 814 }
 815
 816 impl Rng for XorShiftRng {
 817     #[inline]
 818     pub fn next(&mut self) -> u32 {
 819         let x = self.x;
 820         let t = x ^ (x << 11);
 821         self.x = self.y;
 822         self.y = self.z;
 823         self.z = self.w;
 824         let w = self.w;
 825         self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
 826         self.w
 827     }
 828 }
 829
 830 impl XorShiftRng {
 831     /// Create an xor shift random number generator with a default seed.
 832     pub fn new() -> XorShiftRng {
 833         // constants taken from http://en.wikipedia.org/wiki/Xorshift
 834         XorShiftRng::new_seeded(123456789u32,
 835                                 362436069u32,
 836                                 521288629u32,
 837                                 88675123u32)
 838     }
 839
 840     /**
 841      * Create a random number generator using the specified seed. A generator
 842      * constructed with a given seed will generate the same sequence of values
 843      * as all other generators constructed with the same seed.
 844      */
 845     pub fn new_seeded(x: u32, y: u32, z: u32, w: u32) -> XorShiftRng {
 846         XorShiftRng {
 847             x: x,
 848             y: y,
 849             z: z,
 850             w: w,
 851         }
 852     }
 853 }
 854
 855 /// Create a new random seed.
 856 pub fn seed() -> ~[u8] {
 857     unsafe {
 858         let n = rustrt::rand_seed_size() as uint;
 859         let mut s = vec::from_elem(n, 0_u8);
 860         do s.as_mut_buf |p, sz| {
 861             rustrt::rand_gen_seed(p, sz as size_t)
 862         }
 863         s
 864     }
 865 }
 866
 867 // used to make space in TLS for a random number generator
 868 static tls_rng_state: local_data::Key<@@mut IsaacRng> = &local_data::Key;
 869
 870 /**
 871  * Gives back a lazily initialized task-local random number generator,
 872  * seeded by the system. Intended to be used in method chaining style, ie
 873  * `task_rng().gen::<int>()`.
 874  */
 875 #[inline]
 876 pub fn task_rng() -> @mut IsaacRng {
 877     let r = local_data::get(tls_rng_state, |k| k.map(|&k| *k));
 878     match r {
 879         None => {
 880             let rng = @@mut IsaacRng::new_seeded(seed());
 881             local_data::set(tls_rng_state, rng);
 882             *rng
 883         }
 884         Some(rng) => *rng
 885     }
 886 }
 887
 888 // Allow direct chaining with `task_rng`
 889 impl<R: Rng> Rng for @mut R {
 890     #[inline]
 891     fn next(&mut self) -> u32 {
 892         (**self).next()
 893     }
 894 }
 895
 896 /**
 897  * Returns a random value of a Rand type, using the task's random number
 898  * generator.
 899  */
 900 #[inline]
 901 pub fn random<T: Rand>() -> T {
 902     task_rng().gen()
 903 }
 904
 905 #[cfg(test)]
 906 mod test {
 907     use option::{Option, Some};
 908     use super::*;
 909
 910     #[test]
 911     fn test_rng_seeded() {
 912         let seed = seed();
 913         let mut ra = IsaacRng::new_seeded(seed);
 914         let mut rb = IsaacRng::new_seeded(seed);
 915         assert_eq!(ra.gen_str(100u), rb.gen_str(100u));
 916     }
 917
 918     #[test]
 919     fn test_rng_seeded_custom_seed() {
 920         // much shorter than generated seeds which are 1024 bytes
 921         let seed = [2u8, 32u8, 4u8, 32u8, 51u8];
 922         let mut ra = IsaacRng::new_seeded(seed);
 923         let mut rb = IsaacRng::new_seeded(seed);
 924         assert_eq!(ra.gen_str(100u), rb.gen_str(100u));
 925     }
 926
 927     #[test]
 928     fn test_rng_seeded_custom_seed2() {
 929         let seed = [2u8, 32u8, 4u8, 32u8, 51u8];
 930         let mut ra = IsaacRng::new_seeded(seed);
 931         // Regression test that isaac is actually using the above vector
 932         let r = ra.next();
 933         error!("%?", r);
 934         assert!(r == 890007737u32 // on x86_64
 935                      || r == 2935188040u32); // on x86
 936     }
 937
 938     #[test]
 939     fn test_gen_int_range() {
 940         let mut r = rng();
 941         let a = r.gen_int_range(-3, 42);
 942         assert!(a >= -3 && a < 42);
 943         assert_eq!(r.gen_int_range(0, 1), 0);
 944         assert_eq!(r.gen_int_range(-12, -11), -12);
 945     }
 946
 947     #[test]
 948     #[should_fail]
 949     #[ignore(cfg(windows))]
 950     fn test_gen_int_from_fail() {
 951         let mut r = rng();
 952         r.gen_int_range(5, -2);
 953     }
 954
 955     #[test]
 956     fn test_gen_uint_range() {
 957         let mut r = rng();
 958         let a = r.gen_uint_range(3u, 42u);
 959         assert!(a >= 3u && a < 42u);
 960         assert_eq!(r.gen_uint_range(0u, 1u), 0u);
 961         assert_eq!(r.gen_uint_range(12u, 13u), 12u);
 962     }
 963
 964     #[test]
 965     #[should_fail]
 966     #[ignore(cfg(windows))]
 967     fn test_gen_uint_range_fail() {
 968         let mut r = rng();
 969         r.gen_uint_range(5u, 2u);
 970     }
 971
 972     #[test]
 973     fn test_gen_float() {
 974         let mut r = rng();
 975         let a = r.gen::<float>();
 976         let b = r.gen::<float>();
 977         debug!((a, b));
 978     }
 979
 980     #[test]
 981     fn test_gen_weighted_bool() {
 982         let mut r = rng();
 983         assert_eq!(r.gen_weighted_bool(0u), true);
 984         assert_eq!(r.gen_weighted_bool(1u), true);
 985     }
 986
 987     #[test]
 988     fn test_gen_str() {
 989         let mut r = rng();
 990         debug!(r.gen_str(10u));
 991         debug!(r.gen_str(10u));
 992         debug!(r.gen_str(10u));
 993         assert_eq!(r.gen_str(0u).len(), 0u);
 994         assert_eq!(r.gen_str(10u).len(), 10u);
 995         assert_eq!(r.gen_str(16u).len(), 16u);
 996     }
 997
 998     #[test]
 999     fn test_gen_bytes() {
1000         let mut r = rng();
1001         assert_eq!(r.gen_bytes(0u).len(), 0u);
1002         assert_eq!(r.gen_bytes(10u).len(), 10u);
1003         assert_eq!(r.gen_bytes(16u).len(), 16u);
1004     }
1005
1006     #[test]
1007     fn test_choose() {
1008         let mut r = rng();
1009         assert_eq!(r.choose([1, 1, 1]), 1);
1010     }
1011
1012     #[test]
1013     fn test_choose_option() {
1014         let mut r = rng();
1015         let x: Option<int> = r.choose_option([]);
1016         assert!(x.is_none());
1017         assert_eq!(r.choose_option([1, 1, 1]), Some(1));
1018     }
1019
1020     #[test]
1021     fn test_choose_weighted() {
1022         let mut r = rng();
1023         assert!(r.choose_weighted([
1024             Weighted { weight: 1u, item: 42 },
1025         ]) == 42);
1026         assert!(r.choose_weighted([
1027             Weighted { weight: 0u, item: 42 },
1028             Weighted { weight: 1u, item: 43 },
1029         ]) == 43);
1030     }
1031
1032     #[test]
1033     fn test_choose_weighted_option() {
1034         let mut r = rng();
1035         assert!(r.choose_weighted_option([
1036             Weighted { weight: 1u, item: 42 },
1037         ]) == Some(42));
1038         assert!(r.choose_weighted_option([
1039             Weighted { weight: 0u, item: 42 },
1040             Weighted { weight: 1u, item: 43 },
1041         ]) == Some(43));
1042         let v: Option<int> = r.choose_weighted_option([]);
1043         assert!(v.is_none());
1044     }
1045
1046     #[test]
1047     fn test_weighted_vec() {
1048         let mut r = rng();
1049         let empty: ~[int] = ~[];
1050         assert_eq!(r.weighted_vec([]), empty);
1051         assert!(r.weighted_vec([
1052             Weighted { weight: 0u, item: 3u },
1053             Weighted { weight: 1u, item: 2u },
1054             Weighted { weight: 2u, item: 1u },
1055         ]) == ~[2u, 1u, 1u]);
1056     }
1057
1058     #[test]
1059     fn test_shuffle() {
1060         let mut r = rng();
1061         let empty: ~[int] = ~[];
1062         assert_eq!(r.shuffle([]), empty);
1063         assert_eq!(r.shuffle([1, 1, 1]), ~[1, 1, 1]);
1064     }
1065
1066     #[test]
1067     fn test_task_rng() {
1068         let mut r = task_rng();
1069         r.gen::<int>();
1070         assert_eq!(r.shuffle([1, 1, 1]), ~[1, 1, 1]);
1071         assert_eq!(r.gen_uint_range(0u, 1u), 0u);
1072     }
1073
1074     #[test]
1075     fn test_random() {
1076         // not sure how to test this aside from just getting some values
1077         let _n : uint = random();
1078         let _f : f32 = random();
1079         let _o : Option<Option<i8>> = random();
1080         let _many : ((),
1081                      (~uint, @int, ~Option<~(@char, ~(@bool,))>),
1082                      (u8, i8, u16, i16, u32, i32, u64, i64),
1083                      (f32, (f64, (float,)))) = random();
1084     }
1085
1086     #[test]
1087     fn compare_isaac_implementation() {
1088         // This is to verify that the implementation of the ISAAC rng is
1089         // correct (i.e. matches the output of the upstream implementation,
1090         // which is in the runtime)
1091         use libc::size_t;
1092
1093         #[abi = "cdecl"]
1094         mod rustrt {
1095             use libc::size_t;
1096
1097             #[allow(non_camel_case_types)] // runtime type
1098             pub enum rust_rng {}
1099
1100             extern {
1101                 pub fn rand_new_seeded(buf: *u8, sz: size_t) -> *rust_rng;
1102                 pub fn rand_next(rng: *rust_rng) -> u32;
1103                 pub fn rand_free(rng: *rust_rng);
1104             }
1105         }
1106
1107         // run against several seeds
1108         do 10.times {
1109             unsafe {
1110                 let seed = super::seed();
1111                 let rt_rng = do seed.as_imm_buf |p, sz| {
1112                     rustrt::rand_new_seeded(p, sz as size_t)
1113                 };
1114                 let mut rng = IsaacRng::new_seeded(seed);
1115
1116                 do 10000.times {
1117                     assert_eq!(rng.next(), rustrt::rand_next(rt_rng));
1118                 }
1119                 rustrt::rand_free(rt_rng);
1120             }
1121         }
1122     }
1123 }
1124
1125 #[cfg(test)]
1126 mod bench {
1127     use extra::test::BenchHarness;
1128     use rand::*;
1129     use sys::size_of;
1130
1131     #[bench]
1132     fn rand_xorshift(bh: &mut BenchHarness) {
1133         let mut rng = XorShiftRng::new();
1134         do bh.iter {
1135             rng.gen::<uint>();
1136         }
1137         bh.bytes = size_of::<uint>() as u64;
1138     }
1139
1140     #[bench]
1141     fn rand_isaac(bh: &mut BenchHarness) {
1142         let mut rng = IsaacRng::new();
1143         do bh.iter {
1144             rng.gen::<uint>();
1145         }
1146         bh.bytes = size_of::<uint>() as u64;
1147     }
1148
1149     #[bench]
1150     fn rand_shuffle_100(bh: &mut BenchHarness) {
1151         let mut rng = XorShiftRng::new();
1152         let x : &mut[uint] = [1,..100];
1153         do bh.iter {
1154             rng.shuffle_mut(x);
1155         }
1156     }
1157 }