rand_core/seedable_rng.rs
1use crate::{Rng, TryRng};
2
3/// A random number generator that can be explicitly seeded.
4///
5/// This trait encapsulates the low-level functionality common to all
6/// pseudo-random number generators (PRNGs, or algorithmic generators).
7///
8/// A generator implementing `SeedableRng` will usually be deterministic, but
9/// beware that portability and reproducibility of results **is not implied**.
10/// Refer to documentation of the generator, noting that generators named after
11/// a specific algorithm are usually tested for reproducibility against a
12/// reference vector, while `SmallRng` and `StdRng` specifically opt out of
13/// reproducibility guarantees.
14pub trait SeedableRng: Sized {
15 /// Seed type, which is restricted to types mutably-dereferenceable as `u8`
16 /// arrays (we recommend `[u8; N]` for some `N`).
17 ///
18 /// It is recommended to seed PRNGs with a seed of at least circa 100 bits,
19 /// which means an array of `[u8; 12]` or greater to avoid picking RNGs with
20 /// partially overlapping periods.
21 ///
22 /// For cryptographic RNG's a seed of 256 bits is recommended, `[u8; 32]`.
23 ///
24 ///
25 /// # Implementing `SeedableRng` for RNGs with large seeds
26 ///
27 /// Note that [`Default`] is not implemented for large arrays `[u8; N]` with
28 /// `N` > 32. To be able to implement the traits required by `SeedableRng`
29 /// for RNGs with such large seeds, the newtype pattern can be used:
30 ///
31 /// ```
32 /// use rand_core::SeedableRng;
33 ///
34 /// const N: usize = 64;
35 /// #[derive(Clone)]
36 /// pub struct MyRngSeed(pub [u8; N]);
37 /// # #[allow(dead_code)]
38 /// pub struct MyRng(MyRngSeed);
39 ///
40 /// impl Default for MyRngSeed {
41 /// fn default() -> MyRngSeed {
42 /// MyRngSeed([0; N])
43 /// }
44 /// }
45 ///
46 /// impl AsRef<[u8]> for MyRngSeed {
47 /// fn as_ref(&self) -> &[u8] {
48 /// &self.0
49 /// }
50 /// }
51 ///
52 /// impl AsMut<[u8]> for MyRngSeed {
53 /// fn as_mut(&mut self) -> &mut [u8] {
54 /// &mut self.0
55 /// }
56 /// }
57 ///
58 /// impl SeedableRng for MyRng {
59 /// type Seed = MyRngSeed;
60 ///
61 /// fn from_seed(seed: MyRngSeed) -> MyRng {
62 /// MyRng(seed)
63 /// }
64 /// }
65 /// ```
66 type Seed: Clone + Default + AsRef<[u8]> + AsMut<[u8]>;
67
68 /// Create a new PRNG using the given seed.
69 ///
70 /// PRNG implementations are allowed to assume that bits in the seed are
71 /// well distributed. That means usually that the number of one and zero
72 /// bits are roughly equal, and values like 0, 1 and (size - 1) are unlikely.
73 /// Note that many non-cryptographic PRNGs will show poor quality output
74 /// if this is not adhered to. If you wish to seed from simple numbers, use
75 /// `seed_from_u64` instead.
76 ///
77 /// All PRNG implementations should be reproducible unless otherwise noted:
78 /// given a fixed `seed`, the same sequence of output should be produced
79 /// on all runs, library versions and architectures (e.g. check endianness).
80 /// Any "value-breaking" changes to the generator should require bumping at
81 /// least the minor version and documentation of the change.
82 ///
83 /// It is not required that this function yield the same state as a
84 /// reference implementation of the PRNG given equivalent seed; if necessary
85 /// another constructor replicating behaviour from a reference
86 /// implementation can be added.
87 ///
88 /// PRNG implementations should make sure `from_seed` never panics. In the
89 /// case that some special values (like an all zero seed) are not viable
90 /// seeds it is preferable to map these to alternative constant value(s),
91 /// for example `0xBAD5EEDu32` or `0x0DDB1A5E5BAD5EEDu64` ("odd biases? bad
92 /// seed"). This is assuming only a small number of values must be rejected.
93 fn from_seed(seed: Self::Seed) -> Self;
94
95 /// Create a new PRNG using a `u64` seed.
96 ///
97 /// This is a convenience-wrapper around `from_seed` to allow construction
98 /// of any `SeedableRng` from a simple `u64` value. It is designed such that
99 /// low Hamming Weight numbers like 0 and 1 can be used and should still
100 /// result in good, independent seeds to the PRNG which is returned.
101 ///
102 /// This **is not suitable for cryptography**, as should be clear given that
103 /// the input size is only 64 bits.
104 ///
105 /// Implementations for PRNGs *may* provide their own implementations of
106 /// this function, but the default implementation should be good enough for
107 /// all purposes. *Changing* the implementation of this function should be
108 /// considered a value-breaking change.
109 fn seed_from_u64(mut state: u64) -> Self {
110 let mut seed = Self::Seed::default();
111 let mut iter = seed.as_mut().chunks_exact_mut(4);
112 for chunk in &mut iter {
113 chunk.copy_from_slice(&pcg32(&mut state));
114 }
115 let rem = iter.into_remainder();
116 if !rem.is_empty() {
117 rem.copy_from_slice(&pcg32(&mut state)[..rem.len()]);
118 }
119
120 Self::from_seed(seed)
121 }
122
123 /// Create a new PRNG seeded from an infallible `Rng`.
124 ///
125 /// This may be useful when needing to rapidly seed many PRNGs from a master
126 /// PRNG, and to allow forking of PRNGs. It may be considered deterministic.
127 ///
128 /// The master PRNG should be at least as high quality as the child PRNGs.
129 /// When seeding non-cryptographic child PRNGs, we recommend using a
130 /// different algorithm for the master PRNG (ideally a CSPRNG) to avoid
131 /// correlations between the child PRNGs. If this is not possible (e.g.
132 /// forking using small non-crypto PRNGs) ensure that your PRNG has a good
133 /// mixing function on the output or consider use of a hash function with
134 /// `from_seed`.
135 ///
136 /// Note that seeding `XorShiftRng` from another `XorShiftRng` provides an
137 /// extreme example of what can go wrong: the new PRNG will be a clone
138 /// of the parent.
139 ///
140 /// PRNG implementations are allowed to assume that a good RNG is provided
141 /// for seeding, and that it is cryptographically secure when appropriate.
142 /// As of `rand` 0.7 / `rand_core` 0.5, implementations overriding this
143 /// method should ensure the implementation satisfies reproducibility
144 /// (in prior versions this was not required).
145 ///
146 /// [`rand`]: https://docs.rs/rand
147 fn from_rng<R: Rng + ?Sized>(rng: &mut R) -> Self {
148 let mut seed = Self::Seed::default();
149 rng.fill_bytes(seed.as_mut());
150 Self::from_seed(seed)
151 }
152
153 /// Create a new PRNG seeded from a potentially fallible `Rng`.
154 ///
155 /// See [`from_rng`][SeedableRng::from_rng] docs for more information.
156 fn try_from_rng<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
157 let mut seed = Self::Seed::default();
158 rng.try_fill_bytes(seed.as_mut())?;
159 Ok(Self::from_seed(seed))
160 }
161
162 /// Fork this PRNG
163 ///
164 /// This creates a new PRNG from the current one by initializing a new one and
165 /// seeding it from the current one.
166 ///
167 /// This is useful when initializing a PRNG for a thread
168 fn fork(&mut self) -> Self
169 where
170 Self: Rng,
171 {
172 Self::from_rng(self)
173 }
174
175 /// Fork this PRNG
176 ///
177 /// This creates a new PRNG from the current one by initializing a new one and
178 /// seeding it from the current one.
179 ///
180 /// This is useful when initializing a PRNG for a thread.
181 ///
182 /// This is the failable equivalent to [`SeedableRng::fork`]
183 fn try_fork(&mut self) -> Result<Self, Self::Error>
184 where
185 Self: TryRng,
186 {
187 Self::try_from_rng(self)
188 }
189}
190
191/// PCG32 generator function
192fn pcg32(state: &mut u64) -> [u8; 4] {
193 const MUL: u64 = 0x5851_F42D_4C95_7F2D;
194 const INC: u64 = 0xA176_54E4_6FBE_17F3;
195
196 // We advance the state first (to get away from the input value,
197 // in case it has low Hamming Weight).
198 *state = state.wrapping_mul(MUL).wrapping_add(INC);
199 let state = *state;
200
201 // Use PCG output function with to_le to generate x:
202 let xorshifted = (((state >> 18) ^ state) >> 27) as u32;
203 let rot = (state >> 59) as u32;
204 let x = xorshifted.rotate_right(rot);
205 x.to_le_bytes()
206}