(index<- ) ./libstd/rand/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.
4 //
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.
10
11 //! The ISAAC random number generator.
12
13 use cast;
14 use rand::{Rng, SeedableRng, OSRng};
15 use iter::{Iterator, range, range_step, Repeat};
16 use option::{None, Some};
17
18 static RAND_SIZE_LEN: u32 = 8;
19 static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN;
20
21 /// A random number generator that uses the [ISAAC
22 /// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29).
23 ///
24 /// The ISAAC algorithm is suitable for cryptographic purposes.
25 pub struct IsaacRng {
26 priv cnt: u32,
27 priv rsl: [u32, .. RAND_SIZE],
28 priv mem: [u32, .. RAND_SIZE],
29 priv a: u32,
30 priv b: u32,
31 priv c: u32
32 }
33 static EMPTY: IsaacRng = IsaacRng {
34 cnt: 0,
35 rsl: [0, .. RAND_SIZE],
36 mem: [0, .. RAND_SIZE],
37 a: 0, b: 0, c: 0
38 };
39
40 impl IsaacRng {
41 /// Create an ISAAC random number generator with a random seed.
42 pub fn new() -> IsaacRng {
43 let mut rng = EMPTY;
44
45 {
46 let bytes = unsafe {cast::transmute::<&mut [u32], &mut [u8]>(rng.rsl)};
47 OSRng::new().fill_bytes(bytes);
48 }
49
50 rng.init(true);
51 rng
52 }
53
54 /// Create an ISAAC random number generator using the default
55 /// fixed seed.
56 pub fn new_unseeded() -> IsaacRng {
57 let mut rng = EMPTY;
58 rng.init(false);
59 rng
60 }
61
62 /// Initialises `self`. If `use_rsl` is true, then use the current value
63 /// of `rsl` as a seed, otherwise construct one algorithmically (not
64 /// randomly).
65 fn init(&mut self, use_rsl: bool) {
66 let mut a = 0x9e3779b9;
67 let mut b = a;
68 let mut c = a;
69 let mut d = a;
70 let mut e = a;
71 let mut f = a;
72 let mut g = a;
73 let mut h = a;
74
75 macro_rules! mix(
76 () => {{
77 a^=b<<11; d+=a; b+=c;
78 b^=c>>2; e+=b; c+=d;
79 c^=d<<8; f+=c; d+=e;
80 d^=e>>16; g+=d; e+=f;
81 e^=f<<10; h+=e; f+=g;
82 f^=g>>4; a+=f; g+=h;
83 g^=h<<8; b+=g; h+=a;
84 h^=a>>9; c+=h; a+=b;
85 }}
86 );
87
88 do 4.times { mix!(); }
89
90 if use_rsl {
91 macro_rules! memloop (
92 ($arr:expr) => {{
93 for i in range_step(0u32, RAND_SIZE, 8) {
94 a+=$arr[i ]; b+=$arr[i+1];
95 c+=$arr[i+2]; d+=$arr[i+3];
96 e+=$arr[i+4]; f+=$arr[i+5];
97 g+=$arr[i+6]; h+=$arr[i+7];
98 mix!();
99 self.mem[i ]=a; self.mem[i+1]=b;
100 self.mem[i+2]=c; self.mem[i+3]=d;
101 self.mem[i+4]=e; self.mem[i+5]=f;
102 self.mem[i+6]=g; self.mem[i+7]=h;
103 }
104 }}
105 );
106
107 memloop!(self.rsl);
108 memloop!(self.mem);
109 } else {
110 for i in range_step(0u32, RAND_SIZE, 8) {
111 mix!();
112 self.mem[i ]=a; self.mem[i+1]=b;
113 self.mem[i+2]=c; self.mem[i+3]=d;
114 self.mem[i+4]=e; self.mem[i+5]=f;
115 self.mem[i+6]=g; self.mem[i+7]=h;
116 }
117 }
118
119 self.isaac();
120 }
121
122 /// Refills the output buffer (`self.rsl`)
123 #[inline]
124 fn isaac(&mut self) {
125 self.c += 1;
126 // abbreviations
127 let mut a = self.a;
128 let mut b = self.b + self.c;
129
130 static MIDPOINT: uint = RAND_SIZE as uint / 2;
131
132 macro_rules! ind (($x:expr) => {
133 self.mem[($x >> 2) & (RAND_SIZE - 1)]
134 });
135 macro_rules! rngstep(
136 ($j:expr, $shift:expr) => {{
137 let base = $j;
138 let mix = if $shift < 0 {
139 a >> -$shift as uint
140 } else {
141 a << $shift as uint
142 };
143
144 let x = self.mem[base + mr_offset];
145 a = (a ^ mix) + self.mem[base + m2_offset];
146 let y = ind!(x) + a + b;
147 self.mem[base + mr_offset] = y;
148
149 b = ind!(y >> RAND_SIZE_LEN) + x;
150 self.rsl[base + mr_offset] = b;
151 }}
152 );
153
154 let r = [(0, MIDPOINT), (MIDPOINT, 0)];
155 for &(mr_offset, m2_offset) in r.iter() {
156 for i in range_step(0u, MIDPOINT, 4) {
157 rngstep!(i + 0, 13);
158 rngstep!(i + 1, -6);
159 rngstep!(i + 2, 2);
160 rngstep!(i + 3, -16);
161 }
162 }
163
164 self.a = a;
165 self.b = b;
166 self.cnt = RAND_SIZE;
167 }
168 }
169
170 impl Rng for IsaacRng {
171 #[inline]
172 fn next_u32(&mut self) -> u32 {
173 if self.cnt == 0 {
174 // make some more numbers
175 self.isaac();
176 }
177 self.cnt -= 1;
178 self.rsl[self.cnt]
179 }
180 }
181
182 impl<'self> SeedableRng<&'self [u32]> for IsaacRng {
183 fn reseed(&mut self, seed: &'self [u32]) {
184 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
185 // - 1], 0, 0, ...], to fill rng.rsl.
186 let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u32));
187
188 for (rsl_elem, seed_elem) in self.rsl.mut_iter().zip(seed_iter) {
189 *rsl_elem = seed_elem;
190 }
191 self.cnt = 0;
192 self.a = 0;
193 self.b = 0;
194 self.c = 0;
195
196 self.init(true);
197 }
198
199 /// Create an ISAAC random number generator with a seed. This can
200 /// be any length, although the maximum number of elements used is
201 /// 256 and any more will be silently ignored. A generator
202 /// constructed with a given seed will generate the same sequence
203 /// of values as all other generators constructed with that seed.
204 fn from_seed(seed: &'self [u32]) -> IsaacRng {
205 let mut rng = EMPTY;
206 rng.reseed(seed);
207 rng
208 }
209 }
210
211
212 static RAND_SIZE_64_LEN: uint = 8;
213 static RAND_SIZE_64: uint = 1 << RAND_SIZE_64_LEN;
214
215 /// A random number generator that uses the 64-bit variant of the
216 /// [ISAAC
217 /// algorithm](http://en.wikipedia.org/wiki/ISAAC_%28cipher%29).
218 ///
219 /// The ISAAC algorithm is suitable for cryptographic purposes.
220 pub struct Isaac64Rng {
221 priv cnt: uint,
222 priv rsl: [u64, .. RAND_SIZE_64],
223 priv mem: [u64, .. RAND_SIZE_64],
224 priv a: u64,
225 priv b: u64,
226 priv c: u64,
227 }
228
229 static EMPTY_64: Isaac64Rng = Isaac64Rng {
230 cnt: 0,
231 rsl: [0, .. RAND_SIZE_64],
232 mem: [0, .. RAND_SIZE_64],
233 a: 0, b: 0, c: 0,
234 };
235
236 impl Isaac64Rng {
237 /// Create a 64-bit ISAAC random number generator with a random
238 /// seed.
239 pub fn new() -> Isaac64Rng {
240 let mut rng = EMPTY_64;
241 {
242 let bytes = unsafe {cast::transmute::<&mut [u64], &mut [u8]>(rng.rsl)};
243 OSRng::new().fill_bytes(bytes);
244 }
245 rng.init(true);
246 rng
247 }
248
249 /// Create a 64-bit ISAAC random number generator using the
250 /// default fixed seed.
251 pub fn new_unseeded() -> Isaac64Rng {
252 let mut rng = EMPTY_64;
253 rng.init(false);
254 rng
255 }
256
257 /// Initialises `self`. If `use_rsl` is true, then use the current value
258 /// of `rsl` as a seed, otherwise construct one algorithmically (not
259 /// randomly).
260 fn init(&mut self, use_rsl: bool) {
261 macro_rules! init (
262 ($var:ident) => (
263 let mut $var = 0x9e3779b97f4a7c13;
264 )
265 );
266 init!(a); init!(b); init!(c); init!(d);
267 init!(e); init!(f); init!(g); init!(h);
268
269 macro_rules! mix(
270 () => {{
271 a-=e; f^=h>>9; h+=a;
272 b-=f; g^=a<<9; a+=b;
273 c-=g; h^=b>>23; b+=c;
274 d-=h; a^=c<<15; c+=d;
275 e-=a; b^=d>>14; d+=e;
276 f-=b; c^=e<<20; e+=f;
277 g-=c; d^=f>>17; f+=g;
278 h-=d; e^=g<<14; g+=h;
279 }}
280 );
281
282 for _ in range(0, 4) { mix!(); }
283 if use_rsl {
284 macro_rules! memloop (
285 ($arr:expr) => {{
286 for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) {
287 a+=$arr[i ]; b+=$arr[i+1];
288 c+=$arr[i+2]; d+=$arr[i+3];
289 e+=$arr[i+4]; f+=$arr[i+5];
290 g+=$arr[i+6]; h+=$arr[i+7];
291 mix!();
292 self.mem[i ]=a; self.mem[i+1]=b;
293 self.mem[i+2]=c; self.mem[i+3]=d;
294 self.mem[i+4]=e; self.mem[i+5]=f;
295 self.mem[i+6]=g; self.mem[i+7]=h;
296 }
297 }}
298 );
299
300 memloop!(self.rsl);
301 memloop!(self.mem);
302 } else {
303 for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) {
304 mix!();
305 self.mem[i ]=a; self.mem[i+1]=b;
306 self.mem[i+2]=c; self.mem[i+3]=d;
307 self.mem[i+4]=e; self.mem[i+5]=f;
308 self.mem[i+6]=g; self.mem[i+7]=h;
309 }
310 }
311
312 self.isaac64();
313 }
314
315 /// Refills the output buffer (`self.rsl`)
316 fn isaac64(&mut self) {
317 self.c += 1;
318 // abbreviations
319 let mut a = self.a;
320 let mut b = self.b + self.c;
321 static MIDPOINT: uint = RAND_SIZE_64 / 2;
322 static MP_VEC: [(uint, uint), .. 2] = [(0,MIDPOINT), (MIDPOINT, 0)];
323 macro_rules! ind (
324 ($x:expr) => {
325 self.mem.unsafe_get(($x as uint >> 3) & (RAND_SIZE_64 - 1))
326 }
327 );
328 macro_rules! rngstep(
329 ($j:expr, $shift:expr) => {{
330 let base = base + $j;
331 let mix = a ^ (if $shift < 0 {
332 a >> -$shift as uint
333 } else {
334 a << $shift as uint
335 });
336 let mix = if $j == 0 {!mix} else {mix};
337
338 unsafe {
339 let x = self.mem.unsafe_get(base + mr_offset);
340 a = mix + self.mem.unsafe_get(base + m2_offset);
341 let y = ind!(x) + a + b;
342 self.mem.unsafe_set(base + mr_offset, y);
343
344 b = ind!(y >> RAND_SIZE_64_LEN) + x;
345 self.rsl.unsafe_set(base + mr_offset, b);
346 }
347 }}
348 );
349
350 for &(mr_offset, m2_offset) in MP_VEC.iter() {
351 for base in range(0, MIDPOINT / 4).map(|i| i * 4) {
352 rngstep!(0, 21);
353 rngstep!(1, -5);
354 rngstep!(2, 12);
355 rngstep!(3, -33);
356 }
357 }
358
359 self.a = a;
360 self.b = b;
361 self.cnt = RAND_SIZE_64;
362 }
363 }
364
365 impl Rng for Isaac64Rng {
366 // FIXME #7771: having next_u32 like this should be unnecessary
367 #[inline]
368 fn next_u32(&mut self) -> u32 {
369 self.next_u64() as u32
370 }
371
372 #[inline]
373 fn next_u64(&mut self) -> u64 {
374 if self.cnt == 0 {
375 // make some more numbers
376 self.isaac64();
377 }
378 self.cnt -= 1;
379 unsafe { self.rsl.unsafe_get(self.cnt) }
380 }
381 }
382
383 impl<'self> SeedableRng<&'self [u64]> for Isaac64Rng {
384 fn reseed(&mut self, seed: &'self [u64]) {
385 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
386 // - 1], 0, 0, ...], to fill rng.rsl.
387 let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u64));
388
389 for (rsl_elem, seed_elem) in self.rsl.mut_iter().zip(seed_iter) {
390 *rsl_elem = seed_elem;
391 }
392 self.cnt = 0;
393 self.a = 0;
394 self.b = 0;
395 self.c = 0;
396
397 self.init(true);
398 }
399
400 /// Create an ISAAC random number generator with a seed. This can
401 /// be any length, although the maximum number of elements used is
402 /// 256 and any more will be silently ignored. A generator
403 /// constructed with a given seed will generate the same sequence
404 /// of values as all other generators constructed with that seed.
405 fn from_seed(seed: &'self [u64]) -> Isaac64Rng {
406 let mut rng = EMPTY_64;
407 rng.reseed(seed);
408 rng
409 }
410 }
411
412 #[cfg(test)]
413 mod test {
414 use super::*;
415 use rand::{Rng, SeedableRng, OSRng};
416 use option::Some;
417 use iter::range;
418 use vec;
419
420 #[test]
421 fn test_rng_32_rand_seeded() {
422 let s = OSRng::new().gen_vec::<u32>(256);
423 let mut ra: IsaacRng = SeedableRng::from_seed(s.as_slice());
424 let mut rb: IsaacRng = SeedableRng::from_seed(s.as_slice());
425 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
426 }
427 #[test]
428 fn test_rng_64_rand_seeded() {
429 let s = OSRng::new().gen_vec::<u64>(256);
430 let mut ra: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
431 let mut rb: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
432 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
433 }
434
435 #[test]
436 fn test_rng_32_seeded() {
437 let seed = &[2, 32, 4, 32, 51];
438 let mut ra: IsaacRng = SeedableRng::from_seed(seed);
439 let mut rb: IsaacRng = SeedableRng::from_seed(seed);
440 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
441 }
442 #[test]
443 fn test_rng_64_seeded() {
444 let seed = &[2, 32, 4, 32, 51];
445 let mut ra: Isaac64Rng = SeedableRng::from_seed(seed);
446 let mut rb: Isaac64Rng = SeedableRng::from_seed(seed);
447 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
448 }
449
450 #[test]
451 fn test_rng_32_reseed() {
452 let s = OSRng::new().gen_vec::<u32>(256);
453 let mut r: IsaacRng = SeedableRng::from_seed(s.as_slice());
454 let string1 = r.gen_ascii_str(100);
455
456 r.reseed(s);
457
458 let string2 = r.gen_ascii_str(100);
459 assert_eq!(string1, string2);
460 }
461 #[test]
462 fn test_rng_64_reseed() {
463 let s = OSRng::new().gen_vec::<u64>(256);
464 let mut r: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
465 let string1 = r.gen_ascii_str(100);
466
467 r.reseed(s);
468
469 let string2 = r.gen_ascii_str(100);
470 assert_eq!(string1, string2);
471 }
472
473 #[test]
474 fn test_rng_32_true_values() {
475 let seed = &[2, 32, 4, 32, 51];
476 let mut ra: IsaacRng = SeedableRng::from_seed(seed);
477 // Regression test that isaac is actually using the above vector
478 let v = vec::from_fn(10, |_| ra.next_u32());
479 assert_eq!(v,
480 ~[447462228, 2081944040, 3163797308, 2379916134, 2377489184,
481 1132373754, 536342443, 2995223415, 1265094839, 345325140]);
482
483 let seed = &[500, -4000, 123456, 9876543, 1, 1, 1, 1, 1];
484 let mut rb: IsaacRng = SeedableRng::from_seed(seed);
485 // skip forward to the 10000th number
486 for _ in range(0, 10000) { rb.next_u32(); }
487
488 let v = vec::from_fn(10, |_| rb.next_u32());
489 assert_eq!(v,
490 ~[612373032, 292987903, 1819311337, 3141271980, 422447569,
491 310096395, 1083172510, 867909094, 2478664230, 2073577855]);
492 }
493 #[test]
494 fn test_rng_64_true_values() {
495 let seed = &[2, 32, 4, 32, 51];
496 let mut ra: Isaac64Rng = SeedableRng::from_seed(seed);
497 // Regression test that isaac is actually using the above vector
498 let v = vec::from_fn(10, |_| ra.next_u64());
499 assert_eq!(v,
500 ~[15015576812873463115, 12461067598045625862, 14818626436142668771,
501 5562406406765984441, 11813289907965514161, 13443797187798420053,
502 6935026941854944442, 7750800609318664042, 14428747036317928637,
503 14028894460301215947]);
504
505 let seed = &[500, -4000, 123456, 9876543, 1, 1, 1, 1, 1];
506 let mut rb: Isaac64Rng = SeedableRng::from_seed(seed);
507 // skip forward to the 10000th number
508 for _ in range(0, 10000) { rb.next_u64(); }
509
510 let v = vec::from_fn(10, |_| rb.next_u64());
511 assert_eq!(v,
512 ~[13557216323596688637, 17060829581390442094, 4927582063811333743,
513 2699639759356482270, 4819341314392384881, 6047100822963614452,
514 11086255989965979163, 11901890363215659856, 5370800226050011580,
515 16496463556025356451]);
516 }
517 }