Multiplicative scramble hash

hash.test.js

const M = 1_295_827;
const N = 36 ** 4; // 1_679_616

// Extended Euclidean algorithm to find modular inverse
function modInverse(a, m) {
  let [old_r, r] = [a, m];
  let [old_s, s] = [1, 0];
  while (r !== 0) {
    const q = Math.floor(old_r / r);
    [old_r, r] = [r, old_r - q * r];
    [old_s, s] = [s, old_s - q * s];
  }
  return ((old_s % m) + m) % m;
}

const M_INV = modInverse(M, N);

const encode = n => ((n * M) % N).toString(36).toUpperCase().padStart(4, '0');
const decode = s => (parseInt(s, 36) * M_INV) % N;

// --- Tests ---

let passed = 0;
let failed = 0;

function test(name, fn) {
  try {
    fn();
    console.log(`  ✅ ${name}`);
    passed++;
  } catch (e) {
    console.log(`  ❌ ${name}: ${e.message}`);
    failed++;
  }
}

function assert(cond, msg) {
  if (!cond) throw new Error(msg);
}

console.log("\n=== Encode/Decode Round-trip ===");

test("zero round-trips", () => assert(decode(encode(0)) === 0));
test("one round-trips",  () => assert(decode(encode(1)) === 1));
test("max value (999999) round-trips", () => assert(decode(encode(999_999)) === 999_999));

const SAMPLES = [1, 42, 100, 1337, 99999, 500000, 999999];
for (const n of SAMPLES) {
  test(`round-trip ${n}`, () => assert(decode(encode(n)) === n, `got ${decode(encode(n))}`));
}

console.log("\n=== Output Format ===");

test("always 4 chars", () => {
  for (const n of [0, 1, 100, 999_999]) {
    const s = encode(n);
    assert(s.length === 4, `encode(${n}) = "${s}" (length ${s.length})`);
  }
});

test("only base-36 characters", () => {
  const valid = /^[0-9A-Z]{4}$/;
  for (const n of [0, 1, 999_999, 42, 123456]) {
    const s = encode(n);
    assert(valid.test(s), `"${s}" contains invalid chars`);
  }
});

console.log("\n=== Collision Check (full range 0–999,999) ===");

test("no collisions across entire input range", () => {
  const seen = new Set();
  for (let n = 0; n < 1_000_000; n++) {
    const s = encode(n);
    assert(!seen.has(s), `collision at n=${n}, encoded="${s}"`);
    seen.add(s);
  }
  assert(seen.size === 1_000_000, `expected 1000000 unique ids, got ${seen.size}`);
});

console.log("\n=== Non-Sequential Check ===");

test("consecutive inputs don't produce consecutive outputs", () => {
  let seqCount = 0;
  for (let n = 0; n < 999; n++) {
    if (parseInt(encode(n + 1), 36) === parseInt(encode(n), 36) + 1) seqCount++;
  }
  // Allow a tiny number of accidental sequential hits, but not many
  assert(seqCount < 5, `too many sequential outputs: ${seqCount}/999`);
});

test("sample of encoded values looks scattered", () => {
  const vals = [0,1,2,3,4,5].map(n => parseInt(encode(n), 36));
  const diffs = vals.slice(1).map((v, i) => Math.abs(v - vals[i]));
  const allLarge = diffs.every(d => d > 1000);
  assert(allLarge, `diffs too small: ${diffs}`);
});

console.log("\n=== Summary ===");
console.log(`  ${passed} passed, ${failed} failed\n`);