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