]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! Interface to random number generators in Rust. | |
12 | //! | |
13 | //! This is an experimental library which lives underneath the standard library | |
14 | //! in its dependency chain. This library is intended to define the interface | |
15 | //! for random number generation and also provide utilities around doing so. It | |
16 | //! is not recommended to use this library directly, but rather the official | |
17 | //! interface through `std::rand`. | |
18 | ||
c34b1796 AL |
19 | // Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364) |
20 | #![cfg_attr(stage0, feature(custom_attribute))] | |
1a4d82fc JJ |
21 | #![crate_name = "rand"] |
22 | #![crate_type = "rlib"] | |
23 | #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk.png", | |
62682a34 | 24 | html_favicon_url = "https://doc.rust-lang.org/favicon.ico", |
1a4d82fc JJ |
25 | html_root_url = "http://doc.rust-lang.org/nightly/", |
26 | html_playground_url = "http://play.rust-lang.org/")] | |
1a4d82fc | 27 | #![no_std] |
1a4d82fc | 28 | #![staged_api] |
bd371182 AL |
29 | #![unstable(feature = "rand", |
30 | reason = "use `rand` from crates.io")] | |
85aaf69f | 31 | #![feature(core)] |
62682a34 SL |
32 | #![feature(core_float)] |
33 | #![feature(core_prelude)] | |
34 | #![feature(core_slice_ext)] | |
9346a6ac | 35 | #![feature(no_std)] |
62682a34 | 36 | #![feature(num_bits_bytes)] |
9346a6ac | 37 | #![feature(staged_api)] |
c34b1796 | 38 | #![feature(step_by)] |
85aaf69f | 39 | |
62682a34 | 40 | #![cfg_attr(test, feature(test, rand, rustc_private, iter_order))] |
c34b1796 | 41 | |
85aaf69f | 42 | #![allow(deprecated)] |
1a4d82fc JJ |
43 | |
44 | #[macro_use] | |
45 | extern crate core; | |
46 | ||
47 | #[cfg(test)] #[macro_use] extern crate std; | |
48 | #[cfg(test)] #[macro_use] extern crate log; | |
49 | ||
50 | use core::prelude::*; | |
85aaf69f | 51 | use core::marker::PhantomData; |
1a4d82fc JJ |
52 | |
53 | pub use isaac::{IsaacRng, Isaac64Rng}; | |
54 | pub use chacha::ChaChaRng; | |
55 | ||
56 | use distributions::{Range, IndependentSample}; | |
57 | use distributions::range::SampleRange; | |
58 | ||
59 | #[cfg(test)] | |
c34b1796 | 60 | const RAND_BENCH_N: u64 = 100; |
1a4d82fc JJ |
61 | |
62 | pub mod distributions; | |
63 | pub mod isaac; | |
64 | pub mod chacha; | |
65 | pub mod reseeding; | |
66 | mod rand_impls; | |
67 | ||
68 | /// A type that can be randomly generated using an `Rng`. | |
69 | pub trait Rand : Sized { | |
70 | /// Generates a random instance of this type using the specified source of | |
71 | /// randomness. | |
72 | fn rand<R: Rng>(rng: &mut R) -> Self; | |
73 | } | |
74 | ||
75 | /// A random number generator. | |
76 | pub trait Rng : Sized { | |
77 | /// Return the next random u32. | |
78 | /// | |
79 | /// This rarely needs to be called directly, prefer `r.gen()` to | |
80 | /// `r.next_u32()`. | |
81 | // FIXME #7771: Should be implemented in terms of next_u64 | |
82 | fn next_u32(&mut self) -> u32; | |
83 | ||
84 | /// Return the next random u64. | |
85 | /// | |
86 | /// By default this is implemented in terms of `next_u32`. An | |
87 | /// implementation of this trait must provide at least one of | |
88 | /// these two methods. Similarly to `next_u32`, this rarely needs | |
89 | /// to be called directly, prefer `r.gen()` to `r.next_u64()`. | |
90 | fn next_u64(&mut self) -> u64 { | |
91 | ((self.next_u32() as u64) << 32) | (self.next_u32() as u64) | |
92 | } | |
93 | ||
94 | /// Return the next random f32 selected from the half-open | |
95 | /// interval `[0, 1)`. | |
96 | /// | |
97 | /// By default this is implemented in terms of `next_u32`, but a | |
98 | /// random number generator which can generate numbers satisfying | |
99 | /// the requirements directly can overload this for performance. | |
100 | /// It is required that the return value lies in `[0, 1)`. | |
101 | /// | |
102 | /// See `Closed01` for the closed interval `[0,1]`, and | |
103 | /// `Open01` for the open interval `(0,1)`. | |
104 | fn next_f32(&mut self) -> f32 { | |
c34b1796 AL |
105 | const MANTISSA_BITS: usize = 24; |
106 | const IGNORED_BITS: usize = 8; | |
1a4d82fc JJ |
107 | const SCALE: f32 = (1u64 << MANTISSA_BITS) as f32; |
108 | ||
109 | // using any more than `MANTISSA_BITS` bits will | |
110 | // cause (e.g.) 0xffff_ffff to correspond to 1 | |
111 | // exactly, so we need to drop some (8 for f32, 11 | |
112 | // for f64) to guarantee the open end. | |
113 | (self.next_u32() >> IGNORED_BITS) as f32 / SCALE | |
114 | } | |
115 | ||
116 | /// Return the next random f64 selected from the half-open | |
117 | /// interval `[0, 1)`. | |
118 | /// | |
119 | /// By default this is implemented in terms of `next_u64`, but a | |
120 | /// random number generator which can generate numbers satisfying | |
121 | /// the requirements directly can overload this for performance. | |
122 | /// It is required that the return value lies in `[0, 1)`. | |
123 | /// | |
124 | /// See `Closed01` for the closed interval `[0,1]`, and | |
125 | /// `Open01` for the open interval `(0,1)`. | |
126 | fn next_f64(&mut self) -> f64 { | |
c34b1796 AL |
127 | const MANTISSA_BITS: usize = 53; |
128 | const IGNORED_BITS: usize = 11; | |
1a4d82fc JJ |
129 | const SCALE: f64 = (1u64 << MANTISSA_BITS) as f64; |
130 | ||
131 | (self.next_u64() >> IGNORED_BITS) as f64 / SCALE | |
132 | } | |
133 | ||
134 | /// Fill `dest` with random data. | |
135 | /// | |
136 | /// This has a default implementation in terms of `next_u64` and | |
137 | /// `next_u32`, but should be overridden by implementations that | |
138 | /// offer a more efficient solution than just calling those | |
139 | /// methods repeatedly. | |
140 | /// | |
141 | /// This method does *not* have a requirement to bear any fixed | |
142 | /// relationship to the other methods, for example, it does *not* | |
143 | /// have to result in the same output as progressively filling | |
144 | /// `dest` with `self.gen::<u8>()`, and any such behaviour should | |
145 | /// not be relied upon. | |
146 | /// | |
147 | /// This method should guarantee that `dest` is entirely filled | |
148 | /// with new data, and may panic if this is impossible | |
149 | /// (e.g. reading past the end of a file that is being used as the | |
150 | /// source of randomness). | |
1a4d82fc JJ |
151 | fn fill_bytes(&mut self, dest: &mut [u8]) { |
152 | // this could, in theory, be done by transmuting dest to a | |
153 | // [u64], but this is (1) likely to be undefined behaviour for | |
154 | // LLVM, (2) has to be very careful about alignment concerns, | |
155 | // (3) adds more `unsafe` that needs to be checked, (4) | |
156 | // probably doesn't give much performance gain if | |
157 | // optimisations are on. | |
85aaf69f | 158 | let mut count = 0; |
1a4d82fc | 159 | let mut num = 0; |
85aaf69f | 160 | for byte in dest { |
1a4d82fc JJ |
161 | if count == 0 { |
162 | // we could micro-optimise here by generating a u32 if | |
163 | // we only need a few more bytes to fill the vector | |
164 | // (i.e. at most 4). | |
165 | num = self.next_u64(); | |
166 | count = 8; | |
167 | } | |
168 | ||
169 | *byte = (num & 0xff) as u8; | |
170 | num >>= 8; | |
171 | count -= 1; | |
172 | } | |
173 | } | |
174 | ||
175 | /// Return a random value of a `Rand` type. | |
1a4d82fc JJ |
176 | #[inline(always)] |
177 | fn gen<T: Rand>(&mut self) -> T { | |
178 | Rand::rand(self) | |
179 | } | |
180 | ||
181 | /// Return an iterator that will yield an infinite number of randomly | |
182 | /// generated items. | |
1a4d82fc | 183 | fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> { |
85aaf69f | 184 | Generator { rng: self, _marker: PhantomData } |
1a4d82fc JJ |
185 | } |
186 | ||
187 | /// Generate a random value in the range [`low`, `high`). | |
188 | /// | |
189 | /// This is a convenience wrapper around | |
190 | /// `distributions::Range`. If this function will be called | |
191 | /// repeatedly with the same arguments, one should use `Range`, as | |
192 | /// that will amortize the computations that allow for perfect | |
193 | /// uniformity, as they only happen on initialization. | |
194 | /// | |
195 | /// # Panics | |
196 | /// | |
197 | /// Panics if `low >= high`. | |
1a4d82fc JJ |
198 | fn gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T { |
199 | assert!(low < high, "Rng.gen_range called with low >= high"); | |
200 | Range::new(low, high).ind_sample(self) | |
201 | } | |
202 | ||
203 | /// Return a bool with a 1 in n chance of true | |
c34b1796 | 204 | fn gen_weighted_bool(&mut self, n: usize) -> bool { |
1a4d82fc JJ |
205 | n <= 1 || self.gen_range(0, n) == 0 |
206 | } | |
207 | ||
208 | /// Return an iterator of random characters from the set A-Z,a-z,0-9. | |
1a4d82fc JJ |
209 | fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> { |
210 | AsciiGenerator { rng: self } | |
211 | } | |
212 | ||
213 | /// Return a random element from `values`. | |
214 | /// | |
215 | /// Return `None` if `values` is empty. | |
1a4d82fc JJ |
216 | fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> { |
217 | if values.is_empty() { | |
218 | None | |
219 | } else { | |
85aaf69f | 220 | Some(&values[self.gen_range(0, values.len())]) |
1a4d82fc JJ |
221 | } |
222 | } | |
223 | ||
224 | /// Shuffle a mutable slice in place. | |
1a4d82fc JJ |
225 | fn shuffle<T>(&mut self, values: &mut [T]) { |
226 | let mut i = values.len(); | |
85aaf69f | 227 | while i >= 2 { |
1a4d82fc | 228 | // invariant: elements with index >= i have been locked in place. |
85aaf69f | 229 | i -= 1; |
1a4d82fc | 230 | // lock element i in place. |
85aaf69f | 231 | values.swap(i, self.gen_range(0, i + 1)); |
1a4d82fc JJ |
232 | } |
233 | } | |
234 | } | |
235 | ||
236 | /// Iterator which will generate a stream of random items. | |
237 | /// | |
238 | /// This iterator is created via the `gen_iter` method on `Rng`. | |
239 | pub struct Generator<'a, T, R:'a> { | |
240 | rng: &'a mut R, | |
85aaf69f | 241 | _marker: PhantomData<T> |
1a4d82fc JJ |
242 | } |
243 | ||
244 | impl<'a, T: Rand, R: Rng> Iterator for Generator<'a, T, R> { | |
245 | type Item = T; | |
246 | ||
247 | fn next(&mut self) -> Option<T> { | |
248 | Some(self.rng.gen()) | |
249 | } | |
250 | } | |
251 | ||
252 | /// Iterator which will continuously generate random ascii characters. | |
253 | /// | |
254 | /// This iterator is created via the `gen_ascii_chars` method on `Rng`. | |
255 | pub struct AsciiGenerator<'a, R:'a> { | |
256 | rng: &'a mut R, | |
257 | } | |
258 | ||
259 | impl<'a, R: Rng> Iterator for AsciiGenerator<'a, R> { | |
260 | type Item = char; | |
261 | ||
262 | fn next(&mut self) -> Option<char> { | |
c34b1796 | 263 | const GEN_ASCII_STR_CHARSET: &'static [u8] = |
1a4d82fc JJ |
264 | b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\ |
265 | abcdefghijklmnopqrstuvwxyz\ | |
266 | 0123456789"; | |
267 | Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char) | |
268 | } | |
269 | } | |
270 | ||
271 | /// A random number generator that can be explicitly seeded to produce | |
272 | /// the same stream of randomness multiple times. | |
273 | pub trait SeedableRng<Seed>: Rng { | |
274 | /// Reseed an RNG with the given seed. | |
1a4d82fc JJ |
275 | fn reseed(&mut self, Seed); |
276 | ||
277 | /// Create a new RNG with the given seed. | |
1a4d82fc JJ |
278 | fn from_seed(seed: Seed) -> Self; |
279 | } | |
280 | ||
281 | /// An Xorshift[1] random number | |
282 | /// generator. | |
283 | /// | |
284 | /// The Xorshift algorithm is not suitable for cryptographic purposes | |
285 | /// but is very fast. If you do not know for sure that it fits your | |
286 | /// requirements, use a more secure one such as `IsaacRng` or `OsRng`. | |
287 | /// | |
288 | /// [1]: Marsaglia, George (July 2003). ["Xorshift | |
289 | /// RNGs"](http://www.jstatsoft.org/v08/i14/paper). *Journal of | |
290 | /// Statistical Software*. Vol. 8 (Issue 14). | |
1a4d82fc JJ |
291 | #[derive(Clone)] |
292 | pub struct XorShiftRng { | |
293 | x: u32, | |
294 | y: u32, | |
295 | z: u32, | |
296 | w: u32, | |
297 | } | |
298 | ||
299 | impl XorShiftRng { | |
300 | /// Creates a new XorShiftRng instance which is not seeded. | |
301 | /// | |
302 | /// The initial values of this RNG are constants, so all generators created | |
303 | /// by this function will yield the same stream of random numbers. It is | |
304 | /// highly recommended that this is created through `SeedableRng` instead of | |
305 | /// this function | |
306 | pub fn new_unseeded() -> XorShiftRng { | |
307 | XorShiftRng { | |
308 | x: 0x193a6754, | |
309 | y: 0xa8a7d469, | |
310 | z: 0x97830e05, | |
311 | w: 0x113ba7bb, | |
312 | } | |
313 | } | |
314 | } | |
315 | ||
316 | impl Rng for XorShiftRng { | |
317 | #[inline] | |
318 | fn next_u32(&mut self) -> u32 { | |
319 | let x = self.x; | |
320 | let t = x ^ (x << 11); | |
321 | self.x = self.y; | |
322 | self.y = self.z; | |
323 | self.z = self.w; | |
324 | let w = self.w; | |
325 | self.w = w ^ (w >> 19) ^ (t ^ (t >> 8)); | |
326 | self.w | |
327 | } | |
328 | } | |
329 | ||
330 | impl SeedableRng<[u32; 4]> for XorShiftRng { | |
331 | /// Reseed an XorShiftRng. This will panic if `seed` is entirely 0. | |
332 | fn reseed(&mut self, seed: [u32; 4]) { | |
333 | assert!(!seed.iter().all(|&x| x == 0), | |
334 | "XorShiftRng.reseed called with an all zero seed."); | |
335 | ||
336 | self.x = seed[0]; | |
337 | self.y = seed[1]; | |
338 | self.z = seed[2]; | |
339 | self.w = seed[3]; | |
340 | } | |
341 | ||
342 | /// Create a new XorShiftRng. This will panic if `seed` is entirely 0. | |
343 | fn from_seed(seed: [u32; 4]) -> XorShiftRng { | |
344 | assert!(!seed.iter().all(|&x| x == 0), | |
345 | "XorShiftRng::from_seed called with an all zero seed."); | |
346 | ||
347 | XorShiftRng { | |
348 | x: seed[0], | |
349 | y: seed[1], | |
350 | z: seed[2], | |
351 | w: seed[3] | |
352 | } | |
353 | } | |
354 | } | |
355 | ||
356 | impl Rand for XorShiftRng { | |
357 | fn rand<R: Rng>(rng: &mut R) -> XorShiftRng { | |
358 | let mut tuple: (u32, u32, u32, u32) = rng.gen(); | |
359 | while tuple == (0, 0, 0, 0) { | |
360 | tuple = rng.gen(); | |
361 | } | |
362 | let (x, y, z, w) = tuple; | |
363 | XorShiftRng { x: x, y: y, z: z, w: w } | |
364 | } | |
365 | } | |
366 | ||
367 | /// A wrapper for generating floating point numbers uniformly in the | |
368 | /// open interval `(0,1)` (not including either endpoint). | |
369 | /// | |
370 | /// Use `Closed01` for the closed interval `[0,1]`, and the default | |
371 | /// `Rand` implementation for `f32` and `f64` for the half-open | |
372 | /// `[0,1)`. | |
1a4d82fc JJ |
373 | pub struct Open01<F>(pub F); |
374 | ||
375 | /// A wrapper for generating floating point numbers uniformly in the | |
376 | /// closed interval `[0,1]` (including both endpoints). | |
377 | /// | |
378 | /// Use `Open01` for the closed interval `(0,1)`, and the default | |
379 | /// `Rand` implementation of `f32` and `f64` for the half-open | |
380 | /// `[0,1)`. | |
1a4d82fc JJ |
381 | pub struct Closed01<F>(pub F); |
382 | ||
1a4d82fc JJ |
383 | #[cfg(test)] |
384 | mod test { | |
9346a6ac | 385 | use std::__rand as rand; |
1a4d82fc JJ |
386 | |
387 | pub struct MyRng<R> { inner: R } | |
388 | ||
389 | impl<R: rand::Rng> ::Rng for MyRng<R> { | |
390 | fn next_u32(&mut self) -> u32 { | |
9346a6ac | 391 | rand::Rng::next_u32(&mut self.inner) |
1a4d82fc JJ |
392 | } |
393 | } | |
394 | ||
395 | pub fn rng() -> MyRng<rand::ThreadRng> { | |
396 | MyRng { inner: rand::thread_rng() } | |
397 | } | |
398 | ||
9346a6ac AL |
399 | pub fn weak_rng() -> MyRng<rand::ThreadRng> { |
400 | MyRng { inner: rand::thread_rng() } | |
1a4d82fc JJ |
401 | } |
402 | } |