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
  17 use {Rng, SeedableRng, Rand};
  18
  19 static RAND_SIZE_LEN: u32 = 8;
  20 static RAND_SIZE: u32 = 1 << (RAND_SIZE_LEN as uint);
  21 static 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_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
 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::new(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();
 238
 239             raw::mut_buf_as_slice(ptr as *mut u8,
 240                                   (RAND_SIZE*4) as uint, |slice| {
 241                 other.fill_bytes(slice);
 242             })
 243         }
 244         ret.cnt = 0;
 245         ret.a = 0;
 246         ret.b = 0;
 247         ret.c = 0;
 248
 249         ret.init(true);
 250         return ret;
 251     }
 252 }
 253
 254 static RAND_SIZE_64_LEN: uint = 8;
 255 static RAND_SIZE_64: uint = 1 << RAND_SIZE_64_LEN;
 256
 257 /// A random number generator that uses ISAAC-64[1], the 64-bit
 258 /// variant of the ISAAC algorithm.
 259 ///
 260 /// The ISAAC algorithm is generally accepted as suitable for
 261 /// cryptographic purposes, but this implementation has not be
 262 /// verified as such. Prefer a generator like `OsRng` that defers to
 263 /// the operating system for cases that need high security.
 264 ///
 265 /// [1]: Bob Jenkins, [*ISAAC: A fast cryptographic random number
 266 /// generator*](http://www.burtleburtle.net/bob/rand/isaacafa.html)
 267 pub struct Isaac64Rng {
 268     cnt: uint,
 269     rsl: [u64, .. RAND_SIZE_64],
 270     mem: [u64, .. RAND_SIZE_64],
 271     a: u64,
 272     b: u64,
 273     c: u64,
 274 }
 275
 276 static EMPTY_64: Isaac64Rng = Isaac64Rng {
 277     cnt: 0,
 278     rsl: [0, .. RAND_SIZE_64],
 279     mem: [0, .. RAND_SIZE_64],
 280     a: 0, b: 0, c: 0,
 281 };
 282
 283 impl Isaac64Rng {
 284     /// Create a 64-bit ISAAC random number generator using the
 285     /// default fixed seed.
 286     pub fn new_unseeded() -> Isaac64Rng {
 287         let mut rng = EMPTY_64;
 288         rng.init(false);
 289         rng
 290     }
 291
 292     /// Initialises `self`. If `use_rsl` is true, then use the current value
 293     /// of `rsl` as a seed, otherwise construct one algorithmically (not
 294     /// randomly).
 295     fn init(&mut self, use_rsl: bool) {
 296         macro_rules! init (
 297             ($var:ident) => (
 298                 let mut $var = 0x9e3779b97f4a7c13;
 299             )
 300         );
 301         init!(a); init!(b); init!(c); init!(d);
 302         init!(e); init!(f); init!(g); init!(h);
 303
 304         macro_rules! mix(
 305             () => {{
 306                 a-=e; f^=h>>9;  h+=a;
 307                 b-=f; g^=a<<9;  a+=b;
 308                 c-=g; h^=b>>23; b+=c;
 309                 d-=h; a^=c<<15; c+=d;
 310                 e-=a; b^=d>>14; d+=e;
 311                 f-=b; c^=e<<20; e+=f;
 312                 g-=c; d^=f>>17; f+=g;
 313                 h-=d; e^=g<<14; g+=h;
 314             }}
 315         );
 316
 317         for _ in range(0u, 4) {
 318             mix!();
 319         }
 320
 321         if use_rsl {
 322             macro_rules! memloop (
 323                 ($arr:expr) => {{
 324                     for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) {
 325                         a+=$arr[i  ]; b+=$arr[i+1];
 326                         c+=$arr[i+2]; d+=$arr[i+3];
 327                         e+=$arr[i+4]; f+=$arr[i+5];
 328                         g+=$arr[i+6]; h+=$arr[i+7];
 329                         mix!();
 330                         self.mem[i  ]=a; self.mem[i+1]=b;
 331                         self.mem[i+2]=c; self.mem[i+3]=d;
 332                         self.mem[i+4]=e; self.mem[i+5]=f;
 333                         self.mem[i+6]=g; self.mem[i+7]=h;
 334                     }
 335                 }}
 336             );
 337
 338             memloop!(self.rsl);
 339             memloop!(self.mem);
 340         } else {
 341             for i in range(0, RAND_SIZE_64 / 8).map(|i| i * 8) {
 342                 mix!();
 343                 self.mem[i  ]=a; self.mem[i+1]=b;
 344                 self.mem[i+2]=c; self.mem[i+3]=d;
 345                 self.mem[i+4]=e; self.mem[i+5]=f;
 346                 self.mem[i+6]=g; self.mem[i+7]=h;
 347             }
 348         }
 349
 350         self.isaac64();
 351     }
 352
 353     /// Refills the output buffer (`self.rsl`)
 354     fn isaac64(&mut self) {
 355         self.c += 1;
 356         // abbreviations
 357         let mut a = self.a;
 358         let mut b = self.b + self.c;
 359         static MIDPOINT: uint =  RAND_SIZE_64 / 2;
 360         static MP_VEC: [(uint, uint), .. 2] = [(0,MIDPOINT), (MIDPOINT, 0)];
 361         macro_rules! ind (
 362             ($x:expr) => {
 363                 *self.mem.unsafe_get(($x as uint >> 3) & (RAND_SIZE_64 - 1))
 364             }
 365         );
 366
 367         for &(mr_offset, m2_offset) in MP_VEC.iter() {
 368             for base in range(0, MIDPOINT / 4).map(|i| i * 4) {
 369
 370                 macro_rules! rngstepp(
 371                     ($j:expr, $shift:expr) => {{
 372                             let base = base + $j;
 373                             let mix = a ^ (a << $shift as uint);
 374                             let mix = if $j == 0 {!mix} else {mix};
 375
 376                             unsafe {
 377                                 let x = *self.mem.unsafe_get(base + mr_offset);
 378                                 a = mix + *self.mem.unsafe_get(base + m2_offset);
 379                                 let y = ind!(x) + a + b;
 380                                 self.mem.unsafe_set(base + mr_offset, y);
 381
 382                                 b = ind!(y >> RAND_SIZE_64_LEN) + x;
 383                                 self.rsl.unsafe_set(base + mr_offset, b);
 384                             }
 385                         }}
 386                     );
 387                 macro_rules! rngstepn(
 388                     ($j:expr, $shift:expr) => {{
 389                             let base = base + $j;
 390                             let mix = a ^ (a >> $shift as uint);
 391                             let mix = if $j == 0 {!mix} else {mix};
 392
 393                             unsafe {
 394                                 let x = *self.mem.unsafe_get(base + mr_offset);
 395                                 a = mix + *self.mem.unsafe_get(base + m2_offset);
 396                                 let y = ind!(x) + a + b;
 397                                 self.mem.unsafe_set(base + mr_offset, y);
 398
 399                                 b = ind!(y >> RAND_SIZE_64_LEN) + x;
 400                                 self.rsl.unsafe_set(base + mr_offset, b);
 401                             }
 402                         }}
 403                     );
 404                 rngstepp!(0u, 21);
 405                 rngstepn!(1u, 5);
 406                 rngstepp!(2u, 12);
 407                 rngstepn!(3u, 33);
 408             }
 409         }
 410
 411         self.a = a;
 412         self.b = b;
 413         self.cnt = RAND_SIZE_64;
 414     }
 415 }
 416
 417 impl Rng for Isaac64Rng {
 418     // FIXME #7771: having next_u32 like this should be unnecessary
 419     #[inline]
 420     fn next_u32(&mut self) -> u32 {
 421         self.next_u64() as u32
 422     }
 423
 424     #[inline]
 425     fn next_u64(&mut self) -> u64 {
 426         if self.cnt == 0 {
 427             // make some more numbers
 428             self.isaac64();
 429         }
 430         self.cnt -= 1;
 431
 432         // See corresponding location in IsaacRng.next_u32 for
 433         // explanation.
 434         debug_assert!(self.cnt < RAND_SIZE_64)
 435         self.rsl[(self.cnt % RAND_SIZE_64) as uint]
 436     }
 437 }
 438
 439 impl<'a> SeedableRng<&'a [u64]> for Isaac64Rng {
 440     fn reseed(&mut self, seed: &'a [u64]) {
 441         // make the seed into [seed[0], seed[1], ..., seed[seed.len()
 442         // - 1], 0, 0, ...], to fill rng.rsl.
 443         let seed_iter = seed.iter().map(|&x| x).chain(Repeat::new(0u64));
 444
 445         for (rsl_elem, seed_elem) in self.rsl.iter_mut().zip(seed_iter) {
 446             *rsl_elem = seed_elem;
 447         }
 448         self.cnt = 0;
 449         self.a = 0;
 450         self.b = 0;
 451         self.c = 0;
 452
 453         self.init(true);
 454     }
 455
 456     /// Create an ISAAC random number generator with a seed. This can
 457     /// be any length, although the maximum number of elements used is
 458     /// 256 and any more will be silently ignored. A generator
 459     /// constructed with a given seed will generate the same sequence
 460     /// of values as all other generators constructed with that seed.
 461     fn from_seed(seed: &'a [u64]) -> Isaac64Rng {
 462         let mut rng = EMPTY_64;
 463         rng.reseed(seed);
 464         rng
 465     }
 466 }
 467
 468 impl Rand for Isaac64Rng {
 469     fn rand<R: Rng>(other: &mut R) -> Isaac64Rng {
 470         let mut ret = EMPTY_64;
 471         unsafe {
 472             let ptr = ret.rsl.as_mut_ptr();
 473
 474             raw::mut_buf_as_slice(ptr as *mut u8,
 475                                   (RAND_SIZE_64*8) as uint, |slice| {
 476                 other.fill_bytes(slice);
 477             })
 478         }
 479         ret.cnt = 0;
 480         ret.a = 0;
 481         ret.b = 0;
 482         ret.c = 0;
 483
 484         ret.init(true);
 485         return ret;
 486     }
 487 }
 488
 489 #[cfg(test)]
 490 mod test {
 491     use std::prelude::*;
 492
 493     use core::iter::order;
 494     use {Rng, SeedableRng};
 495     use super::{IsaacRng, Isaac64Rng};
 496
 497     #[test]
 498     fn test_rng_32_rand_seeded() {
 499         let s = ::test::rng().gen_iter::<u32>().take(256).collect::<Vec<u32>>();
 500         let mut ra: IsaacRng = SeedableRng::from_seed(s.as_slice());
 501         let mut rb: IsaacRng = SeedableRng::from_seed(s.as_slice());
 502         assert!(order::equals(ra.gen_ascii_chars().take(100),
 503                               rb.gen_ascii_chars().take(100)));
 504     }
 505     #[test]
 506     fn test_rng_64_rand_seeded() {
 507         let s = ::test::rng().gen_iter::<u64>().take(256).collect::<Vec<u64>>();
 508         let mut ra: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
 509         let mut rb: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
 510         assert!(order::equals(ra.gen_ascii_chars().take(100),
 511                               rb.gen_ascii_chars().take(100)));
 512     }
 513
 514     #[test]
 515     fn test_rng_32_seeded() {
 516         let seed: &[_] = &[1, 23, 456, 7890, 12345];
 517         let mut ra: IsaacRng = SeedableRng::from_seed(seed);
 518         let mut rb: IsaacRng = SeedableRng::from_seed(seed);
 519         assert!(order::equals(ra.gen_ascii_chars().take(100),
 520                               rb.gen_ascii_chars().take(100)));
 521     }
 522     #[test]
 523     fn test_rng_64_seeded() {
 524         let seed: &[_] = &[1, 23, 456, 7890, 12345];
 525         let mut ra: Isaac64Rng = SeedableRng::from_seed(seed);
 526         let mut rb: Isaac64Rng = SeedableRng::from_seed(seed);
 527         assert!(order::equals(ra.gen_ascii_chars().take(100),
 528                               rb.gen_ascii_chars().take(100)));
 529     }
 530
 531     #[test]
 532     fn test_rng_32_reseed() {
 533         let s = ::test::rng().gen_iter::<u32>().take(256).collect::<Vec<u32>>();
 534         let mut r: IsaacRng = SeedableRng::from_seed(s.as_slice());
 535         let string1: String = r.gen_ascii_chars().take(100).collect();
 536
 537         r.reseed(s.as_slice());
 538
 539         let string2: String = r.gen_ascii_chars().take(100).collect();
 540         assert_eq!(string1, string2);
 541     }
 542     #[test]
 543     fn test_rng_64_reseed() {
 544         let s = ::test::rng().gen_iter::<u64>().take(256).collect::<Vec<u64>>();
 545         let mut r: Isaac64Rng = SeedableRng::from_seed(s.as_slice());
 546         let string1: String = r.gen_ascii_chars().take(100).collect();
 547
 548         r.reseed(s.as_slice());
 549
 550         let string2: String = r.gen_ascii_chars().take(100).collect();
 551         assert_eq!(string1, string2);
 552     }
 553
 554     #[test]
 555     fn test_rng_32_true_values() {
 556         let seed: &[_] = &[1, 23, 456, 7890, 12345];
 557         let mut ra: IsaacRng = SeedableRng::from_seed(seed);
 558         // Regression test that isaac is actually using the above vector
 559         let v = Vec::from_fn(10, |_| ra.next_u32());
 560         assert_eq!(v,
 561                    vec!(2558573138, 873787463, 263499565, 2103644246, 3595684709,
 562                         4203127393, 264982119, 2765226902, 2737944514, 3900253796));
 563
 564         let seed: &[_] = &[12345, 67890, 54321, 9876];
 565         let mut rb: IsaacRng = SeedableRng::from_seed(seed);
 566         // skip forward to the 10000th number
 567         for _ in range(0u, 10000) { rb.next_u32(); }
 568
 569         let v = Vec::from_fn(10, |_| rb.next_u32());
 570         assert_eq!(v,
 571                    vec!(3676831399, 3183332890, 2834741178, 3854698763, 2717568474,
 572                         1576568959, 3507990155, 179069555, 141456972, 2478885421));
 573     }
 574     #[test]
 575     fn test_rng_64_true_values() {
 576         let seed: &[_] = &[1, 23, 456, 7890, 12345];
 577         let mut ra: Isaac64Rng = SeedableRng::from_seed(seed);
 578         // Regression test that isaac is actually using the above vector
 579         let v = Vec::from_fn(10, |_| ra.next_u64());
 580         assert_eq!(v,
 581                    vec!(547121783600835980, 14377643087320773276, 17351601304698403469,
 582                         1238879483818134882, 11952566807690396487, 13970131091560099343,
 583                         4469761996653280935, 15552757044682284409, 6860251611068737823,
 584                         13722198873481261842));
 585
 586         let seed: &[_] = &[12345, 67890, 54321, 9876];
 587         let mut rb: Isaac64Rng = SeedableRng::from_seed(seed);
 588         // skip forward to the 10000th number
 589         for _ in range(0u, 10000) { rb.next_u64(); }
 590
 591         let v = Vec::from_fn(10, |_| rb.next_u64());
 592         assert_eq!(v,
 593                    vec!(18143823860592706164, 8491801882678285927, 2699425367717515619,
 594                         17196852593171130876, 2606123525235546165, 15790932315217671084,
 595                         596345674630742204, 9947027391921273664, 11788097613744130851,
 596                         10391409374914919106));
 597     }
 598 }