diff -r 000000000000 -r 6474c204b198 js/src/parjs-benchmarks/seedrandom.js --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/parjs-benchmarks/seedrandom.js Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,299 @@ +// seedrandom.js version 2.1. +// Author: David Bau +// Date: 2013 Mar 16 +// +// Defines a method Math.seedrandom() that, when called, substitutes +// an explicitly seeded RC4-based algorithm for Math.random(). Also +// supports automatic seeding from local or network sources of entropy. +// +// http://davidbau.com/encode/seedrandom.js +// http://davidbau.com/encode/seedrandom-min.js +// +// Usage: +// +// +// +// Math.seedrandom('yay.'); Sets Math.random to a function that is +// initialized using the given explicit seed. +// +// Math.seedrandom(); Sets Math.random to a function that is +// seeded using the current time, dom state, +// and other accumulated local entropy. +// The generated seed string is returned. +// +// Math.seedrandom('yowza.', true); +// Seeds using the given explicit seed mixed +// together with accumulated entropy. +// +// Seeds using urandom bits from a server. +// +// More advanced examples: +// +// Math.seedrandom("hello."); // Use "hello." as the seed. +// document.write(Math.random()); // Always 0.9282578795792454 +// document.write(Math.random()); // Always 0.3752569768646784 +// var rng1 = Math.random; // Remember the current prng. +// +// var autoseed = Math.seedrandom(); // New prng with an automatic seed. +// document.write(Math.random()); // Pretty much unpredictable x. +// +// Math.random = rng1; // Continue "hello." prng sequence. +// document.write(Math.random()); // Always 0.7316977468919549 +// +// Math.seedrandom(autoseed); // Restart at the previous seed. +// document.write(Math.random()); // Repeat the 'unpredictable' x. +// +// function reseed(event, count) { // Define a custom entropy collector. +// var t = []; +// function w(e) { +// t.push([e.pageX, e.pageY, +new Date]); +// if (t.length < count) { return; } +// document.removeEventListener(event, w); +// Math.seedrandom(t, true); // Mix in any previous entropy. +// } +// document.addEventListener(event, w); +// } +// reseed('mousemove', 100); // Reseed after 100 mouse moves. +// +// Version notes: +// +// The random number sequence is the same as version 1.0 for string seeds. +// Version 2.0 changed the sequence for non-string seeds. +// Version 2.1 speeds seeding and uses window.crypto to autoseed if present. +// +// The standard ARC4 key scheduler cycles short keys, which means that +// seedrandom('ab') is equivalent to seedrandom('abab') and 'ababab'. +// Therefore it is a good idea to add a terminator to avoid trivial +// equivalences on short string seeds, e.g., Math.seedrandom(str + '\0'). +// Starting with version 2.0, a terminator is added automatically for +// non-string seeds, so seeding with the number 111 is the same as seeding +// with '111\0'. +// +// When seedrandom() is called with zero args, it uses a seed +// drawn from the browser crypto object if present. If there is no +// crypto support, seedrandom() uses the current time, the native rng, +// and a walk of several DOM objects to collect a few bits of entropy. +// +// Each time the one- or two-argument forms of seedrandom are called, +// entropy from the passed seed is accumulated in a pool to help generate +// future seeds for the zero- and two-argument forms of seedrandom. +// +// On speed - This javascript implementation of Math.random() is about +// 3-10x slower than the built-in Math.random() because it is not native +// code, but that is typically fast enough. Some details (timings on +// Chrome 25 on a 2010 vintage macbook): +// +// seeded Math.random() - avg less than 0.0002 milliseconds per call +// seedrandom('explicit.') - avg less than 0.2 milliseconds per call +// seedrandom('explicit.', true) - avg less than 0.2 milliseconds per call +// seedrandom() with crypto - avg less than 0.2 milliseconds per call +// seedrandom() without crypto - avg about 12 milliseconds per call +// +// On a 2012 windows 7 1.5ghz i5 laptop, Chrome, Firefox 19, IE 10, and +// Opera have similarly fast timings. Slowest numbers are on Opera, with +// about 0.0005 milliseconds per seeded Math.random() and 15 milliseconds +// for autoseeding. +// +// LICENSE (BSD): +// +// Copyright 2013 David Bau, all rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright +// notice, this list of conditions and the following disclaimer in the +// documentation and/or other materials provided with the distribution. +// +// 3. Neither the name of this module nor the names of its contributors may +// be used to endorse or promote products derived from this software +// without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +/** + * All code is in an anonymous closure to keep the global namespace clean. + */ +(function ( + global, pool, math, width, chunks, digits) { + +// +// The following constants are related to IEEE 754 limits. +// +var startdenom = math.pow(width, chunks), + significance = math.pow(2, digits), + overflow = significance * 2, + mask = width - 1; + +// +// seedrandom() +// This is the seedrandom function described above. +// +math['seedrandom'] = function(seed, use_entropy) { + var key = []; + + // Flatten the seed string or build one from local entropy if needed. + var shortseed = mixkey(flatten( + use_entropy ? [seed, tostring(pool)] : + 0 in arguments ? seed : autoseed(), 3), key); + + // Use the seed to initialize an ARC4 generator. + var arc4 = new ARC4(key); + + // Mix the randomness into accumulated entropy. + mixkey(tostring(arc4.S), pool); + + // Override Math.random + + // This function returns a random double in [0, 1) that contains + // randomness in every bit of the mantissa of the IEEE 754 value. + + math['random'] = function() { // Closure to return a random double: + var n = arc4.g(chunks), // Start with a numerator n < 2 ^ 48 + d = startdenom, // and denominator d = 2 ^ 48. + x = 0; // and no 'extra last byte'. + while (n < significance) { // Fill up all significant digits by + n = (n + x) * width; // shifting numerator and + d *= width; // denominator and generating a + x = arc4.g(1); // new least-significant-byte. + } + while (n >= overflow) { // To avoid rounding up, before adding + n /= 2; // last byte, shift everything + d /= 2; // right using integer math until + x >>>= 1; // we have exactly the desired bits. + } + return (n + x) / d; // Form the number within [0, 1). + }; + + // Return the seed that was used + return shortseed; +}; + +// +// ARC4 +// +// An ARC4 implementation. The constructor takes a key in the form of +// an array of at most (width) integers that should be 0 <= x < (width). +// +// The g(count) method returns a pseudorandom integer that concatenates +// the next (count) outputs from ARC4. Its return value is a number x +// that is in the range 0 <= x < (width ^ count). +// +/** @constructor */ +function ARC4(key) { + var t, keylen = key.length, + me = this, i = 0, j = me.i = me.j = 0, s = me.S = []; + + // The empty key [] is treated as [0]. + if (!keylen) { key = [keylen++]; } + + // Set up S using the standard key scheduling algorithm. + while (i < width) { + s[i] = i++; + } + for (i = 0; i < width; i++) { + s[i] = s[j = mask & (j + key[i % keylen] + (t = s[i]))]; + s[j] = t; + } + + // The "g" method returns the next (count) outputs as one number. + (me.g = function(count) { + // Using instance members instead of closure state nearly doubles speed. + var t, r = 0, + i = me.i, j = me.j, s = me.S; + while (count--) { + t = s[i = mask & (i + 1)]; + r = r * width + s[mask & ((s[i] = s[j = mask & (j + t)]) + (s[j] = t))]; + } + me.i = i; me.j = j; + return r; + // For robust unpredictability discard an initial batch of values. + // See http://www.rsa.com/rsalabs/node.asp?id=2009 + })(width); +} + +// +// flatten() +// Converts an object tree to nested arrays of strings. +// +function flatten(obj, depth) { + var result = [], typ = (typeof obj)[0], prop; + if (depth && typ == 'o') { + for (prop in obj) { + if (obj.hasOwnProperty(prop)) { + try { result.push(flatten(obj[prop], depth - 1)); } catch (e) {} + } + } + } + return (result.length ? result : typ == 's' ? obj : obj + '\0'); +} + +// +// mixkey() +// Mixes a string seed into a key that is an array of integers, and +// returns a shortened string seed that is equivalent to the result key. +// +function mixkey(seed, key) { + var stringseed = seed + '', smear, j = 0; + while (j < stringseed.length) { + key[mask & j] = + mask & ((smear ^= key[mask & j] * 19) + stringseed.charCodeAt(j++)); + } + return tostring(key); +} + +// +// autoseed() +// Returns an object for autoseeding, using window.crypto if available. +// +/** @param {Uint8Array=} seed */ +function autoseed(seed) { + try { + global.crypto.getRandomValues(seed = new Uint8Array(width)); + return tostring(seed); + } catch (e) { + return [+new Date, global.document, global.history, + global.navigator, global.screen, tostring(pool)]; + } +} + +// +// tostring() +// Converts an array of charcodes to a string +// +function tostring(a) { + return String.fromCharCode.apply(0, a); +} + +// +// When seedrandom.js is loaded, we immediately mix a few bits +// from the built-in RNG into the entropy pool. Because we do +// not want to intefere with determinstic PRNG state later, +// seedrandom will not call math.random on its own again after +// initialization. +// +mixkey(math.random(), pool); + +// End anonymous scope, and pass initial values. +})( + this, // global window object + [], // pool: entropy pool starts empty + Math, // math: package containing random, pow, and seedrandom + 256, // width: each RC4 output is 0 <= x < 256 + 6, // chunks: at least six RC4 outputs for each double + 52 // digits: there are 52 significant digits in a double +);