QR 码内部原理：掩码算法、GF(2⁸) 上的 Reed-Solomon 纠错与扫描器流水线

输入数据
  → 模式分析与分段优化
  → 比特流编码
  → 纠错码字生成（GF(2⁸) 上的 Reed-Solomon）
  → 码字交织
  → 模块放置（蛇形路径）
  → 掩码处理（8 个候选评分，选择最优）
  → 格式信息与版本信息编码
  → 最终矩阵

███████   穿过中心的任意扫描线上
█     █   暗:亮:暗:亮:暗模块的比率
█ ███ █   始终为 1:1:3:1:1。此特性具有
█ ███ █   旋转不变性和尺度无关性 ——
█ ███ █   无论距离、角度或透视畸变如何，
█     █   扫描器都能检测到它。
███████

输入: "ABC123def"
朴素方案: 全部使用字节模式 → 9 × 8 = 72 位
最优方案: 字母数字("ABC123") + 字节("def")
         = (6 字符 × 5.5 位) + 模式开销 + (3 × 8) ≈ 57 位

   模块列按两列一组从右向左处理：
   
   从右下角开始：
   
   ←  列对 (n-1, n)
       ↑ 向上移动，在列对内右左交替
   
   ←  列对 (n-3, n-2)
       ↓ 向下移动，在列对内右左交替
   
   ←  列对 (n-5, n-4)
       ↑ 再次向上
   
   ... 持续直到所有数据模块被填充
   
   第 6 列（时序图案）被完全跳过。

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

加法：字节值的异或
乘法：指数相加后对 255 取模（使用对数/反对数表）

示例：
  α³ × α⁵ = α⁸
  α²⁵⁰ × α¹⁰ = α²⁶⁰ 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]:
    """生成 Reed-Solomon 纠错码字。"""
    generator = compute_generator_polynomial(ec_count)
    
    # 消息多项式 = 数据左移 ec_count 个位置
    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):]  # 余数 = 纠错码字

def evaluate_mask(matrix: list[list[int]]) -> int:
    """计算掩码后 QR 矩阵的总惩罚分数。"""
    penalty = 0
    n = len(matrix)
    
    # 规则 1：连续同色模块
    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)
    
    # 规则 2：同色 2×2 块
    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
    
    # 规则 3：类定位图案
    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
    
    # 规则 4：明暗比率
    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

合法: https://bank.example.com/transfer
攻击: https://bаnk.example.com/transfer  (西里尔字母 'а')
      https://bank-example.com/transfer
      https://bank.example.com.evil.com/transfer

QR 载荷: '; DROP TABLE users; --

扫描器 → URL 预览（显示完整域名）→
  用户确认 →
    安全浏览检查（Google Safe Browsing API 或类似服务）→
      着陆页的内容安全策略 →
        不自动执行 tel:/sms:/wifi: 协议方案

对每个像素 (x, y):
  local_mean = 周围窗口内像素的均值（如 21×21）
  threshold = local_mean - C（C 通常为 5-10）
  binary[x][y] = 1 if pixel[x][y] < threshold else 0

对每条水平扫描线：
  跟踪连续同色像素的游程长度
  当找到 5 个连续游程时：
    检查比率是否近似 1:1:3:1:1（误差 ±50% 以内）
    如果是：记录中心点为候选
    
对垂直扫描线和 45° 对角线重复

源点：图像坐标中检测到的定位/校正中心
目标：理想模块网格坐标

H = compute_homography(src_points, dst_points)  // 3×3 矩阵

对理想网格中的每个 (row, col)：
  (x, y) = H⁻¹ × (col + 0.5, row + 0.5)
  module_value = binary_image[round(y)][round(x)]

头部（模式指示符 0011）：
  - 符号位置（4 位）：0–15
  - 总符号数（4 位）：0–15
  - 校验字节（8 位）：所有符号中全部数据字节的异或

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('');
}

// 示例：以字母数字模式编码 "HELLO"
const bitstream = '0010'              // 模式指示符
  + '000001001'                       // 字符计数（版本 1 为 9 位）
  + encodeAlphanumericMode('HELLO');  // 数据位

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

def init_gf_tables():
    """使用多项式 0x11D 初始化 GF(2⁸) 对数和反对数表。"""
    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]:
    """计算 n 个纠错码字的生成多项式。"""
    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]:
    """编码数据并返回纠错码字。"""
    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()

# 示例：版本 1-M 有 16 个数据码字，10 个纠错码字
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}")

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
}

最小模块尺寸 ≥ 扫描器分辨率 × 2（奈奎斯特准则）

基于摄像头的扫描：
  模块像素数 = (物理尺寸 × 相机分辨率) / 扫描距离
  最低要求：每个模块 2-3 像素才能可靠检测

经验法则：
  最小 QR 码尺寸 (mm) ≈ 扫描距离 (mm) / 10
  30cm 扫描 → 最小 3cm
  2m 扫描 → 最小 20cm

1. 计算每种候选模式分段的数据比特长度
2. 对每个版本 V（1–40）：
   a. 查找 V 在目标纠错级别下的总数据码字
   b. 计算可用数据比特 = 码字数 × 8
   c. 如果可用比特 ≥ 所需比特：V 足够
3. 返回最小足够版本

模块数 = 17 + 4V
V=1: 21×21（M 级共 26 码字，16 数据 + 10 纠错）
V=10: 57×57（M 级共 346 码字，213 数据 + 133 纠错）
V=40: 177×177（M 级共 3706 码字，2334 数据 + 1372 纠错）