Something went wrong. Try again.
Something went wrong. Try again.
5.2 kB · 128 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129// Sigil: bytes of a known length written as a sigil, one word of letters and// digits that a double-click selects whole, with no two characters alike, and// a check that confirms a reading or picks the right one of several.// The specification is README.md ("The encoding"); python/sigilcode.py is the// reference implementation, and vectors.json the tests every implementation// passes. The data is written in order, unjumbled; README.md's "Why Sigil// writes the data in order" says why.
import { ALPHABET, IGNORED, UPPERCASE } from "./alphabet.js";
const CHARS: string[] = Array.from(ALPHABET);export const N = CHARS.length;if (N !== 1353) throw new Error("the alphabet must have 1,353 characters");const DIGIT = new Map<string, number>([ ...Array.from(UPPERCASE).map((c, d): [string, number] => [c, d]), ...CHARS.map((c, d): [string, number] => [c, d]),]);const BN = BigInt(N);
/** A sigil that encodes no data of the length asked for: `kind` is * "length" (the wrong number of characters), "character" (one outside the * alphabet), "range" (a value too large for the length), or "check" (the check * fails: a character was misread or changed). */export class DecodeError extends Error { constructor(public kind: "length" | "character" | "range" | "check", message: string) { super(message); }}
function isPrime(k: number): boolean { if (k < 2) return false; for (let p = 2; p * p <= k; p++) if (k % p === 0) return false; return true;}
/** The smallest prime larger than N: K must exceed N (README.md, "Why the * check catches what it does"). */let LEAST_K = N + 1;while (!isPrime(LEAST_K)) LEAST_K++;
/** [n, K] for data of `length` bytes (at least 1): the sigil's characters, * the fewest whose room R = floor(N^n / 2^(8 * length)) holds a prime larger * than N, and K, the largest prime at most R. */export function layout(length: number): [number, number] { if (!(Number.isInteger(length) && length >= 1)) throw new RangeError("Sigil encodes at least one byte"); const bits = BigInt(8 * length); let n = 1; while (BN ** BigInt(n) >> bits < BigInt(LEAST_K)) n++; let k = Number(BN ** BigInt(n) >> bits); while (!isPrime(k)) k--; return [n, k];}
const toBig = (b: Uint8Array) => b.reduce((v, byte) => (v << 8n) | BigInt(byte), 0n);
/** `data`'s sigil, layout(data.length)[0] characters of the alphabet. * Its protection against look-alikes holds for data that looks random (a * secure hash's output, a key, a random identifier): hash or jumble structured data * before encoding it (README.md, "Data with structure: hash it, or jumble it"). */export function encode(data: Uint8Array): string { const [n, k] = layout(data.length); let w = toBig(data) * BigInt(k); const out: string[] = new Array(n); for (let i = n - 1; i >= 0; i--) { out[i] = CHARS[Number(w % BN)]; w /= BN; } return out.join("");}
/** White space and the default-ignorable characters, which decoding skips. */function ignored(ch: string): boolean { const p = ch.codePointAt(0)!; return IGNORED.some(([a, b]) => a <= p && p <= b);}
export function decode(sigil: string, length: number): Uint8Array { const [n, k] = layout(length); const chars = Array.from(sigil) .map((ch, i): [string, number] => [ch, i]) .filter(([ch]) => !ignored(ch)); if (chars.length !== n) throw new DecodeError("length", `${chars.length} characters; ${length} bytes take ${n}`); let w = 0n; for (const [ch, i] of chars) { const d = DIGIT.get(ch); if (d === undefined) throw new DecodeError("character", `character ${i + 1} (U+${ch.codePointAt(0)!.toString(16).toUpperCase().padStart(4, "0")}) is not in the alphabet`); w = w * BN + BigInt(d); } const K = BigInt(k); if (w >= K << BigInt(8 * length)) throw new DecodeError("range", `its value is too large for ${length} bytes: a character was misread or changed`); if (w % K !== 0n) throw new DecodeError("check", "the check fails: a character was misread or changed"); let v = w / K; const data = new Uint8Array(length); for (let i = length - 1; i >= 0; i--) { data[i] = Number(v & 0xffn); v >>= 8n; } return data;}
/** Every data of `length` bytes that some reading decodes to, for a reader * unsure of some characters (an OCR tool, say): `readings` gives each * character's possible readings, one string a character, the likeliest first. * One result is the answer; more mean the readings leave the sigil ambiguous. */export function decodeReadings(readings: string[], length: number): Uint8Array[] { const options = readings.map((r) => Array.from(r)); const found: Uint8Array[] = []; const seen = new Set<string>(); const walk = (i: number, chosen: string) => { if (i === options.length) { try { const data = decode(chosen, length); const key = Array.from(data).join(","); if (!seen.has(key)) { seen.add(key); found.push(data); } } catch (e) { if (!(e instanceof DecodeError)) throw e; } return; } for (const ch of options[i]) walk(i + 1, chosen + ch); }; walk(0, ""); return found;}