Writing a QR Code Encoder From Scratch — Reed-Solomon, Masking, and All

#javascript #algorithms #webdev #qrcode

Writing a QR Code Encoder From Scratch — Reed-Solomon, Masking, and All

QR codes look simple until you encode one from scratch. You need Reed-Solomon error correction over GF(256), finder patterns at three corners, alignment patterns at specific coordinates, 8 mask patterns with penalty scoring, and format information with its own BCH error correction. Implementing ISO/IEC 18004 turned out to be one of the most rewarding algorithm projects I've done.

Most QR code libraries are thousands of lines of dense code. I wanted to understand why. The answer: QR codes are a tightly-specified standard where every byte has a reason, and the reasons span coding theory, geometry, and human factors.

🔗 Live demo: https://sen.ltd/portfolio/qr-scanner/
📦 GitHub: https://github.com/sen-ltd/qr-scanner

Features:

QR encoder from scratch: versions 1-10, byte mode, all 4 EC levels
Customizable colors, size, error correction
PNG download
Browser-based scanner using BarcodeDetector API
URL auto-detection
Japanese / English UI
Zero dependencies, 62 tests

The encoding pipeline

Generating a QR code is a 6-stage pipeline:

Data encoding: text → bitstream with mode indicator and length header
Reed-Solomon error correction: compute EC codewords over GF(256)
Matrix construction: place finder patterns, timing, alignment
Data placement: zig-zag the codewords into the matrix
Masking: apply one of 8 mask patterns, choose best by penalty score
Format info: encode EC level + mask into BCH-protected format bits

Each stage has its own specification section and failure modes.

Reed-Solomon over GF(256)

QR codes use Reed-Solomon error correction to recover from damage. The math lives in GF(256), a finite field with 256 elements:

// Multiplication via log tables
const GF_EXP = new Uint8Array(512);
const GF_LOG = new Uint8Array(256);
function initGF() {
  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; // primitive polynomial
  }
}

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

The primitive polynomial 0x11d (x⁸ + x⁴ + x³ + x² + 1) is specified by the QR standard. Using the wrong polynomial produces codes that look right but don't decode.

The 8 mask patterns

After placing data, QR codes apply one of 8 mask patterns to avoid scanner-confusing configurations (like large blocks of same-color modules). The scorer assigns a penalty to each mask and picks the lowest:

const MASK_PATTERNS = [
  (r, c) => (r + c) % 2 === 0,
  (r, c) => r % 2 === 0,
  (r, 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,
];

Four penalty rules:

Runs of 5+ same-color modules in a row/column
2×2 blocks of same color
Patterns resembling the finder pattern (prevents false positives during scanning)
Imbalanced ratio of dark/light modules

The zig-zag data placement

Data codewords are placed starting from the bottom-right, moving up in vertical pairs of columns, zig-zagging right-to-left across the whole matrix, skipping reserved regions (finders, timing, format):

let col = size - 1;
let upward = true;
while (col > 0) {
  if (col === 6) col--; // skip timing column
  for (let i = 0; i < size; i++) {
    const row = upward ? size - 1 - i : i;
    for (let c = 0; c < 2; c++) {
      if (!reserved[row][col - c]) {
        matrix[row][col - c] = readBit();
      }
    }
  }
  upward = !upward;
  col -= 2;
}

This deterministic traversal means the decoder can do the same thing in reverse.

The scanner side

For scanning, modern browsers have a BarcodeDetector API that handles the hard parts natively:

const detector = new BarcodeDetector({ formats: ['qr_code'] });
const barcodes = await detector.detect(videoElement);
if (barcodes.length > 0) {
  console.log(barcodes[0].rawValue);
}

Chrome and Edge support it directly; Safari and Firefox don't yet. A graceful fallback message explains the situation.

Tests

62 tests covering: Reed-Solomon correctness, matrix dimensions per version, data placement, mask selection, format info BCH encoding, URL detection, and canvas rendering helpers.