1 // Copyright 2018 Developers of the Rand project.
2 // Copyright 2017 Paul Dicker.
3 // Copyright 2014-2017 Melissa O'Neill and PCG Project contributors
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or https://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 //! PCG random number generators
12 
13 // This is the default multiplier used by PCG for 64-bit state.
14 const MULTIPLIER: u128 = 0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645;
15 
16 use core::fmt;
17 use core::mem::transmute;
18 use rand_core::{RngCore, SeedableRng, Error, le};
19 
20 /// A PCG random number generator (XSL 128/64 (MCG) variant).
21 ///
22 /// Permuted Congruential Generator with 128-bit state, internal Multiplicative
23 /// Congruential Generator, and 64-bit output via "xorshift low (bits),
24 /// random rotation" output function.
25 ///
26 /// This is a 128-bit MCG with the PCG-XSL-RR output function.
27 /// Note that compared to the standard `pcg64` (128-bit LCG with PCG-XSL-RR
28 /// output function), this RNG is faster, also has a long cycle, and still has
29 /// good performance on statistical tests.
30 ///
31 /// Note: this RNG is only available using Rust 1.26 or later.
32 #[derive(Clone)]
33 #[cfg_attr(feature="serde1", derive(Serialize,Deserialize))]
34 pub struct Mcg128Xsl64 {
35     state: u128,
36 }
37 
38 /// A friendly name for `Mcg128Xsl64`.
39 pub type Pcg64Mcg = Mcg128Xsl64;
40 
41 impl Mcg128Xsl64 {
42     /// Construct an instance compatible with PCG seed.
43     ///
44     /// Note that PCG specifies a default value for the parameter:
45     ///
46     /// - `state = 0xcafef00dd15ea5e5`
new(state: u128) -> Self47     pub fn new(state: u128) -> Self {
48         // Force low bit to 1, as in C version (C++ uses `state | 3` instead).
49         Mcg128Xsl64 { state: state | 1 }
50     }
51 }
52 
53 // Custom Debug implementation that does not expose the internal state
54 impl fmt::Debug for Mcg128Xsl64 {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result55     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
56         write!(f, "Mcg128Xsl64 {{}}")
57     }
58 }
59 
60 /// We use a single 126-bit seed to initialise the state and select a stream.
61 /// Two `seed` bits (lowest order of last byte) are ignored.
62 impl SeedableRng for Mcg128Xsl64 {
63     type Seed = [u8; 16];
64 
from_seed(seed: Self::Seed) -> Self65     fn from_seed(seed: Self::Seed) -> Self {
66         // Read as if a little-endian u128 value:
67         let mut seed_u64 = [0u64; 2];
68         le::read_u64_into(&seed, &mut seed_u64);
69         let state = (seed_u64[0] as u128) |
70                     (seed_u64[1] as u128) << 64;
71         Mcg128Xsl64::new(state)
72     }
73 }
74 
75 impl RngCore for Mcg128Xsl64 {
76     #[inline]
next_u32(&mut self) -> u3277     fn next_u32(&mut self) -> u32 {
78         self.next_u64() as u32
79     }
80 
81     #[inline]
next_u64(&mut self) -> u6482     fn next_u64(&mut self) -> u64 {
83         // prepare the LCG for the next round
84         let state = self.state.wrapping_mul(MULTIPLIER);
85         self.state = state;
86 
87         // Output function XSL RR ("xorshift low (bits), random rotation")
88         // Constants are for 128-bit state, 64-bit output
89         const XSHIFT: u32 = 64;     // (128 - 64 + 64) / 2
90         const ROTATE: u32 = 122;    // 128 - 6
91 
92         let rot = (state >> ROTATE) as u32;
93         let xsl = ((state >> XSHIFT) as u64) ^ (state as u64);
94         xsl.rotate_right(rot)
95     }
96 
97     #[inline]
fill_bytes(&mut self, dest: &mut [u8])98     fn fill_bytes(&mut self, dest: &mut [u8]) {
99         // specialisation of impls::fill_bytes_via_next; approx 3x faster
100         let mut left = dest;
101         while left.len() >= 8 {
102             let (l, r) = {left}.split_at_mut(8);
103             left = r;
104             let chunk: [u8; 8] = unsafe {
105                 transmute(self.next_u64().to_le())
106             };
107             l.copy_from_slice(&chunk);
108         }
109         let n = left.len();
110         if n > 0 {
111             let chunk: [u8; 8] = unsafe {
112                 transmute(self.next_u64().to_le())
113             };
114             left.copy_from_slice(&chunk[..n]);
115         }
116     }
117 
118     #[inline]
try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error>119     fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
120         Ok(self.fill_bytes(dest))
121     }
122 }
123