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