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