summaryrefslogtreecommitdiff
path: root/rand/rand_pcg/src
diff options
context:
space:
mode:
Diffstat (limited to 'rand/rand_pcg/src')
-rw-r--r--rand/rand_pcg/src/lib.rs48
-rw-r--r--rand/rand_pcg/src/pcg128.rs122
-rw-r--r--rand/rand_pcg/src/pcg64.rs141
3 files changed, 311 insertions, 0 deletions
diff --git a/rand/rand_pcg/src/lib.rs b/rand/rand_pcg/src/lib.rs
new file mode 100644
index 0000000..5160e87
--- /dev/null
+++ b/rand/rand_pcg/src/lib.rs
@@ -0,0 +1,48 @@
+// Copyright 2018 Developers of the Rand project.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! The PCG random number generators.
+//!
+//! This is a native Rust implementation of a small selection of PCG generators.
+//! The primary goal of this crate is simple, minimal, well-tested code; in
+//! other words it is explicitly not a goal to re-implement all of PCG.
+//!
+//! This crate provides:
+//!
+//! - `Pcg32` aka `Lcg64Xsh32`, officially known as `pcg32`, a general
+//! purpose RNG. This is a good choice on both 32-bit and 64-bit CPUs
+//! (for 32-bit output).
+//! - `Pcg64Mcg` aka `Mcg128Xsl64`, officially known as `mcg_xsl_rr_128_64`,
+//! a general purpose RNG using 128-bit multiplications. This has poor
+//! performance on 32-bit CPUs but is a good choice on 64-bit CPUs for
+//! both 32-bit and 64-bit output. (Note: this RNG is only available using
+//! Rust 1.26 or later.)
+//!
+//! Both of these use 16 bytes of state and 128-bit seeds, and are considered
+//! value-stable (i.e. any change affecting the output given a fixed seed would
+//! be considered a breaking change to the crate).
+
+#![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png",
+ html_favicon_url = "https://www.rust-lang.org/favicon.ico",
+ html_root_url = "https://rust-random.github.io/rand/")]
+
+#![deny(missing_docs)]
+#![deny(missing_debug_implementations)]
+
+#![no_std]
+
+extern crate rand_core;
+
+#[cfg(feature="serde1")] extern crate serde;
+#[cfg(feature="serde1")] #[macro_use] extern crate serde_derive;
+
+mod pcg64;
+#[cfg(rust_1_26)] mod pcg128;
+
+pub use self::pcg64::{Pcg32, Lcg64Xsh32};
+#[cfg(rust_1_26)] pub use self::pcg128::{Pcg64Mcg, Mcg128Xsl64};
diff --git a/rand/rand_pcg/src/pcg128.rs b/rand/rand_pcg/src/pcg128.rs
new file mode 100644
index 0000000..9aff506
--- /dev/null
+++ b/rand/rand_pcg/src/pcg128.rs
@@ -0,0 +1,122 @@
+// Copyright 2018 Developers of the Rand project.
+// Copyright 2017 Paul Dicker.
+// Copyright 2014-2017 Melissa O'Neill and PCG Project contributors
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! PCG random number generators
+
+// This is the default multiplier used by PCG for 64-bit state.
+const MULTIPLIER: u128 = 0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645;
+
+use core::fmt;
+use core::mem::transmute;
+use rand_core::{RngCore, SeedableRng, Error, le};
+
+/// A PCG random number generator (XSL 128/64 (MCG) variant).
+///
+/// Permuted Congruential Generator with 128-bit state, internal Multiplicative
+/// Congruential Generator, and 64-bit output via "xorshift low (bits),
+/// random rotation" output function.
+///
+/// This is a 128-bit MCG with the PCG-XSL-RR output function.
+/// Note that compared to the standard `pcg64` (128-bit LCG with PCG-XSL-RR
+/// output function), this RNG is faster, also has a long cycle, and still has
+/// good performance on statistical tests.
+///
+/// Note: this RNG is only available using Rust 1.26 or later.
+#[derive(Clone)]
+#[cfg_attr(feature="serde1", derive(Serialize,Deserialize))]
+pub struct Mcg128Xsl64 {
+ state: u128,
+}
+
+/// A friendly name for `Mcg128Xsl64`.
+pub type Pcg64Mcg = Mcg128Xsl64;
+
+impl Mcg128Xsl64 {
+ /// Construct an instance compatible with PCG seed.
+ ///
+ /// Note that PCG specifies a default value for the parameter:
+ ///
+ /// - `state = 0xcafef00dd15ea5e5`
+ pub fn new(state: u128) -> Self {
+ // Force low bit to 1, as in C version (C++ uses `state | 3` instead).
+ Mcg128Xsl64 { state: state | 1 }
+ }
+}
+
+// Custom Debug implementation that does not expose the internal state
+impl fmt::Debug for Mcg128Xsl64 {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(f, "Mcg128Xsl64 {{}}")
+ }
+}
+
+/// We use a single 126-bit seed to initialise the state and select a stream.
+/// Two `seed` bits (lowest order of last byte) are ignored.
+impl SeedableRng for Mcg128Xsl64 {
+ type Seed = [u8; 16];
+
+ fn from_seed(seed: Self::Seed) -> Self {
+ // Read as if a little-endian u128 value:
+ let mut seed_u64 = [0u64; 2];
+ le::read_u64_into(&seed, &mut seed_u64);
+ let state = (seed_u64[0] as u128) |
+ (seed_u64[1] as u128) << 64;
+ Mcg128Xsl64::new(state)
+ }
+}
+
+impl RngCore for Mcg128Xsl64 {
+ #[inline]
+ fn next_u32(&mut self) -> u32 {
+ self.next_u64() as u32
+ }
+
+ #[inline]
+ fn next_u64(&mut self) -> u64 {
+ // prepare the LCG for the next round
+ let state = self.state.wrapping_mul(MULTIPLIER);
+ self.state = state;
+
+ // Output function XSL RR ("xorshift low (bits), random rotation")
+ // Constants are for 128-bit state, 64-bit output
+ const XSHIFT: u32 = 64; // (128 - 64 + 64) / 2
+ const ROTATE: u32 = 122; // 128 - 6
+
+ let rot = (state >> ROTATE) as u32;
+ let xsl = ((state >> XSHIFT) as u64) ^ (state as u64);
+ xsl.rotate_right(rot)
+ }
+
+ #[inline]
+ fn fill_bytes(&mut self, dest: &mut [u8]) {
+ // specialisation of impls::fill_bytes_via_next; approx 3x faster
+ let mut left = dest;
+ while left.len() >= 8 {
+ let (l, r) = {left}.split_at_mut(8);
+ left = r;
+ let chunk: [u8; 8] = unsafe {
+ transmute(self.next_u64().to_le())
+ };
+ l.copy_from_slice(&chunk);
+ }
+ let n = left.len();
+ if n > 0 {
+ let chunk: [u8; 8] = unsafe {
+ transmute(self.next_u64().to_le())
+ };
+ left.copy_from_slice(&chunk[..n]);
+ }
+ }
+
+ #[inline]
+ fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
+ Ok(self.fill_bytes(dest))
+ }
+}
diff --git a/rand/rand_pcg/src/pcg64.rs b/rand/rand_pcg/src/pcg64.rs
new file mode 100644
index 0000000..9177ec2
--- /dev/null
+++ b/rand/rand_pcg/src/pcg64.rs
@@ -0,0 +1,141 @@
+// Copyright 2018 Developers of the Rand project.
+// Copyright 2017 Paul Dicker.
+// Copyright 2014-2017 Melissa O'Neill and PCG Project contributors
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! PCG random number generators
+
+use core::fmt;
+use core::mem::transmute;
+use rand_core::{RngCore, SeedableRng, Error, le, impls};
+
+// This is the default multiplier used by PCG for 64-bit state.
+const MULTIPLIER: u64 = 6364136223846793005;
+
+/// A PCG random number generator (XSH RR 64/32 (LCG) variant).
+///
+/// Permuted Congruential Generator with 64-bit state, internal Linear
+/// Congruential Generator, and 32-bit output via "xorshift high (bits),
+/// random rotation" output function.
+///
+/// This is a 64-bit LCG with explicitly chosen stream with the PCG-XSH-RR
+/// output function. This combination is the standard `pcg32`.
+///
+/// Despite the name, this implementation uses 16 bytes (128 bit) space
+/// comprising 64 bits of state and 64 bits stream selector. These are both set
+/// by `SeedableRng`, using a 128-bit seed.
+#[derive(Clone)]
+#[cfg_attr(feature="serde1", derive(Serialize,Deserialize))]
+pub struct Lcg64Xsh32 {
+ state: u64,
+ increment: u64,
+}
+
+/// `Lcg64Xsh32` is also officially known as `pcg32`.
+pub type Pcg32 = Lcg64Xsh32;
+
+impl Lcg64Xsh32 {
+ /// Construct an instance compatible with PCG seed and stream.
+ ///
+ /// Note that PCG specifies default values for both parameters:
+ ///
+ /// - `state = 0xcafef00dd15ea5e5`
+ /// - `stream = 721347520444481703`
+ pub fn new(state: u64, stream: u64) -> Self {
+ // The increment must be odd, hence we discard one bit:
+ let increment = (stream << 1) | 1;
+ Lcg64Xsh32::from_state_incr(state, increment)
+ }
+
+ #[inline]
+ fn from_state_incr(state: u64, increment: u64) -> Self {
+ let mut pcg = Lcg64Xsh32 { state, increment };
+ // Move away from inital value:
+ pcg.state = pcg.state.wrapping_add(pcg.increment);
+ pcg.step();
+ pcg
+ }
+
+ #[inline]
+ fn step(&mut self) {
+ // prepare the LCG for the next round
+ self.state = self.state
+ .wrapping_mul(MULTIPLIER)
+ .wrapping_add(self.increment);
+ }
+}
+
+// Custom Debug implementation that does not expose the internal state
+impl fmt::Debug for Lcg64Xsh32 {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(f, "Lcg64Xsh32 {{}}")
+ }
+}
+
+/// We use a single 127-bit seed to initialise the state and select a stream.
+/// One `seed` bit (lowest bit of `seed[8]`) is ignored.
+impl SeedableRng for Lcg64Xsh32 {
+ type Seed = [u8; 16];
+
+ fn from_seed(seed: Self::Seed) -> Self {
+ let mut seed_u64 = [0u64; 2];
+ le::read_u64_into(&seed, &mut seed_u64);
+
+ // The increment must be odd, hence we discard one bit:
+ Lcg64Xsh32::from_state_incr(seed_u64[0], seed_u64[1] | 1)
+ }
+}
+
+impl RngCore for Lcg64Xsh32 {
+ #[inline]
+ fn next_u32(&mut self) -> u32 {
+ let state = self.state;
+ self.step();
+
+ // Output function XSH RR: xorshift high (bits), followed by a random rotate
+ // Constants are for 64-bit state, 32-bit output
+ const ROTATE: u32 = 59; // 64 - 5
+ const XSHIFT: u32 = 18; // (5 + 32) / 2
+ const SPARE: u32 = 27; // 64 - 32 - 5
+
+ let rot = (state >> ROTATE) as u32;
+ let xsh = (((state >> XSHIFT) ^ state) >> SPARE) as u32;
+ xsh.rotate_right(rot)
+ }
+
+ #[inline]
+ fn next_u64(&mut self) -> u64 {
+ impls::next_u64_via_u32(self)
+ }
+
+ #[inline]
+ fn fill_bytes(&mut self, dest: &mut [u8]) {
+ // specialisation of impls::fill_bytes_via_next; approx 40% faster
+ let mut left = dest;
+ while left.len() >= 4 {
+ let (l, r) = {left}.split_at_mut(4);
+ left = r;
+ let chunk: [u8; 4] = unsafe {
+ transmute(self.next_u32().to_le())
+ };
+ l.copy_from_slice(&chunk);
+ }
+ let n = left.len();
+ if n > 0 {
+ let chunk: [u8; 4] = unsafe {
+ transmute(self.next_u32().to_le())
+ };
+ left.copy_from_slice(&chunk[..n]);
+ }
+ }
+
+ #[inline]
+ fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
+ Ok(self.fill_bytes(dest))
+ }
+}
generated by cgit v1.2.3 (git 2.46.0) at 2024-11-03 23:03:59 +0000