diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/rand/isaac.rs | 517 | ||||
| -rw-r--r-- | src/libstd/rand/mod.rs | 758 | ||||
| -rw-r--r-- | src/libstd/rand/os.rs | 178 | ||||
| -rw-r--r-- | src/libstd/rand/rand_impls.rs | 224 | ||||
| -rw-r--r-- | src/libstd/rand/reader.rs | 124 | ||||
| -rw-r--r-- | src/libstd/rand/reseeding.rs | 204 | ||||
| -rw-r--r-- | src/libstd/rt/sched.rs | 50 | ||||
| -rw-r--r-- | src/libstd/rt/task.rs | 2 |
8 files changed, 1621 insertions, 436 deletions
diff --git a/src/libstd/rand/isaac.rs b/src/libstd/rand/isaac.rs new file mode 100644 index 00000000000..0068b60cfa5 --- /dev/null +++ b/src/libstd/rand/isaac.rs @@ -0,0 +1,517 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The ISAAC random number generator. + +use cast; +use rand::{Rng, SeedableRng, OSRng}; +use iter::{Iterator, range, range_step, Repeat}; +use option::{None, Some}; + +static RAND_SIZE_LEN: u32 = 8; +static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN; + +/// A random number generator that uses the [ISAAC +/// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29). +/// +/// The ISAAC algorithm is suitable for cryptographic purposes. +pub struct IsaacRng { + priv cnt: u32, + priv rsl: [u32, .. RAND_SIZE], + priv mem: [u32, .. RAND_SIZE], + priv a: u32, + priv b: u32, + priv c: u32 +} +static EMPTY: IsaacRng = IsaacRng { + cnt: 0, + rsl: [0, .. RAND_SIZE], + mem: [0, .. RAND_SIZE], + a: 0, b: 0, c: 0 +}; + +impl IsaacRng { + /// Create an ISAAC random number generator with a random seed. + pub fn new() -> IsaacRng { + let mut rng = EMPTY; + + { + let bytes = unsafe {cast::transmute::<&mut [u32], &mut [u8]>(rng.rsl)}; + OSRng::new().fill_bytes(bytes); + } + + rng.init(true); + rng + } + + /// Create an ISAAC random number generator using the default + /// fixed seed. + pub fn new_unseeded() -> IsaacRng { + let mut rng = EMPTY; + rng.init(false); + rng + } + + /// Initialises `self`. If `use_rsl` is true, then use the current value + /// of `rsl` as a seed, otherwise construct one algorithmically (not + /// randomly). + fn init(&mut self, use_rsl: bool) { + let mut a = 0x9e3779b9; + let mut b = a; + let mut c = a; + let mut d = a; + let mut e = a; + let mut f = a; + let mut g = a; + let mut h = a; + + macro_rules! mix( + () => {{ + a^=b<<11; d+=a; b+=c; + b^=c>>2; e+=b; c+=d; + c^=d<<8; f+=c; d+=e; + d^=e>>16; g+=d; e+=f; + e^=f<<10; h+=e; f+=g; + f^=g>>4; a+=f; g+=h; + g^=h<<8; b+=g; h+=a; + h^=a>>9; c+=h; a+=b; + }} + ); + + do 4.times { mix!(); } + + if use_rsl { + macro_rules! memloop ( + ($arr:expr) => {{ + for i in range_step(0u32, RAND_SIZE, 8) { + a+=$arr[i ]; b+=$arr[i+1]; + c+=$arr[i+2]; d+=$arr[i+3]; + e+=$arr[i+4]; f+=$arr[i+5]; + g+=$arr[i+6]; h+=$arr[i+7]; + mix!(); + self.mem[i ]=a; self.mem[i+1]=b; + self.mem[i+2]=c; self.mem[i+3]=d; + self.mem[i+4]=e; self.mem[i+5]=f; + self.mem[i+6]=g; self.mem[i+7]=h; + } + }} + ); + + memloop!(self.rsl); + memloop!(self.mem); + } else { + for i in range_step(0u32, RAND_SIZE, 8) { + mix!(); + self.mem[i ]=a; self.mem[i+1]=b; + self.mem[i+2]=c; self.mem[i+3]=d; + self.mem[i+4]=e; self.mem[i+5]=f; + self.mem[i+6]=g; self.mem[i+7]=h; + } + } + + self.isaac(); + } + + /// Refills the output buffer (`self.rsl`) + #[inline] + fn isaac(&mut self) { + self.c += 1; + // abbreviations + let mut a = self.a; + let mut b = self.b + self.c; + + static MIDPOINT: uint = RAND_SIZE as uint / 2; + + macro_rules! ind (($x:expr) => { + self.mem[($x >> 2) & (RAND_SIZE - 1)] + }); + macro_rules! rngstep( + ($j:expr, $shift:expr) => {{ + let base = $j; + let mix = if $shift < 0 { + a >> -$shift as uint + } else { + a << $shift as uint + }; + + let x = self.mem[base + mr_offset]; + a = (a ^ mix) + self.mem[base + m2_offset]; + let y = ind!(x) + a + b; + self.mem[base + mr_offset] = y; + + b = ind!(y >> RAND_SIZE_LEN) + x; + self.rsl[base + mr_offset] = b; + }} + ); + + let r = [(0, MIDPOINT), (MIDPOINT, 0)]; + for &(mr_offset, m2_offset) in r.iter() { + for i in range_step(0u, MIDPOINT, 4) { + rngstep!(i + 0, 13); + rngstep!(i + 1, -6); + rngstep!(i + 2, 2); + rngstep!(i + 3, -16); + } + } + + self.a = a; + self.b = b; + self.cnt = RAND_SIZE; + } +} + +impl Rng for IsaacRng { + #[inline] + fn next_u32(&mut self) -> u32 { + if self.cnt == 0 { + // make some more numbers + self.isaac(); + } + self.cnt -= 1; + self.rsl[self.cnt] + } +} + +impl<'self> SeedableRng<&'self [u32]> for IsaacRng { + fn reseed(&mut self, seed: &'self [u32]) { + // make the seed into [seed[0], seed[1], ..., seed[seed.len() + // - 1], 0, 0, ...], to fill rng.rsl. + let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u32)); + + for (rsl_elem, seed_elem) in self.rsl.mut_iter().zip(seed_iter) { + *rsl_elem = seed_elem; + } + self.cnt = 0; + self.a = 0; + self.b = 0; + self.c = 0; + + self.init(true); + } + + /// Create an ISAAC random number generator with a seed. This can + /// be any length, although the maximum number of elements used is + /// 256 and any more will be silently ignored. A generator + /// constructed with a given seed will generate the same sequence + /// of values as all other generators constructed with that seed. + fn from_seed(seed: &'self [u32]) -> IsaacRng { + let mut rng = EMPTY; + rng.reseed(seed); + rng + } +} + + +static RAND_SIZE_64_LEN: uint = 8; +static RAND_SIZE_64: uint = 1 << RAND_SIZE_64_LEN; + +/// A random number generator that uses the 64-bit variant of the +/// [ISAAC +/// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29). +/// +/// The ISAAC algorithm is suitable for cryptographic purposes. +pub struct Isaac64Rng { + priv cnt: uint, + priv rsl: [u64, .. RAND_SIZE_64], + priv mem: [u64, .. RAND_SIZE_64], + priv a: u64, + priv b: u64, + priv c: u64, +} + +static EMPTY_64: Isaac64Rng = Isaac64Rng { + cnt: 0, + rsl: [0, .. RAND_SIZE_64], + mem: [0, .. RAND_SIZE_64], + a: 0, b: 0, c: 0, +}; + +impl Isaac64Rng { + /// Create a 64-bit ISAAC random number generator with a random + /// seed. + pub fn new() -> Isaac64Rng { + let mut rng = EMPTY_64; + { + let bytes = unsafe {cast::transmute::<&mut [u64], &mut [u8]>(rng.rsl)}; + OSRng::new().fill_bytes(bytes); + } + rng.init(true); + rng + } + + /// Create a 64-bit ISAAC random number generator using the + /// default fixed seed. + pub fn new_unseeded() -> Isaac64Rng { + let mut rng = EMPTY_64; + rng.init(false); + rng + } + + /// Initialises `self`. If `use_rsl` is true, then use the current value + /// of `rsl` as a seed, otherwise construct one algorithmically (not + /// randomly). + fn init(&mut self, use_rsl: bool) { + macro_rules! init ( + ($var:ident) => ( + let mut $var = 0x9e3779b97f4a7c13; + ) + ); + init!(a); init!(b); init!(c); init!(d); + init!(e); init!(f); init!(g); init!(h); + + macro_rules! mix( + () => {{ + a-=e; f^=h>>9; h+=a; + b-=f; g^=a<<9; a+=b; + c-=g; h^=b>>23; b+=c; + d-=h; a^=c<<15; c+=d; + e-=a; b^=d>>14; d+=e; + f-=b; c^=e<<20; e+=f; + g-=c; d^=f>>17; f+=g; + h-=d; e^=g<<14; g+=h; + }} + ); + + for _ in range(0, 4) { mix!(); } + if use_rsl { + macro_rules! memloop ( + ($arr:expr) => {{ + for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) { + a+=$arr[i ]; b+=$arr[i+1]; + c+=$arr[i+2]; d+=$arr[i+3]; + e+=$arr[i+4]; f+=$arr[i+5]; + g+=$arr[i+6]; h+=$arr[i+7]; + mix!(); + self.mem[i ]=a; self.mem[i+1]=b; + self.mem[i+2]=c; self.mem[i+3]=d; + self.mem[i+4]=e; self.mem[i+5]=f; + self.mem[i+6]=g; self.mem[i+7]=h; + } + }} + ); + + memloop!(self.rsl); + memloop!(self.mem); + } else { + for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) { + mix!(); + self.mem[i ]=a; self.mem[i+1]=b; + self.mem[i+2]=c; self.mem[i+3]=d; + self.mem[i+4]=e; self.mem[i+5]=f; + self.mem[i+6]=g; self.mem[i+7]=h; + } + } + + self.isaac64(); + } + + /// Refills the output buffer (`self.rsl`) + fn isaac64(&mut self) { + self.c += 1; + // abbreviations + let mut a = self.a; + let mut b = self.b + self.c; + static MIDPOINT: uint = RAND_SIZE_64 / 2; + static MP_VEC: [(uint, uint), .. 2] = [(0,MIDPOINT), (MIDPOINT, 0)]; + macro_rules! ind ( + ($x:expr) => { + self.mem.unsafe_get(($x as uint >> 3) & (RAND_SIZE_64 - 1)) + } + ); + macro_rules! rngstep( + ($j:expr, $shift:expr) => {{ + let base = base + $j; + let mix = a ^ (if $shift < 0 { + a >> -$shift as uint + } else { + a << $shift as uint + }); + let mix = if $j == 0 {!mix} else {mix}; + + unsafe { + let x = self.mem.unsafe_get(base + mr_offset); + a = mix + self.mem.unsafe_get(base + m2_offset); + let y = ind!(x) + a + b; + self.mem.unsafe_set(base + mr_offset, y); + + b = ind!(y >> RAND_SIZE_64_LEN) + x; + self.rsl.unsafe_set(base + mr_offset, b); + } + }} + ); + + for &(mr_offset, m2_offset) in MP_VEC.iter() { + for base in range(0, MIDPOINT / 4).map(|i| i * 4) { + rngstep!(0, 21); + rngstep!(1, -5); + rngstep!(2, 12); + rngstep!(3, -33); + } + } + + self.a = a; + self.b = b; + self.cnt = RAND_SIZE_64; + } +} + +impl Rng for Isaac64Rng { + // FIXME #7771: having next_u32 like this should be unnecessary + #[inline] + fn next_u32(&mut self) -> u32 { + self.next_u64() as u32 + } + + #[inline] + fn next_u64(&mut self) -> u64 { + if self.cnt == 0 { + // make some more numbers + self.isaac64(); + } + self.cnt -= 1; + unsafe { self.rsl.unsafe_get(self.cnt) } + } +} + +impl<'self> SeedableRng<&'self [u64]> for Isaac64Rng { + fn reseed(&mut self, seed: &'self [u64]) { + // make the seed into [seed[0], seed[1], ..., seed[seed.len() + // - 1], 0, 0, ...], to fill rng.rsl. + let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u64)); + + for (rsl_elem, seed_elem) in self.rsl.mut_iter().zip(seed_iter) { + *rsl_elem = seed_elem; + } + self.cnt = 0; + self.a = 0; + self.b = 0; + self.c = 0; + + self.init(true); + } + + /// Create an ISAAC random number generator with a seed. This can + /// be any length, although the maximum number of elements used is + /// 256 and any more will be silently ignored. A generator + /// constructed with a given seed will generate the same sequence + /// of values as all other generators constructed with that seed. + fn from_seed(seed: &'self [u64]) -> Isaac64Rng { + let mut rng = EMPTY_64; + rng.reseed(seed); + rng + } +} + +#[cfg(test)] +mod test { + use super::*; + use rand::{Rng, SeedableRng, OSRng}; + use option::Some; + use iter::range; + use vec; + + #[test] + fn test_rng_32_rand_seeded() { + let s = OSRng::new().gen_vec::<u32>(256); + let mut ra: IsaacRng = SeedableRng::from_seed(s.as_slice()); + let mut rb: IsaacRng = SeedableRng::from_seed(s.as_slice()); + assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); + } + #[test] + fn test_rng_64_rand_seeded() { + let s = OSRng::new().gen_vec::<u64>(256); + let mut ra: Isaac64Rng = SeedableRng::from_seed(s.as_slice()); + let mut rb: Isaac64Rng = SeedableRng::from_seed(s.as_slice()); + assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); + } + + #[test] + fn test_rng_32_seeded() { + let seed = &[2, 32, 4, 32, 51]; + let mut ra: IsaacRng = SeedableRng::from_seed(seed); + let mut rb: IsaacRng = SeedableRng::from_seed(seed); + assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); + } + #[test] + fn test_rng_64_seeded() { + let seed = &[2, 32, 4, 32, 51]; + let mut ra: Isaac64Rng = SeedableRng::from_seed(seed); + let mut rb: Isaac64Rng = SeedableRng::from_seed(seed); + assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); + } + + #[test] + fn test_rng_32_reseed() { + let s = OSRng::new().gen_vec::<u32>(256); + let mut r: IsaacRng = SeedableRng::from_seed(s.as_slice()); + let string1 = r.gen_ascii_str(100); + + r.reseed(s); + + let string2 = r.gen_ascii_str(100); + assert_eq!(string1, string2); + } + #[test] + fn test_rng_64_reseed() { + let s = OSRng::new().gen_vec::<u64>(256); + let mut r: Isaac64Rng = SeedableRng::from_seed(s.as_slice()); + let string1 = r.gen_ascii_str(100); + + r.reseed(s); + + let string2 = r.gen_ascii_str(100); + assert_eq!(string1, string2); + } + + #[test] + fn test_rng_32_true_values() { + let seed = &[2, 32, 4, 32, 51]; + let mut ra: IsaacRng = SeedableRng::from_seed(seed); + // Regression test that isaac is actually using the above vector + let v = vec::from_fn(10, |_| ra.next_u32()); + assert_eq!(v, + ~[447462228, 2081944040, 3163797308, 2379916134, 2377489184, + 1132373754, 536342443, 2995223415, 1265094839, 345325140]); + + let seed = &[500, -4000, 123456, 9876543, 1, 1, 1, 1, 1]; + let mut rb: IsaacRng = SeedableRng::from_seed(seed); + // skip forward to the 10000th number + for _ in range(0, 10000) { rb.next_u32(); } + + let v = vec::from_fn(10, |_| rb.next_u32()); + assert_eq!(v, + ~[612373032, 292987903, 1819311337, 3141271980, 422447569, + 310096395, 1083172510, 867909094, 2478664230, 2073577855]); + } + #[test] + fn test_rng_64_true_values() { + let seed = &[2, 32, 4, 32, 51]; + let mut ra: Isaac64Rng = SeedableRng::from_seed(seed); + // Regression test that isaac is actually using the above vector + let v = vec::from_fn(10, |_| ra.next_u64()); + assert_eq!(v, + ~[15015576812873463115, 12461067598045625862, 14818626436142668771, + 5562406406765984441, 11813289907965514161, 13443797187798420053, + 6935026941854944442, 7750800609318664042, 14428747036317928637, + 14028894460301215947]); + + let seed = &[500, -4000, 123456, 9876543, 1, 1, 1, 1, 1]; + let mut rb: Isaac64Rng = SeedableRng::from_seed(seed); + // skip forward to the 10000th number + for _ in range(0, 10000) { rb.next_u64(); } + + let v = vec::from_fn(10, |_| rb.next_u64()); + assert_eq!(v, + ~[13557216323596688637, 17060829581390442094, 4927582063811333743, + 2699639759356482270, 4819341314392384881, 6047100822963614452, + 11086255989965979163, 11901890363215659856, 5370800226050011580, + 16496463556025356451]); + } +} diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs index 70bcb0f7170..9b757092266 100644 --- a/src/libstd/rand/mod.rs +++ b/src/libstd/rand/mod.rs @@ -1,4 +1,4 @@ -// Copyright 2012 The Rust Project Developers. See the COPYRIGHT +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT // file at the top-level directory of this distribution and at // http://rust-lang.org/COPYRIGHT. // @@ -19,6 +19,15 @@ suffice, but sometimes an annotation is required, e.g. `rand::random::<f64>()`. See the `distributions` submodule for sampling random numbers from distributions like normal and exponential. +# Task-local RNG + +There is built-in support for a RNG associated with each task stored +in task-local storage. This RNG can be accessed via `task_rng`, or +used implicitly via `random`. This RNG is normally randomly seeded +from an operating-system source of randomness, e.g. `/dev/urandom` on +Unix systems, and will automatically reseed itself from this source +after generating 32 KiB of random data. + # Examples ```rust @@ -44,21 +53,23 @@ fn main () { */ use cast; -use cmp; use container::Container; -use int; -use iter::{Iterator, range, range_step}; +use iter::{Iterator, range}; use local_data; use prelude::*; use str; -use sys; -use u32; use u64; -use uint; use vec; -use libc::size_t; + +pub use self::isaac::{IsaacRng, Isaac64Rng}; +pub use self::os::OSRng; pub mod distributions; +pub mod isaac; +pub mod os; +pub mod reader; +pub mod reseeding; +mod rand_impls; /// A type that can be randomly generated using an Rng pub trait Rand { @@ -67,178 +78,6 @@ pub trait Rand { fn rand<R: Rng>(rng: &mut R) -> Self; } -impl Rand for int { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> int { - if int::bits == 32 { - rng.next() as int - } else { - rng.gen::<i64>() as int - } - } -} - -impl Rand for i8 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> i8 { - rng.next() as i8 - } -} - -impl Rand for i16 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> i16 { - rng.next() as i16 - } -} - -impl Rand for i32 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> i32 { - rng.next() as i32 - } -} - -impl Rand for i64 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> i64 { - (rng.next() as i64 << 32) | rng.next() as i64 - } -} - -impl Rand for uint { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> uint { - if uint::bits == 32 { - rng.next() as uint - } else { - rng.gen::<u64>() as uint - } - } -} - -impl Rand for u8 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> u8 { - rng.next() as u8 - } -} - -impl Rand for u16 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> u16 { - rng.next() as u16 - } -} - -impl Rand for u32 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> u32 { - rng.next() - } -} - -impl Rand for u64 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> u64 { - (rng.next() as u64 << 32) | rng.next() as u64 - } -} - -impl Rand for f32 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> f32 { - rng.gen::<f64>() as f32 - } -} - -static SCALE : f64 = (u32::max_value as f64) + 1.0f64; -impl Rand for f64 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> f64 { - let u1 = rng.next() as f64; - let u2 = rng.next() as f64; - let u3 = rng.next() as f64; - - ((u1 / SCALE + u2) / SCALE + u3) / SCALE - } -} - -impl Rand for bool { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> bool { - rng.next() & 1u32 == 1u32 - } -} - -macro_rules! tuple_impl { - // use variables to indicate the arity of the tuple - ($($tyvar:ident),* ) => { - // the trailing commas are for the 1 tuple - impl< - $( $tyvar : Rand ),* - > Rand for ( $( $tyvar ),* , ) { - - #[inline] - fn rand<R: Rng>(_rng: &mut R) -> ( $( $tyvar ),* , ) { - ( - // use the $tyvar's to get the appropriate number of - // repeats (they're not actually needed) - $( - _rng.gen::<$tyvar>() - ),* - , - ) - } - } - } -} - -impl Rand for () { - #[inline] - fn rand<R: Rng>(_: &mut R) -> () { () } -} -tuple_impl!{A} -tuple_impl!{A, B} -tuple_impl!{A, B, C} -tuple_impl!{A, B, C, D} -tuple_impl!{A, B, C, D, E} -tuple_impl!{A, B, C, D, E, F} -tuple_impl!{A, B, C, D, E, F, G} -tuple_impl!{A, B, C, D, E, F, G, H} -tuple_impl!{A, B, C, D, E, F, G, H, I} -tuple_impl!{A, B, C, D, E, F, G, H, I, J} - -impl<T:Rand> Rand for Option<T> { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> Option<T> { - if rng.gen() { - Some(rng.gen()) - } else { - None - } - } -} - -impl<T: Rand> Rand for ~T { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> ~T { ~rng.gen() } -} - -impl<T: Rand + 'static> Rand for @T { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> @T { @rng.gen() } -} - -#[abi = "cdecl"] -pub mod rustrt { - use libc::size_t; - - extern { - pub fn rand_gen_seed(buf: *mut u8, sz: size_t); - } -} - /// A value with a particular weight compared to other values pub struct Weighted<T> { /// The numerical weight of this item @@ -249,9 +88,92 @@ pub struct Weighted<T> { /// A random number generator pub trait Rng { - /// Return the next random integer - fn next(&mut self) -> u32; + /// Return the next random u32. This rarely needs to be called + /// directly, prefer `r.gen()` to `r.next_u32()`. + /// + // FIXME #7771: Should be implemented in terms of next_u64 + fn next_u32(&mut self) -> u32; + /// Return the next random u64. This rarely needs to be called + /// directly, prefer `r.gen()` to `r.next_u64()`. + /// + /// By default this is implemented in terms of `next_u32`. An + /// implementation of this trait must provide at least one of + /// these two methods. + fn next_u64(&mut self) -> u64 { + (self.next_u32() as u64 << 32) | (self.next_u32() as u64) + } + + /// Fill `dest` with random data. + /// + /// This has a default implementation in terms of `next_u64` and + /// `next_u32`, but should be overriden by implementations that + /// offer a more efficient solution than just calling those + /// methods repeatedly. + /// + /// This method does *not* have a requirement to bear any fixed + /// relationship to the other methods, for example, it does *not* + /// have to result in the same output as progressively filling + /// `dest` with `self.gen::<u8>()`, and any such behaviour should + /// not be relied upon. + /// + /// This method should guarantee that `dest` is entirely filled + /// with new data, and may fail if this is impossible + /// (e.g. reading past the end of a file that is being used as the + /// source of randomness). + /// + /// # Example + /// + /// ```rust + /// use std::rand::{task_rng, Rng}; + /// + /// fn main() { + /// let mut v = [0u8, .. 13579]; + /// task_rng().fill_bytes(v); + /// println!("{:?}", v); + /// } + /// ``` + fn fill_bytes(&mut self, mut dest: &mut [u8]) { + // this relies on the lengths being transferred correctly when + // transmuting between vectors like this. + let as_u64: &mut &mut [u64] = unsafe { cast::transmute(&mut dest) }; + for dest in as_u64.mut_iter() { + *dest = self.next_u64(); + } + + // the above will have filled up the vector as much as + // possible in multiples of 8 bytes. + let mut remaining = dest.len() % 8; + + // space for a u32 + if remaining >= 4 { + let as_u32: &mut &mut [u32] = unsafe { cast::transmute(&mut dest) }; + as_u32[as_u32.len() - 1] = self.next_u32(); + remaining -= 4; + } + // exactly filled + if remaining == 0 { return } + + // now we know we've either got 1, 2 or 3 spots to go, + // i.e. exactly one u32 is enough. + let rand = self.next_u32(); + let remaining_index = dest.len() - remaining; + match dest.mut_slice_from(remaining_index) { + [ref mut a] => { + *a = rand as u8; + } + [ref mut a, ref mut b] => { + *a = rand as u8; + *b = (rand >> 8) as u8; + } + [ref mut a, ref mut b, ref mut c] => { + *a = rand as u8; + *b = (rand >> 8) as u8; + *c = (rand >> 16) as u8; + } + _ => fail2!("Rng.fill_bytes: the impossible occurred: remaining != 1, 2 or 3") + } + } /// Return a random value of a Rand type. /// @@ -556,202 +478,118 @@ pub trait Rng { } } +/// A random number generator that can be explicitly seeded to produce +/// the same stream of randomness multiple times. +pub trait SeedableRng<Seed>: Rng { + /// Reseed an RNG with the given seed. + /// + /// # Example + /// + /// ```rust + /// use std::rand; + /// use std::rand::Rng; + /// + /// fn main() { + /// let mut rng: rand::StdRng = rand::SeedableRng::from_seed(&[1, 2, 3, 4]); + /// println!("{}", rng.gen::<f64>()); + /// rng.reseed([5, 6, 7, 8]); + /// println!("{}", rng.gen::<f64>()); + /// } + /// ``` + fn reseed(&mut self, Seed); + + /// Create a new RNG with the given seed. + /// + /// # Example + /// + /// ```rust + /// use std::rand; + /// use std::rand::Rng; + /// + /// fn main() { + /// let mut rng: rand::StdRng = rand::SeedableRng::from_seed(&[1, 2, 3, 4]); + /// println!("{}", rng.gen::<f64>()); + /// } + /// ``` + fn from_seed(seed: Seed) -> Self; +} + /// Create a random number generator with a default algorithm and seed. /// /// It returns the cryptographically-safest `Rng` algorithm currently /// available in Rust. If you require a specifically seeded `Rng` for /// consistency over time you should pick one algorithm and create the /// `Rng` yourself. -pub fn rng() -> IsaacRng { - IsaacRng::new() -} - -/// Create a weak random number generator with a default algorithm and seed. /// -/// It returns the fastest `Rng` algorithm currently available in Rust without -/// consideration for cryptography or security. If you require a specifically -/// seeded `Rng` for consistency over time you should pick one algorithm and -/// create the `Rng` yourself. -pub fn weak_rng() -> XorShiftRng { - XorShiftRng::new() +/// This is a very expensive operation as it has to read randomness +/// from the operating system and use this in an expensive seeding +/// operation. If one does not require high performance generation of +/// random numbers, `task_rng` and/or `random` may be more +/// appropriate. +pub fn rng() -> StdRng { + StdRng::new() } -static RAND_SIZE_LEN: u32 = 8; -static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN; +/// The standard RNG. This is designed to be efficient on the current +/// platform. +#[cfg(not(target_word_size="64"))] +pub struct StdRng { priv rng: IsaacRng } -/// A random number generator that uses the [ISAAC -/// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29). -/// -/// The ISAAC algorithm is suitable for cryptographic purposes. -pub struct IsaacRng { - priv cnt: u32, - priv rsl: [u32, .. RAND_SIZE], - priv mem: [u32, .. RAND_SIZE], - priv a: u32, - priv b: u32, - priv c: u32 -} +/// The standard RNG. This is designed to be efficient on the current +/// platform. +#[cfg(target_word_size="64")] +pub struct StdRng { priv rng: Isaac64Rng } -impl IsaacRng { - /// Create an ISAAC random number generator with a random seed. - pub fn new() -> IsaacRng { - IsaacRng::new_seeded(seed()) +impl StdRng { + /// Create a randomly seeded instance of `StdRng`. This reads + /// randomness from the OS to seed the PRNG. + #[cfg(not(target_word_size="64"))] + pub fn new() -> StdRng { + StdRng { rng: IsaacRng::new() } } - - /// Create an ISAAC random number generator with a seed. This can be any - /// length, although the maximum number of bytes used is 1024 and any more - /// will be silently ignored. A generator constructed with a given seed - /// will generate the same sequence of values as all other generators - /// constructed with the same seed. - pub fn new_seeded(seed: &[u8]) -> IsaacRng { - let mut rng = IsaacRng { - cnt: 0, - rsl: [0, .. RAND_SIZE], - mem: [0, .. RAND_SIZE], - a: 0, b: 0, c: 0 - }; - - let array_size = sys::size_of_val(&rng.rsl); - let copy_length = cmp::min(array_size, seed.len()); - - // manually create a &mut [u8] slice of randrsl to copy into. - let dest = unsafe { cast::transmute((&mut rng.rsl, array_size)) }; - vec::bytes::copy_memory(dest, seed, copy_length); - rng.init(true); - rng + /// Create a randomly seeded instance of `StdRng`. This reads + /// randomness from the OS to seed the PRNG. + #[cfg(target_word_size="64")] + pub fn new() -> StdRng { + StdRng { rng: Isaac64Rng::new() } } +} - /// Create an ISAAC random number generator using the default - /// fixed seed. - pub fn new_unseeded() -> IsaacRng { - let mut rng = IsaacRng { - cnt: 0, - rsl: [0, .. RAND_SIZE], - mem: [0, .. RAND_SIZE], - a: 0, b: 0, c: 0 - }; - rng.init(false); - rng +impl Rng for StdRng { + #[inline] + fn next_u32(&mut self) -> u32 { + self.rng.next_u32() } - /// Initialises `self`. If `use_rsl` is true, then use the current value - /// of `rsl` as a seed, otherwise construct one algorithmically (not - /// randomly). - fn init(&mut self, use_rsl: bool) { - let mut a = 0x9e3779b9; - let mut b = a; - let mut c = a; - let mut d = a; - let mut e = a; - let mut f = a; - let mut g = a; - let mut h = a; - - macro_rules! mix( - () => {{ - a^=b<<11; d+=a; b+=c; - b^=c>>2; e+=b; c+=d; - c^=d<<8; f+=c; d+=e; - d^=e>>16; g+=d; e+=f; - e^=f<<10; h+=e; f+=g; - f^=g>>4; a+=f; g+=h; - g^=h<<8; b+=g; h+=a; - h^=a>>9; c+=h; a+=b; - }} - ); - - do 4.times { mix!(); } - - if use_rsl { - macro_rules! memloop ( - ($arr:expr) => {{ - for i in range_step(0u32, RAND_SIZE, 8) { - a+=$arr[i ]; b+=$arr[i+1]; - c+=$arr[i+2]; d+=$arr[i+3]; - e+=$arr[i+4]; f+=$arr[i+5]; - g+=$arr[i+6]; h+=$arr[i+7]; - mix!(); - self.mem[i ]=a; self.mem[i+1]=b; - self.mem[i+2]=c; self.mem[i+3]=d; - self.mem[i+4]=e; self.mem[i+5]=f; - self.mem[i+6]=g; self.mem[i+7]=h; - } - }} - ); - - memloop!(self.rsl); - memloop!(self.mem); - } else { - for i in range_step(0u32, RAND_SIZE, 8) { - mix!(); - self.mem[i ]=a; self.mem[i+1]=b; - self.mem[i+2]=c; self.mem[i+3]=d; - self.mem[i+4]=e; self.mem[i+5]=f; - self.mem[i+6]=g; self.mem[i+7]=h; - } - } - - self.isaac(); + #[inline] + fn next_u64(&mut self) -> u64 { + self.rng.next_u64() } +} - /// Refills the output buffer (`self.rsl`) - #[inline] - fn isaac(&mut self) { - self.c += 1; - // abbreviations - let mut a = self.a; - let mut b = self.b + self.c; - - static MIDPOINT: uint = RAND_SIZE as uint / 2; - - macro_rules! ind (($x:expr) => { - self.mem[($x >> 2) & (RAND_SIZE - 1)] - }); - macro_rules! rngstep( - ($j:expr, $shift:expr) => {{ - let base = $j; - let mix = if $shift < 0 { - a >> -$shift as uint - } else { - a << $shift as uint - }; - - let x = self.mem[base + mr_offset]; - a = (a ^ mix) + self.mem[base + m2_offset]; - let y = ind!(x) + a + b; - self.mem[base + mr_offset] = y; - - b = ind!(y >> RAND_SIZE_LEN) + x; - self.rsl[base + mr_offset] = b; - }} - ); - - let r = [(0, MIDPOINT), (MIDPOINT, 0)]; - for &(mr_offset, m2_offset) in r.iter() { - for i in range_step(0u, MIDPOINT, 4) { - rngstep!(i + 0, 13); - rngstep!(i + 1, -6); - rngstep!(i + 2, 2); - rngstep!(i + 3, -16); - } - } +impl<'self> SeedableRng<&'self [uint]> for StdRng { + fn reseed(&mut self, seed: &'self [uint]) { + // the internal RNG can just be seeded from the above + // randomness. + self.rng.reseed(unsafe {cast::transmute(seed)}) + } - self.a = a; - self.b = b; - self.cnt = RAND_SIZE; + fn from_seed(seed: &'self [uint]) -> StdRng { + StdRng { rng: SeedableRng::from_seed(unsafe {cast::transmute(seed)}) } } } -impl Rng for IsaacRng { - #[inline] - fn next(&mut self) -> u32 { - if self.cnt == 0 { - // make some more numbers - self.isaac(); - } - self.cnt -= 1; - self.rsl[self.cnt] - } +/// Create a weak random number generator with a default algorithm and seed. +/// +/// It returns the fastest `Rng` algorithm currently available in Rust without +/// consideration for cryptography or security. If you require a specifically +/// seeded `Rng` for consistency over time you should pick one algorithm and +/// create the `Rng` yourself. +/// +/// This will read randomness from the operating system to seed the +/// generator. +pub fn weak_rng() -> XorShiftRng { + XorShiftRng::new() } /// An [Xorshift random number @@ -769,7 +607,7 @@ pub struct XorShiftRng { impl Rng for XorShiftRng { #[inline] - fn next(&mut self) -> u32 { + fn next_u32(&mut self) -> u32 { let x = self.x; let t = x ^ (x << 11); self.x = self.y; @@ -781,89 +619,123 @@ impl Rng for XorShiftRng { } } +impl SeedableRng<[u32, .. 4]> for XorShiftRng { + /// Reseed an XorShiftRng. This will fail if `seed` is entirely 0. + 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]; + } + + /// Create a new XorShiftRng. This will fail if `seed` is entirely 0. + 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 XorShiftRng { /// Create an xor shift random number generator with a random seed. pub fn new() -> XorShiftRng { - #[fixed_stack_segment]; #[inline(never)]; - - // generate seeds the same way as seed(), except we have a spceific size let mut s = [0u8, ..16]; loop { - do s.as_mut_buf |p, sz| { - unsafe { - rustrt::rand_gen_seed(p, sz as size_t); - } - } + let mut r = OSRng::new(); + r.fill_bytes(s); + if !s.iter().all(|x| *x == 0) { break; } } - let s: &[u32, ..4] = unsafe { cast::transmute(&s) }; - XorShiftRng::new_seeded(s[0], s[1], s[2], s[3]) - } - - /** - * Create a random number generator using the specified seed. A generator - * constructed with a given seed will generate the same sequence of values - * as all other generators constructed with the same seed. - */ - pub fn new_seeded(x: u32, y: u32, z: u32, w: u32) -> XorShiftRng { - XorShiftRng { - x: x, - y: y, - z: z, - w: w, - } + let s: [u32, ..4] = unsafe { cast::transmute(s) }; + SeedableRng::from_seed(s) } } -/// Create a new random seed. -pub fn seed() -> ~[u8] { - #[fixed_stack_segment]; #[inline(never)]; +/// Controls how the task-local RNG is reseeded. +struct TaskRngReseeder; - unsafe { - let n = RAND_SIZE * 4; - let mut s = vec::from_elem(n as uint, 0_u8); - do s.as_mut_buf |p, sz| { - rustrt::rand_gen_seed(p, sz as size_t) - } - s +impl reseeding::Reseeder<StdRng> for TaskRngReseeder { + fn reseed(&mut self, rng: &mut StdRng) { + *rng = StdRng::new(); } } +static TASK_RNG_RESEED_THRESHOLD: uint = 32_768; +/// The task-local RNG. +pub type TaskRng = reseeding::ReseedingRng<StdRng, TaskRngReseeder>; // used to make space in TLS for a random number generator -local_data_key!(tls_rng_state: @@mut IsaacRng) +local_data_key!(TASK_RNG_KEY: @mut TaskRng) -/** - * Gives back a lazily initialized task-local random number generator, - * seeded by the system. Intended to be used in method chaining style, ie - * `task_rng().gen::<int>()`. - */ -#[inline] -pub fn task_rng() -> @mut IsaacRng { - let r = local_data::get(tls_rng_state, |k| k.map(|&k| *k)); +/// Retrieve the lazily-initialized task-local random number +/// generator, seeded by the system. Intended to be used in method +/// chaining style, e.g. `task_rng().gen::<int>()`. +/// +/// The RNG provided will reseed itself from the operating system +/// after generating a certain amount of randomness. +/// +/// The internal RNG used is platform and architecture dependent, even +/// if the operating system random number generator is rigged to give +/// the same sequence always. If absolute consistency is required, +/// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`. +pub fn task_rng() -> @mut TaskRng { + let r = local_data::get(TASK_RNG_KEY, |k| k.map(|&k| *k)); match r { None => { - let rng = @@mut IsaacRng::new_seeded(seed()); - local_data::set(tls_rng_state, rng); - *rng + let rng = @mut reseeding::ReseedingRng::new(StdRng::new(), + TASK_RNG_RESEED_THRESHOLD, + TaskRngReseeder); + local_data::set(TASK_RNG_KEY, rng); + rng } - Some(rng) => *rng + Some(rng) => rng } } // Allow direct chaining with `task_rng` impl<R: Rng> Rng for @mut R { #[inline] - fn next(&mut self) -> u32 { - (**self).next() + fn next_u32(&mut self) -> u32 { + (**self).next_u32() + } + #[inline] + fn next_u64(&mut self) -> u64 { + (**self).next_u64() + } + + #[inline] + fn fill_bytes(&mut self, bytes: &mut [u8]) { + (**self).fill_bytes(bytes); } } -/** - * Returns a random value of a Rand type, using the task's random number - * generator. - */ +/// Generate a random value using the task-local random number +/// generator. +/// +/// # Example +/// +/// ```rust +/// use std::rand::random; +/// +/// fn main() { +/// if random() { +/// let x = random(); +/// println!("{}", 2u * x); +/// } else { +/// println!("{}", random::<float>()); +/// } +/// } +/// ``` #[inline] pub fn random<T: Rand>() -> T { task_rng().gen() @@ -876,31 +748,11 @@ mod test { use super::*; #[test] - fn test_rng_seeded() { - let seed = seed(); - let mut ra = IsaacRng::new_seeded(seed); - let mut rb = IsaacRng::new_seeded(seed); - assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); - } - - #[test] - fn test_rng_seeded_custom_seed() { - // much shorter than generated seeds which are 1024 bytes - let seed = [2u8, 32u8, 4u8, 32u8, 51u8]; - let mut ra = IsaacRng::new_seeded(seed); - let mut rb = IsaacRng::new_seeded(seed); - assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); - } + fn test_fill_bytes_default() { + let mut r = weak_rng(); - #[test] - fn test_rng_seeded_custom_seed2() { - let seed = [2u8, 32u8, 4u8, 32u8, 51u8]; - let mut ra = IsaacRng::new_seeded(seed); - // Regression test that isaac is actually using the above vector - let r = ra.next(); - debug2!("{:?}", r); - assert!(r == 890007737u32 // on x86_64 - || r == 2935188040u32); // on x86 + let mut v = [0u8, .. 100]; + r.fill_bytes(v); } #[test] @@ -1070,6 +922,26 @@ mod test { **e >= MIN_VAL && **e <= MAX_VAL })); } + + #[test] + fn test_std_rng_seeded() { + let s = OSRng::new().gen_vec::<uint>(256); + let mut ra: StdRng = SeedableRng::from_seed(s.as_slice()); + let mut rb: StdRng = SeedableRng::from_seed(s.as_slice()); + assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); + } + + #[test] + fn test_std_rng_reseed() { + let s = OSRng::new().gen_vec::<uint>(256); + let mut r: StdRng = SeedableRng::from_seed(s.as_slice()); + let string1 = r.gen_ascii_str(100); + + r.reseed(s); + + let string2 = r.gen_ascii_str(100); + assert_eq!(string1, string2); + } } #[cfg(test)] @@ -1097,6 +969,24 @@ mod bench { } #[bench] + fn rand_isaac64(bh: &mut BenchHarness) { + let mut rng = Isaac64Rng::new(); + do bh.iter { + rng.gen::<uint>(); + } + bh.bytes = size_of::<uint>() as u64; + } + + #[bench] + fn rand_std(bh: &mut BenchHarness) { + let mut rng = StdRng::new(); + do bh.iter { + rng.gen::<uint>(); + } + bh.bytes = size_of::<uint>() as u64; + } + + #[bench] fn rand_shuffle_100(bh: &mut BenchHarness) { let mut rng = XorShiftRng::new(); let x : &mut[uint] = [1,..100]; diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs new file mode 100644 index 00000000000..4c8cf06c55e --- /dev/null +++ b/src/libstd/rand/os.rs @@ -0,0 +1,178 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Interfaces to the operating system provided random number +//! generators. + +use rand::Rng; +use ops::Drop; + +#[cfg(unix)] +use rand::reader::ReaderRng; +#[cfg(unix)] +use rt::io::{file, Open, Read}; + +#[cfg(windows)] +use cast; +#[cfg(windows)] +use libc::{c_long, DWORD, BYTE}; +#[cfg(windows)] +type HCRYPTPROV = c_long; +// the extern functions imported from the runtime on Windows are +// implemented so that they either succeed or abort(), so we can just +// assume they work when we call them. + +/// A random number generator that retrieves randomness straight from +/// the operating system. On Unix-like systems this reads from +/// `/dev/urandom`, on Windows this uses `CryptGenRandom`. +/// +/// This does not block. +#[cfg(unix)] +pub struct OSRng { + priv inner: ReaderRng<file::FileStream> +} +/// A random number generator that retrieves randomness straight from +/// the operating system. On Unix-like systems this reads from +/// `/dev/urandom`, on Windows this uses `CryptGenRandom`. +/// +/// This does not block. +#[cfg(windows)] +pub struct OSRng { + priv hcryptprov: HCRYPTPROV +} + +impl OSRng { + /// Create a new `OSRng`. + #[cfg(unix)] + pub fn new() -> OSRng { + let reader = file::open(& &"/dev/urandom", Open, Read).expect("Error opening /dev/urandom"); + let reader_rng = ReaderRng::new(reader); + + OSRng { inner: reader_rng } + } + + /// Create a new `OSRng`. + #[cfg(windows)] + pub fn new() -> OSRng { + externfn!(fn rust_win32_rand_acquire(phProv: *mut HCRYPTPROV)) + + let mut hcp = 0; + unsafe {rust_win32_rand_acquire(&mut hcp)}; + + OSRng { hcryptprov: hcp } + } +} + +#[cfg(unix)] +impl Rng for OSRng { + fn next_u32(&mut self) -> u32 { + self.inner.next_u32() + } + fn next_u64(&mut self) -> u64 { + self.inner.next_u64() + } + fn fill_bytes(&mut self, v: &mut [u8]) { + self.inner.fill_bytes(v) + } +} + +#[cfg(windows)] +impl Rng for OSRng { + fn next_u32(&mut self) -> u32 { + let mut v = [0u8, .. 4]; + self.fill_bytes(v); + unsafe { cast::transmute(v) } + } + fn next_u64(&mut self) -> u64 { + let mut v = [0u8, .. 8]; + self.fill_bytes(v); + unsafe { cast::transmute(v) } + } + fn fill_bytes(&mut self, v: &mut [u8]) { + externfn!(fn rust_win32_rand_gen(hProv: HCRYPTPROV, dwLen: DWORD, pbBuffer: *mut BYTE)) + + do v.as_mut_buf |ptr, len| { + unsafe {rust_win32_rand_gen(self.hcryptprov, len as DWORD, ptr)} + } + } +} + +impl Drop for OSRng { + #[cfg(unix)] + fn drop(&mut self) { + // ensure that OSRng is not implicitly copyable on all + // platforms, for consistency. + } + + #[cfg(windows)] + fn drop(&mut self) { + externfn!(fn rust_win32_rand_release(hProv: HCRYPTPROV)) + + unsafe {rust_win32_rand_release(self.hcryptprov)} + } +} + + +#[cfg(test)] +mod test { + use super::*; + use rand::Rng; + + #[test] + fn test_os_rng() { + let mut r = OSRng::new(); + + r.next_u32(); + r.next_u64(); + + let mut v = [0u8, .. 1000]; + r.fill_bytes(v); + } + + #[test] + fn test_os_rng_tasks() { + use task; + use comm; + use comm::{GenericChan, GenericPort}; + use option::{None, Some}; + use iter::{Iterator, range}; + use vec::{ImmutableVector, OwnedVector}; + + let mut chans = ~[]; + for _ in range(0, 20) { + let (p, c) = comm::stream(); + chans.push(c); + do task::spawn_with(p) |p| { + // wait until all the tasks are ready to go. + p.recv(); + + // deschedule to attempt to interleave things as much + // as possible (XXX: is this a good test?) + let mut r = OSRng::new(); + task::deschedule(); + let mut v = [0u8, .. 1000]; + + for _ in range(0, 100) { + r.next_u32(); + task::deschedule(); + r.next_u64(); + task::deschedule(); + r.fill_bytes(v); + task::deschedule(); + } + } + } + + // start all the tasks + for c in chans.iter() { + c.send(()) + } + } +} diff --git a/src/libstd/rand/rand_impls.rs b/src/libstd/rand/rand_impls.rs new file mode 100644 index 00000000000..aad0d4e861c --- /dev/null +++ b/src/libstd/rand/rand_impls.rs @@ -0,0 +1,224 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The implementations of `Rand` for the built-in types. + +use char; +use int; +use option::{Option, Some, None}; +use rand::{Rand,Rng}; +use uint; + +impl Rand for int { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> int { + if int::bits == 32 { + rng.gen::<i32>() as int + } else { + rng.gen::<i64>() as int + } + } +} + +impl Rand for i8 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> i8 { + rng.next_u32() as i8 + } +} + +impl Rand for i16 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> i16 { + rng.next_u32() as i16 + } +} + +impl Rand for i32 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> i32 { + rng.next_u32() as i32 + } +} + +impl Rand for i64 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> i64 { + rng.next_u64() as i64 + } +} + +impl Rand for uint { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> uint { + if uint::bits == 32 { + rng.gen::<u32>() as uint + } else { + rng.gen::<u64>() as uint + } + } +} + +impl Rand for u8 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> u8 { + rng.next_u32() as u8 + } +} + +impl Rand for u16 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> u16 { + rng.next_u32() as u16 + } +} + +impl Rand for u32 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> u32 { + rng.next_u32() + } +} + +impl Rand for u64 { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> u64 { + rng.next_u64() + } +} + +impl Rand for f32 { + /// A random `f32` in the range `[0, 1)`, using 24 bits of + /// precision. + #[inline] + fn rand<R: Rng>(rng: &mut R) -> f32 { + // using any more than 24 bits will cause (e.g.) 0xffff_ffff + // to correspond to 1 exactly, so we need to drop 8 to + // guarantee the open end. + + static SCALE: f32 = (1u32 << 24) as f32; + (rng.next_u32() >> 8) as f32 / SCALE + } +} + +impl Rand for f64 { + /// A random `f64` in the range `[0, 1)`, using 53 bits of + /// precision. + #[inline] + fn rand<R: Rng>(rng: &mut R) -> f64 { + // as for f32, but using more bits. + + static SCALE: f64 = (1u64 << 53) as f64; + (rng.next_u64() >> 11) as f64 / SCALE + } +} + + +impl Rand for char { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> char { + // a char is 21 bits + static CHAR_MASK: u32 = 0x001f_ffff; + loop { + // Rejection sampling. About 0.2% of numbers with at most + // 21-bits are invalid codepoints (surrogates), so this + // will succeed first go almost every time. + match char::from_u32(rng.next_u32() & CHAR_MASK) { + Some(c) => return c, + None => {} + } + } + } +} + +impl Rand for bool { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> bool { + rng.gen::<u8>() & 1 == 1 + } +} + +macro_rules! tuple_impl { + // use variables to indicate the arity of the tuple + ($($tyvar:ident),* ) => { + // the trailing commas are for the 1 tuple + impl< + $( $tyvar : Rand ),* + > Rand for ( $( $tyvar ),* , ) { + + #[inline] + fn rand<R: Rng>(_rng: &mut R) -> ( $( $tyvar ),* , ) { + ( + // use the $tyvar's to get the appropriate number of + // repeats (they're not actually needed) + $( + _rng.gen::<$tyvar>() + ),* + , + ) + } + } + } +} + +impl Rand for () { + #[inline] + fn rand<R: Rng>(_: &mut R) -> () { () } +} +tuple_impl!{A} +tuple_impl!{A, B} +tuple_impl!{A, B, C} +tuple_impl!{A, B, C, D} +tuple_impl!{A, B, C, D, E} +tuple_impl!{A, B, C, D, E, F} +tuple_impl!{A, B, C, D, E, F, G} +tuple_impl!{A, B, C, D, E, F, G, H} +tuple_impl!{A, B, C, D, E, F, G, H, I} +tuple_impl!{A, B, C, D, E, F, G, H, I, J} + +impl<T:Rand> Rand for Option<T> { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> Option<T> { + if rng.gen() { + Some(rng.gen()) + } else { + None + } + } +} + +impl<T: Rand> Rand for ~T { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> ~T { ~rng.gen() } +} + +impl<T: Rand + 'static> Rand for @T { + #[inline] + fn rand<R: Rng>(rng: &mut R) -> @T { @rng.gen() } +} + +#[cfg(test)] +mod tests { + use rand::Rng; + struct ConstantRng(u64); + impl Rng for ConstantRng { + fn next_u32(&mut self) -> u32 { + (**self) as u32 + } + fn next_u64(&mut self) -> u64 { + **self + } + } + fn floating_point_edge_cases() { + // the test for exact equality is correct here. + assert!(ConstantRng(0xffff_ffff).gen::<f32>() != 1.0) + assert!(ConstantRng(0xffff_ffff_ffff_ffff).gen::<f64>() != 1.0) + } +} diff --git a/src/libstd/rand/reader.rs b/src/libstd/rand/reader.rs new file mode 100644 index 00000000000..961a5b2cd28 --- /dev/null +++ b/src/libstd/rand/reader.rs @@ -0,0 +1,124 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! A wrapper around any Reader to treat it as an RNG. + +use option::{Some, None}; +use rt::io::Reader; +use rt::io::ReaderByteConversions; + +use rand::Rng; + +/// An RNG that reads random bytes straight from a `Reader`. This will +/// work best with an infinite reader, but this is not required. +/// +/// It will fail if it there is insufficient data to fulfill a request. +/// +/// # Example +/// +/// ```rust +/// use std::rand::{reader, Rng}; +/// use std::rt::io::mem; +/// +/// fn main() { +/// let mut rng = reader::ReaderRng::new(mem::MemReader::new(~[1,2,3,4,5,6,7,8])); +/// println!("{:x}", rng.gen::<uint>()); +/// } +/// ``` +pub struct ReaderRng<R> { + priv reader: R +} + +impl<R: Reader> ReaderRng<R> { + /// Create a new `ReaderRng` from a `Reader`. + pub fn new(r: R) -> ReaderRng<R> { + ReaderRng { + reader: r + } + } +} + +impl<R: Reader> Rng for ReaderRng<R> { + fn next_u32(&mut self) -> u32 { + // This is designed for speed: reading a LE integer on a LE + // platform just involves blitting the bytes into the memory + // of the u32, similarly for BE on BE; avoiding byteswapping. + if cfg!(target_endian="little") { + self.reader.read_le_u32_() + } else { + self.reader.read_be_u32_() + } + } + fn next_u64(&mut self) -> u64 { + // see above for explanation. + if cfg!(target_endian="little") { + self.reader.read_le_u64_() + } else { + self.reader.read_be_u64_() + } + } + fn fill_bytes(&mut self, v: &mut [u8]) { + if v.len() == 0 { return } + match self.reader.read(v) { + Some(n) if n == v.len() => return, + Some(n) => fail2!("ReaderRng.fill_bytes could not fill buffer: \ + read {} out of {} bytes.", n, v.len()), + None => fail2!("ReaderRng.fill_bytes reached eof.") + } + } +} + +#[cfg(test)] +mod test { + use super::*; + use rt::io::mem::MemReader; + use cast; + + #[test] + fn test_reader_rng_u64() { + // transmute from the target to avoid endianness concerns. + let v = ~[1u64, 2u64, 3u64]; + let bytes: ~[u8] = unsafe {cast::transmute(v)}; + let mut rng = ReaderRng::new(MemReader::new(bytes)); + + assert_eq!(rng.next_u64(), 1); + assert_eq!(rng.next_u64(), 2); + assert_eq!(rng.next_u64(), 3); + } + #[test] + fn test_reader_rng_u32() { + // transmute from the target to avoid endianness concerns. + let v = ~[1u32, 2u32, 3u32]; + let bytes: ~[u8] = unsafe {cast::transmute(v)}; + let mut rng = ReaderRng::new(MemReader::new(bytes)); + + assert_eq!(rng.next_u32(), 1); + assert_eq!(rng.next_u32(), 2); + assert_eq!(rng.next_u32(), 3); + } + #[test] + fn test_reader_rng_fill_bytes() { + let v = [1u8, 2, 3, 4, 5, 6, 7, 8]; + let mut w = [0u8, .. 8]; + + let mut rng = ReaderRng::new(MemReader::new(v.to_owned())); + rng.fill_bytes(w); + + assert_eq!(v, w); + } + + #[test] + #[should_fail] + fn test_reader_rng_insufficient_bytes() { + let mut rng = ReaderRng::new(MemReader::new(~[])); + let mut v = [0u8, .. 3]; + rng.fill_bytes(v); + } +} diff --git a/src/libstd/rand/reseeding.rs b/src/libstd/rand/reseeding.rs new file mode 100644 index 00000000000..3b4919392fc --- /dev/null +++ b/src/libstd/rand/reseeding.rs @@ -0,0 +1,204 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! A wrapper around another RNG that reseeds it after it +//! generates a certain number of random bytes. + +use rand::{Rng, SeedableRng}; +use default::Default; + +/// How many bytes of entropy the underling RNG is allowed to generate +/// before it is reseeded. +static DEFAULT_GENERATION_THRESHOLD: uint = 32 * 1024; + +/// A wrapper around any RNG which reseeds the underlying RNG after it +/// has generated a certain number of random bytes. +pub struct ReseedingRng<R, Rsdr> { + priv rng: R, + priv generation_threshold: uint, + priv bytes_generated: uint, + /// Controls the behaviour when reseeding the RNG. + reseeder: Rsdr +} + +impl<R: Rng, Rsdr: Reseeder<R>> ReseedingRng<R, Rsdr> { + /// Create a new `ReseedingRng` with the given parameters. + /// + /// # Arguments + /// + /// * `rng`: the random number generator to use. + /// * `generation_threshold`: the number of bytes of entropy at which to reseed the RNG. + /// * `reseeder`: the reseeding object to use. + pub fn new(rng: R, generation_threshold: uint, reseeder: Rsdr) -> ReseedingRng<R,Rsdr> { + ReseedingRng { + rng: rng, + generation_threshold: generation_threshold, + bytes_generated: 0, + reseeder: reseeder + } + } + + /// Reseed the internal RNG if the number of bytes that have been + /// generated exceed the threshold. + pub fn reseed_if_necessary(&mut self) { + if self.bytes_generated >= self.generation_threshold { + self.reseeder.reseed(&mut self.rng); + self.bytes_generated = 0; + } + } +} + + +impl<R: Rng, Rsdr: Reseeder<R>> Rng for ReseedingRng<R, Rsdr> { + fn next_u32(&mut self) -> u32 { + self.reseed_if_necessary(); + self.bytes_generated += 4; + self.rng.next_u32() + } + + fn next_u64(&mut self) -> u64 { + self.reseed_if_necessary(); + self.bytes_generated += 8; + self.rng.next_u64() + } + + fn fill_bytes(&mut self, dest: &mut [u8]) { + self.reseed_if_necessary(); + self.bytes_generated += dest.len(); + self.fill_bytes(dest) + } +} + +impl<S, R: SeedableRng<S>, Rsdr: Reseeder<R>> + SeedableRng<(Rsdr, S)> for ReseedingRng<R, Rsdr> { + fn reseed(&mut self, (rsdr, seed): (Rsdr, S)) { + self.rng.reseed(seed); + self.reseeder = rsdr; + self.bytes_generated = 0; + } + /// Create a new `ReseedingRng` from the given reseeder and + /// seed. This uses a default value for `generation_threshold`. + fn from_seed((rsdr, seed): (Rsdr, S)) -> ReseedingRng<R, Rsdr> { + ReseedingRng { + rng: SeedableRng::from_seed(seed), + generation_threshold: DEFAULT_GENERATION_THRESHOLD, + bytes_generated: 0, + reseeder: rsdr + } + } +} + +/// Something that can be used to reseed an RNG via `ReseedingRng`. +/// +/// # Example +/// +/// ```rust +/// use std::rand; +/// use std::rand::{Rng, SeedableRng}; +/// use std::rand::reseeding::{Reseeder, ReseedingRng}; +/// +/// struct TickTockReseeder { tick: bool } +/// impl Reseeder<rand::StdRng> for TickTockReseeder { +/// fn reseed(&mut self, rng: &mut rand::StdRng) { +/// let val = if self.tick {0} else {1}; +/// rng.reseed(&[val]); +/// self.tick = !self.tick; +/// } +/// } +/// fn main() { +/// let rsdr = TickTockReseeder { tick: true }; +/// let mut rng = ReseedingRng::new(rand::StdRng::new(), 10, rsdr); +/// +/// // this will repeat, because it gets reseeded very regularly. +/// println(rng.gen_ascii_str(100)); +/// } +/// +/// ``` +pub trait Reseeder<R> { + /// Reseed the given RNG. + fn reseed(&mut self, rng: &mut R); +} + +/// Reseed an RNG using a `Default` instance. This reseeds by +/// replacing the RNG with the result of a `Default::default` call. +pub struct ReseedWithDefault; + +impl<R: Rng + Default> Reseeder<R> for ReseedWithDefault { + fn reseed(&mut self, rng: &mut R) { + *rng = Default::default(); + } +} +impl Default for ReseedWithDefault { + fn default() -> ReseedWithDefault { ReseedWithDefault } +} + +#[cfg(test)] +mod test { + use super::*; + use rand::{SeedableRng, Rng}; + use default::Default; + use iter::range; + use option::{None, Some}; + + struct Counter { + i: u32 + } + + impl Rng for Counter { + fn next_u32(&mut self) -> u32 { + self.i += 1; + // very random + self.i - 1 + } + } + impl Default for Counter { + fn default() -> Counter { + Counter { i: 0 } + } + } + impl SeedableRng<u32> for Counter { + fn reseed(&mut self, seed: u32) { + self.i = seed; + } + fn from_seed(seed: u32) -> Counter { + Counter { i: seed } + } + } + type MyRng = ReseedingRng<Counter, ReseedWithDefault>; + + #[test] + fn test_reseeding() { + let mut rs = ReseedingRng::new(Counter {i:0}, 400, ReseedWithDefault); + + let mut i = 0; + for _ in range(0, 1000) { + assert_eq!(rs.next_u32(), i % 100); + i += 1; + } + } + + #[test] + fn test_rng_seeded() { + let mut ra: MyRng = SeedableRng::from_seed((ReseedWithDefault, 2)); + let mut rb: MyRng = SeedableRng::from_seed((ReseedWithDefault, 2)); + assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u)); + } + + #[test] + fn test_rng_reseed() { + let mut r: MyRng = SeedableRng::from_seed((ReseedWithDefault, 3)); + let string1 = r.gen_ascii_str(100); + + r.reseed((ReseedWithDefault, 3)); + + let string2 = r.gen_ascii_str(100); + assert_eq!(string1, string2); + } +} diff --git a/src/libstd/rt/sched.rs b/src/libstd/rt/sched.rs index cbffec51cc9..ee43ced44ab 100644 --- a/src/libstd/rt/sched.rs +++ b/src/libstd/rt/sched.rs @@ -140,7 +140,7 @@ impl Scheduler { cleanup_job: None, run_anything: run_anything, friend_handle: friend, - rng: XorShiftRng::new(), + rng: new_sched_rng(), idle_callback: None, yield_check_count: 0, steal_for_yield: false @@ -844,6 +844,54 @@ impl ClosureConverter for UnsafeTaskReceiver { fn to_fn(self) -> &fn(&mut Scheduler, ~Task) { unsafe { transmute(self) } } } +// On unix, we read randomness straight from /dev/urandom, but the +// default constructor of an XorShiftRng does this via io::file, which +// relies on the scheduler existing, so we have to manually load +// randomness. Windows has its own C API for this, so we don't need to +// worry there. +#[cfg(windows)] +fn new_sched_rng() -> XorShiftRng { + XorShiftRng::new() +} +#[cfg(unix)] +#[fixed_stack_segment] #[inline(never)] +fn new_sched_rng() -> XorShiftRng { + use libc; + use sys; + use c_str::ToCStr; + use vec::MutableVector; + use iter::Iterator; + use rand::SeedableRng; + + let fd = do "/dev/urandom".with_c_str |name| { + unsafe { libc::open(name, libc::O_RDONLY, 0) } + }; + if fd == -1 { + rtabort!("could not open /dev/urandom for reading.") + } + + let mut seeds = [0u32, .. 4]; + let size = sys::size_of_val(&seeds); + loop { + let nbytes = do seeds.as_mut_buf |buf, _| { + unsafe { + libc::read(fd, + buf as *mut libc::c_void, + size as libc::size_t) + } + }; + rtassert!(nbytes as uint == size); + + if !seeds.iter().all(|x| *x == 0) { + break; + } + } + + unsafe {libc::close(fd);} + + SeedableRng::from_seed(seeds) +} + #[cfg(test)] mod test { extern mod extra; diff --git a/src/libstd/rt/task.rs b/src/libstd/rt/task.rs index 2d1b57cebf5..48b894f51e0 100644 --- a/src/libstd/rt/task.rs +++ b/src/libstd/rt/task.rs @@ -509,7 +509,7 @@ mod test { do run_in_newsched_task() { use rand::{rng, Rng}; let mut r = rng(); - let _ = r.next(); + let _ = r.next_u32(); } } |