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::IteratorUtil;
  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 unsafe fn rand_seed_size() -> size_t;
 256         pub unsafe 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 chars.iter().advance |c| { 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).get()
 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).get()
 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 v.iter().advance |item| {
 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 v.iter().advance |item| {
 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 v.iter().advance |item| {
 586             for uint::range(0u, item.weight) |_i| {
 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 pub fn rng() -> IsaacRng {
 614     IsaacRng::new()
 615 }
 616
 617 static RAND_SIZE_LEN: u32 = 8;
 618 static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN;
 619
 620 /// A random number generator that uses the [ISAAC
 621 /// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29).
 622 pub struct IsaacRng {
 623     priv cnt: u32,
 624     priv rsl: [u32, .. RAND_SIZE],
 625     priv mem: [u32, .. RAND_SIZE],
 626     priv a: u32,
 627     priv b: u32,
 628     priv c: u32
 629 }
 630
 631 impl IsaacRng {
 632     /// Create an ISAAC random number generator with a random seed.
 633     pub fn new() -> IsaacRng {
 634         IsaacRng::new_seeded(seed())
 635     }
 636
 637     /// Create an ISAAC random number generator with a seed. This can be any
 638     /// length, although the maximum number of bytes used is 1024 and any more
 639     /// will be silently ignored. A generator constructed with a given seed
 640     /// will generate the same sequence of values as all other generators
 641     /// constructed with the same seed.
 642     pub fn new_seeded(seed: &[u8]) -> IsaacRng {
 643         let mut rng = IsaacRng {
 644             cnt: 0,
 645             rsl: [0, .. RAND_SIZE],
 646             mem: [0, .. RAND_SIZE],
 647             a: 0, b: 0, c: 0
 648         };
 649
 650         let array_size = sys::size_of_val(&rng.rsl);
 651         let copy_length = cmp::min(array_size, seed.len());
 652
 653         // manually create a &mut [u8] slice of randrsl to copy into.
 654         let dest = unsafe { cast::transmute((&mut rng.rsl, array_size)) };
 655         vec::bytes::copy_memory(dest, seed, copy_length);
 656         rng.init(true);
 657         rng
 658     }
 659
 660     /// Create an ISAAC random number generator using the default
 661     /// fixed seed.
 662     pub fn new_unseeded() -> IsaacRng {
 663         let mut rng = IsaacRng {
 664             cnt: 0,
 665             rsl: [0, .. RAND_SIZE],
 666             mem: [0, .. RAND_SIZE],
 667             a: 0, b: 0, c: 0
 668         };
 669         rng.init(false);
 670         rng
 671     }
 672
 673     /// Initialises `self`. If `use_rsl` is true, then use the current value
 674     /// of `rsl` as a seed, otherwise construct one algorithmically (not
 675     /// randomly).
 676     fn init(&mut self, use_rsl: bool) {
 677         let mut a = 0x9e3779b9;
 678         let mut b = a;
 679         let mut c = a;
 680         let mut d = a;
 681         let mut e = a;
 682         let mut f = a;
 683         let mut g = a;
 684         let mut h = a;
 685
 686         macro_rules! mix(
 687             () => {{
 688                 a^=b<<11; d+=a; b+=c;
 689                 b^=c>>2;  e+=b; c+=d;
 690                 c^=d<<8;  f+=c; d+=e;
 691                 d^=e>>16; g+=d; e+=f;
 692                 e^=f<<10; h+=e; f+=g;
 693                 f^=g>>4;  a+=f; g+=h;
 694                 g^=h<<8;  b+=g; h+=a;
 695                 h^=a>>9;  c+=h; a+=b;
 696             }}
 697         );
 698
 699         for 4.times { mix!(); }
 700
 701         if use_rsl {
 702             macro_rules! memloop (
 703                 ($arr:expr) => {{
 704                     for u32::range_step(0, RAND_SIZE, 8) |i| {
 705                         a+=$arr[i  ]; b+=$arr[i+1];
 706                         c+=$arr[i+2]; d+=$arr[i+3];
 707                         e+=$arr[i+4]; f+=$arr[i+5];
 708                         g+=$arr[i+6]; h+=$arr[i+7];
 709                         mix!();
 710                         self.mem[i  ]=a; self.mem[i+1]=b;
 711                         self.mem[i+2]=c; self.mem[i+3]=d;
 712                         self.mem[i+4]=e; self.mem[i+5]=f;
 713                         self.mem[i+6]=g; self.mem[i+7]=h;
 714                     }
 715                 }}
 716             );
 717
 718             memloop!(self.rsl);
 719             memloop!(self.mem);
 720         } else {
 721             for u32::range_step(0, RAND_SIZE, 8) |i| {
 722                 mix!();
 723                 self.mem[i  ]=a; self.mem[i+1]=b;
 724                 self.mem[i+2]=c; self.mem[i+3]=d;
 725                 self.mem[i+4]=e; self.mem[i+5]=f;
 726                 self.mem[i+6]=g; self.mem[i+7]=h;
 727             }
 728         }
 729
 730         self.isaac();
 731     }
 732
 733     /// Refills the output buffer (`self.rsl`)
 734     #[inline]
 735     fn isaac(&mut self) {
 736         self.c += 1;
 737         // abbreviations
 738         let mut a = self.a;
 739         let mut b = self.b + self.c;
 740
 741         static MIDPOINT: uint = RAND_SIZE as uint / 2;
 742
 743         macro_rules! ind (($x:expr) => {
 744             self.mem[($x >> 2) & (RAND_SIZE - 1)]
 745         });
 746         macro_rules! rngstep(
 747             ($j:expr, $shift:expr) => {{
 748                 let base = base + $j;
 749                 let mix = if $shift < 0 {
 750                     a >> -$shift as uint
 751                 } else {
 752                     a << $shift as uint
 753                 };
 754
 755                 let x = self.mem[base  + mr_offset];
 756                 a = (a ^ mix) + self.mem[base + m2_offset];
 757                 let y = ind!(x) + a + b;
 758                 self.mem[base + mr_offset] = y;
 759
 760                 b = ind!(y >> RAND_SIZE_LEN) + x;
 761                 self.rsl[base + mr_offset] = b;
 762             }}
 763         );
 764
 765         let r = [(0, MIDPOINT), (MIDPOINT, 0)];
 766         for r.iter().advance |&(mr_offset, m2_offset)| {
 767             for uint::range_step(0, MIDPOINT, 4) |base| {
 768                 rngstep!(0, 13);
 769                 rngstep!(1, -6);
 770                 rngstep!(2, 2);
 771                 rngstep!(3, -16);
 772             }
 773         }
 774
 775         self.a = a;
 776         self.b = b;
 777         self.cnt = RAND_SIZE;
 778     }
 779 }
 780
 781 impl Rng for IsaacRng {
 782     #[inline]
 783     fn next(&mut self) -> u32 {
 784         if self.cnt == 0 {
 785             // make some more numbers
 786             self.isaac();
 787         }
 788         self.cnt -= 1;
 789         self.rsl[self.cnt]
 790     }
 791 }
 792
 793 /// An [Xorshift random number
 794 /// generator](http://en.wikipedia.org/wiki/Xorshift). Not suitable for
 795 /// cryptographic purposes.
 796 pub struct XorShiftRng {
 797     priv x: u32,
 798     priv y: u32,
 799     priv z: u32,
 800     priv w: u32,
 801 }
 802
 803 impl Rng for XorShiftRng {
 804     #[inline]
 805     pub fn next(&mut self) -> u32 {
 806         let x = self.x;
 807         let t = x ^ (x << 11);
 808         self.x = self.y;
 809         self.y = self.z;
 810         self.z = self.w;
 811         let w = self.w;
 812         self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
 813         self.w
 814     }
 815 }
 816
 817 impl XorShiftRng {
 818     /// Create an xor shift random number generator with a default seed.
 819     pub fn new() -> XorShiftRng {
 820         // constants taken from http://en.wikipedia.org/wiki/Xorshift
 821         XorShiftRng::new_seeded(123456789u32,
 822                                 362436069u32,
 823                                 521288629u32,
 824                                 88675123u32)
 825     }
 826
 827     /**
 828      * Create a random number generator using the specified seed. A generator
 829      * constructed with a given seed will generate the same sequence of values
 830      * as all other generators constructed with the same seed.
 831      */
 832     pub fn new_seeded(x: u32, y: u32, z: u32, w: u32) -> XorShiftRng {
 833         XorShiftRng {
 834             x: x,
 835             y: y,
 836             z: z,
 837             w: w,
 838         }
 839     }
 840 }
 841
 842 /// Create a new random seed.
 843 pub fn seed() -> ~[u8] {
 844     unsafe {
 845         let n = rustrt::rand_seed_size() as uint;
 846         let mut s = vec::from_elem(n, 0_u8);
 847         do s.as_mut_buf |p, sz| {
 848             rustrt::rand_gen_seed(p, sz as size_t)
 849         }
 850         s
 851     }
 852 }
 853
 854 // used to make space in TLS for a random number generator
 855 static tls_rng_state: local_data::Key<@@mut IsaacRng> = &local_data::Key;
 856
 857 /**
 858  * Gives back a lazily initialized task-local random number generator,
 859  * seeded by the system. Intended to be used in method chaining style, ie
 860  * `task_rng().gen::<int>()`.
 861  */
 862 #[inline]
 863 pub fn task_rng() -> @mut IsaacRng {
 864     let r = local_data::get(tls_rng_state, |k| k.map(|&k| *k));
 865     match r {
 866         None => {
 867             let rng = @@mut IsaacRng::new_seeded(seed());
 868             local_data::set(tls_rng_state, rng);
 869             *rng
 870         }
 871         Some(rng) => *rng
 872     }
 873 }
 874
 875 // Allow direct chaining with `task_rng`
 876 impl<R: Rng> Rng for @mut R {
 877     #[inline]
 878     fn next(&mut self) -> u32 {
 879         (**self).next()
 880     }
 881 }
 882
 883 /**
 884  * Returns a random value of a Rand type, using the task's random number
 885  * generator.
 886  */
 887 #[inline]
 888 pub fn random<T: Rand>() -> T {
 889     task_rng().gen()
 890 }
 891
 892 #[cfg(test)]
 893 mod test {
 894     use option::{Option, Some};
 895     use super::*;
 896
 897     #[test]
 898     fn test_rng_seeded() {
 899         let seed = seed();
 900         let mut ra = IsaacRng::new_seeded(seed);
 901         let mut rb = IsaacRng::new_seeded(seed);
 902         assert_eq!(ra.gen_str(100u), rb.gen_str(100u));
 903     }
 904
 905     #[test]
 906     fn test_rng_seeded_custom_seed() {
 907         // much shorter than generated seeds which are 1024 bytes
 908         let seed = [2u8, 32u8, 4u8, 32u8, 51u8];
 909         let mut ra = IsaacRng::new_seeded(seed);
 910         let mut rb = IsaacRng::new_seeded(seed);
 911         assert_eq!(ra.gen_str(100u), rb.gen_str(100u));
 912     }
 913
 914     #[test]
 915     fn test_rng_seeded_custom_seed2() {
 916         let seed = [2u8, 32u8, 4u8, 32u8, 51u8];
 917         let mut ra = IsaacRng::new_seeded(seed);
 918         // Regression test that isaac is actually using the above vector
 919         let r = ra.next();
 920         error!("%?", r);
 921         assert!(r == 890007737u32 // on x86_64
 922                      || r == 2935188040u32); // on x86
 923     }
 924
 925     #[test]
 926     fn test_gen_int_range() {
 927         let mut r = rng();
 928         let a = r.gen_int_range(-3, 42);
 929         assert!(a >= -3 && a < 42);
 930         assert_eq!(r.gen_int_range(0, 1), 0);
 931         assert_eq!(r.gen_int_range(-12, -11), -12);
 932     }
 933
 934     #[test]
 935     #[should_fail]
 936     #[ignore(cfg(windows))]
 937     fn test_gen_int_from_fail() {
 938         let mut r = rng();
 939         r.gen_int_range(5, -2);
 940     }
 941
 942     #[test]
 943     fn test_gen_uint_range() {
 944         let mut r = rng();
 945         let a = r.gen_uint_range(3u, 42u);
 946         assert!(a >= 3u && a < 42u);
 947         assert_eq!(r.gen_uint_range(0u, 1u), 0u);
 948         assert_eq!(r.gen_uint_range(12u, 13u), 12u);
 949     }
 950
 951     #[test]
 952     #[should_fail]
 953     #[ignore(cfg(windows))]
 954     fn test_gen_uint_range_fail() {
 955         let mut r = rng();
 956         r.gen_uint_range(5u, 2u);
 957     }
 958
 959     #[test]
 960     fn test_gen_float() {
 961         let mut r = rng();
 962         let a = r.gen::<float>();
 963         let b = r.gen::<float>();
 964         debug!((a, b));
 965     }
 966
 967     #[test]
 968     fn test_gen_weighted_bool() {
 969         let mut r = rng();
 970         assert_eq!(r.gen_weighted_bool(0u), true);
 971         assert_eq!(r.gen_weighted_bool(1u), true);
 972     }
 973
 974     #[test]
 975     fn test_gen_str() {
 976         let mut r = rng();
 977         debug!(r.gen_str(10u));
 978         debug!(r.gen_str(10u));
 979         debug!(r.gen_str(10u));
 980         assert_eq!(r.gen_str(0u).len(), 0u);
 981         assert_eq!(r.gen_str(10u).len(), 10u);
 982         assert_eq!(r.gen_str(16u).len(), 16u);
 983     }
 984
 985     #[test]
 986     fn test_gen_bytes() {
 987         let mut r = rng();
 988         assert_eq!(r.gen_bytes(0u).len(), 0u);
 989         assert_eq!(r.gen_bytes(10u).len(), 10u);
 990         assert_eq!(r.gen_bytes(16u).len(), 16u);
 991     }
 992
 993     #[test]
 994     fn test_choose() {
 995         let mut r = rng();
 996         assert_eq!(r.choose([1, 1, 1]), 1);
 997     }
 998
 999     #[test]
1000     fn test_choose_option() {
1001         let mut r = rng();
1002         let x: Option<int> = r.choose_option([]);
1003         assert!(x.is_none());
1004         assert_eq!(r.choose_option([1, 1, 1]), Some(1));
1005     }
1006
1007     #[test]
1008     fn test_choose_weighted() {
1009         let mut r = rng();
1010         assert!(r.choose_weighted([
1011             Weighted { weight: 1u, item: 42 },
1012         ]) == 42);
1013         assert!(r.choose_weighted([
1014             Weighted { weight: 0u, item: 42 },
1015             Weighted { weight: 1u, item: 43 },
1016         ]) == 43);
1017     }
1018
1019     #[test]
1020     fn test_choose_weighted_option() {
1021         let mut r = rng();
1022         assert!(r.choose_weighted_option([
1023             Weighted { weight: 1u, item: 42 },
1024         ]) == Some(42));
1025         assert!(r.choose_weighted_option([
1026             Weighted { weight: 0u, item: 42 },
1027             Weighted { weight: 1u, item: 43 },
1028         ]) == Some(43));
1029         let v: Option<int> = r.choose_weighted_option([]);
1030         assert!(v.is_none());
1031     }
1032
1033     #[test]
1034     fn test_weighted_vec() {
1035         let mut r = rng();
1036         let empty: ~[int] = ~[];
1037         assert_eq!(r.weighted_vec([]), empty);
1038         assert!(r.weighted_vec([
1039             Weighted { weight: 0u, item: 3u },
1040             Weighted { weight: 1u, item: 2u },
1041             Weighted { weight: 2u, item: 1u },
1042         ]) == ~[2u, 1u, 1u]);
1043     }
1044
1045     #[test]
1046     fn test_shuffle() {
1047         let mut r = rng();
1048         let empty: ~[int] = ~[];
1049         assert_eq!(r.shuffle([]), empty);
1050         assert_eq!(r.shuffle([1, 1, 1]), ~[1, 1, 1]);
1051     }
1052
1053     #[test]
1054     fn test_task_rng() {
1055         let mut r = task_rng();
1056         r.gen::<int>();
1057         assert_eq!(r.shuffle([1, 1, 1]), ~[1, 1, 1]);
1058         assert_eq!(r.gen_uint_range(0u, 1u), 0u);
1059     }
1060
1061     #[test]
1062     fn test_random() {
1063         // not sure how to test this aside from just getting some values
1064         let _n : uint = random();
1065         let _f : f32 = random();
1066         let _o : Option<Option<i8>> = random();
1067         let _many : ((),
1068                      (~uint, @int, ~Option<~(@char, ~(@bool,))>),
1069                      (u8, i8, u16, i16, u32, i32, u64, i64),
1070                      (f32, (f64, (float,)))) = random();
1071     }
1072
1073     #[test]
1074     fn compare_isaac_implementation() {
1075         // This is to verify that the implementation of the ISAAC rng is
1076         // correct (i.e. matches the output of the upstream implementation,
1077         // which is in the runtime)
1078         use libc::size_t;
1079
1080         #[abi = "cdecl"]
1081         mod rustrt {
1082             use libc::size_t;
1083
1084             #[allow(non_camel_case_types)] // runtime type
1085             pub enum rust_rng {}
1086
1087             extern {
1088                 pub unsafe fn rand_new_seeded(buf: *u8, sz: size_t)
1089                                               -> *rust_rng;
1090                 pub unsafe fn rand_next(rng: *rust_rng) -> u32;
1091                 pub unsafe fn rand_free(rng: *rust_rng);
1092             }
1093         }
1094
1095         // run against several seeds
1096         for 10.times {
1097             unsafe {
1098                 let seed = super::seed();
1099                 let rt_rng = do seed.as_imm_buf |p, sz| {
1100                     rustrt::rand_new_seeded(p, sz as size_t)
1101                 };
1102                 let mut rng = IsaacRng::new_seeded(seed);
1103
1104                 for 10000.times {
1105                     assert_eq!(rng.next(), rustrt::rand_next(rt_rng));
1106                 }
1107                 rustrt::rand_free(rt_rng);
1108             }
1109         }
1110     }
1111 }
1112
1113 #[cfg(test)]
1114 mod bench {
1115     use extra::test::BenchHarness;
1116     use rand::*;
1117     use sys::size_of;
1118
1119     #[bench]
1120     fn rand_xorshift(bh: &mut BenchHarness) {
1121         let mut rng = XorShiftRng::new();
1122         do bh.iter {
1123             rng.gen::<uint>();
1124         }
1125         bh.bytes = size_of::<uint>() as u64;
1126     }
1127
1128     #[bench]
1129     fn rand_isaac(bh: &mut BenchHarness) {
1130         let mut rng = IsaacRng::new();
1131         do bh.iter {
1132             rng.gen::<uint>();
1133         }
1134         bh.bytes = size_of::<uint>() as u64;
1135     }
1136
1137     #[bench]
1138     fn rand_shuffle_100(bh: &mut BenchHarness) {
1139         let mut rng = XorShiftRng::new();
1140         let x : &mut[uint] = [1,..100];
1141         do bh.iter {
1142             rng.shuffle_mut(x);
1143         }
1144     }
1145 }