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

rand_xoshiro/
splitmix64.rs
