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