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