1 // Copyright 2013-2017 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 //! Utilities for random number generation
12 //!
13 //! The key functions are `random()` and `Rng::gen()`. These are polymorphic and
14 //! so can be used to generate any type that implements `Rand`. Type inference
15 //! means that often a simple call to `rand::random()` or `rng.gen()` will
16 //! suffice, but sometimes an annotation is required, e.g.
17 //! `rand::random::<f64>()`.
18 //!
19 //! See the `distributions` submodule for sampling random numbers from
20 //! distributions like normal and exponential.
21 //!
22 //! # Usage
23 //!
24 //! This crate is [on crates.io](https://crates.io/crates/rand) and can be
25 //! used by adding `rand` to the dependencies in your project's `Cargo.toml`.
26 //!
27 //! ```toml
28 //! [dependencies]
29 //! rand = "0.4"
30 //! ```
31 //!
32 //! and this to your crate root:
33 //!
34 //! ```rust
35 //! extern crate rand;
36 //! ```
37 //!
38 //! # Thread-local RNG
39 //!
40 //! There is built-in support for a RNG associated with each thread stored
41 //! in thread-local storage. This RNG can be accessed via `thread_rng`, or
42 //! used implicitly via `random`. This RNG is normally randomly seeded
43 //! from an operating-system source of randomness, e.g. `/dev/urandom` on
44 //! Unix systems, and will automatically reseed itself from this source
45 //! after generating 32 KiB of random data.
46 //!
47 //! # Cryptographic security
48 //!
49 //! An application that requires an entropy source for cryptographic purposes
50 //! must use `OsRng`, which reads randomness from the source that the operating
51 //! system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on
52 //! Windows).
53 //! The other random number generators provided by this module are not suitable
54 //! for such purposes.
55 //!
56 //! *Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`.
57 //! This module uses `/dev/urandom` for the following reasons:
58 //!
59 //! - On Linux, `/dev/random` may block if entropy pool is empty;
60 //! `/dev/urandom` will not block. This does not mean that `/dev/random`
61 //! provides better output than `/dev/urandom`; the kernel internally runs a
62 //! cryptographically secure pseudorandom number generator (CSPRNG) based on
63 //! entropy pool for random number generation, so the "quality" of
64 //! `/dev/random` is not better than `/dev/urandom` in most cases. However,
65 //! this means that `/dev/urandom` can yield somewhat predictable randomness
66 //! if the entropy pool is very small, such as immediately after first
67 //! booting. Linux 3.17 added the `getrandom(2)` system call which solves
68 //! the issue: it blocks if entropy pool is not initialized yet, but it does
69 //! not block once initialized. `OsRng` tries to use `getrandom(2)` if
70 //! available, and use `/dev/urandom` fallback if not. If an application
71 //! does not have `getrandom` and likely to be run soon after first booting,
72 //! or on a system with very few entropy sources, one should consider using
73 //! `/dev/random` via `ReadRng`.
74 //! - On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no
75 //! difference between the two sources. (Also note that, on some systems
76 //! e.g. FreeBSD, both `/dev/random` and `/dev/urandom` may block once if
77 //! the CSPRNG has not seeded yet.)
78 //!
79 //! # Examples
80 //!
81 //! ```rust
82 //! use rand::Rng;
83 //!
84 //! let mut rng = rand::thread_rng();
85 //! if rng.gen() { // random bool
86 //! println!("i32: {}, u32: {}", rng.gen::<i32>(), rng.gen::<u32>())
87 //! }
88 //! ```
89 //!
90 //! ```rust
91 //! let tuple = rand::random::<(f64, char)>();
92 //! println!("{:?}", tuple)
93 //! ```
94 //!
95 //! ## Monte Carlo estimation of π
96 //!
97 //! For this example, imagine we have a square with sides of length 2 and a unit
98 //! circle, both centered at the origin. Since the area of a unit circle is π,
99 //! we have:
100 //!
101 //! ```text
102 //! (area of unit circle) / (area of square) = π / 4
103 //! ```
104 //!
105 //! So if we sample many points randomly from the square, roughly π / 4 of them
106 //! should be inside the circle.
107 //!
108 //! We can use the above fact to estimate the value of π: pick many points in
109 //! the square at random, calculate the fraction that fall within the circle,
110 //! and multiply this fraction by 4.
111 //!
112 //! ```
113 //! use rand::distributions::{IndependentSample, Range};
114 //!
115 //! fn main() {
116 //! let between = Range::new(-1f64, 1.);
117 //! let mut rng = rand::thread_rng();
118 //!
119 //! let total = 1_000_000;
120 //! let mut in_circle = 0;
121 //!
122 //! for _ in 0..total {
123 //! let a = between.ind_sample(&mut rng);
124 //! let b = between.ind_sample(&mut rng);
125 //! if a*a + b*b <= 1. {
126 //! in_circle += 1;
127 //! }
128 //! }
129 //!
130 //! // prints something close to 3.14159...
131 //! println!("{}", 4. * (in_circle as f64) / (total as f64));
132 //! }
133 //! ```
134 //!
135 //! ## Monty Hall Problem
136 //!
137 //! This is a simulation of the [Monty Hall Problem][]:
138 //!
139 //! > Suppose you're on a game show, and you're given the choice of three doors:
140 //! > Behind one door is a car; behind the others, goats. You pick a door, say
141 //! > No. 1, and the host, who knows what's behind the doors, opens another
142 //! > door, say No. 3, which has a goat. He then says to you, "Do you want to
143 //! > pick door No. 2?" Is it to your advantage to switch your choice?
144 //!
145 //! The rather unintuitive answer is that you will have a 2/3 chance of winning
146 //! if you switch and a 1/3 chance of winning if you don't, so it's better to
147 //! switch.
148 //!
149 //! This program will simulate the game show and with large enough simulation
150 //! steps it will indeed confirm that it is better to switch.
151 //!
152 //! [Monty Hall Problem]: http://en.wikipedia.org/wiki/Monty_Hall_problem
153 //!
154 //! ```
155 //! use rand::Rng;
156 //! use rand::distributions::{IndependentSample, Range};
157 //!
158 //! struct SimulationResult {
159 //! win: bool,
160 //! switch: bool,
161 //! }
162 //!
163 //! // Run a single simulation of the Monty Hall problem.
164 //! fn simulate<R: Rng>(random_door: &Range<u32>, rng: &mut R)
165 //! -> SimulationResult {
166 //! let car = random_door.ind_sample(rng);
167 //!
168 //! // This is our initial choice
169 //! let mut choice = random_door.ind_sample(rng);
170 //!
171 //! // The game host opens a door
172 //! let open = game_host_open(car, choice, rng);
173 //!
174 //! // Shall we switch?
175 //! let switch = rng.gen();
176 //! if switch {
177 //! choice = switch_door(choice, open);
178 //! }
179 //!
180 //! SimulationResult { win: choice == car, switch: switch }
181 //! }
182 //!
183 //! // Returns the door the game host opens given our choice and knowledge of
184 //! // where the car is. The game host will never open the door with the car.
185 //! fn game_host_open<R: Rng>(car: u32, choice: u32, rng: &mut R) -> u32 {
186 //! let choices = free_doors(&[car, choice]);
187 //! rand::seq::sample_slice(rng, &choices, 1)[0]
188 //! }
189 //!
190 //! // Returns the door we switch to, given our current choice and
191 //! // the open door. There will only be one valid door.
192 //! fn switch_door(choice: u32, open: u32) -> u32 {
193 //! free_doors(&[choice, open])[0]
194 //! }
195 //!
196 //! fn free_doors(blocked: &[u32]) -> Vec<u32> {
197 //! (0..3).filter(|x| !blocked.contains(x)).collect()
198 //! }
199 //!
200 //! fn main() {
201 //! // The estimation will be more accurate with more simulations
202 //! let num_simulations = 10000;
203 //!
204 //! let mut rng = rand::thread_rng();
205 //! let random_door = Range::new(0, 3);
206 //!
207 //! let (mut switch_wins, mut switch_losses) = (0, 0);
208 //! let (mut keep_wins, mut keep_losses) = (0, 0);
209 //!
210 //! println!("Running {} simulations...", num_simulations);
211 //! for _ in 0..num_simulations {
212 //! let result = simulate(&random_door, &mut rng);
213 //!
214 //! match (result.win, result.switch) {
215 //! (true, true) => switch_wins += 1,
216 //! (true, false) => keep_wins += 1,
217 //! (false, true) => switch_losses += 1,
218 //! (false, false) => keep_losses += 1,
219 //! }
220 //! }
221 //!
222 //! let total_switches = switch_wins + switch_losses;
223 //! let total_keeps = keep_wins + keep_losses;
224 //!
225 //! println!("Switched door {} times with {} wins and {} losses",
226 //! total_switches, switch_wins, switch_losses);
227 //!
228 //! println!("Kept our choice {} times with {} wins and {} losses",
229 //! total_keeps, keep_wins, keep_losses);
230 //!
231 //! // With a large number of simulations, the values should converge to
232 //! // 0.667 and 0.333 respectively.
233 //! println!("Estimated chance to win if we switch: {}",
234 //! switch_wins as f32 / total_switches as f32);
235 //! println!("Estimated chance to win if we don't: {}",
236 //! keep_wins as f32 / total_keeps as f32);
237 //! }
238 //! ```
239
240 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
241 html_favicon_url = "https://www.rust-lang.org/favicon.ico",
242 html_root_url = "https://docs.rs/rand/0.4")]
243
244 #![deny(missing_debug_implementations)]
245
246 #![cfg_attr(not(feature="std"), no_std)]
247 #![cfg_attr(all(feature="alloc", not(feature="std")), feature(alloc))]
248 #![cfg_attr(feature = "i128_support", feature(i128_type, i128))]
249
250 #[cfg(feature="std")] extern crate std as core;
251 #[cfg(all(feature = "alloc", not(feature="std")))] extern crate alloc;
252
253 #[cfg(target_env = "sgx")]
254 extern crate rdrand;
255
256 #[cfg(target_env = "sgx")]
257 extern crate rand_core;
258
259 use core::marker;
260 use core::mem;
261 #[cfg(feature="std")] use std::cell::RefCell;
262 #[cfg(feature="std")] use std::io;
263 #[cfg(feature="std")] use std::rc::Rc;
264
265 // external rngs
266 pub use jitter::JitterRng;
267 #[cfg(feature="std")] pub use os::OsRng;
268
269 // pseudo rngs
270 pub use isaac::{IsaacRng, Isaac64Rng};
271 pub use chacha::ChaChaRng;
272 pub use prng::XorShiftRng;
273
274 // local use declarations
275 #[cfg(target_pointer_width = "32")]
276 use prng::IsaacRng as IsaacWordRng;
277 #[cfg(target_pointer_width = "64")]
278 use prng::Isaac64Rng as IsaacWordRng;
279
280 use distributions::{Range, IndependentSample};
281 use distributions::range::SampleRange;
282
283 // public modules
284 pub mod distributions;
285 pub mod jitter;
286 #[cfg(feature="std")] pub mod os;
287 #[cfg(feature="std")] pub mod read;
288 pub mod reseeding;
289 #[cfg(any(feature="std", feature = "alloc"))] pub mod seq;
290
291 // These tiny modules are here to avoid API breakage, probably only temporarily
292 pub mod chacha {
293 //! The ChaCha random number generator.
294 pub use prng::ChaChaRng;
295 }
296 pub mod isaac {
297 //! The ISAAC random number generator.
298 pub use prng::{IsaacRng, Isaac64Rng};
299 }
300
301 // private modules
302 mod rand_impls;
303 mod prng;
304
305
306 /// A type that can be randomly generated using an `Rng`.
307 ///
308 /// ## Built-in Implementations
309 ///
310 /// This crate implements `Rand` for various primitive types. Assuming the
311 /// provided `Rng` is well-behaved, these implementations generate values with
312 /// the following ranges and distributions:
313 ///
314 /// * Integers (`i32`, `u32`, `isize`, `usize`, etc.): Uniformly distributed
315 /// over all values of the type.
316 /// * `char`: Uniformly distributed over all Unicode scalar values, i.e. all
317 /// code points in the range `0...0x10_FFFF`, except for the range
318 /// `0xD800...0xDFFF` (the surrogate code points). This includes
319 /// unassigned/reserved code points.
320 /// * `bool`: Generates `false` or `true`, each with probability 0.5.
321 /// * Floating point types (`f32` and `f64`): Uniformly distributed in the
322 /// half-open range `[0, 1)`. (The [`Open01`], [`Closed01`], [`Exp1`], and
323 /// [`StandardNormal`] wrapper types produce floating point numbers with
324 /// alternative ranges or distributions.)
325 ///
326 /// [`Open01`]: struct.Open01.html
327 /// [`Closed01`]: struct.Closed01.html
328 /// [`Exp1`]: distributions/exponential/struct.Exp1.html
329 /// [`StandardNormal`]: distributions/normal/struct.StandardNormal.html
330 ///
331 /// The following aggregate types also implement `Rand` as long as their
332 /// component types implement it:
333 ///
334 /// * Tuples and arrays: Each element of the tuple or array is generated
335 /// independently, using its own `Rand` implementation.
336 /// * `Option<T>`: Returns `None` with probability 0.5; otherwise generates a
337 /// random `T` and returns `Some(T)`.
338 pub trait Rand : Sized {
339 /// Generates a random instance of this type using the specified source of
340 /// randomness.
rand<R: Rng>(rng: &mut R) -> Self341 fn rand<R: Rng>(rng: &mut R) -> Self;
342 }
343
344 /// A random number generator.
345 pub trait Rng {
346 /// Return the next random u32.
347 ///
348 /// This rarely needs to be called directly, prefer `r.gen()` to
349 /// `r.next_u32()`.
350 // FIXME #rust-lang/rfcs#628: Should be implemented in terms of next_u64
next_u32(&mut self) -> u32351 fn next_u32(&mut self) -> u32;
352
353 /// Return the next random u64.
354 ///
355 /// By default this is implemented in terms of `next_u32`. An
356 /// implementation of this trait must provide at least one of
357 /// these two methods. Similarly to `next_u32`, this rarely needs
358 /// to be called directly, prefer `r.gen()` to `r.next_u64()`.
next_u64(&mut self) -> u64359 fn next_u64(&mut self) -> u64 {
360 ((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
361 }
362
363 /// Return the next random f32 selected from the half-open
364 /// interval `[0, 1)`.
365 ///
366 /// This uses a technique described by Saito and Matsumoto at
367 /// MCQMC'08. Given that the IEEE floating point numbers are
368 /// uniformly distributed over [1,2), we generate a number in
369 /// this range and then offset it onto the range [0,1). Our
370 /// choice of bits (masking v. shifting) is arbitrary and
371 /// should be immaterial for high quality generators. For low
372 /// quality generators (ex. LCG), prefer bitshifting due to
373 /// correlation between sequential low order bits.
374 ///
375 /// See:
376 /// A PRNG specialized in double precision floating point numbers using
377 /// an affine transition
378 ///
379 /// * <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/dSFMT.pdf>
380 /// * <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/dSFMT-slide-e.pdf>
381 ///
382 /// By default this is implemented in terms of `next_u32`, but a
383 /// random number generator which can generate numbers satisfying
384 /// the requirements directly can overload this for performance.
385 /// It is required that the return value lies in `[0, 1)`.
386 ///
387 /// See `Closed01` for the closed interval `[0,1]`, and
388 /// `Open01` for the open interval `(0,1)`.
next_f32(&mut self) -> f32389 fn next_f32(&mut self) -> f32 {
390 const UPPER_MASK: u32 = 0x3F800000;
391 const LOWER_MASK: u32 = 0x7FFFFF;
392 let tmp = UPPER_MASK | (self.next_u32() & LOWER_MASK);
393 let result: f32 = unsafe { mem::transmute(tmp) };
394 result - 1.0
395 }
396
397 /// Return the next random f64 selected from the half-open
398 /// interval `[0, 1)`.
399 ///
400 /// By default this is implemented in terms of `next_u64`, but a
401 /// random number generator which can generate numbers satisfying
402 /// the requirements directly can overload this for performance.
403 /// It is required that the return value lies in `[0, 1)`.
404 ///
405 /// See `Closed01` for the closed interval `[0,1]`, and
406 /// `Open01` for the open interval `(0,1)`.
next_f64(&mut self) -> f64407 fn next_f64(&mut self) -> f64 {
408 const UPPER_MASK: u64 = 0x3FF0000000000000;
409 const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
410 let tmp = UPPER_MASK | (self.next_u64() & LOWER_MASK);
411 let result: f64 = unsafe { mem::transmute(tmp) };
412 result - 1.0
413 }
414
415 /// Fill `dest` with random data.
416 ///
417 /// This has a default implementation in terms of `next_u64` and
418 /// `next_u32`, but should be overridden by implementations that
419 /// offer a more efficient solution than just calling those
420 /// methods repeatedly.
421 ///
422 /// This method does *not* have a requirement to bear any fixed
423 /// relationship to the other methods, for example, it does *not*
424 /// have to result in the same output as progressively filling
425 /// `dest` with `self.gen::<u8>()`, and any such behaviour should
426 /// not be relied upon.
427 ///
428 /// This method should guarantee that `dest` is entirely filled
429 /// with new data, and may panic if this is impossible
430 /// (e.g. reading past the end of a file that is being used as the
431 /// source of randomness).
432 ///
433 /// # Example
434 ///
435 /// ```rust
436 /// use rand::{thread_rng, Rng};
437 ///
438 /// let mut v = [0u8; 13579];
439 /// thread_rng().fill_bytes(&mut v);
440 /// println!("{:?}", &v[..]);
441 /// ```
fill_bytes(&mut self, dest: &mut [u8])442 fn fill_bytes(&mut self, dest: &mut [u8]) {
443 // this could, in theory, be done by transmuting dest to a
444 // [u64], but this is (1) likely to be undefined behaviour for
445 // LLVM, (2) has to be very careful about alignment concerns,
446 // (3) adds more `unsafe` that needs to be checked, (4)
447 // probably doesn't give much performance gain if
448 // optimisations are on.
449 let mut count = 0;
450 let mut num = 0;
451 for byte in dest.iter_mut() {
452 if count == 0 {
453 // we could micro-optimise here by generating a u32 if
454 // we only need a few more bytes to fill the vector
455 // (i.e. at most 4).
456 num = self.next_u64();
457 count = 8;
458 }
459
460 *byte = (num & 0xff) as u8;
461 num >>= 8;
462 count -= 1;
463 }
464 }
465
466 /// Return a random value of a `Rand` type.
467 ///
468 /// # Example
469 ///
470 /// ```rust
471 /// use rand::{thread_rng, Rng};
472 ///
473 /// let mut rng = thread_rng();
474 /// let x: u32 = rng.gen();
475 /// println!("{}", x);
476 /// println!("{:?}", rng.gen::<(f64, bool)>());
477 /// ```
478 #[inline(always)]
gen<T: Rand>(&mut self) -> T where Self: Sized479 fn gen<T: Rand>(&mut self) -> T where Self: Sized {
480 Rand::rand(self)
481 }
482
483 /// Return an iterator that will yield an infinite number of randomly
484 /// generated items.
485 ///
486 /// # Example
487 ///
488 /// ```
489 /// use rand::{thread_rng, Rng};
490 ///
491 /// let mut rng = thread_rng();
492 /// let x = rng.gen_iter::<u32>().take(10).collect::<Vec<u32>>();
493 /// println!("{:?}", x);
494 /// println!("{:?}", rng.gen_iter::<(f64, bool)>().take(5)
495 /// .collect::<Vec<(f64, bool)>>());
496 /// ```
gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> where Self: Sized497 fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> where Self: Sized {
498 Generator { rng: self, _marker: marker::PhantomData }
499 }
500
501 /// Generate a random value in the range [`low`, `high`).
502 ///
503 /// This is a convenience wrapper around
504 /// `distributions::Range`. If this function will be called
505 /// repeatedly with the same arguments, one should use `Range`, as
506 /// that will amortize the computations that allow for perfect
507 /// uniformity, as they only happen on initialization.
508 ///
509 /// # Panics
510 ///
511 /// Panics if `low >= high`.
512 ///
513 /// # Example
514 ///
515 /// ```rust
516 /// use rand::{thread_rng, Rng};
517 ///
518 /// let mut rng = thread_rng();
519 /// let n: u32 = rng.gen_range(0, 10);
520 /// println!("{}", n);
521 /// let m: f64 = rng.gen_range(-40.0f64, 1.3e5f64);
522 /// println!("{}", m);
523 /// ```
gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T where Self: Sized524 fn gen_range<T: PartialOrd + SampleRange>(&mut self, low: T, high: T) -> T where Self: Sized {
525 assert!(low < high, "Rng.gen_range called with low >= high");
526 Range::new(low, high).ind_sample(self)
527 }
528
529 /// Return a bool with a 1 in n chance of true
530 ///
531 /// # Example
532 ///
533 /// ```rust
534 /// use rand::{thread_rng, Rng};
535 ///
536 /// let mut rng = thread_rng();
537 /// println!("{}", rng.gen_weighted_bool(3));
538 /// ```
gen_weighted_bool(&mut self, n: u32) -> bool where Self: Sized539 fn gen_weighted_bool(&mut self, n: u32) -> bool where Self: Sized {
540 n <= 1 || self.gen_range(0, n) == 0
541 }
542
543 /// Return an iterator of random characters from the set A-Z,a-z,0-9.
544 ///
545 /// # Example
546 ///
547 /// ```rust
548 /// use rand::{thread_rng, Rng};
549 ///
550 /// let s: String = thread_rng().gen_ascii_chars().take(10).collect();
551 /// println!("{}", s);
552 /// ```
gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> where Self: Sized553 fn gen_ascii_chars<'a>(&'a mut self) -> AsciiGenerator<'a, Self> where Self: Sized {
554 AsciiGenerator { rng: self }
555 }
556
557 /// Return a random element from `values`.
558 ///
559 /// Return `None` if `values` is empty.
560 ///
561 /// # Example
562 ///
563 /// ```
564 /// use rand::{thread_rng, Rng};
565 ///
566 /// let choices = [1, 2, 4, 8, 16, 32];
567 /// let mut rng = thread_rng();
568 /// println!("{:?}", rng.choose(&choices));
569 /// assert_eq!(rng.choose(&choices[..0]), None);
570 /// ```
choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> where Self: Sized571 fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> where Self: Sized {
572 if values.is_empty() {
573 None
574 } else {
575 Some(&values[self.gen_range(0, values.len())])
576 }
577 }
578
579 /// Return a mutable pointer to a random element from `values`.
580 ///
581 /// Return `None` if `values` is empty.
choose_mut<'a, T>(&mut self, values: &'a mut [T]) -> Option<&'a mut T> where Self: Sized582 fn choose_mut<'a, T>(&mut self, values: &'a mut [T]) -> Option<&'a mut T> where Self: Sized {
583 if values.is_empty() {
584 None
585 } else {
586 let len = values.len();
587 Some(&mut values[self.gen_range(0, len)])
588 }
589 }
590
591 /// Shuffle a mutable slice in place.
592 ///
593 /// This applies Durstenfeld's algorithm for the [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)
594 /// which produces an unbiased permutation.
595 ///
596 /// # Example
597 ///
598 /// ```rust
599 /// use rand::{thread_rng, Rng};
600 ///
601 /// let mut rng = thread_rng();
602 /// let mut y = [1, 2, 3];
603 /// rng.shuffle(&mut y);
604 /// println!("{:?}", y);
605 /// rng.shuffle(&mut y);
606 /// println!("{:?}", y);
607 /// ```
shuffle<T>(&mut self, values: &mut [T]) where Self: Sized608 fn shuffle<T>(&mut self, values: &mut [T]) where Self: Sized {
609 let mut i = values.len();
610 while i >= 2 {
611 // invariant: elements with index >= i have been locked in place.
612 i -= 1;
613 // lock element i in place.
614 values.swap(i, self.gen_range(0, i + 1));
615 }
616 }
617 }
618
619 impl<'a, R: ?Sized> Rng for &'a mut R where R: Rng {
next_u32(&mut self) -> u32620 fn next_u32(&mut self) -> u32 {
621 (**self).next_u32()
622 }
623
next_u64(&mut self) -> u64624 fn next_u64(&mut self) -> u64 {
625 (**self).next_u64()
626 }
627
next_f32(&mut self) -> f32628 fn next_f32(&mut self) -> f32 {
629 (**self).next_f32()
630 }
631
next_f64(&mut self) -> f64632 fn next_f64(&mut self) -> f64 {
633 (**self).next_f64()
634 }
635
fill_bytes(&mut self, dest: &mut [u8])636 fn fill_bytes(&mut self, dest: &mut [u8]) {
637 (**self).fill_bytes(dest)
638 }
639 }
640
641 #[cfg(feature="std")]
642 impl<R: ?Sized> Rng for Box<R> where R: Rng {
next_u32(&mut self) -> u32643 fn next_u32(&mut self) -> u32 {
644 (**self).next_u32()
645 }
646
next_u64(&mut self) -> u64647 fn next_u64(&mut self) -> u64 {
648 (**self).next_u64()
649 }
650
next_f32(&mut self) -> f32651 fn next_f32(&mut self) -> f32 {
652 (**self).next_f32()
653 }
654
next_f64(&mut self) -> f64655 fn next_f64(&mut self) -> f64 {
656 (**self).next_f64()
657 }
658
fill_bytes(&mut self, dest: &mut [u8])659 fn fill_bytes(&mut self, dest: &mut [u8]) {
660 (**self).fill_bytes(dest)
661 }
662 }
663
664 /// Iterator which will generate a stream of random items.
665 ///
666 /// This iterator is created via the [`gen_iter`] method on [`Rng`].
667 ///
668 /// [`gen_iter`]: trait.Rng.html#method.gen_iter
669 /// [`Rng`]: trait.Rng.html
670 #[derive(Debug)]
671 pub struct Generator<'a, T, R:'a> {
672 rng: &'a mut R,
673 _marker: marker::PhantomData<fn() -> T>,
674 }
675
676 impl<'a, T: Rand, R: Rng> Iterator for Generator<'a, T, R> {
677 type Item = T;
678
next(&mut self) -> Option<T>679 fn next(&mut self) -> Option<T> {
680 Some(self.rng.gen())
681 }
682 }
683
684 /// Iterator which will continuously generate random ascii characters.
685 ///
686 /// This iterator is created via the [`gen_ascii_chars`] method on [`Rng`].
687 ///
688 /// [`gen_ascii_chars`]: trait.Rng.html#method.gen_ascii_chars
689 /// [`Rng`]: trait.Rng.html
690 #[derive(Debug)]
691 pub struct AsciiGenerator<'a, R:'a> {
692 rng: &'a mut R,
693 }
694
695 impl<'a, R: Rng> Iterator for AsciiGenerator<'a, R> {
696 type Item = char;
697
next(&mut self) -> Option<char>698 fn next(&mut self) -> Option<char> {
699 const GEN_ASCII_STR_CHARSET: &'static [u8] =
700 b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
701 abcdefghijklmnopqrstuvwxyz\
702 0123456789";
703 Some(*self.rng.choose(GEN_ASCII_STR_CHARSET).unwrap() as char)
704 }
705 }
706
707 /// A random number generator that can be explicitly seeded to produce
708 /// the same stream of randomness multiple times.
709 pub trait SeedableRng<Seed>: Rng {
710 /// Reseed an RNG with the given seed.
711 ///
712 /// # Example
713 ///
714 /// ```rust
715 /// use rand::{Rng, SeedableRng, StdRng};
716 ///
717 /// let seed: &[_] = &[1, 2, 3, 4];
718 /// let mut rng: StdRng = SeedableRng::from_seed(seed);
719 /// println!("{}", rng.gen::<f64>());
720 /// rng.reseed(&[5, 6, 7, 8]);
721 /// println!("{}", rng.gen::<f64>());
722 /// ```
reseed(&mut self, Seed)723 fn reseed(&mut self, Seed);
724
725 /// Create a new RNG with the given seed.
726 ///
727 /// # Example
728 ///
729 /// ```rust
730 /// use rand::{Rng, SeedableRng, StdRng};
731 ///
732 /// let seed: &[_] = &[1, 2, 3, 4];
733 /// let mut rng: StdRng = SeedableRng::from_seed(seed);
734 /// println!("{}", rng.gen::<f64>());
735 /// ```
from_seed(seed: Seed) -> Self736 fn from_seed(seed: Seed) -> Self;
737 }
738
739 /// A wrapper for generating floating point numbers uniformly in the
740 /// open interval `(0,1)` (not including either endpoint).
741 ///
742 /// Use `Closed01` for the closed interval `[0,1]`, and the default
743 /// `Rand` implementation for `f32` and `f64` for the half-open
744 /// `[0,1)`.
745 ///
746 /// # Example
747 /// ```rust
748 /// use rand::{random, Open01};
749 ///
750 /// let Open01(val) = random::<Open01<f32>>();
751 /// println!("f32 from (0,1): {}", val);
752 /// ```
753 #[derive(Debug)]
754 pub struct Open01<F>(pub F);
755
756 /// A wrapper for generating floating point numbers uniformly in the
757 /// closed interval `[0,1]` (including both endpoints).
758 ///
759 /// Use `Open01` for the closed interval `(0,1)`, and the default
760 /// `Rand` implementation of `f32` and `f64` for the half-open
761 /// `[0,1)`.
762 ///
763 /// # Example
764 ///
765 /// ```rust
766 /// use rand::{random, Closed01};
767 ///
768 /// let Closed01(val) = random::<Closed01<f32>>();
769 /// println!("f32 from [0,1]: {}", val);
770 /// ```
771 #[derive(Debug)]
772 pub struct Closed01<F>(pub F);
773
774 /// The standard RNG. This is designed to be efficient on the current
775 /// platform.
776 #[derive(Copy, Clone, Debug)]
777 pub struct StdRng {
778 rng: IsaacWordRng,
779 }
780
781 impl StdRng {
782 /// Create a randomly seeded instance of `StdRng`.
783 ///
784 /// This is a very expensive operation as it has to read
785 /// randomness from the operating system and use this in an
786 /// expensive seeding operation. If one is only generating a small
787 /// number of random numbers, or doesn't need the utmost speed for
788 /// generating each number, `thread_rng` and/or `random` may be more
789 /// appropriate.
790 ///
791 /// Reading the randomness from the OS may fail, and any error is
792 /// propagated via the `io::Result` return value.
793 #[cfg(feature="std")]
new() -> io::Result<StdRng>794 pub fn new() -> io::Result<StdRng> {
795 match OsRng::new() {
796 Ok(mut r) => Ok(StdRng { rng: r.gen() }),
797 Err(e1) => {
798 match JitterRng::new() {
799 Ok(mut r) => Ok(StdRng { rng: r.gen() }),
800 Err(_) => {
801 Err(e1)
802 }
803 }
804 }
805 }
806 }
807 }
808
809 impl Rng for StdRng {
810 #[inline]
next_u32(&mut self) -> u32811 fn next_u32(&mut self) -> u32 {
812 self.rng.next_u32()
813 }
814
815 #[inline]
next_u64(&mut self) -> u64816 fn next_u64(&mut self) -> u64 {
817 self.rng.next_u64()
818 }
819 }
820
821 impl<'a> SeedableRng<&'a [usize]> for StdRng {
reseed(&mut self, seed: &'a [usize])822 fn reseed(&mut self, seed: &'a [usize]) {
823 // the internal RNG can just be seeded from the above
824 // randomness.
825 self.rng.reseed(unsafe {mem::transmute(seed)})
826 }
827
from_seed(seed: &'a [usize]) -> StdRng828 fn from_seed(seed: &'a [usize]) -> StdRng {
829 StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
830 }
831 }
832
833 /// Create a weak random number generator with a default algorithm and seed.
834 ///
835 /// It returns the fastest `Rng` algorithm currently available in Rust without
836 /// consideration for cryptography or security. If you require a specifically
837 /// seeded `Rng` for consistency over time you should pick one algorithm and
838 /// create the `Rng` yourself.
839 ///
840 /// This will seed the generator with randomness from thread_rng.
841 #[cfg(feature="std")]
weak_rng() -> XorShiftRng842 pub fn weak_rng() -> XorShiftRng {
843 thread_rng().gen()
844 }
845
846 /// Controls how the thread-local RNG is reseeded.
847 #[cfg(feature="std")]
848 #[derive(Debug)]
849 struct ThreadRngReseeder;
850
851 #[cfg(feature="std")]
852 impl reseeding::Reseeder<StdRng> for ThreadRngReseeder {
reseed(&mut self, rng: &mut StdRng)853 fn reseed(&mut self, rng: &mut StdRng) {
854 match StdRng::new() {
855 Ok(r) => *rng = r,
856 Err(e) => panic!("No entropy available: {}", e),
857 }
858 }
859 }
860 #[cfg(feature="std")]
861 const THREAD_RNG_RESEED_THRESHOLD: u64 = 32_768;
862 #[cfg(feature="std")]
863 type ThreadRngInner = reseeding::ReseedingRng<StdRng, ThreadRngReseeder>;
864
865 /// The thread-local RNG.
866 #[cfg(feature="std")]
867 #[derive(Clone, Debug)]
868 pub struct ThreadRng {
869 rng: Rc<RefCell<ThreadRngInner>>,
870 }
871
872 /// Retrieve the lazily-initialized thread-local random number
873 /// generator, seeded by the system. Intended to be used in method
874 /// chaining style, e.g. `thread_rng().gen::<i32>()`.
875 ///
876 /// After generating a certain amount of randomness, the RNG will reseed itself
877 /// from the operating system or, if the operating system RNG returns an error,
878 /// a seed based on the current system time.
879 ///
880 /// The internal RNG used is platform and architecture dependent, even
881 /// if the operating system random number generator is rigged to give
882 /// the same sequence always. If absolute consistency is required,
883 /// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
884 #[cfg(feature="std")]
thread_rng() -> ThreadRng885 pub fn thread_rng() -> ThreadRng {
886 // used to make space in TLS for a random number generator
887 thread_local!(static THREAD_RNG_KEY: Rc<RefCell<ThreadRngInner>> = {
888 let r = match StdRng::new() {
889 Ok(r) => r,
890 Err(e) => panic!("No entropy available: {}", e),
891 };
892 let rng = reseeding::ReseedingRng::new(r,
893 THREAD_RNG_RESEED_THRESHOLD,
894 ThreadRngReseeder);
895 Rc::new(RefCell::new(rng))
896 });
897
898 ThreadRng { rng: THREAD_RNG_KEY.with(|t| t.clone()) }
899 }
900
901 #[cfg(feature="std")]
902 impl Rng for ThreadRng {
next_u32(&mut self) -> u32903 fn next_u32(&mut self) -> u32 {
904 self.rng.borrow_mut().next_u32()
905 }
906
next_u64(&mut self) -> u64907 fn next_u64(&mut self) -> u64 {
908 self.rng.borrow_mut().next_u64()
909 }
910
911 #[inline]
fill_bytes(&mut self, bytes: &mut [u8])912 fn fill_bytes(&mut self, bytes: &mut [u8]) {
913 self.rng.borrow_mut().fill_bytes(bytes)
914 }
915 }
916
917 /// Generates a random value using the thread-local random number generator.
918 ///
919 /// `random()` can generate various types of random things, and so may require
920 /// type hinting to generate the specific type you want.
921 ///
922 /// This function uses the thread local random number generator. This means
923 /// that if you're calling `random()` in a loop, caching the generator can
924 /// increase performance. An example is shown below.
925 ///
926 /// # Examples
927 ///
928 /// ```
929 /// let x = rand::random::<u8>();
930 /// println!("{}", x);
931 ///
932 /// let y = rand::random::<f64>();
933 /// println!("{}", y);
934 ///
935 /// if rand::random() { // generates a boolean
936 /// println!("Better lucky than good!");
937 /// }
938 /// ```
939 ///
940 /// Caching the thread local random number generator:
941 ///
942 /// ```
943 /// use rand::Rng;
944 ///
945 /// let mut v = vec![1, 2, 3];
946 ///
947 /// for x in v.iter_mut() {
948 /// *x = rand::random()
949 /// }
950 ///
951 /// // can be made faster by caching thread_rng
952 ///
953 /// let mut rng = rand::thread_rng();
954 ///
955 /// for x in v.iter_mut() {
956 /// *x = rng.gen();
957 /// }
958 /// ```
959 #[cfg(feature="std")]
960 #[inline]
random<T: Rand>() -> T961 pub fn random<T: Rand>() -> T {
962 thread_rng().gen()
963 }
964
965 /// DEPRECATED: use `seq::sample_iter` instead.
966 ///
967 /// Randomly sample up to `amount` elements from a finite iterator.
968 /// The order of elements in the sample is not random.
969 ///
970 /// # Example
971 ///
972 /// ```rust
973 /// use rand::{thread_rng, sample};
974 ///
975 /// let mut rng = thread_rng();
976 /// let sample = sample(&mut rng, 1..100, 5);
977 /// println!("{:?}", sample);
978 /// ```
979 #[cfg(feature="std")]
980 #[inline(always)]
981 #[deprecated(since="0.4.0", note="renamed to seq::sample_iter")]
sample<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Vec<T> where I: IntoIterator<Item=T>, R: Rng,982 pub fn sample<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Vec<T>
983 where I: IntoIterator<Item=T>,
984 R: Rng,
985 {
986 // the legacy sample didn't care whether amount was met
987 seq::sample_iter(rng, iterable, amount)
988 .unwrap_or_else(|e| e)
989 }
990
991 #[cfg(test)]
992 mod test {
993 use super::{Rng, thread_rng, random, SeedableRng, StdRng, weak_rng};
994 use std::iter::repeat;
995
996 pub struct MyRng<R> { inner: R }
997
998 impl<R: Rng> Rng for MyRng<R> {
next_u32(&mut self) -> u32999 fn next_u32(&mut self) -> u32 {
1000 fn next<T: Rng>(t: &mut T) -> u32 {
1001 t.next_u32()
1002 }
1003 next(&mut self.inner)
1004 }
1005 }
1006
rng() -> MyRng<::ThreadRng>1007 pub fn rng() -> MyRng<::ThreadRng> {
1008 MyRng { inner: ::thread_rng() }
1009 }
1010
1011 struct ConstRng { i: u64 }
1012 impl Rng for ConstRng {
next_u32(&mut self) -> u321013 fn next_u32(&mut self) -> u32 { self.i as u32 }
next_u64(&mut self) -> u641014 fn next_u64(&mut self) -> u64 { self.i }
1015
1016 // no fill_bytes on purpose
1017 }
1018
iter_eq<I, J>(i: I, j: J) -> bool where I: IntoIterator, J: IntoIterator<Item=I::Item>, I::Item: Eq1019 pub fn iter_eq<I, J>(i: I, j: J) -> bool
1020 where I: IntoIterator,
1021 J: IntoIterator<Item=I::Item>,
1022 I::Item: Eq
1023 {
1024 // make sure the iterators have equal length
1025 let mut i = i.into_iter();
1026 let mut j = j.into_iter();
1027 loop {
1028 match (i.next(), j.next()) {
1029 (Some(ref ei), Some(ref ej)) if ei == ej => { }
1030 (None, None) => return true,
1031 _ => return false,
1032 }
1033 }
1034 }
1035
1036 #[test]
test_fill_bytes_default()1037 fn test_fill_bytes_default() {
1038 let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
1039
1040 // check every remainder mod 8, both in small and big vectors.
1041 let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
1042 80, 81, 82, 83, 84, 85, 86, 87];
1043 for &n in lengths.iter() {
1044 let mut v = repeat(0u8).take(n).collect::<Vec<_>>();
1045 r.fill_bytes(&mut v);
1046
1047 // use this to get nicer error messages.
1048 for (i, &byte) in v.iter().enumerate() {
1049 if byte == 0 {
1050 panic!("byte {} of {} is zero", i, n)
1051 }
1052 }
1053 }
1054 }
1055
1056 #[test]
test_gen_range()1057 fn test_gen_range() {
1058 let mut r = thread_rng();
1059 for _ in 0..1000 {
1060 let a = r.gen_range(-3, 42);
1061 assert!(a >= -3 && a < 42);
1062 assert_eq!(r.gen_range(0, 1), 0);
1063 assert_eq!(r.gen_range(-12, -11), -12);
1064 }
1065
1066 for _ in 0..1000 {
1067 let a = r.gen_range(10, 42);
1068 assert!(a >= 10 && a < 42);
1069 assert_eq!(r.gen_range(0, 1), 0);
1070 assert_eq!(r.gen_range(3_000_000, 3_000_001), 3_000_000);
1071 }
1072
1073 }
1074
1075 #[test]
1076 #[should_panic]
test_gen_range_panic_int()1077 fn test_gen_range_panic_int() {
1078 let mut r = thread_rng();
1079 r.gen_range(5, -2);
1080 }
1081
1082 #[test]
1083 #[should_panic]
test_gen_range_panic_usize()1084 fn test_gen_range_panic_usize() {
1085 let mut r = thread_rng();
1086 r.gen_range(5, 2);
1087 }
1088
1089 #[test]
test_gen_weighted_bool()1090 fn test_gen_weighted_bool() {
1091 let mut r = thread_rng();
1092 assert_eq!(r.gen_weighted_bool(0), true);
1093 assert_eq!(r.gen_weighted_bool(1), true);
1094 }
1095
1096 #[test]
test_gen_ascii_str()1097 fn test_gen_ascii_str() {
1098 let mut r = thread_rng();
1099 assert_eq!(r.gen_ascii_chars().take(0).count(), 0);
1100 assert_eq!(r.gen_ascii_chars().take(10).count(), 10);
1101 assert_eq!(r.gen_ascii_chars().take(16).count(), 16);
1102 }
1103
1104 #[test]
test_gen_vec()1105 fn test_gen_vec() {
1106 let mut r = thread_rng();
1107 assert_eq!(r.gen_iter::<u8>().take(0).count(), 0);
1108 assert_eq!(r.gen_iter::<u8>().take(10).count(), 10);
1109 assert_eq!(r.gen_iter::<f64>().take(16).count(), 16);
1110 }
1111
1112 #[test]
test_choose()1113 fn test_choose() {
1114 let mut r = thread_rng();
1115 assert_eq!(r.choose(&[1, 1, 1]).map(|&x|x), Some(1));
1116
1117 let v: &[isize] = &[];
1118 assert_eq!(r.choose(v), None);
1119 }
1120
1121 #[test]
test_shuffle()1122 fn test_shuffle() {
1123 let mut r = thread_rng();
1124 let empty: &mut [isize] = &mut [];
1125 r.shuffle(empty);
1126 let mut one = [1];
1127 r.shuffle(&mut one);
1128 let b: &[_] = &[1];
1129 assert_eq!(one, b);
1130
1131 let mut two = [1, 2];
1132 r.shuffle(&mut two);
1133 assert!(two == [1, 2] || two == [2, 1]);
1134
1135 let mut x = [1, 1, 1];
1136 r.shuffle(&mut x);
1137 let b: &[_] = &[1, 1, 1];
1138 assert_eq!(x, b);
1139 }
1140
1141 #[test]
test_thread_rng()1142 fn test_thread_rng() {
1143 let mut r = thread_rng();
1144 r.gen::<i32>();
1145 let mut v = [1, 1, 1];
1146 r.shuffle(&mut v);
1147 let b: &[_] = &[1, 1, 1];
1148 assert_eq!(v, b);
1149 assert_eq!(r.gen_range(0, 1), 0);
1150 }
1151
1152 #[test]
test_rng_trait_object()1153 fn test_rng_trait_object() {
1154 let mut rng = thread_rng();
1155 {
1156 let mut r = &mut rng as &mut Rng;
1157 r.next_u32();
1158 (&mut r).gen::<i32>();
1159 let mut v = [1, 1, 1];
1160 (&mut r).shuffle(&mut v);
1161 let b: &[_] = &[1, 1, 1];
1162 assert_eq!(v, b);
1163 assert_eq!((&mut r).gen_range(0, 1), 0);
1164 }
1165 {
1166 let mut r = Box::new(rng) as Box<Rng>;
1167 r.next_u32();
1168 r.gen::<i32>();
1169 let mut v = [1, 1, 1];
1170 r.shuffle(&mut v);
1171 let b: &[_] = &[1, 1, 1];
1172 assert_eq!(v, b);
1173 assert_eq!(r.gen_range(0, 1), 0);
1174 }
1175 }
1176
1177 #[test]
test_random()1178 fn test_random() {
1179 // not sure how to test this aside from just getting some values
1180 let _n : usize = random();
1181 let _f : f32 = random();
1182 let _o : Option<Option<i8>> = random();
1183 let _many : ((),
1184 (usize,
1185 isize,
1186 Option<(u32, (bool,))>),
1187 (u8, i8, u16, i16, u32, i32, u64, i64),
1188 (f32, (f64, (f64,)))) = random();
1189 }
1190
1191 #[test]
test_std_rng_seeded()1192 fn test_std_rng_seeded() {
1193 let s = thread_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>();
1194 let mut ra: StdRng = SeedableRng::from_seed(&s[..]);
1195 let mut rb: StdRng = SeedableRng::from_seed(&s[..]);
1196 assert!(iter_eq(ra.gen_ascii_chars().take(100),
1197 rb.gen_ascii_chars().take(100)));
1198 }
1199
1200 #[test]
test_std_rng_reseed()1201 fn test_std_rng_reseed() {
1202 let s = thread_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>();
1203 let mut r: StdRng = SeedableRng::from_seed(&s[..]);
1204 let string1 = r.gen_ascii_chars().take(100).collect::<String>();
1205
1206 r.reseed(&s);
1207
1208 let string2 = r.gen_ascii_chars().take(100).collect::<String>();
1209 assert_eq!(string1, string2);
1210 }
1211
1212 #[test]
test_weak_rng()1213 fn test_weak_rng() {
1214 let s = weak_rng().gen_iter::<usize>().take(256).collect::<Vec<usize>>();
1215 let mut ra: StdRng = SeedableRng::from_seed(&s[..]);
1216 let mut rb: StdRng = SeedableRng::from_seed(&s[..]);
1217 assert!(iter_eq(ra.gen_ascii_chars().take(100),
1218 rb.gen_ascii_chars().take(100)));
1219 }
1220 }
1221