1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://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 random number generator.
13 #![allow(non_camel_case_types)]
16 use std
::iter
::repeat
;
17 use std
::num
::Wrapping
as w
;
20 use {Rng, SeedableRng, Rand, w32, w64}
;
22 const RAND_SIZE_LEN
: usize = 8;
23 const RAND_SIZE
: u32 = 1 << RAND_SIZE_LEN
;
24 const RAND_SIZE_USIZE
: usize = 1 << RAND_SIZE_LEN
;
26 /// A random number generator that uses the ISAAC algorithm[1].
28 /// The ISAAC algorithm is generally accepted as suitable for
29 /// cryptographic purposes, but this implementation has not be
30 /// verified as such. Prefer a generator like `OsRng` that defers to
31 /// the operating system for cases that need high security.
33 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
34 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
38 rsl
: [w32
; RAND_SIZE_USIZE
],
39 mem
: [w32
; RAND_SIZE_USIZE
],
45 static EMPTY
: IsaacRng
= IsaacRng
{
47 rsl
: [w(0); RAND_SIZE_USIZE
],
48 mem
: [w(0); RAND_SIZE_USIZE
],
49 a
: w(0), b
: w(0), c
: w(0),
54 /// Create an ISAAC random number generator using the default
56 pub fn new_unseeded() -> IsaacRng
{
62 /// Initialises `self`. If `use_rsl` is true, then use the current value
63 /// of `rsl` as a seed, otherwise construct one algorithmically (not
65 fn init(&mut self, use_rsl
: bool
) {
66 let mut a
= w(0x9e3779b9);
77 a
=a^
(b
<<11); d
=d
+a
; b
=b
+c
;
78 b
=b^
(c
>>2); e
=e
+b
; c
=c
+d
;
79 c
=c^
(d
<<8); f
=f
+c
; d
=d
+e
;
80 d
=d^
(e
>>16); g
=g
+d
; e
=e
+f
;
81 e
=e^
(f
<<10); h
=h
+e
; f
=f
+g
;
82 f
=f^
(g
>>4); a
=a
+f
; g
=g
+h
;
83 g
=g^
(h
<<8); b
=b
+g
; h
=h
+a
;
84 h
=h^
(a
>>9); c
=c
+h
; a
=a
+b
;
93 macro_rules
! memloop
{
95 for i
in (0..RAND_SIZE_USIZE
/8).map(|i
| i
* 8) {
96 a
=a
+$arr
[i
]; b
=b
+$arr
[i
+1];
97 c
=c
+$arr
[i
+2]; d
=d
+$arr
[i
+3];
98 e
=e
+$arr
[i
+4]; f
=f
+$arr
[i
+5];
99 g
=g
+$arr
[i
+6]; h
=h
+$arr
[i
+7];
101 self.mem
[i
]=a
; self.mem
[i
+1]=b
;
102 self.mem
[i
+2]=c
; self.mem
[i
+3]=d
;
103 self.mem
[i
+4]=e
; self.mem
[i
+5]=f
;
104 self.mem
[i
+6]=g
; self.mem
[i
+7]=h
;
112 for i
in (0..RAND_SIZE_USIZE
/8).map(|i
| i
* 8) {
114 self.mem
[i
]=a
; self.mem
[i
+1]=b
;
115 self.mem
[i
+2]=c
; self.mem
[i
+3]=d
;
116 self.mem
[i
+4]=e
; self.mem
[i
+5]=f
;
117 self.mem
[i
+6]=g
; self.mem
[i
+7]=h
;
124 /// Refills the output buffer (`self.rsl`)
126 fn isaac(&mut self) {
127 self.c
= self.c
+ w(1);
130 let mut b
= self.b
+ self.c
;
132 const MIDPOINT
: usize = RAND_SIZE_USIZE
/ 2;
135 ($x
:expr
) => ( self.mem
[($x
>> 2usize
).0 as usize & (RAND_SIZE_USIZE
- 1)] )
138 let r
= [(0, MIDPOINT
), (MIDPOINT
, 0)];
139 for &(mr_offset
, m2_offset
) in r
.iter() {
141 macro_rules
! rngstepp
{
142 ($j
:expr
, $shift
:expr
) => {{
144 let mix
= a
<< $shift
;
146 let x
= self.mem
[base
+ mr_offset
];
147 a
= (a ^ mix
) + self.mem
[base
+ m2_offset
];
148 let y
= ind
!(x
) + a
+ b
;
149 self.mem
[base
+ mr_offset
] = y
;
151 b
= ind
!(y
>> RAND_SIZE_LEN
) + x
;
152 self.rsl
[base
+ mr_offset
] = b
;
156 macro_rules
! rngstepn
{
157 ($j
:expr
, $shift
:expr
) => {{
159 let mix
= a
>> $shift
;
161 let x
= self.mem
[base
+ mr_offset
];
162 a
= (a ^ mix
) + self.mem
[base
+ m2_offset
];
163 let y
= ind
!(x
) + a
+ b
;
164 self.mem
[base
+ mr_offset
] = y
;
166 b
= ind
!(y
>> RAND_SIZE_LEN
) + x
;
167 self.rsl
[base
+ mr_offset
] = b
;
171 for i
in (0..MIDPOINT
/4).map(|i
| i
* 4) {
172 rngstepp
!(i
+ 0, 13);
175 rngstepn
!(i
+ 3, 16);
181 self.cnt
= RAND_SIZE
;
185 // Cannot be derived because [u32; 256] does not implement Clone
186 impl Clone
for IsaacRng
{
187 fn clone(&self) -> IsaacRng
{
192 impl Rng
for IsaacRng
{
194 fn next_u32(&mut self) -> u32 {
196 // make some more numbers
201 // self.cnt is at most RAND_SIZE, but that is before the
202 // subtraction above. We want to index without bounds
203 // checking, but this could lead to incorrect code if someone
204 // misrefactors, so we check, sometimes.
206 // (Changes here should be reflected in Isaac64Rng.next_u64.)
207 debug_assert
!(self.cnt
< RAND_SIZE
);
209 // (the % is cheaply telling the optimiser that we're always
210 // in bounds, without unsafe. NB. this is a power of two, so
211 // it optimises to a bitwise mask).
212 self.rsl
[(self.cnt
% RAND_SIZE
) as usize].0
216 impl<'a
> SeedableRng
<&'a
[u32]> for IsaacRng
{
217 fn reseed(&mut self, seed
: &'a
[u32]) {
218 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
219 // - 1], 0, 0, ...], to fill rng.rsl.
220 let seed_iter
= seed
.iter().map(|&x
| x
).chain(repeat(0u32));
222 for (rsl_elem
, seed_elem
) in self.rsl
.iter_mut().zip(seed_iter
) {
223 *rsl_elem
= w(seed_elem
);
233 /// Create an ISAAC random number generator with a seed. This can
234 /// be any length, although the maximum number of elements used is
235 /// 256 and any more will be silently ignored. A generator
236 /// constructed with a given seed will generate the same sequence
237 /// of values as all other generators constructed with that seed.
238 fn from_seed(seed
: &'a
[u32]) -> IsaacRng
{
245 impl Rand
for IsaacRng
{
246 fn rand
<R
: Rng
>(other
: &mut R
) -> IsaacRng
{
249 let ptr
= ret
.rsl
.as_mut_ptr() as *mut u8;
251 let slice
= slice
::from_raw_parts_mut(ptr
, RAND_SIZE_USIZE
* 4);
252 other
.fill_bytes(slice
);
264 impl fmt
::Debug
for IsaacRng
{
265 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
266 write
!(f
, "IsaacRng {{}}")
270 const RAND_SIZE_64_LEN
: usize = 8;
271 const RAND_SIZE_64
: usize = 1 << RAND_SIZE_64_LEN
;
273 /// A random number generator that uses ISAAC-64[1], the 64-bit
274 /// variant of the ISAAC algorithm.
276 /// The ISAAC algorithm is generally accepted as suitable for
277 /// cryptographic purposes, but this implementation has not be
278 /// verified as such. Prefer a generator like `OsRng` that defers to
279 /// the operating system for cases that need high security.
281 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
282 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
284 pub struct Isaac64Rng
{
286 rsl
: [w64
; RAND_SIZE_64
],
287 mem
: [w64
; RAND_SIZE_64
],
293 static EMPTY_64
: Isaac64Rng
= Isaac64Rng
{
295 rsl
: [w(0); RAND_SIZE_64
],
296 mem
: [w(0); RAND_SIZE_64
],
297 a
: w(0), b
: w(0), c
: w(0),
301 /// Create a 64-bit ISAAC random number generator using the
302 /// default fixed seed.
303 pub fn new_unseeded() -> Isaac64Rng
{
304 let mut rng
= EMPTY_64
;
309 /// Initialises `self`. If `use_rsl` is true, then use the current value
310 /// of `rsl` as a seed, otherwise construct one algorithmically (not
312 fn init(&mut self, use_rsl
: bool
) {
315 let mut $var
= w(0x9e3779b97f4a7c13);
318 init
!(a
); init
!(b
); init
!(c
); init
!(d
);
319 init
!(e
); init
!(f
); init
!(g
); init
!(h
);
323 a
=a
-e
; f
=f^
(h
>>9); h
=h
+a
;
324 b
=b
-f
; g
=g^
(a
<<9); a
=a
+b
;
325 c
=c
-g
; h
=h^
(b
>>23); b
=b
+c
;
326 d
=d
-h
; a
=a^
(c
<<15); c
=c
+d
;
327 e
=e
-a
; b
=b^
(d
>>14); d
=d
+e
;
328 f
=f
-b
; c
=c^
(e
<<20); e
=e
+f
;
329 g
=g
-c
; d
=d^
(f
>>17); f
=f
+g
;
330 h
=h
-d
; e
=e^
(g
<<14); g
=g
+h
;
339 macro_rules
! memloop
{
341 for i
in (0..RAND_SIZE_64
/ 8).map(|i
| i
* 8) {
342 a
=a
+$arr
[i
]; b
=b
+$arr
[i
+1];
343 c
=c
+$arr
[i
+2]; d
=d
+$arr
[i
+3];
344 e
=e
+$arr
[i
+4]; f
=f
+$arr
[i
+5];
345 g
=g
+$arr
[i
+6]; h
=h
+$arr
[i
+7];
347 self.mem
[i
]=a
; self.mem
[i
+1]=b
;
348 self.mem
[i
+2]=c
; self.mem
[i
+3]=d
;
349 self.mem
[i
+4]=e
; self.mem
[i
+5]=f
;
350 self.mem
[i
+6]=g
; self.mem
[i
+7]=h
;
358 for i
in (0..RAND_SIZE_64
/ 8).map(|i
| i
* 8) {
360 self.mem
[i
]=a
; self.mem
[i
+1]=b
;
361 self.mem
[i
+2]=c
; self.mem
[i
+3]=d
;
362 self.mem
[i
+4]=e
; self.mem
[i
+5]=f
;
363 self.mem
[i
+6]=g
; self.mem
[i
+7]=h
;
370 /// Refills the output buffer (`self.rsl`)
371 fn isaac64(&mut self) {
372 self.c
= self.c
+ w(1);
375 let mut b
= self.b
+ self.c
;
376 const MIDPOINT
: usize = RAND_SIZE_64
/ 2;
377 const MP_VEC
: [(usize, usize); 2] = [(0,MIDPOINT
), (MIDPOINT
, 0)];
380 *self.mem
.get_unchecked((($x
>> 3usize
).0 as usize) & (RAND_SIZE_64
- 1))
384 for &(mr_offset
, m2_offset
) in MP_VEC
.iter() {
385 for base
in (0..MIDPOINT
/ 4).map(|i
| i
* 4) {
387 macro_rules
! rngstepp
{
388 ($j
:expr
, $shift
:expr
) => {{
389 let base
= base
+ $j
;
390 let mix
= a ^
(a
<< $shift
);
391 let mix
= if $j
== 0 {!mix}
else {mix}
;
394 let x
= *self.mem
.get_unchecked(base
+ mr_offset
);
395 a
= mix
+ *self.mem
.get_unchecked(base
+ m2_offset
);
396 let y
= ind
!(x
) + a
+ b
;
397 *self.mem
.get_unchecked_mut(base
+ mr_offset
) = y
;
399 b
= ind
!(y
>> RAND_SIZE_64_LEN
) + x
;
400 *self.rsl
.get_unchecked_mut(base
+ mr_offset
) = b
;
405 macro_rules
! rngstepn
{
406 ($j
:expr
, $shift
:expr
) => {{
407 let base
= base
+ $j
;
408 let mix
= a ^
(a
>> $shift
);
409 let mix
= if $j
== 0 {!mix}
else {mix}
;
412 let x
= *self.mem
.get_unchecked(base
+ mr_offset
);
413 a
= mix
+ *self.mem
.get_unchecked(base
+ m2_offset
);
414 let y
= ind
!(x
) + a
+ b
;
415 *self.mem
.get_unchecked_mut(base
+ mr_offset
) = y
;
417 b
= ind
!(y
>> RAND_SIZE_64_LEN
) + x
;
418 *self.rsl
.get_unchecked_mut(base
+ mr_offset
) = b
;
432 self.cnt
= RAND_SIZE_64
;
436 // Cannot be derived because [u32; 256] does not implement Clone
437 impl Clone
for Isaac64Rng
{
438 fn clone(&self) -> Isaac64Rng
{
443 impl Rng
for Isaac64Rng
{
444 // FIXME #7771: having next_u32 like this should be unnecessary
446 fn next_u32(&mut self) -> u32 {
447 self.next_u64() as u32
451 fn next_u64(&mut self) -> u64 {
453 // make some more numbers
458 // See corresponding location in IsaacRng.next_u32 for
460 debug_assert
!(self.cnt
< RAND_SIZE_64
);
461 self.rsl
[(self.cnt
% RAND_SIZE_64
) as usize].0
465 impl<'a
> SeedableRng
<&'a
[u64]> for Isaac64Rng
{
466 fn reseed(&mut self, seed
: &'a
[u64]) {
467 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
468 // - 1], 0, 0, ...], to fill rng.rsl.
469 let seed_iter
= seed
.iter().map(|&x
| x
).chain(repeat(0u64));
471 for (rsl_elem
, seed_elem
) in self.rsl
.iter_mut().zip(seed_iter
) {
472 *rsl_elem
= w(seed_elem
);
482 /// Create an ISAAC random number generator with a seed. This can
483 /// be any length, although the maximum number of elements used is
484 /// 256 and any more will be silently ignored. A generator
485 /// constructed with a given seed will generate the same sequence
486 /// of values as all other generators constructed with that seed.
487 fn from_seed(seed
: &'a
[u64]) -> Isaac64Rng
{
488 let mut rng
= EMPTY_64
;
494 impl Rand
for Isaac64Rng
{
495 fn rand
<R
: Rng
>(other
: &mut R
) -> Isaac64Rng
{
496 let mut ret
= EMPTY_64
;
498 let ptr
= ret
.rsl
.as_mut_ptr() as *mut u8;
500 let slice
= slice
::from_raw_parts_mut(ptr
, RAND_SIZE_64
* 8);
501 other
.fill_bytes(slice
);
513 impl fmt
::Debug
for Isaac64Rng
{
514 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
515 write
!(f
, "Isaac64Rng {{}}")
521 use {Rng, SeedableRng}
;
522 use super::{IsaacRng, Isaac64Rng}
;
525 fn test_rng_32_rand_seeded() {
526 let s
= ::test
::rng().gen_iter
::<u32>().take(256).collect
::<Vec
<u32>>();
527 let mut ra
: IsaacRng
= SeedableRng
::from_seed(&s
[..]);
528 let mut rb
: IsaacRng
= SeedableRng
::from_seed(&s
[..]);
529 assert
!(::test
::iter_eq(ra
.gen_ascii_chars().take(100),
530 rb
.gen_ascii_chars().take(100)));
533 fn test_rng_64_rand_seeded() {
534 let s
= ::test
::rng().gen_iter
::<u64>().take(256).collect
::<Vec
<u64>>();
535 let mut ra
: Isaac64Rng
= SeedableRng
::from_seed(&s
[..]);
536 let mut rb
: Isaac64Rng
= SeedableRng
::from_seed(&s
[..]);
537 assert
!(::test
::iter_eq(ra
.gen_ascii_chars().take(100),
538 rb
.gen_ascii_chars().take(100)));
542 fn test_rng_32_seeded() {
543 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
544 let mut ra
: IsaacRng
= SeedableRng
::from_seed(seed
);
545 let mut rb
: IsaacRng
= SeedableRng
::from_seed(seed
);
546 assert
!(::test
::iter_eq(ra
.gen_ascii_chars().take(100),
547 rb
.gen_ascii_chars().take(100)));
550 fn test_rng_64_seeded() {
551 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
552 let mut ra
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
553 let mut rb
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
554 assert
!(::test
::iter_eq(ra
.gen_ascii_chars().take(100),
555 rb
.gen_ascii_chars().take(100)));
559 fn test_rng_32_reseed() {
560 let s
= ::test
::rng().gen_iter
::<u32>().take(256).collect
::<Vec
<u32>>();
561 let mut r
: IsaacRng
= SeedableRng
::from_seed(&s
[..]);
562 let string1
: String
= r
.gen_ascii_chars().take(100).collect();
566 let string2
: String
= r
.gen_ascii_chars().take(100).collect();
567 assert_eq
!(string1
, string2
);
570 fn test_rng_64_reseed() {
571 let s
= ::test
::rng().gen_iter
::<u64>().take(256).collect
::<Vec
<u64>>();
572 let mut r
: Isaac64Rng
= SeedableRng
::from_seed(&s
[..]);
573 let string1
: String
= r
.gen_ascii_chars().take(100).collect();
577 let string2
: String
= r
.gen_ascii_chars().take(100).collect();
578 assert_eq
!(string1
, string2
);
582 fn test_rng_32_true_values() {
583 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
584 let mut ra
: IsaacRng
= SeedableRng
::from_seed(seed
);
585 // Regression test that isaac is actually using the above vector
586 let v
= (0..10).map(|_
| ra
.next_u32()).collect
::<Vec
<_
>>();
588 vec
!(2558573138, 873787463, 263499565, 2103644246, 3595684709,
589 4203127393, 264982119, 2765226902, 2737944514, 3900253796));
591 let seed
: &[_
] = &[12345, 67890, 54321, 9876];
592 let mut rb
: IsaacRng
= SeedableRng
::from_seed(seed
);
593 // skip forward to the 10000th number
594 for _
in 0..10000 { rb.next_u32(); }
596 let v
= (0..10).map(|_
| rb
.next_u32()).collect
::<Vec
<_
>>();
598 vec
!(3676831399, 3183332890, 2834741178, 3854698763, 2717568474,
599 1576568959, 3507990155, 179069555, 141456972, 2478885421));
602 fn test_rng_64_true_values() {
603 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
604 let mut ra
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
605 // Regression test that isaac is actually using the above vector
606 let v
= (0..10).map(|_
| ra
.next_u64()).collect
::<Vec
<_
>>();
608 vec
!(547121783600835980, 14377643087320773276, 17351601304698403469,
609 1238879483818134882, 11952566807690396487, 13970131091560099343,
610 4469761996653280935, 15552757044682284409, 6860251611068737823,
611 13722198873481261842));
613 let seed
: &[_
] = &[12345, 67890, 54321, 9876];
614 let mut rb
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
615 // skip forward to the 10000th number
616 for _
in 0..10000 { rb.next_u64(); }
618 let v
= (0..10).map(|_
| rb
.next_u64()).collect
::<Vec
<_
>>();
620 vec
!(18143823860592706164, 8491801882678285927, 2699425367717515619,
621 17196852593171130876, 2606123525235546165, 15790932315217671084,
622 596345674630742204, 9947027391921273664, 11788097613744130851,
623 10391409374914919106));
627 fn test_rng_clone() {
628 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
629 let mut rng
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
630 let mut clone
= rng
.clone();
632 assert_eq
!(rng
.next_u64(), clone
.next_u64());