isaac.js (7625B)
1 /* ---------------------------------------------------------------------- 2 * Copyright (c) 2012 Yves-Marie K. Rinquin 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to deal in the Software without restriction, including 7 * without limitation the rights to use, copy, modify, merge, publish, 8 * distribute, sublicense, and/or sell copies of the Software, and to 9 * permit persons to whom the Software is furnished to do so, subject to 10 * the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be 13 * included in all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 19 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 20 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 21 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 22 * 23 * ---------------------------------------------------------------------- 24 * 25 * ISAAC is a cryptographically secure pseudo-random number generator 26 * (or CSPRNG for short) designed by Robert J. Jenkins Jr. in 1996 and 27 * based on RC4. It is designed for speed and security. 28 * 29 * ISAAC's informations & analysis: 30 * http://burtleburtle.net/bob/rand/isaac.html 31 * ISAAC's implementation details: 32 * http://burtleburtle.net/bob/rand/isaacafa.html 33 * 34 * ISAAC succesfully passed TestU01 35 * 36 * ---------------------------------------------------------------------- 37 * 38 * Usage: 39 * <script src="isaac.js"></script> 40 * var random_number = isaac.random(); 41 * 42 * Output: [ 0x00000000; 0xffffffff] 43 * [-2147483648; 2147483647] 44 * 45 */ 46 47 48 /* js string (ucs-2/utf16) to a 32-bit integer (utf-8 chars, little-endian) array */ 49 String.prototype.toIntArray = function() { 50 var w1, w2, u, r4 = [], r = [], i = 0; 51 var s = this + '\0\0\0'; // pad string to avoid discarding last chars 52 var l = s.length - 1; 53 54 while(i < l) { 55 w1 = s.charCodeAt(i++); 56 w2 = s.charCodeAt(i+1); 57 if (w1 < 0x0080) { 58 // 0x0000 - 0x007f code point: basic ascii 59 r4.push(w1); 60 } else if(w1 < 0x0800) { 61 // 0x0080 - 0x07ff code point 62 r4.push(((w1 >>> 6) & 0x1f) | 0xc0); 63 r4.push(((w1 >>> 0) & 0x3f) | 0x80); 64 } else if((w1 & 0xf800) != 0xd800) { 65 // 0x0800 - 0xd7ff / 0xe000 - 0xffff code point 66 r4.push(((w1 >>> 12) & 0x0f) | 0xe0); 67 r4.push(((w1 >>> 6) & 0x3f) | 0x80); 68 r4.push(((w1 >>> 0) & 0x3f) | 0x80); 69 } else if(((w1 & 0xfc00) == 0xd800) 70 && ((w2 & 0xfc00) == 0xdc00)) { 71 // 0xd800 - 0xdfff surrogate / 0x10ffff - 0x10000 code point 72 u = ((w2 & 0x3f) | ((w1 & 0x3f) << 10)) + 0x10000; 73 r4.push(((u >>> 18) & 0x07) | 0xf0); 74 r4.push(((u >>> 12) & 0x3f) | 0x80); 75 r4.push(((u >>> 6) & 0x3f) | 0x80); 76 r4.push(((u >>> 0) & 0x3f) | 0x80); 77 i++; 78 } else { 79 // invalid char 80 } 81 /* add integer (four utf-8 value) to array */ 82 if(r4.length > 3) { 83 // little endian 84 r.push((r4.shift() << 0) | (r4.shift() << 8) | 85 (r4.shift() << 16) | (r4.shift() << 24)); 86 } 87 } 88 89 return r; 90 } 91 92 /* isaac module pattern */ 93 var isaac = (function(){ 94 95 /* private: internal states */ 96 var m = Array(256), // internal memory 97 acc = 0, // accumulator 98 brs = 0, // last result 99 cnt = 0, // counter 100 r = Array(256), // result array 101 gnt = 0; // generation counter 102 103 seed(Math.random() * 0xffffffff); 104 105 /* private: 32-bit integer safe adder */ 106 function add(x, y) { 107 var lsb = (x & 0xffff) + (y & 0xffff); 108 var msb = (x >>> 16) + (y >>> 16) + (lsb >>> 16); 109 return (msb << 16) | (lsb & 0xffff); 110 } 111 112 /* public: initialisation */ 113 function reset() { 114 acc = brs = cnt = 0; 115 for(var i = 0; i < 256; ++i) 116 m[i] = r[i] = 0; 117 gnt = 0; 118 } 119 120 /* public: seeding function */ 121 function seed(s) { 122 var a, b, c, d, e, f, g, h, i; 123 124 /* seeding the seeds of love */ 125 a = b = c = d = 126 e = f = g = h = 0x9e3779b9; /* the golden ratio */ 127 128 if(s && typeof(s) === 'string') 129 s = s.toIntArray(); 130 131 if(s && typeof(s) === 'number') { 132 s = [s]; 133 } 134 135 if(s instanceof Array) { 136 reset(); 137 for(i = 0; i < s.length; i++) 138 r[i & 0xff] += (typeof(s[i]) === 'number') ? s[i] : 0; 139 } 140 141 /* private: seed mixer */ 142 function seed_mix() { 143 a ^= b << 11; d = add(d, a); b = add(b, c); 144 b ^= c >>> 2; e = add(e, b); c = add(c, d); 145 c ^= d << 8; f = add(f, c); d = add(d, e); 146 d ^= e >>> 16; g = add(g, d); e = add(e, f); 147 e ^= f << 10; h = add(h, e); f = add(f, g); 148 f ^= g >>> 4; a = add(a, f); g = add(g, h); 149 g ^= h << 8; b = add(b, g); h = add(h, a); 150 h ^= a >>> 9; c = add(c, h); a = add(a, b); 151 } 152 153 for(i = 0; i < 4; i++) /* scramble it */ 154 seed_mix(); 155 156 for(i = 0; i < 256; i += 8) { 157 if(s) { /* use all the information in the seed */ 158 a = add(a, r[i + 0]); b = add(b, r[i + 1]); 159 c = add(c, r[i + 2]); d = add(d, r[i + 3]); 160 e = add(e, r[i + 4]); f = add(f, r[i + 5]); 161 g = add(g, r[i + 6]); h = add(h, r[i + 7]); 162 } 163 seed_mix(); 164 /* fill in m[] with messy stuff */ 165 m[i + 0] = a; m[i + 1] = b; m[i + 2] = c; m[i + 3] = d; 166 m[i + 4] = e; m[i + 5] = f; m[i + 6] = g; m[i + 7] = h; 167 } 168 if(s) { 169 /* do a second pass to make all of the seed affect all of m[] */ 170 for(i = 0; i < 256; i += 8) { 171 a = add(a, m[i + 0]); b = add(b, m[i + 1]); 172 c = add(c, m[i + 2]); d = add(d, m[i + 3]); 173 e = add(e, m[i + 4]); f = add(f, m[i + 5]); 174 g = add(g, m[i + 6]); h = add(h, m[i + 7]); 175 seed_mix(); 176 /* fill in m[] with messy stuff (again) */ 177 m[i + 0] = a; m[i + 1] = b; m[i + 2] = c; m[i + 3] = d; 178 m[i + 4] = e; m[i + 5] = f; m[i + 6] = g; m[i + 7] = h; 179 } 180 } 181 182 prng(); /* fill in the first set of results */ 183 gnt = 256; /* prepare to use the first set of results */; 184 } 185 186 /* public: isaac generator, n = number of run */ 187 function prng(n){ 188 var i, x, y; 189 190 n = (n && typeof(n) === 'number') 191 ? Math.abs(Math.floor(n)) : 1; 192 193 while(n--) { 194 cnt = add(cnt, 1); 195 brs = add(brs, cnt); 196 197 for(i = 0; i < 256; i++) { 198 switch(i & 3) { 199 case 0: acc ^= acc << 13; break; 200 case 1: acc ^= acc >>> 6; break; 201 case 2: acc ^= acc << 2; break; 202 case 3: acc ^= acc >>> 16; break; 203 } 204 acc = add(m[(i + 128) & 0xff], acc); x = m[i]; 205 m[i] = y = add(m[(x >>> 2) & 0xff], add(acc, brs)); 206 r[i] = brs = add(m[(y >>> 10) & 0xff], x); 207 } 208 } 209 } 210 211 /* public: return a random number between */ 212 function rand() { 213 if(!gnt--) { 214 prng(); gnt = 255; 215 } 216 return r[gnt]; 217 } 218 219 /* public: return internals in an object*/ 220 function internals(){ 221 return {a: acc, b: brs, c: cnt, m: m, r: r}; 222 } 223 224 function random(){ 225 return 0.5 + this.rand() * 2.3283064365386963e-10; // 2^-32 226 } 227 228 /* return class object */ 229 return { 230 'reset': reset, 231 'seed': seed, 232 'prng': prng, 233 'rand': rand, 234 'random': random, 235 'internals': internals 236 }; 237 })(); /* declare and execute */ 238 239 ( "undefined" !== ( typeof( module ) ) ) && module.exports && ( module.exports = isaac );