QR Code Generator — TypeScript source

// Pure QR code encoder — ISO/IEC 18004, versions 1-40, EC levels L/M/Q/H,
// numeric + alphanumeric + byte modes, all 8 masks with penalty auto-select.
// No React, no DOM (TextEncoder only). Deterministic; invalid input → null.
//
// Version/EC block structure comes from ./qr-tables (transcribed from the
// published spec tables); format and version information strings are computed
// at runtime via their BCH generators rather than transcribed.

import { EC_BLOCKS, ALIGNMENT_CENTERS, type EcLevelKey } from './qr-tables';

export type EcLevel = EcLevelKey;
export type DataMode = 'numeric' | 'alphanumeric' | 'byte';

export interface QrOptions {
  ecLevel?: EcLevel;
  minVersion?: number;
  maxVersion?: number;
  /** 0-7; automatic penalty selection when omitted. */
  mask?: number;
}

export interface QrResult {
  version: number;
  ecLevel: EcLevel;
  size: number;
  mask: number;
  mode: DataMode;
  /** Row-major; modules[y][x]; true = dark. */
  modules: boolean[][];
}

export interface SvgOptions {
  scale?: number;
  margin?: number;
  fg?: string;
  bg?: string;
}

// ---------------------------------------------------------------------------
// Modes and character sets
// ---------------------------------------------------------------------------

const ALNUM_CHARSET = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:';

function pickMode(text: string): DataMode {
  if (/^[0-9]+$/.test(text)) return 'numeric';
  if (text.length > 0 && /^[0-9A-Z $%*+./:-]+$/.test(text)) return 'alphanumeric';
  return 'byte';
}

function countBitsFor(mode: DataMode, version: number): number {
  if (mode === 'byte') return version <= 9 ? 8 : 16;
  return version <= 9 ? 9 : version <= 26 ? 11 : 13;
}

const MODE_INDICATOR: Record<DataMode, number> = {
  numeric: 0b0001,
  alphanumeric: 0b0010,
  byte: 0b0100,
};

// ---------------------------------------------------------------------------
// BitBuffer — MSB-first packing
// ---------------------------------------------------------------------------

class BitBuffer {
  private bits: number[] = [];

  get length(): number {
    return this.bits.length;
  }

  push(value: number, count: number): void {
    for (let i = count - 1; i >= 0; i--) this.bits.push((value >>> i) & 1);
  }

  toBytes(): number[] {
    // The caller pads to a byte boundary before calling, so every group is 8.
    const out: number[] = [];
    for (let i = 0; i < this.bits.length; i += 8) {
      let byte = 0;
      for (let b = 0; b < 8; b++) byte = (byte << 1) | this.bits[i + b];
      out.push(byte);
    }
    return out;
  }
}

// ---------------------------------------------------------------------------
// Reed-Solomon over GF(256), primitive polynomial 0x11D
// ---------------------------------------------------------------------------

const GF_EXP = new Uint8Array(256);
const GF_LOG = new Uint8Array(256);
{
  let x = 1;
  for (let i = 0; i < 255; i++) {
    GF_EXP[i] = x;
    GF_LOG[x] = i;
    x <<= 1;
    if (x & 0x100) x ^= 0x11d;
  }
}

export function gfMul(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return GF_EXP[(GF_LOG[a] + GF_LOG[b]) % 255];
}

/** Generator polynomial of the given degree, coefficients highest-first, monic. */
function rsGenerator(degree: number): number[] {
  let poly = [1];
  for (let i = 0; i < degree; i++) {
    const next = new Array<number>(poly.length + 1).fill(0);
    for (let j = 0; j < poly.length; j++) {
      next[j] ^= poly[j];
      next[j + 1] ^= gfMul(poly[j], GF_EXP[i]);
    }
    poly = next;
  }
  return poly;
}

/** Error-correction codewords for `data` (synthetic division by the generator). */
function rsEncode(data: number[], ecLen: number): number[] {
  const gen = rsGenerator(ecLen);
  const rem = new Array<number>(ecLen).fill(0);
  for (const byte of data) {
    const factor = byte ^ rem[0];
    rem.shift();
    rem.push(0);
    if (factor !== 0) {
      for (let i = 0; i < ecLen; i++) rem[i] ^= gfMul(gen[i + 1], factor);
    }
  }
  return rem;
}

// ---------------------------------------------------------------------------
// BCH format / version information (computed, not transcribed)
// ---------------------------------------------------------------------------

const EC_FORMAT_BITS: Record<EcLevel, number> = { L: 0b01, M: 0b00, Q: 0b11, H: 0b10 };

/** 15-bit format info string (MSB first) for (ecLevel, mask), incl. the 0x5412 mask. */
export function formatInfoString(ecLevel: EcLevel, mask: number): string {
  const data = (EC_FORMAT_BITS[ecLevel] << 3) | mask;
  let v = data << 10;
  const G = 0x537;
  for (let i = 14; i >= 10; i--) {
    if (v & (1 << i)) v ^= G << (i - 10);
  }
  const rem = v & 0x3ff;
  const full = ((data << 10) | rem) ^ 0x5412;
  return full.toString(2).padStart(15, '0');
}

/** 18-bit version info string (MSB first) for versions >= 7. */
export function versionInfoString(version: number): string {
  let v = version << 12;
  const G = 0x1f25;
  for (let i = 17; i >= 12; i--) {
    if (v & (1 << i)) v ^= G << (i - 12);
  }
  const full = (version << 12) | (v & 0xfff);
  return full.toString(2).padStart(18, '0');
}

// ---------------------------------------------------------------------------
// Matrix construction
// ---------------------------------------------------------------------------

class Matrix {
  readonly size: number;
  readonly modules: boolean[][];
  readonly reserved: boolean[][];

  constructor(size: number) {
    this.size = size;
    this.modules = Array.from({ length: size }, () => new Array<boolean>(size).fill(false));
    this.reserved = Array.from({ length: size }, () => new Array<boolean>(size).fill(false));
  }

  set(x: number, y: number, dark: boolean): void {
    this.modules[y][x] = dark;
    this.reserved[y][x] = true;
  }

  /** Write a DATA module — marks nothing reserved, so masking still applies. */
  write(x: number, y: number, dark: boolean): void {
    this.modules[y][x] = dark;
  }

  /** Format/version cells are reserved now, written after masking. */
  reserve(x: number, y: number): void {
    this.reserved[y][x] = true;
  }

  drawFinder(x: number, y: number): void {
    for (let dy = -1; dy <= 7; dy++) {
      for (let dx = -1; dx <= 7; dx++) {
        const X = x + dx;
        const Y = y + dy;
        if (X < 0 || X >= this.size || Y < 0 || Y >= this.size) continue;
        const dark =
          (dx >= 0 && dx <= 6 && (dy === 0 || dy === 6)) ||
          (dy >= 0 && dy <= 6 && (dx === 0 || dx === 6)) ||
          (dx >= 2 && dx <= 4 && dy >= 2 && dy <= 4);
        this.set(X, Y, dark);
      }
    }
  }

  drawAlignment(cx: number, cy: number): void {
    for (let dy = -2; dy <= 2; dy++) {
      for (let dx = -2; dx <= 2; dx++) {
        const dark = Math.max(Math.abs(dx), Math.abs(dy)) !== 1;
        this.set(cx + dx, cy + dy, dark);
      }
    }
  }

  drawFunctionPatterns(version: number): void {
    const size = this.size;
    this.drawFinder(0, 0);
    this.drawFinder(size - 7, 0);
    this.drawFinder(0, size - 7);

    for (let i = 8; i < size - 8; i++) {
      const dark = i % 2 === 0;
      this.set(i, 6, dark);
      this.set(6, i, dark);
    }

    this.set(8, size - 8, true); // dark module: (col 8, row 4*version+9) = size-8

    // Alignment patterns — skip the three that would overlap finders.
    const centers = ALIGNMENT_CENTERS[version - 1];
    const last = centers[centers.length - 1];
    for (const cy of centers) {
      for (const cx of centers) {
        if ((cx === 6 && cy === 6) || (cx === 6 && cy === last) || (cx === last && cy === 6)) {
          continue;
        }
        this.drawAlignment(cx, cy);
      }
    }

    this.reserveFormatAreas(version);
  }

  /** Reserve both format copies + the version info areas (v >= 7). */
  reserveFormatAreas(version: number): void {
    const size = this.size;
    for (let i = 0; i <= 8; i++) {
      this.reserve(i, 8); // row 8, cols 0-8 (skip col 6 — already timing)
      if (i !== 6) this.reserve(8, i); // col 8, rows 0-8
    }
    for (let i = 0; i < 8; i++) this.reserve(size - 1 - i, 8); // col 8, bottom 8 rows
    for (let i = 0; i < 8; i++) this.reserve(8, size - 1 - i); // row 8, right 8 cols

    if (version >= 7) {
      // 3x6 + 6x3 blocks at bottom-right of the top-right finder and
      // right of the bottom-left finder. Both copies mirror each other.
      for (let i = 0; i < 18; i++) {
        const a = size - 11 + (i % 3);
        const b = Math.floor(i / 3);
        this.reserve(a, b);
        this.reserve(b, a);
      }
    }
  }

  drawFormatAndVersion(ecLevel: EcLevel, mask: number, version: number): void {
    const size = this.size;
    const format = formatInfoString(ecLevel, mask);
    const bit = (i: number) => format[i] === '1';

    // Copy 1 (top-left): row 8 cols 0-5,7,8 then col 8 rows 7,5..0 — MSB first.
    const copy1: Array<[number, number]> = [
      [0, 8], [1, 8], [2, 8], [3, 8], [4, 8], [5, 8], [7, 8], [8, 8],
      [8, 7], [8, 5], [8, 4], [8, 3], [8, 2], [8, 1], [8, 0],
    ];
    copy1.forEach(([x, y], i) => this.set(x, y, bit(i)));

    // Copy 2: col 8 bottom 7 rows, then row 8 right 8 cols — MSB first.
    for (let i = 0; i < 7; i++) this.set(8, size - 1 - i, bit(i));
    for (let i = 7; i < 15; i++) this.set(size - 15 + i, 8, bit(i));

    if (version >= 7) {
      const vinfo = versionInfoString(version);
      for (let i = 0; i < 18; i++) {
        const dark = vinfo[i] === '1';
        const a = size - 11 + (i % 3);
        const b = Math.floor(i / 3);
        this.set(a, b, dark);
        this.set(b, a, dark);
      }
    }
  }
}

// ---------------------------------------------------------------------------
// Masking and penalty
// ---------------------------------------------------------------------------

function maskBit(mask: number, x: number, y: number): boolean {
  switch (mask) {
    case 0:
      return (x + y) % 2 === 0;
    case 1:
      return y % 2 === 0;
    case 2:
      return x % 3 === 0;
    case 3:
      return (x + y) % 3 === 0;
    case 4:
      return (Math.floor(y / 2) + Math.floor(x / 3)) % 2 === 0;
    case 5:
      return ((x * y) % 2) + ((x * y) % 3) === 0;
    case 6:
      return (((x * y) % 2) + ((x * y) % 3)) % 2 === 0;
    default:
      return (((x + y) % 2) + ((x * y) % 3)) % 2 === 0;
  }
}

function penalty(matrix: Matrix): number {
  const size = matrix.size;
  const m = matrix.modules;
  let score = 0;

  // N1: runs of 5+ same color, rows and columns.
  const runScore = (getter: (i: number, j: number) => boolean): number => {
    let s = 0;
    for (let i = 0; i < size; i++) {
      let run = 1;
      let color = getter(i, 0);
      for (let j = 1; j < size; j++) {
        const c = getter(i, j);
        if (c === color) {
          run++;
          if (run === 5) s += 3;
          else if (run > 5) s += 1;
        } else {
          run = 1;
          color = c;
        }
      }
    }
    return s;
  };
  score += runScore((y, x) => m[y][x]);
  score += runScore((x, y) => m[y][x]);

  // N2: 2x2 blocks of one color.
  for (let y = 0; y < size - 1; y++) {
    for (let x = 0; x < size - 1; x++) {
      const c = m[y][x];
      if (c === m[y][x + 1] && c === m[y + 1][x] && c === m[y + 1][x + 1]) score += 3;
    }
  }

  // N3: finder-like 1011101 with 4 light modules on one side.
  const finderPenalty = (getter: (i: number, j: number) => boolean): number => {
    let s = 0;
    for (let i = 0; i < size; i++) {
      for (let j = 0; j <= size - 11; j++) {
        const seq = [1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0];
        const seqRev = [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1];
        let fwd = true;
        let rev = true;
        for (let k = 0; k < 11; k++) {
          const dark = getter(i, j + k);
          if (dark !== (seq[k] === 1)) fwd = false;
          if (dark !== (seqRev[k] === 1)) rev = false;
        }
        if (fwd || rev) s += 40;
      }
    }
    return s;
  };
  score += finderPenalty((y, x) => m[y][x]);
  score += finderPenalty((x, y) => m[y][x]);

  // N4: dark-module ratio deviation from 50%.
  let dark = 0;
  for (const row of m) for (const cell of row) if (cell) dark++;
  const total = size * size;
  const k = Math.floor(Math.abs((dark * 100) / total - 50) / 5);
  score += k * 10;

  return score;
}

// ---------------------------------------------------------------------------
// Encoder pipeline
// ---------------------------------------------------------------------------

function dataCapacityCodewords(version: number, ecLevel: EcLevel): number {
  const spec = EC_BLOCKS[ecLevel][version - 1];
  return spec.blocks.reduce((sum, b) => sum + b.count * b.dataCodewords, 0);
}

function payloadBits(mode: DataMode, text: string, bytes: number[], version: number, buf: BitBuffer): void {
  const count = mode === 'byte' ? bytes.length : text.length;
  buf.push(MODE_INDICATOR[mode], 4);
  buf.push(count, countBitsFor(mode, version));

  if (mode === 'numeric') {
    for (let i = 0; i < text.length; i += 3) {
      const chunk = text.slice(i, i + 3);
      const value = Number(chunk);
      buf.push(value, chunk.length === 3 ? 10 : chunk.length === 2 ? 7 : 4);
    }
  } else if (mode === 'alphanumeric') {
    for (let i = 0; i < text.length; i += 2) {
      if (i + 1 < text.length) {
        buf.push(ALNUM_CHARSET.indexOf(text[i]) * 45 + ALNUM_CHARSET.indexOf(text[i + 1]), 11);
      } else {
        buf.push(ALNUM_CHARSET.indexOf(text[i]), 6);
      }
    }
  } else {
    for (const byte of bytes) buf.push(byte, 8);
  }
}

export function encode(text: string, opts: QrOptions = {}): QrResult | null {
  const ecLevel: EcLevel = opts.ecLevel ?? 'M';
  const minVersion = opts.minVersion ?? 1;
  const maxVersion = Math.min(opts.maxVersion ?? 40, 40);
  if (minVersion < 1 || minVersion > maxVersion) return null;

  const mode = pickMode(text);
  const bytes = mode === 'byte' ? Array.from(new TextEncoder().encode(text)) : [];

  // Smallest version whose data capacity fits the payload.
  let version = 0;
  for (let v = minVersion; v <= maxVersion; v++) {
    const count = mode === 'byte' ? bytes.length : text.length;
    const needed = 4 + countBitsFor(mode, v) + estimatePayloadSize(mode, text, bytes);
    if (needed <= dataCapacityCodewords(v, ecLevel) * 8) {
      version = v;
      break;
    }
  }
  if (version === 0) return null;

  const capacityBits = dataCapacityCodewords(version, ecLevel) * 8;
  const buf = new BitBuffer();
  payloadBits(mode, text, bytes, version, buf);

  // Terminator (up to 4 bits), byte alignment, pad codewords.
  const maxTerminator = Math.min(4, capacityBits - buf.length);
  if (maxTerminator > 0) buf.push(0, maxTerminator);
  while (buf.length % 8 !== 0) buf.push(0, 1);
  const padBytes = [0xec, 0x11];
  let padIndex = 0;
  while (buf.length < capacityBits) {
    buf.push(padBytes[padIndex % 2], 8);
    padIndex++;
  }
  const dataCodewords = buf.toBytes();

  // Split into blocks, compute EC, interleave.
  const spec = EC_BLOCKS[ecLevel][version - 1];
  const dataBlocks: number[][] = [];
  for (const group of spec.blocks) {
    for (let b = 0; b < group.count; b++) {
      const offset = dataBlocks.reduce((sum, blk) => sum + blk.length, 0);
      dataBlocks.push(dataCodewords.slice(offset, offset + group.dataCodewords));
    }
  }
  const ecBlocks = dataBlocks.map((blk) => rsEncode(blk, spec.ecPerBlock));
  const finalCodewords: number[] = [];
  const maxData = Math.max(...dataBlocks.map((b) => b.length));
  for (let i = 0; i < maxData; i++) {
    for (const blk of dataBlocks) if (i < blk.length) finalCodewords.push(blk[i]);
  }
  for (let i = 0; i < spec.ecPerBlock; i++) {
    for (const blk of ecBlocks) finalCodewords.push(blk[i]);
  }

  // Matrix: function patterns, zigzag data, mask, format/version info.
  const size = version * 4 + 17;
  const matrix = new Matrix(size);
  matrix.drawFunctionPatterns(version);

  const bitStream: boolean[] = [];
  for (const cw of finalCodewords) {
    for (let i = 7; i >= 0; i--) bitStream.push(((cw >>> i) & 1) === 1);
  }

  let bitIndex = 0;
  let upward = true;
  for (let right = size - 1; right >= 1; right -= 2) {
    if (right === 6) right -= 1;
    for (let vert = 0; vert < size; vert++) {
      const y = upward ? size - 1 - vert : vert;
      for (const x of [right, right - 1]) {
        if (matrix.reserved[y][x]) continue;
        matrix.write(x, y, bitIndex < bitStream.length ? bitStream[bitIndex] : false);
        bitIndex++;
      }
    }
    upward = !upward;
  }

  // Mask from a pristine post-placement base — candidates never accumulate.
  const base = matrix.modules.map((row) => row.slice());
  const applyToModules = (mask: number | null): void => {
    for (let y = 0; y < size; y++) {
      for (let x = 0; x < size; x++) {
        matrix.modules[y][x] = base[y][x];
        if (mask !== null && !matrix.reserved[y][x] && maskBit(mask, x, y)) {
          matrix.modules[y][x] = !matrix.modules[y][x];
        }
      }
    }
  };

  let chosenMask = 0;
  if (opts.mask !== undefined) {
    if (opts.mask < 0 || opts.mask > 7) return null;
    chosenMask = opts.mask;
    applyToModules(chosenMask);
  } else {
    let best = Infinity;
    for (let mask = 0; mask < 8; mask++) {
      applyToModules(mask);
      const p = penalty(matrix);
      if (p < best) {
        best = p;
        chosenMask = mask;
      }
    }
    applyToModules(chosenMask);
  }

  matrix.drawFormatAndVersion(ecLevel, chosenMask, version);

  return { version, ecLevel, size, mask: chosenMask, mode, modules: matrix.modules };
}

/** Payload bit count for the mode, independent of the count-indicator width. */
function estimatePayloadSize(mode: DataMode, text: string, bytes: number[]): number {
  if (mode === 'numeric') {
    const pairs = Math.floor(text.length / 3);
    const rest = text.length - pairs * 3;
    return pairs * 10 + (rest === 2 ? 7 : rest === 1 ? 4 : 0);
  }
  if (mode === 'alphanumeric') {
    const pairs = Math.floor(text.length / 2);
    const rest = text.length - pairs * 2;
    return pairs * 11 + (rest === 1 ? 6 : 0);
  }
  return bytes.length * 8;
}

// ---------------------------------------------------------------------------
// SVG rendering
// ---------------------------------------------------------------------------

export function toSvg(res: QrResult, o: SvgOptions = {}): string {
  const scale = o.scale ?? 4;
  const margin = o.margin ?? 4;
  const fg = o.fg ?? '#000000';
  const bg = o.bg ?? '#ffffff';
  const dim = (res.size + margin * 2) * scale;

  let path = '';
  for (let y = 0; y < res.size; y++) {
    for (let x = 0; x < res.size; x++) {
      if (!res.modules[y][x]) continue;
      const px = (x + margin) * scale;
      const py = (y + margin) * scale;
      path += `M${px} ${py}h${scale}v${scale}h-${scale}z`;
    }
  }

  return (
    `<svg xmlns="http://www.w3.org/2000/svg" width="${dim}" height="${dim}" viewBox="0 0 ${dim} ${dim}" ` +
    `shape-rendering="crispEdges" role="img" aria-label="QR code">` +
    `<rect width="${dim}" height="${dim}" fill="${bg}"/>` +
    `<path d="${path}" fill="${fg}"/>` +
    `</svg>`
  );
}