1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // https://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! The ISAAC-64 random number generator.
13 use core
::{fmt, slice}
;
14 use core
::num
::Wrapping
as w
;
15 use rand_core
::{RngCore, SeedableRng, Error, le}
;
16 use rand_core
::block
::{BlockRngCore, BlockRng64}
;
17 use prng
::isaac_array
::IsaacArray
;
19 #[allow(non_camel_case_types)]
22 const RAND_SIZE_LEN
: usize = 8;
23 const RAND_SIZE
: usize = 1 << RAND_SIZE_LEN
;
25 /// A random number generator that uses ISAAC-64, the 64-bit variant of the
28 /// ISAAC stands for "Indirection, Shift, Accumulate, Add, and Count" which are
29 /// the principal bitwise operations employed. It is the most advanced of a
30 /// series of array based random number generator designed by Robert Jenkins
33 /// ISAAC-64 is mostly similar to ISAAC. Because it operates on 64-bit integers
34 /// instead of 32-bit, it uses twice as much memory to hold its state and
35 /// results. Also it uses different constants for shifts and indirect indexing,
36 /// optimized to give good results for 64bit arithmetic.
38 /// ISAAC-64 is notably fast and produces excellent quality random numbers for
39 /// non-cryptographic applications.
41 /// In spite of being designed with cryptographic security in mind, ISAAC hasn't
42 /// been stringently cryptanalyzed and thus cryptographers do not not
43 /// consensually trust it to be secure. When looking for a secure RNG, prefer
44 /// [`Hc128Rng`] instead, which, like ISAAC, is an array-based RNG and one of
45 /// the stream-ciphers selected the by eSTREAM contest.
47 /// ## Overview of the ISAAC-64 algorithm:
51 /// Input: a, b, c, s[256] // state
52 /// Output: r[256] // results
54 /// mix(a,i) = !(a ^ a << 21) if i = 0 mod 4
55 /// a ^ a >> 5 if i = 1 mod 4
56 /// a ^ a << 12 if i = 2 mod 4
57 /// a ^ a >> 33 if i = 3 mod 4
64 /// a = mix(a,i) + s[i+128 mod 256]
65 /// y = a + b + s[x>>3 mod 256]
67 /// b = x + s[y>>11 mod 256]
72 /// This implementation uses [`BlockRng64`] to implement the [`RngCore`] methods.
74 /// See for more information the documentation of [`IsaacRng`].
76 /// [^1]: Bob Jenkins, [*ISAAC and RC4*](
77 /// http://burtleburtle.net/bob/rand/isaac.html)
79 /// [`IsaacRng`]: ../isaac/struct.IsaacRng.html
80 /// [`Hc128Rng`]: ../hc128/struct.Hc128Rng.html
81 /// [`BlockRng64`]: ../../../rand_core/block/struct.BlockRng64.html
82 /// [`RngCore`]: ../../trait.RngCore.html
83 #[derive(Clone, Debug)]
84 #[cfg_attr(feature="serde1", derive(Serialize, Deserialize))]
85 pub struct Isaac64Rng(BlockRng64
<Isaac64Core
>);
87 impl RngCore
for Isaac64Rng
{
89 fn next_u32(&mut self) -> u32 {
94 fn next_u64(&mut self) -> u64 {
98 fn fill_bytes(&mut self, dest
: &mut [u8]) {
99 self.0.fill_bytes
(dest
)
102 fn try_fill_bytes(&mut self, dest
: &mut [u8]) -> Result
<(), Error
> {
103 self.0.try_fill_bytes(dest
)
107 impl SeedableRng
for Isaac64Rng
{
108 type Seed
= <Isaac64Core
as SeedableRng
>::Seed
;
110 fn from_seed(seed
: Self::Seed
) -> Self {
111 Isaac64Rng(BlockRng64
::<Isaac64Core
>::from_seed(seed
))
114 /// Create an ISAAC random number generator using an `u64` as seed.
115 /// If `seed == 0` this will produce the same stream of random numbers as
116 /// the reference implementation when used unseeded.
117 fn seed_from_u64(seed
: u64) -> Self {
118 Isaac64Rng(BlockRng64
::<Isaac64Core
>::seed_from_u64(seed
))
121 fn from_rng
<S
: RngCore
>(rng
: S
) -> Result
<Self, Error
> {
122 BlockRng64
::<Isaac64Core
>::from_rng(rng
).map(|rng
| Isaac64Rng(rng
))
127 /// Create a 64-bit ISAAC random number generator using the
128 /// default fixed seed.
130 /// DEPRECATED. `Isaac64Rng::new_from_u64(0)` will produce identical results.
131 #[deprecated(since="0.5.0", note="use the FromEntropy or SeedableRng trait")]
132 pub fn new_unseeded() -> Self {
133 Self::seed_from_u64(0)
136 /// Create an ISAAC-64 random number generator using an `u64` as seed.
137 /// If `seed == 0` this will produce the same stream of random numbers as
138 /// the reference implementation when used unseeded.
139 #[deprecated(since="0.6.0", note="use SeedableRng::seed_from_u64 instead")]
140 pub fn new_from_u64(seed
: u64) -> Self {
141 Self::seed_from_u64(seed
)
145 /// The core of `Isaac64Rng`, used with `BlockRng`.
147 #[cfg_attr(feature="serde1", derive(Serialize, Deserialize))]
148 pub struct Isaac64Core
{
149 #[cfg_attr(feature="serde1",serde(with="super::isaac_array::isaac_array_serde"))]
150 mem
: [w64
; RAND_SIZE
],
156 // Custom Debug implementation that does not expose the internal state
157 impl fmt
::Debug
for Isaac64Core
{
158 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
159 write
!(f
, "Isaac64Core {{}}")
163 impl BlockRngCore
for Isaac64Core
{
165 type Results
= IsaacArray
<Self::Item
>;
167 /// Refills the output buffer, `results`. See also the pseudocode desciption
168 /// of the algorithm in the [`Isaac64Rng`] documentation.
170 /// Optimisations used (similar to the reference implementation):
172 /// - The loop is unrolled 4 times, once for every constant of mix().
173 /// - The contents of the main loop are moved to a function `rngstep`, to
174 /// reduce code duplication.
175 /// - We use local variables for a and b, which helps with optimisations.
176 /// - We split the main loop in two, one that operates over 0..128 and one
177 /// over 128..256. This way we can optimise out the addition and modulus
178 /// from `s[i+128 mod 256]`.
179 /// - We maintain one index `i` and add `m` or `m2` as base (m2 for the
180 /// `s[i+128 mod 256]`), relying on the optimizer to turn it into pointer
182 /// - We fill `results` backwards. The reference implementation reads values
183 /// from `results` in reverse. We read them in the normal direction, to
184 /// make `fill_bytes` a memcopy. To maintain compatibility we fill in
187 /// [`Isaac64Rng`]: struct.Isaac64Rng.html
188 fn generate(&mut self, results
: &mut IsaacArray
<Self::Item
>) {
192 let mut b
= self.b
+ self.c
;
193 const MIDPOINT
: usize = RAND_SIZE
/ 2;
196 fn ind(mem
:&[w64
; RAND_SIZE
], v
: w64
, amount
: usize) -> w64
{
197 let index
= (v
>> amount
).0 as usize % RAND_SIZE
;
202 fn rngstep(mem
: &mut [w64
; RAND_SIZE
],
203 results
: &mut [u64; RAND_SIZE
],
210 let x
= mem
[base
+ m
];
211 *a
= mix
+ mem
[base
+ m2
];
212 let y
= *a
+ *b
+ ind(&mem
, x
, 3);
214 *b
= x
+ ind(&mem
, y
, 3 + RAND_SIZE_LEN
);
215 results
[RAND_SIZE
- 1 - base
- m
] = (*b
).0;
219 let mut m2
= MIDPOINT
;
220 for i
in (0..MIDPOINT
/4).map(|i
| i
* 4) {
221 rngstep(&mut self.mem
, results
, !(a ^
(a
<< 21)), &mut a
, &mut b
, i
+ 0, m
, m2
);
222 rngstep(&mut self.mem
, results
, a ^
(a
>> 5 ), &mut a
, &mut b
, i
+ 1, m
, m2
);
223 rngstep(&mut self.mem
, results
, a ^
(a
<< 12), &mut a
, &mut b
, i
+ 2, m
, m2
);
224 rngstep(&mut self.mem
, results
, a ^
(a
>> 33), &mut a
, &mut b
, i
+ 3, m
, m2
);
229 for i
in (0..MIDPOINT
/4).map(|i
| i
* 4) {
230 rngstep(&mut self.mem
, results
, !(a ^
(a
<< 21)), &mut a
, &mut b
, i
+ 0, m
, m2
);
231 rngstep(&mut self.mem
, results
, a ^
(a
>> 5 ), &mut a
, &mut b
, i
+ 1, m
, m2
);
232 rngstep(&mut self.mem
, results
, a ^
(a
<< 12), &mut a
, &mut b
, i
+ 2, m
, m2
);
233 rngstep(&mut self.mem
, results
, a ^
(a
>> 33), &mut a
, &mut b
, i
+ 3, m
, m2
);
242 /// Create a new ISAAC-64 random number generator.
243 fn init(mut mem
: [w64
; RAND_SIZE
], rounds
: u32) -> Self {
244 fn mix(a
: &mut w64
, b
: &mut w64
, c
: &mut w64
, d
: &mut w64
,
245 e
: &mut w64
, f
: &mut w64
, g
: &mut w64
, h
: &mut w64
) {
246 *a
-= *e
; *f ^
= *h
>> 9; *h
+= *a
;
247 *b
-= *f
; *g ^
= *a
<< 9; *a
+= *b
;
248 *c
-= *g
; *h ^
= *b
>> 23; *b
+= *c
;
249 *d
-= *h
; *a ^
= *c
<< 15; *c
+= *d
;
250 *e
-= *a
; *b ^
= *d
>> 14; *d
+= *e
;
251 *f
-= *b
; *c ^
= *e
<< 20; *e
+= *f
;
252 *g
-= *c
; *d ^
= *f
>> 17; *f
+= *g
;
253 *h
-= *d
; *e ^
= *g
<< 14; *g
+= *h
;
256 // These numbers are the result of initializing a...h with the
257 // fractional part of the golden ratio in binary (0x9e3779b97f4a7c13)
258 // and applying mix() 4 times.
259 let mut a
= w(0x647c4677a2884b7c);
260 let mut b
= w(0xb9f8b322c73ac862);
261 let mut c
= w(0x8c0ea5053d4712a0);
262 let mut d
= w(0xb29b2e824a595524);
263 let mut e
= w(0x82f053db8355e0ce);
264 let mut f
= w(0x48fe4a0fa5a09315);
265 let mut g
= w(0xae985bf2cbfc89ed);
266 let mut h
= w(0x98f5704f6c44c0ab);
268 // Normally this should do two passes, to make all of the seed effect
271 for i
in (0..RAND_SIZE
/8).map(|i
| i
* 8) {
272 a
+= mem
[i
]; b
+= mem
[i
+1];
273 c
+= mem
[i
+2]; d
+= mem
[i
+3];
274 e
+= mem
[i
+4]; f
+= mem
[i
+5];
275 g
+= mem
[i
+6]; h
+= mem
[i
+7];
276 mix(&mut a
, &mut b
, &mut c
, &mut d
,
277 &mut e
, &mut f
, &mut g
, &mut h
);
278 mem
[i
] = a
; mem
[i
+1] = b
;
279 mem
[i
+2] = c
; mem
[i
+3] = d
;
280 mem
[i
+4] = e
; mem
[i
+5] = f
;
281 mem
[i
+6] = g
; mem
[i
+7] = h
;
285 Self { mem, a: w(0), b: w(0), c: w(0) }
288 /// Create an ISAAC-64 random number generator using an `u64` as seed.
289 /// If `seed == 0` this will produce the same stream of random numbers as
290 /// the reference implementation when used unseeded.
291 #[deprecated(since="0.6.0", note="use SeedableRng::seed_from_u64 instead")]
292 pub fn new_from_u64(seed
: u64) -> Self {
293 Self::seed_from_u64(seed
)
297 impl SeedableRng
for Isaac64Core
{
298 type Seed
= [u8; 32];
300 fn from_seed(seed
: Self::Seed
) -> Self {
301 let mut seed_u64
= [0u64; 4];
302 le
::read_u64_into(&seed
, &mut seed_u64
);
303 // Convert the seed to `Wrapping<u64>` and zero-extend to `RAND_SIZE`.
304 let mut seed_extended
= [w(0); RAND_SIZE
];
305 for (x
, y
) in seed_extended
.iter_mut().zip(seed_u64
.iter()) {
308 Self::init(seed_extended
, 2)
311 fn seed_from_u64(seed
: u64) -> Self {
312 let mut key
= [w(0); RAND_SIZE
];
314 // Initialize with only one pass.
315 // A second pass does not improve the quality here, because all of the
316 // seed was already available in the first round.
317 // Not doing the second pass has the small advantage that if
318 // `seed == 0` this method produces exactly the same state as the
319 // reference implementation when used unseeded.
323 fn from_rng
<R
: RngCore
>(mut rng
: R
) -> Result
<Self, Error
> {
324 // Custom `from_rng` implementation that fills a seed with the same size
325 // as the entire state.
326 let mut seed
= [w(0u64); RAND_SIZE
];
328 let ptr
= seed
.as_mut_ptr() as *mut u8;
329 let slice
= slice
::from_raw_parts_mut(ptr
, RAND_SIZE
* 8);
330 rng
.try_fill_bytes(slice
)?
;
332 for i
in seed
.iter_mut() {
336 Ok(Self::init(seed
, 2))
342 use {RngCore, SeedableRng}
;
343 use super::Isaac64Rng
;
346 fn test_isaac64_construction() {
347 // Test that various construction techniques produce a working RNG.
348 let seed
= [1,0,0,0, 23,0,0,0, 200,1,0,0, 210,30,0,0,
349 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0];
350 let mut rng1
= Isaac64Rng
::from_seed(seed
);
351 assert_eq
!(rng1
.next_u64(), 14964555543728284049);
353 let mut rng2
= Isaac64Rng
::from_rng(rng1
).unwrap();
354 assert_eq
!(rng2
.next_u64(), 919595328260451758);
358 fn test_isaac64_true_values_64() {
359 let seed
= [1,0,0,0, 0,0,0,0, 23,0,0,0, 0,0,0,0,
360 200,1,0,0, 0,0,0,0, 210,30,0,0, 0,0,0,0];
361 let mut rng1
= Isaac64Rng
::from_seed(seed
);
362 let mut results
= [0u64; 10];
363 for i
in results
.iter_mut() { *i = rng1.next_u64(); }
365 15071495833797886820, 7720185633435529318,
366 10836773366498097981, 5414053799617603544,
367 12890513357046278984, 17001051845652595546,
368 9240803642279356310, 12558996012687158051,
369 14673053937227185542, 1677046725350116783];
370 assert_eq
!(results
, expected
);
372 let seed
= [57,48,0,0, 0,0,0,0, 50,9,1,0, 0,0,0,0,
373 49,212,0,0, 0,0,0,0, 148,38,0,0, 0,0,0,0];
374 let mut rng2
= Isaac64Rng
::from_seed(seed
);
375 // skip forward to the 10000th number
376 for _
in 0..10000 { rng2.next_u64(); }
378 for i
in results
.iter_mut() { *i = rng2.next_u64(); }
380 18143823860592706164, 8491801882678285927, 2699425367717515619,
381 17196852593171130876, 2606123525235546165, 15790932315217671084,
382 596345674630742204, 9947027391921273664, 11788097613744130851,
383 10391409374914919106];
384 assert_eq
!(results
, expected
);
388 fn test_isaac64_true_values_32() {
389 let seed
= [1,0,0,0, 0,0,0,0, 23,0,0,0, 0,0,0,0,
390 200,1,0,0, 0,0,0,0, 210,30,0,0, 0,0,0,0];
391 let mut rng
= Isaac64Rng
::from_seed(seed
);
392 let mut results
= [0u32; 12];
393 for i
in results
.iter_mut() { *i = rng.next_u32(); }
394 // Subset of above values, as an LE u32 sequence
396 3477963620, 3509106075,
397 687845478, 1797495790,
398 227048253, 2523132918,
399 4044335064, 1260557630,
400 4079741768, 3001306521,
401 69157722, 3958365844];
402 assert_eq
!(results
, expected
);
406 fn test_isaac64_true_values_mixed() {
407 let seed
= [1,0,0,0, 0,0,0,0, 23,0,0,0, 0,0,0,0,
408 200,1,0,0, 0,0,0,0, 210,30,0,0, 0,0,0,0];
409 let mut rng
= Isaac64Rng
::from_seed(seed
);
410 // Test alternating between `next_u64` and `next_u32` works as expected.
411 // Values are the same as `test_isaac64_true_values` and
412 // `test_isaac64_true_values_32`.
413 assert_eq
!(rng
.next_u64(), 15071495833797886820);
414 assert_eq
!(rng
.next_u32(), 687845478);
415 assert_eq
!(rng
.next_u32(), 1797495790);
416 assert_eq
!(rng
.next_u64(), 10836773366498097981);
417 assert_eq
!(rng
.next_u32(), 4044335064);
419 assert_eq
!(rng
.next_u64(), 12890513357046278984);
420 assert_eq
!(rng
.next_u32(), 69157722);
424 fn test_isaac64_true_bytes() {
425 let seed
= [1,0,0,0, 0,0,0,0, 23,0,0,0, 0,0,0,0,
426 200,1,0,0, 0,0,0,0, 210,30,0,0, 0,0,0,0];
427 let mut rng
= Isaac64Rng
::from_seed(seed
);
428 let mut results
= [0u8; 32];
429 rng
.fill_bytes(&mut results
);
430 // Same as first values in test_isaac64_true_values as bytes in LE order
431 let expected
= [100, 131, 77, 207, 155, 181, 40, 209,
432 102, 176, 255, 40, 238, 155, 35, 107,
433 61, 123, 136, 13, 246, 243, 99, 150,
434 216, 167, 15, 241, 62, 149, 34, 75];
435 assert_eq
!(results
, expected
);
439 fn test_isaac64_new_uninitialized() {
440 // Compare the results from initializing `IsaacRng` with
441 // `seed_from_u64(0)`, to make sure it is the same as the reference
442 // implementation when used uninitialized.
443 // Note: We only test the first 16 integers, not the full 256 of the
445 let mut rng
= Isaac64Rng
::seed_from_u64(0);
446 let mut results
= [0u64; 16];
447 for i
in results
.iter_mut() { *i = rng.next_u64(); }
448 let expected
: [u64; 16] = [
449 0xF67DFBA498E4937C, 0x84A5066A9204F380, 0xFEE34BD5F5514DBB,
450 0x4D1664739B8F80D6, 0x8607459AB52A14AA, 0x0E78BC5A98529E49,
451 0xFE5332822AD13777, 0x556C27525E33D01A, 0x08643CA615F3149F,
452 0xD0771FAF3CB04714, 0x30E86F68A37B008D, 0x3074EBC0488A3ADF,
453 0x270645EA7A2790BC, 0x5601A0A8D3763C6A, 0x2F83071F53F325DD,
455 assert_eq
!(results
, expected
);
459 fn test_isaac64_clone() {
460 let seed
= [1,0,0,0, 0,0,0,0, 23,0,0,0, 0,0,0,0,
461 200,1,0,0, 0,0,0,0, 210,30,0,0, 0,0,0,0];
462 let mut rng1
= Isaac64Rng
::from_seed(seed
);
463 let mut rng2
= rng1
.clone();
465 assert_eq
!(rng1
.next_u64(), rng2
.next_u64());
470 #[cfg(all(feature="serde1", feature="std"))]
471 fn test_isaac64_serde() {
473 use std
::io
::{BufWriter, BufReader}
;
475 let seed
= [1,0,0,0, 23,0,0,0, 200,1,0,0, 210,30,0,0,
476 57,48,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0];
477 let mut rng
= Isaac64Rng
::from_seed(seed
);
479 let buf
: Vec
<u8> = Vec
::new();
480 let mut buf
= BufWriter
::new(buf
);
481 bincode
::serialize_into(&mut buf
, &rng
).expect("Could not serialize");
483 let buf
= buf
.into_inner().unwrap();
484 let mut read
= BufReader
::new(&buf
[..]);
485 let mut deserialized
: Isaac64Rng
= bincode
::deserialize_from(&mut read
).expect("Could not deserialize");
487 for _
in 0..300 { // more than the 256 buffered results
488 assert_eq
!(rng
.next_u64(), deserialized
.next_u64());