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 ~3 modules, interior ≥ 1.5× side.432  const candidates: { cx: number; cy: number; size: number }[] = [];433434  const yStart = Math.floor(H * 0.2);435  const yEnd = Math.floor(H * 0.8);436  for (let y = yStart; y < yEnd; y += 2) {437    let x = 0;438    while (x < W) {439      while (x < W && !binary[y][x]) x++;440      if (x >= W) break;441      const darkStart = x;442      while (x < W && binary[y][x]) x++;443      const darkLen = x - darkStart;444445      const lightStart = x;446      while (x < W && !binary[y][x]) x++;447      const lightLen = x - lightStart;448449      const dark2Start = x;450      while (x < W && binary[y][x]) x++;451      const dark2Len = x - dark2Start;452453      if (454        darkLen >= 4 &&455        dark2Len >= 4 &&456        Math.abs(darkLen - dark2Len) <= darkLen * 0.3 &&457        lightLen > darkLen * 1.5 &&458        lightLen < darkLen * 12459      ) {460        const cx = Math.floor((darkStart + x) / 2);461        const size = x - darkStart;462        candidates.push({ cx, cy: y, size });463      }464    }465  }466467  if (candidates.length < 3) return null;468469  // Cluster by (cx, size) proximity and pick the strongest cluster.470  const best = candidates.reduce((a, b) => (a.size > b.size ? a : b));471472  // Refine cy by scanning vertically through the diamond's horizontal axis.473  let cyTop = best.cy;474  while (cyTop > 0 && binary[cyTop][best.cx]) cyTop--;475  let cyBot = best.cy;476  while (477    cyBot < H - 1 &&478    (binary[cyBot][best.cx] ||479      (best.cx > 0 && binary[cyBot][best.cx - 1]) ||480      (best.cx < W - 1 && binary[cyBot][best.cx + 1]))481  ) cyBot++;482  const cy = Math.floor((cyTop + cyBot) / 2);483  return { cx: best.cx, cy, size: best.size };484}485486function estimateModuleSize(487  _binary: boolean[][],488  rune: { cx: number; cy: number; size: number },489  _W: number,490): number {491  // Rune spans ~23 modules at its widest horizontal cross-section.492  // Round to integer: module boundaries are always integer pixels.493  return Math.round(rune.size / 23);494}495496function detectRotation(497  binary: boolean[][],498  rune: { cx: number; cy: number; size: number },499  modulePx: number,500): number {501  // Orientation marker is a 3×3 dark block at (rune-row 1-3, rune-col 20-22)502  // = 10 modules right and 10 modules above center at 0°.503  const offsets: { angle: number; dr: number; dc: number }[] = [504    { angle: 0,   dr: -10, dc: +10 },505    { angle: 90,  dr: +10, dc: +10 },506    { angle: 180, dr: +10, dc: -10 },507    { angle: 270, dr: -10, dc: -10 },508  ];509  let bestAngle = 0;510  let bestScore = -1;511  for (const { angle, dr, dc } of offsets) {512    const pr = Math.round(rune.cy + dr * modulePx);513    const pc = Math.round(rune.cx + dc * modulePx);514    let darkCount = 0;515    for (let dr2 = -1; dr2 <= 1; dr2++) {516      for (let dc2 = -1; dc2 <= 1; dc2++) {517        const r = pr + Math.round(dr2 * modulePx);518        const c = pc + Math.round(dc2 * modulePx);519        if (r >= 0 && r < binary.length && c >= 0 && c < binary[0].length) {520          if (binary[r][c]) darkCount++;521        }522      }523    }524    if (darkCount > bestScore) {525      bestScore = darkCount;526      bestAngle = angle;527    }528  }529  return bestAngle;530}531532function sampleModuleGrid(533  binary: boolean[][],534  center: { x: number; y: number },535  modulePx: number,536  symbolModules: number,537  rotation: number,538): boolean[][] {539  const half = Math.floor(symbolModules / 2);540  const matrix: boolean[][] = Array.from(541    { length: symbolModules },542    () => new Array<boolean>(symbolModules).fill(false),543  );544  for (let r = 0; r < symbolModules; r++) {545    for (let c = 0; c < symbolModules; c++) {546      let dr = r - half;547      let dc = c - half;548      if (rotation === 90)  { [dr, dc] = [dc, -dr]; }549      if (rotation === 180) { [dr, dc] = [-dr, -dc]; }550      if (rotation === 270) { [dr, dc] = [-dc, dr]; }551      const px = Math.round(center.x + dc * modulePx);552      const py = Math.round(center.y + dr * modulePx);553      if (554        py >= 0 &&555        py < binary.length &&556        px >= 0 &&557        px < binary[0].length558      ) matrix[r][c] = binary[py][px];559    }560  }561  return matrix;562}563564function readDataBits(565  matrix: boolean[][],566  center: number,567  size: number,568  count: number,569): boolean[] {570  const bits: boolean[] = [];571  for (let r = QUIET_ZONE; r < size - QUIET_ZONE && bits.length < count; r++) {572    for (let c = QUIET_ZONE; c < size - QUIET_ZONE && bits.length < count; c++) {573      if (isReserved(r, c, center, size)) continue;574      bits.push(matrix[r][c]);575    }576  }577  return bits;578}579580function bitsToBytes(bits: boolean[]): number[] {581  const bytes: number[] = [];582  for (let i = 0; i < bits.length; i += 8) {583    let byte = 0;584    for (let j = 0; j < 8 && i + j < bits.length; j++) {585      if (bits[i + j]) byte |= 1 << (7 - j);586    }587    bytes.push(byte);588  }589  return bytes;590}