diff options
46 files changed, 161 insertions, 4380 deletions
diff --git a/src/Cargo.lock b/src/Cargo.lock index 0263c74595f..79aea99a5a9 100644 --- a/src/Cargo.lock +++ b/src/Cargo.lock @@ -28,6 +28,7 @@ name = "alloc" version = "0.0.0" dependencies = [ "core 0.0.0", + "rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)", "std_unicode 0.0.0", ] @@ -367,7 +368,7 @@ version = "0.1.0" name = "core" version = "0.0.0" dependencies = [ - "rand 0.0.0", + "rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)", ] [[package]] @@ -1368,13 +1369,6 @@ dependencies = [ [[package]] name = "rand" -version = "0.0.0" -dependencies = [ - "core 0.0.0", -] - -[[package]] -name = "rand" version = "0.3.17" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ @@ -1596,6 +1590,7 @@ name = "rustc_back" version = "0.0.0" dependencies = [ "log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", + "rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)", "serialize 0.0.0", "syntax 0.0.0", ] @@ -1703,6 +1698,7 @@ version = "0.0.0" dependencies = [ "graphviz 0.0.0", "log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", + "rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)", "rustc 0.0.0", "rustc_data_structures 0.0.0", "serialize 0.0.0", @@ -2125,7 +2121,7 @@ dependencies = [ "panic_abort 0.0.0", "panic_unwind 0.0.0", "profiler_builtins 0.0.0", - "rand 0.0.0", + "rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)", "rustc_asan 0.0.0", "rustc_lsan 0.0.0", "rustc_msan 0.0.0", diff --git a/src/bootstrap/compile.rs b/src/bootstrap/compile.rs index 4540f620872..db013691bb1 100644 --- a/src/bootstrap/compile.rs +++ b/src/bootstrap/compile.rs @@ -107,8 +107,8 @@ impl Step for Std { let mut cargo = builder.cargo(compiler, Mode::Libstd, target, "build"); std_cargo(build, &compiler, target, &mut cargo); run_cargo(build, - &mut cargo, - &libstd_stamp(build, compiler, target)); + &mut cargo, + &libstd_stamp(build, compiler, target)); builder.ensure(StdLink { compiler: builder.compiler(compiler.stage, build.build), @@ -359,8 +359,8 @@ impl Step for Test { let mut cargo = builder.cargo(compiler, Mode::Libtest, target, "build"); test_cargo(build, &compiler, target, &mut cargo); run_cargo(build, - &mut cargo, - &libtest_stamp(build, compiler, target)); + &mut cargo, + &libtest_stamp(build, compiler, target)); builder.ensure(TestLink { compiler: builder.compiler(compiler.stage, build.build), @@ -866,12 +866,13 @@ fn run_cargo(build: &Build, cargo: &mut Command, stamp: &Path) { // `std-<hash>.dll.lib` on Windows. The aforementioned methods only // split the file name by the last extension (`.lib`) while we need // to split by all extensions (`.dll.lib`). + let expected_len = t!(filename.metadata()).len(); let filename = filename.file_name().unwrap().to_str().unwrap(); let mut parts = filename.splitn(2, '.'); let file_stem = parts.next().unwrap().to_owned(); let extension = parts.next().unwrap().to_owned(); - toplevel.push((file_stem, extension)); + toplevel.push((file_stem, extension, expected_len)); } } @@ -891,11 +892,12 @@ fn run_cargo(build: &Build, cargo: &mut Command, stamp: &Path) { .map(|e| t!(e)) .map(|e| (e.path(), e.file_name().into_string().unwrap(), t!(e.metadata()))) .collect::<Vec<_>>(); - for (prefix, extension) in toplevel { - let candidates = contents.iter().filter(|&&(_, ref filename, _)| { + for (prefix, extension, expected_len) in toplevel { + let candidates = contents.iter().filter(|&&(_, ref filename, ref meta)| { filename.starts_with(&prefix[..]) && filename[prefix.len()..].starts_with("-") && - filename.ends_with(&extension[..]) + filename.ends_with(&extension[..]) && + meta.len() == expected_len }); let max = candidates.max_by_key(|&&(_, _, ref metadata)| { FileTime::from_last_modification_time(metadata) diff --git a/src/bootstrap/dist.rs b/src/bootstrap/dist.rs index e79f6e086ae..090fb6c778c 100644 --- a/src/bootstrap/dist.rs +++ b/src/bootstrap/dist.rs @@ -743,7 +743,6 @@ impl Step for Src { "src/liblibc", "src/libpanic_abort", "src/libpanic_unwind", - "src/librand", "src/librustc_asan", "src/librustc_lsan", "src/librustc_msan", diff --git a/src/doc/unstable-book/src/library-features/rand.md b/src/doc/unstable-book/src/library-features/rand.md deleted file mode 100644 index d0229d94c20..00000000000 --- a/src/doc/unstable-book/src/library-features/rand.md +++ /dev/null @@ -1,5 +0,0 @@ -# `rand` - -This feature is internal to the Rust compiler and is not intended for general use. - ------------------------- diff --git a/src/liballoc/Cargo.toml b/src/liballoc/Cargo.toml index 686e5681d12..0a265ee1376 100644 --- a/src/liballoc/Cargo.toml +++ b/src/liballoc/Cargo.toml @@ -11,6 +11,9 @@ path = "lib.rs" core = { path = "../libcore" } std_unicode = { path = "../libstd_unicode" } +[dev-dependencies] +rand = "0.3" + [[test]] name = "collectionstests" path = "../liballoc/tests/lib.rs" diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs index a40ed060604..3cc3ea46796 100644 --- a/src/liballoc/lib.rs +++ b/src/liballoc/lib.rs @@ -135,6 +135,8 @@ extern crate std; #[cfg(test)] extern crate test; +#[cfg(test)] +extern crate rand; extern crate std_unicode; diff --git a/src/liballoc/linked_list.rs b/src/liballoc/linked_list.rs index f897feb7afa..fac6acaca61 100644 --- a/src/liballoc/linked_list.rs +++ b/src/liballoc/linked_list.rs @@ -1269,10 +1269,11 @@ unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {} #[cfg(test)] mod tests { - use std::__rand::{thread_rng, Rng}; use std::thread; use std::vec::Vec; + use rand::{thread_rng, Rng}; + use super::{LinkedList, Node}; #[cfg(test)] diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs index c5beb63d12e..00ebd88d464 100644 --- a/src/liballoc/tests/lib.rs +++ b/src/liballoc/tests/lib.rs @@ -30,6 +30,7 @@ #![feature(unicode)] extern crate std_unicode; +extern crate rand; use std::hash::{Hash, Hasher}; use std::collections::hash_map::DefaultHasher; diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs index c53bf15f1bf..85d5ce304b8 100644 --- a/src/liballoc/tests/slice.rs +++ b/src/liballoc/tests/slice.rs @@ -10,9 +10,10 @@ use std::cmp::Ordering::{Equal, Greater, Less}; use std::mem; -use std::__rand::{Rng, thread_rng}; use std::rc::Rc; +use rand::{Rng, thread_rng}; + fn square(n: usize) -> usize { n * n } diff --git a/src/libcore/Cargo.toml b/src/libcore/Cargo.toml index 178df02ccdd..d1a0a5f09e0 100644 --- a/src/libcore/Cargo.toml +++ b/src/libcore/Cargo.toml @@ -10,7 +10,7 @@ test = false bench = false [dev-dependencies] -rand = { path = "../librand" } +rand = "0.3" [[test]] name = "coretests" diff --git a/src/libcore/tests/num/flt2dec/mod.rs b/src/libcore/tests/num/flt2dec/mod.rs index 0f4d19e7092..2720c5c8677 100644 --- a/src/libcore/tests/num/flt2dec/mod.rs +++ b/src/libcore/tests/num/flt2dec/mod.rs @@ -10,8 +10,7 @@ use std::prelude::v1::*; use std::{str, mem, i16, f32, f64, fmt}; -use std::__rand as rand; -use rand::{Rand, XorShiftRng}; +use rand::{self, Rand, XorShiftRng}; use rand::distributions::{IndependentSample, Range}; use core::num::flt2dec::{decode, DecodableFloat, FullDecoded, Decoded}; diff --git a/src/librand/Cargo.toml b/src/librand/Cargo.toml deleted file mode 100644 index eda5f217565..00000000000 --- a/src/librand/Cargo.toml +++ /dev/null @@ -1,12 +0,0 @@ -[package] -authors = ["The Rust Project Developers"] -name = "rand" -version = "0.0.0" - -[lib] -name = "rand" -path = "lib.rs" -doc = false - -[dependencies] -core = { path = "../libcore" } diff --git a/src/librand/chacha.rs b/src/librand/chacha.rs deleted file mode 100644 index e355eb44e46..00000000000 --- a/src/librand/chacha.rs +++ /dev/null @@ -1,309 +0,0 @@ -// Copyright 2014 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 ChaCha random number generator. - -use core::fmt; -use {Rand, Rng, SeedableRng}; - -const KEY_WORDS: usize = 8; // 8 words for the 256-bit key -const STATE_WORDS: usize = 16; -const CHACHA_ROUNDS: usize = 20; // Cryptographically secure from 8 upwards as of this writing - -/// A random number generator that uses the ChaCha20 algorithm [1]. -/// -/// The ChaCha algorithm is widely accepted as suitable for -/// cryptographic purposes, but this implementation has not been -/// verified as such. Prefer a generator like `OsRng` that defers to -/// the operating system for cases that need high security. -/// -/// [1]: D. J. Bernstein, [*ChaCha, a variant of -/// Salsa20*](http://cr.yp.to/chacha.html) -#[derive(Copy, Clone)] -pub struct ChaChaRng { - buffer: [u32; STATE_WORDS], // Internal buffer of output - state: [u32; STATE_WORDS], // Initial state - index: usize, // Index into state -} - -impl fmt::Debug for ChaChaRng { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("ChaChaRng") - .field("buffer", &self.buffer.iter()) - .field("state", &self.state.iter()) - .field("index", &self.index) - .finish() - } -} - -static EMPTY: ChaChaRng = ChaChaRng { - buffer: [0; STATE_WORDS], - state: [0; STATE_WORDS], - index: STATE_WORDS, -}; - - -macro_rules! quarter_round{ - ($a: expr, $b: expr, $c: expr, $d: expr) => {{ - $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left(16); - $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left(12); - $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left( 8); - $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left( 7); - }} -} - -macro_rules! double_round{ - ($x: expr) => {{ - // Column round - quarter_round!($x[ 0], $x[ 4], $x[ 8], $x[12]); - quarter_round!($x[ 1], $x[ 5], $x[ 9], $x[13]); - quarter_round!($x[ 2], $x[ 6], $x[10], $x[14]); - quarter_round!($x[ 3], $x[ 7], $x[11], $x[15]); - // Diagonal round - quarter_round!($x[ 0], $x[ 5], $x[10], $x[15]); - quarter_round!($x[ 1], $x[ 6], $x[11], $x[12]); - quarter_round!($x[ 2], $x[ 7], $x[ 8], $x[13]); - quarter_round!($x[ 3], $x[ 4], $x[ 9], $x[14]); - }} -} - -#[inline] -fn core(output: &mut [u32; STATE_WORDS], input: &[u32; STATE_WORDS]) { - *output = *input; - - for _ in 0..CHACHA_ROUNDS / 2 { - double_round!(output); - } - - for i in 0..STATE_WORDS { - output[i] = output[i].wrapping_add(input[i]); - } -} - -impl ChaChaRng { - /// Create an ChaCha random number generator using the default - /// fixed key of 8 zero words. - pub fn new_unseeded() -> ChaChaRng { - let mut rng = EMPTY; - rng.init(&[0; KEY_WORDS]); - rng - } - - /// Sets the internal 128-bit ChaCha counter to - /// a user-provided value. This permits jumping - /// arbitrarily ahead (or backwards) in the pseudorandom stream. - /// - /// Since the nonce words are used to extend the counter to 128 bits, - /// users wishing to obtain the conventional ChaCha pseudorandom stream - /// associated with a particular nonce can call this function with - /// arguments `0, desired_nonce`. - pub fn set_counter(&mut self, counter_low: u64, counter_high: u64) { - self.state[12] = (counter_low >> 0) as u32; - self.state[13] = (counter_low >> 32) as u32; - self.state[14] = (counter_high >> 0) as u32; - self.state[15] = (counter_high >> 32) as u32; - self.index = STATE_WORDS; // force recomputation - } - - /// Initializes `self.state` with the appropriate key and constants - /// - /// We deviate slightly from the ChaCha specification regarding - /// the nonce, which is used to extend the counter to 128 bits. - /// This is provably as strong as the original cipher, though, - /// since any distinguishing attack on our variant also works - /// against ChaCha with a chosen-nonce. See the XSalsa20 [1] - /// security proof for a more involved example of this. - /// - /// The modified word layout is: - /// ```text - /// constant constant constant constant - /// key key key key - /// key key key key - /// counter counter counter counter - /// ``` - /// [1]: Daniel J. Bernstein. [*Extending the Salsa20 - /// nonce.*](http://cr.yp.to/papers.html#xsalsa) - fn init(&mut self, key: &[u32; KEY_WORDS]) { - self.state[0] = 0x61707865; - self.state[1] = 0x3320646E; - self.state[2] = 0x79622D32; - self.state[3] = 0x6B206574; - - for i in 0..KEY_WORDS { - self.state[4 + i] = key[i]; - } - - self.state[12] = 0; - self.state[13] = 0; - self.state[14] = 0; - self.state[15] = 0; - - self.index = STATE_WORDS; - } - - /// Refill the internal output buffer (`self.buffer`) - fn update(&mut self) { - core(&mut self.buffer, &self.state); - self.index = 0; - // update 128-bit counter - self.state[12] += 1; - if self.state[12] != 0 { - return; - } - self.state[13] += 1; - if self.state[13] != 0 { - return; - } - self.state[14] += 1; - if self.state[14] != 0 { - return; - } - self.state[15] += 1; - } -} - -impl Rng for ChaChaRng { - #[inline] - fn next_u32(&mut self) -> u32 { - if self.index == STATE_WORDS { - self.update(); - } - - let value = self.buffer[self.index % STATE_WORDS]; - self.index += 1; - value - } -} - -impl<'a> SeedableRng<&'a [u32]> for ChaChaRng { - fn reseed(&mut self, seed: &'a [u32]) { - // reset state - self.init(&[0; KEY_WORDS]); - // set key in place - let key = &mut self.state[4..4 + KEY_WORDS]; - for (k, s) in key.iter_mut().zip(seed) { - *k = *s; - } - } - - /// Create a ChaCha generator from a seed, - /// obtained from a variable-length u32 array. - /// Only up to 8 words are used; if less than 8 - /// words are used, the remaining are set to zero. - fn from_seed(seed: &'a [u32]) -> ChaChaRng { - let mut rng = EMPTY; - rng.reseed(seed); - rng - } -} - -impl Rand for ChaChaRng { - fn rand<R: Rng>(other: &mut R) -> ChaChaRng { - let mut key: [u32; KEY_WORDS] = [0; KEY_WORDS]; - for word in &mut key { - *word = other.gen(); - } - SeedableRng::from_seed(&key[..]) - } -} - - -#[cfg(test)] -mod tests { - use std::prelude::v1::*; - - use {Rng, SeedableRng}; - use super::ChaChaRng; - - #[test] - fn test_rng_rand_seeded() { - let s = ::test::rng().gen_iter::<u32>().take(8).collect::<Vec<u32>>(); - let mut ra: ChaChaRng = SeedableRng::from_seed(&*s); - let mut rb: ChaChaRng = SeedableRng::from_seed(&*s); - assert!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - - #[test] - fn test_rng_seeded() { - let seed: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7]; - let mut ra: ChaChaRng = SeedableRng::from_seed(seed); - let mut rb: ChaChaRng = SeedableRng::from_seed(seed); - assert!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - - #[test] - fn test_rng_reseed() { - let s = ::test::rng().gen_iter::<u32>().take(8).collect::<Vec<u32>>(); - let mut r: ChaChaRng = SeedableRng::from_seed(&*s); - let string1: String = r.gen_ascii_chars().take(100).collect(); - - r.reseed(&s); - - let string2: String = r.gen_ascii_chars().take(100).collect(); - assert_eq!(string1, string2); - } - - #[test] - #[rustfmt_skip] - fn test_rng_true_values() { - // Test vectors 1 and 2 from - // http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04 - let seed: &[_] = &[0; 8]; - let mut ra: ChaChaRng = SeedableRng::from_seed(seed); - - let v = (0..16).map(|_| ra.next_u32()).collect::<Vec<_>>(); - assert_eq!(v, - vec![0xade0b876, 0x903df1a0, 0xe56a5d40, 0x28bd8653, - 0xb819d2bd, 0x1aed8da0, 0xccef36a8, 0xc70d778b, - 0x7c5941da, 0x8d485751, 0x3fe02477, 0x374ad8b8, - 0xf4b8436a, 0x1ca11815, 0x69b687c3, 0x8665eeb2]); - - let v = (0..16).map(|_| ra.next_u32()).collect::<Vec<_>>(); - assert_eq!(v, - vec![0xbee7079f, 0x7a385155, 0x7c97ba98, 0x0d082d73, - 0xa0290fcb, 0x6965e348, 0x3e53c612, 0xed7aee32, - 0x7621b729, 0x434ee69c, 0xb03371d5, 0xd539d874, - 0x281fed31, 0x45fb0a51, 0x1f0ae1ac, 0x6f4d794b]); - - - let seed: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7]; - let mut ra: ChaChaRng = SeedableRng::from_seed(seed); - - // Store the 17*i-th 32-bit word, - // i.e., the i-th word of the i-th 16-word block - let mut v: Vec<u32> = Vec::new(); - for _ in 0..16 { - v.push(ra.next_u32()); - for _ in 0..16 { - ra.next_u32(); - } - } - - assert_eq!(v, - vec![0xf225c81a, 0x6ab1be57, 0x04d42951, 0x70858036, - 0x49884684, 0x64efec72, 0x4be2d186, 0x3615b384, - 0x11cfa18e, 0xd3c50049, 0x75c775f6, 0x434c6530, - 0x2c5bad8f, 0x898881dc, 0x5f1c86d9, 0xc1f8e7f4]); - } - - #[test] - fn test_rng_clone() { - let seed: &[_] = &[0; 8]; - let mut rng: ChaChaRng = SeedableRng::from_seed(seed); - let mut clone = rng.clone(); - for _ in 0..16 { - assert_eq!(rng.next_u64(), clone.next_u64()); - } - } -} diff --git a/src/librand/distributions/exponential.rs b/src/librand/distributions/exponential.rs deleted file mode 100644 index 3337cc2a627..00000000000 --- a/src/librand/distributions/exponential.rs +++ /dev/null @@ -1,155 +0,0 @@ -// 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 exponential distribution. - -use core::fmt; - -#[cfg(not(test))] // only necessary for no_std -use FloatMath; - -use {Rand, Rng}; -use distributions::{IndependentSample, Sample, ziggurat, ziggurat_tables}; - -/// A wrapper around an `f64` to generate Exp(1) random numbers. -/// -/// See `Exp` for the general exponential distribution. Note that this has to -/// be unwrapped before use as an `f64` (using either `*` or `mem::transmute` -/// is safe). -/// -/// Implemented via the ZIGNOR variant[1] of the Ziggurat method. The -/// exact description in the paper was adjusted to use tables for the -/// exponential distribution rather than normal. -/// -/// [1]: Jurgen A. Doornik (2005). [*An Improved Ziggurat Method to -/// Generate Normal Random -/// Samples*](http://www.doornik.com/research/ziggurat.pdf). Nuffield -/// College, Oxford -#[derive(Copy, Clone)] -pub struct Exp1(pub f64); - -// This could be done via `-rng.gen::<f64>().ln()` but that is slower. -impl Rand for Exp1 { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> Exp1 { - #[inline] - fn pdf(x: f64) -> f64 { - (-x).exp() - } - #[inline] - fn zero_case<R: Rng>(rng: &mut R, _u: f64) -> f64 { - ziggurat_tables::ZIG_EXP_R - rng.gen::<f64>().ln() - } - - Exp1(ziggurat(rng, - false, - &ziggurat_tables::ZIG_EXP_X, - &ziggurat_tables::ZIG_EXP_F, - pdf, - zero_case)) - } -} - -impl fmt::Debug for Exp1 { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_tuple("Exp1") - .field(&self.0) - .finish() - } -} - -/// The exponential distribution `Exp(lambda)`. -/// -/// This distribution has density function: `f(x) = lambda * -/// exp(-lambda * x)` for `x > 0`. -#[derive(Copy, Clone)] -pub struct Exp { - /// `lambda` stored as `1/lambda`, since this is what we scale by. - lambda_inverse: f64, -} - -impl Exp { - /// Construct a new `Exp` with the given shape parameter - /// `lambda`. Panics if `lambda <= 0`. - pub fn new(lambda: f64) -> Exp { - assert!(lambda > 0.0, "Exp::new called with `lambda` <= 0"); - Exp { lambda_inverse: 1.0 / lambda } - } -} - -impl Sample<f64> for Exp { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for Exp { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - let Exp1(n) = rng.gen::<Exp1>(); - n * self.lambda_inverse - } -} - -impl fmt::Debug for Exp { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Exp") - .field("lambda_inverse", &self.lambda_inverse) - .finish() - } -} - -#[cfg(test)] -mod tests { - use distributions::{IndependentSample, Sample}; - use super::Exp; - - #[test] - fn test_exp() { - let mut exp = Exp::new(10.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - assert!(exp.sample(&mut rng) >= 0.0); - assert!(exp.ind_sample(&mut rng) >= 0.0); - } - } - #[test] - #[should_panic] - fn test_exp_invalid_lambda_zero() { - Exp::new(0.0); - } - #[test] - #[should_panic] - fn test_exp_invalid_lambda_neg() { - Exp::new(-10.0); - } -} - -#[cfg(test)] -mod bench { - extern crate test; - - use self::test::Bencher; - use std::mem::size_of; - use super::Exp; - use distributions::Sample; - - #[bench] - fn rand_exp(b: &mut Bencher) { - let mut rng = ::test::weak_rng(); - let mut exp = Exp::new(2.71828 * 3.14159); - - b.iter(|| { - for _ in 0..::RAND_BENCH_N { - exp.sample(&mut rng); - } - }); - b.bytes = size_of::<f64>() as u64 * ::RAND_BENCH_N; - } -} diff --git a/src/librand/distributions/gamma.rs b/src/librand/distributions/gamma.rs deleted file mode 100644 index e796197ab5b..00000000000 --- a/src/librand/distributions/gamma.rs +++ /dev/null @@ -1,439 +0,0 @@ -// 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 Gamma and derived distributions. - -use core::fmt; - -use self::GammaRepr::*; -use self::ChiSquaredRepr::*; - -#[cfg(not(test))] // only necessary for no_std -use FloatMath; - -use {Open01, Rng}; -use super::normal::StandardNormal; -use super::{Exp, IndependentSample, Sample}; - -/// The Gamma distribution `Gamma(shape, scale)` distribution. -/// -/// The density function of this distribution is -/// -/// ```text -/// f(x) = x^(k - 1) * exp(-x / θ) / (Γ(k) * θ^k) -/// ``` -/// -/// where `Γ` is the Gamma function, `k` is the shape and `θ` is the -/// scale and both `k` and `θ` are strictly positive. -/// -/// The algorithm used is that described by Marsaglia & Tsang 2000[1], -/// falling back to directly sampling from an Exponential for `shape -/// == 1`, and using the boosting technique described in [1] for -/// `shape < 1`. -/// -/// [1]: George Marsaglia and Wai Wan Tsang. 2000. "A Simple Method -/// for Generating Gamma Variables" *ACM Trans. Math. Softw.* 26, 3 -/// (September 2000), -/// 363-372. DOI:[10.1145/358407.358414](http://doi.acm.org/10.1145/358407.358414) -pub struct Gamma { - repr: GammaRepr, -} - -impl fmt::Debug for Gamma { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Gamma") - .field("repr", - &match self.repr { - GammaRepr::Large(_) => "Large", - GammaRepr::One(_) => "Exp", - GammaRepr::Small(_) => "Small" - }) - .finish() - } -} - -enum GammaRepr { - Large(GammaLargeShape), - One(Exp), - Small(GammaSmallShape), -} - -// These two helpers could be made public, but saving the -// match-on-Gamma-enum branch from using them directly (e.g. if one -// knows that the shape is always > 1) doesn't appear to be much -// faster. - -/// Gamma distribution where the shape parameter is less than 1. -/// -/// Note, samples from this require a compulsory floating-point `pow` -/// call, which makes it significantly slower than sampling from a -/// gamma distribution where the shape parameter is greater than or -/// equal to 1. -/// -/// See `Gamma` for sampling from a Gamma distribution with general -/// shape parameters. -struct GammaSmallShape { - inv_shape: f64, - large_shape: GammaLargeShape, -} - -/// Gamma distribution where the shape parameter is larger than 1. -/// -/// See `Gamma` for sampling from a Gamma distribution with general -/// shape parameters. -struct GammaLargeShape { - scale: f64, - c: f64, - d: f64, -} - -impl Gamma { - /// Construct an object representing the `Gamma(shape, scale)` - /// distribution. - /// - /// Panics if `shape <= 0` or `scale <= 0`. - pub fn new(shape: f64, scale: f64) -> Gamma { - assert!(shape > 0.0, "Gamma::new called with shape <= 0"); - assert!(scale > 0.0, "Gamma::new called with scale <= 0"); - - let repr = if shape == 1.0 { - One(Exp::new(1.0 / scale)) - } else if 0.0 <= shape && shape < 1.0 { - Small(GammaSmallShape::new_raw(shape, scale)) - } else { - Large(GammaLargeShape::new_raw(shape, scale)) - }; - Gamma { repr } - } -} - -impl GammaSmallShape { - fn new_raw(shape: f64, scale: f64) -> GammaSmallShape { - GammaSmallShape { - inv_shape: 1. / shape, - large_shape: GammaLargeShape::new_raw(shape + 1.0, scale), - } - } -} - -impl GammaLargeShape { - fn new_raw(shape: f64, scale: f64) -> GammaLargeShape { - let d = shape - 1. / 3.; - GammaLargeShape { - scale, - c: 1. / (9. * d).sqrt(), - d, - } - } -} - -impl Sample<f64> for Gamma { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} -impl Sample<f64> for GammaSmallShape { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} -impl Sample<f64> for GammaLargeShape { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for Gamma { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - match self.repr { - Small(ref g) => g.ind_sample(rng), - One(ref g) => g.ind_sample(rng), - Large(ref g) => g.ind_sample(rng), - } - } -} -impl IndependentSample<f64> for GammaSmallShape { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - let Open01(u) = rng.gen::<Open01<f64>>(); - - self.large_shape.ind_sample(rng) * u.powf(self.inv_shape) - } -} -impl IndependentSample<f64> for GammaLargeShape { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - loop { - let StandardNormal(x) = rng.gen::<StandardNormal>(); - let v_cbrt = 1.0 + self.c * x; - if v_cbrt <= 0.0 { - // a^3 <= 0 iff a <= 0 - continue; - } - - let v = v_cbrt * v_cbrt * v_cbrt; - let Open01(u) = rng.gen::<Open01<f64>>(); - - let x_sqr = x * x; - if u < 1.0 - 0.0331 * x_sqr * x_sqr || - u.ln() < 0.5 * x_sqr + self.d * (1.0 - v + v.ln()) { - return self.d * v * self.scale; - } - } - } -} - -/// The chi-squared distribution `χ²(k)`, where `k` is the degrees of -/// freedom. -/// -/// For `k > 0` integral, this distribution is the sum of the squares -/// of `k` independent standard normal random variables. For other -/// `k`, this uses the equivalent characterization `χ²(k) = Gamma(k/2, -/// 2)`. -pub struct ChiSquared { - repr: ChiSquaredRepr, -} - -impl fmt::Debug for ChiSquared { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("ChiSquared") - .field("repr", - &match self.repr { - ChiSquaredRepr::DoFExactlyOne => "DoFExactlyOne", - ChiSquaredRepr::DoFAnythingElse(_) => "DoFAnythingElse", - }) - .finish() - } -} - -enum ChiSquaredRepr { - // k == 1, Gamma(alpha, ..) is particularly slow for alpha < 1, - // e.g. when alpha = 1/2 as it would be for this case, so special- - // casing and using the definition of N(0,1)^2 is faster. - DoFExactlyOne, - DoFAnythingElse(Gamma), -} - -impl ChiSquared { - /// Create a new chi-squared distribution with degrees-of-freedom - /// `k`. Panics if `k < 0`. - pub fn new(k: f64) -> ChiSquared { - let repr = if k == 1.0 { - DoFExactlyOne - } else { - assert!(k > 0.0, "ChiSquared::new called with `k` < 0"); - DoFAnythingElse(Gamma::new(0.5 * k, 2.0)) - }; - ChiSquared { repr: repr } - } -} - -impl Sample<f64> for ChiSquared { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for ChiSquared { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - match self.repr { - DoFExactlyOne => { - // k == 1 => N(0,1)^2 - let StandardNormal(norm) = rng.gen::<StandardNormal>(); - norm * norm - } - DoFAnythingElse(ref g) => g.ind_sample(rng), - } - } -} - -/// The Fisher F distribution `F(m, n)`. -/// -/// This distribution is equivalent to the ratio of two normalized -/// chi-squared distributions, that is, `F(m,n) = (χ²(m)/m) / -/// (χ²(n)/n)`. -pub struct FisherF { - numer: ChiSquared, - denom: ChiSquared, - // denom_dof / numer_dof so that this can just be a straight - // multiplication, rather than a division. - dof_ratio: f64, -} - -impl FisherF { - /// Create a new `FisherF` distribution, with the given - /// parameter. Panics if either `m` or `n` are not positive. - pub fn new(m: f64, n: f64) -> FisherF { - assert!(m > 0.0, "FisherF::new called with `m < 0`"); - assert!(n > 0.0, "FisherF::new called with `n < 0`"); - - FisherF { - numer: ChiSquared::new(m), - denom: ChiSquared::new(n), - dof_ratio: n / m, - } - } -} - -impl Sample<f64> for FisherF { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for FisherF { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - self.numer.ind_sample(rng) / self.denom.ind_sample(rng) * self.dof_ratio - } -} - -impl fmt::Debug for FisherF { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("FisherF") - .field("numer", &self.numer) - .field("denom", &self.denom) - .field("dof_ratio", &self.dof_ratio) - .finish() - } -} - -/// The Student t distribution, `t(nu)`, where `nu` is the degrees of -/// freedom. -pub struct StudentT { - chi: ChiSquared, - dof: f64, -} - -impl StudentT { - /// Create a new Student t distribution with `n` degrees of - /// freedom. Panics if `n <= 0`. - pub fn new(n: f64) -> StudentT { - assert!(n > 0.0, "StudentT::new called with `n <= 0`"); - StudentT { - chi: ChiSquared::new(n), - dof: n, - } - } -} - -impl Sample<f64> for StudentT { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for StudentT { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - let StandardNormal(norm) = rng.gen::<StandardNormal>(); - norm * (self.dof / self.chi.ind_sample(rng)).sqrt() - } -} - -impl fmt::Debug for StudentT { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("StudentT") - .field("chi", &self.chi) - .field("dof", &self.dof) - .finish() - } -} - -#[cfg(test)] -mod tests { - use distributions::{IndependentSample, Sample}; - use super::{ChiSquared, FisherF, StudentT}; - - #[test] - fn test_chi_squared_one() { - let mut chi = ChiSquared::new(1.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - chi.sample(&mut rng); - chi.ind_sample(&mut rng); - } - } - #[test] - fn test_chi_squared_small() { - let mut chi = ChiSquared::new(0.5); - let mut rng = ::test::rng(); - for _ in 0..1000 { - chi.sample(&mut rng); - chi.ind_sample(&mut rng); - } - } - #[test] - fn test_chi_squared_large() { - let mut chi = ChiSquared::new(30.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - chi.sample(&mut rng); - chi.ind_sample(&mut rng); - } - } - #[test] - #[should_panic] - fn test_chi_squared_invalid_dof() { - ChiSquared::new(-1.0); - } - - #[test] - fn test_f() { - let mut f = FisherF::new(2.0, 32.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - f.sample(&mut rng); - f.ind_sample(&mut rng); - } - } - - #[test] - fn test_t() { - let mut t = StudentT::new(11.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - t.sample(&mut rng); - t.ind_sample(&mut rng); - } - } -} - -#[cfg(test)] -mod bench { - extern crate test; - use self::test::Bencher; - use std::mem::size_of; - use distributions::IndependentSample; - use super::Gamma; - - - #[bench] - fn bench_gamma_large_shape(b: &mut Bencher) { - let gamma = Gamma::new(10., 1.0); - let mut rng = ::test::weak_rng(); - - b.iter(|| { - for _ in 0..::RAND_BENCH_N { - gamma.ind_sample(&mut rng); - } - }); - b.bytes = size_of::<f64>() as u64 * ::RAND_BENCH_N; - } - - #[bench] - fn bench_gamma_small_shape(b: &mut Bencher) { - let gamma = Gamma::new(0.1, 1.0); - let mut rng = ::test::weak_rng(); - - b.iter(|| { - for _ in 0..::RAND_BENCH_N { - gamma.ind_sample(&mut rng); - } - }); - b.bytes = size_of::<f64>() as u64 * ::RAND_BENCH_N; - } -} diff --git a/src/librand/distributions/mod.rs b/src/librand/distributions/mod.rs deleted file mode 100644 index 47967a719d3..00000000000 --- a/src/librand/distributions/mod.rs +++ /dev/null @@ -1,397 +0,0 @@ -// 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. - -//! Sampling from random distributions. -//! -//! This is a generalization of `Rand` to allow parameters to control the -//! exact properties of the generated values, e.g. the mean and standard -//! deviation of a normal distribution. The `Sample` trait is the most -//! general, and allows for generating values that change some state -//! internally. The `IndependentSample` trait is for generating values -//! that do not need to record state. - -use core::fmt; - -#[cfg(not(test))] // only necessary for no_std -use core::num::Float; - -use core::marker::PhantomData; - -use {Rand, Rng}; - -pub use self::range::Range; -pub use self::gamma::{ChiSquared, FisherF, Gamma, StudentT}; -pub use self::normal::{LogNormal, Normal}; -pub use self::exponential::Exp; - -pub mod range; -pub mod gamma; -pub mod normal; -pub mod exponential; - -/// Types that can be used to create a random instance of `Support`. -pub trait Sample<Support> { - /// Generate a random value of `Support`, using `rng` as the - /// source of randomness. - fn sample<R: Rng>(&mut self, rng: &mut R) -> Support; -} - -/// `Sample`s that do not require keeping track of state. -/// -/// Since no state is recorded, each sample is (statistically) -/// independent of all others, assuming the `Rng` used has this -/// property. -// FIXME maybe having this separate is overkill (the only reason is to -// take &self rather than &mut self)? or maybe this should be the -// trait called `Sample` and the other should be `DependentSample`. -pub trait IndependentSample<Support>: Sample<Support> { - /// Generate a random value. - fn ind_sample<R: Rng>(&self, _: &mut R) -> Support; -} - -/// A wrapper for generating types that implement `Rand` via the -/// `Sample` & `IndependentSample` traits. -pub struct RandSample<Sup> { - _marker: PhantomData<Sup>, -} - -impl<Sup> RandSample<Sup> { - pub fn new() -> RandSample<Sup> { - RandSample { _marker: PhantomData } - } -} - -impl<Sup: Rand> Sample<Sup> for RandSample<Sup> { - fn sample<R: Rng>(&mut self, rng: &mut R) -> Sup { - self.ind_sample(rng) - } -} - -impl<Sup: Rand> IndependentSample<Sup> for RandSample<Sup> { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> Sup { - rng.gen() - } -} - -impl<Sup> fmt::Debug for RandSample<Sup> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.pad("RandSample { .. }") - } -} - -/// A value with a particular weight for use with `WeightedChoice`. -pub struct Weighted<T> { - /// The numerical weight of this item - pub weight: usize, - /// The actual item which is being weighted - pub item: T, -} - -impl<T: fmt::Debug> fmt::Debug for Weighted<T> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Weighted") - .field("weight", &self.weight) - .field("item", &self.item) - .finish() - } -} - -/// A distribution that selects from a finite collection of weighted items. -/// -/// Each item has an associated weight that influences how likely it -/// is to be chosen: higher weight is more likely. -/// -/// The `Clone` restriction is a limitation of the `Sample` and -/// `IndependentSample` traits. Note that `&T` is (cheaply) `Clone` for -/// all `T`, as is `usize`, so one can store references or indices into -/// another vector. -pub struct WeightedChoice<'a, T: 'a> { - items: &'a mut [Weighted<T>], - weight_range: Range<usize>, -} - -impl<'a, T: Clone> WeightedChoice<'a, T> { - /// Create a new `WeightedChoice`. - /// - /// Panics if: - /// - `v` is empty - /// - the total weight is 0 - /// - the total weight is larger than a `usize` can contain. - pub fn new(items: &'a mut [Weighted<T>]) -> WeightedChoice<'a, T> { - // strictly speaking, this is subsumed by the total weight == 0 case - assert!(!items.is_empty(), - "WeightedChoice::new called with no items"); - - let mut running_total = 0_usize; - - // we convert the list from individual weights to cumulative - // weights so we can binary search. This *could* drop elements - // with weight == 0 as an optimisation. - for item in &mut *items { - running_total = match running_total.checked_add(item.weight) { - Some(n) => n, - None => { - panic!("WeightedChoice::new called with a total weight larger than a usize \ - can contain") - } - }; - - item.weight = running_total; - } - assert!(running_total != 0, - "WeightedChoice::new called with a total weight of 0"); - - WeightedChoice { - items, - // we're likely to be generating numbers in this range - // relatively often, so might as well cache it - weight_range: Range::new(0, running_total), - } - } -} - -impl<'a, T: Clone> Sample<T> for WeightedChoice<'a, T> { - fn sample<R: Rng>(&mut self, rng: &mut R) -> T { - self.ind_sample(rng) - } -} - -impl<'a, T: Clone> IndependentSample<T> for WeightedChoice<'a, T> { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> T { - // we want to find the first element that has cumulative - // weight > sample_weight, which we do by binary since the - // cumulative weights of self.items are sorted. - - // choose a weight in [0, total_weight) - let sample_weight = self.weight_range.ind_sample(rng); - - // short circuit when it's the first item - if sample_weight < self.items[0].weight { - return self.items[0].item.clone(); - } - - let mut idx = 0; - let mut modifier = self.items.len(); - - // now we know that every possibility has an element to the - // left, so we can just search for the last element that has - // cumulative weight <= sample_weight, then the next one will - // be "it". (Note that this greatest element will never be the - // last element of the vector, since sample_weight is chosen - // in [0, total_weight) and the cumulative weight of the last - // one is exactly the total weight.) - while modifier > 1 { - let i = idx + modifier / 2; - if self.items[i].weight <= sample_weight { - // we're small, so look to the right, but allow this - // exact element still. - idx = i; - // we need the `/ 2` to round up otherwise we'll drop - // the trailing elements when `modifier` is odd. - modifier += 1; - } else { - // otherwise we're too big, so go left. (i.e. do - // nothing) - } - modifier /= 2; - } - return self.items[idx + 1].item.clone(); - } -} - -impl<'a, T: fmt::Debug> fmt::Debug for WeightedChoice<'a, T> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("WeightedChoice") - .field("items", &self.items) - .field("weight_range", &self.weight_range) - .finish() - } -} - -mod ziggurat_tables; - -/// Sample a random number using the Ziggurat method (specifically the -/// ZIGNOR variant from Doornik 2005). Most of the arguments are -/// directly from the paper: -/// -/// * `rng`: source of randomness -/// * `symmetric`: whether this is a symmetric distribution, or one-sided with P(x < 0) = 0. -/// * `X`: the $x_i$ abscissae. -/// * `F`: precomputed values of the PDF at the $x_i$, (i.e. $f(x_i)$) -/// * `F_DIFF`: precomputed values of $f(x_i) - f(x_{i+1})$ -/// * `pdf`: the probability density function -/// * `zero_case`: manual sampling from the tail when we chose the -/// bottom box (i.e. i == 0) -// the perf improvement (25-50%) is definitely worth the extra code -// size from force-inlining. -#[inline(always)] -fn ziggurat<R: Rng, P, Z>(rng: &mut R, - symmetric: bool, - x_tab: ziggurat_tables::ZigTable, - f_tab: ziggurat_tables::ZigTable, - mut pdf: P, - mut zero_case: Z) - -> f64 - where P: FnMut(f64) -> f64, - Z: FnMut(&mut R, f64) -> f64 -{ - const SCALE: f64 = (1u64 << 53) as f64; - loop { - // reimplement the f64 generation as an optimisation suggested - // by the Doornik paper: we have a lot of precision-space - // (i.e. there are 11 bits of the 64 of a u64 to use after - // creating a f64), so we might as well reuse some to save - // generating a whole extra random number. (Seems to be 15% - // faster.) - // - // This unfortunately misses out on the benefits of direct - // floating point generation if an RNG like dSMFT is - // used. (That is, such RNGs create floats directly, highly - // efficiently and overload next_f32/f64, so by not calling it - // this may be slower than it would be otherwise.) - // FIXME: investigate/optimise for the above. - let bits: u64 = rng.gen(); - let i = (bits & 0xff) as usize; - let f = (bits >> 11) as f64 / SCALE; - - // u is either U(-1, 1) or U(0, 1) depending on if this is a - // symmetric distribution or not. - let u = if symmetric { 2.0 * f - 1.0 } else { f }; - let x = u * x_tab[i]; - - let test_x = if symmetric { x.abs() } else { x }; - - // algebraically equivalent to |u| < x_tab[i+1]/x_tab[i] (or u < x_tab[i+1]/x_tab[i]) - if test_x < x_tab[i + 1] { - return x; - } - if i == 0 { - return zero_case(rng, u); - } - // algebraically equivalent to f1 + DRanU()*(f0 - f1) < 1 - if f_tab[i + 1] + (f_tab[i] - f_tab[i + 1]) * rng.gen::<f64>() < pdf(x) { - return x; - } - } -} - -#[cfg(test)] -mod tests { - use {Rand, Rng}; - use super::{IndependentSample, RandSample, Sample, Weighted, WeightedChoice}; - - #[derive(PartialEq, Debug)] - struct ConstRand(usize); - impl Rand for ConstRand { - fn rand<R: Rng>(_: &mut R) -> ConstRand { - ConstRand(0) - } - } - - // 0, 1, 2, 3, ... - struct CountingRng { - i: u32, - } - impl Rng for CountingRng { - fn next_u32(&mut self) -> u32 { - self.i += 1; - self.i - 1 - } - fn next_u64(&mut self) -> u64 { - self.next_u32() as u64 - } - } - - #[test] - fn test_rand_sample() { - let mut rand_sample = RandSample::<ConstRand>::new(); - - assert_eq!(rand_sample.sample(&mut ::test::rng()), ConstRand(0)); - assert_eq!(rand_sample.ind_sample(&mut ::test::rng()), ConstRand(0)); - } - #[test] - #[rustfmt_skip] - fn test_weighted_choice() { - // this makes assumptions about the internal implementation of - // WeightedChoice, specifically: it doesn't reorder the items, - // it doesn't do weird things to the RNG (so 0 maps to 0, 1 to - // 1, internally; modulo a modulo operation). - - macro_rules! t { - ($items:expr, $expected:expr) => {{ - let mut items = $items; - let wc = WeightedChoice::new(&mut items); - let expected = $expected; - - let mut rng = CountingRng { i: 0 }; - - for &val in &expected { - assert_eq!(wc.ind_sample(&mut rng), val) - } - }} - } - - t!(vec![Weighted { weight: 1, item: 10 }], - [10]); - - // skip some - t!(vec![Weighted { weight: 0, item: 20 }, - Weighted { weight: 2, item: 21 }, - Weighted { weight: 0, item: 22 }, - Weighted { weight: 1, item: 23 }], - [21, 21, 23]); - - // different weights - t!(vec![Weighted { weight: 4, item: 30 }, - Weighted { weight: 3, item: 31 }], - [30, 30, 30, 30, 31, 31, 31]); - - // check that we're binary searching - // correctly with some vectors of odd - // length. - t!(vec![Weighted { weight: 1, item: 40 }, - Weighted { weight: 1, item: 41 }, - Weighted { weight: 1, item: 42 }, - Weighted { weight: 1, item: 43 }, - Weighted { weight: 1, item: 44 }], - [40, 41, 42, 43, 44]); - t!(vec![Weighted { weight: 1, item: 50 }, - Weighted { weight: 1, item: 51 }, - Weighted { weight: 1, item: 52 }, - Weighted { weight: 1, item: 53 }, - Weighted { weight: 1, item: 54 }, - Weighted { weight: 1, item: 55 }, - Weighted { weight: 1, item: 56 }], - [50, 51, 52, 53, 54, 55, 56]); - } - - #[test] - #[should_panic] - fn test_weighted_choice_no_items() { - WeightedChoice::<isize>::new(&mut []); - } - #[test] - #[should_panic] - #[rustfmt_skip] - fn test_weighted_choice_zero_weight() { - WeightedChoice::new(&mut [Weighted { weight: 0, item: 0 }, - Weighted { weight: 0, item: 1 }]); - } - #[test] - #[should_panic] - #[rustfmt_skip] - fn test_weighted_choice_weight_overflows() { - let x = (!0) as usize / 2; // x + x + 2 is the overflow - WeightedChoice::new(&mut [Weighted { weight: x, item: 0 }, - Weighted { weight: 1, item: 1 }, - Weighted { weight: x, item: 2 }, - Weighted { weight: 1, item: 3 }]); - } -} diff --git a/src/librand/distributions/normal.rs b/src/librand/distributions/normal.rs deleted file mode 100644 index e1518dab21c..00000000000 --- a/src/librand/distributions/normal.rs +++ /dev/null @@ -1,234 +0,0 @@ -// 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 normal and derived distributions. - -use core::fmt; - -#[cfg(not(test))] // only necessary for no_std -use FloatMath; - -use {Open01, Rand, Rng}; -use distributions::{IndependentSample, Sample, ziggurat, ziggurat_tables}; - -/// A wrapper around an `f64` to generate N(0, 1) random numbers -/// (a.k.a. a standard normal, or Gaussian). -/// -/// See `Normal` for the general normal distribution. That this has to -/// be unwrapped before use as an `f64` (using either `*` or -/// `mem::transmute` is safe). -/// -/// Implemented via the ZIGNOR variant[1] of the Ziggurat method. -/// -/// [1]: Jurgen A. Doornik (2005). [*An Improved Ziggurat Method to -/// Generate Normal Random -/// Samples*](http://www.doornik.com/research/ziggurat.pdf). Nuffield -/// College, Oxford -#[derive(Copy, Clone)] -pub struct StandardNormal(pub f64); - -impl Rand for StandardNormal { - fn rand<R: Rng>(rng: &mut R) -> StandardNormal { - #[inline] - fn pdf(x: f64) -> f64 { - (-x * x / 2.0).exp() - } - #[inline] - fn zero_case<R: Rng>(rng: &mut R, u: f64) -> f64 { - // compute a random number in the tail by hand - - // strange initial conditions, because the loop is not - // do-while, so the condition should be true on the first - // run, they get overwritten anyway (0 < 1, so these are - // good). - let mut x = 1.0f64; - let mut y = 0.0f64; - - while -2.0 * y < x * x { - let Open01(x_) = rng.gen::<Open01<f64>>(); - let Open01(y_) = rng.gen::<Open01<f64>>(); - - x = x_.ln() / ziggurat_tables::ZIG_NORM_R; - y = y_.ln(); - } - - if u < 0.0 { - x - ziggurat_tables::ZIG_NORM_R - } else { - ziggurat_tables::ZIG_NORM_R - x - } - } - - StandardNormal(ziggurat(rng, - true, // this is symmetric - &ziggurat_tables::ZIG_NORM_X, - &ziggurat_tables::ZIG_NORM_F, - pdf, - zero_case)) - } -} - -impl fmt::Debug for StandardNormal { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_tuple("StandardNormal") - .field(&self.0) - .finish() - } -} - -/// The normal distribution `N(mean, std_dev**2)`. -/// -/// This uses the ZIGNOR variant of the Ziggurat method, see -/// `StandardNormal` for more details. -#[derive(Copy, Clone)] -pub struct Normal { - mean: f64, - std_dev: f64, -} - -impl Normal { - /// Construct a new `Normal` distribution with the given mean and - /// standard deviation. - /// - /// # Panics - /// - /// Panics if `std_dev < 0`. - pub fn new(mean: f64, std_dev: f64) -> Normal { - assert!(std_dev >= 0.0, "Normal::new called with `std_dev` < 0"); - Normal { - mean, - std_dev, - } - } -} - -impl Sample<f64> for Normal { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for Normal { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - let StandardNormal(n) = rng.gen::<StandardNormal>(); - self.mean + self.std_dev * n - } -} - -impl fmt::Debug for Normal { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Normal") - .field("mean", &self.mean) - .field("std_dev", &self.std_dev) - .finish() - } -} - - -/// The log-normal distribution `ln N(mean, std_dev**2)`. -/// -/// If `X` is log-normal distributed, then `ln(X)` is `N(mean, -/// std_dev**2)` distributed. -#[derive(Copy, Clone)] -pub struct LogNormal { - norm: Normal, -} - -impl LogNormal { - /// Construct a new `LogNormal` distribution with the given mean - /// and standard deviation. - /// - /// # Panics - /// - /// Panics if `std_dev < 0`. - pub fn new(mean: f64, std_dev: f64) -> LogNormal { - assert!(std_dev >= 0.0, "LogNormal::new called with `std_dev` < 0"); - LogNormal { norm: Normal::new(mean, std_dev) } - } -} - -impl Sample<f64> for LogNormal { - fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 { - self.ind_sample(rng) - } -} - -impl IndependentSample<f64> for LogNormal { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 { - self.norm.ind_sample(rng).exp() - } -} - -impl fmt::Debug for LogNormal { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("LogNormal") - .field("norm", &self.norm) - .finish() - } -} - -#[cfg(test)] -mod tests { - use distributions::{IndependentSample, Sample}; - use super::{LogNormal, Normal}; - - #[test] - fn test_normal() { - let mut norm = Normal::new(10.0, 10.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - norm.sample(&mut rng); - norm.ind_sample(&mut rng); - } - } - #[test] - #[should_panic] - fn test_normal_invalid_sd() { - Normal::new(10.0, -1.0); - } - - - #[test] - fn test_log_normal() { - let mut lnorm = LogNormal::new(10.0, 10.0); - let mut rng = ::test::rng(); - for _ in 0..1000 { - lnorm.sample(&mut rng); - lnorm.ind_sample(&mut rng); - } - } - #[test] - #[should_panic] - fn test_log_normal_invalid_sd() { - LogNormal::new(10.0, -1.0); - } -} - -#[cfg(test)] -mod bench { - extern crate test; - use self::test::Bencher; - use std::mem::size_of; - use distributions::Sample; - use super::Normal; - - #[bench] - fn rand_normal(b: &mut Bencher) { - let mut rng = ::test::weak_rng(); - let mut normal = Normal::new(-2.71828, 3.14159); - - b.iter(|| { - for _ in 0..::RAND_BENCH_N { - normal.sample(&mut rng); - } - }); - b.bytes = size_of::<f64>() as u64 * ::RAND_BENCH_N; - } -} diff --git a/src/librand/distributions/range.rs b/src/librand/distributions/range.rs deleted file mode 100644 index f2f8132e5b4..00000000000 --- a/src/librand/distributions/range.rs +++ /dev/null @@ -1,227 +0,0 @@ -// 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. - -//! Generating numbers between two others. - -// this is surprisingly complicated to be both generic & correct - -use core::fmt; -use core::marker::Sized; -use Rng; -use distributions::{IndependentSample, Sample}; - -/// Sample values uniformly between two bounds. -/// -/// This gives a uniform distribution (assuming the RNG used to sample -/// it is itself uniform & the `SampleRange` implementation for the -/// given type is correct), even for edge cases like `low = 0`, -/// `high = 170`, for which a naive modulo operation would return -/// numbers less than 85 with double the probability to those greater -/// than 85. -/// -/// Types should attempt to sample in `[low, high)`, i.e., not -/// including `high`, but this may be very difficult. All the -/// primitive integer types satisfy this property, and the float types -/// normally satisfy it, but rounding may mean `high` can occur. -pub struct Range<X> { - low: X, - range: X, - accept_zone: X, -} - -impl<X: SampleRange + PartialOrd> Range<X> { - /// Create a new `Range` instance that samples uniformly from - /// `[low, high)`. Panics if `low >= high`. - pub fn new(low: X, high: X) -> Range<X> { - assert!(low < high, "Range::new called with `low >= high`"); - SampleRange::construct_range(low, high) - } -} - -impl<Sup: SampleRange> Sample<Sup> for Range<Sup> { - #[inline] - fn sample<R: Rng>(&mut self, rng: &mut R) -> Sup { - self.ind_sample(rng) - } -} - -impl<Sup: SampleRange> IndependentSample<Sup> for Range<Sup> { - fn ind_sample<R: Rng>(&self, rng: &mut R) -> Sup { - SampleRange::sample_range(self, rng) - } -} - -impl<X: fmt::Debug> fmt::Debug for Range<X> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Range") - .field("low", &self.low) - .field("range", &self.range) - .field("accept_zone", &self.accept_zone) - .finish() - } -} - -/// The helper trait for types that have a sensible way to sample -/// uniformly between two values. This should not be used directly, -/// and is only to facilitate `Range`. -#[doc(hidden)] -pub trait SampleRange: Sized { - /// Construct the `Range` object that `sample_range` - /// requires. This should not ever be called directly, only via - /// `Range::new`, which will check that `low < high`, so this - /// function doesn't have to repeat the check. - fn construct_range(low: Self, high: Self) -> Range<Self>; - - /// Sample a value from the given `Range` with the given `Rng` as - /// a source of randomness. - fn sample_range<R: Rng>(r: &Range<Self>, rng: &mut R) -> Self; -} - -macro_rules! integer_impl { - ($ty:ident, $unsigned:ident) => { - impl SampleRange for $ty { - // we play free and fast with unsigned vs signed here - // (when $ty is signed), but that's fine, since the - // contract of this macro is for $ty and $unsigned to be - // "bit-equal", so casting between them is a no-op & a - // bijection. - - fn construct_range(low: $ty, high: $ty) -> Range<$ty> { - let range = (high as $unsigned).wrapping_sub(low as $unsigned); - let unsigned_max: $unsigned = $unsigned::max_value(); - - // this is the largest number that fits into $unsigned - // that `range` divides evenly, so, if we've sampled - // `n` uniformly from this region, then `n % range` is - // uniform in [0, range) - let zone = unsigned_max - unsigned_max % range; - - Range { - low, - range: range as $ty, - accept_zone: zone as $ty - } - } - #[inline] - fn sample_range<R: Rng>(r: &Range<$ty>, rng: &mut R) -> $ty { - loop { - // rejection sample - let v = rng.gen::<$unsigned>(); - // until we find something that fits into the - // region which r.range evenly divides (this will - // be uniformly distributed) - if v < r.accept_zone as $unsigned { - // and return it, with some adjustments - return r.low.wrapping_add((v % r.range as $unsigned) as $ty); - } - } - } - } - } -} - -integer_impl! { i8, u8 } -integer_impl! { i16, u16 } -integer_impl! { i32, u32 } -integer_impl! { i64, u64 } -integer_impl! { isize, usize } -integer_impl! { u8, u8 } -integer_impl! { u16, u16 } -integer_impl! { u32, u32 } -integer_impl! { u64, u64 } -integer_impl! { usize, usize } - -macro_rules! float_impl { - ($ty:ty) => { - impl SampleRange for $ty { - fn construct_range(low: $ty, high: $ty) -> Range<$ty> { - Range { - low, - range: high - low, - accept_zone: 0.0 // unused - } - } - fn sample_range<R: Rng>(r: &Range<$ty>, rng: &mut R) -> $ty { - r.low + r.range * rng.gen::<$ty>() - } - } - } -} - -float_impl! { f32 } -float_impl! { f64 } - -#[cfg(test)] -mod tests { - use distributions::{IndependentSample, Sample}; - use super::Range; - - #[should_panic] - #[test] - fn test_range_bad_limits_equal() { - Range::new(10, 10); - } - #[should_panic] - #[test] - fn test_range_bad_limits_flipped() { - Range::new(10, 5); - } - - #[test] - fn test_integers() { - let mut rng = ::test::rng(); - macro_rules! t { - ($($ty:ident),*) => {{ - $( - let v: &[($ty, $ty)] = &[(0, 10), - (10, 127), - ($ty::min_value(), $ty::max_value())]; - for &(low, high) in v { - let mut sampler: Range<$ty> = Range::new(low, high); - for _ in 0..1000 { - let v = sampler.sample(&mut rng); - assert!(low <= v && v < high); - let v = sampler.ind_sample(&mut rng); - assert!(low <= v && v < high); - } - } - )* - }} - } - t!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize) - } - - #[test] - fn test_floats() { - let mut rng = ::test::rng(); - macro_rules! t { - ($($ty:ty),*) => {{ - $( - let v: &[($ty, $ty)] = &[(0.0, 100.0), - (-1e35, -1e25), - (1e-35, 1e-25), - (-1e35, 1e35)]; - for &(low, high) in v { - let mut sampler: Range<$ty> = Range::new(low, high); - for _ in 0..1000 { - let v = sampler.sample(&mut rng); - assert!(low <= v && v < high); - let v = sampler.ind_sample(&mut rng); - assert!(low <= v && v < high); - } - } - )* - }} - } - - t!(f32, f64) - } - -} diff --git a/src/librand/distributions/ziggurat_tables.rs b/src/librand/distributions/ziggurat_tables.rs deleted file mode 100644 index 7dfb0f131a2..00000000000 --- a/src/librand/distributions/ziggurat_tables.rs +++ /dev/null @@ -1,284 +0,0 @@ -// 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. - -// Tables for distributions which are sampled using the ziggurat -// algorithm. Autogenerated by `ziggurat_tables.py`. - -pub type ZigTable = &'static [f64; 257]; -pub const ZIG_NORM_R: f64 = 3.654152885361008796; -#[rustfmt_skip] -pub static ZIG_NORM_X: [f64; 257] = - [3.910757959537090045, 3.654152885361008796, 3.449278298560964462, 3.320244733839166074, - 3.224575052047029100, 3.147889289517149969, 3.083526132001233044, 3.027837791768635434, - 2.978603279880844834, 2.934366867207854224, 2.894121053612348060, 2.857138730872132548, - 2.822877396825325125, 2.790921174000785765, 2.760944005278822555, 2.732685359042827056, - 2.705933656121858100, 2.680514643284522158, 2.656283037575502437, 2.633116393630324570, - 2.610910518487548515, 2.589575986706995181, 2.569035452680536569, 2.549221550323460761, - 2.530075232158516929, 2.511544441625342294, 2.493583041269680667, 2.476149939669143318, - 2.459208374333311298, 2.442725318198956774, 2.426670984935725972, 2.411018413899685520, - 2.395743119780480601, 2.380822795170626005, 2.366237056715818632, 2.351967227377659952, - 2.337996148795031370, 2.324308018869623016, 2.310888250599850036, 2.297723348901329565, - 2.284800802722946056, 2.272108990226823888, 2.259637095172217780, 2.247375032945807760, - 2.235313384928327984, 2.223443340090905718, 2.211756642882544366, 2.200245546609647995, - 2.188902771624720689, 2.177721467738641614, 2.166695180352645966, 2.155817819875063268, - 2.145083634046203613, 2.134487182844320152, 2.124023315687815661, 2.113687150684933957, - 2.103474055713146829, 2.093379631137050279, 2.083399693996551783, 2.073530263516978778, - 2.063767547809956415, 2.054107931648864849, 2.044547965215732788, 2.035084353727808715, - 2.025713947862032960, 2.016433734904371722, 2.007240830558684852, 1.998132471356564244, - 1.989106007615571325, 1.980158896898598364, 1.971288697931769640, 1.962493064942461896, - 1.953769742382734043, 1.945116560006753925, 1.936531428273758904, 1.928012334050718257, - 1.919557336591228847, 1.911164563769282232, 1.902832208548446369, 1.894558525668710081, - 1.886341828534776388, 1.878180486290977669, 1.870072921069236838, 1.862017605397632281, - 1.854013059758148119, 1.846057850283119750, 1.838150586580728607, 1.830289919680666566, - 1.822474540091783224, 1.814703175964167636, 1.806974591348693426, 1.799287584547580199, - 1.791640986550010028, 1.784033659547276329, 1.776464495522344977, 1.768932414909077933, - 1.761436365316706665, 1.753975320315455111, 1.746548278279492994, 1.739154261283669012, - 1.731792314050707216, 1.724461502945775715, 1.717160915015540690, 1.709889657069006086, - 1.702646854797613907, 1.695431651932238548, 1.688243209434858727, 1.681080704722823338, - 1.673943330923760353, 1.666830296159286684, 1.659740822855789499, 1.652674147080648526, - 1.645629517902360339, 1.638606196773111146, 1.631603456932422036, 1.624620582830568427, - 1.617656869570534228, 1.610711622367333673, 1.603784156023583041, 1.596873794420261339, - 1.589979870021648534, 1.583101723393471438, 1.576238702733332886, 1.569390163412534456, - 1.562555467528439657, 1.555733983466554893, 1.548925085471535512, 1.542128153226347553, - 1.535342571438843118, 1.528567729435024614, 1.521803020758293101, 1.515047842773992404, - 1.508301596278571965, 1.501563685112706548, 1.494833515777718391, 1.488110497054654369, - 1.481394039625375747, 1.474683555695025516, 1.467978458615230908, 1.461278162507407830, - 1.454582081885523293, 1.447889631277669675, 1.441200224845798017, 1.434513276002946425, - 1.427828197027290358, 1.421144398672323117, 1.414461289772464658, 1.407778276843371534, - 1.401094763676202559, 1.394410150925071257, 1.387723835686884621, 1.381035211072741964, - 1.374343665770030531, 1.367648583594317957, 1.360949343030101844, 1.354245316759430606, - 1.347535871177359290, 1.340820365893152122, 1.334098153216083604, 1.327368577624624679, - 1.320630975217730096, 1.313884673146868964, 1.307128989027353860, 1.300363230327433728, - 1.293586693733517645, 1.286798664489786415, 1.279998415710333237, 1.273185207661843732, - 1.266358287014688333, 1.259516886060144225, 1.252660221891297887, 1.245787495544997903, - 1.238897891102027415, 1.231990574742445110, 1.225064693752808020, 1.218119375481726552, - 1.211153726239911244, 1.204166830140560140, 1.197157747875585931, 1.190125515422801650, - 1.183069142678760732, 1.175987612011489825, 1.168879876726833800, 1.161744859441574240, - 1.154581450355851802, 1.147388505416733873, 1.140164844363995789, 1.132909248648336975, - 1.125620459211294389, 1.118297174115062909, 1.110938046009249502, 1.103541679420268151, - 1.096106627847603487, 1.088631390649514197, 1.081114409698889389, 1.073554065787871714, - 1.065948674757506653, 1.058296483326006454, 1.050595664586207123, 1.042844313139370538, - 1.035040439828605274, 1.027181966030751292, 1.019266717460529215, 1.011292417434978441, - 1.003256679539591412, 0.995156999629943084, 0.986990747093846266, 0.978755155288937750, - 0.970447311058864615, 0.962064143217605250, 0.953602409875572654, 0.945058684462571130, - 0.936429340280896860, 0.927710533396234771, 0.918898183643734989, 0.909987953490768997, - 0.900975224455174528, 0.891855070726792376, 0.882622229578910122, 0.873271068082494550, - 0.863795545546826915, 0.854189171001560554, 0.844444954902423661, 0.834555354079518752, - 0.824512208745288633, 0.814306670128064347, 0.803929116982664893, 0.793369058833152785, - 0.782615023299588763, 0.771654424216739354, 0.760473406422083165, 0.749056662009581653, - 0.737387211425838629, 0.725446140901303549, 0.713212285182022732, 0.700661841097584448, - 0.687767892786257717, 0.674499822827436479, 0.660822574234205984, 0.646695714884388928, - 0.632072236375024632, 0.616896989996235545, 0.601104617743940417, 0.584616766093722262, - 0.567338257040473026, 0.549151702313026790, 0.529909720646495108, 0.509423329585933393, - 0.487443966121754335, 0.463634336771763245, 0.437518402186662658, 0.408389134588000746, - 0.375121332850465727, 0.335737519180459465, 0.286174591747260509, 0.215241895913273806, - 0.000000000000000000]; -#[rustfmt_skip] -pub static ZIG_NORM_F: [f64; 257] = - [0.000477467764586655, 0.001260285930498598, 0.002609072746106363, 0.004037972593371872, - 0.005522403299264754, 0.007050875471392110, 0.008616582769422917, 0.010214971439731100, - 0.011842757857943104, 0.013497450601780807, 0.015177088307982072, 0.016880083152595839, - 0.018605121275783350, 0.020351096230109354, 0.022117062707379922, 0.023902203305873237, - 0.025705804008632656, 0.027527235669693315, 0.029365939758230111, 0.031221417192023690, - 0.033093219458688698, 0.034980941461833073, 0.036884215688691151, 0.038802707404656918, - 0.040736110656078753, 0.042684144916619378, 0.044646552251446536, 0.046623094902089664, - 0.048613553216035145, 0.050617723861121788, 0.052635418276973649, 0.054666461325077916, - 0.056710690106399467, 0.058767952921137984, 0.060838108349751806, 0.062921024437977854, - 0.065016577971470438, 0.067124653828023989, 0.069245144397250269, 0.071377949059141965, - 0.073522973714240991, 0.075680130359194964, 0.077849336702372207, 0.080030515814947509, - 0.082223595813495684, 0.084428509570654661, 0.086645194450867782, 0.088873592068594229, - 0.091113648066700734, 0.093365311913026619, 0.095628536713353335, 0.097903279039215627, - 0.100189498769172020, 0.102487158942306270, 0.104796225622867056, 0.107116667775072880, - 0.109448457147210021, 0.111791568164245583, 0.114145977828255210, 0.116511665626037014, - 0.118888613443345698, 0.121276805485235437, 0.123676228202051403, 0.126086870220650349, - 0.128508722280473636, 0.130941777174128166, 0.133386029692162844, 0.135841476571757352, - 0.138308116449064322, 0.140785949814968309, 0.143274978974047118, 0.145775208006537926, - 0.148286642733128721, 0.150809290682410169, 0.153343161060837674, 0.155888264725064563, - 0.158444614156520225, 0.161012223438117663, 0.163591108232982951, 0.166181285765110071, - 0.168782774801850333, 0.171395595638155623, 0.174019770082499359, 0.176655321444406654, - 0.179302274523530397, 0.181960655600216487, 0.184630492427504539, 0.187311814224516926, - 0.190004651671193070, 0.192709036904328807, 0.195425003514885592, 0.198152586546538112, - 0.200891822495431333, 0.203642749311121501, 0.206405406398679298, 0.209179834621935651, - 0.211966076307852941, 0.214764175252008499, 0.217574176725178370, 0.220396127481011589, - 0.223230075764789593, 0.226076071323264877, 0.228934165415577484, 0.231804410825248525, - 0.234686861873252689, 0.237581574432173676, 0.240488605941449107, 0.243408015423711988, - 0.246339863502238771, 0.249284212419516704, 0.252241126056943765, 0.255210669955677150, - 0.258192911338648023, 0.261187919133763713, 0.264195763998317568, 0.267216518344631837, - 0.270250256366959984, 0.273297054069675804, 0.276356989296781264, 0.279430141762765316, - 0.282516593084849388, 0.285616426816658109, 0.288729728483353931, 0.291856585618280984, - 0.294997087801162572, 0.298151326697901342, 0.301319396102034120, 0.304501391977896274, - 0.307697412505553769, 0.310907558127563710, 0.314131931597630143, 0.317370638031222396, - 0.320623784958230129, 0.323891482377732021, 0.327173842814958593, 0.330470981380537099, - 0.333783015832108509, 0.337110066638412809, 0.340452257045945450, 0.343809713148291340, - 0.347182563958251478, 0.350570941482881204, 0.353974980801569250, 0.357394820147290515, - 0.360830600991175754, 0.364282468130549597, 0.367750569780596226, 0.371235057669821344, - 0.374736087139491414, 0.378253817247238111, 0.381788410875031348, 0.385340034841733958, - 0.388908860020464597, 0.392495061461010764, 0.396098818517547080, 0.399720314981931668, - 0.403359739222868885, 0.407017284331247953, 0.410693148271983222, 0.414387534042706784, - 0.418100649839684591, 0.421832709231353298, 0.425583931339900579, 0.429354541031341519, - 0.433144769114574058, 0.436954852549929273, 0.440785034667769915, 0.444635565397727750, - 0.448506701509214067, 0.452398706863882505, 0.456311852680773566, 0.460246417814923481, - 0.464202689050278838, 0.468180961407822172, 0.472181538469883255, 0.476204732721683788, - 0.480250865911249714, 0.484320269428911598, 0.488413284707712059, 0.492530263646148658, - 0.496671569054796314, 0.500837575128482149, 0.505028667945828791, 0.509245245998136142, - 0.513487720749743026, 0.517756517232200619, 0.522052074674794864, 0.526374847174186700, - 0.530725304406193921, 0.535103932383019565, 0.539511234259544614, 0.543947731192649941, - 0.548413963257921133, 0.552910490428519918, 0.557437893621486324, 0.561996775817277916, - 0.566587763258951771, 0.571211506738074970, 0.575868682975210544, 0.580559996103683473, - 0.585286179266300333, 0.590047996335791969, 0.594846243770991268, 0.599681752622167719, - 0.604555390700549533, 0.609468064928895381, 0.614420723892076803, 0.619414360609039205, - 0.624450015550274240, 0.629528779928128279, 0.634651799290960050, 0.639820277456438991, - 0.645035480824251883, 0.650298743114294586, 0.655611470583224665, 0.660975147780241357, - 0.666391343912380640, 0.671861719900766374, 0.677388036222513090, 0.682972161648791376, - 0.688616083008527058, 0.694321916130032579, 0.700091918140490099, 0.705928501336797409, - 0.711834248882358467, 0.717811932634901395, 0.723864533472881599, 0.729995264565802437, - 0.736207598131266683, 0.742505296344636245, 0.748892447223726720, 0.755373506511754500, - 0.761953346841546475, 0.768637315803334831, 0.775431304986138326, 0.782341832659861902, - 0.789376143571198563, 0.796542330428254619, 0.803849483176389490, 0.811307874318219935, - 0.818929191609414797, 0.826726833952094231, 0.834716292992930375, 0.842915653118441077, - 0.851346258465123684, 0.860033621203008636, 0.869008688043793165, 0.878309655816146839, - 0.887984660763399880, 0.898095921906304051, 0.908726440060562912, 0.919991505048360247, - 0.932060075968990209, 0.945198953453078028, 0.959879091812415930, 0.977101701282731328, - 1.000000000000000000]; -pub const ZIG_EXP_R: f64 = 7.697117470131050077; -#[rustfmt_skip] -pub static ZIG_EXP_X: [f64; 257] = - [8.697117470131052741, 7.697117470131050077, 6.941033629377212577, 6.478378493832569696, - 6.144164665772472667, 5.882144315795399869, 5.666410167454033697, 5.482890627526062488, - 5.323090505754398016, 5.181487281301500047, 5.054288489981304089, 4.938777085901250530, - 4.832939741025112035, 4.735242996601741083, 4.644491885420085175, 4.559737061707351380, - 4.480211746528421912, 4.405287693473573185, 4.334443680317273007, 4.267242480277365857, - 4.203313713735184365, 4.142340865664051464, 4.084051310408297830, 4.028208544647936762, - 3.974606066673788796, 3.923062500135489739, 3.873417670399509127, 3.825529418522336744, - 3.779270992411667862, 3.734528894039797375, 3.691201090237418825, 3.649195515760853770, - 3.608428813128909507, 3.568825265648337020, 3.530315889129343354, 3.492837654774059608, - 3.456332821132760191, 3.420748357251119920, 3.386035442460300970, 3.352149030900109405, - 3.319047470970748037, 3.286692171599068679, 3.255047308570449882, 3.224079565286264160, - 3.193757903212240290, 3.164053358025972873, 3.134938858084440394, 3.106389062339824481, - 3.078380215254090224, 3.050890016615455114, 3.023897504455676621, 2.997382949516130601, - 2.971327759921089662, 2.945714394895045718, 2.920526286512740821, 2.895747768600141825, - 2.871364012015536371, 2.847360965635188812, 2.823725302450035279, 2.800444370250737780, - 2.777506146439756574, 2.754899196562344610, 2.732612636194700073, 2.710636095867928752, - 2.688959688741803689, 2.667573980773266573, 2.646469963151809157, 2.625639026797788489, - 2.605072938740835564, 2.584763820214140750, 2.564704126316905253, 2.544886627111869970, - 2.525304390037828028, 2.505950763528594027, 2.486819361740209455, 2.467904050297364815, - 2.449198932978249754, 2.430698339264419694, 2.412396812688870629, 2.394289099921457886, - 2.376370140536140596, 2.358635057409337321, 2.341079147703034380, 2.323697874390196372, - 2.306486858283579799, 2.289441870532269441, 2.272558825553154804, 2.255833774367219213, - 2.239262898312909034, 2.222842503111036816, 2.206569013257663858, 2.190438966723220027, - 2.174449009937774679, 2.158595893043885994, 2.142876465399842001, 2.127287671317368289, - 2.111826546019042183, 2.096490211801715020, 2.081275874393225145, 2.066180819490575526, - 2.051202409468584786, 2.036338080248769611, 2.021585338318926173, 2.006941757894518563, - 1.992404978213576650, 1.977972700957360441, 1.963642687789548313, 1.949412758007184943, - 1.935280786297051359, 1.921244700591528076, 1.907302480018387536, 1.893452152939308242, - 1.879691795072211180, 1.866019527692827973, 1.852433515911175554, 1.838931967018879954, - 1.825513128903519799, 1.812175288526390649, 1.798916770460290859, 1.785735935484126014, - 1.772631179231305643, 1.759600930889074766, 1.746643651946074405, 1.733757834985571566, - 1.720942002521935299, 1.708194705878057773, 1.695514524101537912, 1.682900062917553896, - 1.670349953716452118, 1.657862852574172763, 1.645437439303723659, 1.633072416535991334, - 1.620766508828257901, 1.608518461798858379, 1.596327041286483395, 1.584191032532688892, - 1.572109239386229707, 1.560080483527888084, 1.548103603714513499, 1.536177455041032092, - 1.524300908219226258, 1.512472848872117082, 1.500692176842816750, 1.488957805516746058, - 1.477268661156133867, 1.465623682245745352, 1.454021818848793446, 1.442462031972012504, - 1.430943292938879674, 1.419464582769983219, 1.408024891569535697, 1.396623217917042137, - 1.385258568263121992, 1.373929956328490576, 1.362636402505086775, 1.351376933258335189, - 1.340150580529504643, 1.328956381137116560, 1.317793376176324749, 1.306660610415174117, - 1.295557131686601027, 1.284481990275012642, 1.273434238296241139, 1.262412929069615330, - 1.251417116480852521, 1.240445854334406572, 1.229498195693849105, 1.218573192208790124, - 1.207669893426761121, 1.196787346088403092, 1.185924593404202199, 1.175080674310911677, - 1.164254622705678921, 1.153445466655774743, 1.142652227581672841, 1.131873919411078511, - 1.121109547701330200, 1.110358108727411031, 1.099618588532597308, 1.088889961938546813, - 1.078171191511372307, 1.067461226479967662, 1.056759001602551429, 1.046063435977044209, - 1.035373431790528542, 1.024687873002617211, 1.014005623957096480, 1.003325527915696735, - 0.992646405507275897, 0.981967053085062602, 0.971286240983903260, 0.960602711668666509, - 0.949915177764075969, 0.939222319955262286, 0.928522784747210395, 0.917815182070044311, - 0.907098082715690257, 0.896370015589889935, 0.885629464761751528, 0.874874866291025066, - 0.864104604811004484, 0.853317009842373353, 0.842510351810368485, 0.831682837734273206, - 0.820832606554411814, 0.809957724057418282, 0.799056177355487174, 0.788125868869492430, - 0.777164609759129710, 0.766170112735434672, 0.755139984181982249, 0.744071715500508102, - 0.732962673584365398, 0.721810090308756203, 0.710611050909655040, 0.699362481103231959, - 0.688061132773747808, 0.676703568029522584, 0.665286141392677943, 0.653804979847664947, - 0.642255960424536365, 0.630634684933490286, 0.618936451394876075, 0.607156221620300030, - 0.595288584291502887, 0.583327712748769489, 0.571267316532588332, 0.559100585511540626, - 0.546820125163310577, 0.534417881237165604, 0.521885051592135052, 0.509211982443654398, - 0.496388045518671162, 0.483401491653461857, 0.470239275082169006, 0.456886840931420235, - 0.443327866073552401, 0.429543940225410703, 0.415514169600356364, 0.401214678896277765, - 0.386617977941119573, 0.371692145329917234, 0.356399760258393816, 0.340696481064849122, - 0.324529117016909452, 0.307832954674932158, 0.290527955491230394, 0.272513185478464703, - 0.253658363385912022, 0.233790483059674731, 0.212671510630966620, 0.189958689622431842, - 0.165127622564187282, 0.137304980940012589, 0.104838507565818778, 0.063852163815001570, - 0.000000000000000000]; -#[rustfmt_skip] -pub static ZIG_EXP_F: [f64; 257] = - [0.000167066692307963, 0.000454134353841497, 0.000967269282327174, 0.001536299780301573, - 0.002145967743718907, 0.002788798793574076, 0.003460264777836904, 0.004157295120833797, - 0.004877655983542396, 0.005619642207205489, 0.006381905937319183, 0.007163353183634991, - 0.007963077438017043, 0.008780314985808977, 0.009614413642502212, 0.010464810181029981, - 0.011331013597834600, 0.012212592426255378, 0.013109164931254991, 0.014020391403181943, - 0.014945968011691148, 0.015885621839973156, 0.016839106826039941, 0.017806200410911355, - 0.018786700744696024, 0.019780424338009740, 0.020787204072578114, 0.021806887504283581, - 0.022839335406385240, 0.023884420511558174, 0.024942026419731787, 0.026012046645134221, - 0.027094383780955803, 0.028188948763978646, 0.029295660224637411, 0.030414443910466622, - 0.031545232172893622, 0.032687963508959555, 0.033842582150874358, 0.035009037697397431, - 0.036187284781931443, 0.037377282772959382, 0.038578995503074871, 0.039792391023374139, - 0.041017441380414840, 0.042254122413316254, 0.043502413568888197, 0.044762297732943289, - 0.046033761076175184, 0.047316792913181561, 0.048611385573379504, 0.049917534282706379, - 0.051235237055126281, 0.052564494593071685, 0.053905310196046080, 0.055257689676697030, - 0.056621641283742870, 0.057997175631200659, 0.059384305633420280, 0.060783046445479660, - 0.062193415408541036, 0.063615431999807376, 0.065049117786753805, 0.066494496385339816, - 0.067951593421936643, 0.069420436498728783, 0.070901055162371843, 0.072393480875708752, - 0.073897746992364746, 0.075413888734058410, 0.076941943170480517, 0.078481949201606435, - 0.080033947542319905, 0.081597980709237419, 0.083174093009632397, 0.084762330532368146, - 0.086362741140756927, 0.087975374467270231, 0.089600281910032886, 0.091237516631040197, - 0.092887133556043569, 0.094549189376055873, 0.096223742550432825, 0.097910853311492213, - 0.099610583670637132, 0.101322997425953631, 0.103048160171257702, 0.104786139306570145, - 0.106537004050001632, 0.108300825451033755, 0.110077676405185357, 0.111867631670056283, - 0.113670767882744286, 0.115487163578633506, 0.117316899211555525, 0.119160057175327641, - 0.121016721826674792, 0.122886979509545108, 0.124770918580830933, 0.126668629437510671, - 0.128580204545228199, 0.130505738468330773, 0.132445327901387494, 0.134399071702213602, - 0.136367070926428829, 0.138349428863580176, 0.140346251074862399, 0.142357645432472146, - 0.144383722160634720, 0.146424593878344889, 0.148480375643866735, 0.150551185001039839, - 0.152637142027442801, 0.154738369384468027, 0.156854992369365148, 0.158987138969314129, - 0.161134939917591952, 0.163298528751901734, 0.165478041874935922, 0.167673618617250081, - 0.169885401302527550, 0.172113535315319977, 0.174358169171353411, 0.176619454590494829, - 0.178897546572478278, 0.181192603475496261, 0.183504787097767436, 0.185834262762197083, - 0.188181199404254262, 0.190545769663195363, 0.192928149976771296, 0.195328520679563189, - 0.197747066105098818, 0.200183974691911210, 0.202639439093708962, 0.205113656293837654, - 0.207606827724221982, 0.210119159388988230, 0.212650861992978224, 0.215202151075378628, - 0.217773247148700472, 0.220364375843359439, 0.222975768058120111, 0.225607660116683956, - 0.228260293930716618, 0.230933917169627356, 0.233628783437433291, 0.236345152457059560, - 0.239083290262449094, 0.241843469398877131, 0.244625969131892024, 0.247431075665327543, - 0.250259082368862240, 0.253110290015629402, 0.255985007030415324, 0.258883549749016173, - 0.261806242689362922, 0.264753418835062149, 0.267725419932044739, 0.270722596799059967, - 0.273745309652802915, 0.276793928448517301, 0.279868833236972869, 0.282970414538780746, - 0.286099073737076826, 0.289255223489677693, 0.292439288161892630, 0.295651704281261252, - 0.298892921015581847, 0.302163400675693528, 0.305463619244590256, 0.308794066934560185, - 0.312155248774179606, 0.315547685227128949, 0.318971912844957239, 0.322428484956089223, - 0.325917972393556354, 0.329440964264136438, 0.332998068761809096, 0.336589914028677717, - 0.340217149066780189, 0.343880444704502575, 0.347580494621637148, 0.351318016437483449, - 0.355093752866787626, 0.358908472948750001, 0.362762973354817997, 0.366658079781514379, - 0.370594648435146223, 0.374573567615902381, 0.378595759409581067, 0.382662181496010056, - 0.386773829084137932, 0.390931736984797384, 0.395136981833290435, 0.399390684475231350, - 0.403694012530530555, 0.408048183152032673, 0.412454465997161457, 0.416914186433003209, - 0.421428728997616908, 0.425999541143034677, 0.430628137288459167, 0.435316103215636907, - 0.440065100842354173, 0.444876873414548846, 0.449753251162755330, 0.454696157474615836, - 0.459707615642138023, 0.464789756250426511, 0.469944825283960310, 0.475175193037377708, - 0.480483363930454543, 0.485871987341885248, 0.491343869594032867, 0.496901987241549881, - 0.502549501841348056, 0.508289776410643213, 0.514126393814748894, 0.520063177368233931, - 0.526104213983620062, 0.532253880263043655, 0.538516872002862246, 0.544898237672440056, - 0.551403416540641733, 0.558038282262587892, 0.564809192912400615, 0.571723048664826150, - 0.578787358602845359, 0.586010318477268366, 0.593400901691733762, 0.600968966365232560, - 0.608725382079622346, 0.616682180915207878, 0.624852738703666200, 0.633251994214366398, - 0.641896716427266423, 0.650805833414571433, 0.660000841079000145, 0.669506316731925177, - 0.679350572264765806, 0.689566496117078431, 0.700192655082788606, 0.711274760805076456, - 0.722867659593572465, 0.735038092431424039, 0.747868621985195658, 0.761463388849896838, - 0.775956852040116218, 0.791527636972496285, 0.808421651523009044, 0.826993296643051101, - 0.847785500623990496, 0.871704332381204705, 0.900469929925747703, 0.938143680862176477, - 1.000000000000000000]; diff --git a/src/librand/isaac.rs b/src/librand/isaac.rs deleted file mode 100644 index 17ecf79daee..00000000000 --- a/src/librand/isaac.rs +++ /dev/null @@ -1,746 +0,0 @@ -// 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. - -#![allow(non_camel_case_types)] - -use core::fmt; -use core::slice; -use core::iter::repeat; -use core::num::Wrapping as w; - -use {Rand, Rng, SeedableRng}; - -type w32 = w<u32>; -type w64 = w<u64>; - -const RAND_SIZE_LEN: usize = 8; -const RAND_SIZE: u32 = 1 << RAND_SIZE_LEN; -const RAND_SIZE_USIZE: usize = 1 << RAND_SIZE_LEN; - -/// A random number generator that uses the ISAAC algorithm[1]. -/// -/// The ISAAC algorithm is generally accepted as suitable for -/// cryptographic purposes, but this implementation has not be -/// verified as such. Prefer a generator like `OsRng` that defers to -/// the operating system for cases that need high security. -/// -/// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number -/// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html) -#[derive(Copy)] -pub struct IsaacRng { - cnt: u32, - rsl: [w32; RAND_SIZE_USIZE], - mem: [w32; RAND_SIZE_USIZE], - a: w32, - b: w32, - c: w32, -} - -impl fmt::Debug for IsaacRng { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("IsaacRng") - .field("cnt", &self.cnt) - .field("rsl", &self.rsl.iter()) - .field("mem", &self.mem.iter()) - .field("a", &self.a) - .field("b", &self.b) - .field("c", &self.c) - .finish() - } -} - -static EMPTY: IsaacRng = IsaacRng { - cnt: 0, - rsl: [w(0); RAND_SIZE_USIZE], - mem: [w(0); RAND_SIZE_USIZE], - a: w(0), - b: w(0), - c: w(0), -}; - -impl IsaacRng { - /// Create an ISAAC random number generator using the default - /// fixed seed. - pub fn new_unseeded() -> IsaacRng { - let mut rng = EMPTY; - rng.init(false); - rng - } - - /// Initializes `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 = w(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 = a ^ (b << 11); - d = d + a; - b = b + c; - - b = b ^ (c >> 2); - e = e + b; - c = c + d; - - c = c ^ (d << 8); - f = f + c; - d = d + e; - - d = d ^ (e >> 16); - g = g + d; - e = e + f; - - e = e ^ (f << 10); - h = h + e; - f = f + g; - - f = f ^ (g >> 4); - a = a + f; - g = g + h; - - g = g ^ (h << 8); - b = b + g; - h = h + a; - - h = h ^ (a >> 9); - c = c + h; - a = a + b; - }} - } - - for _ in 0..4 { - mix!(); - } - - if use_rsl { - macro_rules! memloop { - ($arr:expr) => {{ - for i in (0..RAND_SIZE_USIZE).step_by(8) { - a = a + $arr[i]; - b = b + $arr[i + 1]; - c = c + $arr[i + 2]; - d = d + $arr[i + 3]; - e = e + $arr[i + 4]; - f = f + $arr[i + 5]; - g = g + $arr[i + 6]; - h = 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 (0..RAND_SIZE_USIZE).step_by(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 = self.c + w(1); - // abbreviations - let mut a = self.a; - let mut b = self.b + self.c; - - const MIDPOINT: usize = RAND_SIZE_USIZE / 2; - - macro_rules! ind { - ($x:expr) => (self.mem[($x >> 2).0 as usize & (RAND_SIZE_USIZE - 1)] ) - } - - let r = [(0, MIDPOINT), (MIDPOINT, 0)]; - for &(mr_offset, m2_offset) in &r { - - macro_rules! rngstepp { - ($j:expr, $shift:expr) => {{ - let base = $j; - let mix = a << $shift; - - 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; - }} - } - - macro_rules! rngstepn { - ($j:expr, $shift:expr) => {{ - let base = $j; - let mix = a >> $shift; - - 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; - }} - } - - for i in (0..MIDPOINT).step_by(4) { - rngstepp!(i + 0, 13); - rngstepn!(i + 1, 6); - rngstepp!(i + 2, 2); - rngstepn!(i + 3, 16); - } - } - - self.a = a; - self.b = b; - self.cnt = RAND_SIZE; - } -} - -// Cannot be derived because [u32; 256] does not implement Clone -impl Clone for IsaacRng { - fn clone(&self) -> IsaacRng { - *self - } -} - -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.cnt is at most RAND_SIZE, but that is before the - // subtraction above. We want to index without bounds - // checking, but this could lead to incorrect code if someone - // misrefactors, so we check, sometimes. - // - // (Changes here should be reflected in Isaac64Rng.next_u64.) - debug_assert!(self.cnt < RAND_SIZE); - - // (the % is cheaply telling the optimiser that we're always - // in bounds, without unsafe. NB. this is a power of two, so - // it optimises to a bitwise mask). - self.rsl[(self.cnt % RAND_SIZE) as usize].0 - } -} - -impl<'a> SeedableRng<&'a [u32]> for IsaacRng { - fn reseed(&mut self, seed: &'a [u32]) { - // make the seed into [seed[0], seed[1], ..., seed[seed.len() - // - 1], 0, 0, ...], to fill rng.rsl. - let seed_iter = seed.iter().cloned().chain(repeat(0)); - - for (rsl_elem, seed_elem) in self.rsl.iter_mut().zip(seed_iter) { - *rsl_elem = w(seed_elem); - } - self.cnt = 0; - self.a = w(0); - self.b = w(0); - self.c = w(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: &'a [u32]) -> IsaacRng { - let mut rng = EMPTY; - rng.reseed(seed); - rng - } -} - -impl Rand for IsaacRng { - fn rand<R: Rng>(other: &mut R) -> IsaacRng { - let mut ret = EMPTY; - unsafe { - let ptr = ret.rsl.as_mut_ptr() as *mut u8; - - let slice = slice::from_raw_parts_mut(ptr, RAND_SIZE_USIZE * 4); - other.fill_bytes(slice); - } - ret.cnt = 0; - ret.a = w(0); - ret.b = w(0); - ret.c = w(0); - - ret.init(true); - return ret; - } -} - -const RAND_SIZE_64_LEN: usize = 8; -const RAND_SIZE_64: usize = 1 << RAND_SIZE_64_LEN; - -/// A random number generator that uses ISAAC-64[1], the 64-bit -/// variant of the ISAAC algorithm. -/// -/// The ISAAC algorithm is generally accepted as suitable for -/// cryptographic purposes, but this implementation has not be -/// verified as such. Prefer a generator like `OsRng` that defers to -/// the operating system for cases that need high security. -/// -/// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number -/// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html) -#[derive(Copy)] -pub struct Isaac64Rng { - cnt: usize, - rsl: [w64; RAND_SIZE_64], - mem: [w64; RAND_SIZE_64], - a: w64, - b: w64, - c: w64, -} - -impl fmt::Debug for Isaac64Rng { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Isaac64Rng") - .field("cnt", &self.cnt) - .field("rsl", &self.rsl.iter()) - .field("mem", &self.mem.iter()) - .field("a", &self.a) - .field("b", &self.b) - .field("c", &self.c) - .finish() - } -} - -static EMPTY_64: Isaac64Rng = Isaac64Rng { - cnt: 0, - rsl: [w(0); RAND_SIZE_64], - mem: [w(0); RAND_SIZE_64], - a: w(0), - b: w(0), - c: w(0), -}; - -impl Isaac64Rng { - /// 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 - } - - /// Initializes `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 = w(0x9e3779b97f4a7c13); - ) - } - init!(a); - init!(b); - init!(c); - init!(d); - init!(e); - init!(f); - init!(g); - init!(h); - - macro_rules! mix { - () => {{ - a = a - e; - f = f ^ (h >> 9); - h = h + a; - - b = b - f; - g = g ^ (a << 9); - a = a + b; - - c = c - g; - h = h ^ (b >> 23); - b = b + c; - - d = d - h; - a = a ^ (c << 15); - c = c + d; - - e = e - a; - b = b ^ (d >> 14); - d = d + e; - - f = f - b; - c = c ^ (e << 20); - e = e + f; - - g = g - c; - d = d ^ (f >> 17); - f = f + g; - - h = h - d; - e = e ^ (g << 14); - g = g + h; - }} - } - - for _ in 0..4 { - mix!(); - } - - if use_rsl { - macro_rules! memloop { - ($arr:expr) => {{ - for i in (0..RAND_SIZE_64 / 8).map(|i| i * 8) { - a = a + $arr[i]; - b = b + $arr[i + 1]; - c = c + $arr[i + 2]; - d = d + $arr[i + 3]; - e = e + $arr[i + 4]; - f = f + $arr[i + 5]; - g = g + $arr[i + 6]; - h = 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 (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 = self.c + w(1); - // abbreviations - let mut a = self.a; - let mut b = self.b + self.c; - const MIDPOINT: usize = RAND_SIZE_64 / 2; - const MP_VEC: [(usize, usize); 2] = [(0, MIDPOINT), (MIDPOINT, 0)]; - macro_rules! ind { - ($x:expr) => { - *self.mem.get_unchecked((($x >> 3).0 as usize) & (RAND_SIZE_64 - 1)) - } - } - - for &(mr_offset, m2_offset) in &MP_VEC { - for base in (0..MIDPOINT / 4).map(|i| i * 4) { - - macro_rules! rngstepp { - ($j:expr, $shift:expr) => {{ - let base = base + $j; - let mix = a ^ (a << $shift); - let mix = if $j == 0 {!mix} else {mix}; - - unsafe { - let x = *self.mem.get_unchecked(base + mr_offset); - a = mix + *self.mem.get_unchecked(base + m2_offset); - let y = ind!(x) + a + b; - *self.mem.get_unchecked_mut(base + mr_offset) = y; - - b = ind!(y >> RAND_SIZE_64_LEN) + x; - *self.rsl.get_unchecked_mut(base + mr_offset) = b; - } - }} - } - - macro_rules! rngstepn { - ($j:expr, $shift:expr) => {{ - let base = base + $j; - let mix = a ^ (a >> $shift); - let mix = if $j == 0 {!mix} else {mix}; - - unsafe { - let x = *self.mem.get_unchecked(base + mr_offset); - a = mix + *self.mem.get_unchecked(base + m2_offset); - let y = ind!(x) + a + b; - *self.mem.get_unchecked_mut(base + mr_offset) = y; - - b = ind!(y >> RAND_SIZE_64_LEN) + x; - *self.rsl.get_unchecked_mut(base + mr_offset) = b; - } - }} - } - - rngstepp!(0, 21); - rngstepn!(1, 5); - rngstepp!(2, 12); - rngstepn!(3, 33); - } - } - - self.a = a; - self.b = b; - self.cnt = RAND_SIZE_64; - } -} - -// Cannot be derived because [u32; 256] does not implement Clone -impl Clone for Isaac64Rng { - fn clone(&self) -> Isaac64Rng { - *self - } -} - -impl Rng for Isaac64Rng { - // FIXME(https://github.com/rust-lang/rfcs/issues/628) - // 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; - - // See corresponding location in IsaacRng.next_u32 for - // explanation. - debug_assert!(self.cnt < RAND_SIZE_64); - self.rsl[(self.cnt % RAND_SIZE_64) as usize].0 - } -} - -impl<'a> SeedableRng<&'a [u64]> for Isaac64Rng { - fn reseed(&mut self, seed: &'a [u64]) { - // make the seed into [seed[0], seed[1], ..., seed[seed.len() - // - 1], 0, 0, ...], to fill rng.rsl. - let seed_iter = seed.iter().cloned().chain(repeat(0)); - - for (rsl_elem, seed_elem) in self.rsl.iter_mut().zip(seed_iter) { - *rsl_elem = w(seed_elem); - } - self.cnt = 0; - self.a = w(0); - self.b = w(0); - self.c = w(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: &'a [u64]) -> Isaac64Rng { - let mut rng = EMPTY_64; - rng.reseed(seed); - rng - } -} - -impl Rand for Isaac64Rng { - fn rand<R: Rng>(other: &mut R) -> Isaac64Rng { - let mut ret = EMPTY_64; - unsafe { - let ptr = ret.rsl.as_mut_ptr() as *mut u8; - - let slice = slice::from_raw_parts_mut(ptr, RAND_SIZE_64 * 8); - other.fill_bytes(slice); - } - ret.cnt = 0; - ret.a = w(0); - ret.b = w(0); - ret.c = w(0); - - ret.init(true); - return ret; - } -} - - -#[cfg(test)] -mod tests { - use std::prelude::v1::*; - - use {Rng, SeedableRng}; - use super::{Isaac64Rng, IsaacRng}; - - #[test] - fn test_rng_32_rand_seeded() { - let s = ::test::rng().gen_iter::<u32>().take(256).collect::<Vec<u32>>(); - let mut ra: IsaacRng = SeedableRng::from_seed(&s[..]); - let mut rb: IsaacRng = SeedableRng::from_seed(&s[..]); - assert!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - #[test] - fn test_rng_64_rand_seeded() { - let s = ::test::rng().gen_iter::<u64>().take(256).collect::<Vec<u64>>(); - let mut ra: Isaac64Rng = SeedableRng::from_seed(&s[..]); - let mut rb: Isaac64Rng = SeedableRng::from_seed(&s[..]); - assert!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - - #[test] - fn test_rng_32_seeded() { - let seed: &[_] = &[1, 23, 456, 7890, 12345]; - let mut ra: IsaacRng = SeedableRng::from_seed(seed); - let mut rb: IsaacRng = SeedableRng::from_seed(seed); - assert!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - #[test] - fn test_rng_64_seeded() { - let seed: &[_] = &[1, 23, 456, 7890, 12345]; - let mut ra: Isaac64Rng = SeedableRng::from_seed(seed); - let mut rb: Isaac64Rng = SeedableRng::from_seed(seed); - assert!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - - #[test] - fn test_rng_32_reseed() { - let s = ::test::rng().gen_iter::<u32>().take(256).collect::<Vec<u32>>(); - let mut r: IsaacRng = SeedableRng::from_seed(&s[..]); - let string1: String = r.gen_ascii_chars().take(100).collect(); - - r.reseed(&s); - - let string2: String = r.gen_ascii_chars().take(100).collect(); - assert_eq!(string1, string2); - } - #[test] - fn test_rng_64_reseed() { - let s = ::test::rng().gen_iter::<u64>().take(256).collect::<Vec<u64>>(); - let mut r: Isaac64Rng = SeedableRng::from_seed(&s[..]); - let string1: String = r.gen_ascii_chars().take(100).collect(); - - r.reseed(&s); - - let string2: String = r.gen_ascii_chars().take(100).collect(); - assert_eq!(string1, string2); - } - - #[test] - #[rustfmt_skip] - fn test_rng_32_true_values() { - let seed: &[_] = &[1, 23, 456, 7890, 12345]; - let mut ra: IsaacRng = SeedableRng::from_seed(seed); - // Regression test that isaac is actually using the above vector - let v = (0..10).map(|_| ra.next_u32()).collect::<Vec<_>>(); - assert_eq!(v, - vec![2558573138, 873787463, 263499565, 2103644246, 3595684709, - 4203127393, 264982119, 2765226902, 2737944514, 3900253796]); - - let seed: &[_] = &[12345, 67890, 54321, 9876]; - let mut rb: IsaacRng = SeedableRng::from_seed(seed); - // skip forward to the 10000th number - for _ in 0..10000 { - rb.next_u32(); - } - - let v = (0..10).map(|_| rb.next_u32()).collect::<Vec<_>>(); - assert_eq!(v, - vec![3676831399, 3183332890, 2834741178, 3854698763, 2717568474, - 1576568959, 3507990155, 179069555, 141456972, 2478885421]); - } - #[test] - #[rustfmt_skip] - fn test_rng_64_true_values() { - let seed: &[_] = &[1, 23, 456, 7890, 12345]; - let mut ra: Isaac64Rng = SeedableRng::from_seed(seed); - // Regression test that isaac is actually using the above vector - let v = (0..10).map(|_| ra.next_u64()).collect::<Vec<_>>(); - assert_eq!(v, - vec![547121783600835980, 14377643087320773276, 17351601304698403469, - 1238879483818134882, 11952566807690396487, 13970131091560099343, - 4469761996653280935, 15552757044682284409, 6860251611068737823, - 13722198873481261842]); - - let seed: &[_] = &[12345, 67890, 54321, 9876]; - let mut rb: Isaac64Rng = SeedableRng::from_seed(seed); - // skip forward to the 10000th number - for _ in 0..10000 { - rb.next_u64(); - } - - let v = (0..10).map(|_| rb.next_u64()).collect::<Vec<_>>(); - assert_eq!(v, - vec![18143823860592706164, 8491801882678285927, 2699425367717515619, - 17196852593171130876, 2606123525235546165, 15790932315217671084, - 596345674630742204, 9947027391921273664, 11788097613744130851, - 10391409374914919106]); - - } - - #[test] - fn test_rng_clone() { - let seed: &[_] = &[1, 23, 456, 7890, 12345]; - let mut rng: Isaac64Rng = SeedableRng::from_seed(seed); - let mut clone = rng.clone(); - for _ in 0..16 { - assert_eq!(rng.next_u64(), clone.next_u64()); - } - } -} diff --git a/src/librand/lib.rs b/src/librand/lib.rs deleted file mode 100644 index 82344f0ec09..00000000000 --- a/src/librand/lib.rs +++ /dev/null @@ -1,481 +0,0 @@ -// Copyright 2013-2014 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. - -//! Interface to random number generators in Rust. -//! -//! This is an experimental library which lives underneath the standard library -//! in its dependency chain. This library is intended to define the interface -//! for random number generation and also provide utilities around doing so. It -//! is not recommended to use this library directly, but rather the official -//! interface through `std::rand`. - -#![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png", - html_favicon_url = "https://doc.rust-lang.org/favicon.ico", - html_root_url = "https://doc.rust-lang.org/nightly/", - html_playground_url = "https://play.rust-lang.org/", - test(attr(deny(warnings))))] -#![deny(warnings)] -#![deny(missing_debug_implementations)] -#![no_std] -#![unstable(feature = "rand", - reason = "use `rand` from crates.io", - issue = "27703")] -#![feature(core_intrinsics)] -#![feature(staged_api)] -#![feature(iterator_step_by)] -#![feature(custom_attribute)] -#![feature(specialization)] -#![allow(unused_attributes)] - -#![cfg_attr(not(test), feature(core_float))] // only necessary for no_std -#![cfg_attr(test, feature(test, rand))] - -#![allow(deprecated)] - -#[cfg(test)] -#[macro_use] -extern crate std; - -use core::fmt; -use core::f64; -use core::intrinsics; -use core::marker::PhantomData; - -pub use isaac::{Isaac64Rng, IsaacRng}; -pub use chacha::ChaChaRng; - -use distributions::{IndependentSample, Range}; -use distributions::range::SampleRange; - -#[cfg(test)] -const RAND_BENCH_N: u64 = 100; - -pub mod distributions; -pub mod isaac; -pub mod chacha; -pub mod reseeding; -mod rand_impls; - -// Temporary trait to implement a few floating-point routines -// needed by librand; this is necessary because librand doesn't -// depend on libstd. This will go away when librand is integrated -// into libstd. -#[doc(hidden)] -trait FloatMath: Sized { - fn exp(self) -> Self; - fn ln(self) -> Self; - fn sqrt(self) -> Self; - fn powf(self, n: Self) -> Self; -} - -impl FloatMath for f64 { - #[inline] - fn exp(self) -> f64 { - unsafe { intrinsics::expf64(self) } - } - - #[inline] - fn ln(self) -> f64 { - unsafe { intrinsics::logf64(self) } - } - - #[inline] - fn powf(self, n: f64) -> f64 { - unsafe { intrinsics::powf64(self, n) } - } - - #[inline] - fn sqrt(self) -> f64 { - if self < 0.0 { - f64::NAN - } else { - unsafe { intrinsics::sqrtf64(self) } - } - } -} - -/// A type that can be randomly generated using an `Rng`. -#[doc(hidden)] -pub trait Rand: Sized { - /// Generates a random instance of this type using the specified source of - /// randomness. - fn rand<R: Rng>(rng: &mut R) -> Self; -} - -/// A random number generator. -pub trait Rng: Sized { - /// Return the next random u32. - /// - /// This rarely needs to be called directly, prefer `r.gen()` to - /// `r.next_u32()`. - // FIXME(https://github.com/rust-lang/rfcs/issues/628) - // Should be implemented in terms of next_u64 - fn next_u32(&mut self) -> u32; - - /// Return the next random 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. Similarly to `next_u32`, this rarely needs - /// to be called directly, prefer `r.gen()` to `r.next_u64()`. - fn next_u64(&mut self) -> u64 { - ((self.next_u32() as u64) << 32) | (self.next_u32() as u64) - } - - /// Return the next random f32 selected from the half-open - /// interval `[0, 1)`. - /// - /// By default this is implemented in terms of `next_u32`, but a - /// random number generator which can generate numbers satisfying - /// the requirements directly can overload this for performance. - /// It is required that the return value lies in `[0, 1)`. - /// - /// See `Closed01` for the closed interval `[0,1]`, and - /// `Open01` for the open interval `(0,1)`. - fn next_f32(&mut self) -> f32 { - const MANTISSA_BITS: usize = 24; - const IGNORED_BITS: usize = 8; - const SCALE: f32 = (1u64 << MANTISSA_BITS) as f32; - - // using any more than `MANTISSA_BITS` bits will - // cause (e.g.) 0xffff_ffff to correspond to 1 - // exactly, so we need to drop some (8 for f32, 11 - // for f64) to guarantee the open end. - (self.next_u32() >> IGNORED_BITS) as f32 / SCALE - } - - /// Return the next random f64 selected from the half-open - /// interval `[0, 1)`. - /// - /// By default this is implemented in terms of `next_u64`, but a - /// random number generator which can generate numbers satisfying - /// the requirements directly can overload this for performance. - /// It is required that the return value lies in `[0, 1)`. - /// - /// See `Closed01` for the closed interval `[0,1]`, and - /// `Open01` for the open interval `(0,1)`. - 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 - } - - /// Fill `dest` with random data. - /// - /// This has a default implementation in terms of `next_u64` and - /// `next_u32`, but should be overridden 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 behavior should - /// not be relied upon. - /// - /// This method should guarantee that `dest` is entirely filled - /// with new data, and may panic if this is impossible - /// (e.g. reading past the end of a file that is being used as the - /// source of randomness). - fn fill_bytes(&mut self, dest: &mut [u8]) { - // this could, in theory, be done by transmuting dest to a - // [u64], but this is (1) likely to be undefined behaviour for - // LLVM, (2) has to be very careful about alignment concerns, - // (3) adds more `unsafe` that needs to be checked, (4) - // probably doesn't give much performance gain if - // optimisations are on. - let mut count = 0; - let mut num = 0; - for byte in dest { - if count == 0 { - // we could micro-optimise here by generating a u32 if - // we only need a few more bytes to fill the vector - // (i.e. at most 4). - num = self.next_u64(); - count = 8; - } - - *byte = (num & 0xff) as u8; - num >>= 8; - count -= 1; - } - } - - /// Return a random value of a `Rand` type. - #[inline(always)] - fn gen<T: Rand>(&mut self) -> T { - Rand::rand(self) - } - - /// Return an iterator that will yield an infinite number of randomly - /// generated items. - fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> { - Generator { - rng: self, - _marker: PhantomData, - } - } - - /// Generate a random value in the range [`low`, `high`). - /// - /// This is a convenience wrapper around - /// `distributions::Range`. If this function will be called - /// repeatedly with the same arguments, one should use `Range`, as - /// that will amortize the computations that allow for perfect - /// uniformity, as they only happen on initialization. - /// - /// # Panics - /// - /// Panics if `low >= high`. - 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) - } - - /// Return a bool with a 1 in n chance of true - fn gen_weighted_bool(&mut self, n: usize) -> bool { - n <= 1 || self.gen_range(0, n) == 0 - } - - /// Return an iterator of random characters from the set A-Z,a-z,0-9. - fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> { - AsciiGenerator { rng: self } - } - - /// Return a random element from `values`. - /// - /// Return `None` if `values` is empty. - 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())]) - } - } - - /// Shuffle a mutable slice in place. - fn shuffle<T>(&mut self, values: &mut [T]) { - let mut i = values.len(); - while i >= 2 { - // invariant: elements with index >= i have been locked in place. - i -= 1; - // lock element i in place. - values.swap(i, self.gen_range(0, i + 1)); - } - } -} - -/// Iterator which will generate a stream of random items. -/// -/// This iterator is created via the `gen_iter` method on `Rng`. -pub struct Generator<'a, T, R: 'a> { - rng: &'a mut R, - _marker: PhantomData<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()) - } -} - -impl<'a, T, R: fmt::Debug> fmt::Debug for Generator<'a, T, R> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("Generator") - .field("rng", &self.rng) - .finish() - } -} - -/// Iterator which will continuously generate random ascii characters. -/// -/// This iterator is created via the `gen_ascii_chars` method on `Rng`. -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> { - const GEN_ASCII_STR_CHARSET: &'static [u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\ - abcdefghijklmnopqrstuvwxyz\ - 0123456789"; - Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char) - } -} - -impl<'a, R: fmt::Debug> fmt::Debug for AsciiGenerator<'a, R> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("AsciiGenerator") - .field("rng", &self.rng) - .finish() - } -} - -/// 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. - fn reseed(&mut self, _: Seed); - - /// Create a new RNG with the given seed. - fn from_seed(seed: Seed) -> Self; -} - -/// An Xorshift[1] random number -/// generator. -/// -/// The Xorshift algorithm is not suitable for cryptographic purposes -/// but is very fast. If you do not know for sure that it fits your -/// requirements, use a more secure one such as `IsaacRng` or `OsRng`. -/// -/// [1]: Marsaglia, George (July 2003). ["Xorshift -/// RNGs"](http://www.jstatsoft.org/v08/i14/paper). *Journal of -/// Statistical Software*. Vol. 8 (Issue 14). -#[derive(Clone, Debug)] -pub struct XorShiftRng { - x: u32, - y: u32, - z: u32, - w: u32, -} - -impl XorShiftRng { - /// Creates a new XorShiftRng instance which is not seeded. - /// - /// The initial values of this RNG are constants, so all generators created - /// by this function will yield the same stream of random numbers. It is - /// highly recommended that this is created through `SeedableRng` instead of - /// this function - 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 { - /// Reseed an XorShiftRng. This will panic 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 panic 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 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, - y, - z, - w, - } - } -} - -/// A wrapper for generating floating point numbers uniformly in the -/// open interval `(0,1)` (not including either endpoint). -/// -/// Use `Closed01` for the closed interval `[0,1]`, and the default -/// `Rand` implementation for `f32` and `f64` for the half-open -/// `[0,1)`. -pub struct Open01<F>(pub F); - -impl<F: fmt::Debug> fmt::Debug for Open01<F> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_tuple("Open01") - .field(&self.0) - .finish() - } -} - -/// A wrapper for generating floating point numbers uniformly in the -/// closed interval `[0,1]` (including both endpoints). -/// -/// Use `Open01` for the closed interval `(0,1)`, and the default -/// `Rand` implementation of `f32` and `f64` for the half-open -/// `[0,1)`. -pub struct Closed01<F>(pub F); - -impl<F: fmt::Debug> fmt::Debug for Closed01<F> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_tuple("Closed01") - .field(&self.0) - .finish() - } -} - -#[cfg(test)] -mod test { - use std::__rand as rand; - - pub struct MyRng<R> { - inner: R, - } - - impl<R: rand::Rng> ::Rng for MyRng<R> { - fn next_u32(&mut self) -> u32 { - rand::Rng::next_u32(&mut self.inner) - } - } - - pub fn rng() -> MyRng<rand::ThreadRng> { - MyRng { inner: rand::thread_rng() } - } - - pub fn weak_rng() -> MyRng<rand::ThreadRng> { - MyRng { inner: rand::thread_rng() } - } -} diff --git a/src/librand/rand_impls.rs b/src/librand/rand_impls.rs deleted file mode 100644 index b0d824da3ab..00000000000 --- a/src/librand/rand_impls.rs +++ /dev/null @@ -1,208 +0,0 @@ -// Copyright 2013-2014 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 core::char; -use core::mem; - -use {Rand, Rng}; - -impl Rand for isize { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> isize { - if mem::size_of::<isize>() == 4 { - rng.gen::<i32>() as isize - } else { - rng.gen::<i64>() as isize - } - } -} - -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 usize { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> usize { - if mem::size_of::<usize>() == 4 { - rng.gen::<u32>() as usize - } else { - rng.gen::<u64>() as usize - } - } -} - -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() - } -} - -macro_rules! float_impls { - ($mod_name:ident, $ty:ty, $mantissa_bits:expr, $method_name:ident) => { - mod $mod_name { - use {Rand, Rng, Open01, Closed01}; - - const SCALE: $ty = (1u64 << $mantissa_bits) as $ty; - - impl Rand for $ty { - /// Generate a floating point number in the half-open - /// interval `[0,1)`. - /// - /// See `Closed01` for the closed interval `[0,1]`, - /// and `Open01` for the open interval `(0,1)`. - #[inline] - fn rand<R: Rng>(rng: &mut R) -> $ty { - rng.$method_name() - } - } - impl Rand for Open01<$ty> { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> Open01<$ty> { - // add a small amount (specifically 2 bits below - // the precision of f64/f32 at 1.0), so that small - // numbers are larger than 0, but large numbers - // aren't pushed to/above 1. - Open01(rng.$method_name() + 0.25 / SCALE) - } - } - impl Rand for Closed01<$ty> { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> Closed01<$ty> { - // rescale so that 1.0 - epsilon becomes 1.0 - // precisely. - Closed01(rng.$method_name() * SCALE / (SCALE - 1.0)) - } - } - } - } -} -float_impls! { f64_rand_impls, f64, 53, next_f64 } -float_impls! { f32_rand_impls, f32, 24, next_f32 } - -impl Rand for char { - #[inline] - fn rand<R: Rng>(rng: &mut R) -> char { - // a char is 21 bits - const 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. - if let Some(c) = char::from_u32(rng.next_u32() & CHAR_MASK) { - return c; - } - } - } -} - -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} -tuple_impl!{A, B, C, D, E, F, G, H, I, J, K} -tuple_impl!{A, B, C, D, E, F, G, H, I, J, K, L} - -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 } - } -} diff --git a/src/librand/reseeding.rs b/src/librand/reseeding.rs deleted file mode 100644 index 2821b7a8232..00000000000 --- a/src/librand/reseeding.rs +++ /dev/null @@ -1,216 +0,0 @@ -// 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 core::fmt; -use {Rng, SeedableRng}; - -/// How many bytes of entropy the underling RNG is allowed to generate -/// before it is reseeded. -const DEFAULT_GENERATION_THRESHOLD: usize = 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> { - rng: R, - generation_threshold: usize, - bytes_generated: usize, - /// Controls the behavior when reseeding the RNG. - pub 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: usize, reseeder: Rsdr) -> ReseedingRng<R, Rsdr> { - ReseedingRng { - rng, - generation_threshold, - bytes_generated: 0, - 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.rng.fill_bytes(dest) - } -} - -impl<S, R: SeedableRng<S>, Rsdr: Reseeder<R> + Default> - 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, - } - } -} - -impl<R: fmt::Debug, Rsdr: fmt::Debug> fmt::Debug for ReseedingRng<R, Rsdr> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("ReseedingRng") - .field("rng", &self.rng) - .field("generation_threshold", &self.generation_threshold) - .field("bytes_generated", &self.bytes_generated) - .field("reseeder", &self.reseeder) - .finish() - } -} - -/// Something that can be used to reseed an RNG via `ReseedingRng`. -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. -#[derive(Copy, Clone, Debug)] -pub struct ReseedWithDefault; - -impl<R: Rng + Default> Reseeder<R> for ReseedWithDefault { - fn reseed(&mut self, rng: &mut R) { - *rng = Default::default(); - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl Default for ReseedWithDefault { - /// Creates an instance of `ReseedWithDefault`. - fn default() -> ReseedWithDefault { - ReseedWithDefault - } -} - -#[cfg(test)] -mod tests { - use std::prelude::v1::*; - - use super::{ReseedWithDefault, ReseedingRng}; - use {Rng, SeedableRng}; - - 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 { - /// Constructs a `Counter` with initial value zero. - 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 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!(ra.gen_ascii_chars() - .take(100) - .eq(rb.gen_ascii_chars().take(100))); - } - - #[test] - fn test_rng_reseed() { - let mut r: MyRng = SeedableRng::from_seed((ReseedWithDefault, 3)); - let string1: String = r.gen_ascii_chars().take(100).collect(); - - r.reseed((ReseedWithDefault, 3)); - - let string2: String = r.gen_ascii_chars().take(100).collect(); - assert_eq!(string1, string2); - } - - const FILL_BYTES_V_LEN: usize = 13579; - #[test] - fn test_rng_fill_bytes() { - let mut v = vec![0; FILL_BYTES_V_LEN]; - ::test::rng().fill_bytes(&mut v); - - // Sanity test: if we've gotten here, `fill_bytes` has not infinitely - // recursed. - assert_eq!(v.len(), FILL_BYTES_V_LEN); - - // To test that `fill_bytes` actually did something, check that the - // average of `v` is not 0. - let mut sum = 0.0; - for &x in &v { - sum += x as f64; - } - assert!(sum / v.len() as f64 != 0.0); - } -} diff --git a/src/librustc_back/Cargo.toml b/src/librustc_back/Cargo.toml index 730abc54568..92b024b67d4 100644 --- a/src/librustc_back/Cargo.toml +++ b/src/librustc_back/Cargo.toml @@ -12,6 +12,7 @@ crate-type = ["dylib"] syntax = { path = "../libsyntax" } serialize = { path = "../libserialize" } log = "0.3" +rand = "0.3" [features] jemalloc = [] diff --git a/src/librustc_back/lib.rs b/src/librustc_back/lib.rs index 6a9833d3784..d67de123415 100644 --- a/src/librustc_back/lib.rs +++ b/src/librustc_back/lib.rs @@ -29,11 +29,10 @@ #![feature(box_syntax)] #![feature(const_fn)] #![feature(libc)] -#![feature(rand)] -#![cfg_attr(test, feature(rand))] extern crate syntax; extern crate libc; +extern crate rand; extern crate serialize; #[macro_use] extern crate log; diff --git a/src/librustc_back/tempdir.rs b/src/librustc_back/tempdir.rs index 8ffaddd7c29..1a251536622 100644 --- a/src/librustc_back/tempdir.rs +++ b/src/librustc_back/tempdir.rs @@ -12,7 +12,7 @@ use std::env; use std::io::{self, Error, ErrorKind}; use std::fs; use std::path::{self, PathBuf, Path}; -use std::__rand::{thread_rng, Rng}; +use rand::{thread_rng, Rng}; /// A wrapper for a path to temporary directory implementing automatic /// scope-based deletion. diff --git a/src/librustc_incremental/Cargo.toml b/src/librustc_incremental/Cargo.toml index 7bf2efa4b88..b40a1b7c0cb 100644 --- a/src/librustc_incremental/Cargo.toml +++ b/src/librustc_incremental/Cargo.toml @@ -10,9 +10,10 @@ crate-type = ["dylib"] [dependencies] graphviz = { path = "../libgraphviz" } +log = "0.3" +rand = "0.3" rustc = { path = "../librustc" } rustc_data_structures = { path = "../librustc_data_structures" } serialize = { path = "../libserialize" } -log = "0.3" syntax = { path = "../libsyntax" } syntax_pos = { path = "../libsyntax_pos" } diff --git a/src/librustc_incremental/lib.rs b/src/librustc_incremental/lib.rs index e82c2897d21..5eaf8553ee3 100644 --- a/src/librustc_incremental/lib.rs +++ b/src/librustc_incremental/lib.rs @@ -15,7 +15,6 @@ html_root_url = "https://doc.rust-lang.org/nightly/")] #![deny(warnings)] -#![feature(rand)] #![feature(conservative_impl_trait)] #![feature(i128_type)] #![feature(inclusive_range_syntax)] @@ -25,6 +24,7 @@ extern crate graphviz; #[macro_use] extern crate rustc; extern crate rustc_data_structures; extern crate serialize as rustc_serialize; +extern crate rand; #[macro_use] extern crate log; extern crate syntax; diff --git a/src/librustc_incremental/persist/fs.rs b/src/librustc_incremental/persist/fs.rs index 458f47a1602..4141137a7db 100644 --- a/src/librustc_incremental/persist/fs.rs +++ b/src/librustc_incremental/persist/fs.rs @@ -125,7 +125,8 @@ use std::io; use std::mem; use std::path::{Path, PathBuf}; use std::time::{UNIX_EPOCH, SystemTime, Duration}; -use std::__rand::{thread_rng, Rng}; + +use rand::{thread_rng, Rng}; const LOCK_FILE_EXT: &'static str = ".lock"; const DEP_GRAPH_FILENAME: &'static str = "dep-graph.bin"; diff --git a/src/libstd/Cargo.toml b/src/libstd/Cargo.toml index d239b79d4ba..3430ecabcbe 100644 --- a/src/libstd/Cargo.toml +++ b/src/libstd/Cargo.toml @@ -20,12 +20,14 @@ panic_unwind = { path = "../libpanic_unwind", optional = true } panic_abort = { path = "../libpanic_abort" } core = { path = "../libcore" } libc = { path = "../rustc/libc_shim" } -rand = { path = "../librand" } compiler_builtins = { path = "../rustc/compiler_builtins_shim" } profiler_builtins = { path = "../libprofiler_builtins", optional = true } std_unicode = { path = "../libstd_unicode" } unwind = { path = "../libunwind" } +[dev-dependencies] +rand = "0.3" + [target.x86_64-apple-darwin.dependencies] rustc_asan = { path = "../librustc_asan" } rustc_tsan = { path = "../librustc_tsan" } diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index d96a4f40d3f..1771e924414 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -20,8 +20,8 @@ use hash::{Hash, Hasher, BuildHasher, SipHasher13}; use iter::{FromIterator, FusedIterator}; use mem::{self, replace}; use ops::{Deref, Index, InPlace, Place, Placer}; -use rand::{self, Rng}; use ptr; +use sys; use super::table::{self, Bucket, EmptyBucket, FullBucket, FullBucketMut, RawTable, SafeHash}; use super::table::BucketState::{Empty, Full}; @@ -2461,9 +2461,7 @@ impl RandomState { // increment one of the seeds on every RandomState creation, giving // every corresponding HashMap a different iteration order. thread_local!(static KEYS: Cell<(u64, u64)> = { - let r = rand::OsRng::new(); - let mut r = r.expect("failed to create an OS RNG"); - Cell::new((r.gen(), r.gen())) + Cell::new(sys::hashmap_random_keys()) }); KEYS.with(|keys| { diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs index 429153dc58b..37cc7a49b52 100644 --- a/src/libstd/lib.rs +++ b/src/libstd/lib.rs @@ -356,6 +356,7 @@ use prelude::v1::*; // Access to Bencher, etc. #[cfg(test)] extern crate test; +#[cfg(test)] extern crate rand; // We want to reexport a few macros from core but libcore has already been // imported by the compiler (via our #[no_std] attribute) In this case we just @@ -364,9 +365,6 @@ use prelude::v1::*; debug_assert_ne, unreachable, unimplemented, write, writeln, try)] extern crate core as __core; -#[doc(masked)] -#[allow(deprecated)] -extern crate rand as core_rand; #[macro_use] #[macro_reexport(vec, format)] extern crate alloc; @@ -504,24 +502,12 @@ mod sys; // Private support modules mod panicking; -mod rand; mod memchr; // The runtime entry point and a few unstable public functions used by the // compiler pub mod rt; -// Some external utilities of the standard library rely on randomness (aka -// rustc_back::TempDir and tests) and need a way to get at the OS rng we've got -// here. This module is not at all intended for stabilization as-is, however, -// but it may be stabilized long-term. As a result we're exposing a hidden, -// unstable module so we can get our build working. -#[doc(hidden)] -#[unstable(feature = "rand", issue = "27703")] -pub mod __rand { - pub use rand::{thread_rng, ThreadRng, Rng}; -} - // Include a number of private modules that exist solely to provide // the rustdoc documentation for primitive types. Using `include!` // because rustdoc only looks for these modules at the crate level. diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs deleted file mode 100644 index 8da070e7a49..00000000000 --- a/src/libstd/rand/mod.rs +++ /dev/null @@ -1,286 +0,0 @@ -// 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. - -//! Utilities for random number generation -//! -//! The key functions are `random()` and `Rng::gen()`. These are polymorphic -//! and so can be used to generate any type that implements `Rand`. Type inference -//! means that often a simple call to `rand::random()` or `rng.gen()` will -//! 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. -//! -//! # Thread-local RNG -//! -//! There is built-in support for a RNG associated with each thread stored -//! in thread-local storage. This RNG can be accessed via `thread_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. -//! -//! # Cryptographic security -//! -//! An application that requires an entropy source for cryptographic purposes -//! must use `OsRng`, which reads randomness from the source that the operating -//! system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on Windows). -//! The other random number generators provided by this module are not suitable -//! for such purposes. -//! -//! *Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`. -//! This module uses `/dev/urandom` for the following reasons: -//! -//! - On Linux, `/dev/random` may block if entropy pool is empty; `/dev/urandom` will not block. -//! This does not mean that `/dev/random` provides better output than -//! `/dev/urandom`; the kernel internally runs a cryptographically secure pseudorandom -//! number generator (CSPRNG) based on entropy pool for random number generation, -//! so the "quality" of `/dev/random` is not better than `/dev/urandom` in most cases. -//! However, this means that `/dev/urandom` can yield somewhat predictable randomness -//! if the entropy pool is very small, such as immediately after first booting. -//! Linux 3.17 added the `getrandom(2)` system call which solves the issue: it blocks if entropy -//! pool is not initialized yet, but it does not block once initialized. -//! `getrandom(2)` was based on `getentropy(2)`, an existing system call in OpenBSD. -//! `OsRng` tries to use `getrandom(2)` if available, and use `/dev/urandom` fallback if not. -//! If an application does not have `getrandom` and likely to be run soon after first booting, -//! or on a system with very few entropy sources, one should consider using `/dev/random` via -//! `ReaderRng`. -//! - On some systems (e.g. FreeBSD, OpenBSD and macOS) there is no difference -//! between the two sources. (Also note that, on some systems e.g. FreeBSD, both `/dev/random` -//! and `/dev/urandom` may block once if the CSPRNG has not seeded yet.) - -#![unstable(feature = "rand", issue = "27703")] - -use cell::RefCell; -use fmt; -use io; -use mem; -use rc::Rc; -use sys; - -#[cfg(target_pointer_width = "32")] -use core_rand::IsaacRng as IsaacWordRng; -#[cfg(target_pointer_width = "64")] -use core_rand::Isaac64Rng as IsaacWordRng; - -pub use core_rand::{Rand, Rng, SeedableRng}; -pub use core_rand::{XorShiftRng, IsaacRng, Isaac64Rng}; -pub use core_rand::reseeding; - -pub mod reader; - -/// The standard RNG. This is designed to be efficient on the current -/// platform. -#[derive(Copy, Clone)] -pub struct StdRng { - rng: IsaacWordRng, -} - -impl StdRng { - /// Create a randomly seeded instance of `StdRng`. - /// - /// 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 is only generating a small - /// number of random numbers, or doesn't need the utmost speed for - /// generating each number, `thread_rng` and/or `random` may be more - /// appropriate. - /// - /// Reading the randomness from the OS may fail, and any error is - /// propagated via the `io::Result` return value. - pub fn new() -> io::Result<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]) { - // the internal RNG can just be seeded from the above - // randomness. - self.rng.reseed(unsafe {mem::transmute(seed)}) - } - - fn from_seed(seed: &'a [usize]) -> StdRng { - StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) } - } -} - -/// Controls how the thread-local RNG is reseeded. -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) - } - } -} -const THREAD_RNG_RESEED_THRESHOLD: usize = 32_768; -type ThreadRngInner = reseeding::ReseedingRng<StdRng, ThreadRngReseeder>; - -/// The thread-local RNG. -#[derive(Clone)] -pub struct ThreadRng { - rng: Rc<RefCell<ThreadRngInner>>, -} - -impl fmt::Debug for ThreadRng { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.pad("ThreadRng { .. }") - } -} - -/// Retrieve the lazily-initialized thread-local random number -/// generator, seeded by the system. Intended to be used in method -/// chaining style, e.g. `thread_rng().gen::<isize>()`. -/// -/// 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 thread_rng() -> ThreadRng { - // used to make space in TLS for a random number generator - 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) - } -} - -/// A random number generator that retrieves randomness straight from -/// the operating system. Platform sources: -/// -/// - Unix-like systems (Linux, Android, macOS): read directly from -/// `/dev/urandom`, or from `getrandom(2)` system call if available. -/// - Windows: calls `CryptGenRandom`, using the default cryptographic -/// service provider with the `PROV_RSA_FULL` type. -/// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed. -/// - OpenBSD: uses the `getentropy(2)` system call. -/// -/// This does not block. -pub struct OsRng(sys::rand::OsRng); - -impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - sys::rand::OsRng::new().map(OsRng) - } -} - -impl Rng for OsRng { - #[inline] - fn next_u32(&mut self) -> u32 { - self.0.next_u32() - } - - #[inline] - fn next_u64(&mut self) -> u64 { - self.0.next_u64() - } - - #[inline] - fn fill_bytes(&mut self, bytes: &mut [u8]) { - self.0.fill_bytes(bytes) - } -} - - -#[cfg(test)] -mod tests { - use sync::mpsc::channel; - use rand::Rng; - use super::OsRng; - use thread; - - #[test] - fn test_os_rng() { - let mut r = OsRng::new().unwrap(); - - r.next_u32(); - r.next_u64(); - - let mut v = [0; 1000]; - r.fill_bytes(&mut v); - } - - #[test] - #[cfg_attr(target_os = "emscripten", ignore)] - fn test_os_rng_tasks() { - - let mut txs = vec![]; - for _ in 0..20 { - let (tx, rx) = channel(); - txs.push(tx); - - thread::spawn(move|| { - // wait until all the threads are ready to go. - rx.recv().unwrap(); - - // deschedule to attempt to interleave things as much - // as possible (XXX: is this a good test?) - let mut r = OsRng::new().unwrap(); - thread::yield_now(); - let mut v = [0; 1000]; - - for _ in 0..100 { - r.next_u32(); - thread::yield_now(); - r.next_u64(); - thread::yield_now(); - r.fill_bytes(&mut v); - thread::yield_now(); - } - }); - } - - // start all the threads - for tx in &txs { - tx.send(()).unwrap(); - } - } -} diff --git a/src/libstd/rt.rs b/src/libstd/rt.rs index 06fd838ea06..40b24cedcdc 100644 --- a/src/libstd/rt.rs +++ b/src/libstd/rt.rs @@ -23,7 +23,6 @@ #![doc(hidden)] - // Reexport some of our utilities which are expected by other crates. pub use panicking::{begin_panic, begin_panic_fmt, update_panic_count}; diff --git a/src/libstd/sync/rwlock.rs b/src/libstd/sync/rwlock.rs index d59a0b65a69..6216d78528d 100644 --- a/src/libstd/sync/rwlock.rs +++ b/src/libstd/sync/rwlock.rs @@ -554,8 +554,6 @@ impl<'a, T: ?Sized> Drop for RwLockWriteGuard<'a, T> { #[cfg(all(test, not(target_os = "emscripten")))] mod tests { - #![allow(deprecated)] // rand - use rand::{self, Rng}; use sync::mpsc::channel; use thread; @@ -576,7 +574,7 @@ mod tests { #[test] fn frob() { - const N: usize = 10; + const N: u32 = 10; const M: usize = 1000; let r = Arc::new(RwLock::new(())); diff --git a/src/libstd/sys/redox/mod.rs b/src/libstd/sys/redox/mod.rs index 7c728ebb1af..7137a506743 100644 --- a/src/libstd/sys/redox/mod.rs +++ b/src/libstd/sys/redox/mod.rs @@ -12,6 +12,8 @@ use io::{self, ErrorKind}; +pub use self::rand::hashmap_random_keys; + pub mod args; #[cfg(feature = "backtrace")] pub mod backtrace; diff --git a/src/libstd/sys/redox/rand.rs b/src/libstd/sys/redox/rand.rs index eb28eca38bc..3b378f53429 100644 --- a/src/libstd/sys/redox/rand.rs +++ b/src/libstd/sys/redox/rand.rs @@ -8,50 +8,6 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use io; -use rand::Rng; - -// FIXME: Use rand: -pub struct OsRng { - state: [u64; 2] -} - -impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - Ok(OsRng { - state: [0xBADF00D1, 0xDEADBEEF] - }) - } -} - -impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - self.next_u64() as u32 - } - fn next_u64(&mut self) -> u64 { - // Store the first and second part. - let mut x = self.state[0]; - let y = self.state[1]; - - // Put the second part into the first slot. - self.state[0] = y; - // Twist the first slot. - x ^= x << 23; - // Update the second slot. - self.state[1] = x ^ y ^ (x >> 17) ^ (y >> 26); - - // Generate the final integer. - self.state[1].wrapping_add(y) - - } - fn fill_bytes(&mut self, buf: &mut [u8]) { - for chunk in buf.chunks_mut(8) { - let mut rand: u64 = self.next_u64(); - for b in chunk.iter_mut() { - *b = rand as u8; - rand = rand >> 8; - } - } - } +pub fn hashmap_random_keys() -> (u64, u64) { + (0, 0) } diff --git a/src/libstd/sys/unix/mod.rs b/src/libstd/sys/unix/mod.rs index c2772e2e2cc..4669b2a636c 100644 --- a/src/libstd/sys/unix/mod.rs +++ b/src/libstd/sys/unix/mod.rs @@ -29,6 +29,8 @@ use libc; #[cfg(all(not(dox), target_os = "fuchsia"))] pub use os::fuchsia as platform; #[cfg(all(not(dox), target_os = "l4re"))] pub use os::linux as platform; +pub use self::rand::hashmap_random_keys; + #[macro_use] pub mod weak; diff --git a/src/libstd/sys/unix/rand.rs b/src/libstd/sys/unix/rand.rs index e2d40742c71..bbffe0f0ffe 100644 --- a/src/libstd/sys/unix/rand.rs +++ b/src/libstd/sys/unix/rand.rs @@ -8,20 +8,17 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -pub use self::imp::OsRng; - use mem; - -fn next_u32(fill_buf: &mut FnMut(&mut [u8])) -> u32 { - let mut buf: [u8; 4] = [0; 4]; - fill_buf(&mut buf); - unsafe { mem::transmute::<[u8; 4], u32>(buf) } -} - -fn next_u64(fill_buf: &mut FnMut(&mut [u8])) -> u64 { - let mut buf: [u8; 8] = [0; 8]; - fill_buf(&mut buf); - unsafe { mem::transmute::<[u8; 8], u64>(buf) } +use slice; + +pub fn hashmap_random_keys() -> (u64, u64) { + let mut v = (0, 0); + unsafe { + let view = slice::from_raw_parts_mut(&mut v as *mut _ as *mut u8, + mem::size_of_val(&v)); + imp::fill_bytes(view); + } + return v } #[cfg(all(unix, @@ -30,14 +27,9 @@ fn next_u64(fill_buf: &mut FnMut(&mut [u8])) -> u64 { not(target_os = "freebsd"), not(target_os = "fuchsia")))] mod imp { - use self::OsRngInner::*; - use super::{next_u32, next_u64}; - use fs::File; - use io; + use io::Read; use libc; - use rand::Rng; - use rand::reader::ReaderRng; use sys::os::errno; #[cfg(all(target_os = "linux", @@ -81,7 +73,7 @@ mod imp { target_arch = "s390x"))))] fn getrandom(_buf: &mut [u8]) -> libc::c_long { -1 } - fn getrandom_fill_bytes(v: &mut [u8]) { + fn getrandom_fill_bytes(v: &mut [u8]) -> bool { let mut read = 0; while read < v.len() { let result = getrandom(&mut v[read..]); @@ -90,18 +82,7 @@ mod imp { if err == libc::EINTR { continue; } else if err == libc::EAGAIN { - // if getrandom() returns EAGAIN it would have blocked - // because the non-blocking pool (urandom) has not - // initialized in the kernel yet due to a lack of entropy - // the fallback we do here is to avoid blocking applications - // which could depend on this call without ever knowing - // they do and don't have a work around. The PRNG of - // /dev/urandom will still be used but not over a completely - // full entropy pool - let reader = File::open("/dev/urandom").expect("Unable to open /dev/urandom"); - let mut reader_rng = ReaderRng::new(reader); - reader_rng.fill_bytes(&mut v[read..]); - read += v.len(); + return false } else { panic!("unexpected getrandom error: {}", err); } @@ -109,6 +90,8 @@ mod imp { read += result as usize; } } + + return true } #[cfg(all(target_os = "linux", @@ -120,6 +103,7 @@ mod imp { target_arch = "powerpc64", target_arch = "s390x")))] fn is_getrandom_available() -> bool { + use io; use sync::atomic::{AtomicBool, Ordering}; use sync::Once; @@ -151,89 +135,37 @@ mod imp { target_arch = "s390x"))))] fn is_getrandom_available() -> bool { false } - pub struct OsRng { - inner: OsRngInner, - } - - enum OsRngInner { - OsGetrandomRng, - OsReaderRng(ReaderRng<File>), - } - - impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - if is_getrandom_available() { - return Ok(OsRng { inner: OsGetrandomRng }); - } - - let reader = File::open("/dev/urandom")?; - let reader_rng = ReaderRng::new(reader); - - Ok(OsRng { inner: OsReaderRng(reader_rng) }) + pub fn fill_bytes(v: &mut [u8]) { + // getrandom_fill_bytes here can fail if getrandom() returns EAGAIN, + // meaning it would have blocked because the non-blocking pool (urandom) + // has not initialized in the kernel yet due to a lack of entropy the + // fallback we do here is to avoid blocking applications which could + // depend on this call without ever knowing they do and don't have a + // work around. The PRNG of /dev/urandom will still be used but not + // over a completely full entropy pool + if is_getrandom_available() && getrandom_fill_bytes(v) { + return } - } - impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - match self.inner { - OsGetrandomRng => next_u32(&mut getrandom_fill_bytes), - OsReaderRng(ref mut rng) => rng.next_u32(), - } - } - fn next_u64(&mut self) -> u64 { - match self.inner { - OsGetrandomRng => next_u64(&mut getrandom_fill_bytes), - OsReaderRng(ref mut rng) => rng.next_u64(), - } - } - fn fill_bytes(&mut self, v: &mut [u8]) { - match self.inner { - OsGetrandomRng => getrandom_fill_bytes(v), - OsReaderRng(ref mut rng) => rng.fill_bytes(v) - } - } + let mut file = File::open("/dev/urandom") + .expect("failed to open /dev/urandom"); + file.read_exact(v).expect("failed to read /dev/urandom"); } } #[cfg(target_os = "openbsd")] mod imp { - use super::{next_u32, next_u64}; - - use io; use libc; use sys::os::errno; - use rand::Rng; - - pub struct OsRng { - // dummy field to ensure that this struct cannot be constructed outside - // of this module - _dummy: (), - } - - impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - Ok(OsRng { _dummy: () }) - } - } - impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - next_u32(&mut |v| self.fill_bytes(v)) - } - fn next_u64(&mut self) -> u64 { - next_u64(&mut |v| self.fill_bytes(v)) - } - fn fill_bytes(&mut self, v: &mut [u8]) { - // getentropy(2) permits a maximum buffer size of 256 bytes - for s in v.chunks_mut(256) { - let ret = unsafe { - libc::getentropy(s.as_mut_ptr() as *mut libc::c_void, s.len()) - }; - if ret == -1 { - panic!("unexpected getentropy error: {}", errno()); - } + pub fn fill_bytes(v: &mut [u8]) { + // getentropy(2) permits a maximum buffer size of 256 bytes + for s in v.chunks_mut(256) { + let ret = unsafe { + libc::getentropy(s.as_mut_ptr() as *mut libc::c_void, s.len()) + }; + if ret == -1 { + panic!("unexpected getentropy error: {}", errno()); } } } @@ -241,18 +173,9 @@ mod imp { #[cfg(target_os = "ios")] mod imp { - use super::{next_u32, next_u64}; - use io; - use ptr; - use rand::Rng; use libc::{c_int, size_t}; - - pub struct OsRng { - // dummy field to ensure that this struct cannot be constructed outside - // of this module - _dummy: (), - } + use ptr; enum SecRandom {} @@ -261,79 +184,41 @@ mod imp { extern { fn SecRandomCopyBytes(rnd: *const SecRandom, - count: size_t, bytes: *mut u8) -> c_int; + count: size_t, + bytes: *mut u8) -> c_int; } - impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - Ok(OsRng { _dummy: () }) - } - } - - impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - next_u32(&mut |v| self.fill_bytes(v)) - } - fn next_u64(&mut self) -> u64 { - next_u64(&mut |v| self.fill_bytes(v)) - } - fn fill_bytes(&mut self, v: &mut [u8]) { - let ret = unsafe { - SecRandomCopyBytes(kSecRandomDefault, v.len(), - v.as_mut_ptr()) - }; - if ret == -1 { - panic!("couldn't generate random bytes: {}", - io::Error::last_os_error()); - } + pub fn fill_bytes(v: &mut [u8]) { + let ret = unsafe { + SecRandomCopyBytes(kSecRandomDefault, + v.len(), + v.as_mut_ptr()) + }; + if ret == -1 { + panic!("couldn't generate random bytes: {}", + io::Error::last_os_error()); } } } #[cfg(target_os = "freebsd")] mod imp { - use super::{next_u32, next_u64}; - - use io; use libc; - use rand::Rng; use ptr; - pub struct OsRng { - // dummy field to ensure that this struct cannot be constructed outside - // of this module - _dummy: (), - } - - impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - Ok(OsRng { _dummy: () }) - } - } - - impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - next_u32(&mut |v| self.fill_bytes(v)) - } - fn next_u64(&mut self) -> u64 { - next_u64(&mut |v| self.fill_bytes(v)) - } - fn fill_bytes(&mut self, v: &mut [u8]) { - let mib = [libc::CTL_KERN, libc::KERN_ARND]; - // kern.arandom permits a maximum buffer size of 256 bytes - for s in v.chunks_mut(256) { - let mut s_len = s.len(); - let ret = unsafe { - libc::sysctl(mib.as_ptr(), mib.len() as libc::c_uint, - s.as_mut_ptr() as *mut _, &mut s_len, - ptr::null(), 0) - }; - if ret == -1 || s_len != s.len() { - panic!("kern.arandom sysctl failed! (returned {}, s.len() {}, oldlenp {})", - ret, s.len(), s_len); - } + pub fn fill_bytes(v: &mut [u8]) { + let mib = [libc::CTL_KERN, libc::KERN_ARND]; + // kern.arandom permits a maximum buffer size of 256 bytes + for s in v.chunks_mut(256) { + let mut s_len = s.len(); + let ret = unsafe { + libc::sysctl(mib.as_ptr(), mib.len() as libc::c_uint, + s.as_mut_ptr() as *mut _, &mut s_len, + ptr::null(), 0) + }; + if ret == -1 || s_len != s.len() { + panic!("kern.arandom sysctl failed! (returned {}, s.len() {}, oldlenp {})", + ret, s.len(), s_len); } } } @@ -341,11 +226,6 @@ mod imp { #[cfg(target_os = "fuchsia")] mod imp { - use super::{next_u32, next_u64}; - - use io; - use rand::Rng; - #[link(name = "zircon")] extern { fn zx_cprng_draw(buffer: *mut u8, len: usize, actual: *mut usize) -> i32; @@ -363,39 +243,18 @@ mod imp { } } - pub struct OsRng { - // dummy field to ensure that this struct cannot be constructed outside - // of this module - _dummy: (), - } - - impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - Ok(OsRng { _dummy: () }) - } - } - - impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - next_u32(&mut |v| self.fill_bytes(v)) - } - fn next_u64(&mut self) -> u64 { - next_u64(&mut |v| self.fill_bytes(v)) - } - fn fill_bytes(&mut self, v: &mut [u8]) { - let mut buf = v; - while !buf.is_empty() { - let ret = getrandom(buf); - match ret { - Err(err) => { - panic!("kernel zx_cprng_draw call failed! (returned {}, buf.len() {})", - err, buf.len()) - } - Ok(actual) => { - let move_buf = buf; - buf = &mut move_buf[(actual as usize)..]; - } + pub fn fill_bytes(v: &mut [u8]) { + let mut buf = v; + while !buf.is_empty() { + let ret = getrandom(buf); + match ret { + Err(err) => { + panic!("kernel zx_cprng_draw call failed! (returned {}, buf.len() {})", + err, buf.len()) + } + Ok(actual) => { + let move_buf = buf; + buf = &mut move_buf[(actual as usize)..]; } } } diff --git a/src/libstd/sys/windows/mod.rs b/src/libstd/sys/windows/mod.rs index e7a9a121b25..ab8e155331e 100644 --- a/src/libstd/sys/windows/mod.rs +++ b/src/libstd/sys/windows/mod.rs @@ -17,6 +17,8 @@ use os::windows::ffi::{OsStrExt, OsStringExt}; use path::PathBuf; use time::Duration; +pub use self::rand::hashmap_random_keys; + #[macro_use] pub mod compat; pub mod args; diff --git a/src/libstd/sys/windows/pipe.rs b/src/libstd/sys/windows/pipe.rs index 452d720ce59..f3b1185c6ea 100644 --- a/src/libstd/sys/windows/pipe.rs +++ b/src/libstd/sys/windows/pipe.rs @@ -15,11 +15,13 @@ use io; use mem; use path::Path; use ptr; -use rand::{self, Rng}; use slice; +use sync::atomic::Ordering::SeqCst; +use sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT}; use sys::c; use sys::fs::{File, OpenOptions}; use sys::handle::Handle; +use sys::hashmap_random_keys; //////////////////////////////////////////////////////////////////////////////// // Anonymous pipes @@ -71,10 +73,9 @@ pub fn anon_pipe(ours_readable: bool) -> io::Result<Pipes> { let mut reject_remote_clients_flag = c::PIPE_REJECT_REMOTE_CLIENTS; loop { tries += 1; - let key: u64 = rand::thread_rng().gen(); name = format!(r"\\.\pipe\__rust_anonymous_pipe1__.{}.{}", c::GetCurrentProcessId(), - key); + random_number()); let wide_name = OsStr::new(&name) .encode_wide() .chain(Some(0)) @@ -156,6 +157,17 @@ pub fn anon_pipe(ours_readable: bool) -> io::Result<Pipes> { } } +fn random_number() -> usize { + static N: AtomicUsize = ATOMIC_USIZE_INIT; + loop { + if N.load(SeqCst) != 0 { + return N.fetch_add(1, SeqCst) + } + + N.store(hashmap_random_keys().0 as usize, SeqCst); + } +} + impl AnonPipe { pub fn handle(&self) -> &Handle { &self.inner } pub fn into_handle(self) -> Handle { self.inner } diff --git a/src/libstd/sys/windows/rand.rs b/src/libstd/sys/windows/rand.rs index f66b0a3bdc3..262323656aa 100644 --- a/src/libstd/sys/windows/rand.rs +++ b/src/libstd/sys/windows/rand.rs @@ -8,45 +8,19 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. - use io; use mem; -use rand::Rng; use sys::c; -pub struct OsRng; - -impl OsRng { - /// Create a new `OsRng`. - pub fn new() -> io::Result<OsRng> { - Ok(OsRng) - } -} - -impl Rng for OsRng { - fn next_u32(&mut self) -> u32 { - let mut v = [0; 4]; - self.fill_bytes(&mut v); - unsafe { mem::transmute(v) } - } - - fn next_u64(&mut self) -> u64 { - let mut v = [0; 8]; - self.fill_bytes(&mut v); - unsafe { mem::transmute(v) } - } - - fn fill_bytes(&mut self, v: &mut [u8]) { - // RtlGenRandom takes an ULONG (u32) for the length so we need to - // split up the buffer. - for slice in v.chunks_mut(<c::ULONG>::max_value() as usize) { - let ret = unsafe { - c::RtlGenRandom(slice.as_mut_ptr(), slice.len() as c::ULONG) - }; - if ret == 0 { - panic!("couldn't generate random bytes: {}", - io::Error::last_os_error()); - } - } +pub fn hashmap_random_keys() -> (u64, u64) { + let mut v = (0, 0); + let ret = unsafe { + c::RtlGenRandom(&mut v as *mut _ as *mut u8, + mem::size_of_val(&v) as c::ULONG) + }; + if ret == 0 { + panic!("couldn't generate random bytes: {}", + io::Error::last_os_error()); } + return v } diff --git a/src/test/compile-fail/task-rng-isnt-sendable.rs b/src/test/compile-fail/task-rng-isnt-sendable.rs deleted file mode 100644 index d85717f8ce5..00000000000 --- a/src/test/compile-fail/task-rng-isnt-sendable.rs +++ /dev/null @@ -1,21 +0,0 @@ -// 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. - -#![feature(rand)] - -// ensure that the ThreadRng isn't/doesn't become accidentally sendable. - -use std::__rand::ThreadRng; - -fn test_send<S: Send>() {} - -pub fn main() { - test_send::<ThreadRng>(); //~ ERROR std::marker::Send` is not satisfied -} diff --git a/src/test/run-pass/binary-heap-panic-safe.rs b/src/test/run-pass-fulldeps/binary-heap-panic-safe.rs index 93d3345a809..6139a7d3201 100644 --- a/src/test/run-pass/binary-heap-panic-safe.rs +++ b/src/test/run-pass-fulldeps/binary-heap-panic-safe.rs @@ -8,9 +8,11 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -#![feature(rand, std_panic)] +#![feature(rustc_private, std_panic)] -use std::__rand::{thread_rng, Rng}; +extern crate rand; + +use rand::{thread_rng, Rng}; use std::panic::{self, AssertUnwindSafe}; use std::collections::BinaryHeap; diff --git a/src/test/run-pass/env.rs b/src/test/run-pass-fulldeps/env.rs index e602fb2d7d2..cf2ea732ee1 100644 --- a/src/test/run-pass/env.rs +++ b/src/test/run-pass-fulldeps/env.rs @@ -10,14 +10,15 @@ // compile-flags: --test -#![feature(rand, std_panic)] +#![feature(rustc_private, std_panic)] + +extern crate rand; use std::env::*; -use std::__rand as rand; -use std::__rand::Rng; use std::iter::repeat; use std::ffi::{OsString, OsStr}; +use rand::Rng; fn make_rand_name() -> OsString { let mut rng = rand::thread_rng(); diff --git a/src/test/run-pass/vector-sort-panic-safe.rs b/src/test/run-pass-fulldeps/vector-sort-panic-safe.rs index c6a1859de30..82305045f80 100644 --- a/src/test/run-pass/vector-sort-panic-safe.rs +++ b/src/test/run-pass-fulldeps/vector-sort-panic-safe.rs @@ -10,11 +10,13 @@ // ignore-emscripten no threads support -#![feature(rand)] +#![feature(rustc_private)] #![feature(sort_unstable)] #![feature(const_atomic_usize_new)] -use std::__rand::{thread_rng, Rng}; +extern crate rand; + +use rand::{thread_rng, Rng}; use std::cell::Cell; use std::cmp::Ordering; use std::panic; |