]>
git.proxmox.com Git - rustc.git/blob - vendor/rand_core-0.4.0/src/lib.rs
1 // Copyright 2018 Developers of the Rand project.
2 // Copyright 2017-2018 The Rust Project Developers.
4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
7 // option. This file may not be copied, modified, or distributed
8 // except according to those terms.
10 //! Random number generation traits
12 //! This crate is mainly of interest to crates publishing implementations of
13 //! [`RngCore`]. Other users are encouraged to use the [`rand`] crate instead
14 //! which re-exports the main traits and error types.
16 //! [`RngCore`] is the core trait implemented by algorithmic pseudo-random number
17 //! generators and external random-number sources.
19 //! [`SeedableRng`] is an extension trait for construction from fixed seeds and
20 //! other random number generators.
22 //! [`Error`] is provided for error-handling. It is safe to use in `no_std`
25 //! The [`impls`] and [`le`] sub-modules include a few small functions to assist
26 //! implementation of [`RngCore`].
28 //! [`rand`]: https://docs.rs/rand
30 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
31 html_favicon_url
= "https://www.rust-lang.org/favicon.ico",
32 html_root_url
= "https://rust-random.github.io/rand/")]
34 #![deny(missing_docs)]
35 #![deny(missing_debug_implementations)]
36 #![doc(test(attr(allow(unused_variables), deny(warnings))))]
38 #![cfg_attr(not(feature="std"), no_std)]
39 #![cfg_attr(all(feature="alloc", not(feature="std")), feature(alloc))]
41 #[cfg(feature="std")] extern crate core;
42 #[cfg(all(feature = "alloc", not(feature="std")))] extern crate alloc;
43 #[cfg(feature="serde1")] extern crate serde;
44 #[cfg(feature="serde1")] #[macro_use] extern crate serde_derive;
47 use core
::default::Default
;
48 use core
::convert
::AsMut
;
49 use core
::ptr
::copy_nonoverlapping
;
51 #[cfg(all(feature="alloc", not(feature="std")))] use alloc::boxed::Box;
53 pub use error
::{ErrorKind, Error}
;
62 /// The core of a random number generator.
64 /// This trait encapsulates the low-level functionality common to all
65 /// generators, and is the "back end", to be implemented by generators.
66 /// End users should normally use the `Rng` trait from the [`rand`] crate,
67 /// which is automatically implemented for every type implementing `RngCore`.
69 /// Three different methods for generating random data are provided since the
70 /// optimal implementation of each is dependent on the type of generator. There
71 /// is no required relationship between the output of each; e.g. many
72 /// implementations of [`fill_bytes`] consume a whole number of `u32` or `u64`
73 /// values and drop any remaining unused bytes.
75 /// The [`try_fill_bytes`] method is a variant of [`fill_bytes`] allowing error
76 /// handling; it is not deemed sufficiently useful to add equivalents for
77 /// [`next_u32`] or [`next_u64`] since the latter methods are almost always used
78 /// with algorithmic generators (PRNGs), which are normally infallible.
80 /// Algorithmic generators implementing [`SeedableRng`] should normally have
81 /// *portable, reproducible* output, i.e. fix Endianness when converting values
82 /// to avoid platform differences, and avoid making any changes which affect
83 /// output (except by communicating that the release has breaking changes).
85 /// Typically implementators will implement only one of the methods available
86 /// in this trait directly, then use the helper functions from the
87 /// [`impls`] module to implement the other methods.
89 /// It is recommended that implementations also implement:
91 /// - `Debug` with a custom implementation which *does not* print any internal
92 /// state (at least, [`CryptoRng`]s should not risk leaking state through
94 /// - `Serialize` and `Deserialize` (from Serde), preferably making Serde
95 /// support optional at the crate level in PRNG libs.
96 /// - `Clone`, if possible.
97 /// - *never* implement `Copy` (accidental copies may cause repeated values).
98 /// - *do not* implement `Default` for pseudorandom generators, but instead
99 /// implement [`SeedableRng`], to guide users towards proper seeding.
100 /// External / hardware RNGs can choose to implement `Default`.
101 /// - `Eq` and `PartialEq` could be implemented, but are probably not useful.
105 /// A simple example, obviously not generating very *random* output:
108 /// #![allow(dead_code)]
109 /// use rand_core::{RngCore, Error, impls};
111 /// struct CountingRng(u64);
113 /// impl RngCore for CountingRng {
114 /// fn next_u32(&mut self) -> u32 {
115 /// self.next_u64() as u32
118 /// fn next_u64(&mut self) -> u64 {
123 /// fn fill_bytes(&mut self, dest: &mut [u8]) {
124 /// impls::fill_bytes_via_next(self, dest)
127 /// fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
128 /// Ok(self.fill_bytes(dest))
133 /// [`rand`]: https://docs.rs/rand
134 /// [`try_fill_bytes`]: RngCore::try_fill_bytes
135 /// [`fill_bytes`]: RngCore::fill_bytes
136 /// [`next_u32`]: RngCore::next_u32
137 /// [`next_u64`]: RngCore::next_u64
139 /// Return the next random `u32`.
141 /// RNGs must implement at least one method from this trait directly. In
142 /// the case this method is not implemented directly, it can be implemented
143 /// using `self.next_u64() as u32` or via
144 /// [`fill_bytes`][impls::next_u32_via_fill].
145 fn next_u32(&mut self) -> u32;
147 /// Return the next random `u64`.
149 /// RNGs must implement at least one method from this trait directly. In
150 /// the case this method is not implemented directly, it can be implemented
151 /// via [`next_u32`][impls::next_u64_via_u32] or via
152 /// [`fill_bytes`][impls::next_u64_via_fill].
153 fn next_u64(&mut self) -> u64;
155 /// Fill `dest` with random data.
157 /// RNGs must implement at least one method from this trait directly. In
158 /// the case this method is not implemented directly, it can be implemented
159 /// via [`next_u*`][impls::fill_bytes_via_next] or
160 /// via [`try_fill_bytes`][RngCore::try_fill_bytes]; if this generator can
161 /// fail the implementation must choose how best to handle errors here
162 /// (e.g. panic with a descriptive message or log a warning and retry a few
165 /// This method should guarantee that `dest` is entirely filled
166 /// with new data, and may panic if this is impossible
167 /// (e.g. reading past the end of a file that is being used as the
168 /// source of randomness).
169 fn fill_bytes(&mut self, dest
: &mut [u8]);
171 /// Fill `dest` entirely with random data.
173 /// This is the only method which allows an RNG to report errors while
174 /// generating random data thus making this the primary method implemented
175 /// by external (true) RNGs (e.g. `OsRng`) which can fail. It may be used
176 /// directly to generate keys and to seed (infallible) PRNGs.
178 /// Other than error handling, this method is identical to [`fill_bytes`];
179 /// thus this may be implemented using `Ok(self.fill_bytes(dest))` or
180 /// `fill_bytes` may be implemented with
181 /// `self.try_fill_bytes(dest).unwrap()` or more specific error handling.
183 /// [`fill_bytes`]: RngCore::fill_bytes
184 fn try_fill_bytes(&mut self, dest
: &mut [u8]) -> Result
<(), Error
>;
187 /// A marker trait used to indicate that an [`RngCore`] or [`BlockRngCore`]
188 /// implementation is supposed to be cryptographically secure.
190 /// *Cryptographically secure generators*, also known as *CSPRNGs*, should
191 /// satisfy an additional properties over other generators: given the first
192 /// *k* bits of an algorithm's output
193 /// sequence, it should not be possible using polynomial-time algorithms to
194 /// predict the next bit with probability significantly greater than 50%.
196 /// Some generators may satisfy an additional property, however this is not
197 /// required by this trait: if the CSPRNG's state is revealed, it should not be
198 /// computationally-feasible to reconstruct output prior to this. Some other
199 /// generators allow backwards-computation and are consided *reversible*.
201 /// Note that this trait is provided for guidance only and cannot guarantee
202 /// suitability for cryptographic applications. In general it should only be
203 /// implemented for well-reviewed code implementing well-regarded algorithms.
205 /// Note also that use of a `CryptoRng` does not protect against other
206 /// weaknesses such as seeding from a weak entropy source or leaking state.
208 /// [`BlockRngCore`]: block::BlockRngCore
209 pub trait CryptoRng {}
211 /// A random number generator that can be explicitly seeded.
213 /// This trait encapsulates the low-level functionality common to all
214 /// pseudo-random number generators (PRNGs, or algorithmic generators).
216 /// The `FromEntropy` trait from the [`rand`] crate is automatically
217 /// implemented for every type implementing `SeedableRng`, providing
218 /// a convenient `from_entropy()` constructor.
220 /// [`rand`]: https://docs.rs/rand
221 pub trait SeedableRng
: Sized
{
222 /// Seed type, which is restricted to types mutably-dereferencable as `u8`
223 /// arrays (we recommend `[u8; N]` for some `N`).
225 /// It is recommended to seed PRNGs with a seed of at least circa 100 bits,
226 /// which means an array of `[u8; 12]` or greater to avoid picking RNGs with
227 /// partially overlapping periods.
229 /// For cryptographic RNG's a seed of 256 bits is recommended, `[u8; 32]`.
232 /// # Implementing `SeedableRng` for RNGs with large seeds
234 /// Note that the required traits `core::default::Default` and
235 /// `core::convert::AsMut<u8>` are not implemented for large arrays
236 /// `[u8; N]` with `N` > 32. To be able to implement the traits required by
237 /// `SeedableRng` for RNGs with such large seeds, the newtype pattern can be
241 /// use rand_core::SeedableRng;
243 /// const N: usize = 64;
244 /// pub struct MyRngSeed(pub [u8; N]);
245 /// pub struct MyRng(MyRngSeed);
247 /// impl Default for MyRngSeed {
248 /// fn default() -> MyRngSeed {
249 /// MyRngSeed([0; N])
253 /// impl AsMut<[u8]> for MyRngSeed {
254 /// fn as_mut(&mut self) -> &mut [u8] {
259 /// impl SeedableRng for MyRng {
260 /// type Seed = MyRngSeed;
262 /// fn from_seed(seed: MyRngSeed) -> MyRng {
267 type Seed
: Sized
+ Default
+ AsMut
<[u8]>;
269 /// Create a new PRNG using the given seed.
271 /// PRNG implementations are allowed to assume that bits in the seed are
272 /// well distributed. That means usually that the number of one and zero
273 /// bits are about equal, and values like 0, 1 and (size - 1) are unlikely.
275 /// PRNG implementations are recommended to be reproducible. A PRNG seeded
276 /// using this function with a fixed seed should produce the same sequence
277 /// of output in the future and on different architectures (with for example
278 /// different endianness).
280 /// It is however not required that this function yield the same state as a
281 /// reference implementation of the PRNG given equivalent seed; if necessary
282 /// another constructor replicating behaviour from a reference
283 /// implementation can be added.
285 /// PRNG implementations should make sure `from_seed` never panics. In the
286 /// case that some special values (like an all zero seed) are not viable
287 /// seeds it is preferable to map these to alternative constant value(s),
288 /// for example `0xBAD5EEDu32` or `0x0DDB1A5E5BAD5EEDu64` ("odd biases? bad
289 /// seed"). This is assuming only a small number of values must be rejected.
290 fn from_seed(seed
: Self::Seed
) -> Self;
292 /// Create a new PRNG using a `u64` seed.
294 /// This is a convenience-wrapper around `from_seed` to allow construction
295 /// of any `SeedableRng` from a simple `u64` value. It is designed such that
296 /// low Hamming Weight numbers like 0 and 1 can be used and should still
297 /// result in good, independent seeds to the PRNG which is returned.
299 /// This **is not suitable for cryptography**, as should be clear given that
300 /// the input size is only 64 bits.
302 /// Implementations for PRNGs *may* provide their own implementations of
303 /// this function, but the default implementation should be good enough for
304 /// all purposes. *Changing* the implementation of this function should be
305 /// considered a value-breaking change.
306 fn seed_from_u64(mut state
: u64) -> Self {
307 // We use PCG32 to generate a u32 sequence, and copy to the seed
308 const MUL
: u64 = 6364136223846793005;
309 const INC
: u64 = 11634580027462260723;
311 let mut seed
= Self::Seed
::default();
312 for chunk
in seed
.as_mut().chunks_mut(4) {
313 // We advance the state first (to get away from the input value,
314 // in case it has low Hamming Weight).
315 state
= state
.wrapping_mul(MUL
).wrapping_add(INC
);
317 // Use PCG output function with to_le to generate x:
318 let xorshifted
= (((state
>> 18) ^ state
) >> 27) as u32;
319 let rot
= (state
>> 59) as u32;
320 let x
= xorshifted
.rotate_right(rot
).to_le();
323 let p
= &x
as *const u32 as *const u8;
324 copy_nonoverlapping(p
, chunk
.as_mut_ptr(), chunk
.len());
328 Self::from_seed(seed
)
331 /// Create a new PRNG seeded from another `Rng`.
333 /// This is the recommended way to initialize PRNGs with fresh entropy. The
334 /// `FromEntropy` trait from the [`rand`] crate provides a convenient
335 /// `from_entropy` method based on `from_rng`.
337 /// Usage of this method is not recommended when reproducibility is required
338 /// since implementing PRNGs are not required to fix Endianness and are
339 /// allowed to modify implementations in new releases.
341 /// It is important to use a good source of randomness to initialize the
342 /// PRNG. Cryptographic PRNG may be rendered insecure when seeded from a
343 /// non-cryptographic PRNG or with insufficient entropy.
344 /// Many non-cryptographic PRNGs will show statistical bias in their first
345 /// results if their seed numbers are small or if there is a simple pattern
348 /// Prefer to seed from a strong external entropy source like `OsRng` from
349 /// the [`rand_os`] crate or from a cryptographic PRNG; if creating a new
350 /// generator for cryptographic uses you *must* seed from a strong source.
352 /// Seeding a small PRNG from another small PRNG is possible, but
353 /// something to be careful with. An extreme example of how this can go
354 /// wrong is seeding an Xorshift RNG from another Xorshift RNG, which
355 /// will effectively clone the generator. In general seeding from a
356 /// generator which is hard to predict is probably okay.
358 /// PRNG implementations are allowed to assume that a good RNG is provided
359 /// for seeding, and that it is cryptographically secure when appropriate.
361 /// [`rand`]: https://docs.rs/rand
362 /// [`rand_os`]: https://docs.rs/rand_os
363 fn from_rng
<R
: RngCore
>(mut rng
: R
) -> Result
<Self, Error
> {
364 let mut seed
= Self::Seed
::default();
365 rng
.try_fill_bytes(seed
.as_mut())?
;
366 Ok(Self::from_seed(seed
))
370 // Implement `RngCore` for references to an `RngCore`.
371 // Force inlining all functions, so that it is up to the `RngCore`
372 // implementation and the optimizer to decide on inlining.
373 impl<'a
, R
: RngCore
+ ?Sized
> RngCore
for &'a
mut R
{
375 fn next_u32(&mut self) -> u32 {
380 fn next_u64(&mut self) -> u64 {
385 fn fill_bytes(&mut self, dest
: &mut [u8]) {
386 (**self).fill_bytes(dest
)
390 fn try_fill_bytes(&mut self, dest
: &mut [u8]) -> Result
<(), Error
> {
391 (**self).try_fill_bytes(dest
)
395 // Implement `RngCore` for boxed references to an `RngCore`.
396 // Force inlining all functions, so that it is up to the `RngCore`
397 // implementation and the optimizer to decide on inlining.
398 #[cfg(feature="alloc")]
399 impl<R
: RngCore
+ ?Sized
> RngCore
for Box
<R
> {
401 fn next_u32(&mut self) -> u32 {
406 fn next_u64(&mut self) -> u64 {
411 fn fill_bytes(&mut self, dest
: &mut [u8]) {
412 (**self).fill_bytes(dest
)
416 fn try_fill_bytes(&mut self, dest
: &mut [u8]) -> Result
<(), Error
> {
417 (**self).try_fill_bytes(dest
)
421 #[cfg(feature="std")]
422 impl std
::io
::Read
for RngCore
{
423 fn read(&mut self, buf
: &mut [u8]) -> Result
<usize, std
::io
::Error
> {
424 self.try_fill_bytes(buf
)?
;
429 // Implement `CryptoRng` for references to an `CryptoRng`.
430 impl<'a
, R
: CryptoRng
+ ?Sized
> CryptoRng
for &'a
mut R {}
432 // Implement `CryptoRng` for boxed references to an `CryptoRng`.
433 #[cfg(feature="alloc")]
434 impl<R
: CryptoRng
+ ?Sized
> CryptoRng
for Box
<R
> {}
441 fn test_seed_from_u64() {
442 struct SeedableNum(u64);
443 impl SeedableRng
for SeedableNum
{
445 fn from_seed(seed
: Self::Seed
) -> Self {
446 let mut x
= [0u64; 1];
447 le
::read_u64_into(&seed
, &mut x
);
453 const SEEDS
: [u64; N
] = [0u64, 1, 2, 3, 4, 8, 16, -1i64 as u64];
454 let mut results
= [0u64; N
];
455 for (i
, seed
) in SEEDS
.iter().enumerate() {
456 let SeedableNum(x
) = SeedableNum
::seed_from_u64(*seed
);
460 for (i1
, r1
) in results
.iter().enumerate() {
461 let weight
= r1
.count_ones();
462 // This is the binomial distribution B(64, 0.5), so chance of
463 // weight < 20 is binocdf(19, 64, 0.5) = 7.8e-4, and same for
465 assert
!(weight
>= 20 && weight
<= 44);
467 for (i2
, r2
) in results
.iter().enumerate() {
468 if i1
== i2 { continue; }
469 let diff_weight
= (r1 ^ r2
).count_ones();
470 assert
!(diff_weight
>= 20);
474 // value-breakage test:
475 assert_eq
!(results
[0], 5029875928683246316);