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