mayan.ts: encoder + decoder per spec — Othalan rune (23×23 diamond+legs+orientation marker), 27×27 reserved center, 30% RS ECC, mode header 0x4D/v1/u16 length, adaptive binarize via integral image, Chien rotation 0/90/180/270

@@ -0,0 +1,591 @@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+ */18+19+import { reedSolomonEncode, reedSolomonDecode } from "./rs";20+21+export const MAYAN_MAGIC = 0x4d;22+export const MAYAN_VERSION = 0x01;23+export const RUNE_ZONE = 27;     // reserved center: 23×23 rune + 2-module padding each side24+export const QUIET_ZONE = 2;25+export const ECC_RATE = 0.30;26+export const MAX_PAYLOAD_BYTES = 65535;27+28+export interface MayanResult {29+  canvas: HTMLCanvasElement;30+  symbolSize: number;31+  payloadBytes: number;32+  printable: boolean;33+}34+35+// ── SIZE CALCULATION ─────────────────────────────────────────────────────────36+37+export 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);42+43+  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+}55+56+function 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+}63+64+// ── RUNE DRAWING ─────────────────────────────────────────────────────────────65+66+function 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+}83+84+function 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+}104+105+function 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;114+115+  // 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];120+121+  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);125+126+  // 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);129+130+  // Orientation marker: 3×3 dark block at top-right of rune zone131+  fillRect(matrix, r0 + 0, c0 + 20, STROKE, STROKE);132+}133+134+// ── RESERVED-POSITION TEST ───────────────────────────────────────────────────135+136+export 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+}165+166+// ── MATRIX BUILD ─────────────────────────────────────────────────────────────167+168+export 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);179+180+  // 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;186+187+  const fullData = new Uint8Array(header.length + encryptedPayload.length);188+  fullData.set(header);189+  fullData.set(encryptedPayload, header.length);190+191+  const withECC = reedSolomonEncode(fullData);192+193+  // 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+  }198+199+  // Build matrix200+  const matrix: boolean[][] = Array.from(201+    { length: size },202+    () => new Array<boolean>(size).fill(false),203+  );204+205+  // 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+  }215+216+  drawOthalan(matrix, center, center);217+218+  // 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+  }226+227+  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+}236+237+function 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+}259+260+/** Expose the matrix in addition to the canvas — for round-trip tests that261+ * skip the binarization step. */262+export 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+}308+309+// ── DECODER ──────────────────────────────────────────────────────────────────310+311+/** 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. */314+export function decodeMayan(imageData: ImageData): Uint8Array | null {315+  const binary = adaptiveBinarize(imageData);316+  const W = imageData.width;317+  const H = imageData.height;318+319+  const rune = findOthalan(binary, W, H);320+  if (!rune) return null;321+322+  const modulePx = estimateModuleSize(binary, rune, W);323+  if (!modulePx || modulePx < 1) return null;324+325+  const symbolModules = Math.round(Math.min(W, H) / modulePx);326+  if (symbolModules < 64) return null;327+328+  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+  );336+337+  return decodeMatrix(matrix, symbolModules);338+}339+340+/** Decode a Mayan code from a sampled module matrix (for tests). */341+export function decodeMatrix(342+  matrix: boolean[][],343+  symbolModules: number,344+): Uint8Array | null {345+  const center = Math.floor(symbolModules / 2);346+347+  // 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;355+356+  // 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));363+364+  let decoded: Uint8Array;365+  try {366+    decoded = reedSolomonDecode(rawBytes, totalDataBytes);367+  } catch {368+    return null;369+  }370+  return decoded.slice(4, 4 + payloadLength);371+}372+373+// ── BINARIZATION ─────────────────────────────────────────────────────────────374+375+function 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+}413+414+// ── RUNE LOCATION ───────────────────────────────────────────────────────────415+416+function 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 }[] = [];424+425+  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;435+436+      const lightStart = x;437+      while (x < W && !binary[y][x]) x++;438+      const lightLen = x - lightStart;439+440+      const dark2Start = x;441+      while (x < W && binary[y][x]) x++;442+      const dark2Len = x - dark2Start;443+444+      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+  }456+457+  if (candidates.length < 3) return null;458+459+  // Cluster by (cx, size) proximity and pick the strongest cluster.460+  const best = candidates.reduce((a, b) => (a.size > b.size ? a : b));461+462+  // 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+}475+476+function 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+}496+497+function 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+}532+533+function 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+}564+565+function 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+}580+581+function 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+}