🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

xorshift

Package Overview
Dependencies
Maintainers
1
Versions
7
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

xorshift - npm Package Compare versions

Comparing version

0.1.0
to
0.2.0

.travis.yml
benchmark.js
compare.js
reference.json

4

LICENSE.md

@@ -1,2 +0,2 @@

Copyright (c) 2012 Andreas Madsen
Copyright (c) 2014 Andreas Madsen & Emil Bay

@@ -19,2 +19,2 @@ Permission is hereby granted, free of charge, to any person obtaining a copy

OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
THE SOFTWARE.

10

package.json
{
"name": "xorshift",
"description": "Random number generator using xorshift",
"version": "0.1.0",
"description": "Random number generator using xorshift128+",
"version": "0.2.0",
"author": "Andreas Madsen <amwebdk@gmail.com>",
"contributors": [
"Emil Bay <github@tixz.dk>"
],
"main": "./xorshift.js",
"scripts": {
"test": "tap test.js"
"test": "tap test.js",
"benchmark": "node ./benchmark.js"
},

@@ -10,0 +14,0 @@ "repository" : {

104

README.md

@@ -1,4 +0,4 @@

#xorshift
#xorshift [![Build Status](https://travis-ci.org/AndreasMadsen/xorshift.svg?branch=master)](https://travis-ci.org/AndreasMadsen/xorshift)
> Random number generator using xorshift
> Random number generator using xorshift128+

@@ -8,32 +8,104 @@ ## Installation

```sheel
NOT YET PUBLISHED # npm install xorshift
# npm install xorshift
```
## Documentation
## Example
```javascript
var xorshift = require('xorshift')
var bview = require('binary-view');
var xorshift = require('xorshift');
for (var i = 0; i < 10; i++) {
console.log(bview(xorshift()));
console.log(xorshift.random()); // number in range [0, 1)
}
```
## Testing
## Documentation
This repo also contains an reference implementation of the 128bit xorshift.
First you should compile the code.
This module exports a default pseudo random generator. This generators seed have
already been set (using `Date.now()`). If this is not suitable a custom
generator can be initialized using the constructor function
`xorshift.constructor`. In both cases random numbers can be generated using
the two methods, `.random` and `.randomint`.
```shell
gcc -O2 reference.c -o reference
```javascript
var xorshift = require('xorshift');
```
Next you should execute the binary
### xorshift.random()
This method returns a random 64bit double, with its value in the range [0, 1).
That means 0 is inclusive and 1 is exclusive. This is completely similar to
`Math.random()`.
```javascript
console.log(xorshift.random()); // number between 0 and 1
```
This method will serve most purposes, for instance to randomly select between
2, 3 and 4, this function can be used:
```javascript
function uniformint(a, b) {
return Math.floor(a + xorshift().random() * (b - a));
}
console.log(uniformint(2, 4));
```
### xorshift.randomint()
This method returns a random 64bit integer. Since JavaScript don't support
64bit integers, the number is represented as an array with two elements in
big-endian order.
This method is useful if high precision is required, the `xorshift.random()`
method won't allow you to get this precision since a 64bit IEEE754 double
only contains the 52 most significant bits.
```javascript
var bview = require('binary-view');
console.log(bview( new Uint32Array(xorshift.randomint()) ));
```
### xorshift.constructor
This method is used to construct a new random generator, with a specific seed.
This can be useful when testing software where random numbers are involved and
getting consistent results are important.
```javascript
var XorShift = require('xorshift').constructor;
var rng1 = new XorShift([1, 0, 2, 0]);
var rng2 = new XorShift([1, 0, 2, 0]);
assert(rng1.random() === rng2.random());
```
A `XorShift` instance have both methods `random` and `randomint`. In fact the
`xorshift` module is an instance of the `XorShift` constructor.
## Reference
This module implements the xorshift128+ pseudo random number generator.
> This is the fastest generator passing BigCrush without systematic
> errors, but due to the relatively short period it is acceptable only
> for applications with a very mild amount of parallelism; otherwise, use
> a xorshift1024* generator.
> – <cite> http://xorshift.di.unimi.it </cite>
This source also have a
[reference implementation](http://xorshift.di.unimi.it/xorshift128plus.c)
for the xorshift128+ generator. A wrapper around this implementation have been
created and is used for testing this module. To compile and run it:
```shell
./reference <numbers>
gcc -O2 reference.c -o reference
./reference <numbers> <seed0> <seed1>
```
`<numbers>` can be any number greater than zero, and it will be the amount
* `<numbers>` can be any number greater than zero, and it will be the amount
if random numbers in the stdout. The default value is `10`.
* `<seed0>` and `<seed1>` forms the 128bit seed that the algorithm uses. Default
is `[1, 2]`.

@@ -44,3 +116,3 @@ ##License

> Copyright (c) 2014
> Copyright (c) 2014 Andreas Madsen & Emil Bay
>

@@ -47,0 +119,0 @@ > Permission is hereby granted, free of charge, to any person obtaining a copy

113

test.js
var os = require('os');
var test = require('tap').test;
var xorshift = require('./xorshift.js');
var reference = require('./reference.json');
function hexview(arr) {
var a = arr[0].toString(16);
var b = arr[1].toString(16);
a = (new Array(9 - a.length)).join(0) + a;
b = (new Array(9 - b.length)).join(0) + b;
return (a + b).toUpperCase();
}
test('random double', function (t) {
t.test('with seed = [1, 2]', function (t) {
var ref = reference['1-2'];
var rng = xorshift.constructor([0, 1, 0, 2]);
for (var i = 0; i < ref.length; i++) {
t.equal(rng.random(), parseInt(ref[i], 16) / Math.pow(2, 64));
}
t.end();
});
t.test('with seed = [3, 4]', function (t) {
var ref = reference['3-4'];
var rng = xorshift.constructor([0, 3, 0, 4]);
for (var i = 0; i < ref.length; i++) {
t.equal(rng.random(), parseInt(ref[i], 16) / Math.pow(2, 64));
}
t.end();
});
t.end();
});
test('random int array', function (t) {
t.test('with seed = [1, 2]', function (t) {
var ref = reference['1-2'];
var rng = xorshift.constructor([0, 1, 0, 2]);
for (var i = 0; i < ref.length; i++) {
t.strictEqual(hexview(rng.randomint()), ref[i]);
}
t.end();
});
t.test('with seed = [3, 4]', function (t) {
var ref = reference['3-4'];
var rng = xorshift.constructor([0, 3, 0, 4]);
for (var i = 0; i < ref.length; i++) {
t.strictEqual(hexview(rng.randomint()), ref[i]);
}
t.end();
});
t.end();
});
test('default instance', function (t) {
t.test('random int', function (t) {
// demand that the 100 first outputs are different
var obj = Object.create(null);
for (var i = 0; i< 100; i++) {
obj[hexview(xorshift.randomint())] = 1;
}
t.equal(Object.keys(obj).length, 100);
t.end();
});
t.test('random double', function (t) {
// demand that the 100 first outputs are different
var obj = Object.create(null);
for (var i = 0; i< 100; i++) {
var rand = xorshift.random();
obj[rand.toExponential(20)] = 1;
t.ok(rand >= 0 && rand < 1, 'random double is [0, 1)');
}
t.equal(Object.keys(obj).length, 100);
t.end();
});
t.end();
});
test('bad initialization', function (t) {
t.test('wrong input type', function (t) {
var error = null;
try {
xorshift.constructor("0102");
} catch (e) { error = e; }
t.equal(error.name, 'TypeError');
t.equal(error.message, 'seed must be an array with 4 numbers');
t.end();
});
t.test('wrong array length', function (t) {
var error = null;
try {
xorshift.constructor([1, 2, 0]);
} catch (e) { error = e; }
t.equal(error.name, 'TypeError');
t.equal(error.message, 'seed must be an array with 4 numbers');
t.end();
});
t.end();
});

177

xorshift.js
var bview = require('binary-view');
/**
* Create a pseudorandom number generator, with a seed.
* @param {array} seed "128-bit" integer, composed of 4x32-bit
* integers in big endian order.
*/
function XorShift(seed) {
// Note the extension, this === module.exports is required because
// the `constructor` function will be used to generate new instances.
// In that case `this` will point to the default RNG, and `this` will
// be an instance of XorShift.
if (!(this instanceof XorShift) || this === module.exports) {
return new XorShift(seed);
}
var s = new Uint32Array(4);
var s16 = new Uint16Array(s.buffer);
if (!Array.isArray(seed) || seed.length !== 4) {
throw new TypeError('seed must be an array with 4 numbers');
}
function leftShift(read, write, amount) {
var s0 = read[0];
var s1 = read[1];
var m = 0xFFFFFFFF << (32 - amount);
write[0] = (s0 << amount) | ((s1 & m) >>> (32 - amount));
write[1] = s1 << amount;
// uint64_t s = [seed ...]
this._state0U = seed[0] | 0;
this._state0L = seed[1] | 0;
this._state1U = seed[2] | 0;
this._state1L = seed[3] | 0;
}
function xor(readA, readB, write) {
write[0] = readA[0] ^ readB[0];
write[1] = readA[1] ^ readB[1];
}
/**
* Returns a 64bit random number as a 2x32bit array
* @return {array}
*/
XorShift.prototype.randomint = function() {
// uint64_t s1 = s[0]
var s1U = this._state0U, s1L = this._state0L;
// uint64_t s0 = s[1]
var s0U = this._state1U, s0L = this._state1L;
function rightShift(read, write, amount) {
var s0 = read[0];
var s1 = read[1];
// s[0] = s0
this._state0U = s0U;
this._state0L = s0L;
var m = 0xFFFFFFFF >>> (32 - amount);
write[1] = (s1 >>> amount) | ((s0 & m) << (32 - amount));
write[0] = s0 >>> amount;
}
// - t1 = [0, 0]
var t1U = 0, t1L = 0;
// - t2 = [0, 0]
var t2U = 0, t2L = 0;
function add(readA, readB, write) {
var readA16 = new Uint16Array(readA.buffer);
var readB16 = new Uint16Array(readB.buffer);
var write16 = new Uint16Array(write.buffer);
// s1 ^= s1 << 23;
// :: t1 = s1 << 23
var a1 = 23;
var m1 = 0xFFFFFFFF << (32 - a1);
t1U = (s1U << a1) | ((s1L & m1) >>> (32 - a1));
t1L = s1L << a1;
// :: s1 = s1 ^ t1
s1U = s1U ^ t1U;
s1L = s1L ^ t1L;
var a00 = readA16[2];
var a01 = readA16[3];
var a10 = readA16[0];
var a11 = readA16[1];
// t1 = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) )
// :: t1 = s1 ^ s0
t1U = s1U ^ s0U;
t1L = s1L ^ s0L;
// :: t2 = s1 >> 17
var a2 = 17;
var m2 = 0xFFFFFFFF >>> (32 - a2);
t2U = s1U >>> a2;
t2L = (s1L >>> a2) | ((s1U & m2) << (32 - a2));
// :: t1 = t1 ^ t2
t1U = t1U ^ t2U;
t1L = t1L ^ t2L;
// :: t2 = s0 >> 26
var a3 = 26;
var m3 = 0xFFFFFFFF >>> (32 - a3);
t2U = s0U >>> a3;
t2L = (s0L >>> a3) | ((s0U & m3) << (32 - a3));
// :: t1 = t1 ^ t2
t1U = t1U ^ t2U;
t1L = t1L ^ t2L;
var b00 = readB16[2];
var b01 = readB16[3];
var b10 = readB16[0];
var b11 = readB16[1];
// s[1] = t1
this._state1U = t1U;
this._state1L = t1L;
c00 = a00 + b00;
c01 = a01 + b01 + (c00 >>> 16);
c10 = a10 + b10 + (c01 >>> 16);
c11 = a11 + b11 + (c10 >>> 16);
// return t1 + s0
// :: t2 = t1 + s0
var sumL = (t1L >>> 0) + (s0L >>> 0);
t2U = (t1U + s0U + (sumL / 2 >>> 31)) >>> 0;
t2L = sumL >>> 0;
write16[2] = c00;
write16[3] = c01;
write16[0] = c10;
write16[1] = c11;
}
// :: ret t2
return [t2U, t2L];
};
s[1] = 1;
s[3] = 2;
/**
* Returns a random number normalized [0, 1), just like Math.random()
* @return {number}
*/
XorShift.prototype.random = function() {
var t2 = this.randomint();
function xorshift() {
var t1 = new Uint32Array(2);
var t2 = new Uint32Array(2);
// :: ret t2 / 2**64
return (t2[0] * 4294967296 + t2[1]) / 18446744073709551616;
};
// uint64_t s1 = s[ 0 ];
var s1 = new Uint32Array(s.subarray(0, 2));
// const uint64_t s0 = s[ 1 ];
var s0 = new Uint32Array(s.subarray(2, 4));
// There is nothing particularly scientific about this seed, it is just
// based on the clock.
module.exports = new XorShift([
0, Date.now() / 65536,
0, Date.now() % 65536
]);
// s[ 0 ] = s0;
s[0] = s0[0];
s[1] = s0[1];
// s1 ^= s1 << 23;
leftShift(s1, t1, 23);
xor(s1, t1, s1);
// k = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) )
xor(s1, s0, t1);
rightShift(s1, t2, 17);
xor(t1, t2, t1);
rightShift(s0, t2, 26);
xor(t1, t2, t1);
// s[1] = k
s[2] = t1[0];
s[3] = t1[1];
// return k + s0
add(t1, s0, t2);
return t2;
}
module.exports = xorshift;
// Perform 20 iterations in the RNG, this prevens a short seed from generating
// pseudo predictable number.
(function () {
var rng = module.exports;
for (var i = 0; i < 20; i++) {
rng.randomint();
}
})();
.npmignore

Sorry, the diff of this file is not supported yet

reference.c

Sorry, the diff of this file is not supported yet