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: [u64; 1] = [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}
171