Random 32-bit magic number generator

README.md

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.

magic32.mjs

// @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();