seedable PRNG from hash

README.md

PCG

This is a PRNG, built on Jacob Rus' implementation and modified slightly for a user-friendly API.

See here for source: https://observablehq.com/@jrus/permuted-congruential-generator

Usage

import PCGR from './pcgr.js';

const random = PCGR();

// get random values between 0 (inclusive) and 1 (exclusive)
const a = random.next();

// reset state to a deterministic 64-bit seed
random.seed(mySeed);

// or, reset state to a non-deterministic browser-random seed
random.seed(null);

// continue generating random values...
const b = random.next();

Seed from Hash

If you have a hash with 64 bits or more, you can use this to get a seed from it.

Note: This takes the first 64 bits of the hash; maybe another solution would somehow use more bits in the hash.

// example hash, e.g. Ethereum token ID
const hash = '0xa7d8d9ef8d8ce8992df33d8b8cf4aebabd5bd270';

// Generate RNG
const seed = getStateFromHash(hash);
const random = PCGR(seed);
console.log(random.next());

// Take lower 64 bits from a 0x-prefixed hash and return 64 bit integer
function getStateFromHash(hash) {
  // get bytes, let's assume the hash is at least 64bit long
  const nBytes = 8;
  const bytes = [];
  for (let j = 0; j < nBytes; j++) {
    const e0 = 2 + 2 * j;
    bytes.push(parseInt(hash.slice(e0, e0 + 2), 16));
  }

  // Get a 64-bit integer stored in 4-element uint16array from the 8 bytes
  const uint16 = new Uint16Array(4);
  const dv = new DataView(uint16.buffer);
  for (let i = 0; i < nBytes; i++) {
    dv.setUint8(i, bytes[i % bytes.length]);
  }
  return uint16;
}

Update: Seed from Full Hash

I've added another solution to use the entire hash (so that any small change in the string produces a new PRNG). This is done by hashing the decimal bytes to two different unsigned 32-bit integers, and then combining them into a 64 bit seed.

See x_hash.js.

pcgr.js

// This is a copy of Jacob Rus' PCG Random Number Generator,
// and only slightly modified to include additional API features.
// https://observablehq.com/@jrus/permuted-congruential-generator

// Gets a seed state from pure browser randomness
export function getRandomState() {
  const state = new Uint16Array(4);
  for (let i = 0; i < state.length; i++) {
    state[i] = Math.random() * 0x10000;
  }
  return state;
}

// Gets a PRNG based pn PCG
export default function PCGR(initialState = getRandomState()) {
  // Note that the index order [0, 1, 2, 3] is little-endian
  const eps = Math.pow(2, -32),
    m0 = 0x7f2d,
    m1 = 0x4c95,
    m2 = 0xf42d,
    m3 = 0x5851, // 6364136223846793005
    a0 = 0x814f,
    a1 = 0xf767,
    a2 = 0x7b7e,
    a3 = 0x1405; // 1442695040888963407

  let state = new Uint16Array(4);
  seed(initialState);

  return {
    seed,
    next() {
      // Advance internal state
      const s0 = state[0],
        s1 = state[1],
        s2 = state[2],
        s3 = state[3],
        new0 = (a0 + m0 * s0) | 0,
        new1 = (a1 + m0 * s1 + (m1 * s0 + (new0 >>> 16))) | 0,
        new2 = (a2 + m0 * s2 + m1 * s1 + (m2 * s0 + (new1 >>> 16))) | 0,
        new3 = a3 + m0 * s3 + (m1 * s2 + m2 * s1) + (m3 * s0 + (new2 >>> 16));
      (state[0] = new0), (state[1] = new1), (state[2] = new2);
      state[3] = new3;

      // Calculate output function (XSH RR), uses old state
      const xorshifted =
          (s3 << 21) + (((s3 >> 2) ^ s2) << 5) + (((s2 >> 2) ^ s1) >> 11),
        out_int32 =
          (xorshifted >>> (s3 >> 11)) | (xorshifted << (-(s3 >> 11) & 31));
      return eps * (out_int32 >>> 0);
    },
  };

  function seed(newState) {
    if (!newState) {
      newState = getRandomState();
    }
    for (let i = 0; i < state.length; i++) {
      state[i] = newState[i];
    }
  }
}

x_hash.js

// Gets a 64-bit seed state from a long hash string 0xFFFFFF...
// The hash is expected to be 0x-prefixed and in pairs of hex decimals
export function getStateFromHash(hash) {
  const nBytes = Math.floor((hash.length - 2) / 2);
  const bytes = [];
  for (let j = 0; j < nBytes; j++) {
    const e0 = 2 + 2 * j;
    bytes.push(parseInt(hash.slice(e0, e0 + 2), 16));
  }

  // to keep it simple, we just use 32bit murmur2 with two different seeds
  const seed_a = 2690382925;
  const seed_b = 42970470;
  const lower = hash32(bytes, seed_a);
  const upper = hash32(bytes, seed_b);
  const uint16 = new Uint16Array(4);
  const dv = new DataView(uint16.buffer);
  dv.setUint32(0, lower);
  dv.setUint32(4, upper);
  return uint16;
}

function hash32(bytes, seed = 0) {
  // murmur2 32bit
  // https://github.com/garycourt/murmurhash-js/blob/master/murmurhash2_gc.js

  var mask = 0xffff;
  var maskByte = 0xff;
  var m = 0x5bd1e995;
  var l = bytes.length,
    h = seed ^ l,
    i = 0,
    k;

  while (l >= 4) {
    k =
      (bytes[i] & maskByte) |
      ((bytes[++i] & maskByte) << 8) |
      ((bytes[++i] & maskByte) << 16) |
      ((bytes[++i] & maskByte) << 24);
    k = (k & mask) * m + ((((k >>> 16) * m) & mask) << 16);
    k ^= k >>> 24;
    k = (k & mask) * m + ((((k >>> 16) * m) & mask) << 16);
    h = ((h & mask) * m + ((((h >>> 16) * m) & mask) << 16)) ^ k;
    l -= 4;
    ++i;
  }

  switch (l) {
    case 3:
      h ^= (bytes[i + 2] & maskByte) << 16;
    case 2:
      h ^= (bytes[i + 1] & maskByte) << 8;
    case 1:
      h ^= bytes[i] & maskByte;
      h = (h & mask) * m + ((((h >>> 16) * m) & mask) << 16);
  }

  h ^= h >>> 13;
  h = (h & mask) * m + ((((h >>> 16) * m) & mask) << 16);
  h ^= h >>> 15;
  return h >>> 0;
}