#![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
html_favicon_url = "http://www.rust-lang.org/favicon.ico",
html_root_url = "http://doc.rust-lang.org/rand/")]
#![feature(core, os, old_path, old_io)]
#![cfg_attr(test, feature(test))]
extern crate core;
#[cfg(test)] #[macro_use] extern crate log;
use std::cell::RefCell;
use std::marker;
use std::mem;
use std::old_io::IoResult;
use std::rc::Rc;
pub use os::OsRng;
pub use isaac::{IsaacRng, Isaac64Rng};
pub use chacha::ChaChaRng;
#[cfg(target_pointer_width = "32")]
use IsaacRng as IsaacWordRng;
#[cfg(target_pointer_width = "64")]
use Isaac64Rng as IsaacWordRng;
use distributions::{Range, IndependentSample};
use distributions::range::SampleRange;
pub mod distributions;
pub mod isaac;
pub mod chacha;
pub mod reseeding;
mod rand_impls;
pub mod os;
pub mod reader;
pub trait Rand : Sized {
fn rand<R: Rng>(rng: &mut R) -> Self;
}
pub trait Rng : Sized {
fn next_u32(&mut self) -> u32;
fn next_u64(&mut self) -> u64 {
((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
}
fn next_f32(&mut self) -> f32 {
const MANTISSA_BITS: usize = 24;
const IGNORED_BITS: usize = 8;
const SCALE: f32 = (1u64 << MANTISSA_BITS) as f32;
(self.next_u32() >> IGNORED_BITS) as f32 / SCALE
}
fn next_f64(&mut self) -> f64 {
const MANTISSA_BITS: usize = 53;
const IGNORED_BITS: usize = 11;
const SCALE: f64 = (1u64 << MANTISSA_BITS) as f64;
(self.next_u64() >> IGNORED_BITS) as f64 / SCALE
}
fn fill_bytes(&mut self, dest: &mut [u8]) {
let mut count = 0;
let mut num = 0;
for byte in dest.iter_mut() {
if count == 0 {
num = self.next_u64();
count = 8;
}
*byte = (num & 0xff) as u8;
num >>= 8;
count -= 1;
}
}
#[inline(always)]
fn gen<T: Rand>(&mut self) -> T {
Rand::rand(self)
}
fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> {
Generator { rng: self, _marker: marker::PhantomData }
}
fn gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T {
assert!(low < high, "Rng.gen_range called with low >= high");
Range::new(low, high).ind_sample(self)
}
fn gen_weighted_bool(&mut self, n: usize) -> bool {
n <= 1 || self.gen_range(0, n) == 0
}
fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> {
AsciiGenerator { rng: self }
}
fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
if values.is_empty() {
None
} else {
Some(&values[self.gen_range(0, values.len())])
}
}
fn shuffle<T>(&mut self, values: &mut [T]) {
let mut i = values.len();
while i >= 2 {
i -= 1;
values.swap(i, self.gen_range(0, i + 1));
}
}
}
pub struct Generator<'a, T, R:'a> {
rng: &'a mut R,
_marker: marker::PhantomData<fn() -> T>,
}
impl<'a, T: Rand, R: Rng> Iterator for Generator<'a, T, R> {
type Item = T;
fn next(&mut self) -> Option<T> {
Some(self.rng.gen())
}
}
pub struct AsciiGenerator<'a, R:'a> {
rng: &'a mut R,
}
impl<'a, R: Rng> Iterator for AsciiGenerator<'a, R> {
type Item = char;
fn next(&mut self) -> Option<char> {
static GEN_ASCII_STR_CHARSET: &'static [u8] =
b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
abcdefghijklmnopqrstuvwxyz\
0123456789";
Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char)
}
}
pub trait SeedableRng<Seed>: Rng {
fn reseed(&mut self, Seed);
fn from_seed(seed: Seed) -> Self;
}
#[allow(missing_copy_implementations)]
#[derive(Clone)]
pub struct XorShiftRng {
x: u32,
y: u32,
z: u32,
w: u32,
}
impl XorShiftRng {
pub fn new_unseeded() -> XorShiftRng {
XorShiftRng {
x: 0x193a6754,
y: 0xa8a7d469,
z: 0x97830e05,
w: 0x113ba7bb,
}
}
}
impl Rng for XorShiftRng {
#[inline]
fn next_u32(&mut self) -> u32 {
let x = self.x;
let t = x ^ (x << 11);
self.x = self.y;
self.y = self.z;
self.z = self.w;
let w = self.w;
self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
self.w
}
}
impl SeedableRng<[u32; 4]> for XorShiftRng {
fn reseed(&mut self, seed: [u32; 4]) {
assert!(!seed.iter().all(|&x| x == 0),
"XorShiftRng.reseed called with an all zero seed.");
self.x = seed[0];
self.y = seed[1];
self.z = seed[2];
self.w = seed[3];
}
fn from_seed(seed: [u32; 4]) -> XorShiftRng {
assert!(!seed.iter().all(|&x| x == 0),
"XorShiftRng::from_seed called with an all zero seed.");
XorShiftRng {
x: seed[0],
y: seed[1],
z: seed[2],
w: seed[3]
}
}
}
impl Rand for XorShiftRng {
fn rand<R: Rng>(rng: &mut R) -> XorShiftRng {
let mut tuple: (u32, u32, u32, u32) = rng.gen();
while tuple == (0, 0, 0, 0) {
tuple = rng.gen();
}
let (x, y, z, w) = tuple;
XorShiftRng { x: x, y: y, z: z, w: w }
}
}
pub struct Open01<F>(pub F);
pub struct Closed01<F>(pub F);
#[derive(Copy, Clone)]
pub struct StdRng {
rng: IsaacWordRng,
}
impl StdRng {
pub fn new() -> IoResult<StdRng> {
OsRng::new().map(|mut r| StdRng { rng: r.gen() })
}
}
impl Rng for StdRng {
#[inline]
fn next_u32(&mut self) -> u32 {
self.rng.next_u32()
}
#[inline]
fn next_u64(&mut self) -> u64 {
self.rng.next_u64()
}
}
impl<'a> SeedableRng<&'a [usize]> for StdRng {
fn reseed(&mut self, seed: &'a [usize]) {
self.rng.reseed(unsafe {mem::transmute(seed)})
}
fn from_seed(seed: &'a [usize]) -> StdRng {
StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
}
}
pub fn weak_rng() -> XorShiftRng {
match OsRng::new() {
Ok(mut r) => r.gen(),
Err(e) => panic!("weak_rng: failed to create seeded RNG: {:?}", e)
}
}
struct ThreadRngReseeder;
impl reseeding::Reseeder<StdRng> for ThreadRngReseeder {
fn reseed(&mut self, rng: &mut StdRng) {
*rng = match StdRng::new() {
Ok(r) => r,
Err(e) => panic!("could not reseed thread_rng: {}", e)
}
}
}
static THREAD_RNG_RESEED_THRESHOLD: usize = 32_768;
type ThreadRngInner = reseeding::ReseedingRng<StdRng, ThreadRngReseeder>;
#[derive(Clone)]
pub struct ThreadRng {
rng: Rc<RefCell<ThreadRngInner>>,
}
pub fn thread_rng() -> ThreadRng {
thread_local!(static THREAD_RNG_KEY: Rc<RefCell<ThreadRngInner>> = {
let r = match StdRng::new() {
Ok(r) => r,
Err(e) => panic!("could not initialize thread_rng: {}", e)
};
let rng = reseeding::ReseedingRng::new(r,
THREAD_RNG_RESEED_THRESHOLD,
ThreadRngReseeder);
Rc::new(RefCell::new(rng))
});
ThreadRng { rng: THREAD_RNG_KEY.with(|t| t.clone()) }
}
impl Rng for ThreadRng {
fn next_u32(&mut self) -> u32 {
self.rng.borrow_mut().next_u32()
}
fn next_u64(&mut self) -> u64 {
self.rng.borrow_mut().next_u64()
}
#[inline]
fn fill_bytes(&mut self, bytes: &mut [u8]) {
self.rng.borrow_mut().fill_bytes(bytes)
}
}
#[inline]
pub fn random<T: Rand>() -> T {
thread_rng().gen()
}
pub fn sample<T, I: Iterator<Item=T>, R: Rng>(rng: &mut R,
mut iter: I,
amount: usize) -> Vec<T> {
let mut reservoir: Vec<T> = iter.by_ref().take(amount).collect();
for (i, elem) in iter.enumerate() {
let k = rng.gen_range(0, i + 1 + amount);
if k < amount {
reservoir[k] = elem;
}
}
return reservoir;
}
#[cfg(test)]
mod test {
use super::{Rng, thread_rng, random, SeedableRng, StdRng, sample};
use std::iter::{order, repeat};
pub struct MyRng<R> { inner: R }
impl<R: Rng> Rng for MyRng<R> {
fn next_u32(&mut self) -> u32 {
fn next<T: Rng>(t: &mut T) -> u32 {
t.next_u32()
}
next(&mut self.inner)
}
}
pub fn rng() -> MyRng<::ThreadRng> {
MyRng { inner: ::thread_rng() }
}
pub fn weak_rng() -> MyRng<::XorShiftRng> {
MyRng { inner: ::weak_rng() }
}
struct ConstRng { i: u64 }
impl Rng for ConstRng {
fn next_u32(&mut self) -> u32 { self.i as u32 }
fn next_u64(&mut self) -> u64 { self.i }
}
#[test]
fn test_fill_bytes_default() {
let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
80, 81, 82, 83, 84, 85, 86, 87];
for &n in lengths.iter() {
let mut v = repeat(0u8).take(n).collect::<Vec<_>>();
r.fill_bytes(v.as_mut_slice());
for (i, &byte) in v.iter().enumerate() {
if byte == 0 {
panic!("byte {} of {} is zero", i, n)
}
}
}
}
#[test]
fn test_gen_range() {
let mut r = thread_rng();
for _ in 0..1000 {
let a = r.gen_range(-3, 42);
assert!(a >= -3 && a < 42);
assert_eq!(r.gen_range(0, 1), 0);
assert_eq!(r.gen_range(-12, -11), -12);
}
for _ in 0..1000 {
let a = r.gen_range(10, 42);
assert!(a >= 10 && a < 42);
assert_eq!(r.gen_range(0, 1), 0);
assert_eq!(r.gen_range(3_000_000, 3_000_001), 3_000_000);
}
}
#[test]
#[should_fail]
fn test_gen_range_panic_int() {
let mut r = thread_rng();
r.gen_range(5, -2);
}
#[test]
#[should_fail]
fn test_gen_range_panic_usize() {
let mut r = thread_rng();
r.gen_range(5, 2);
}
#[test]
fn test_gen_f64() {
let mut r = thread_rng();
let a = r.gen::<f64>();
let b = r.gen::<f64>();
debug!("{:?}", (a, b));
}
#[test]
fn test_gen_weighted_bool() {
let mut r = thread_rng();
assert_eq!(r.gen_weighted_bool(0), true);
assert_eq!(r.gen_weighted_bool(1), true);
}
#[test]
fn test_gen_ascii_str() {
let mut r = thread_rng();
assert_eq!(r.gen_ascii_chars().take(0).count(), 0);
assert_eq!(r.gen_ascii_chars().take(10).count(), 10);
assert_eq!(r.gen_ascii_chars().take(16).count(), 16);
}
#[test]
fn test_gen_vec() {
let mut r = thread_rng();
assert_eq!(r.gen_iter::<u8>().take(0).count(), 0);
assert_eq!(r.gen_iter::<u8>().take(10).count(), 10);
assert_eq!(r.gen_iter::<f64>().take(16).count(), 16);
}
#[test]
fn test_choose() {
let mut r = thread_rng();
assert_eq!(r.choose(&[1, 1, 1]).map(|&x|x), Some(1));
let v: &[isize] = &[];
assert_eq!(r.choose(v), None);
}
#[test]
fn test_shuffle() {
let mut r = thread_rng();
let empty: &mut [isize] = &mut [];
r.shuffle(empty);
let mut one = [1];
r.shuffle(&mut one);
let b: &[_] = &[1];
assert_eq!(one, b);
let mut two = [1, 2];
r.shuffle(&mut two);
assert!(two == [1, 2] || two == [2, 1]);
let mut x = [1, 1, 1];
r.shuffle(&mut x);
let b: &[_] = &[1, 1, 1];
assert_eq!(x, b);
}
#[test]
fn test_thread_rng() {
let mut r = thread_rng();
r.gen::<i32>();
let mut v = [1, 1, 1];
r.shuffle(&mut v);
let b: &[_] = &[1, 1, 1];
assert_eq!(v, b);
assert_eq!(r.gen_range(0, 1), 0);
}
#[test]
fn test_random() {
let _n : usize = random();
let _f : f32 = random();
let _o : Option<Option<i8>> = random();
let _many : ((),
(usize,
isize,
Option<(u32, (bool,))>),
(u8, i8, u16, i16, u32, i32, u64, i64),
(f32, (f64, (f64,)))) = random();
}
#[test]
fn test_sample() {
let min_val = 1;
let max_val = 100;
let mut r = thread_rng();
let vals = (min_val..max_val).collect::<Vec<i32>>();
let small_sample = sample(&mut r, vals.iter(), 5);
let large_sample = sample(&mut r, vals.iter(), vals.len() + 5);
assert_eq!(small_sample.len(), 5);
assert_eq!(large_sample.len(), vals.len());
assert!(small_sample.iter().all(|e| {
**e >= min_val && **e <= max_val
}));
}
#[test]
fn test_std_rng_seeded() {
let s = thread_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>();
let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
assert!(order::equals(ra.gen_ascii_chars().take(100),
rb.gen_ascii_chars().take(100)));
}
#[test]
fn test_std_rng_reseed() {
let s = thread_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>();
let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
let string1 = r.gen_ascii_chars().take(100).collect::<String>();
r.reseed(s.as_slice());
let string2 = r.gen_ascii_chars().take(100).collect::<String>();
assert_eq!(string1, string2);
}
}
#[cfg(test)]
static RAND_BENCH_N: u64 = 100;
#[cfg(test)]
mod bench {
extern crate test;
use self::test::{black_box, Bencher};
use super::{XorShiftRng, StdRng, IsaacRng, Isaac64Rng, Rng, RAND_BENCH_N};
use super::{OsRng, weak_rng};
use std::mem::size_of;
#[bench]
fn rand_xorshift(b: &mut Bencher) {
let mut rng: XorShiftRng = OsRng::new().unwrap().gen();
b.iter(|| {
for _ in 0..RAND_BENCH_N {
black_box(rng.gen::<usize>());
}
});
b.bytes = size_of::<usize>() as u64 * RAND_BENCH_N;
}
#[bench]
fn rand_isaac(b: &mut Bencher) {
let mut rng: IsaacRng = OsRng::new().unwrap().gen();
b.iter(|| {
for _ in 0..RAND_BENCH_N {
black_box(rng.gen::<usize>());
}
});
b.bytes = size_of::<usize>() as u64 * RAND_BENCH_N;
}
#[bench]
fn rand_isaac64(b: &mut Bencher) {
let mut rng: Isaac64Rng = OsRng::new().unwrap().gen();
b.iter(|| {
for _ in 0..RAND_BENCH_N {
black_box(rng.gen::<usize>());
}
});
b.bytes = size_of::<usize>() as u64 * RAND_BENCH_N;
}
#[bench]
fn rand_std(b: &mut Bencher) {
let mut rng = StdRng::new().unwrap();
b.iter(|| {
for _ in 0..RAND_BENCH_N {
black_box(rng.gen::<usize>());
}
});
b.bytes = size_of::<usize>() as u64 * RAND_BENCH_N;
}
#[bench]
fn rand_shuffle_100(b: &mut Bencher) {
let mut rng = weak_rng();
let x : &mut [usize] = &mut [1; 100];
b.iter(|| {
rng.shuffle(x);
})
}
}