]>
Commit | Line | Data |
---|---|---|
0731742a XL |
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 | use core::fmt; | |
0731742a | 14 | use rand_core::{RngCore, SeedableRng, Error, le, impls}; |
f035d41b | 15 | #[cfg(feature="serde1")] use serde::{Serialize, Deserialize}; |
0731742a XL |
16 | |
17 | // This is the default multiplier used by PCG for 64-bit state. | |
18 | const MULTIPLIER: u64 = 6364136223846793005; | |
19 | ||
20 | /// A PCG random number generator (XSH RR 64/32 (LCG) variant). | |
f035d41b | 21 | /// |
0731742a XL |
22 | /// Permuted Congruential Generator with 64-bit state, internal Linear |
23 | /// Congruential Generator, and 32-bit output via "xorshift high (bits), | |
24 | /// random rotation" output function. | |
f035d41b | 25 | /// |
0731742a XL |
26 | /// This is a 64-bit LCG with explicitly chosen stream with the PCG-XSH-RR |
27 | /// output function. This combination is the standard `pcg32`. | |
f035d41b | 28 | /// |
0731742a XL |
29 | /// Despite the name, this implementation uses 16 bytes (128 bit) space |
30 | /// comprising 64 bits of state and 64 bits stream selector. These are both set | |
31 | /// by `SeedableRng`, using a 128-bit seed. | |
32 | #[derive(Clone)] | |
33 | #[cfg_attr(feature="serde1", derive(Serialize,Deserialize))] | |
34 | pub struct Lcg64Xsh32 { | |
35 | state: u64, | |
36 | increment: u64, | |
37 | } | |
38 | ||
39 | /// `Lcg64Xsh32` is also officially known as `pcg32`. | |
40 | pub type Pcg32 = Lcg64Xsh32; | |
41 | ||
42 | impl Lcg64Xsh32 { | |
43 | /// Construct an instance compatible with PCG seed and stream. | |
f035d41b | 44 | /// |
0731742a | 45 | /// Note that PCG specifies default values for both parameters: |
f035d41b | 46 | /// |
0731742a | 47 | /// - `state = 0xcafef00dd15ea5e5` |
f035d41b XL |
48 | /// - `stream = 0xa02bdbf7bb3c0a7` |
49 | // Note: stream is 1442695040888963407u64 >> 1 | |
0731742a XL |
50 | pub fn new(state: u64, stream: u64) -> Self { |
51 | // The increment must be odd, hence we discard one bit: | |
52 | let increment = (stream << 1) | 1; | |
53 | Lcg64Xsh32::from_state_incr(state, increment) | |
54 | } | |
f035d41b | 55 | |
0731742a XL |
56 | #[inline] |
57 | fn from_state_incr(state: u64, increment: u64) -> Self { | |
58 | let mut pcg = Lcg64Xsh32 { state, increment }; | |
59 | // Move away from inital value: | |
60 | pcg.state = pcg.state.wrapping_add(pcg.increment); | |
61 | pcg.step(); | |
62 | pcg | |
63 | } | |
f035d41b | 64 | |
0731742a XL |
65 | #[inline] |
66 | fn step(&mut self) { | |
67 | // prepare the LCG for the next round | |
68 | self.state = self.state | |
69 | .wrapping_mul(MULTIPLIER) | |
70 | .wrapping_add(self.increment); | |
71 | } | |
72 | } | |
73 | ||
74 | // Custom Debug implementation that does not expose the internal state | |
75 | impl fmt::Debug for Lcg64Xsh32 { | |
76 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
77 | write!(f, "Lcg64Xsh32 {{}}") | |
78 | } | |
79 | } | |
80 | ||
81 | /// We use a single 127-bit seed to initialise the state and select a stream. | |
82 | /// One `seed` bit (lowest bit of `seed[8]`) is ignored. | |
83 | impl SeedableRng for Lcg64Xsh32 { | |
84 | type Seed = [u8; 16]; | |
85 | ||
86 | fn from_seed(seed: Self::Seed) -> Self { | |
87 | let mut seed_u64 = [0u64; 2]; | |
88 | le::read_u64_into(&seed, &mut seed_u64); | |
89 | ||
90 | // The increment must be odd, hence we discard one bit: | |
91 | Lcg64Xsh32::from_state_incr(seed_u64[0], seed_u64[1] | 1) | |
92 | } | |
93 | } | |
94 | ||
95 | impl RngCore for Lcg64Xsh32 { | |
96 | #[inline] | |
97 | fn next_u32(&mut self) -> u32 { | |
98 | let state = self.state; | |
99 | self.step(); | |
100 | ||
101 | // Output function XSH RR: xorshift high (bits), followed by a random rotate | |
102 | // Constants are for 64-bit state, 32-bit output | |
103 | const ROTATE: u32 = 59; // 64 - 5 | |
104 | const XSHIFT: u32 = 18; // (5 + 32) / 2 | |
105 | const SPARE: u32 = 27; // 64 - 32 - 5 | |
106 | ||
107 | let rot = (state >> ROTATE) as u32; | |
108 | let xsh = (((state >> XSHIFT) ^ state) >> SPARE) as u32; | |
109 | xsh.rotate_right(rot) | |
110 | } | |
111 | ||
112 | #[inline] | |
113 | fn next_u64(&mut self) -> u64 { | |
114 | impls::next_u64_via_u32(self) | |
115 | } | |
116 | ||
117 | #[inline] | |
118 | fn fill_bytes(&mut self, dest: &mut [u8]) { | |
f035d41b | 119 | impls::fill_bytes_via_next(self, dest) |
0731742a XL |
120 | } |
121 | ||
122 | #[inline] | |
123 | fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { | |
f035d41b XL |
124 | self.fill_bytes(dest); |
125 | Ok(()) | |
0731742a XL |
126 | } |
127 | } |