1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/parjs-benchmarks/seedrandom.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,299 @@
1.4 +// seedrandom.js version 2.1.
1.5 +// Author: David Bau
1.6 +// Date: 2013 Mar 16
1.7 +//
1.8 +// Defines a method Math.seedrandom() that, when called, substitutes
1.9 +// an explicitly seeded RC4-based algorithm for Math.random(). Also
1.10 +// supports automatic seeding from local or network sources of entropy.
1.11 +//
1.12 +// http://davidbau.com/encode/seedrandom.js
1.13 +// http://davidbau.com/encode/seedrandom-min.js
1.14 +//
1.15 +// Usage:
1.16 +//
1.17 +// <script src=http://davidbau.com/encode/seedrandom-min.js></script>
1.18 +//
1.19 +// Math.seedrandom('yay.'); Sets Math.random to a function that is
1.20 +// initialized using the given explicit seed.
1.21 +//
1.22 +// Math.seedrandom(); Sets Math.random to a function that is
1.23 +// seeded using the current time, dom state,
1.24 +// and other accumulated local entropy.
1.25 +// The generated seed string is returned.
1.26 +//
1.27 +// Math.seedrandom('yowza.', true);
1.28 +// Seeds using the given explicit seed mixed
1.29 +// together with accumulated entropy.
1.30 +//
1.31 +// <script src="https://jsonlib.appspot.com/urandom?callback=Math.seedrandom">
1.32 +// </script> Seeds using urandom bits from a server.
1.33 +//
1.34 +// More advanced examples:
1.35 +//
1.36 +// Math.seedrandom("hello."); // Use "hello." as the seed.
1.37 +// document.write(Math.random()); // Always 0.9282578795792454
1.38 +// document.write(Math.random()); // Always 0.3752569768646784
1.39 +// var rng1 = Math.random; // Remember the current prng.
1.40 +//
1.41 +// var autoseed = Math.seedrandom(); // New prng with an automatic seed.
1.42 +// document.write(Math.random()); // Pretty much unpredictable x.
1.43 +//
1.44 +// Math.random = rng1; // Continue "hello." prng sequence.
1.45 +// document.write(Math.random()); // Always 0.7316977468919549
1.46 +//
1.47 +// Math.seedrandom(autoseed); // Restart at the previous seed.
1.48 +// document.write(Math.random()); // Repeat the 'unpredictable' x.
1.49 +//
1.50 +// function reseed(event, count) { // Define a custom entropy collector.
1.51 +// var t = [];
1.52 +// function w(e) {
1.53 +// t.push([e.pageX, e.pageY, +new Date]);
1.54 +// if (t.length < count) { return; }
1.55 +// document.removeEventListener(event, w);
1.56 +// Math.seedrandom(t, true); // Mix in any previous entropy.
1.57 +// }
1.58 +// document.addEventListener(event, w);
1.59 +// }
1.60 +// reseed('mousemove', 100); // Reseed after 100 mouse moves.
1.61 +//
1.62 +// Version notes:
1.63 +//
1.64 +// The random number sequence is the same as version 1.0 for string seeds.
1.65 +// Version 2.0 changed the sequence for non-string seeds.
1.66 +// Version 2.1 speeds seeding and uses window.crypto to autoseed if present.
1.67 +//
1.68 +// The standard ARC4 key scheduler cycles short keys, which means that
1.69 +// seedrandom('ab') is equivalent to seedrandom('abab') and 'ababab'.
1.70 +// Therefore it is a good idea to add a terminator to avoid trivial
1.71 +// equivalences on short string seeds, e.g., Math.seedrandom(str + '\0').
1.72 +// Starting with version 2.0, a terminator is added automatically for
1.73 +// non-string seeds, so seeding with the number 111 is the same as seeding
1.74 +// with '111\0'.
1.75 +//
1.76 +// When seedrandom() is called with zero args, it uses a seed
1.77 +// drawn from the browser crypto object if present. If there is no
1.78 +// crypto support, seedrandom() uses the current time, the native rng,
1.79 +// and a walk of several DOM objects to collect a few bits of entropy.
1.80 +//
1.81 +// Each time the one- or two-argument forms of seedrandom are called,
1.82 +// entropy from the passed seed is accumulated in a pool to help generate
1.83 +// future seeds for the zero- and two-argument forms of seedrandom.
1.84 +//
1.85 +// On speed - This javascript implementation of Math.random() is about
1.86 +// 3-10x slower than the built-in Math.random() because it is not native
1.87 +// code, but that is typically fast enough. Some details (timings on
1.88 +// Chrome 25 on a 2010 vintage macbook):
1.89 +//
1.90 +// seeded Math.random() - avg less than 0.0002 milliseconds per call
1.91 +// seedrandom('explicit.') - avg less than 0.2 milliseconds per call
1.92 +// seedrandom('explicit.', true) - avg less than 0.2 milliseconds per call
1.93 +// seedrandom() with crypto - avg less than 0.2 milliseconds per call
1.94 +// seedrandom() without crypto - avg about 12 milliseconds per call
1.95 +//
1.96 +// On a 2012 windows 7 1.5ghz i5 laptop, Chrome, Firefox 19, IE 10, and
1.97 +// Opera have similarly fast timings. Slowest numbers are on Opera, with
1.98 +// about 0.0005 milliseconds per seeded Math.random() and 15 milliseconds
1.99 +// for autoseeding.
1.100 +//
1.101 +// LICENSE (BSD):
1.102 +//
1.103 +// Copyright 2013 David Bau, all rights reserved.
1.104 +//
1.105 +// Redistribution and use in source and binary forms, with or without
1.106 +// modification, are permitted provided that the following conditions are met:
1.107 +//
1.108 +// 1. Redistributions of source code must retain the above copyright
1.109 +// notice, this list of conditions and the following disclaimer.
1.110 +//
1.111 +// 2. Redistributions in binary form must reproduce the above copyright
1.112 +// notice, this list of conditions and the following disclaimer in the
1.113 +// documentation and/or other materials provided with the distribution.
1.114 +//
1.115 +// 3. Neither the name of this module nor the names of its contributors may
1.116 +// be used to endorse or promote products derived from this software
1.117 +// without specific prior written permission.
1.118 +//
1.119 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.120 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.121 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.122 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.123 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.124 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.125 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.126 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.127 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.128 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.129 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.130 +//
1.131 +/**
1.132 + * All code is in an anonymous closure to keep the global namespace clean.
1.133 + */
1.134 +(function (
1.135 + global, pool, math, width, chunks, digits) {
1.136 +
1.137 +//
1.138 +// The following constants are related to IEEE 754 limits.
1.139 +//
1.140 +var startdenom = math.pow(width, chunks),
1.141 + significance = math.pow(2, digits),
1.142 + overflow = significance * 2,
1.143 + mask = width - 1;
1.144 +
1.145 +//
1.146 +// seedrandom()
1.147 +// This is the seedrandom function described above.
1.148 +//
1.149 +math['seedrandom'] = function(seed, use_entropy) {
1.150 + var key = [];
1.151 +
1.152 + // Flatten the seed string or build one from local entropy if needed.
1.153 + var shortseed = mixkey(flatten(
1.154 + use_entropy ? [seed, tostring(pool)] :
1.155 + 0 in arguments ? seed : autoseed(), 3), key);
1.156 +
1.157 + // Use the seed to initialize an ARC4 generator.
1.158 + var arc4 = new ARC4(key);
1.159 +
1.160 + // Mix the randomness into accumulated entropy.
1.161 + mixkey(tostring(arc4.S), pool);
1.162 +
1.163 + // Override Math.random
1.164 +
1.165 + // This function returns a random double in [0, 1) that contains
1.166 + // randomness in every bit of the mantissa of the IEEE 754 value.
1.167 +
1.168 + math['random'] = function() { // Closure to return a random double:
1.169 + var n = arc4.g(chunks), // Start with a numerator n < 2 ^ 48
1.170 + d = startdenom, // and denominator d = 2 ^ 48.
1.171 + x = 0; // and no 'extra last byte'.
1.172 + while (n < significance) { // Fill up all significant digits by
1.173 + n = (n + x) * width; // shifting numerator and
1.174 + d *= width; // denominator and generating a
1.175 + x = arc4.g(1); // new least-significant-byte.
1.176 + }
1.177 + while (n >= overflow) { // To avoid rounding up, before adding
1.178 + n /= 2; // last byte, shift everything
1.179 + d /= 2; // right using integer math until
1.180 + x >>>= 1; // we have exactly the desired bits.
1.181 + }
1.182 + return (n + x) / d; // Form the number within [0, 1).
1.183 + };
1.184 +
1.185 + // Return the seed that was used
1.186 + return shortseed;
1.187 +};
1.188 +
1.189 +//
1.190 +// ARC4
1.191 +//
1.192 +// An ARC4 implementation. The constructor takes a key in the form of
1.193 +// an array of at most (width) integers that should be 0 <= x < (width).
1.194 +//
1.195 +// The g(count) method returns a pseudorandom integer that concatenates
1.196 +// the next (count) outputs from ARC4. Its return value is a number x
1.197 +// that is in the range 0 <= x < (width ^ count).
1.198 +//
1.199 +/** @constructor */
1.200 +function ARC4(key) {
1.201 + var t, keylen = key.length,
1.202 + me = this, i = 0, j = me.i = me.j = 0, s = me.S = [];
1.203 +
1.204 + // The empty key [] is treated as [0].
1.205 + if (!keylen) { key = [keylen++]; }
1.206 +
1.207 + // Set up S using the standard key scheduling algorithm.
1.208 + while (i < width) {
1.209 + s[i] = i++;
1.210 + }
1.211 + for (i = 0; i < width; i++) {
1.212 + s[i] = s[j = mask & (j + key[i % keylen] + (t = s[i]))];
1.213 + s[j] = t;
1.214 + }
1.215 +
1.216 + // The "g" method returns the next (count) outputs as one number.
1.217 + (me.g = function(count) {
1.218 + // Using instance members instead of closure state nearly doubles speed.
1.219 + var t, r = 0,
1.220 + i = me.i, j = me.j, s = me.S;
1.221 + while (count--) {
1.222 + t = s[i = mask & (i + 1)];
1.223 + r = r * width + s[mask & ((s[i] = s[j = mask & (j + t)]) + (s[j] = t))];
1.224 + }
1.225 + me.i = i; me.j = j;
1.226 + return r;
1.227 + // For robust unpredictability discard an initial batch of values.
1.228 + // See http://www.rsa.com/rsalabs/node.asp?id=2009
1.229 + })(width);
1.230 +}
1.231 +
1.232 +//
1.233 +// flatten()
1.234 +// Converts an object tree to nested arrays of strings.
1.235 +//
1.236 +function flatten(obj, depth) {
1.237 + var result = [], typ = (typeof obj)[0], prop;
1.238 + if (depth && typ == 'o') {
1.239 + for (prop in obj) {
1.240 + if (obj.hasOwnProperty(prop)) {
1.241 + try { result.push(flatten(obj[prop], depth - 1)); } catch (e) {}
1.242 + }
1.243 + }
1.244 + }
1.245 + return (result.length ? result : typ == 's' ? obj : obj + '\0');
1.246 +}
1.247 +
1.248 +//
1.249 +// mixkey()
1.250 +// Mixes a string seed into a key that is an array of integers, and
1.251 +// returns a shortened string seed that is equivalent to the result key.
1.252 +//
1.253 +function mixkey(seed, key) {
1.254 + var stringseed = seed + '', smear, j = 0;
1.255 + while (j < stringseed.length) {
1.256 + key[mask & j] =
1.257 + mask & ((smear ^= key[mask & j] * 19) + stringseed.charCodeAt(j++));
1.258 + }
1.259 + return tostring(key);
1.260 +}
1.261 +
1.262 +//
1.263 +// autoseed()
1.264 +// Returns an object for autoseeding, using window.crypto if available.
1.265 +//
1.266 +/** @param {Uint8Array=} seed */
1.267 +function autoseed(seed) {
1.268 + try {
1.269 + global.crypto.getRandomValues(seed = new Uint8Array(width));
1.270 + return tostring(seed);
1.271 + } catch (e) {
1.272 + return [+new Date, global.document, global.history,
1.273 + global.navigator, global.screen, tostring(pool)];
1.274 + }
1.275 +}
1.276 +
1.277 +//
1.278 +// tostring()
1.279 +// Converts an array of charcodes to a string
1.280 +//
1.281 +function tostring(a) {
1.282 + return String.fromCharCode.apply(0, a);
1.283 +}
1.284 +
1.285 +//
1.286 +// When seedrandom.js is loaded, we immediately mix a few bits
1.287 +// from the built-in RNG into the entropy pool. Because we do
1.288 +// not want to intefere with determinstic PRNG state later,
1.289 +// seedrandom will not call math.random on its own again after
1.290 +// initialization.
1.291 +//
1.292 +mixkey(math.random(), pool);
1.293 +
1.294 +// End anonymous scope, and pass initial values.
1.295 +})(
1.296 + this, // global window object
1.297 + [], // pool: entropy pool starts empty
1.298 + Math, // math: package containing random, pow, and seedrandom
1.299 + 256, // width: each RC4 output is 0 <= x < 256
1.300 + 6, // chunks: at least six RC4 outputs for each double
1.301 + 52 // digits: there are 52 significant digits in a double
1.302 +);
