fnvHash.js

/**
 * Takes a string and returns a 24 byte base64url encoded hash of the string. Uses the FNV-1a hash function.
 * @param str
 * @returns {string}
 */
export function fnvBase64UrlHash(str) {
    return bigIntToBase64Url(fnvHash96(str));
}

/**
 * Takes a string and hashes it using a 128 bit FNV-1a hash. The hash is shortened to 96 bits using xor folding.
 * See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
 * @param str
 * @returns {bigint}
 */
export function fnvHash96(str) {
    const hash = fnvHash128(str);
    const lower = hash & 0xFFFFFFFFFFFFFFFFFFFFFFFFn;
    const higher = (hash & 0xFFFFFFFF000000000000000000000000n) >> 96n;
    return lower ^ higher;
}


/**
 * Takes a string and hashes it using a 128 bit FNV-1a hash
 * See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
 * @param str
 * @returns {bigint}
 */
export function fnvHash128(str) {
    let fnvPrime = 0x0000000001000000000000000000013Bn;
    let hash = 0x6c62272e07bb014262b821756295c58dn;
    const encoder = new TextEncoder();
    const bytes = encoder.encode(str);

    for (let i = 0; i < bytes.length; ) {
        hash ^= BigInt(bytes[i++]);
        hash = BigInt.asUintN(128, hash * fnvPrime);
    }
    return hash;
}


/**
 * Takes a BigInt and returns a base64url encoded string of the first 96 bits of the BigInt
 * @param bigInt
 * @returns {string}
 */
// Lookup table for converting a 6 bit number to a base64Url character as a UInt8Array
const base64UrlLookup = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
export function bigIntToBase64Url(bigInt) {
    let output = "";
    // iterate over the first 96 bits of the BigInt, 6 bits at a time
    for (let i = 15n; i >= 0n; i--) {
        const sixBits = BigInt.asUintN(6,bigInt >> (6n * i));
        output += base64UrlLookup[sixBits];
    }
    return output;
}