Simple pseudo-random generator using SFC32

seeded-random.ts

/**
 * This is a simple PRNG I built for fun using the SFC32 algorithm by Chris Doty-Humphrey.
 *
 * This code is provided without any warranty, express or implied, and is hereby placed in the public domain.
 *
 * If you're looking for a good quality pseudo-random generator as an NPM package, I recommend `pure-rand`.
 */

/* eslint-disable unicorn/prefer-code-point */
/* eslint-disable unicorn/prefer-math-trunc */

// SFC32 internal state is 128 bits, which is four 32-bit integers
const SFC32_STATE_SIZE = 4

// Using (21, 9, 3) as in the original implementation
const SFC32_BARREL_SHIFT = 21
const SFC32_RSHIFT = 9
const SFC32_LSHIFT = 3

// Twelve rounds of seeding are used by the original author
const SFC32_SEED_ROUNDS = 12

// Based on some not-very-scientific testing, there doesn't seem to be much benefit to seeding more than twice per character
const SFC32_PER_STRING_CHARACTER_SEED_ROUNDS = 2

const MANTISSA_SIZE = Math.pow(2, 52)

const MASK_LOWER_20 = 0b1111_1111_1111_1111_1111

// Default seed to ensure that even an uninitialized generator will produce evenly distributed outputs
const DEFAULT_SEED = [
  0x54_0e_85_92, 0x6f_a3_2b_71, 0x4d_ff_ec_78, 0xfe_eb_3f_c8,
]

export class SeededRandomGenerator {
  #state = new Uint32Array(SFC32_STATE_SIZE) as Uint32Array &
    [a: number, b: number, c: number, counter: number]

  constructor(
    seed?: readonly [a: number, b: number, c: number, counter: number]
  ) {
    for (let index = 0; index < SFC32_STATE_SIZE; index++) {
      this.#state[index] = (seed ?? DEFAULT_SEED)[index]!
    }
  }

  /**
   * Low-level function used for adding entropy to the generator.
   *
   * @param seed - A 32-bit or 52-bit integer seed.
   */
  private unsafeSeedStep(seed: number) {
    this.#state[1] = seed ^ this.#state[1]
    this.#state[2] = (seed / Math.pow(2, 32)) ^ this.#state[2]
    this.#state[3]++
  }

  /**
   * Seed the generator with an integer.
   *
   * @param seed - A 32-bit or 52-bit integer seed.
   */
  seedInteger(seed: number) {
    if (!Number.isInteger(seed)) {
      throw new TypeError(`Seed must be an integer`)
    }

    this.unsafeSeedStep(seed)

    for (let index = 0; index < SFC32_SEED_ROUNDS; index++) {
      this.nextUint32()
    }

    return this
  }

  /**
   * Seed the generator with a string.
   *
   * @param seed - Any JavaScript string.
   */
  seedString(seed: string) {
    for (let index = 0; index < seed.length; index++) {
      this.unsafeSeedStep(seed.charCodeAt(index))
      for (
        let index = 0;
        index < SFC32_PER_STRING_CHARACTER_SEED_ROUNDS;
        index++
      ) {
        this.nextUint32()
      }
    }

    for (let index = 0; index < SFC32_SEED_ROUNDS; index++) {
      this.nextUint32()
    }

    return this
  }

  /**
   * Generate a pseudo-random integer in the range [0, 2^32) using the SFC32 algorithm.
   *
   * @remarks
   *
   * The algorithm was originally developed by Chris Doty-Humphrey who placed it in the public domain, see: https://pracrand.sourceforge.net/license.txt
   *
   * Each call to this method will advance the internal state of the generator by one turn.
   *
   * @returns A pseudo-random unsigned 32-bit integer.
   */
  nextUint32() {
    const value = (this.#state[0] + this.#state[1] + this.#state[3]++) | 0
    this.#state[0] = this.#state[1] ^ (this.#state[1] >>> SFC32_RSHIFT)
    this.#state[1] = this.#state[2] + (this.#state[2] << SFC32_LSHIFT)
    this.#state[2] =
      ((this.#state[2] << SFC32_BARREL_SHIFT) |
        (this.#state[2] >>> SFC32_BARREL_SHIFT)) +
      value
    return value >>> 0
  }

  /**
   * Pseudo-random replacement for Math.random() using the SFC32 algorithm.
   *
   * @remarks
   *
   * Just like Math.random(), this function will return a positive double-precision floating point number with an exponent of zero and a random mantissa. This means that the resulting number is in the range [0, 1).
   *
   * Each invokation advances the internal state of the generator by two turns.
   *
   * @returns A pseudo-random floating point number in the range [0, 1).
   */
  nextDouble() {
    return (
      ((this.nextUint32() & MASK_LOWER_20) * Math.pow(2, 32) +
        this.nextUint32()) /
      MANTISSA_SIZE
    )
  }

  get state() {
    const stateCopy = new Uint32Array(SFC32_STATE_SIZE)
    stateCopy.set(this.#state)
    return stateCopy
  }

  set state(newState: Uint32Array) {
    if (newState.length !== SFC32_STATE_SIZE) {
      throw new TypeError(
        `State must be an array of ${SFC32_STATE_SIZE} 32-bit integers`
      )
    }

    this.#state.set(newState)
  }

  static fromStringSeed(seed: string) {
    return new SeededRandomGenerator().seedString(seed)
  }

  static fromIntegerSeed(seed: number) {
    return new SeededRandomGenerator().seedInteger(seed)
  }
}

if (import.meta.vitest) {
  const { describe } = import.meta.vitest
  describe("SeededRandomGenerator", () => {
    describe("nextUint32", (it) => {
      it("should generate numbers in the proper range", ({ expect }) => {
        const generator = SeededRandomGenerator.fromStringSeed("test-range")

        const pseudoRandomNumbers = Array.from({ length: 100 }, () =>
          generator.nextUint32()
        )

        for (const number of pseudoRandomNumbers) {
          expect(number).toBeGreaterThanOrEqual(0)
          expect(number).toBeLessThan(Math.pow(2, 32))
        }
      })

      it("should generate the same sequence of uint32 for the same seed", ({
        expect,
      }) => {
        const generator1 = SeededRandomGenerator.fromStringSeed("test")
        const generator2 = SeededRandomGenerator.fromStringSeed("test")

        const pseudoRandomNumbers1 = Array.from({ length: 100 }, () =>
          generator1.nextUint32()
        )
        const pseudoRandomNumbers2 = Array.from({ length: 100 }, () =>
          generator2.nextUint32()
        )

        expect(pseudoRandomNumbers1).toEqual(pseudoRandomNumbers2)
      })

      it("should generate the same sequence of uint32 for the same seed as before", ({
        expect,
      }) => {
        const generator = SeededRandomGenerator.fromStringSeed("test")

        const pseudoRandomNumbers = Array.from({ length: 10 }, () =>
          generator.nextUint32()
        )

        expect(pseudoRandomNumbers).toMatchInlineSnapshot(`
          [
            1007413867,
            3102276828,
            1881525607,
            2814943599,
            268167672,
            166216641,
            911106218,
            3324033710,
            3869776514,
            2635435505,
          ]
        `)
      })

      it("should generate different sequences for different seeds", ({
        expect,
      }) => {
        const generator1 = SeededRandomGenerator.fromStringSeed("test1")
        const generator2 = SeededRandomGenerator.fromStringSeed("test2")

        const pseudoRandomNumbers1 = Array.from({ length: 100 }, () =>
          generator1.nextUint32()
        )

        const pseudoRandomNumbers2 = Array.from({ length: 100 }, () =>
          generator2.nextUint32()
        )

        // All values should be unique
        expect(
          new Set([...pseudoRandomNumbers1, ...pseudoRandomNumbers2]).size
        ).toEqual(pseudoRandomNumbers1.length + pseudoRandomNumbers2.length)
      })
    })

    describe("nextDouble", (it) => {
      it("should generate numbers in the proper range", ({ expect }) => {
        const generator = SeededRandomGenerator.fromStringSeed("test-range")

        const pseudoRandomNumbers = Array.from({ length: 100 }, () =>
          generator.nextDouble()
        )

        for (const number of pseudoRandomNumbers) {
          expect(number).toBeGreaterThanOrEqual(0)
          expect(number).toBeLessThan(1)
        }
      })

      it("should generate the same sequence of doubles for the same seed", ({
        expect,
      }) => {
        const generator = SeededRandomGenerator.fromStringSeed("test")

        const pseudoRandomNumbers = Array.from({ length: 10 }, () =>
          generator.nextDouble()
        )

        expect(pseudoRandomNumbers).toMatchInlineSnapshot(`
          [
            0.7447316382456881,
            0.36264768162262917,
            0.7446213137629771,
            0.898600362717541,
            0.5064722190953683,
            0.9996748725842701,
            0.40502510073884435,
            0.5496044172156553,
            0.5119799779322056,
            0.24055129968647648,
          ]
        `)
      })
    })
  })
}

test-avalanche.ts

import assert from "node:assert"
import { randomBytes } from "node:crypto"

import { SeededRandomGenerator } from "./seeded-random"

const TOTAL_ITERATIONS = 1_000_000
const MAX_SEED_LENGTH = 10

/**
 * Find the number of bits that are different between two 32-bit integers.
 */
const hammingDistance = (a: number, b: number) => {
  let xor = (a ^ b) >>> 0

  let distance = 0
  while (xor > 0) {
    distance += xor & 1
    xor >>>= 1
  }

  return distance
}

{
  let totalHammingDistance = 0
  for (let iteration = 0; iteration < TOTAL_ITERATIONS; iteration++) {
    const seed = randomBytes(Math.random() * MAX_SEED_LENGTH + 1)

    // Mask highest bit so we get ASCII
    for (let index = 0; index < seed.length; index++) {
      seed[index] &= 0b0111_1111
    }

    // Create a second seed where a random bit is flipped
    const seed2 = new Uint8Array(seed.length)
    seed2.set(seed)
    seed2[Math.floor(Math.random() * seed.length)] ^= Math.pow(
      2,
      Math.floor(Math.random() * 7)
    )

    assert(seed.compare(seed2) !== 0, "Seeds should be different")

    // Encode these seeds as strings
    const seedString = new TextDecoder().decode(seed)
    const seedString2 = new TextDecoder().decode(seed2)

    assert(seedString !== seedString2, "Seed strings should be different")

    // Create two generators with these seeds
    const generator = new SeededRandomGenerator()
    generator.seedString(seedString)
    const generator2 = new SeededRandomGenerator()
    generator2.seedString(seedString2)

    const a = generator.nextUint32()
    const b = generator2.nextUint32()

    totalHammingDistance += hammingDistance(a, b)
  }

  const averageHammingDistancePerBit =
    totalHammingDistance / (32 * TOTAL_ITERATIONS)

  console.log(
    `Average Hamming distance per bit for generators with different seeds: ${averageHammingDistancePerBit}`
  )
}

{
  let totalHammingDistance = 0
  for (let iteration = 0; iteration < TOTAL_ITERATIONS; iteration++) {
    const seed = randomBytes(Math.random() * MAX_SEED_LENGTH + 1)

    // Mask highest bit so we get ASCII
    for (let index = 0; index < seed.length; index++) {
      seed[index] &= 0b0111_1111
    }

    const seedString = new TextDecoder().decode(seed)

    const generator = new SeededRandomGenerator()
    generator.seedString(seedString)

    const a = generator.nextUint32()
    const b = generator.nextUint32()

    totalHammingDistance += hammingDistance(a, b)
  }

  const averageHammingDistancePerBit =
    totalHammingDistance / (32 * TOTAL_ITERATIONS)

  console.log(
    `Average Hamming distance per bit for consecutive outputs: ${averageHammingDistancePerBit}`
  )
}