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