]> git.proxmox.com Git - rustc.git/blob - src/librand/lib.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librand / lib.rs
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"]
21 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
22 html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
23 html_root_url = "https://doc.rust-lang.org/nightly/",
24 html_playground_url = "https://play.rust-lang.org/",
25 test(attr(deny(warnings))))]
26 #![cfg_attr(not(stage0), deny(warnings))]
27 #![no_std]
28 #![unstable(feature = "rand",
29 reason = "use `rand` from crates.io",
30 issue = "27703")]
31 #![feature(core_float)]
32 #![feature(core_intrinsics)]
33 #![feature(staged_api)]
34 #![feature(step_by)]
35 #![feature(custom_attribute)]
36 #![allow(unused_attributes)]
37
38 #![cfg_attr(test, feature(test, rand))]
39
40 #![allow(deprecated)]
41
42 #[cfg(test)]
43 #[macro_use]
44 extern crate std;
45
46 use core::f64;
47 use core::intrinsics;
48 use core::marker::PhantomData;
49
50 pub use isaac::{IsaacRng, Isaac64Rng};
51 pub use chacha::ChaChaRng;
52
53 use distributions::{Range, IndependentSample};
54 use distributions::range::SampleRange;
55
56 #[cfg(test)]
57 const RAND_BENCH_N: u64 = 100;
58
59 pub mod distributions;
60 pub mod isaac;
61 pub mod chacha;
62 pub mod reseeding;
63 mod rand_impls;
64
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.
69 #[doc(hidden)]
70 trait FloatMath : Sized {
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
103 /// A type that can be randomly generated using an `Rng`.
104 #[doc(hidden)]
105 pub trait Rand : Sized {
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.
112 pub trait Rng : Sized {
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 {
141 const MANTISSA_BITS: usize = 24;
142 const IGNORED_BITS: usize = 8;
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 {
163 const MANTISSA_BITS: usize = 53;
164 const IGNORED_BITS: usize = 11;
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).
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.
194 let mut count = 0;
195 let mut num = 0;
196 for byte in dest {
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.
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.
219 fn gen_iter<'a, T: Rand>(&'a mut self) -> Generator<'a, T, Self> {
220 Generator {
221 rng: self,
222 _marker: PhantomData,
223 }
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`.
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
243 fn gen_weighted_bool(&mut self, n: usize) -> bool {
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.
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.
255 fn choose<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
256 if values.is_empty() {
257 None
258 } else {
259 Some(&values[self.gen_range(0, values.len())])
260 }
261 }
262
263 /// Shuffle a mutable slice in place.
264 fn shuffle<T>(&mut self, values: &mut [T]) {
265 let mut i = values.len();
266 while i >= 2 {
267 // invariant: elements with index >= i have been locked in place.
268 i -= 1;
269 // lock element i in place.
270 values.swap(i, self.gen_range(0, i + 1));
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`.
278 pub struct Generator<'a, T, R: 'a> {
279 rng: &'a mut R,
280 _marker: PhantomData<T>,
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`.
294 pub struct AsciiGenerator<'a, R: 'a> {
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> {
302 const GEN_ASCII_STR_CHARSET: &'static [u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
303 abcdefghijklmnopqrstuvwxyz\
304 0123456789";
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.
313 fn reseed(&mut self, Seed);
314
315 /// Create a new RNG with the given seed.
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).
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],
389 w: seed[3],
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;
401 XorShiftRng {
402 x: x,
403 y: y,
404 z: z,
405 w: w,
406 }
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)`.
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)`.
424 pub struct Closed01<F>(pub F);
425
426 #[cfg(test)]
427 mod test {
428 use std::__rand as rand;
429
430 pub struct MyRng<R> {
431 inner: R,
432 }
433
434 impl<R: rand::Rng> ::Rng for MyRng<R> {
435 fn next_u32(&mut self) -> u32 {
436 rand::Rng::next_u32(&mut self.inner)
437 }
438 }
439
440 pub fn rng() -> MyRng<rand::ThreadRng> {
441 MyRng { inner: rand::thread_rng() }
442 }
443
444 pub fn weak_rng() -> MyRng<rand::ThreadRng> {
445 MyRng { inner: rand::thread_rng() }
446 }
447 }