GearHash.js

/**
 * Gear hash table — the 256 random u32 constants used by FastCDC's rolling hash.
 *
 * The update rule is:    h = ((h << 1) + GEAR[byte]) >>> 0
 *
 * Each byte adds in a value drawn from this table; the shift makes older bytes'
 * contributions decay (and after ~32 iterations fall off entirely), so `h` behaves
 * as a rolling hash over a short suffix of the stream. This is exactly the
 * property FastCDC needs to detect chunk boundaries by content.
 *
 * The table is generated deterministically at module load by a small xorshift32
 * PRNG seeded with a fixed constant. Doing it this way avoids hand-typing 256
 * literals (which had a subtle bit-31 bias in the earlier version) and guarantees
 * that two implementations using the same seed produce identical chunk boundaries.
 *
 * @see https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia
 */

const GEAR_SEED = 0xC0FFEE12;

/** @type {Uint32Array} */
export const GEAR = (() => {
    // xorshift32 — uniformly distributed across all 32 bits, period 2^32 - 1.
    let s = GEAR_SEED >>> 0;
    const out = new Uint32Array(256);
    for (let i = 0; i < 256; i++) {
        s ^= s << 13;
        s ^= s >>> 17;
        s ^= s << 5;
        s >>>= 0;
        out[i] = s;
    }
    return out;
})();