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