Skip to content

Instantly share code, notes, and snippets.

@miyaokamarina
Created July 11, 2023 21:11
Show Gist options
  • Save miyaokamarina/9cca54900d5b14d3b7c61a8fcfb4db26 to your computer and use it in GitHub Desktop.
Save miyaokamarina/9cca54900d5b14d3b7c61a8fcfb4db26 to your computer and use it in GitHub Desktop.
Illustrative examples of hash functions and their inverses for 4, 8, and 16-bit inputs.
// @ts-check
// SPDX-License-Identifier: CC0-1.0
/**
* 4-bit hash.
*
* Single LCG step + xorshift.
*
* @param {number} x
*/
export const toyhash4 = x => {
x *= 0x5;
x &= 0xF;
x ^= x >> 2;
return x;
};
/**
* 8-bit hash.
*
* Single MCG step + xorshift.
*
* @param {number} x
*/
export const toyhash8 = x => {
x *= 0x69;
x &= 0xFF;
x ^= x >> 4;
return x;
};
/**
* MurmurHash3-like 16-bit hash function.
*
* @param {number} x
*/
export const toyhash16 = x => {
x ^= x >> 8;
x *= 0x4DC5;
x &= 0xFFFF;
x ^= x >> 8;
x *= 0x7435;
x &= 0xFFFF;
x ^= x >> 8;
return x;
};
/**
* Inverse of the 4-bit hash.
*
* @param {number} x
*/
export const untoyhash4 = x => {
x ^= x >> 2;
x *= 0xD;
x &= 0xF;
return x;
};
/**
* Inverse of the 8-bit hash.
*
* @param {number} x
*/
export const untoyhash8 = x => {
x ^= x >> 4;
x *= 0xD9;
x &= 0xFF;
return x;
}
/**
* Inverse of the 16-bit hash.
*
* @param {number} x
*/
export const untoyhash16 = x => {
x ^= x >> 8;
x *= 0x3E1D;
x &= 0xFFFF;
x ^= x >> 8;
x *= 0xA90D;
x &= 0xFFFF;
x ^= x >> 8;
return x;
};
// @ts-check
// Avalanche test:
/**
* 16-bit `popcnt`
*
* @param {number} x
*/
const popcnt16 = x => {
x = (x & 0x5555) + (x >> 1 & 0x5555);
x = (x & 0x3333) + (x >> 2 & 0x3333);
x = (x & 0x0f0f) + (x >> 4 & 0x0f0f);
x = (x & 0x00ff) + (x >> 8 & 0x00ff);
return x;
};
/**
* Average output bit flip chance, when inputs differ in one bit.
*
* @param {(x: number) => number} f
* @param {number} len
*/
const flip_chance = (f, len) => {
let end = 1 << len;
let sum = 0;
for (let s0 = 0; s0 < end; s0++) {
for (let bit = 1; bit < end; bit <<= 1) {
let t0 = s0 ^ bit;
let s1 = f(s0);
let t1 = f(t0);
sum += popcnt16(s1 ^ t1);
}
}
return sum / (end * len * len);
};
if (flip_chance(toyhash4, 4) !== 0.5) {
throw new Error('toyhash4 avalanche test failed');
}
console.log('toyhash4 avalanche test: OK');
if (flip_chance(toyhash8, 8) !== 0.5) {
throw new Error('toyhash8 avalanche test failed');
}
console.log('toyhash8 avalanche test: OK');
if (flip_chance(toyhash8, 8) !== 0.5) {
throw new Error('toyhash8 avalanche test failed');
}
console.log('toyhash16 avalanche test: OK');
// Inverse functions test:
for (let x = 0; x <= 0xF; x++) {
let y = toyhash4(x);
let z = untoyhash4(y);
if (z !== x) {
throw new Error(`toyhash4 inverse test failed: ${z} ≠ ${x}`);
}
}
console.log('toyhash4 inverse test: OK');
for (let x = 0; x <= 0xFF; x++) {
let y = toyhash8(x);
let z = untoyhash8(y);
if (z !== x) {
throw new Error(`toyhash8 inverse test failed: ${z} ≠ ${x}`);
}
}
console.log('toyhash8 inverse test: OK');
for (let x = 0; x <= 0xFFFF; x++) {
let y = toyhash16(x);
let z = untoyhash16(y);
if (z !== x) {
throw new Error(`toyhash16 inverse test failed: ${z} ≠ ${x}`);
}
}
console.log('toyhash16 inverse test: OK');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment