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