vendor/rand_core/src/block.rs

   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 CryptoRng 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_u32_chunks, fill_via_u64_chunks};
  57 use crate::{CryptoRng, Error, RngCore, SeedableRng};
  58 use core::convert::AsRef;
  59 use core::fmt;
  60 #[cfg(feature = "serde1")]
  61 use serde::{Deserialize, Serialize};
  62
  63 /// A trait for RNGs which do not generate random numbers individually, but in
  64 /// blocks (typically `[u32; N]`). This technique is commonly used by
  65 /// cryptographic RNGs to improve performance.
  66 ///
  67 /// See the [module][crate::block] documentation for details.
  68 pub trait BlockRngCore {
  69     /// Results element type, e.g. `u32`.
  70     type Item;
  71
  72     /// Results type. This is the 'block' an RNG implementing `BlockRngCore`
  73     /// generates, which will usually be an array like `[u32; 16]`.
  74     type Results: AsRef<[Self::Item]> + AsMut<[Self::Item]> + Default;
  75
  76     /// Generate a new block of results.
  77     fn generate(&mut self, results: &mut Self::Results);
  78 }
  79
  80 /// A wrapper type implementing [`RngCore`] for some type implementing
  81 /// [`BlockRngCore`] with `u32` array buffer; i.e. this can be used to implement
  82 /// a full RNG from just a `generate` function.
  83 ///
  84 /// The `core` field may be accessed directly but the results buffer may not.
  85 /// PRNG implementations can simply use a type alias
  86 /// (`pub type MyRng = BlockRng<MyRngCore>;`) but might prefer to use a
  87 /// wrapper type (`pub struct MyRng(BlockRng<MyRngCore>);`); the latter must
  88 /// re-implement `RngCore` but hides the implementation details and allows
  89 /// extra functionality to be defined on the RNG
  90 /// (e.g. `impl MyRng { fn set_stream(...){...} }`).
  91 ///
  92 /// `BlockRng` has heavily optimized implementations of the [`RngCore`] methods
  93 /// reading values from the results buffer, as well as
  94 /// calling [`BlockRngCore::generate`] directly on the output array when
  95 /// [`fill_bytes`] / [`try_fill_bytes`] is called on a large array. These methods
  96 /// also handle the bookkeeping of when to generate a new batch of values.
  97 ///
  98 /// No whole generated `u32` values are thown away and all values are consumed
  99 /// in-order. [`next_u32`] simply takes the next available `u32` value.
 100 /// [`next_u64`] is implemented by combining two `u32` values, least
 101 /// significant first. [`fill_bytes`] and [`try_fill_bytes`] consume a whole
 102 /// number of `u32` values, converting each `u32` to a byte slice in
 103 /// little-endian order. If the requested byte length is not a multiple of 4,
 104 /// some bytes will be discarded.
 105 ///
 106 /// See also [`BlockRng64`] which uses `u64` array buffers. Currently there is
 107 /// no direct support for other buffer types.
 108 ///
 109 /// For easy initialization `BlockRng` also implements [`SeedableRng`].
 110 ///
 111 /// [`next_u32`]: RngCore::next_u32
 112 /// [`next_u64`]: RngCore::next_u64
 113 /// [`fill_bytes`]: RngCore::fill_bytes
 114 /// [`try_fill_bytes`]: RngCore::try_fill_bytes
 115 #[derive(Clone)]
 116 #[cfg_attr(feature = "serde1", derive(Serialize, Deserialize))]
 117 pub struct BlockRng<R: BlockRngCore + ?Sized> {
 118     results: R::Results,
 119     index: usize,
 120     /// The *core* part of the RNG, implementing the `generate` function.
 121     pub core: R,
 122 }
 123
 124 // Custom Debug implementation that does not expose the contents of `results`.
 125 impl<R: BlockRngCore + fmt::Debug> fmt::Debug for BlockRng<R> {
 126     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 127         fmt.debug_struct("BlockRng")
 128             .field("core", &self.core)
 129             .field("result_len", &self.results.as_ref().len())
 130             .field("index", &self.index)
 131             .finish()
 132     }
 133 }
 134
 135 impl<R: BlockRngCore> BlockRng<R> {
 136     /// Create a new `BlockRng` from an existing RNG implementing
 137     /// `BlockRngCore`. Results will be generated on first use.
 138     #[inline]
 139     pub fn new(core: R) -> BlockRng<R> {
 140         let results_empty = R::Results::default();
 141         BlockRng {
 142             core,
 143             index: results_empty.as_ref().len(),
 144             results: results_empty,
 145         }
 146     }
 147
 148     /// Get the index into the result buffer.
 149     ///
 150     /// If this is equal to or larger than the size of the result buffer then
 151     /// the buffer is "empty" and `generate()` must be called to produce new
 152     /// results.
 153     #[inline(always)]
 154     pub fn index(&self) -> usize {
 155         self.index
 156     }
 157
 158     /// Reset the number of available results.
 159     /// This will force a new set of results to be generated on next use.
 160     #[inline]
 161     pub fn reset(&mut self) {
 162         self.index = self.results.as_ref().len();
 163     }
 164
 165     /// Generate a new set of results immediately, setting the index to the
 166     /// given value.
 167     #[inline]
 168     pub fn generate_and_set(&mut self, index: usize) {
 169         assert!(index < self.results.as_ref().len());
 170         self.core.generate(&mut self.results);
 171         self.index = index;
 172     }
 173 }
 174
 175 impl<R: BlockRngCore<Item = u32>> RngCore for BlockRng<R>
 176 where
 177     <R as BlockRngCore>::Results: AsRef<[u32]> + AsMut<[u32]>,
 178 {
 179     #[inline]
 180     fn next_u32(&mut self) -> u32 {
 181         if self.index >= self.results.as_ref().len() {
 182             self.generate_and_set(0);
 183         }
 184
 185         let value = self.results.as_ref()[self.index];
 186         self.index += 1;
 187         value
 188     }
 189
 190     #[inline]
 191     fn next_u64(&mut self) -> u64 {
 192         let read_u64 = |results: &[u32], index| {
 193             let data = &results[index..=index + 1];
 194             u64::from(data[1]) << 32 | u64::from(data[0])
 195         };
 196
 197         let len = self.results.as_ref().len();
 198
 199         let index = self.index;
 200         if index < len - 1 {
 201             self.index += 2;
 202             // Read an u64 from the current index
 203             read_u64(self.results.as_ref(), index)
 204         } else if index >= len {
 205             self.generate_and_set(2);
 206             read_u64(self.results.as_ref(), 0)
 207         } else {
 208             let x = u64::from(self.results.as_ref()[len - 1]);
 209             self.generate_and_set(1);
 210             let y = u64::from(self.results.as_ref()[0]);
 211             (y << 32) | x
 212         }
 213     }
 214
 215     #[inline]
 216     fn fill_bytes(&mut self, dest: &mut [u8]) {
 217         let mut read_len = 0;
 218         while read_len < dest.len() {
 219             if self.index >= self.results.as_ref().len() {
 220                 self.generate_and_set(0);
 221             }
 222             let (consumed_u32, filled_u8) =
 223                 fill_via_u32_chunks(&self.results.as_ref()[self.index..], &mut dest[read_len..]);
 224
 225             self.index += consumed_u32;
 226             read_len += filled_u8;
 227         }
 228     }
 229
 230     #[inline(always)]
 231     fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
 232         self.fill_bytes(dest);
 233         Ok(())
 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<S: RngCore>(rng: S) -> Result<Self, Error> {
 252         Ok(Self::new(R::from_rng(rng)?))
 253     }
 254 }
 255
 256 /// A wrapper type implementing [`RngCore`] for some type implementing
 257 /// [`BlockRngCore`] with `u64` array buffer; i.e. this can be used to implement
 258 /// a full RNG from just a `generate` function.
 259 ///
 260 /// This is similar to [`BlockRng`], but specialized for algorithms that operate
 261 /// on `u64` values.
 262 ///
 263 /// No whole generated `u64` values are thrown away and all values are consumed
 264 /// in-order. [`next_u64`] simply takes the next available `u64` value.
 265 /// [`next_u32`] is however a bit special: half of a `u64` is consumed, leaving
 266 /// the other half in the buffer. If the next function called is [`next_u32`]
 267 /// then the other half is then consumed, however both [`next_u64`] and
 268 /// [`fill_bytes`] discard the rest of any half-consumed `u64`s when called.
 269 ///
 270 /// [`fill_bytes`] and [`try_fill_bytes`] consume a whole number of `u64`
 271 /// values. If the requested length is not a multiple of 8, some bytes will be
 272 /// discarded.
 273 ///
 274 /// [`next_u32`]: RngCore::next_u32
 275 /// [`next_u64`]: RngCore::next_u64
 276 /// [`fill_bytes`]: RngCore::fill_bytes
 277 /// [`try_fill_bytes`]: RngCore::try_fill_bytes
 278 #[derive(Clone)]
 279 #[cfg_attr(feature = "serde1", derive(Serialize, Deserialize))]
 280 pub struct BlockRng64<R: BlockRngCore + ?Sized> {
 281     results: R::Results,
 282     index: usize,
 283     half_used: bool, // true if only half of the previous result is used
 284     /// The *core* part of the RNG, implementing the `generate` function.
 285     pub core: R,
 286 }
 287
 288 // Custom Debug implementation that does not expose the contents of `results`.
 289 impl<R: BlockRngCore + fmt::Debug> fmt::Debug for BlockRng64<R> {
 290     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 291         fmt.debug_struct("BlockRng64")
 292             .field("core", &self.core)
 293             .field("result_len", &self.results.as_ref().len())
 294             .field("index", &self.index)
 295             .field("half_used", &self.half_used)
 296             .finish()
 297     }
 298 }
 299
 300 impl<R: BlockRngCore> BlockRng64<R> {
 301     /// Create a new `BlockRng` from an existing RNG implementing
 302     /// `BlockRngCore`. Results will be generated on first use.
 303     #[inline]
 304     pub fn new(core: R) -> BlockRng64<R> {
 305         let results_empty = R::Results::default();
 306         BlockRng64 {
 307             core,
 308             index: results_empty.as_ref().len(),
 309             half_used: false,
 310             results: results_empty,
 311         }
 312     }
 313
 314     /// Get the index into the result buffer.
 315     ///
 316     /// If this is equal to or larger than the size of the result buffer then
 317     /// the buffer is "empty" and `generate()` must be called to produce new
 318     /// results.
 319     #[inline(always)]
 320     pub fn index(&self) -> usize {
 321         self.index
 322     }
 323
 324     /// Reset the number of available results.
 325     /// This will force a new set of results to be generated on next use.
 326     #[inline]
 327     pub fn reset(&mut self) {
 328         self.index = self.results.as_ref().len();
 329         self.half_used = false;
 330     }
 331
 332     /// Generate a new set of results immediately, setting the index to the
 333     /// given value.
 334     #[inline]
 335     pub fn generate_and_set(&mut self, index: usize) {
 336         assert!(index < self.results.as_ref().len());
 337         self.core.generate(&mut self.results);
 338         self.index = index;
 339         self.half_used = false;
 340     }
 341 }
 342
 343 impl<R: BlockRngCore<Item = u64>> RngCore for BlockRng64<R>
 344 where
 345     <R as BlockRngCore>::Results: AsRef<[u64]> + AsMut<[u64]>,
 346 {
 347     #[inline]
 348     fn next_u32(&mut self) -> u32 {
 349         let mut index = self.index * 2 - self.half_used as usize;
 350         if index >= self.results.as_ref().len() * 2 {
 351             self.core.generate(&mut self.results);
 352             self.index = 0;
 353             // `self.half_used` is by definition `false`
 354             self.half_used = false;
 355             index = 0;
 356         }
 357
 358         self.half_used = !self.half_used;
 359         self.index += self.half_used as usize;
 360
 361         // Index as if this is a u32 slice.
 362         unsafe {
 363             let results = &*(self.results.as_ref() as *const [u64] as *const [u32]);
 364             if cfg!(target_endian = "little") {
 365                 *results.get_unchecked(index)
 366             } else {
 367                 *results.get_unchecked(index ^ 1)
 368             }
 369         }
 370     }
 371
 372     #[inline]
 373     fn next_u64(&mut self) -> u64 {
 374         if self.index >= self.results.as_ref().len() {
 375             self.core.generate(&mut self.results);
 376             self.index = 0;
 377         }
 378
 379         let value = self.results.as_ref()[self.index];
 380         self.index += 1;
 381         self.half_used = false;
 382         value
 383     }
 384
 385     #[inline]
 386     fn fill_bytes(&mut self, dest: &mut [u8]) {
 387         let mut read_len = 0;
 388         self.half_used = false;
 389         while read_len < dest.len() {
 390             if self.index as usize >= self.results.as_ref().len() {
 391                 self.core.generate(&mut self.results);
 392                 self.index = 0;
 393             }
 394
 395             let (consumed_u64, filled_u8) = fill_via_u64_chunks(
 396                 &self.results.as_ref()[self.index as usize..],
 397                 &mut dest[read_len..],
 398             );
 399
 400             self.index += consumed_u64;
 401             read_len += filled_u8;
 402         }
 403     }
 404
 405     #[inline(always)]
 406     fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
 407         self.fill_bytes(dest);
 408         Ok(())
 409     }
 410 }
 411
 412 impl<R: BlockRngCore + SeedableRng> SeedableRng for BlockRng64<R> {
 413     type Seed = R::Seed;
 414
 415     #[inline(always)]
 416     fn from_seed(seed: Self::Seed) -> Self {
 417         Self::new(R::from_seed(seed))
 418     }
 419
 420     #[inline(always)]
 421     fn seed_from_u64(seed: u64) -> Self {
 422         Self::new(R::seed_from_u64(seed))
 423     }
 424
 425     #[inline(always)]
 426     fn from_rng<S: RngCore>(rng: S) -> Result<Self, Error> {
 427         Ok(Self::new(R::from_rng(rng)?))
 428     }
 429 }
 430
 431 impl<R: BlockRngCore + CryptoRng> CryptoRng for BlockRng<R> {}