]>
git.proxmox.com Git - rustc.git/blob - src/librand/isaac.rs
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 core
::iter
::repeat
;
17 use core
::num
::Wrapping
as w
;
19 use {Rand, Rng, SeedableRng}
;
24 const RAND_SIZE_LEN
: usize = 8;
25 const RAND_SIZE
: u32 = 1 << RAND_SIZE_LEN
;
26 const RAND_SIZE_USIZE
: usize = 1 << RAND_SIZE_LEN
;
28 /// A random number generator that uses the ISAAC algorithm[1].
30 /// The ISAAC algorithm is generally accepted as suitable for
31 /// cryptographic purposes, but this implementation has not be
32 /// verified as such. Prefer a generator like `OsRng` that defers to
33 /// the operating system for cases that need high security.
35 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
36 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
40 rsl
: [w32
; RAND_SIZE_USIZE
],
41 mem
: [w32
; RAND_SIZE_USIZE
],
47 static EMPTY
: IsaacRng
= IsaacRng
{
49 rsl
: [w(0); RAND_SIZE_USIZE
],
50 mem
: [w(0); RAND_SIZE_USIZE
],
57 /// Create an ISAAC random number generator using the default
59 pub fn new_unseeded() -> IsaacRng
{
65 /// Initialises `self`. If `use_rsl` is true, then use the current value
66 /// of `rsl` as a seed, otherwise construct one algorithmically (not
68 fn init(&mut self, use_rsl
: bool
) {
69 let mut a
= w(0x9e3779b9);
119 macro_rules
! memloop
{
121 for i
in (0..RAND_SIZE_USIZE
).step_by(8) {
146 for i
in (0..RAND_SIZE_USIZE
).step_by(8) {
162 /// Refills the output buffer (`self.rsl`)
164 fn isaac(&mut self) {
165 self.c
= self.c
+ w(1);
168 let mut b
= self.b
+ self.c
;
170 const MIDPOINT
: usize = RAND_SIZE_USIZE
/ 2;
173 ($x
:expr
) => (self.mem
[($x
>> 2).0 as usize & (RAND_SIZE_USIZE
- 1)] )
176 let r
= [(0, MIDPOINT
), (MIDPOINT
, 0)];
177 for &(mr_offset
, m2_offset
) in &r
{
179 macro_rules
! rngstepp
{
180 ($j
:expr
, $shift
:expr
) => {{
182 let mix
= a
<< $shift
;
184 let x
= self.mem
[base
+ mr_offset
];
185 a
= (a ^ mix
) + self.mem
[base
+ m2_offset
];
186 let y
= ind
!(x
) + a
+ b
;
187 self.mem
[base
+ mr_offset
] = y
;
189 b
= ind
!(y
>> RAND_SIZE_LEN
) + x
;
190 self.rsl
[base
+ mr_offset
] = b
;
194 macro_rules
! rngstepn
{
195 ($j
:expr
, $shift
:expr
) => {{
197 let mix
= a
>> $shift
;
199 let x
= self.mem
[base
+ mr_offset
];
200 a
= (a ^ mix
) + self.mem
[base
+ m2_offset
];
201 let y
= ind
!(x
) + a
+ b
;
202 self.mem
[base
+ mr_offset
] = y
;
204 b
= ind
!(y
>> RAND_SIZE_LEN
) + x
;
205 self.rsl
[base
+ mr_offset
] = b
;
209 for i
in (0..MIDPOINT
).step_by(4) {
210 rngstepp
!(i
+ 0, 13);
213 rngstepn
!(i
+ 3, 16);
219 self.cnt
= RAND_SIZE
;
223 // Cannot be derived because [u32; 256] does not implement Clone
224 impl Clone
for IsaacRng
{
225 fn clone(&self) -> IsaacRng
{
230 impl Rng
for IsaacRng
{
232 fn next_u32(&mut self) -> u32 {
234 // make some more numbers
239 // self.cnt is at most RAND_SIZE, but that is before the
240 // subtraction above. We want to index without bounds
241 // checking, but this could lead to incorrect code if someone
242 // misrefactors, so we check, sometimes.
244 // (Changes here should be reflected in Isaac64Rng.next_u64.)
245 debug_assert
!(self.cnt
< RAND_SIZE
);
247 // (the % is cheaply telling the optimiser that we're always
248 // in bounds, without unsafe. NB. this is a power of two, so
249 // it optimises to a bitwise mask).
250 self.rsl
[(self.cnt
% RAND_SIZE
) as usize].0
254 impl<'a
> SeedableRng
<&'a
[u32]> for IsaacRng
{
255 fn reseed(&mut self, seed
: &'a
[u32]) {
256 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
257 // - 1], 0, 0, ...], to fill rng.rsl.
258 let seed_iter
= seed
.iter().cloned().chain(repeat(0));
260 for (rsl_elem
, seed_elem
) in self.rsl
.iter_mut().zip(seed_iter
) {
261 *rsl_elem
= w(seed_elem
);
271 /// Create an ISAAC random number generator with a seed. This can
272 /// be any length, although the maximum number of elements used is
273 /// 256 and any more will be silently ignored. A generator
274 /// constructed with a given seed will generate the same sequence
275 /// of values as all other generators constructed with that seed.
276 fn from_seed(seed
: &'a
[u32]) -> IsaacRng
{
283 impl Rand
for IsaacRng
{
284 fn rand
<R
: Rng
>(other
: &mut R
) -> IsaacRng
{
287 let ptr
= ret
.rsl
.as_mut_ptr() as *mut u8;
289 let slice
= slice
::from_raw_parts_mut(ptr
, RAND_SIZE_USIZE
* 4);
290 other
.fill_bytes(slice
);
302 const RAND_SIZE_64_LEN
: usize = 8;
303 const RAND_SIZE_64
: usize = 1 << RAND_SIZE_64_LEN
;
305 /// A random number generator that uses ISAAC-64[1], the 64-bit
306 /// variant of the ISAAC algorithm.
308 /// The ISAAC algorithm is generally accepted as suitable for
309 /// cryptographic purposes, but this implementation has not be
310 /// verified as such. Prefer a generator like `OsRng` that defers to
311 /// the operating system for cases that need high security.
313 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
314 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
316 pub struct Isaac64Rng
{
318 rsl
: [w64
; RAND_SIZE_64
],
319 mem
: [w64
; RAND_SIZE_64
],
325 static EMPTY_64
: Isaac64Rng
= Isaac64Rng
{
327 rsl
: [w(0); RAND_SIZE_64
],
328 mem
: [w(0); RAND_SIZE_64
],
335 /// Create a 64-bit ISAAC random number generator using the
336 /// default fixed seed.
337 pub fn new_unseeded() -> Isaac64Rng
{
338 let mut rng
= EMPTY_64
;
343 /// Initialises `self`. If `use_rsl` is true, then use the current value
344 /// of `rsl` as a seed, otherwise construct one algorithmically (not
346 fn init(&mut self, use_rsl
: bool
) {
349 let mut $var
= w(0x9e3779b97f4a7c13);
402 macro_rules
! memloop
{
404 for i
in (0..RAND_SIZE_64
/ 8).map(|i
| i
* 8) {
429 for i
in (0..RAND_SIZE_64
/ 8).map(|i
| i
* 8) {
445 /// Refills the output buffer (`self.rsl`)
446 fn isaac64(&mut self) {
447 self.c
= self.c
+ w(1);
450 let mut b
= self.b
+ self.c
;
451 const MIDPOINT
: usize = RAND_SIZE_64
/ 2;
452 const MP_VEC
: [(usize, usize); 2] = [(0, MIDPOINT
), (MIDPOINT
, 0)];
455 *self.mem
.get_unchecked((($x
>> 3).0 as usize) & (RAND_SIZE_64
- 1))
459 for &(mr_offset
, m2_offset
) in &MP_VEC
{
460 for base
in (0..MIDPOINT
/ 4).map(|i
| i
* 4) {
462 macro_rules
! rngstepp
{
463 ($j
:expr
, $shift
:expr
) => {{
464 let base
= base
+ $j
;
465 let mix
= a ^
(a
<< $shift
);
466 let mix
= if $j
== 0 {!mix}
else {mix}
;
469 let x
= *self.mem
.get_unchecked(base
+ mr_offset
);
470 a
= mix
+ *self.mem
.get_unchecked(base
+ m2_offset
);
471 let y
= ind
!(x
) + a
+ b
;
472 *self.mem
.get_unchecked_mut(base
+ mr_offset
) = y
;
474 b
= ind
!(y
>> RAND_SIZE_64_LEN
) + x
;
475 *self.rsl
.get_unchecked_mut(base
+ mr_offset
) = b
;
480 macro_rules
! rngstepn
{
481 ($j
:expr
, $shift
:expr
) => {{
482 let base
= base
+ $j
;
483 let mix
= a ^
(a
>> $shift
);
484 let mix
= if $j
== 0 {!mix}
else {mix}
;
487 let x
= *self.mem
.get_unchecked(base
+ mr_offset
);
488 a
= mix
+ *self.mem
.get_unchecked(base
+ m2_offset
);
489 let y
= ind
!(x
) + a
+ b
;
490 *self.mem
.get_unchecked_mut(base
+ mr_offset
) = y
;
492 b
= ind
!(y
>> RAND_SIZE_64_LEN
) + x
;
493 *self.rsl
.get_unchecked_mut(base
+ mr_offset
) = b
;
507 self.cnt
= RAND_SIZE_64
;
511 // Cannot be derived because [u32; 256] does not implement Clone
512 impl Clone
for Isaac64Rng
{
513 fn clone(&self) -> Isaac64Rng
{
518 impl Rng
for Isaac64Rng
{
519 // FIXME #7771: having next_u32 like this should be unnecessary
521 fn next_u32(&mut self) -> u32 {
522 self.next_u64() as u32
526 fn next_u64(&mut self) -> u64 {
528 // make some more numbers
533 // See corresponding location in IsaacRng.next_u32 for
535 debug_assert
!(self.cnt
< RAND_SIZE_64
);
536 self.rsl
[(self.cnt
% RAND_SIZE_64
) as usize].0
540 impl<'a
> SeedableRng
<&'a
[u64]> for Isaac64Rng
{
541 fn reseed(&mut self, seed
: &'a
[u64]) {
542 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
543 // - 1], 0, 0, ...], to fill rng.rsl.
544 let seed_iter
= seed
.iter().cloned().chain(repeat(0));
546 for (rsl_elem
, seed_elem
) in self.rsl
.iter_mut().zip(seed_iter
) {
547 *rsl_elem
= w(seed_elem
);
557 /// Create an ISAAC random number generator with a seed. This can
558 /// be any length, although the maximum number of elements used is
559 /// 256 and any more will be silently ignored. A generator
560 /// constructed with a given seed will generate the same sequence
561 /// of values as all other generators constructed with that seed.
562 fn from_seed(seed
: &'a
[u64]) -> Isaac64Rng
{
563 let mut rng
= EMPTY_64
;
569 impl Rand
for Isaac64Rng
{
570 fn rand
<R
: Rng
>(other
: &mut R
) -> Isaac64Rng
{
571 let mut ret
= EMPTY_64
;
573 let ptr
= ret
.rsl
.as_mut_ptr() as *mut u8;
575 let slice
= slice
::from_raw_parts_mut(ptr
, RAND_SIZE_64
* 8);
576 other
.fill_bytes(slice
);
591 use std
::prelude
::v1
::*;
593 use {Rng, SeedableRng}
;
594 use super::{Isaac64Rng, IsaacRng}
;
597 fn test_rng_32_rand_seeded() {
598 let s
= ::test
::rng().gen_iter
::<u32>().take(256).collect
::<Vec
<u32>>();
599 let mut ra
: IsaacRng
= SeedableRng
::from_seed(&s
[..]);
600 let mut rb
: IsaacRng
= SeedableRng
::from_seed(&s
[..]);
601 assert
!(ra
.gen_ascii_chars()
603 .eq(rb
.gen_ascii_chars().take(100)));
606 fn test_rng_64_rand_seeded() {
607 let s
= ::test
::rng().gen_iter
::<u64>().take(256).collect
::<Vec
<u64>>();
608 let mut ra
: Isaac64Rng
= SeedableRng
::from_seed(&s
[..]);
609 let mut rb
: Isaac64Rng
= SeedableRng
::from_seed(&s
[..]);
610 assert
!(ra
.gen_ascii_chars()
612 .eq(rb
.gen_ascii_chars().take(100)));
616 fn test_rng_32_seeded() {
617 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
618 let mut ra
: IsaacRng
= SeedableRng
::from_seed(seed
);
619 let mut rb
: IsaacRng
= SeedableRng
::from_seed(seed
);
620 assert
!(ra
.gen_ascii_chars()
622 .eq(rb
.gen_ascii_chars().take(100)));
625 fn test_rng_64_seeded() {
626 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
627 let mut ra
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
628 let mut rb
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
629 assert
!(ra
.gen_ascii_chars()
631 .eq(rb
.gen_ascii_chars().take(100)));
635 fn test_rng_32_reseed() {
636 let s
= ::test
::rng().gen_iter
::<u32>().take(256).collect
::<Vec
<u32>>();
637 let mut r
: IsaacRng
= SeedableRng
::from_seed(&s
[..]);
638 let string1
: String
= r
.gen_ascii_chars().take(100).collect();
642 let string2
: String
= r
.gen_ascii_chars().take(100).collect();
643 assert_eq
!(string1
, string2
);
646 fn test_rng_64_reseed() {
647 let s
= ::test
::rng().gen_iter
::<u64>().take(256).collect
::<Vec
<u64>>();
648 let mut r
: Isaac64Rng
= SeedableRng
::from_seed(&s
[..]);
649 let string1
: String
= r
.gen_ascii_chars().take(100).collect();
653 let string2
: String
= r
.gen_ascii_chars().take(100).collect();
654 assert_eq
!(string1
, string2
);
659 fn test_rng_32_true_values() {
660 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
661 let mut ra
: IsaacRng
= SeedableRng
::from_seed(seed
);
662 // Regression test that isaac is actually using the above vector
663 let v
= (0..10).map(|_
| ra
.next_u32()).collect
::<Vec
<_
>>();
665 vec
![2558573138, 873787463, 263499565, 2103644246, 3595684709,
666 4203127393, 264982119, 2765226902, 2737944514, 3900253796]);
668 let seed
: &[_
] = &[12345, 67890, 54321, 9876];
669 let mut rb
: IsaacRng
= SeedableRng
::from_seed(seed
);
670 // skip forward to the 10000th number
675 let v
= (0..10).map(|_
| rb
.next_u32()).collect
::<Vec
<_
>>();
677 vec
![3676831399, 3183332890, 2834741178, 3854698763, 2717568474,
678 1576568959, 3507990155, 179069555, 141456972, 2478885421]);
682 fn test_rng_64_true_values() {
683 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
684 let mut ra
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
685 // Regression test that isaac is actually using the above vector
686 let v
= (0..10).map(|_
| ra
.next_u64()).collect
::<Vec
<_
>>();
688 vec
![547121783600835980, 14377643087320773276, 17351601304698403469,
689 1238879483818134882, 11952566807690396487, 13970131091560099343,
690 4469761996653280935, 15552757044682284409, 6860251611068737823,
691 13722198873481261842]);
693 let seed
: &[_
] = &[12345, 67890, 54321, 9876];
694 let mut rb
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
695 // skip forward to the 10000th number
700 let v
= (0..10).map(|_
| rb
.next_u64()).collect
::<Vec
<_
>>();
702 vec
![18143823860592706164, 8491801882678285927, 2699425367717515619,
703 17196852593171130876, 2606123525235546165, 15790932315217671084,
704 596345674630742204, 9947027391921273664, 11788097613744130851,
705 10391409374914919106]);
710 fn test_rng_clone() {
711 let seed
: &[_
] = &[1, 23, 456, 7890, 12345];
712 let mut rng
: Isaac64Rng
= SeedableRng
::from_seed(seed
);
713 let mut clone
= rng
.clone();
715 assert_eq
!(rng
.next_u64(), clone
.next_u64());