author | Shu-yu Guo <shu@rfrn.org> |
Tue, 14 May 2013 19:23:20 -0700 | |
changeset 143443 | 04155dec2ead2dbc7bc13192d200785213d2476b |
parent 143442 | 1d3b60ab634a346cd61e288ec6b9a6629552f539 |
child 143444 | 4667ec13bb63766ee8c694e801491d10949c209a |
push id | 2697 |
push user | bbajaj@mozilla.com |
push date | Mon, 05 Aug 2013 18:49:53 +0000 |
treeherder | mozilla-beta@dfec938c7b63 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | nmatsakis |
bugs | 872352 |
milestone | 24.0a1 |
first release with | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
last release without | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
js/src/parjs-benchmarks/nbody-seeded.js | file | annotate | diff | comparison | revisions | |
js/src/parjs-benchmarks/seedrandom.js | file | annotate | diff | comparison | revisions |
new file mode 100644 --- /dev/null +++ b/js/src/parjs-benchmarks/nbody-seeded.js @@ -0,0 +1,554 @@ +// +// NBody adapted from Intel's nbody benchmark. +// + +load(libdir + "util.js"); +load(libdir + "seedrandom.js"); + +var NBody = { + Constant: { + "deltaTime": 1, // 0.005 in their code. + "epsSqr": 50, // softening factor, when they compute, set to 50. + "initialVelocity": 8 // set to 0 to turn off + }, + + init: function init(mode, numBodies) { + var initPos = new Array(numBodies); + var initVel = new Array(numBodies); + + // initialization of inputs + for (var i = 0; i < numBodies; i++) { + // [x,y,z] + initPos[i] = [Math.floor((Math.random()) * 40000), + Math.floor((Math.random()) * 20000), + Math.floor((Math.random() - .25) * 50000)]; + + // [x,y,z,x,y,z] + initVel[i] = [(Math.random() - 0.5) * NBody.Constant.initialVelocity, + (Math.random() - 0.5) * NBody.Constant.initialVelocity, + (Math.random()) * NBody.Constant.initialVelocity + 10, + + (Math.random() - 0.5) * NBody.Constant.initialVelocity, + (Math.random() - 0.5) * NBody.Constant.initialVelocity, + (Math.random()) * NBody.Constant.initialVelocity]; + } + + NBody.private = {}; + + if (mode === "par") { + NBody.private.pos = new ParallelArray(initPos); + NBody.private.vel = new ParallelArray(initVel); + } else { + NBody.private.pos = initPos; + NBody.private.vel = initVel; + } + + NBody.numBodies = numBodies; + NBody.time = 0; + }, + + // Parallel + + tickPar: function tickPar() { + NBody.private.vel = new ParallelArray([NBody.numBodies], NBody.velocityPar); + NBody.private.pos = new ParallelArray([NBody.numBodies], NBody.positionPar); + NBody.time++; + }, + + velocityPar: function velocityPar(index) { + var pos = NBody.private.pos; + var vel = NBody.private.vel; + + var deltaTime = NBody.Constant.deltaTime; + var epsSqr = NBody.Constant.epsSqr; + var time = NBody.time; + + var shape = vel.shape[0]; + + var newVel; + var newX, newY, newZ; + var newX2, newY2, newZ2; + + var cX = Math.cos(time / 22) * -4200; + var cY = Math.sin(time / 14) * 9200; + var cZ = Math.sin(time / 27) * 6000; + + // pull to center + var maxDistance = 3400; + var pullStrength = .042; + + var speedLimit = 8; + + // zones + var zone = 400; + var repel = 100; + var align = 300; + var attract = 100; + + if (time < 500) { + speedLimit = 2000; + var attractPower = 100.9; + } else { + speedLimit = .2; + attractPower = 20.9; + } + + var zoneSqrd = zone * zone + zone * zone + zone * zone; + + var accX = 0, accY = 0, accZ = 0; + var accX2 = 0, accY2 = 0, accZ2 = 0; + var i; + + // define particle 1 center distance + var dirToCenterX = cX - pos.get(index)[0]; + var dirToCenterY = cY - pos.get(index)[1]; + var dirToCenterZ = cZ - pos.get(index)[2]; + + var distanceSquaredTo = dirToCenterX * dirToCenterX + dirToCenterY * dirToCenterY + dirToCenterZ * dirToCenterZ; + var distToCenter = Math.sqrt(distanceSquaredTo); + + // orient to center + if (distToCenter > maxDistance) { + var velc = (distToCenter - maxDistance) * pullStrength; + if (time < 200) + velc = .2; + else velc = (distToCenter - maxDistance) * pullStrength; + + accX += (dirToCenterX / distToCenter) * velc; + accY += (dirToCenterY / distToCenter) * velc; + accZ += (dirToCenterZ / distToCenter) * velc; + } + + for (i = 0; i < shape; i = i + 1) { + var rx = pos.get(i)[0] - pos.get(index)[0]; + var ry = pos.get(i)[1] - pos.get(index)[1]; + var rz = pos.get(i)[2] - pos.get(index)[2]; + + // make sure we are not testing the particle against its own position + var areSame = 0; + if (pos.get(i)[0] == pos.get(index)[0] && pos.get(i)[1] == pos.get(index)[1] && pos.get(i)[2] == pos.get(index)[2]) + areSame += 1; + + var distSqrd = rx * rx + ry * ry + rz * rz; + + // cant use eqals to test, only <= or >= WTF + if (distSqrd < zoneSqrd && areSame <= 0) { + var length = Math.sqrt(distSqrd); + var percent = distSqrd / zoneSqrd; + + if (distSqrd < repel) { + var F = (repel / percent - 1) * .025; + + var normalRx = (rx / length) * F; + var normalRy = (ry / length) * F; + var normalRz = (rz / length) * F; + + accX = accX + normalRx; + accY = accY + normalRy; + accZ = accZ + normalRz; + + accX2 = accX2 - normalRx; + accY2 = accY2 - normalRy; + accZ2 = accZ2 - normalRz; + } else if (distSqrd < align) { //align + var threshDelta = align - repel; + var adjustedPercent = (percent - repel) / threshDelta; + var Q = (.5 - Math.cos(adjustedPercent * 3.14159265 * 2) * .5 + .5) * 100.9; + + // get velocity 2 + var velX2 = vel.get(i)[4]; + var velY2 = vel.get(i)[5]; + var velZ2 = vel.get(i)[6]; + + var velLength2 = Math.sqrt(velX2 * velX2 + velY2 * velY2 + velZ2 * velZ2); + + // normalize vel2 and multiply by factor + velX2 = (velX2 / velLength2) * Q; + velY2 = (velY2 / velLength2) * Q; + velZ2 = (velZ2 / velLength2) * Q; + + // get own velocity + var velX = vel.get(i)[0]; + var velY = vel.get(i)[1]; + var velZ = vel.get(i)[2]; + + var velLength = Math.sqrt(velX * velX + velY * velY + velZ * velZ); + + // normalize own velocity + velX = (velX / velLength) * Q; + velY = (velY / velLength) * Q; + velZ = (velZ / velLength) * Q; + + accX += velX2; + accY += velY2; + accZ += velZ2; + + accX2 += velX; + accY2 += velY; + accZ2 += velZ; + } + + if (distSqrd > attract) { // attract + var threshDelta2 = 1 - attract; + var adjustedPercent2 = (percent - attract) / threshDelta2; + var C = (1 - (Math.cos(adjustedPercent2 * 3.14159265 * 2) * 0.5 + 0.5)) * attractPower; + + // normalize the distance vector + var dx = (rx / (length)) * C; + var dy = (ry / (length)) * C; + var dz = (rz / (length)) * C; + + accX += dx; + accY += dy; + accZ += dz; + + accX2 -= dx; + accY2 -= dy; + accZ2 -= dz; + } + } + } + + // Speed limits + if (time > 500) { + var accSquared = accX * accX + accY * accY + accZ * accZ; + if (accSquared > speedLimit) { + accX = accX * .015; + accY = accY * .015; + accZ = accZ * .015; + } + + var accSquared2 = accX2 * accX2 + accY2 * accY2 + accZ2 * accZ2; + if (accSquared2 > speedLimit) { + accX2 = accX2 * .015; + accY2 = accY2 * .015; + accZ2 = accZ2 * .015; + } + } + + // Caclulate new velocity + newX = (vel.get(index)[0]) + accX; + newY = (vel.get(index)[1]) + accY; + newZ = (vel.get(index)[2]) + accZ; + + newX2 = (vel.get(index)[3]) + accX2; + newY2 = (vel.get(index)[4]) + accY2; + newZ2 = (vel.get(index)[5]) + accZ2; + + if (time < 500) { + var acs = newX2 * newX2 + newY2 * newY2 + newZ2 * newZ2; + if (acs > speedLimit) { + newX2 = newX2 * .15; + newY2 = newY2 * .15; + newZ2 = newZ2 * .15; + } + + var acs2 = newX * newX + newY * newY + newZ * newZ; + if (acs2 > speedLimit) { + newX = newX * .15; + newY = newY * .15; + newZ = newZ * .15; + } + } + + return [newX, newY, newZ, newX2, newY2, newZ2]; + }, + + positionPar: function positionPar(index) { + var vel = NBody.private.vel; + var pos = NBody.private.pos; + + var x = 0; + var y = 0; + var z = 0; + + var velX = vel.get(index)[0]; + var velY = vel.get(index)[1]; + var velZ = vel.get(index)[2]; + + var velX2 = vel.get(index)[3]; + var velY2 = vel.get(index)[4]; + var velZ2 = vel.get(index)[5]; + + var netVelX = (velX - velX2); + var netVelY = (velY - velY2); + var netVelZ = (velZ - velZ2); + + x = pos.get(index)[0] + (netVelX); + y = pos.get(index)[1] + (netVelY); + z = pos.get(index)[2] + (netVelZ); + + return [x, y, z]; + }, + + // Sequential + + tickSeq: function tickSeq() { + var numBodies = NBody.numBodies; + var newVel = new Array(numBodies); + var newPos = new Array(numBodies); + + for (var i = 0; i < numBodies; i++) + newVel[i] = NBody.velocitySeq(i); + + for (var i = 0; i < numBodies; i++) + newPos[i] = NBody.positionSeq(i); + + NBody.private.vel = newVel; + NBody.private.pos = newPos; + + NBody.time++; + }, + + velocitySeq: function velocitySeq(index) { + var vel = NBody.private.vel; + var pos = NBody.private.pos; + + var deltaTime = NBody.Constant.deltaTime; + var epsSqr = NBody.Constant.epsSqr; + var time = NBody.time; + + var shape = pos.length; + + var newVel; + var newX, newY, newZ; + var newX2, newY2, newZ2; + + var cX = Math.cos(time / 22) * -4200; + var cY = Math.sin(time / 14) * 9200; + var cZ = Math.sin(time / 27) * 6000; + + // pull to center + var maxDistance = 3400; + var pullStrength = .042; + + var speedLimit = 8; + + // zones + var zone = 400; + var repel = 100; + var align = 300; + var attract = 100; + + + if (time < 500) { + speedLimit = 2000; + var attractPower = 100.9; + } else { + speedLimit = .2; + attractPower = 20.9; + } + + var zoneSqrd = zone * zone + zone * zone + zone * zone; + + var accX = 0, accY = 0, accZ = 0; + var accX2 = 0, accY2 = 0, accZ2 = 0; + var i; + + // define particle 1 center distance + var dirToCenterX = cX - pos[index][0]; + var dirToCenterY = cY - pos[index][1]; + var dirToCenterZ = cZ - pos[index][2]; + + var distanceSquaredTo = dirToCenterX * dirToCenterX + dirToCenterY * dirToCenterY + dirToCenterZ * dirToCenterZ; + var distToCenter = Math.sqrt(distanceSquaredTo); + + // orient to center + if (distToCenter > maxDistance) { + var velc = (distToCenter - maxDistance) * pullStrength; + if (time < 200) + velc = .2; + else velc = (distToCenter - maxDistance) * pullStrength; + + accX += (dirToCenterX / distToCenter) * velc; + accY += (dirToCenterY / distToCenter) * velc; + accZ += (dirToCenterZ / distToCenter) * velc; + } + + for (i = 0; i < shape; i = i + 1) { + var rx = pos[i][0] - pos[index][0]; + var ry = pos[i][1] - pos[index][1]; + var rz = pos[i][2] - pos[index][2]; + + var areSame = 0; + if (pos[i][0] == pos[index][0] && pos[i][1] == pos[index][1] && pos[i][2] == pos[index][2]) + areSame += 1; + + var distSqrd = rx * rx + ry * ry + rz * rz; + + // cant use eqals to test, only <= or >= WTF + if (distSqrd < zoneSqrd && areSame <= 0) { + var length = Math.sqrt(distSqrd); + var percent = distSqrd / zoneSqrd; + + + if (distSqrd < repel) { + var F = (repel / percent - 1) * .025; + + var normalRx = (rx / length) * F; + var normalRy = (ry / length) * F; + var normalRz = (rz / length) * F; + + accX = accX + normalRx; + accY = accY + normalRy; + accZ = accZ + normalRz; + + accX2 = accX2 - normalRx; + accY2 = accY2 - normalRy; + accZ2 = accZ2 - normalRz; + } else if (distSqrd < align) { //align + var threshDelta = align - repel; + var adjustedPercent = (percent - repel) / threshDelta; + var Q = (.5 - Math.cos(adjustedPercent * 3.14159265 * 2) * .5 + .5) * 100; + + // get velocity 2 + var velX2 = vel[i][3]; + var velY2 = vel[i][4]; + var velZ2 = vel[i][5]; + + var velLength2 = Math.sqrt(velX2 * velX2 + velY2 * velY2 + velZ2 * velZ2); + + // normalize vel2 and multiply by factor + velX2 = (velX2 / velLength2) * Q; + velY2 = (velY2 / velLength2) * Q; + velZ2 = (velZ2 / velLength2) * Q; + + // get own velocity + var velX = vel[i][0]; + var velY = vel[i][1]; + var velZ = vel[i][2]; + + var velLength = Math.sqrt(velX * velX + velY * velY + velZ * velZ); + + // normalize own velocity + velX = (velX / velLength) * Q; + velY = (velY / velLength) * Q; + velZ = (velZ / velLength) * Q; + + accX += velX2; + accY += velY2; + accZ += velZ2; + + accX2 += velX; + accY2 += velY; + accZ2 += velZ; + } + + if (distSqrd > attract) { //attract + var threshDelta2 = 1 - align; + var adjustedPercent2 = (percent - align) / threshDelta2; + var C = (1 - (Math.cos(adjustedPercent2 * 3.14159265 * 2) * 0.5 + 0.5)) * attractPower; + + // normalize the distance vector + var dx = (rx / (length)) * C; + var dy = (ry / (length)) * C; + var dz = (rz / (length)) * C; + + debug = 1.1; + + accX += dx; + accY += dy; + accZ += dz; + + accX2 -= dx; + accY2 -= dy; + accZ2 -= dz; + } + } + } + + // enforce speed limits + if (time > 500) { + var accSquared = accX * accX + accY * accY + accZ * accZ; + if (accSquared > speedLimit) { + accX = accX * .015; + accY = accY * .015; + accZ = accZ * .015; + } + + var accSquared2 = accX2 * accX2 + accY2 * accY2 + accZ2 * accZ2; + if (accSquared2 > speedLimit) { + accX2 = accX2 * .015; + accY2 = accY2 * .015; + accZ2 = accZ2 * .015; + } + } + + // Caclulate new velocity + newX = vel[index][0] + accX; + newY = vel[index][1] + accY; + newZ = vel[index][2] + accZ; + + newX2 = vel[index][3] + accX2; + newY2 = vel[index][4] + accY2; + newZ2 = vel[index][5] + accZ2; + + if (time < 500) { + var acs = newX2 * newX2 + newY2 * newY2 + newZ2 * newZ2; + if (acs > speedLimit) { + newX2 = newX2 * .15; + newY2 = newY2 * .15; + newZ2 = newZ2 * .15; + } + + var acs2 = newX * newX + newY * newY + newZ * newZ; + if (acs2 > speedLimit) { + newX = newX * .15; + newY = newY * .15; + newZ = newZ * .15; + } + } + + return [newX, newY, newZ, newX2, newY2, newZ2]; + }, + + positionSeq: function positionSeq(index) { + var vel = NBody.private.vel; + var pos = NBody.private.pos; + + var x = 0; + var y = 0; + var z = 0; + + var velX = vel[index][0]; + var velY = vel[index][1]; + var velZ = vel[index][2]; + + var velX2 = vel[index][3]; + var velY2 = vel[index][4]; + var velZ2 = vel[index][5]; + + var netX = (velX - velX2); + var netY = (velY - velY2); + var netZ = (velZ - velZ2); + + x = pos[index][0] + netX; + y = pos[index][1] + netY; + z = pos[index][2] + netZ; + + return [x, y, z]; + } +}; + +function emulateNBody(mode, numBodies, ticks) { + NBody.init(mode, numBodies); + for (var i = 0; i < ticks; i++) { + var start = Date.now(); + if (mode === "par") + NBody.tickPar(); + else + NBody.tickSeq(); + //print(NBody.private.pos); + print(mode + " bodies=" + numBodies + " tick=" + (i+1) + "/" + ticks + ": " + (Date.now() - start) + " ms"); + } +} + +// Using 4000 bodies going off Rick's comment as 4000 being a typical workload. +const NUMBODIES = 4000; +const TICKS = 10; + +Math.seedrandom("seed"); + +benchmark("NBODY", 1, DEFAULT_MEASURE, + function () { emulateNBody("seq", NUMBODIES, TICKS); }, + function () { emulateNBody("par", NUMBODIES, TICKS); });
new file mode 100644 --- /dev/null +++ b/js/src/parjs-benchmarks/seedrandom.js @@ -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: +// +// <script src=http://davidbau.com/encode/seedrandom-min.js></script> +// +// 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. +// +// <script src="https://jsonlib.appspot.com/urandom?callback=Math.seedrandom"> +// </script> 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 +);