rand_xoshiro/
splitmix64.rs

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

rand_xoshiro/
splitmix64.rs
