QR Code Internals: Masking Algorithms, Reed-Solomon over GF(2⁸), and the Scanner Pipeline

Input data
  → Mode analysis & segment optimization
  → Bit stream encoding
  → Error correction codeword generation (Reed-Solomon over GF(2⁸))
  → Codeword interleaving
  → Module placement (serpentine path)
  → Masking (8 candidates scored, best selected)
  → Format & version information encoding
  → Final matrix

███████   The ratio of dark:light:dark:light:dark modules
█     █   scanned through any line crossing the center is
█ ███ █   always 1:1:3:1:1. This property is rotationally
█ ███ █   invariant and scale-independent — the scanner
█ ███ █   detects it regardless of distance, angle, or
█     █   perspective distortion.
███████

Input: "ABC123def"
Naive:  all Byte mode → 9 × 8 = 72 bits
Optimal: Alphanumeric("ABC123") + Byte("def")
         = (6 chars × 5.5 bits) + mode overhead + (3 × 8) = ~57 bits

   Module columns are processed in pairs, right to left:
   
   Starting at bottom-right corner:
   
   ←  Column pair (n-1, n)
       ↑ upward, alternating right-left within pair
   
   ←  Column pair (n-3, n-2)
       ↓ downward, alternating right-left within pair
   
   ←  Column pair (n-5, n-4)
       ↑ upward again
   
   ... continuing until all data modules are filled
   
   Column 6 (timing pattern) is skipped entirely.

GF(2⁸) = {0, α⁰, α¹, α², ..., α²⁵⁴}

Addition: XOR of byte values
Multiplication: add exponents mod 255 (using log/antilog tables)

Example:
  α³ × α⁵ = α⁸
  α²⁵⁰ × α¹⁰ = α²⁶⁰ mod ²⁵⁵ = α⁵

G(x) = (x − α⁰)(x − α¹)(x − α²)...(x − α^(n−1))

G(x) = (x − 1)(x − α)(x − α²)...(x − α⁹)

def rs_encode(data_codewords: list[int], ec_count: int) -> list[int]:
    """Generate Reed-Solomon error correction codewords."""
    generator = compute_generator_polynomial(ec_count)
    
    # message polynomial = data shifted up by ec_count positions
    message = data_codewords + [0] * ec_count
    
    for i in range(len(data_codewords)):
        if message[i] == 0:
            continue
        coeff = gf_log[message[i]]
        for j in range(len(generator)):
            message[i + j] ^= gf_exp[(coeff + gf_log[generator[j]]) % 255]
    
    return message[len(data_codewords):]  # remainder = EC codewords

def evaluate_mask(matrix: list[list[int]]) -> int:
    """Calculate total penalty score for a masked QR matrix."""
    penalty = 0
    n = len(matrix)
    
    # Rule 1: consecutive same-color modules
    for row in matrix:
        penalty += score_consecutive_run(row)
    for col in range(n):
        column = [matrix[row][col] for row in range(n)]
        penalty += score_consecutive_run(column)
    
    # Rule 2: 2×2 same-color blocks
    for i in range(n - 1):
        for j in range(n - 1):
            if matrix[i][j] == matrix[i][j+1] == matrix[i+1][j] == matrix[i+1][j+1]:
                penalty += 3
    
    # Rule 3: finder-like patterns
    pattern_a = [1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
    pattern_b = [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1]
    for row in matrix:
        penalty += count_pattern(row, pattern_a) * 40
        penalty += count_pattern(row, pattern_b) * 40
    for col in range(n):
        column = [matrix[row][col] for row in range(n)]
        penalty += count_pattern(column, pattern_a) * 40
        penalty += count_pattern(column, pattern_b) * 40
    
    # Rule 4: dark/light ratio
    dark = sum(sum(row) for row in matrix)
    total = n * n
    percent = (dark * 100) // total
    k = abs(percent - 50) // 5
    penalty += k * 10
    
    return penalty

Legitimate: https://bank.example.com/transfer
Attack:     https://bаnk.example.com/transfer  (Cyrillic 'а')
            https://bank-example.com/transfer
            https://bank.example.com.evil.com/transfer

QR payload: '; DROP TABLE users; --

Scanner → URL preview (show full domain) →
  User confirmation →
    Safe browsing check (Google Safe Browsing API / similar) →
      Content Security Policy on landing page →
        No auto-execute of tel:/sms:/wifi: schemes

For each pixel (x, y):
  local_mean = mean of pixels in surrounding window (e.g., 21×21)
  threshold = local_mean - C  (C is typically 5-10)
  binary[x][y] = 1 if pixel[x][y] < threshold else 0

For each horizontal scanline:
  Track run lengths of consecutive same-color pixels
  When 5 consecutive runs are found:
    Check if ratios approximate 1:1:3:1:1 (within ±50%)
    If yes: record center point as candidate
    
Repeat for vertical scanlines and 45° diagonals

Source points: detected finder/alignment centers in image coordinates
Destination: ideal module grid coordinates

H = compute_homography(src_points, dst_points)  // 3×3 matrix

For each (row, col) in the ideal grid:
  (x, y) = H⁻¹ × (col + 0.5, row + 0.5)
  module_value = binary_image[round(y)][round(x)]

Header (mode indicator 0011):
  - Symbol position (4 bits): 0–15
  - Total symbols (4 bits): 0–15
  - Parity byte (8 bits): XOR of all data bytes across all symbols

function encodeNumericMode(digits) {
  const groups = [];
  for (let i = 0; i < digits.length; i += 3) {
    const group = digits.slice(i, i + 3);
    const value = parseInt(group, 10);
    const bits = group.length === 3 ? 10 : group.length === 2 ? 7 : 4;
    groups.push(value.toString(2).padStart(bits, '0'));
  }
  return groups.join('');
}

function encodeAlphanumericMode(text) {
  const charMap = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:';
  const groups = [];
  for (let i = 0; i < text.length; i += 2) {
    if (i + 1 < text.length) {
      const val = charMap.indexOf(text[i]) * 45 + charMap.indexOf(text[i + 1]);
      groups.push(val.toString(2).padStart(11, '0'));
    } else {
      groups.push(charMap.indexOf(text[i]).toString(2).padStart(6, '0'));
    }
  }
  return groups.join('');
}

// Example: encoding "HELLO" in alphanumeric mode
const bitstream = '0010'              // mode indicator
  + '000001001'                       // character count (9 bits for Version 1)
  + encodeAlphanumericMode('HELLO');  // data bits

GF_EXP = [0] * 512
GF_LOG = [0] * 256

def init_gf_tables():
    """Initialize GF(2⁸) log and antilog tables with polynomial 0x11D."""
    x = 1
    for i in range(255):
        GF_EXP[i] = x
        GF_LOG[x] = i
        x <<= 1
        if x & 0x100:
            x ^= 0x11D
    for i in range(255, 512):
        GF_EXP[i] = GF_EXP[i - 255]

def gf_mul(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return GF_EXP[GF_LOG[a] + GF_LOG[b]]

def gf_poly_mul(p: list[int], q: list[int]) -> list[int]:
    result = [0] * (len(p) + len(q) - 1)
    for i, a in enumerate(p):
        for j, b in enumerate(q):
            result[i + j] ^= gf_mul(a, b)
    return result

def rs_generator(n: int) -> list[int]:
    """Compute generator polynomial for n EC codewords."""
    g = [1]
    for i in range(n):
        g = gf_poly_mul(g, [1, GF_EXP[i]])
    return g

def rs_encode(data: list[int], ec_count: int) -> list[int]:
    """Encode data and return EC codewords."""
    gen = rs_generator(ec_count)
    msg = data + [0] * ec_count
    for i in range(len(data)):
        coeff = msg[i]
        if coeff == 0:
            continue
        for j in range(len(gen)):
            msg[i + j] ^= gf_mul(coeff, gen[j])
    return msg[len(data):]

init_gf_tables()

# Example: Version 1-M has 16 data codewords, 10 EC codewords
data_codewords = [32, 91, 11, 120, 209, 114, 220, 77, 67, 64, 236, 17, 236, 17, 236, 17]
ec = rs_encode(data_codewords, 10)
print(f"EC codewords: {ec}")

package main

import "math"

type MaskFunc func(i, j int) bool

var masks = [8]MaskFunc{
    func(i, j int) bool { return (i+j)%2 == 0 },
    func(i, j int) bool { return i%2 == 0 },
    func(i, j int) bool { return j%3 == 0 },
    func(i, j int) bool { return (i+j)%3 == 0 },
    func(i, j int) bool { return (i/2+j/3)%2 == 0 },
    func(i, j int) bool { return (i*j)%2+(i*j)%3 == 0 },
    func(i, j int) bool { return ((i*j)%2+(i*j)%3)%2 == 0 },
    func(i, j int) bool { return ((i+j)%2+(i*j)%3)%2 == 0 },
}

func penaltyRule4(matrix [][]int) int {
    n := len(matrix)
    dark := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == 1 {
                dark++
            }
        }
    }
    total := n * n
    percent := float64(dark) * 100.0 / float64(total)
    k := int(math.Abs(percent-50)) / 5
    return k * 10
}

func selectBestMask(dataMatrix [][]int, isFunction [][]bool) int {
    n := len(dataMatrix)
    bestMask := 0
    bestPenalty := math.MaxInt64

    for m := 0; m < 8; m++ {
        masked := applyMask(dataMatrix, isFunction, masks[m], n)
        penalty := calculateTotalPenalty(masked)
        if penalty < bestPenalty {
            bestPenalty = penalty
            bestMask = m
        }
    }
    return bestMask
}

Minimum module size ≥ scanner resolution × 2  (Nyquist criterion)

For camera-based scanning:
  Module pixels = (physical size × camera resolution) / scanning distance
  Minimum: 2-3 pixels per module for reliable detection

Rule of thumb:
  Minimum QR size (mm) ≈ scanning distance (mm) / 10
  30cm scan → 3cm minimum
  2m scan → 20cm minimum

1. Calculate data bit length for each candidate mode segmentation
2. For each version V (1–40):
   a. Look up total data codewords for V at desired EC level
   b. Calculate available data bits = codewords × 8
   c. If available bits ≥ required bits: V is sufficient
3. Return minimum sufficient version

Modules = 17 + 4V
V=1: 21×21 (26 total codewords at M level, 16 data + 10 EC)
V=10: 57×57 (346 total codewords at M level, 213 data + 133 EC)
V=40: 177×177 (3706 total codewords at M level, 2334 data + 1372 EC)