| // Copyright 2018 Developers of the Rand project. |
| // |
| // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your |
| // option. This file may not be copied, modified, or distributed |
| // except according to those terms. |
| |
| use byteorder::{ByteOrder, LittleEndian}; |
| use rand_core::le::read_u64_into; |
| use rand_core::impls::fill_bytes_via_next; |
| use rand_core::{RngCore, SeedableRng, Error}; |
| |
| /// A splitmix64 random number generator. |
| /// |
| /// The splitmix algorithm is not suitable for cryptographic purposes, but is |
| /// very fast and has a 64 bit state. |
| /// |
| /// The algorithm used here is translated from [the `splitmix64.c` |
| /// reference source code](http://xoshiro.di.unimi.it/splitmix64.c) by |
| /// Sebastiano Vigna. For `next_u32`, a more efficient mixing function taken |
| /// from [`dsiutils`](http://dsiutils.di.unimi.it/) is used. |
| #[allow(missing_copy_implementations)] |
| #[derive(Debug, Clone)] |
| pub struct SplitMix64 { |
| x: u64, |
| } |
| |
| const PHI: u64 = 0x9e3779b97f4a7c15; |
| |
| impl RngCore for SplitMix64 { |
| #[inline] |
| fn next_u32(&mut self) -> u32 { |
| self.x = self.x.wrapping_add(PHI); |
| let mut z = self.x; |
| // David Stafford's |
| // (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html) |
| // "Mix4" variant of the 64-bit finalizer in Austin Appleby's |
| // MurmurHash3 algorithm. |
| z = (z ^ (z >> 33)).wrapping_mul(0x62A9D9ED799705F5); |
| z = (z ^ (z >> 28)).wrapping_mul(0xCB24D0A5C88C35B3); |
| (z >> 32) as u32 |
| } |
| |
| #[inline] |
| fn next_u64(&mut self) -> u64 { |
| self.x = self.x.wrapping_add(PHI); |
| let mut z = self.x; |
| z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9); |
| z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb); |
| z ^ (z >> 31) |
| } |
| |
| #[inline] |
| fn fill_bytes(&mut self, dest: &mut [u8]) { |
| fill_bytes_via_next(self, dest); |
| } |
| |
| #[inline] |
| fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { |
| self.fill_bytes(dest); |
| Ok(()) |
| } |
| } |
| |
| impl SeedableRng for SplitMix64 { |
| type Seed = [u8; 8]; |
| |
| /// Create a new `SplitMix64`. |
| fn from_seed(seed: [u8; 8]) -> SplitMix64 { |
| let mut state = [0; 1]; |
| read_u64_into(&seed, &mut state); |
| SplitMix64 { |
| x: state[0], |
| } |
| } |
| |
| /// Seed a `SplitMix64` from a `u64`. |
| fn seed_from_u64(seed: u64) -> SplitMix64 { |
| let mut x = [0; 8]; |
| LittleEndian::write_u64(&mut x, seed); |
| SplitMix64::from_seed(x) |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use super::*; |
| |
| #[test] |
| fn reference() { |
| let mut rng = SplitMix64::seed_from_u64(1477776061723855037); |
| // These values were produced with the reference implementation: |
| // http://xoshiro.di.unimi.it/splitmix64.c |
| let expected : [u64 ; 50]= [ |
| 1985237415132408290, 2979275885539914483, 13511426838097143398, |
| 8488337342461049707, 15141737807933549159, 17093170987380407015, |
| 16389528042912955399, 13177319091862933652, 10841969400225389492, |
| 17094824097954834098, 3336622647361835228, 9678412372263018368, |
| 11111587619974030187, 7882215801036322410, 5709234165213761869, |
| 7799681907651786826, 4616320717312661886, 4251077652075509767, |
| 7836757050122171900, 5054003328188417616, 12919285918354108358, |
| 16477564761813870717, 5124667218451240549, 18099554314556827626, |
| 7603784838804469118, 6358551455431362471, 3037176434532249502, |
| 3217550417701719149, 9958699920490216947, 5965803675992506258, |
| 12000828378049868312, 12720568162811471118, 245696019213873792, |
| 8351371993958923852, 14378754021282935786, 5655432093647472106, |
| 5508031680350692005, 8515198786865082103, 6287793597487164412, |
| 14963046237722101617, 3630795823534910476, 8422285279403485710, |
| 10554287778700714153, 10871906555720704584, 8659066966120258468, |
| 9420238805069527062, 10338115333623340156, 13514802760105037173, |
| 14635952304031724449, 15419692541594102413, |
| ]; |
| for &e in expected.iter() { |
| assert_eq!(rng.next_u64(), e); |
| } |
| } |
| |
| #[test] |
| fn next_u32() { |
| let mut rng = SplitMix64::seed_from_u64(10); |
| // These values were produced with the reference implementation: |
| // http://dsiutils.di.unimi.it/dsiutils-2.5.1-src.tar.gz |
| let expected : [u32 ; 100]= [ |
| 3930361779, 4016923089, 4113052479, 925926767, 1755287528, |
| 802865554, 954171070, 3724185978, 173676273, 1414488795, 12664133, |
| 1784889697, 1303817078, 261610523, 941280008, 2571813643, |
| 2954453492, 378291111, 2546873158, 3923319175, 645257028, |
| 3881821278, 2681538690, 3037029984, 1999958137, 1853970361, |
| 2989951788, 2126166628, 839962987, 3989679659, 3656977858, |
| 684284364, 1673258011, 170979192, 3037622326, 1600748179, |
| 1780764218, 1141430714, 4139736875, 3336905707, 2262051600, |
| 3830850262, 2430765325, 1073032139, 1668888979, 2716938970, |
| 4102420032, 40305196, 386350562, 2754480591, 622869439, 2129598760, |
| 2306038241, 4218338739, 412298926, 3453855056, 3061469690, |
| 4284292697, 994843708, 1591016681, 414726151, 1238182607, 18073498, |
| 1237631493, 351884714, 2347486264, 2488990876, 802846256, 645670443, |
| 957607012, 3126589776, 1966356370, 3036485766, 868696717, |
| 2808613630, 2070968151, 1025536863, 1743949425, 466212687, |
| 2994327271, 209776458, 1246125124, 3344380309, 2203947859, |
| 968313105, 2805485302, 197484837, 3472483632, 3931823935, |
| 3288490351, 4165666529, 3671080416, 689542830, 1272555356, |
| 1039141475, 3984640460, 4142959054, 2252788890, 2459379590, |
| 991872507, |
| ]; |
| for &e in expected.iter() { |
| assert_eq!(rng.next_u32(), e); |
| } |
| } |
| } |