Source

// A small QR code encoder (ISO/IEC 18004: byte mode, error correction level M, versions 1 to 10),
// copied from the Polls app. A form link is about 50 characters; version 10 holds 213.

/** modules[row][col], true is dark. */
export type QrMatrix = boolean[][];

// Level M, indexed by version.
const ECC_PER_BLOCK = [0, 10, 16, 26, 18, 24, 16, 18, 22, 22, 26];
const BLOCKS = [0, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5];

function rawModules(ver: number): number {
  let n = (16 * ver + 128) * ver + 64;
  if (ver >= 2) {
    const align = Math.floor(ver / 7) + 2;
    n -= (25 * align - 10) * align - 55;
    if (ver >= 7) n -= 36;
  }
  return n;
}
const dataCodewords = (ver: number) => Math.floor(rawModules(ver) / 8) - ECC_PER_BLOCK[ver] * BLOCKS[ver];

function gfMul(x: number, y: number): number {
  let z = 0;
  for (let i = 7; i >= 0; i--) {
    z = (z << 1) ^ ((z >>> 7) * 0x11d);
    z ^= ((y >>> i) & 1) * x;
  }
  return z;
}

function rsDivisor(degree: number): number[] {
  const out = new Array(degree).fill(0);
  out[degree - 1] = 1;
  let root = 1;
  for (let i = 0; i < degree; i++) {
    for (let j = 0; j < degree; j++) {
      out[j] = gfMul(out[j], root);
      if (j + 1 < degree) out[j] ^= out[j + 1];
    }
    root = gfMul(root, 2);
  }
  return out;
}

function rsRemainder(data: number[], divisor: number[]): number[] {
  const out = divisor.map(() => 0);
  for (const b of data) {
    const factor = b ^ (out.shift() as number);
    out.push(0);
    divisor.forEach((c, i) => { out[i] ^= gfMul(c, factor); });
  }
  return out;
}

/** Data codewords followed by error correction, split into blocks and interleaved. */
function codewords(bytes: Uint8Array, ver: number): number[] {
  const capacity = dataCodewords(ver) * 8;
  const bits: number[] = [];
  const push = (value: number, length: number) => { for (let i = length - 1; i >= 0; i--) bits.push((value >>> i) & 1); };
  push(0b0100, 4);
  push(bytes.length, ver < 10 ? 8 : 16);
  bytes.forEach((b) => push(b, 8));
  push(0, Math.min(4, capacity - bits.length));
  push(0, (8 - (bits.length % 8)) % 8);
  for (let pad = 0xec; bits.length < capacity; pad ^= 0xec ^ 0x11) push(pad, 8);
  const data: number[] = [];
  for (let i = 0; i < bits.length; i += 8) data.push(bits.slice(i, i + 8).reduce((a, b) => (a << 1) | b, 0));

  const blocks = BLOCKS[ver];
  const eccLen = ECC_PER_BLOCK[ver];
  const raw = Math.floor(rawModules(ver) / 8);
  const shortBlocks = blocks - (raw % blocks);
  const shortLen = Math.floor(raw / blocks);
  const divisor = rsDivisor(eccLen);
  const out: number[][] = [];
  for (let i = 0, k = 0; i < blocks; i++) {
    const block = data.slice(k, k + shortLen - eccLen + (i < shortBlocks ? 0 : 1));
    k += block.length;
    const ecc = rsRemainder(block, divisor);
    if (i < shortBlocks) block.push(0);
    out.push(block.concat(ecc));
  }
  const result: number[] = [];
  for (let i = 0; i < out[0].length; i++) {
    out.forEach((block, j) => { if (i !== shortLen - eccLen || j >= shortBlocks) result.push(block[i]); });
  }
  return result;
}

const MASKS: ((r: number, c: number) => boolean)[] = [
  (r, c) => (r + c) % 2 === 0,
  (r) => r % 2 === 0,
  (_, c) => c % 3 === 0,
  (r, c) => (r + c) % 3 === 0,
  (r, c) => (Math.floor(r / 2) + Math.floor(c / 3)) % 2 === 0,
  (r, c) => ((r * c) % 2) + ((r * c) % 3) === 0,
  (r, c) => (((r * c) % 2) + ((r * c) % 3)) % 2 === 0,
  (r, c) => (((r + c) % 2) + ((r * c) % 3)) % 2 === 0,
];

/** Penalty points for a finished symbol (the four rules of ISO 18004 section 7.8.3). */
function penalty(m: QrMatrix): number {
  const n = m.length;
  let points = 0;
  let dark = 0;
  for (let a = 0; a < n; a++) {
    let runRow = 0, runCol = 0, bitsRow = 0, bitsCol = 0;
    for (let b = 0; b < n; b++) {
      const row = m[a][b], col = m[b][a];
      if (row) dark++;
      runRow = b > 0 && row === m[a][b - 1] ? runRow + 1 : 1;
      if (runRow === 5) points += 3; else if (runRow > 5) points++;
      runCol = b > 0 && col === m[b - 1][a] ? runCol + 1 : 1;
      if (runCol === 5) points += 3; else if (runCol > 5) points++;
      bitsRow = ((bitsRow << 1) & 0x7ff) | (row ? 1 : 0);
      bitsCol = ((bitsCol << 1) & 0x7ff) | (col ? 1 : 0);
      if (b >= 10 && (bitsRow === 0x5d0 || bitsRow === 0x05d)) points += 40;
      if (b >= 10 && (bitsCol === 0x5d0 || bitsCol === 0x05d)) points += 40;
      if (a < n - 1 && b < n - 1) {
        const sum = +m[a][b] + +m[a][b + 1] + +m[a + 1][b] + +m[a + 1][b + 1];
        if (sum === 0 || sum === 4) points += 3;
      }
    }
  }
  return points + Math.abs(Math.ceil((dark * 100) / (n * n) / 5) - 10) * 10;
}

/** The QR code for text, as a grid of modules (no quiet zone). */
export function qrMatrix(text: string): QrMatrix {
  const bytes = new TextEncoder().encode(text);
  let ver = 1;
  while (ver <= 10 && 4 + (ver < 10 ? 8 : 16) + bytes.length * 8 > dataCodewords(ver) * 8) ver++;
  if (ver > 10) throw new Error("That is too long for a QR code.");
  const size = ver * 4 + 17;
  const m: QrMatrix = Array.from({ length: size }, () => new Array(size).fill(false));
  const fixed: boolean[][] = Array.from({ length: size }, () => new Array(size).fill(false));
  const put = (r: number, c: number, dark: boolean) => { m[r][c] = dark; fixed[r][c] = true; };

  for (let i = 0; i < size; i++) { put(6, i, i % 2 === 0); put(i, 6, i % 2 === 0); }
  for (const [cr, cc] of [[3, 3], [3, size - 4], [size - 4, 3]]) {
    for (let dr = -4; dr <= 4; dr++) for (let dc = -4; dc <= 4; dc++) {
      const r = cr + dr, c = cc + dc, d = Math.max(Math.abs(dr), Math.abs(dc));
      if (r >= 0 && r < size && c >= 0 && c < size) put(r, c, d !== 2 && d !== 4);
    }
  }
  if (ver >= 2) {
    const count = Math.floor(ver / 7) + 2;
    const step = Math.ceil((ver * 4 + 4) / (count * 2 - 2)) * 2;
    const pos = [6];
    for (let p = size - 7; pos.length < count; p -= step) pos.splice(1, 0, p);
    pos.forEach((r, i) => pos.forEach((c, j) => {
      if ((i === 0 && j === 0) || (i === 0 && j === count - 1) || (i === count - 1 && j === 0)) return;
      for (let dr = -2; dr <= 2; dr++) for (let dc = -2; dc <= 2; dc++) put(r + dr, c + dc, Math.max(Math.abs(dr), Math.abs(dc)) !== 1);
    }));
  }
  const drawFormat = (mask: number) => {
    let rem = mask; // level M is 00
    for (let i = 0; i < 10; i++) rem = (rem << 1) ^ ((rem >>> 9) * 0x537);
    const bits = ((mask << 10) | rem) ^ 0x5412;
    const bit = (i: number) => ((bits >>> i) & 1) === 1;
    for (let i = 0; i <= 5; i++) put(i, 8, bit(i));
    put(7, 8, bit(6));
    put(8, 8, bit(7));
    put(8, 7, bit(8));
    for (let i = 9; i < 15; i++) put(8, 14 - i, bit(i));
    for (let i = 0; i < 8; i++) put(8, size - 1 - i, bit(i));
    for (let i = 8; i < 15; i++) put(size - 15 + i, 8, bit(i));
    put(size - 8, 8, true);
  };
  drawFormat(0);
  if (ver >= 7) {
    let rem = ver;
    for (let i = 0; i < 12; i++) rem = (rem << 1) ^ ((rem >>> 11) * 0x1f25);
    const bits = (ver << 12) | rem;
    for (let i = 0; i < 18; i++) {
      const dark = ((bits >>> i) & 1) === 1;
      const a = size - 11 + (i % 3), b = Math.floor(i / 3);
      put(b, a, dark);
      put(a, b, dark);
    }
  }

  const data = codewords(bytes, ver);
  let i = 0;
  for (let right = size - 1; right >= 1; right -= 2) {
    if (right === 6) right = 5;
    for (let vert = 0; vert < size; vert++) {
      for (let j = 0; j < 2; j++) {
        const c = right - j;
        const r = ((right + 1) & 2) === 0 ? size - 1 - vert : vert;
        if (!fixed[r][c] && i < data.length * 8) {
          m[r][c] = ((data[i >>> 3] >>> (7 - (i & 7))) & 1) === 1;
          i++;
        }
      }
    }
  }

  const applyMask = (mask: number) => {
    for (let r = 0; r < size; r++) for (let c = 0; c < size; c++) if (!fixed[r][c] && MASKS[mask](r, c)) m[r][c] = !m[r][c];
  };
  let best = 0, bestScore = Infinity;
  for (let mask = 0; mask < 8; mask++) {
    drawFormat(mask);
    applyMask(mask);
    const score = penalty(m);
    if (score < bestScore) { best = mask; bestScore = score; }
    applyMask(mask);
  }
  drawFormat(best);
  applyMask(best);
  return m;
}

/** The quiet-zoned SVG path for a matrix: one rectangle per run of dark modules. */
export function qrPath(m: QrMatrix, margin = 4): { d: string; size: number } {
  let d = "";
  m.forEach((row, r) => {
    for (let c = 0; c < row.length;) {
      if (!row[c]) { c++; continue; }
      let end = c;
      while (end < row.length && row[end]) end++;
      d += `M${c + margin} ${r + margin}h${end - c}v1h-${end - c}z`;
      c = end;
    }
  });
  return { d, size: m.length + margin * 2 };
}