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 xoshiro256++ random number generator.
16///
17/// The xoshiro256++ algorithm is not suitable for cryptographic purposes, but
18/// is very fast and has excellent statistical properties.
19///
20/// The algorithm used here is translated from [the `xoshiro256plusplus.c`
21/// reference source code](http://xoshiro.di.unimi.it/xoshiro256plusplus.c) by
22/// David Blackman and Sebastiano Vigna.
23#[derive(Debug, Clone, PartialEq, Eq)]
24#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
25pub struct Xoshiro256PlusPlus {
26 s: [u64; 4],
27}
28
29impl SeedableRng for Xoshiro256PlusPlus {
30 type Seed = [u8; 32];
31
32 /// Create a new `Xoshiro256PlusPlus`. If `seed` is entirely 0, it will be
33 /// mapped to a different seed.
34 #[inline]
35 fn from_seed(seed: [u8; 32]) -> Xoshiro256PlusPlus {
36 let mut state = [0; 4];
37 read_u64_into(&seed, &mut state);
38 // Check for zero on aligned integers for better code generation.
39 // Furtermore, seed_from_u64(0) will expand to a constant when optimized.
40 if state.iter().all(|&x| x == 0) {
41 return Self::seed_from_u64(0);
42 }
43 Xoshiro256PlusPlus { s: state }
44 }
45
46 /// Create a new `Xoshiro256PlusPlus` from a `u64` seed.
47 ///
48 /// This uses the SplitMix64 generator internally.
49 #[inline]
50 fn seed_from_u64(mut state: u64) -> Self {
51 const PHI: u64 = 0x9e3779b97f4a7c15;
52 let mut s = [0; 4];
53 for i in s.iter_mut() {
54 state = state.wrapping_add(PHI);
55 let mut z = state;
56 z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
57 z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
58 z = z ^ (z >> 31);
59 *i = z;
60 }
61 // By using a non-zero PHI we are guaranteed to generate a non-zero state
62 // Thus preventing a recursion between from_seed and seed_from_u64.
63 debug_assert_ne!(s, [0; 4]);
64 Xoshiro256PlusPlus { s }
65 }
66}
67
68impl RngCore for Xoshiro256PlusPlus {
69 #[inline]
70 fn next_u32(&mut self) -> u32 {
71 // The lowest bits have some linear dependencies, so we use the
72 // upper bits instead.
73 let val = self.next_u64();
74 (val >> 32) as u32
75 }
76
77 #[inline]
78 fn next_u64(&mut self) -> u64 {
79 let res = self.s[0]
80 .wrapping_add(self.s[3])
81 .rotate_left(23)
82 .wrapping_add(self.s[0]);
83
84 let t = self.s[1] << 17;
85
86 self.s[2] ^= self.s[0];
87 self.s[3] ^= self.s[1];
88 self.s[1] ^= self.s[2];
89 self.s[0] ^= self.s[3];
90
91 self.s[2] ^= t;
92
93 self.s[3] = self.s[3].rotate_left(45);
94
95 res
96 }
97
98 #[inline]
99 fn fill_bytes(&mut self, dst: &mut [u8]) {
100 fill_bytes_via_next(self, dst)
101 }
102}
103
104#[cfg(test)]
105mod tests {
106 use super::Xoshiro256PlusPlus;
107 use rand_core::{RngCore, SeedableRng};
108
109 #[test]
110 fn reference() {
111 let mut rng = Xoshiro256PlusPlus::from_seed([
112 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0,
113 0, 0, 0,
114 ]);
115 // These values were produced with the reference implementation:
116 // http://xoshiro.di.unimi.it/xoshiro256plusplus.c
117 let expected = [
118 41943041,
119 58720359,
120 3588806011781223,
121 3591011842654386,
122 9228616714210784205,
123 9973669472204895162,
124 14011001112246962877,
125 12406186145184390807,
126 15849039046786891736,
127 10450023813501588000,
128 ];
129 for &e in &expected {
130 assert_eq!(rng.next_u64(), e);
131 }
132 }
133
134 #[test]
135 fn stable_seed_from_u64() {
136 // We don't guarantee value-stability for SmallRng but this
137 // could influence keeping stability whenever possible (e.g. after optimizations).
138 let mut rng = Xoshiro256PlusPlus::seed_from_u64(0);
139 let expected = [
140 5987356902031041503,
141 7051070477665621255,
142 6633766593972829180,
143 211316841551650330,
144 9136120204379184874,
145 379361710973160858,
146 15813423377499357806,
147 15596884590815070553,
148 5439680534584881407,
149 1369371744833522710,
150 ];
151 for &e in &expected {
152 assert_eq!(rng.next_u64(), e);
153 }
154 }
155}
156