Debian Codegraph @

.cargo/vendor/rand_core/src/block.rs

raw
1 // Copyright 2018 Developers of the Rand project.
2 //
3 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
6 // option. This file may not be copied, modified, or distributed
7 // except according to those terms.
8
9 //! The `BlockRngCore` trait and implementation helpers
10 //!
11 //! The [`BlockRngCore`] trait exists to assist in the implementation of RNGs
12 //! which generate a block of data in a cache instead of returning generated
13 //! values directly.
14 //!
15 //! Usage of this trait is optional, but provides two advantages:
16 //! implementations only need to concern themselves with generation of the
17 //! block, not the various [`RngCore`] methods (especially [`fill_bytes`], where
18 //! the optimal implementations are not trivial), and this allows
19 //! `ReseedingRng` (see [`rand`](https://docs.rs/rand) crate) perform periodic
20 //! reseeding with very low overhead.
21 //!
22 //! # Example
23 //!
24 //! ```no_run
25 //! use rand_core::{RngCore, SeedableRng};
26 //! use rand_core::block::{BlockRngCore, BlockRng};
27 //!
28 //! struct MyRngCore;
29 //!
30 //! impl BlockRngCore for MyRngCore {
31 //! type Item = u32;
32 //! type Results = [u32; 16];
33 //!
34 //! fn generate(&mut self, results: &mut Self::Results) {
35 //! unimplemented!()
36 //! }
37 //! }
38 //!
39 //! impl SeedableRng for MyRngCore {
40 //! type Seed = [u8; 32];
41 //! fn from_seed(seed: Self::Seed) -> Self {
42 //! unimplemented!()
43 //! }
44 //! }
45 //!
46 //! // optionally, also implement CryptoBlockRng for MyRngCore
47 //!
48 //! // Final RNG.
49 //! let mut rng = BlockRng::<MyRngCore>::seed_from_u64(0);
50 //! println!("First value: {}", rng.next_u32());
51 //! ```
52 //!
53 //! [`BlockRngCore`]: crate::block::BlockRngCore
54 //! [`fill_bytes`]: RngCore::fill_bytes
55
56 use crate::impls::fill_via_chunks;
57 use crate::{CryptoRng, RngCore, SeedableRng, TryRngCore};
58 use core::fmt;
59 #[cfg(feature = "serde")]
60 use serde::{Deserialize, Serialize};
61
62 /// A trait for RNGs which do not generate random numbers individually, but in
63 /// blocks (typically `[u32; N]`). This technique is commonly used by
64 /// cryptographic RNGs to improve performance.
65 ///
66 /// See the [module][crate::block] documentation for details.
67 pub trait BlockRngCore {
68 /// Results element type, e.g. `u32`.
69 type Item;
70
71 /// Results type. This is the 'block' an RNG implementing `BlockRngCore`
72 /// generates, which will usually be an array like `[u32; 16]`.
73 type Results: AsRef<[Self::Item]> + AsMut<[Self::Item]> + Default;
74
75 /// Generate a new block of results.
76 fn generate(&mut self, results: &mut Self::Results);
77 }
78
79 /// A marker trait used to indicate that an [`RngCore`] implementation is
80 /// supposed to be cryptographically secure.
81 ///
82 /// See [`CryptoRng`] docs for more information.
83 pub trait CryptoBlockRng: BlockRngCore {}
84
85 /// A wrapper type implementing [`RngCore`] for some type implementing
86 /// [`BlockRngCore`] with `u32` array buffer; i.e. this can be used to implement
87 /// a full RNG from just a `generate` function.
88 ///
89 /// The `core` field may be accessed directly but the results buffer may not.
90 /// PRNG implementations can simply use a type alias
91 /// (`pub type MyRng = BlockRng<MyRngCore>;`) but might prefer to use a
92 /// wrapper type (`pub struct MyRng(BlockRng<MyRngCore>);`); the latter must
93 /// re-implement `RngCore` but hides the implementation details and allows
94 /// extra functionality to be defined on the RNG
95 /// (e.g. `impl MyRng { fn set_stream(...){...} }`).
96 ///
97 /// `BlockRng` has heavily optimized implementations of the [`RngCore`] methods
98 /// reading values from the results buffer, as well as
99 /// calling [`BlockRngCore::generate`] directly on the output array when
100 /// [`fill_bytes`] is called on a large array. These methods also handle
101 /// the bookkeeping of when to generate a new batch of values.
102 ///
103 /// No whole generated `u32` values are thrown away and all values are consumed
104 /// in-order. [`next_u32`] simply takes the next available `u32` value.
105 /// [`next_u64`] is implemented by combining two `u32` values, least
106 /// significant first. [`fill_bytes`] consume a whole number of `u32` values,
107 /// converting each `u32` to a byte slice in little-endian order. If the requested byte
108 /// length is not a multiple of 4, some bytes will be discarded.
109 ///
110 /// See also [`BlockRng64`] which uses `u64` array buffers. Currently there is
111 /// no direct support for other buffer types.
112 ///
113 /// For easy initialization `BlockRng` also implements [`SeedableRng`].
114 ///
115 /// [`next_u32`]: RngCore::next_u32
116 /// [`next_u64`]: RngCore::next_u64
117 /// [`fill_bytes`]: RngCore::fill_bytes
118 #[derive(Clone)]
119 #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
120 #[cfg_attr(
121 feature = "serde",
122 serde(
123 bound = "for<'x> R: Serialize + Deserialize<'x>, for<'x> R::Results: Serialize + Deserialize<'x>"
124 )
125 )]
126 pub struct BlockRng<R: BlockRngCore> {
127 results: R::Results,
128 index: usize,
129 /// The *core* part of the RNG, implementing the `generate` function.
130 pub core: R,
131 }
132
133 // Custom Debug implementation that does not expose the contents of `results`.
134 impl<R: BlockRngCore + fmt::Debug> fmt::Debug for BlockRng<R> {
135 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
136 fmt.debug_struct("BlockRng")
137 .field("core", &self.core)
138 .field("result_len", &self.results.as_ref().len())
139 .field("index", &self.index)
140 .finish()
141 }
142 }
143
144 impl<R: BlockRngCore> BlockRng<R> {
145 /// Create a new `BlockRng` from an existing RNG implementing
146 /// `BlockRngCore`. Results will be generated on first use.
147 #[inline]
148 pub fn new(core: R) -> BlockRng<R> {
149 let results_empty = R::Results::default();
150 BlockRng {
151 core,
152 index: results_empty.as_ref().len(),
153 results: results_empty,
154 }
155 }
156
157 /// Get the index into the result buffer.
158 ///
159 /// If this is equal to or larger than the size of the result buffer then
160 /// the buffer is "empty" and `generate()` must be called to produce new
161 /// results.
162 #[inline(always)]
163 pub fn index(&self) -> usize {
164 self.index
165 }
166
167 /// Reset the number of available results.
168 /// This will force a new set of results to be generated on next use.
169 #[inline]
170 pub fn reset(&mut self) {
171 self.index = self.results.as_ref().len();
172 }
173
174 /// Generate a new set of results immediately, setting the index to the
175 /// given value.
176 #[inline]
177 pub fn generate_and_set(&mut self, index: usize) {
178 assert!(index < self.results.as_ref().len());
179 self.core.generate(&mut self.results);
180 self.index = index;
181 }
182 }
183
184 impl<R: BlockRngCore<Item = u32>> RngCore for BlockRng<R> {
185 #[inline]
186 fn next_u32(&mut self) -> u32 {
187 if self.index >= self.results.as_ref().len() {
188 self.generate_and_set(0);
189 }
190
191 let value = self.results.as_ref()[self.index];
192 self.index += 1;
193 value
194 }
195
196 #[inline]
197 fn next_u64(&mut self) -> u64 {
198 let read_u64 = |results: &[u32], index| {
199 let data = &results[index..=index + 1];
200 (u64::from(data[1]) << 32) | u64::from(data[0])
201 };
202
203 let len = self.results.as_ref().len();
204
205 let index = self.index;
206 if index < len - 1 {
207 self.index += 2;
208 // Read an u64 from the current index
209 read_u64(self.results.as_ref(), index)
210 } else if index >= len {
211 self.generate_and_set(2);
212 read_u64(self.results.as_ref(), 0)
213 } else {
214 let x = u64::from(self.results.as_ref()[len - 1]);
215 self.generate_and_set(1);
216 let y = u64::from(self.results.as_ref()[0]);
217 (y << 32) | x
218 }
219 }
220
221 #[inline]
222 fn fill_bytes(&mut self, dest: &mut [u8]) {
223 let mut read_len = 0;
224 while read_len < dest.len() {
225 if self.index >= self.results.as_ref().len() {
226 self.generate_and_set(0);
227 }
228 let (consumed_u32, filled_u8) =
229 fill_via_chunks(&self.results.as_mut()[self.index..], &mut dest[read_len..]);
230
231 self.index += consumed_u32;
232 read_len += filled_u8;
233 }
234 }
235 }
236
237 impl<R: BlockRngCore + SeedableRng> SeedableRng for BlockRng<R> {
238 type Seed = R::Seed;
239
240 #[inline(always)]
241 fn from_seed(seed: Self::Seed) -> Self {
242 Self::new(R::from_seed(seed))
243 }
244
245 #[inline(always)]
246 fn seed_from_u64(seed: u64) -> Self {
247 Self::new(R::seed_from_u64(seed))
248 }
249
250 #[inline(always)]
251 fn from_rng(rng: &mut impl RngCore) -> Self {
252 Self::new(R::from_rng(rng))
253 }
254
255 #[inline(always)]
256 fn try_from_rng<S: TryRngCore>(rng: &mut S) -> Result<Self, S::Error> {
257 R::try_from_rng(rng).map(Self::new)
258 }
259 }
260
261 impl<R: CryptoBlockRng + BlockRngCore<Item = u32>> CryptoRng for BlockRng<R> {}
262
263 /// A wrapper type implementing [`RngCore`] for some type implementing
264 /// [`BlockRngCore`] with `u64` array buffer; i.e. this can be used to implement
265 /// a full RNG from just a `generate` function.
266 ///
267 /// This is similar to [`BlockRng`], but specialized for algorithms that operate
268 /// on `u64` values.
269 ///
270 /// No whole generated `u64` values are thrown away and all values are consumed
271 /// in-order. [`next_u64`] simply takes the next available `u64` value.
272 /// [`next_u32`] is however a bit special: half of a `u64` is consumed, leaving
273 /// the other half in the buffer. If the next function called is [`next_u32`]
274 /// then the other half is then consumed, however both [`next_u64`] and
275 /// [`fill_bytes`] discard the rest of any half-consumed `u64`s when called.
276 ///
277 /// [`fill_bytes`] consumes a whole number of `u64` values. If the requested length
278 /// is not a multiple of 8, some bytes will be discarded.
279 ///
280 /// [`next_u32`]: RngCore::next_u32
281 /// [`next_u64`]: RngCore::next_u64
282 /// [`fill_bytes`]: RngCore::fill_bytes
283 #[derive(Clone)]
284 #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
285 pub struct BlockRng64<R: BlockRngCore + ?Sized> {
286 results: R::Results,
287 index: usize,
288 half_used: bool, // true if only half of the previous result is used
289 /// The *core* part of the RNG, implementing the `generate` function.
290 pub core: R,
291 }
292
293 // Custom Debug implementation that does not expose the contents of `results`.
294 impl<R: BlockRngCore + fmt::Debug> fmt::Debug for BlockRng64<R> {
295 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
296 fmt.debug_struct("BlockRng64")
297 .field("core", &self.core)
298 .field("result_len", &self.results.as_ref().len())
299 .field("index", &self.index)
300 .field("half_used", &self.half_used)
301 .finish()
302 }
303 }
304
305 impl<R: BlockRngCore> BlockRng64<R> {
306 /// Create a new `BlockRng` from an existing RNG implementing
307 /// `BlockRngCore`. Results will be generated on first use.
308 #[inline]
309 pub fn new(core: R) -> BlockRng64<R> {
310 let results_empty = R::Results::default();
311 BlockRng64 {
312 core,
313 index: results_empty.as_ref().len(),
314 half_used: false,
315 results: results_empty,
316 }
317 }
318
319 /// Get the index into the result buffer.
320 ///
321 /// If this is equal to or larger than the size of the result buffer then
322 /// the buffer is "empty" and `generate()` must be called to produce new
323 /// results.
324 #[inline(always)]
325 pub fn index(&self) -> usize {
326 self.index
327 }
328
329 /// Reset the number of available results.
330 /// This will force a new set of results to be generated on next use.
331 #[inline]
332 pub fn reset(&mut self) {
333 self.index = self.results.as_ref().len();
334 self.half_used = false;
335 }
336
337 /// Generate a new set of results immediately, setting the index to the
338 /// given value.
339 #[inline]
340 pub fn generate_and_set(&mut self, index: usize) {
341 assert!(index < self.results.as_ref().len());
342 self.core.generate(&mut self.results);
343 self.index = index;
344 self.half_used = false;
345 }
346 }
347
348 impl<R: BlockRngCore<Item = u64>> RngCore for BlockRng64<R> {
349 #[inline]
350 fn next_u32(&mut self) -> u32 {
351 let mut index = self.index - self.half_used as usize;
352 if index >= self.results.as_ref().len() {
353 self.core.generate(&mut self.results);
354 self.index = 0;
355 index = 0;
356 // `self.half_used` is by definition `false`
357 self.half_used = false;
358 }
359
360 let shift = 32 * (self.half_used as usize);
361
362 self.half_used = !self.half_used;
363 self.index += self.half_used as usize;
364
365 (self.results.as_ref()[index] >> shift) as u32
366 }
367
368 #[inline]
369 fn next_u64(&mut self) -> u64 {
370 if self.index >= self.results.as_ref().len() {
371 self.core.generate(&mut self.results);
372 self.index = 0;
373 }
374
375 let value = self.results.as_ref()[self.index];
376 self.index += 1;
377 self.half_used = false;
378 value
379 }
380
381 #[inline]
382 fn fill_bytes(&mut self, dest: &mut [u8]) {
383 let mut read_len = 0;
384 self.half_used = false;
385 while read_len < dest.len() {
386 if self.index >= self.results.as_ref().len() {
387 self.core.generate(&mut self.results);
388 self.index = 0;
389 }
390
391 let (consumed_u64, filled_u8) =
392 fill_via_chunks(&self.results.as_mut()[self.index..], &mut dest[read_len..]);
393
394 self.index += consumed_u64;
395 read_len += filled_u8;
396 }
397 }
398 }
399
400 impl<R: BlockRngCore + SeedableRng> SeedableRng for BlockRng64<R> {
401 type Seed = R::Seed;
402
403 #[inline(always)]
404 fn from_seed(seed: Self::Seed) -> Self {
405 Self::new(R::from_seed(seed))
406 }
407
408 #[inline(always)]
409 fn seed_from_u64(seed: u64) -> Self {
410 Self::new(R::seed_from_u64(seed))
411 }
412
413 #[inline(always)]
414 fn from_rng(rng: &mut impl RngCore) -> Self {
415 Self::new(R::from_rng(rng))
416 }
417
418 #[inline(always)]
419 fn try_from_rng<S: TryRngCore>(rng: &mut S) -> Result<Self, S::Error> {
420 R::try_from_rng(rng).map(Self::new)
421 }
422 }
423
424 impl<R: CryptoBlockRng + BlockRngCore<Item = u64>> CryptoRng for BlockRng64<R> {}
425
426 #[cfg(test)]
427 mod test {
428 use crate::block::{BlockRng, BlockRng64, BlockRngCore};
429 use crate::{RngCore, SeedableRng};
430
431 #[derive(Debug, Clone)]
432 struct DummyRng {
433 counter: u32,
434 }
435
436 impl BlockRngCore for DummyRng {
437 type Item = u32;
438 type Results = [u32; 16];
439
440 fn generate(&mut self, results: &mut Self::Results) {
441 for r in results {
442 *r = self.counter;
443 self.counter = self.counter.wrapping_add(3511615421);
444 }
445 }
446 }
447
448 impl SeedableRng for DummyRng {
449 type Seed = [u8; 4];
450
451 fn from_seed(seed: Self::Seed) -> Self {
452 DummyRng {
453 counter: u32::from_le_bytes(seed),
454 }
455 }
456 }
457
458 #[test]
459 fn blockrng_next_u32_vs_next_u64() {
460 let mut rng1 = BlockRng::<DummyRng>::from_seed([1, 2, 3, 4]);
461 let mut rng2 = rng1.clone();
462 let mut rng3 = rng1.clone();
463
464 let mut a = [0; 16];
465 a[..4].copy_from_slice(&rng1.next_u32().to_le_bytes());
466 a[4..12].copy_from_slice(&rng1.next_u64().to_le_bytes());
467 a[12..].copy_from_slice(&rng1.next_u32().to_le_bytes());
468
469 let mut b = [0; 16];
470 b[..4].copy_from_slice(&rng2.next_u32().to_le_bytes());
471 b[4..8].copy_from_slice(&rng2.next_u32().to_le_bytes());
472 b[8..].copy_from_slice(&rng2.next_u64().to_le_bytes());
473 assert_eq!(a, b);
474
475 let mut c = [0; 16];
476 c[..8].copy_from_slice(&rng3.next_u64().to_le_bytes());
477 c[8..12].copy_from_slice(&rng3.next_u32().to_le_bytes());
478 c[12..].copy_from_slice(&rng3.next_u32().to_le_bytes());
479 assert_eq!(a, c);
480 }
481
482 #[derive(Debug, Clone)]
483 struct DummyRng64 {
484 counter: u64,
485 }
486
487 impl BlockRngCore for DummyRng64 {
488 type Item = u64;
489 type Results = [u64; 8];
490
491 fn generate(&mut self, results: &mut Self::Results) {
492 for r in results {
493 *r = self.counter;
494 self.counter = self.counter.wrapping_add(2781463553396133981);
495 }
496 }
497 }
498
499 impl SeedableRng for DummyRng64 {
500 type Seed = [u8; 8];
501
502 fn from_seed(seed: Self::Seed) -> Self {
503 DummyRng64 {
504 counter: u64::from_le_bytes(seed),
505 }
506 }
507 }
508
509 #[test]
510 fn blockrng64_next_u32_vs_next_u64() {
511 let mut rng1 = BlockRng64::<DummyRng64>::from_seed([1, 2, 3, 4, 5, 6, 7, 8]);
512 let mut rng2 = rng1.clone();
513 let mut rng3 = rng1.clone();
514
515 let mut a = [0; 16];
516 a[..4].copy_from_slice(&rng1.next_u32().to_le_bytes());
517 a[4..12].copy_from_slice(&rng1.next_u64().to_le_bytes());
518 a[12..].copy_from_slice(&rng1.next_u32().to_le_bytes());
519
520 let mut b = [0; 16];
521 b[..4].copy_from_slice(&rng2.next_u32().to_le_bytes());
522 b[4..8].copy_from_slice(&rng2.next_u32().to_le_bytes());
523 b[8..].copy_from_slice(&rng2.next_u64().to_le_bytes());
524 assert_ne!(a, b);
525 assert_eq!(&a[..4], &b[..4]);
526 assert_eq!(&a[4..12], &b[8..]);
527
528 let mut c = [0; 16];
529 c[..8].copy_from_slice(&rng3.next_u64().to_le_bytes());
530 c[8..12].copy_from_slice(&rng3.next_u32().to_le_bytes());
531 c[12..].copy_from_slice(&rng3.next_u32().to_le_bytes());
532 assert_eq!(b, c);
533 }
534 }