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 { reedSolomonEncode, reedSolomonDecode } from "./rs";2021export const MAYAN_MAGIC = 0x4d;22export const MAYAN_VERSION = 0x01;23export const RUNE_ZONE = 27;     // reserved center: 23×23 rune + 2-module padding each side24export const QUIET_ZONE = 2;25export const ECC_RATE = 0.30;26export const MAX_PAYLOAD_BYTES = 65535;2728export interface MayanResult {29  canvas: HTMLCanvasElement;30  symbolSize: number;31  payloadBytes: number;32  printable: boolean;33}3435// ── SIZE CALCULATION ─────────────────────────────────────────────────────────3637export function calculateSymbolSize(payloadBytes: number): number {38  const headerBytes = 4;39  const totalData = payloadBytes + headerBytes;40  const withECC = totalData / (1 - ECC_RATE);41  const dataBits = Math.ceil(withECC * 8);4243  for (let size = 64; size <= 600; size++) {44    const totalModules = size * size;45    const centerModules = RUNE_ZONE * RUNE_ZONE;46    const quietModules = 4 * size * QUIET_ZONE - 4 * QUIET_ZONE * QUIET_ZONE;47    const refGridModules = size > 12848      ? approxReferenceGridCount(size)49      : 0;50    const usable = totalModules - centerModules - quietModules - refGridModules;51    if (usable >= dataBits) return size;52  }53  return 600;54}5556function approxReferenceGridCount(size: number): number {57  // Reference grid lines at every 32nd row and column (excluding quiet zone).58  // Conservative overestimate: full lines, ignoring intersections with center.59  const lines = Math.floor((size - 2 * QUIET_ZONE) / 32);60  const linePos = lines * (size - 2 * QUIET_ZONE);61  return linePos * 2;62}6364// ── RUNE DRAWING ─────────────────────────────────────────────────────────────6566function fillRect(67  matrix: boolean[][],68  r: number,69  c: number,70  h: number,71  w: number,72): void {73  for (let dr = 0; dr < h; dr++) {74    for (let dc = 0; dc < w; dc++) {75      const mr = r + dr;76      const mc = c + dc;77      if (mr >= 0 && mr < matrix.length && mc >= 0 && mc < matrix[0].length) {78        matrix[mr][mc] = true;79      }80    }81  }82}8384function drawDiag(85  matrix: boolean[][],86  r0: number,87  c0: number,88  r1: number,89  c1: number,90  r2: number,91  c2: number,92  stroke: number,93): void {94  // Stroke diagonal from (r1,c1) to (r2,c2), origin at (r0,c0), as a stair95  // of stroke×stroke blocks. The half-offset centers the stroke on the line.96  const steps = Math.max(Math.abs(r2 - r1), Math.abs(c2 - c1));97  const half = Math.floor(stroke / 2);98  for (let i = 0; i <= steps; i++) {99    const r = Math.round(r1 + ((r2 - r1) * i) / steps);100    const c = Math.round(c1 + ((c2 - c1) * i) / steps);101    fillRect(matrix, r0 + r - half, c0 + c - half, stroke, stroke);102  }103}104105function drawOthalan(106  matrix: boolean[][],107  centerRow: number,108  centerCol: number,109): void {110  // 23×23 region centered on (centerRow, centerCol). Origin = top-left.111  const r0 = centerRow - 11;112  const c0 = centerCol - 11;113  const STROKE = 3;114115  // Diamond corners (within the 23×23 region)116  const TOP   = [1, 11];117  const RIGHT = [10, 21];118  const BOT   = [19, 11];119  const LEFT  = [10, 1];120121  drawDiag(matrix, r0, c0, TOP[0], TOP[1], RIGHT[0], RIGHT[1], STROKE);122  drawDiag(matrix, r0, c0, RIGHT[0], RIGHT[1], BOT[0], BOT[1], STROKE);123  drawDiag(matrix, r0, c0, BOT[0], BOT[1], LEFT[0], LEFT[1], STROKE);124  drawDiag(matrix, r0, c0, LEFT[0], LEFT[1], TOP[0], TOP[1], STROKE);125126  // Two legs descending from below the diamond127  drawDiag(matrix, r0, c0, 19, 8, 22, 4, STROKE);128  drawDiag(matrix, r0, c0, 19, 14, 22, 18, STROKE);129130  // Orientation marker: 3×3 dark block at top-right of rune zone131  fillRect(matrix, r0 + 0, c0 + 20, STROKE, STROKE);132}133134// ── RESERVED-POSITION TEST ───────────────────────────────────────────────────135136export function isReserved(137  r: number,138  c: number,139  center: number,140  size: number,141): boolean {142  if (r < QUIET_ZONE || r >= size - QUIET_ZONE) return true;143  if (c < QUIET_ZONE || c >= size - QUIET_ZONE) return true;144  // 27×27 center zone145  const half = Math.floor(RUNE_ZONE / 2);146  if (147    r >= center - half &&148    r <= center + half &&149    c >= center - half &&150    c <= center + half151  ) return true;152  // Reference grid153  if (size > 128) {154    if (155      r >= QUIET_ZONE && r < size - QUIET_ZONE && (r - QUIET_ZONE) % 32 === 0 &&156      r !== QUIET_ZONE157    ) return true;158    if (159      c >= QUIET_ZONE && c < size - QUIET_ZONE && (c - QUIET_ZONE) % 32 === 0 &&160      c !== QUIET_ZONE161    ) return true;162  }163  return false;164}165166// ── MATRIX BUILD ─────────────────────────────────────────────────────────────167168export function encodeMayan(169  encryptedPayload: Uint8Array,170  modulePx = 3,171): MayanResult {172  if (encryptedPayload.length > MAX_PAYLOAD_BYTES) {173    throw new Error(174      `Mayan payload too large: ${encryptedPayload.length} bytes (max ${MAX_PAYLOAD_BYTES})`,175    );176  }177  const size = calculateSymbolSize(encryptedPayload.length);178  const center = Math.floor(size / 2);179180  // Mode header (4 bytes): magic | version | length-lo | length-hi181  const header = new Uint8Array(4);182  header[0] = MAYAN_MAGIC;183  header[1] = MAYAN_VERSION;184  header[2] = encryptedPayload.length & 0xff;185  header[3] = (encryptedPayload.length >> 8) & 0xff;186187  const fullData = new Uint8Array(header.length + encryptedPayload.length);188  fullData.set(header);189  fullData.set(encryptedPayload, header.length);190191  const withECC = reedSolomonEncode(fullData);192193  // Bits, MSB-first per byte194  const bits: boolean[] = [];195  for (const byte of withECC) {196    for (let i = 7; i >= 0; i--) bits.push(((byte >> i) & 1) === 1);197  }198199  // Build matrix200  const matrix: boolean[][] = Array.from(201    { length: size },202    () => new Array<boolean>(size).fill(false),203  );204205  // Reference grid (alternating dark/light in fixed phase)206  if (size > 128) {207    for (let p = QUIET_ZONE; p < size - QUIET_ZONE; p++) {208      for (let line = QUIET_ZONE + 32; line < size - QUIET_ZONE; line += 32) {209        const dark = (p % 2) === 0;210        matrix[line][p] = dark;211        matrix[p][line] = dark;212      }213    }214  }215216  drawOthalan(matrix, center, center);217218  // Place data bits219  let bitIdx = 0;220  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bitIdx < bits.length; r++) {221    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bitIdx < bits.length; c++) {222      if (isReserved(r, c, center, size)) continue;223      matrix[r][c] = bits[bitIdx++];224    }225  }226227  const canvas = renderMatrix(matrix, size, modulePx);228  const printable = size * 0.6 <= 210; // fits on A4 width at 0.6mm/module229  return {230    canvas,231    symbolSize: size,232    payloadBytes: encryptedPayload.length,233    printable,234  };235}236237function renderMatrix(238  matrix: boolean[][],239  size: number,240  modulePx: number,241): HTMLCanvasElement {242  const canvas = document.createElement("canvas");243  canvas.width = size * modulePx;244  canvas.height = size * modulePx;245  const ctx = canvas.getContext("2d");246  if (!ctx) throw new Error("Mayan: 2D canvas unavailable");247  ctx.fillStyle = "#ffffff";248  ctx.fillRect(0, 0, canvas.width, canvas.height);249  ctx.fillStyle = "#000000";250  for (let r = 0; r < size; r++) {251    for (let c = 0; c < size; c++) {252      if (matrix[r][c]) {253        ctx.fillRect(c * modulePx, r * modulePx, modulePx, modulePx);254      }255    }256  }257  return canvas;258}259260/** Expose the matrix in addition to the canvas — for round-trip tests that261 * skip the binarization step. */262export function encodeMayanMatrix(263  encryptedPayload: Uint8Array,264): { matrix: boolean[][]; size: number } {265  if (encryptedPayload.length > MAX_PAYLOAD_BYTES) {266    throw new Error(267      `Mayan payload too large: ${encryptedPayload.length} bytes (max ${MAX_PAYLOAD_BYTES})`,268    );269  }270  const size = calculateSymbolSize(encryptedPayload.length);271  const center = Math.floor(size / 2);272  const header = new Uint8Array(4);273  header[0] = MAYAN_MAGIC;274  header[1] = MAYAN_VERSION;275  header[2] = encryptedPayload.length & 0xff;276  header[3] = (encryptedPayload.length >> 8) & 0xff;277  const fullData = new Uint8Array(header.length + encryptedPayload.length);278  fullData.set(header);279  fullData.set(encryptedPayload, header.length);280  const withECC = reedSolomonEncode(fullData);281  const bits: boolean[] = [];282  for (const byte of withECC) {283    for (let i = 7; i >= 0; i--) bits.push(((byte >> i) & 1) === 1);284  }285  const matrix: boolean[][] = Array.from(286    { length: size },287    () => new Array<boolean>(size).fill(false),288  );289  if (size > 128) {290    for (let p = QUIET_ZONE; p < size - QUIET_ZONE; p++) {291      for (let line = QUIET_ZONE + 32; line < size - QUIET_ZONE; line += 32) {292        const dark = (p % 2) === 0;293        matrix[line][p] = dark;294        matrix[p][line] = dark;295      }296    }297  }298  drawOthalan(matrix, center, center);299  let bitIdx = 0;300  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bitIdx < bits.length; r++) {301    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bitIdx < bits.length; c++) {302      if (isReserved(r, c, center, size)) continue;303      matrix[r][c] = bits[bitIdx++];304    }305  }306  return { matrix, size };307}308309// ── DECODER ──────────────────────────────────────────────────────────────────310311/** Decode a Mayan code from raw image data.312 * Returns null when the image isn't a Mayan code (no rune found, magic byte313 * mismatch, or unknown version) or when RS correction fails. */314export function decodeMayan(imageData: ImageData): Uint8Array | null {315  const binary = adaptiveBinarize(imageData);316  const W = imageData.width;317  const H = imageData.height;318319  const rune = findOthalan(binary, W, H);320  if (!rune) return null;321322  const modulePx = estimateModuleSize(binary, rune, W);323  if (!modulePx || modulePx < 1) return null;324325  const symbolModules = Math.round(Math.min(W, H) / modulePx);326  if (symbolModules < 64) return null;327328  const rotation = detectRotation(binary, rune, modulePx);329  const matrix = sampleModuleGrid(330    binary,331    { x: rune.cx, y: rune.cy },332    modulePx,333    symbolModules,334    rotation,335  );336337  return decodeMatrix(matrix, symbolModules);338}339340/** Decode a Mayan code from a sampled module matrix (for tests). */341export function decodeMatrix(342  matrix: boolean[][],343  symbolModules: number,344): Uint8Array | null {345  const center = Math.floor(symbolModules / 2);346347  // Read the first 32 data bits to recover the mode header348  const headerBits = readDataBits(matrix, center, symbolModules, 32);349  if (headerBits.length < 32) return null;350  const headerBytes = bitsToBytes(headerBits);351  if (headerBytes[0] !== MAYAN_MAGIC) return null;352  if (headerBytes[1] !== MAYAN_VERSION) return null;353  const payloadLength = headerBytes[2] | (headerBytes[3] << 8);354  if (payloadLength > MAX_PAYLOAD_BYTES) return null;355356  // Read all data bits — round up to whole RS(255,178) blocks357  const totalDataBytes = 4 + payloadLength;358  const blocks = Math.ceil(totalDataBytes / 178);359  const totalBits = blocks * 255 * 8;360  const allBits = readDataBits(matrix, center, symbolModules, totalBits);361  if (allBits.length < totalBits) return null;362  const rawBytes = new Uint8Array(bitsToBytes(allBits));363364  let decoded: Uint8Array;365  try {366    decoded = reedSolomonDecode(rawBytes, totalDataBytes);367  } catch {368    return null;369  }370  return decoded.slice(4, 4 + payloadLength);371}372373// ── BINARIZATION ─────────────────────────────────────────────────────────────374375function adaptiveBinarize(imageData: ImageData): boolean[][] {376  const { data, width, height } = imageData;377  const out: boolean[][] = Array.from(378    { length: height },379    () => new Array<boolean>(width).fill(false),380  );381  const R = 9;382  // Integral image of grayscale for O(1) box mean per pixel.383  const integral = new Float64Array((width + 1) * (height + 1));384  for (let y = 0; y < height; y++) {385    let rowSum = 0;386    for (let x = 0; x < width; x++) {387      const i = (y * width + x) * 4;388      const gray = 0.299 * data[i] + 0.587 * data[i + 1] + 0.114 * data[i + 2];389      rowSum += gray;390      integral[(y + 1) * (width + 1) + (x + 1)] =391        integral[y * (width + 1) + (x + 1)] + rowSum;392    }393  }394  for (let y = 0; y < height; y++) {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      const x0 = Math.max(0, x - R);399      const y0 = Math.max(0, y - R);400      const x1 = Math.min(width - 1, x + R);401      const y1 = Math.min(height - 1, y + R);402      const sum =403        integral[(y1 + 1) * (width + 1) + (x1 + 1)] -404        integral[(y0) * (width + 1) + (x1 + 1)] -405        integral[(y1 + 1) * (width + 1) + (x0)] +406        integral[(y0) * (width + 1) + (x0)];407      const count = (x1 - x0 + 1) * (y1 - y0 + 1);408      out[y][x] = gray < sum / count - 8;409    }410  }411  return out;412}413414// ── RUNE LOCATION ───────────────────────────────────────────────────────────415416function findOthalan(417  binary: boolean[][],418  W: number,419  H: number,420): { cx: number; cy: number; size: number } | null {421  // Scan horizontally for a dark-light-dark pattern with the diamond's422  // expected proportions: each side ~3 modules, interior ≥ 1.5× side.423  const candidates: { cx: number; cy: number; size: number }[] = [];424425  const yStart = Math.floor(H * 0.2);426  const yEnd = Math.floor(H * 0.8);427  for (let y = yStart; y < yEnd; y += 2) {428    let x = 0;429    while (x < W) {430      while (x < W && !binary[y][x]) x++;431      if (x >= W) break;432      const darkStart = x;433      while (x < W && binary[y][x]) x++;434      const darkLen = x - darkStart;435436      const lightStart = x;437      while (x < W && !binary[y][x]) x++;438      const lightLen = x - lightStart;439440      const dark2Start = x;441      while (x < W && binary[y][x]) x++;442      const dark2Len = x - dark2Start;443444      if (445        darkLen >= 2 &&446        dark2Len >= 2 &&447        Math.abs(darkLen - dark2Len) <= darkLen * 0.5 &&448        lightLen > darkLen * 1.5449      ) {450        const cx = Math.floor((darkStart + x) / 2);451        const size = x - darkStart;452        candidates.push({ cx, cy: y, size });453      }454    }455  }456457  if (candidates.length < 3) return null;458459  // Cluster by (cx, size) proximity and pick the strongest cluster.460  const best = candidates.reduce((a, b) => (a.size > b.size ? a : b));461462  // Refine cy by scanning vertically through the diamond's horizontal axis.463  let cyTop = best.cy;464  while (cyTop > 0 && binary[cyTop][best.cx]) cyTop--;465  let cyBot = best.cy;466  while (467    cyBot < H - 1 &&468    (binary[cyBot][best.cx] ||469      (best.cx > 0 && binary[cyBot][best.cx - 1]) ||470      (best.cx < W - 1 && binary[cyBot][best.cx + 1]))471  ) cyBot++;472  const cy = Math.floor((cyTop + cyBot) / 2);473  return { cx: best.cx, cy, size: best.size };474}475476function estimateModuleSize(477  binary: boolean[][],478  rune: { cx: number; cy: number; size: number },479  W: number,480): number {481  const y = rune.cy;482  const strokeWidths: number[] = [];483  for (let x = Math.max(0, rune.cx - rune.size); x < rune.cx + rune.size; x++) {484    if (x >= W) break;485    if (binary[y][x] && (x === 0 || !binary[y][x - 1])) {486      let runLen = 0;487      let xx = x;488      while (xx < W && binary[y][xx]) { runLen++; xx++; }489      if (runLen > 1 && runLen < rune.size / 2) strokeWidths.push(runLen);490    }491  }492  if (strokeWidths.length === 0) return rune.size / 23;493  const avg = strokeWidths.reduce((a, b) => a + b, 0) / strokeWidths.length;494  return avg / 3;495}496497function detectRotation(498  binary: boolean[][],499  rune: { cx: number; cy: number; size: number },500  modulePx: number,501): number {502  // Orientation marker is a 3×3 dark block at (rune-row 1-3, rune-col 20-22)503  // = 10 modules right and 10 modules above center at 0°.504  const offsets: { angle: number; dr: number; dc: number }[] = [505    { angle: 0,   dr: -10, dc: +10 },506    { angle: 90,  dr: +10, dc: +10 },507    { angle: 180, dr: +10, dc: -10 },508    { angle: 270, dr: -10, dc: -10 },509  ];510  let bestAngle = 0;511  let bestScore = -1;512  for (const { angle, dr, dc } of offsets) {513    const pr = Math.round(rune.cy + dr * modulePx);514    const pc = Math.round(rune.cx + dc * modulePx);515    let darkCount = 0;516    for (let dr2 = -1; dr2 <= 1; dr2++) {517      for (let dc2 = -1; dc2 <= 1; dc2++) {518        const r = pr + Math.round(dr2 * modulePx);519        const c = pc + Math.round(dc2 * modulePx);520        if (r >= 0 && r < binary.length && c >= 0 && c < binary[0].length) {521          if (binary[r][c]) darkCount++;522        }523      }524    }525    if (darkCount > bestScore) {526      bestScore = darkCount;527      bestAngle = angle;528    }529  }530  return bestAngle;531}532533function sampleModuleGrid(534  binary: boolean[][],535  center: { x: number; y: number },536  modulePx: number,537  symbolModules: number,538  rotation: number,539): boolean[][] {540  const half = Math.floor(symbolModules / 2);541  const matrix: boolean[][] = Array.from(542    { length: symbolModules },543    () => new Array<boolean>(symbolModules).fill(false),544  );545  for (let r = 0; r < symbolModules; r++) {546    for (let c = 0; c < symbolModules; c++) {547      let dr = r - half;548      let dc = c - half;549      if (rotation === 90)  { [dr, dc] = [dc, -dr]; }550      if (rotation === 180) { [dr, dc] = [-dr, -dc]; }551      if (rotation === 270) { [dr, dc] = [-dc, dr]; }552      const px = Math.round(center.x + dc * modulePx);553      const py = Math.round(center.y + dr * modulePx);554      if (555        py >= 0 &&556        py < binary.length &&557        px >= 0 &&558        px < binary[0].length559      ) matrix[r][c] = binary[py][px];560    }561  }562  return matrix;563}564565function readDataBits(566  matrix: boolean[][],567  center: number,568  size: number,569  count: number,570): boolean[] {571  const bits: boolean[] = [];572  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bits.length < count; r++) {573    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bits.length < count; c++) {574      if (isReserved(r, c, center, size)) continue;575      bits.push(matrix[r][c]);576    }577  }578  return bits;579}580581function bitsToBytes(bits: boolean[]): number[] {582  const bytes: number[] = [];583  for (let i = 0; i < bits.length; i += 8) {584    let byte = 0;585    for (let j = 0; j < 8 && i + j < bits.length; j++) {586      if (bits[i + j]) byte |= 1 << (7 - j);587    }588    bytes.push(byte);589  }590  return bytes;591}