mayan.ts

1/**2 * Mayan — Peach's proprietary vault backup matrix code.3 *4 * Format: a square dark/light module grid with the Othalan rune ᛟ as the5 * finder pattern at center. Vault data radiates outward in a row-by-row6 * grid skipping the reserved center zone and reference grid positions.7 *8 * Per peach_mayan_spec.md:9 *   - Magic byte 0x4D ('M'), version 0x01, payload length u16 LE10 *   - 30% Reed-Solomon ECC (block-based RS(255,178), see ./rs.ts)11 *   - 23×23 rune + 2-module padding = 27×27 reserved center12 *   - 2-module quiet zone border13 *   - Reference grid every 32 modules for symbols >128 modules14 *15 * Spec §11 reserves the rune as non-negotiable: every Mayan code has the16 * Othalan ᛟ at its center. Do not replace with QR/Aztec/etc.17 */1819import {20  reedSolomonEncode,21  reedSolomonDecode,22  RS_BLOCK_DATA,23  RS_BLOCK_TOTAL,24} from "./rs";2526export const MAYAN_MAGIC = 0x4d;27export const MAYAN_VERSION = 0x01;28export const RUNE_ZONE = 27;     // reserved center: 23×23 rune + 2-module padding each side29export const QUIET_ZONE = 2;30export const ECC_RATE = 0.30;31export const MAX_PAYLOAD_BYTES = 65535;3233export interface MayanResult {34  canvas: HTMLCanvasElement;35  symbolSize: number;36  payloadBytes: number;37  printable: boolean;38}3940// ── SIZE CALCULATION ─────────────────────────────────────────────────────────4142export function calculateSymbolSize(payloadBytes: number): number {43  const headerBytes = 4;44  const totalData = payloadBytes + headerBytes;45  // Use the actual RS-encoded byte count (block-padded) instead of the46  // theoretical ECC_RATE estimate. The RS codec rounds up to whole 178-byte47  // data blocks and emits 255 bytes per block, so smaller payloads have48  // higher effective overhead than the 30% nominal rate.49  const blocks = Math.max(1, Math.ceil(totalData / RS_BLOCK_DATA));50  const dataBits = blocks * RS_BLOCK_TOTAL * 8;5152  for (let size = 64; size <= 600; size++) {53    const totalModules = size * size;54    const centerModules = RUNE_ZONE * RUNE_ZONE;55    const quietModules = 4 * size * QUIET_ZONE - 4 * QUIET_ZONE * QUIET_ZONE;56    const refGridModules = size > 12857      ? approxReferenceGridCount(size)58      : 0;59    const usable = totalModules - centerModules - quietModules - refGridModules;60    if (usable >= dataBits) return size;61  }62  return 600;63}6465function approxReferenceGridCount(size: number): number {66  // Reference grid lines at every 32nd row and column (excluding quiet zone).67  // Conservative overestimate: full lines, ignoring intersections with center.68  const lines = Math.floor((size - 2 * QUIET_ZONE) / 32);69  const linePos = lines * (size - 2 * QUIET_ZONE);70  return linePos * 2;71}7273// ── RUNE DRAWING ─────────────────────────────────────────────────────────────7475function fillRect(76  matrix: boolean[][],77  r: number,78  c: number,79  h: number,80  w: number,81): void {82  for (let dr = 0; dr < h; dr++) {83    for (let dc = 0; dc < w; dc++) {84      const mr = r + dr;85      const mc = c + dc;86      if (mr >= 0 && mr < matrix.length && mc >= 0 && mc < matrix[0].length) {87        matrix[mr][mc] = true;88      }89    }90  }91}9293function drawDiag(94  matrix: boolean[][],95  r0: number,96  c0: number,97  r1: number,98  c1: number,99  r2: number,100  c2: number,101  stroke: number,102): void {103  // Stroke diagonal from (r1,c1) to (r2,c2), origin at (r0,c0), as a stair104  // of stroke×stroke blocks. The half-offset centers the stroke on the line.105  const steps = Math.max(Math.abs(r2 - r1), Math.abs(c2 - c1));106  const half = Math.floor(stroke / 2);107  for (let i = 0; i <= steps; i++) {108    const r = Math.round(r1 + ((r2 - r1) * i) / steps);109    const c = Math.round(c1 + ((c2 - c1) * i) / steps);110    fillRect(matrix, r0 + r - half, c0 + c - half, stroke, stroke);111  }112}113114function drawOthalan(115  matrix: boolean[][],116  centerRow: number,117  centerCol: number,118): void {119  // 23×23 region centered on (centerRow, centerCol). Origin = top-left.120  const r0 = centerRow - 11;121  const c0 = centerCol - 11;122  const STROKE = 3;123124  // Diamond corners (within the 23×23 region)125  const TOP   = [1, 11];126  const RIGHT = [10, 21];127  const BOT   = [19, 11];128  const LEFT  = [10, 1];129130  drawDiag(matrix, r0, c0, TOP[0], TOP[1], RIGHT[0], RIGHT[1], STROKE);131  drawDiag(matrix, r0, c0, RIGHT[0], RIGHT[1], BOT[0], BOT[1], STROKE);132  drawDiag(matrix, r0, c0, BOT[0], BOT[1], LEFT[0], LEFT[1], STROKE);133  drawDiag(matrix, r0, c0, LEFT[0], LEFT[1], TOP[0], TOP[1], STROKE);134135  // Two legs descending from below the diamond136  drawDiag(matrix, r0, c0, 19, 8, 22, 4, STROKE);137  drawDiag(matrix, r0, c0, 19, 14, 22, 18, STROKE);138139  // Orientation marker: 3×3 dark block at top-right of rune zone140  fillRect(matrix, r0 + 0, c0 + 20, STROKE, STROKE);141}142143// ── RESERVED-POSITION TEST ───────────────────────────────────────────────────144145export function isReserved(146  r: number,147  c: number,148  center: number,149  size: number,150): boolean {151  if (r < QUIET_ZONE || r >= size - QUIET_ZONE) return true;152  if (c < QUIET_ZONE || c >= size - QUIET_ZONE) return true;153  // 27×27 center zone154  const half = Math.floor(RUNE_ZONE / 2);155  if (156    r >= center - half &&157    r <= center + half &&158    c >= center - half &&159    c <= center + half160  ) return true;161  // Reference grid162  if (size > 128) {163    if (164      r >= QUIET_ZONE && r < size - QUIET_ZONE && (r - QUIET_ZONE) % 32 === 0 &&165      r !== QUIET_ZONE166    ) return true;167    if (168      c >= QUIET_ZONE && c < size - QUIET_ZONE && (c - QUIET_ZONE) % 32 === 0 &&169      c !== QUIET_ZONE170    ) return true;171  }172  return false;173}174175// ── MATRIX BUILD ─────────────────────────────────────────────────────────────176177export function encodeMayan(178  encryptedPayload: Uint8Array,179  modulePx = 3,180): MayanResult {181  if (encryptedPayload.length > MAX_PAYLOAD_BYTES) {182    throw new Error(183      `Mayan payload too large: ${encryptedPayload.length} bytes (max ${MAX_PAYLOAD_BYTES})`,184    );185  }186  const size = calculateSymbolSize(encryptedPayload.length);187  const center = Math.floor(size / 2);188189  // Mode header (4 bytes): magic | version | length-lo | length-hi190  const header = new Uint8Array(4);191  header[0] = MAYAN_MAGIC;192  header[1] = MAYAN_VERSION;193  header[2] = encryptedPayload.length & 0xff;194  header[3] = (encryptedPayload.length >> 8) & 0xff;195196  const fullData = new Uint8Array(header.length + encryptedPayload.length);197  fullData.set(header);198  fullData.set(encryptedPayload, header.length);199200  const withECC = reedSolomonEncode(fullData);201202  // Bits, MSB-first per byte203  const bits: boolean[] = [];204  for (const byte of withECC) {205    for (let i = 7; i >= 0; i--) bits.push(((byte >> i) & 1) === 1);206  }207208  // Build matrix209  const matrix: boolean[][] = Array.from(210    { length: size },211    () => new Array<boolean>(size).fill(false),212  );213214  // Reference grid (alternating dark/light in fixed phase)215  if (size > 128) {216    for (let p = QUIET_ZONE; p < size - QUIET_ZONE; p++) {217      for (let line = QUIET_ZONE + 32; line < size - QUIET_ZONE; line += 32) {218        const dark = (p % 2) === 0;219        matrix[line][p] = dark;220        matrix[p][line] = dark;221      }222    }223  }224225  drawOthalan(matrix, center, center);226227  // Place data bits228  let bitIdx = 0;229  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bitIdx < bits.length; r++) {230    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bitIdx < bits.length; c++) {231      if (isReserved(r, c, center, size)) continue;232      matrix[r][c] = bits[bitIdx++];233    }234  }235236  const canvas = renderMatrix(matrix, size, modulePx);237  const printable = size * 0.6 <= 210; // fits on A4 width at 0.6mm/module238  return {239    canvas,240    symbolSize: size,241    payloadBytes: encryptedPayload.length,242    printable,243  };244}245246function renderMatrix(247  matrix: boolean[][],248  size: number,249  modulePx: number,250): HTMLCanvasElement {251  const canvas = document.createElement("canvas");252  canvas.width = size * modulePx;253  canvas.height = size * modulePx;254  const ctx = canvas.getContext("2d");255  if (!ctx) throw new Error("Mayan: 2D canvas unavailable");256  ctx.fillStyle = "#ffffff";257  ctx.fillRect(0, 0, canvas.width, canvas.height);258  ctx.fillStyle = "#000000";259  for (let r = 0; r < size; r++) {260    for (let c = 0; c < size; c++) {261      if (matrix[r][c]) {262        ctx.fillRect(c * modulePx, r * modulePx, modulePx, modulePx);263      }264    }265  }266  return canvas;267}268269/** Expose the matrix in addition to the canvas — for round-trip tests that270 * skip the binarization step. */271export function encodeMayanMatrix(272  encryptedPayload: Uint8Array,273): { matrix: boolean[][]; size: number } {274  if (encryptedPayload.length > MAX_PAYLOAD_BYTES) {275    throw new Error(276      `Mayan payload too large: ${encryptedPayload.length} bytes (max ${MAX_PAYLOAD_BYTES})`,277    );278  }279  const size = calculateSymbolSize(encryptedPayload.length);280  const center = Math.floor(size / 2);281  const header = new Uint8Array(4);282  header[0] = MAYAN_MAGIC;283  header[1] = MAYAN_VERSION;284  header[2] = encryptedPayload.length & 0xff;285  header[3] = (encryptedPayload.length >> 8) & 0xff;286  const fullData = new Uint8Array(header.length + encryptedPayload.length);287  fullData.set(header);288  fullData.set(encryptedPayload, header.length);289  const withECC = reedSolomonEncode(fullData);290  const bits: boolean[] = [];291  for (const byte of withECC) {292    for (let i = 7; i >= 0; i--) bits.push(((byte >> i) & 1) === 1);293  }294  const matrix: boolean[][] = Array.from(295    { length: size },296    () => new Array<boolean>(size).fill(false),297  );298  if (size > 128) {299    for (let p = QUIET_ZONE; p < size - QUIET_ZONE; p++) {300      for (let line = QUIET_ZONE + 32; line < size - QUIET_ZONE; line += 32) {301        const dark = (p % 2) === 0;302        matrix[line][p] = dark;303        matrix[p][line] = dark;304      }305    }306  }307  drawOthalan(matrix, center, center);308  let bitIdx = 0;309  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bitIdx < bits.length; r++) {310    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bitIdx < bits.length; c++) {311      if (isReserved(r, c, center, size)) continue;312      matrix[r][c] = bits[bitIdx++];313    }314  }315  return { matrix, size };316}317318// ── DECODER ──────────────────────────────────────────────────────────────────319320/** Decode a Mayan code from raw image data.321 * Returns null when the image isn't a Mayan code (no rune found, magic byte322 * mismatch, or unknown version) or when RS correction fails. */323export function decodeMayan(imageData: ImageData): Uint8Array | null {324  const binary = adaptiveBinarize(imageData);325  const W = imageData.width;326  const H = imageData.height;327328  const rune = findOthalan(binary, W, H);329  if (!rune) return null;330331  const modulePx = estimateModuleSize(binary, rune, W);332  if (!modulePx || modulePx < 1) return null;333334  const symbolModules = Math.round(Math.min(W, H) / modulePx);335  if (symbolModules < 64) return null;336337  const rotation = detectRotation(binary, rune, modulePx);338  const matrix = sampleModuleGrid(339    binary,340    { x: rune.cx, y: rune.cy },341    modulePx,342    symbolModules,343    rotation,344  );345346  return decodeMatrix(matrix, symbolModules);347}348349/** Decode a Mayan code from a sampled module matrix (for tests). */350export function decodeMatrix(351  matrix: boolean[][],352  symbolModules: number,353): Uint8Array | null {354  const center = Math.floor(symbolModules / 2);355356  // Read the first 32 data bits to recover the mode header357  const headerBits = readDataBits(matrix, center, symbolModules, 32);358  if (headerBits.length < 32) return null;359  const headerBytes = bitsToBytes(headerBits);360  if (headerBytes[0] !== MAYAN_MAGIC) return null;361  if (headerBytes[1] !== MAYAN_VERSION) return null;362  const payloadLength = headerBytes[2] | (headerBytes[3] << 8);363  if (payloadLength > MAX_PAYLOAD_BYTES) return null;364365  // Read all data bits — round up to whole RS(255,178) blocks366  const totalDataBytes = 4 + payloadLength;367  const blocks = Math.ceil(totalDataBytes / 178);368  const totalBits = blocks * 255 * 8;369  const allBits = readDataBits(matrix, center, symbolModules, totalBits);370  if (allBits.length < totalBits) return null;371  const rawBytes = new Uint8Array(bitsToBytes(allBits));372373  let decoded: Uint8Array;374  try {375    decoded = reedSolomonDecode(rawBytes, totalDataBytes);376  } catch {377    return null;378  }379  return decoded.slice(4, 4 + payloadLength);380}381382// ── BINARIZATION ─────────────────────────────────────────────────────────────383384function adaptiveBinarize(imageData: ImageData): boolean[][] {385  const { data, width, height } = imageData;386  const out: boolean[][] = Array.from(387    { length: height },388    () => new Array<boolean>(width).fill(false),389  );390  const R = 9;391  // Integral image of grayscale for O(1) box mean per pixel.392  const integral = new Float64Array((width + 1) * (height + 1));393  for (let y = 0; y < height; y++) {394    let rowSum = 0;395    for (let x = 0; x < width; x++) {396      const i = (y * width + x) * 4;397      const gray = 0.299 * data[i] + 0.587 * data[i + 1] + 0.114 * data[i + 2];398      rowSum += gray;399      integral[(y + 1) * (width + 1) + (x + 1)] =400        integral[y * (width + 1) + (x + 1)] + rowSum;401    }402  }403  for (let y = 0; y < height; y++) {404    for (let x = 0; x < width; x++) {405      const i = (y * width + x) * 4;406      const gray = 0.299 * data[i] + 0.587 * data[i + 1] + 0.114 * data[i + 2];407      const x0 = Math.max(0, x - R);408      const y0 = Math.max(0, y - R);409      const x1 = Math.min(width - 1, x + R);410      const y1 = Math.min(height - 1, y + R);411      const sum =412        integral[(y1 + 1) * (width + 1) + (x1 + 1)] -413        integral[(y0) * (width + 1) + (x1 + 1)] -414        integral[(y1 + 1) * (width + 1) + (x0)] +415        integral[(y0) * (width + 1) + (x0)];416      const count = (x1 - x0 + 1) * (y1 - y0 + 1);417      out[y][x] = gray < sum / count - 8;418    }419  }420  return out;421}422423// ── RUNE LOCATION ───────────────────────────────────────────────────────────424425function findOthalan(426  binary: boolean[][],427  W: number,428  H: number,429): { cx: number; cy: number; size: number } | null {430  // Scan horizontally for a dark-light-dark pattern with the diamond's431  // expected proportions: each side ~4-5 modules wide, light interior ≥1.5×.432  //433  // Sliding-window: each dark blob is considered as a potential darkStart.434  // We peek light + dark2 ahead but only consume dark1 — so on a failed435  // match the next iteration's darkStart slides forward to dark2's position436  // (instead of leaping past it). This is critical because the data area437  // immediately left of the rune can contain dark blobs that would otherwise438  // eat the rune's left vertex on a non-sliding scan.439  const candidates: { cx: number; cy: number; size: number }[] = [];440441  const yStart = Math.floor(H * 0.2);442  const yEnd = Math.floor(H * 0.8);443  for (let y = yStart; y < yEnd; y += 2) {444    let x = 0;445    while (x < W) {446      while (x < W && !binary[y][x]) x++;447      if (x >= W) break;448      const darkStart = x;449      while (x < W && binary[y][x]) x++;450      const darkLen = x - darkStart;451452      // Peek ahead: light run, then next dark run. Don't consume them — the453      // next loop iteration will re-skip the light and treat dark2 as dark1.454      let p = x;455      while (p < W && !binary[y][p]) p++;456      const lightLen = p - x;457      const dark2Start = p;458      while (p < W && binary[y][p]) p++;459      const dark2Len = p - dark2Start;460461      if (462        darkLen >= 4 &&463        dark2Len >= 4 &&464        Math.abs(darkLen - dark2Len) <= darkLen * 0.3 &&465        lightLen > darkLen * 1.5 &&466        lightLen < darkLen * 12467      ) {468        const cx = Math.floor((darkStart + p) / 2);469        const size = p - darkStart;470        candidates.push({ cx, cy: y, size });471      }472      // x stays at end of dark1; loop's skip-light advances us into dark2.473    }474  }475476  if (candidates.length < 3) return null;477478  // The rune diamond's three widest scan rows (rune-rows 9, 10, 11) all match479  // the dark-light-dark pattern with size = 23 modules. Pick all candidates480  // tied within ~1 module of the global max, then average their cy/cx to481  // recover the diamond's geometric center robustly.482  const maxSize = candidates.reduce((m, c) => Math.max(m, c.size), 0);483  const modulePx = Math.max(1, Math.round(maxSize / 23));484  const top = candidates.filter((c) => c.size >= maxSize - modulePx);485  let sumCx = 0;486  let sumCy = 0;487  for (const c of top) { sumCx += c.cx; sumCy += c.cy; }488  const cxAvg = sumCx / top.length;489  const cyAvg = sumCy / top.length;490491  // The averaged cy lands on the diamond's geometric vertical center492  // (rune-row 10, the LEFT/RIGHT vertex row). The code-grid center is at493  // rune-row 11 — exactly one module below — because drawOthalan offsets494  // the diamond up by one to make room for the legs. Shift down 1 module.495  return {496    cx: Math.round(cxAvg),497    cy: Math.round(cyAvg + modulePx),498    size: maxSize,499  };500}501502function estimateModuleSize(503  _binary: boolean[][],504  rune: { cx: number; cy: number; size: number },505  _W: number,506): number {507  // Rune spans ~23 modules at its widest horizontal cross-section.508  // Round to integer: module boundaries are always integer pixels.509  return Math.round(rune.size / 23);510}511512function detectRotation(513  binary: boolean[][],514  rune: { cx: number; cy: number; size: number },515  modulePx: number,516): number {517  // Orientation marker is a 3×3 dark block at (rune-row 1-3, rune-col 20-22)518  // = 10 modules right and 10 modules above center at 0°.519  const offsets: { angle: number; dr: number; dc: number }[] = [520    { angle: 0,   dr: -10, dc: +10 },521    { angle: 90,  dr: +10, dc: +10 },522    { angle: 180, dr: +10, dc: -10 },523    { angle: 270, dr: -10, dc: -10 },524  ];525  let bestAngle = 0;526  let bestScore = -1;527  for (const { angle, dr, dc } of offsets) {528    const pr = Math.round(rune.cy + dr * modulePx);529    const pc = Math.round(rune.cx + dc * modulePx);530    let darkCount = 0;531    for (let dr2 = -1; dr2 <= 1; dr2++) {532      for (let dc2 = -1; dc2 <= 1; dc2++) {533        const r = pr + Math.round(dr2 * modulePx);534        const c = pc + Math.round(dc2 * modulePx);535        if (r >= 0 && r < binary.length && c >= 0 && c < binary[0].length) {536          if (binary[r][c]) darkCount++;537        }538      }539    }540    if (darkCount > bestScore) {541      bestScore = darkCount;542      bestAngle = angle;543    }544  }545  return bestAngle;546}547548function sampleModuleGrid(549  binary: boolean[][],550  center: { x: number; y: number },551  modulePx: number,552  symbolModules: number,553  rotation: number,554): boolean[][] {555  const half = Math.floor(symbolModules / 2);556  const matrix: boolean[][] = Array.from(557    { length: symbolModules },558    () => new Array<boolean>(symbolModules).fill(false),559  );560  for (let r = 0; r < symbolModules; r++) {561    for (let c = 0; c < symbolModules; c++) {562      let dr = r - half;563      let dc = c - half;564      if (rotation === 90)  { [dr, dc] = [dc, -dr]; }565      if (rotation === 180) { [dr, dc] = [-dr, -dc]; }566      if (rotation === 270) { [dr, dc] = [-dc, dr]; }567      const px = Math.round(center.x + dc * modulePx);568      const py = Math.round(center.y + dr * modulePx);569      if (570        py >= 0 &&571        py < binary.length &&572        px >= 0 &&573        px < binary[0].length574      ) matrix[r][c] = binary[py][px];575    }576  }577  return matrix;578}579580function readDataBits(581  matrix: boolean[][],582  center: number,583  size: number,584  count: number,585): boolean[] {586  const bits: boolean[] = [];587  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bits.length < count; r++) {588    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bits.length < count; c++) {589      if (isReserved(r, c, center, size)) continue;590      bits.push(matrix[r][c]);591    }592  }593  return bits;594}595596function bitsToBytes(bits: boolean[]): number[] {597  const bytes: number[] = [];598  for (let i = 0; i < bits.length; i += 8) {599    let byte = 0;600    for (let j = 0; j < 8 && i + j < bits.length; j++) {601      if (bits[i + j]) byte |= 1 << (7 - j);602    }603    bytes.push(byte);604  }605  return bytes;606}