rand_xoshiro/
splitmix64.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
9use core::convert::Infallible;
10use rand_core::{SeedableRng, TryRng, utils};
11#[cfg(feature = "serde")]
12use serde::{Deserialize, Serialize};
13
14/// A splitmix64 random number generator.
15///
16/// The splitmix algorithm is not suitable for cryptographic purposes, but is
17/// very fast and has a 64 bit state.
18///
19/// The algorithm used here is translated from [the `splitmix64.c`
20/// reference source code](http://xoshiro.di.unimi.it/splitmix64.c) by
21/// Sebastiano Vigna. For `next_u32`, a more efficient mixing function taken
22/// from [`dsiutils`](http://dsiutils.di.unimi.it/) is used.
23#[allow(missing_copy_implementations)]
24#[derive(Debug, Clone, PartialEq, Eq)]
25#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
26pub struct SplitMix64 {
27    x: u64,
28}
29
30const PHI: u64 = 0x9e3779b97f4a7c15;
31
32impl TryRng for SplitMix64 {
33    type Error = Infallible;
34
35    #[inline]
36    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
37        self.x = self.x.wrapping_add(PHI);
38        let mut z = self.x;
39        // David Stafford's
40        // (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)
41        // "Mix4" variant of the 64-bit finalizer in Austin Appleby's
42        // MurmurHash3 algorithm.
43        z = (z ^ (z >> 33)).wrapping_mul(0x62A9D9ED799705F5);
44        z = (z ^ (z >> 28)).wrapping_mul(0xCB24D0A5C88C35B3);
45        Ok((z >> 32) as u32)
46    }
47
48    #[inline]
49    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
50        self.x = self.x.wrapping_add(PHI);
51        let mut z = self.x;
52        z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
53        z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
54        Ok(z ^ (z >> 31))
55    }
56
57    #[inline]
58    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Self::Error> {
59        utils::fill_bytes_via_next_word(dest, || self.try_next_u64())
60    }
61}
62
63impl SplitMix64 {
64    /// Return the internal state of the generator as little-endian bytes
65    /// that can be passed to [`SeedableRng::from_seed`] to reconstruct an
66    /// identical generator.
67    ///
68    /// [`SeedableRng::from_seed`]: rand_core::SeedableRng::from_seed
69    pub fn state(&self) -> [u8; 8] {
70        self.x.to_le_bytes()
71    }
72}
73
74impl SeedableRng for SplitMix64 {
75    type Seed = [u8; 8];
76
77    /// Create a new `SplitMix64`.
78    fn from_seed(seed: [u8; 8]) -> SplitMix64 {
79        let state: [_; 1] = utils::read_words(&seed);
80        SplitMix64 { x: state[0] }
81    }
82
83    /// Seed a `SplitMix64` from a `u64`.
84    fn seed_from_u64(seed: u64) -> SplitMix64 {
85        SplitMix64::from_seed(seed.to_le_bytes())
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use rand_core::Rng;
93
94    #[test]
95    fn reference() {
96        let mut rng = SplitMix64::seed_from_u64(1477776061723855037);
97        // These values were produced with the reference implementation:
98        // http://xoshiro.di.unimi.it/splitmix64.c
99        let expected: [u64; 50] = [
100            1985237415132408290,
101            2979275885539914483,
102            13511426838097143398,
103            8488337342461049707,
104            15141737807933549159,
105            17093170987380407015,
106            16389528042912955399,
107            13177319091862933652,
108            10841969400225389492,
109            17094824097954834098,
110            3336622647361835228,
111            9678412372263018368,
112            11111587619974030187,
113            7882215801036322410,
114            5709234165213761869,
115            7799681907651786826,
116            4616320717312661886,
117            4251077652075509767,
118            7836757050122171900,
119            5054003328188417616,
120            12919285918354108358,
121            16477564761813870717,
122            5124667218451240549,
123            18099554314556827626,
124            7603784838804469118,
125            6358551455431362471,
126            3037176434532249502,
127            3217550417701719149,
128            9958699920490216947,
129            5965803675992506258,
130            12000828378049868312,
131            12720568162811471118,
132            245696019213873792,
133            8351371993958923852,
134            14378754021282935786,
135            5655432093647472106,
136            5508031680350692005,
137            8515198786865082103,
138            6287793597487164412,
139            14963046237722101617,
140            3630795823534910476,
141            8422285279403485710,
142            10554287778700714153,
143            10871906555720704584,
144            8659066966120258468,
145            9420238805069527062,
146            10338115333623340156,
147            13514802760105037173,
148            14635952304031724449,
149            15419692541594102413,
150        ];
151        for &e in expected.iter() {
152            assert_eq!(rng.next_u64(), e);
153        }
154    }
155
156    #[test]
157    fn state_roundtrip() {
158        let rng = SplitMix64::seed_from_u64(42);
159        let clone = SplitMix64::from_seed(rng.state());
160        assert_eq!(clone, rng);
161    }
162
163    #[test]
164    fn next_u32() {
165        let mut rng = SplitMix64::seed_from_u64(10);
166        // These values were produced with the reference implementation:
167        // http://dsiutils.di.unimi.it/dsiutils-2.5.1-src.tar.gz
168        let expected: [u32; 100] = [
169            3930361779, 4016923089, 4113052479, 925926767, 1755287528, 802865554, 954171070,
170            3724185978, 173676273, 1414488795, 12664133, 1784889697, 1303817078, 261610523,
171            941280008, 2571813643, 2954453492, 378291111, 2546873158, 3923319175, 645257028,
172            3881821278, 2681538690, 3037029984, 1999958137, 1853970361, 2989951788, 2126166628,
173            839962987, 3989679659, 3656977858, 684284364, 1673258011, 170979192, 3037622326,
174            1600748179, 1780764218, 1141430714, 4139736875, 3336905707, 2262051600, 3830850262,
175            2430765325, 1073032139, 1668888979, 2716938970, 4102420032, 40305196, 386350562,
176            2754480591, 622869439, 2129598760, 2306038241, 4218338739, 412298926, 3453855056,
177            3061469690, 4284292697, 994843708, 1591016681, 414726151, 1238182607, 18073498,
178            1237631493, 351884714, 2347486264, 2488990876, 802846256, 645670443, 957607012,
179            3126589776, 1966356370, 3036485766, 868696717, 2808613630, 2070968151, 1025536863,
180            1743949425, 466212687, 2994327271, 209776458, 1246125124, 3344380309, 2203947859,
181            968313105, 2805485302, 197484837, 3472483632, 3931823935, 3288490351, 4165666529,
182            3671080416, 689542830, 1272555356, 1039141475, 3984640460, 4142959054, 2252788890,
183            2459379590, 991872507,
184        ];
185        for &e in expected.iter() {
186            assert_eq!(rng.next_u32(), e);
187        }
188    }
189}
rand_xoshiro/splitmix64.rs

rand_xoshiro/
splitmix64.rs
