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