2 // Author: David Bau 3/11/2010
4 // Defines a method Math.seedrandom() that, when called, substitutes
5 // an explicitly seeded RC4-based algorithm for Math.random(). Also
6 // supports automatic seeding from local or network sources of entropy.
10 // <script src=http://davidbau.com/encode/seedrandom-min.js></script>
12 // Math.seedrandom('yipee'); Sets Math.random to a function that is
13 // initialized using the given explicit seed.
15 // Math.seedrandom(); Sets Math.random to a function that is
16 // seeded using the current time, dom state,
17 // and other accumulated local entropy.
18 // The generated seed string is returned.
20 // Math.seedrandom('yowza', true);
21 // Seeds using the given explicit seed mixed
22 // together with accumulated entropy.
24 // <script src="http://bit.ly/srandom-512"></script>
25 // Seeds using physical random bits downloaded
30 // Math.seedrandom("hello"); // Use "hello" as the seed.
31 // document.write(Math.random()); // Always 0.5463663768140734
32 // document.write(Math.random()); // Always 0.43973793770592234
33 // var rng1 = Math.random; // Remember the current prng.
35 // var autoseed = Math.seedrandom(); // New prng with an automatic seed.
36 // document.write(Math.random()); // Pretty much unpredictable.
38 // Math.random = rng1; // Continue "hello" prng sequence.
39 // document.write(Math.random()); // Always 0.554769432473455
41 // Math.seedrandom(autoseed); // Restart at the previous seed.
42 // document.write(Math.random()); // Repeat the 'unpredictable' value.
46 // Each time seedrandom('arg') is called, entropy from the passed seed
47 // is accumulated in a pool to help generate future seeds for the
48 // zero-argument form of Math.seedrandom, so entropy can be injected over
49 // time by calling seedrandom with explicit data repeatedly.
51 // On speed - This javascript implementation of Math.random() is about
52 // 3-10x slower than the built-in Math.random() because it is not native
53 // code, but this is typically fast enough anyway. Seeding is more expensive,
54 // especially if you use auto-seeding. Some details (timings on Chrome 4):
56 // Our Math.random() - avg less than 0.002 milliseconds per call
57 // seedrandom('explicit') - avg less than 0.5 milliseconds per call
58 // seedrandom('explicit', true) - avg less than 2 milliseconds per call
59 // seedrandom() - avg about 38 milliseconds per call
63 // Copyright 2010 David Bau, all rights reserved.
65 // Redistribution and use in source and binary forms, with or without
66 // modification, are permitted provided that the following conditions are met:
68 // 1. Redistributions of source code must retain the above copyright
69 // notice, this list of conditions and the following disclaimer.
71 // 2. Redistributions in binary form must reproduce the above copyright
72 // notice, this list of conditions and the following disclaimer in the
73 // documentation and/or other materials provided with the distribution.
75 // 3. Neither the name of this module nor the names of its contributors may
76 // be used to endorse or promote products derived from this software
77 // without specific prior written permission.
79 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
80 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
81 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
82 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
83 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
84 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
85 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
86 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
87 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
88 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
89 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
92 * All code is in an anonymous closure to keep the global namespace clean.
94 * @param {number=} overflow
95 * @param {number=} startdenom
97 (function (pool
, math
, width
, chunks
, significance
, overflow
, startdenom
) {
102 // This is the seedrandom function described above.
104 math
['seedrandom'] = function seedrandom(seed
, use_entropy
) {
108 // Flatten the seed string or build one from local entropy if needed.
109 seed
= mixkey(flatten(
110 use_entropy
? [seed
, pool
] :
111 arguments
.length
? seed
:
112 [new Date().getTime(), pool
, window
], 3), key
);
114 // Use the seed to initialize an ARC4 generator.
115 arc4
= new ARC4(key
);
117 // Mix the randomness into accumulated entropy.
118 mixkey(arc4
.S
, pool
);
120 // Override Math.random
122 // This function returns a random double in [0, 1) that contains
123 // randomness in every bit of the mantissa of the IEEE 754 value.
125 math
['random'] = function random() { // Closure to return a random double:
126 var n
= arc4
.g(chunks
); // Start with a numerator n < 2 ^ 48
127 var d
= startdenom
; // and denominator d = 2 ^ 48.
128 var x
= 0; // and no 'extra last byte'.
129 while (n
< significance
) { // Fill up all significant digits by
130 n
= (n
+ x
) * width
; // shifting numerator and
131 d
*= width
; // denominator and generating a
132 x
= arc4
.g(1); // new least-significant-byte.
134 while (n
>= overflow
) { // To avoid rounding up, before adding
135 n
/= 2; // last
byte, shift everything
136 d
/= 2; // right using integer math until
137 x
>>>= 1; // we have exactly the desired bits.
139 return (n
+ x
) / d
; // Form the number within [0, 1).
142 // Return the seed that was used
149 // An ARC4 implementation. The constructor takes a key in the form of
150 // an array of at most (width) integers that should be 0 <= x < (width).
152 // The g(count) method returns a pseudorandom integer that concatenates
153 // the next (count) outputs from ARC4. Its return value is a number x
154 // that is in the range 0 <= x < (width ^ count).
158 var t
, u
, me
= this, keylen
= key
.length
;
159 var i
= 0, j
= me
.i
= me
.j
= me
.m
= 0;
163 // The empty key [] is treated as [0].
164 if (!keylen
) { key
= [keylen
++]; }
166 // Set up S using the standard key scheduling algorithm.
167 while (i
< width
) { me
.S
[i
] = i
++; }
168 for (i
= 0; i
< width
; i
++) {
170 j
= lowbits(j
+ t
+ key
[i
% keylen
]);
176 // The "g" method returns the next (count) outputs as one number.
177 me
.g
= function getnext(count
) {
179 var i
= lowbits(me
.i
+ 1); var t
= s
[i
];
180 var j
= lowbits(me
.j
+ t
); var u
= s
[j
];
183 var r
= s
[lowbits(t
+ u
)];
185 i
= lowbits(i
+ 1); t
= s
[i
];
186 j
= lowbits(j
+ t
); u
= s
[j
];
189 r
= r
* width
+ s
[lowbits(t
+ u
)];
195 // For robust unpredictability discard an initial batch of values.
196 // See http://www.rsa.com/rsalabs/node.asp?id=2009
202 // Converts an object tree to nested arrays of strings.
204 /** @param {Object=} result
205 * @param {string=} prop */
206 function flatten(obj
, depth
, result
, prop
) {
208 if (depth
&& typeof(obj
) == 'object') {
210 if (prop
.indexOf('S') < 5) { // Avoid FF3 bug (local/sessionStorage)
211 try { result
.push(flatten(obj
[prop
], depth
- 1)); } catch (e
) {}
215 return result
.length
? result
: '' + obj
;
220 // Mixes a string seed into a key that is an array of integers, and
221 // returns a shortened string seed that is equivalent to the result key.
223 /** @param {number=} smear
224 * @param {number=} j */
225 function mixkey(seed
, key
, smear
, j
) {
226 seed
+= ''; // Ensure the seed is a string
228 for (j
= 0; j
< seed
.length
; j
++) {
230 lowbits((smear
^= key
[lowbits(j
)] * 19) + seed
.charCodeAt(j
));
233 for (j
in key
) { seed
+= String
.fromCharCode(key
[j
]); }
239 // A quick "n mod width" for width a power of 2.
241 function lowbits(n
) { return n
& (width
- 1); }
244 // The following constants are related to IEEE 754 limits.
246 startdenom
= math
.pow(width
, chunks
);
247 significance
= math
.pow(2, significance
);
248 overflow
= significance
* 2;
251 // When seedrandom.js is loaded, we immediately mix a few bits
252 // from the built-in RNG into the entropy pool. Because we do
253 // not want to intefere with determinstic PRNG state later,
254 // seedrandom will not call math.random on its own again after
257 mixkey(math
.random(), pool
);
259 // End anonymous scope, and pass initial values.
261 [], // pool: entropy pool starts empty
262 Math
, // math: package containing random, pow, and seedrandom
263 256, // width: each RC4 output is 0 <= x < 256
264 6, // chunks: at least six RC4 outputs for each double
265 52 // significance: there are 52 significant digits in a double