(index<- ) ./librand/isaac.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Wed Apr 9 17:27:02 2014
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 {Rng, SeedableRng, OSRng};
14 use std::io::IoResult;
15 use std::iter::{range_step, Repeat};
16 use std::slice::raw;
17 use std::mem;
18
19 static RAND_SIZE_LEN: u32 = 8;
20 static RAND_SIZE: u32 = 1 << RAND_SIZE_LEN;
21
22 /// A random number generator that uses the ISAAC algorithm[1].
23 ///
24 /// The ISAAC algorithm is generally accepted as suitable for
25 /// cryptographic purposes, but this implementation has not be
26 /// verified as such. Prefer a generator like `OSRng` that defers to
27 /// the operating system for cases that need high security.
28 ///
29 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
30 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
31 pub struct IsaacRng {
32 cnt: u32,
33 rsl: [u32, .. RAND_SIZE],
34 mem: [u32, .. RAND_SIZE],
35 a: u32,
36 b: u32,
37 c: u32
38 }
39 static EMPTY: IsaacRng = IsaacRng {
40 cnt: 0,
41 rsl: [0, .. RAND_SIZE],
42 mem: [0, .. RAND_SIZE],
43 a: 0, b: 0, c: 0
44 };
45
46 impl IsaacRng {
47 /// Create an ISAAC random number generator with a random seed.
48 ///
49 /// This reads randomness from the operating system (via `OSRng`)
50 /// which may fail, any error is propagated via the `IoResult`
51 /// return value.
52 pub fn new() -> IoResult<IsaacRng> {
53 let mut rng = EMPTY;
54 let mut os_rng = try!(OSRng::new());
55 unsafe {
56 let ptr = rng.rsl.as_mut_ptr();
57
58 raw::mut_buf_as_slice(ptr as *mut u8, mem::size_of_val(&rng.rsl), |slice| {
59 os_rng.fill_bytes(slice);
60 })
61 }
62
63 rng.init(true);
64 Ok(rng)
65 }
66
67 /// Create an ISAAC random number generator using the default
68 /// fixed seed.
69 pub fn new_unseeded() -> IsaacRng {
70 let mut rng = EMPTY;
71 rng.init(false);
72 rng
73 }
74
75 /// Initialises `self`. If `use_rsl` is true, then use the current value
76 /// of `rsl` as a seed, otherwise construct one algorithmically (not
77 /// randomly).
78 fn init(&mut self, use_rsl: bool) {
79 let mut a = 0x9e3779b9;
80 let mut b = a;
81 let mut c = a;
82 let mut d = a;
83 let mut e = a;
84 let mut f = a;
85 let mut g = a;
86 let mut h = a;
87
88 macro_rules! mix(
89 () => {{
90 a^=b<<11; d+=a; b+=c;
91 b^=c>>2; e+=b; c+=d;
92 c^=d<<8; f+=c; d+=e;
93 d^=e>>16; g+=d; e+=f;
94 e^=f<<10; h+=e; f+=g;
95 f^=g>>4; a+=f; g+=h;
96 g^=h<<8; b+=g; h+=a;
97 h^=a>>9; c+=h; a+=b;
98 }}
99 );
100
101 for _ in range(0, 4) { mix!(); }
102
103 if use_rsl {
104 macro_rules! memloop (
105 ($arr:expr) => {{
106 for i in range_step(0, RAND_SIZE as uint, 8) {
107 a+=$arr[i ]; b+=$arr[i+1];
108 c+=$arr[i+2]; d+=$arr[i+3];
109 e+=$arr[i+4]; f+=$arr[i+5];
110 g+=$arr[i+6]; h+=$arr[i+7];
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
120 memloop!(self.rsl);
121 memloop!(self.mem);
122 } else {
123 for i in range_step(0, RAND_SIZE as uint, 8) {
124 mix!();
125 self.mem[i ]=a; self.mem[i+1]=b;
126 self.mem[i+2]=c; self.mem[i+3]=d;
127 self.mem[i+4]=e; self.mem[i+5]=f;
128 self.mem[i+6]=g; self.mem[i+7]=h;
129 }
130 }
131
132 self.isaac();
133 }
134
135 /// Refills the output buffer (`self.rsl`)
136 #[inline]
137 fn isaac(&mut self) {
138 self.c += 1;
139 // abbreviations
140 let mut a = self.a;
141 let mut b = self.b + self.c;
142
143 static MIDPOINT: uint = RAND_SIZE as uint / 2;
144
145 macro_rules! ind (($x:expr) => {
146 self.mem[(($x >> 2) & (RAND_SIZE - 1)) as uint]
147 });
148 macro_rules! rngstep(
149 ($j:expr, $shift:expr) => {{
150 let base = $j;
151 let mix = if $shift < 0 {
152 a >> -$shift as uint
153 } else {
154 a << $shift as uint
155 };
156
157 let x = self.mem[base + mr_offset];
158 a = (a ^ mix) + self.mem[base + m2_offset];
159 let y = ind!(x) + a + b;
160 self.mem[base + mr_offset] = y;
161
162 b = ind!(y >> RAND_SIZE_LEN) + x;
163 self.rsl[base + mr_offset] = b;
164 }}
165 );
166
167 let r = [(0, MIDPOINT), (MIDPOINT, 0)];
168 for &(mr_offset, m2_offset) in r.iter() {
169 for i in range_step(0u, MIDPOINT, 4) {
170 rngstep!(i + 0, 13);
171 rngstep!(i + 1, -6);
172 rngstep!(i + 2, 2);
173 rngstep!(i + 3, -16);
174 }
175 }
176
177 self.a = a;
178 self.b = b;
179 self.cnt = RAND_SIZE;
180 }
181 }
182
183 impl Rng for IsaacRng {
184 #[inline]
185 fn next_u32(&mut self) -> u32 {
186 if self.cnt == 0 {
187 // make some more numbers
188 self.isaac();
189 }
190 self.cnt -= 1;
191 self.rsl[self.cnt as uint]
192 }
193 }
194
195 impl<'a> SeedableRng<&'a [u32]> for IsaacRng {
196 fn reseed(&mut self, seed: &'a [u32]) {
197 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
198 // - 1], 0, 0, ...], to fill rng.rsl.
199 let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u32));
200
201 for (rsl_elem, seed_elem) in self.rsl.mut_iter().zip(seed_iter) {
202 *rsl_elem = seed_elem;
203 }
204 self.cnt = 0;
205 self.a = 0;
206 self.b = 0;
207 self.c = 0;
208
209 self.init(true);
210 }
211
212 /// Create an ISAAC random number generator with a seed. This can
213 /// be any length, although the maximum number of elements used is
214 /// 256 and any more will be silently ignored. A generator
215 /// constructed with a given seed will generate the same sequence
216 /// of values as all other generators constructed with that seed.
217 fn from_seed(seed: &'a [u32]) -> IsaacRng {
218 let mut rng = EMPTY;
219 rng.reseed(seed);
220 rng
221 }
222 }
223
224
225 static RAND_SIZE_64_LEN: uint = 8;
226 static RAND_SIZE_64: uint = 1 << RAND_SIZE_64_LEN;
227
228 /// A random number generator that uses ISAAC-64[1], the 64-bit
229 /// variant of the ISAAC algorithm.
230 ///
231 /// The ISAAC algorithm is generally accepted as suitable for
232 /// cryptographic purposes, but this implementation has not be
233 /// verified as such. Prefer a generator like `OSRng` that defers to
234 /// the operating system for cases that need high security.
235 ///
236 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
237 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
238 pub struct Isaac64Rng {
239 cnt: uint,
240 rsl: [u64, .. RAND_SIZE_64],
241 mem: [u64, .. RAND_SIZE_64],
242 a: u64,
243 b: u64,
244 c: u64,
245 }
246
247 static EMPTY_64: Isaac64Rng = Isaac64Rng {
248 cnt: 0,
249 rsl: [0, .. RAND_SIZE_64],
250 mem: [0, .. RAND_SIZE_64],
251 a: 0, b: 0, c: 0,
252 };
253
254 impl Isaac64Rng {
255 /// Create a 64-bit ISAAC random number generator with a random
256 /// seed.
257 ///
258 /// This reads randomness from the operating system (via `OSRng`)
259 /// which may fail, any error is propagated via the `IoResult`
260 /// return value.
261 pub fn new() -> IoResult<Isaac64Rng> {
262 let mut rng = EMPTY_64;
263 let mut os_rng = try!(OSRng::new());
264
265 unsafe {
266 let ptr = rng.rsl.as_mut_ptr();
267
268 raw::mut_buf_as_slice(ptr as *mut u8, mem::size_of_val(&rng.rsl), |slice| {
269 os_rng.fill_bytes(slice);
270 })
271 }
272
273 rng.init(true);
274 Ok(rng)
275 }
276
277 /// Create a 64-bit ISAAC random number generator using the
278 /// default fixed seed.
279 pub fn new_unseeded() -> Isaac64Rng {
280 let mut rng = EMPTY_64;
281 rng.init(false);
282 rng
283 }
284
285 /// Initialises `self`. If `use_rsl` is true, then use the current value
286 /// of `rsl` as a seed, otherwise construct one algorithmically (not
287 /// randomly).
288 fn init(&mut self, use_rsl: bool) {
289 macro_rules! init (
290 ($var:ident) => (
291 let mut $var = 0x9e3779b97f4a7c13;
292 )
293 );
294 init!(a); init!(b); init!(c); init!(d);
295 init!(e); init!(f); init!(g); init!(h);
296
297 macro_rules! mix(
298 () => {{
299 a-=e; f^=h>>9; h+=a;
300 b-=f; g^=a<<9; a+=b;
301 c-=g; h^=b>>23; b+=c;
302 d-=h; a^=c<<15; c+=d;
303 e-=a; b^=d>>14; d+=e;
304 f-=b; c^=e<<20; e+=f;
305 g-=c; d^=f>>17; f+=g;
306 h-=d; e^=g<<14; g+=h;
307 }}
308 );
309
310 for _ in range(0, 4) { mix!(); }
311 if use_rsl {
312 macro_rules! memloop (
313 ($arr:expr) => {{
314 for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) {
315 a+=$arr[i ]; b+=$arr[i+1];
316 c+=$arr[i+2]; d+=$arr[i+3];
317 e+=$arr[i+4]; f+=$arr[i+5];
318 g+=$arr[i+6]; h+=$arr[i+7];
319 mix!();
320 self.mem[i ]=a; self.mem[i+1]=b;
321 self.mem[i+2]=c; self.mem[i+3]=d;
322 self.mem[i+4]=e; self.mem[i+5]=f;
323 self.mem[i+6]=g; self.mem[i+7]=h;
324 }
325 }}
326 );
327
328 memloop!(self.rsl);
329 memloop!(self.mem);
330 } else {
331 for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) {
332 mix!();
333 self.mem[i ]=a; self.mem[i+1]=b;
334 self.mem[i+2]=c; self.mem[i+3]=d;
335 self.mem[i+4]=e; self.mem[i+5]=f;
336 self.mem[i+6]=g; self.mem[i+7]=h;
337 }
338 }
339
340 self.isaac64();
341 }
342
343 /// Refills the output buffer (`self.rsl`)
344 fn isaac64(&mut self) {
345 self.c += 1;
346 // abbreviations
347 let mut a = self.a;
348 let mut b = self.b + self.c;
349 static MIDPOINT: uint = RAND_SIZE_64 / 2;
350 static MP_VEC: [(uint, uint), .. 2] = [(0,MIDPOINT), (MIDPOINT, 0)];
351 macro_rules! ind (
352 ($x:expr) => {
353 *self.mem.unsafe_ref(($x as uint >> 3) & (RAND_SIZE_64 - 1))
354 }
355 );
356 macro_rules! rngstep(
357 ($j:expr, $shift:expr) => {{
358 let base = base + $j;
359 let mix = a ^ (if $shift < 0 {
360 a >> -$shift as uint
361 } else {
362 a << $shift as uint
363 });
364 let mix = if $j == 0 {!mix} else {mix};
365
366 unsafe {
367 let x = *self.mem.unsafe_ref(base + mr_offset);
368 a = mix + *self.mem.unsafe_ref(base + m2_offset);
369 let y = ind!(x) + a + b;
370 self.mem.unsafe_set(base + mr_offset, y);
371
372 b = ind!(y >> RAND_SIZE_64_LEN) + x;
373 self.rsl.unsafe_set(base + mr_offset, b);
374 }
375 }}
376 );
377
378 for &(mr_offset, m2_offset) in MP_VEC.iter() {
379 for base in range(0, MIDPOINT / 4).map(|i| i * 4) {
380 rngstep!(0, 21);
381 rngstep!(1, -5);
382 rngstep!(2, 12);
383 rngstep!(3, -33);
384 }
385 }
386
387 self.a = a;
388 self.b = b;
389 self.cnt = RAND_SIZE_64;
390 }
391 }
392
393 impl Rng for Isaac64Rng {
394 // FIXME #7771: having next_u32 like this should be unnecessary
395 #[inline]
396 fn next_u32(&mut self) -> u32 {
397 self.next_u64() as u32
398 }
399
400 #[inline]
401 fn next_u64(&mut self) -> u64 {
402 if self.cnt == 0 {
403 // make some more numbers
404 self.isaac64();
405 }
406 self.cnt -= 1;
407 unsafe { *self.rsl.unsafe_ref(self.cnt) }
408 }
409 }
410
411 impl<'a> SeedableRng<&'a [u64]> for Isaac64Rng {
412 fn reseed(&mut self, seed: &'a [u64]) {
413 // make the seed into [seed[0], seed[1], ..., seed[seed.len()
414 // - 1], 0, 0, ...], to fill rng.rsl.
415 let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u64));
416
417 for (rsl_elem, seed_elem) in self.rsl.mut_iter().zip(seed_iter) {
418 *rsl_elem = seed_elem;
419 }
420 self.cnt = 0;
421 self.a = 0;
422 self.b = 0;
423 self.c = 0;
424
425 self.init(true);
426 }
427
428 /// Create an ISAAC random number generator with a seed. This can
429 /// be any length, although the maximum number of elements used is
430 /// 256 and any more will be silently ignored. A generator
431 /// constructed with a given seed will generate the same sequence
432 /// of values as all other generators constructed with that seed.
433 fn from_seed(seed: &'a [u64]) -> Isaac64Rng {
434 let mut rng = EMPTY_64;
435 rng.reseed(seed);
436 rng
437 }
438 }
439
440 #[cfg(test)]
441 mod test {
442 use super::{IsaacRng, Isaac64Rng};
443 use {Rng, SeedableRng, task_rng};
444
445 #[test]
446 fn test_rng_32_rand_seeded() {
447 let s = task_rng().gen_vec::<u32>(256);
448 let mut ra: IsaacRng = SeedableRng::from_seed(s.as_slice());
449 let mut rb: IsaacRng = SeedableRng::from_seed(s.as_slice());
450 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
451 }
452 #[test]
453 fn test_rng_64_rand_seeded() {
454 let s = task_rng().gen_vec::<u64>(256);
455 let mut ra: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
456 let mut rb: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
457 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
458 }
459
460 #[test]
461 fn test_rng_32_seeded() {
462 let seed = &[1, 23, 456, 7890, 12345];
463 let mut ra: IsaacRng = SeedableRng::from_seed(seed);
464 let mut rb: IsaacRng = SeedableRng::from_seed(seed);
465 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
466 }
467 #[test]
468 fn test_rng_64_seeded() {
469 let seed = &[1, 23, 456, 7890, 12345];
470 let mut ra: Isaac64Rng = SeedableRng::from_seed(seed);
471 let mut rb: Isaac64Rng = SeedableRng::from_seed(seed);
472 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
473 }
474
475 #[test]
476 fn test_rng_32_reseed() {
477 let s = task_rng().gen_vec::<u32>(256);
478 let mut r: IsaacRng = SeedableRng::from_seed(s.as_slice());
479 let string1 = r.gen_ascii_str(100);
480
481 r.reseed(s.as_slice());
482
483 let string2 = r.gen_ascii_str(100);
484 assert_eq!(string1, string2);
485 }
486 #[test]
487 fn test_rng_64_reseed() {
488 let s = task_rng().gen_vec::<u64>(256);
489 let mut r: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
490 let string1 = r.gen_ascii_str(100);
491
492 r.reseed(s.as_slice());
493
494 let string2 = r.gen_ascii_str(100);
495 assert_eq!(string1, string2);
496 }
497
498 #[test]
499 fn test_rng_32_true_values() {
500 let seed = &[1, 23, 456, 7890, 12345];
501 let mut ra: IsaacRng = SeedableRng::from_seed(seed);
502 // Regression test that isaac is actually using the above vector
503 let v = Vec::from_fn(10, |_| ra.next_u32());
504 assert_eq!(v,
505 vec!(2558573138, 873787463, 263499565, 2103644246, 3595684709,
506 4203127393, 264982119, 2765226902, 2737944514, 3900253796));
507
508 let seed = &[12345, 67890, 54321, 9876];
509 let mut rb: IsaacRng = SeedableRng::from_seed(seed);
510 // skip forward to the 10000th number
511 for _ in range(0, 10000) { rb.next_u32(); }
512
513 let v = Vec::from_fn(10, |_| rb.next_u32());
514 assert_eq!(v,
515 vec!(3676831399, 3183332890, 2834741178, 3854698763, 2717568474,
516 1576568959, 3507990155, 179069555, 141456972, 2478885421));
517 }
518 #[test]
519 fn test_rng_64_true_values() {
520 let seed = &[1, 23, 456, 7890, 12345];
521 let mut ra: Isaac64Rng = SeedableRng::from_seed(seed);
522 // Regression test that isaac is actually using the above vector
523 let v = Vec::from_fn(10, |_| ra.next_u64());
524 assert_eq!(v,
525 vec!(547121783600835980, 14377643087320773276, 17351601304698403469,
526 1238879483818134882, 11952566807690396487, 13970131091560099343,
527 4469761996653280935, 15552757044682284409, 6860251611068737823,
528 13722198873481261842));
529
530 let seed = &[12345, 67890, 54321, 9876];
531 let mut rb: Isaac64Rng = SeedableRng::from_seed(seed);
532 // skip forward to the 10000th number
533 for _ in range(0, 10000) { rb.next_u64(); }
534
535 let v = Vec::from_fn(10, |_| rb.next_u64());
536 assert_eq!(v,
537 vec!(18143823860592706164, 8491801882678285927, 2699425367717515619,
538 17196852593171130876, 2606123525235546165, 15790932315217671084,
539 596345674630742204, 9947027391921273664, 11788097613744130851,
540 10391409374914919106));
541 }
542 }