mayan.ts

1/**2 * Mayan v2 — Peach's proprietary vault backup matrix code.3 *4 * Format: a square dark/light module grid with three 7×7 corner anchor5 * squares (TL, TR, BL — BR absent for orientation), a 16-bit symbol-size6 * marker adjacent to the TL anchor, two L-shaped timing strips along the7 * top and left active edges, and the Othalan rune ᛟ at the dead center.8 * Vault data radiates outward in a row-by-row grid skipping all reserved9 * positions.10 *11 * Pipeline (caller responsibility): plaintext → zstd compress → AES-256-GCM12 * encrypt → encodeMayan(). Compress-before-encrypt is non-negotiable; the13 * Peach payload format already does this internally so callers passing14 * `buildPayload()` output here are compliant.15 *16 * Header: 6 bytes — magic 0x4D, version 0x02, payload length u32 LE.17 *18 * Reed-Solomon: RS(255,204) — 204 data bytes + 51 parity per block, 20%19 * overhead. Blocks are interleaved (byte j of block i → position20 * i + j*numBlocks) so a localized burst of damage spreads across blocks21 * instead of crushing one.22 *23 * The rune is the soul of the format. The anchors are scaffolding that24 * makes machine decoding reliable — the decoder uses them for homography,25 * not the rune. See peach_mayan_v2_spec.md for the full rationale.26 */2728import { rsEncodeBlock } from "./rs";2930export const MAYAN_MAGIC = 0x4d;31export const MAYAN_V2 = 0x02;32export const RUNE_ZONE = 27;33export const QUIET_ZONE = 2;34export const ANCHOR_SIZE = 7;35export const ANCHOR_FOOTPRINT = 9; // 7×7 anchor + 1-module light ring on every side36export const RS_DATA = 204;37export const RS_PARITY = 51;38export const RS_BLOCK = RS_DATA + RS_PARITY; // 25539export const HEADER_BYTES = 6;40export const MAX_SYMBOL_SIZE = 1024;41export const MIN_SYMBOL_SIZE = 64;42// Comfortable cap below the 1024-module ceiling. A 1024×1024 symbol holds43// ~130 KB of raw data bits; after 20% RS overhead + header that leaves44// ~100 KB of payload room with margin to spare.45export const MAX_PAYLOAD_BYTES = 100000;4647export interface MayanResult {48  canvas: HTMLCanvasElement;49  symbolSize: number;50  payloadBytes: number;51  printable: boolean;52  paperSize: "A4" | "A3" | "A3-required";53}5455// ── SIZE CALCULATION ─────────────────────────────────────────────────────────5657export function calculateSymbolSize(payloadBytes: number): number {58  const totalData = payloadBytes + HEADER_BYTES;59  const numBlocks = Math.max(1, Math.ceil(totalData / RS_DATA));60  const dataBits = numBlocks * RS_BLOCK * 8;6162  for (let size = MIN_SYMBOL_SIZE; size <= MAX_SYMBOL_SIZE; size++) {63    if (usableModules(size) >= dataBits) return size;64  }65  return MAX_SYMBOL_SIZE;66}6768/** Module budget for data placement at a given symbol size. Subtracts every69 *  reserved region exactly once. */70export function usableModules(size: number): number {71  let reserved = 0;72  // Quiet zone: outer 2-module border73  reserved += quietModuleCount(size);74  // Three anchors (9×9 footprint each)75  reserved += 3 * ANCHOR_FOOTPRINT * ANCHOR_FOOTPRINT;76  // Size bits row (16 modules adjacent to TL anchor, on row=QUIET_ZONE)77  reserved += 16;78  // Timing strips (top + left), excluding overlap with rune zone79  reserved += timingModuleCount(size);80  // Rune zone (27×27 centered). Subtract any overlap already counted in81  // timing strips so we don't double-count the rune-zone-vs-timing crossing.82  reserved += runeModuleCount(size) - runeTimingOverlap(size);83  return size * size - reserved;84}8586function quietModuleCount(size: number): number {87  // Four QUIET_ZONE-thick strips minus the corner overlaps88  return 4 * size * QUIET_ZONE - 4 * QUIET_ZONE * QUIET_ZONE;89}9091function timingModuleCount(size: number): number {92  // Top strip: row q+ANCHOR_FOOTPRINT, cols [q+ANCHOR_FOOTPRINT, size-q-ANCHOR_FOOTPRINT)93  // Left strip: col q+ANCHOR_FOOTPRINT, rows [q+ANCHOR_FOOTPRINT, size-q-ANCHOR_FOOTPRINT)94  // Strips don't overlap (one starts at the position the other occupies one off).95  const span = size - 2 * (QUIET_ZONE + ANCHOR_FOOTPRINT);96  return Math.max(0, 2 * span);97}9899function runeModuleCount(_size: number): number {100  return RUNE_ZONE * RUNE_ZONE;101}102103function runeTimingOverlap(size: number): number {104  // The top timing row crosses the rune zone in 27 modules iff the row index105  // q+ANCHOR_FOOTPRINT falls within the rune row range. Same for the left106  // timing column. Compute exactly.107  const center = Math.floor(size / 2);108  const half = Math.floor(RUNE_ZONE / 2);109  const tRow = QUIET_ZONE + ANCHOR_FOOTPRINT;110  const tCol = QUIET_ZONE + ANCHOR_FOOTPRINT;111  const rowOverlaps = tRow >= center - half && tRow <= center + half;112  const colOverlaps = tCol >= center - half && tCol <= center + half;113  return (rowOverlaps ? RUNE_ZONE : 0) + (colOverlaps ? RUNE_ZONE : 0);114}115116// ── ANCHOR / TIMING / SIZE BIT PLACEMENT ─────────────────────────────────────117118function drawAnchor(matrix: boolean[][], r0: number, c0: number): void {119  // Clear 9×9 light ring120  for (let dr = 0; dr < ANCHOR_FOOTPRINT; dr++) {121    for (let dc = 0; dc < ANCHOR_FOOTPRINT; dc++) {122      matrix[r0 + dr][c0 + dc] = false;123    }124  }125  // 7×7 anchor pattern at +1, +1 inside the light ring.126  // Outer ring dark, gap light, 3×3 dark center.127  const PAT = [128    [1, 1, 1, 1, 1, 1, 1],129    [1, 0, 0, 0, 0, 0, 1],130    [1, 0, 1, 1, 1, 0, 1],131    [1, 0, 1, 1, 1, 0, 1],132    [1, 0, 1, 1, 1, 0, 1],133    [1, 0, 0, 0, 0, 0, 1],134    [1, 1, 1, 1, 1, 1, 1],135  ];136  for (let dr = 0; dr < ANCHOR_SIZE; dr++) {137    for (let dc = 0; dc < ANCHOR_SIZE; dc++) {138      matrix[r0 + 1 + dr][c0 + 1 + dc] = PAT[dr][dc] === 1;139    }140  }141}142143function placeAnchors(matrix: boolean[][], size: number): void {144  const q = QUIET_ZONE;145  drawAnchor(matrix, q, q);146  drawAnchor(matrix, q, size - q - ANCHOR_FOOTPRINT);147  drawAnchor(matrix, size - q - ANCHOR_FOOTPRINT, q);148  // Bottom-right intentionally absent — orientation marker.149}150151function writeSizeBits(matrix: boolean[][], size: number): void {152  // 16 bits, MSB first, on row=QUIET_ZONE, starting one column to the right153  // of the TL anchor footprint. Lives inside the quiet-zone-adjacent strip154  // but outside the anchor light ring.155  const row = QUIET_ZONE;156  const colStart = QUIET_ZONE + ANCHOR_FOOTPRINT + 1;157  for (let i = 0; i < 16; i++) {158    matrix[row][colStart + i] = ((size >> (15 - i)) & 1) === 1;159  }160}161162function sizeBitColumns(): { row: number; colStart: number; colEnd: number } {163  const row = QUIET_ZONE;164  const colStart = QUIET_ZONE + ANCHOR_FOOTPRINT + 1;165  return { row, colStart, colEnd: colStart + 16 };166}167168function placeTimingStrips(matrix: boolean[][], size: number): void {169  const q = QUIET_ZONE;170  const start = q + ANCHOR_FOOTPRINT;171  const end = size - q - ANCHOR_FOOTPRINT;172  // Top timing strip — alternating dark/light starting dark on even module173  for (let c = start; c < end; c++) {174    matrix[start][c] = (c & 1) === 0;175  }176  // Left timing strip177  for (let r = start; r < end; r++) {178    matrix[r][start] = (r & 1) === 0;179  }180}181182// ── RUNE DRAWING (unchanged from v1) ─────────────────────────────────────────183184function fillRect(185  matrix: boolean[][],186  r: number,187  c: number,188  h: number,189  w: number,190): void {191  for (let dr = 0; dr < h; dr++) {192    for (let dc = 0; dc < w; dc++) {193      const mr = r + dr;194      const mc = c + dc;195      if (mr >= 0 && mr < matrix.length && mc >= 0 && mc < matrix[0].length) {196        matrix[mr][mc] = true;197      }198    }199  }200}201202function drawDiag(203  matrix: boolean[][],204  r0: number,205  c0: number,206  r1: number,207  c1: number,208  r2: number,209  c2: number,210  stroke: number,211): void {212  const steps = Math.max(Math.abs(r2 - r1), Math.abs(c2 - c1));213  const half = Math.floor(stroke / 2);214  for (let i = 0; i <= steps; i++) {215    const r = Math.round(r1 + ((r2 - r1) * i) / steps);216    const c = Math.round(c1 + ((c2 - c1) * i) / steps);217    fillRect(matrix, r0 + r - half, c0 + c - half, stroke, stroke);218  }219}220221function drawOthalan(222  matrix: boolean[][],223  centerRow: number,224  centerCol: number,225): void {226  const r0 = centerRow - 11;227  const c0 = centerCol - 11;228  const STROKE = 3;229  const TOP   = [1, 11];230  const RIGHT = [10, 21];231  const BOT   = [19, 11];232  const LEFT  = [10, 1];233  drawDiag(matrix, r0, c0, TOP[0], TOP[1], RIGHT[0], RIGHT[1], STROKE);234  drawDiag(matrix, r0, c0, RIGHT[0], RIGHT[1], BOT[0], BOT[1], STROKE);235  drawDiag(matrix, r0, c0, BOT[0], BOT[1], LEFT[0], LEFT[1], STROKE);236  drawDiag(matrix, r0, c0, LEFT[0], LEFT[1], TOP[0], TOP[1], STROKE);237  drawDiag(matrix, r0, c0, 19, 8, 22, 4, STROKE);238  drawDiag(matrix, r0, c0, 19, 14, 22, 18, STROKE);239  // Orientation marker: 3×3 dark block at top-right of rune zone240  fillRect(matrix, r0 + 0, c0 + 20, STROKE, STROKE);241}242243// ── RESERVED-POSITION TEST ───────────────────────────────────────────────────244245export function isReserved(r: number, c: number, size: number): boolean {246  const q = QUIET_ZONE;247  // Quiet zone248  if (r < q || r >= size - q || c < q || c >= size - q) return true;249250  // Corner anchors (9×9 footprint)251  const aEnd = q + ANCHOR_FOOTPRINT;252  if (r < aEnd && c < aEnd) return true;253  if (r < aEnd && c >= size - aEnd) return true;254  if (r >= size - aEnd && c < aEnd) return true;255256  // Size bits (row=q, cols colStart..colEnd-1)257  const sb = sizeBitColumns();258  if (r === sb.row && c >= sb.colStart && c < sb.colEnd) return true;259260  // Timing strips261  const tStart = aEnd;262  const tEnd = size - aEnd;263  if (r === tStart && c >= tStart && c < tEnd) return true;264  if (c === tStart && r >= tStart && r < tEnd) return true;265266  // Rune zone (27×27 centered)267  const center = Math.floor(size / 2);268  const half = Math.floor(RUNE_ZONE / 2);269  if (r >= center - half && r <= center + half &&270      c >= center - half && c <= center + half) return true;271272  return false;273}274275// ── ENCODE PIPELINE ──────────────────────────────────────────────────────────276277function buildHeaderAndPayload(encryptedPayload: Uint8Array): Uint8Array {278  const header = new Uint8Array(HEADER_BYTES);279  header[0] = MAYAN_MAGIC;280  header[1] = MAYAN_V2;281  const len = encryptedPayload.length;282  header[2] = len & 0xff;283  header[3] = (len >> 8) & 0xff;284  header[4] = (len >> 16) & 0xff;285  header[5] = (len >> 24) & 0xff;286  const out = new Uint8Array(HEADER_BYTES + encryptedPayload.length);287  out.set(header);288  out.set(encryptedPayload, HEADER_BYTES);289  return out;290}291292/** Reed-Solomon encode + interleave. Splits `data` into RS_DATA-byte blocks293 *  (zero-padded last block), encodes each to 255 bytes, then interleaves so294 *  byte j of block i lands at position i + j*numBlocks. */295function rsEncodeAndInterleave(data: Uint8Array): { interleaved: Uint8Array; numBlocks: number } {296  const numBlocks = Math.ceil(data.length / RS_DATA);297  const blocks: Uint8Array[] = [];298  for (let i = 0; i < numBlocks; i++) {299    const slice = data.subarray(i * RS_DATA, (i + 1) * RS_DATA);300    const padded = slice.length === RS_DATA301      ? slice302      : (() => { const p = new Uint8Array(RS_DATA); p.set(slice); return p; })();303    blocks.push(rsEncodeBlock(padded, RS_PARITY));304  }305  const interleaved = new Uint8Array(numBlocks * RS_BLOCK);306  for (let i = 0; i < numBlocks; i++) {307    for (let j = 0; j < RS_BLOCK; j++) {308      interleaved[i + j * numBlocks] = blocks[i][j];309    }310  }311  return { interleaved, numBlocks };312}313314/** Build the 2-D module matrix without rendering to canvas. Used by315 *  round-trip tests to skip the binarization step. */316export function encodeMayanMatrix(317  encryptedPayload: Uint8Array,318): { matrix: boolean[][]; size: number } {319  if (encryptedPayload.length > MAX_PAYLOAD_BYTES) {320    throw new Error(321      `Mayan payload too large: ${encryptedPayload.length} bytes (max ${MAX_PAYLOAD_BYTES})`,322    );323  }324  const size = calculateSymbolSize(encryptedPayload.length);325  if (size > MAX_SYMBOL_SIZE) {326    throw new Error(`Mayan: symbol size ${size} exceeds max ${MAX_SYMBOL_SIZE}`);327  }328  const center = Math.floor(size / 2);329  const fullData = buildHeaderAndPayload(encryptedPayload);330  const { interleaved } = rsEncodeAndInterleave(fullData);331332  // Bits, MSB-first per byte333  const bits: boolean[] = new Array(interleaved.length * 8);334  for (let bi = 0; bi < interleaved.length; bi++) {335    const byte = interleaved[bi];336    for (let i = 0; i < 8; i++) {337      bits[bi * 8 + i] = ((byte >> (7 - i)) & 1) === 1;338    }339  }340341  // Build matrix342  const matrix: boolean[][] = Array.from(343    { length: size },344    () => new Array<boolean>(size).fill(false),345  );346347  // Structural elements first; rune drawn last so its pixels win the348  // crossing region with the timing strips.349  placeAnchors(matrix, size);350  writeSizeBits(matrix, size);351  placeTimingStrips(matrix, size);352  drawOthalan(matrix, center, center);353354  // Place data bits in row-major scan, skipping reserved positions355  let bitIdx = 0;356  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bitIdx < bits.length; r++) {357    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bitIdx < bits.length; c++) {358      if (isReserved(r, c, size)) continue;359      matrix[r][c] = bits[bitIdx++];360    }361  }362363  return { matrix, size };364}365366export function encodeMayan(367  encryptedPayload: Uint8Array,368  modulePx = 3,369): MayanResult {370  const { matrix, size } = encodeMayanMatrix(encryptedPayload);371  const canvas = renderMatrix(matrix, size, modulePx);372  const paperSize: MayanResult["paperSize"] =373    size <= 350 ? "A4" :374    size <= 500 ? "A3" :375    "A3-required";376  return {377    canvas,378    symbolSize: size,379    payloadBytes: encryptedPayload.length,380    printable: paperSize === "A4",381    paperSize,382  };383}384385function renderMatrix(386  matrix: boolean[][],387  size: number,388  modulePx: number,389): HTMLCanvasElement {390  const canvas = document.createElement("canvas");391  canvas.width = size * modulePx;392  canvas.height = size * modulePx;393  const ctx = canvas.getContext("2d");394  if (!ctx) throw new Error("Mayan: 2D canvas unavailable");395  ctx.fillStyle = "#ffffff";396  ctx.fillRect(0, 0, canvas.width, canvas.height);397  ctx.fillStyle = "#000000";398  for (let r = 0; r < size; r++) {399    for (let c = 0; c < size; c++) {400      if (matrix[r][c]) {401        ctx.fillRect(c * modulePx, r * modulePx, modulePx, modulePx);402      }403    }404  }405  return canvas;406}407408// ── DECODE RE-EXPORTS ────────────────────────────────────────────────────────409// The decoder lives in mayan_decode.ts so the encoder can be imported without410// pulling in the homography / image-processing code. Callers that want the411// historical `import { decodeMayan } from "./mayan"` ergonomics get it here.412413export { decodeMayan, decodeMatrix } from "./mayan_decode";