Skip to content

Instantly share code, notes, and snippets.

@miyaokamarina
Last active November 30, 2023 10:39
Show Gist options
  • Save miyaokamarina/2623551288b6f5012087be0b15103b96 to your computer and use it in GitHub Desktop.
Save miyaokamarina/2623551288b6f5012087be0b15103b96 to your computer and use it in GitHub Desktop.
Random 32-bit magic number generator

Random 32-bit magic number generator

A magic number for a binary file format should satisfy the following requirements:

  • invalid in UTF-8,

    Must contain either invalid bytes or invalid sequences.

  • is not ascending,
  • has no equal bytes,
  • has no bytes that are common in binary data,

    00, 01, 80, FF

  • has no bytes that occur in UTF-16 BOM,

    FE, FF

  • has no bytes with zero half-bytes,
  • has approx. 16 set bits,
  • has no repeating hexadecimal digits,
  • also in reverse byte order,
  • and in reverse half-word order.
// @ts-check
/** Number of random magic strings to generate. */
const N = 50;
const main = () => {
/** @type {Set<string>} */
let res = new Set();
while (res.size < N) {
let n = rng();
if (check_permuted(n)) {
res.add(hex(n));
}
}
console.log([...res].join('\n'));
};
/** Check single magic string.
* @param {number} n */
// prettier-ignore
const check = n => {
let v = get_bytes(n);
let s = n.toString(16).toUpperCase().padStart(8, '0');
let [a, b, c, d] = v;
//*****************//
// Trivial checks: //
//*****************//
// Approx. 16 set bits:
n = (n & 0x55555555) + ((n >>> 0x01) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 0x02) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 0x04) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 0x08) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 0x10) & 0x0000ffff);
if (n < 13 || n > 19) return false;
// 00, 01, 80, FF -- common in binary data
// FE -- covers UTF-16 BOM
if (v.some(x => x === 0xff || x === 0xfe || x === 0x80 || x === 0x01 || x === 0x00)) return false;
// Zero half-byte:
if (v.some(x => (x & 0x0f) === 0 || (x & 0xf0) === 0)) return false;
// Ascending sequence:
if (a <= b && b <= c && c <= d) return false;
// Equal bytes:
if (a === b || a === c || a === d || b === c || b === d || c === d) return false;
// Repeating digits:
if (/(.)\1/.test(s)) return false;
//***********************//
// Invalid UTF-8 checks: //
//***********************//
// Out-of-range byte:
if (v.some(x => x >= 248 && x <= 255)) return true;
// Invalid 2-byte sequence head:
if (v.some(x => x >= 192 && x <= 193)) return true;
// Incomplete 2-byte sequence:
if (is_u8h2(a) && !is_u8cb(b)) return true;
if (is_u8h2(b) && !is_u8cb(c)) return true;
if (is_u8h2(c) && !is_u8cb(d)) return true;
// Incomplete 3-byte sequence:
if (is_u8h3(a) && (!is_u8cb(b) || !is_u8cb(c))) return true;
if (is_u8h3(b) && (!is_u8cb(c) || !is_u8cb(d))) return true;
if (is_u8h3(c) && (!is_u8cb(d))) return true;
// Incomplete 4-byte sequence:
if (is_u8h4(a) && (!is_u8cb(b) || !is_u8cb(c) || !is_u8cb(d))) return true;
if (is_u8h4(b) && (!is_u8cb(c) || !is_u8cb(d))) return true;
if (is_u8h4(c) && (!is_u8cb(d))) return true;
// No invalid UTF-8 patterns detected:
return false;
};
/** Check magic string in either byte order.
* @param {number} n */
const check_permuted = n => {
return check(n) && check(half_swap(n)) && check(byte_swap(n));
};
/** @param {number} n */ const hex = n => n.toString(16).toUpperCase().padStart(8, '0');
/** @param {number} n */ const byte_swap = n => half_swap(((n << 8) & 0xff00ff00) | ((n >>> 8) & 0x00ff00ff));
/** @param {number} n */ const half_swap = n => ((n << 16) | (n >>> 16)) >>> 0;
/** @param {number} n */ const get_bytes = n => [n >>> 24, n >>> 16, n >>> 8, n >>> 0].map(x => x & 0xff);
// UTF-8 byte class checks:
/** @param {number} x */ const is_u8h2 = x => x >= 194 && x <= 223;
/** @param {number} x */ const is_u8h3 = x => x >= 224 && x <= 239;
/** @param {number} x */ const is_u8h4 = x => x >= 240 && x <= 247;
/** @param {number} x */ const is_u8cb = x => x >> 6 === 2;
/** Buffered Crypto RNG wrapper. */ const RNG = () => {
let l = 16384;
let i = l;
let b = new Uint32Array(l);
return () => {
if (i >= l) {
crypto.getRandomValues(b);
i = 0;
}
return b[i++];
};
};
const rng = RNG();
main();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment