Files

T

Serendipity 7590b290ca chore: 初始骨架 — 设计文档 + 计划

2026-06-16 23:25:42 +08:00

65 KiB

Raw Permalink Blame History

QR 码生成器 (QRGen) 实现计划

For agentic workers: REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (- [ ]) syntax for tracking.

Goal: 从零实现 ISO/IEC 18004 QR 码生成器，Rust workspace (core + cli)，完整算法手写

Architecture: Workspace 结构 core/ (纯算法库) + cli/ (命令行工具)。core 按数据流水线分层：Galois → RS → 编码 → 矩阵 → 渲染

Tech Stack: Rust 2021 edition, image crate (PNG), clap (CLI parsing), anyhow (error handling)

文件清单

文件	职责	行数估算
`core/src/ecc/galois.rs`	GF(2⁸) 运算 + exp/log 预计算表	~80
`core/src/ecc/reed_solomon.rs`	RS 纠错码生成	~80
`core/src/version.rs`	版本容量表 + 查找	~120
`core/src/encoder/mode.rs`	四种编码模式实现	~150
`core/src/encoder/segment.rs`	字符串分析 + 分段	~100
`core/src/encoder/bitstream.rs`	比特流拼接	~130
`core/src/matrix/grid.rs`	模块矩阵数据结构	~40
`core/src/matrix/patterns.rs`	定位/对齐/时序图案	~100
`core/src/matrix/placement.rs`	蛇形数据排列	~150
`core/src/matrix/mask.rs`	8 种掩码 + 四规则评分	~130
`core/src/render/png.rs`	PNG 渲染	~50
`core/src/render/svg.rs`	SVG 渲染	~50
`core/src/render/ascii.rs`	ASCII 渲染	~50
`core/src/qr.rs`	顶层 API：encode + 输出	~120
`cli/src/main.rs`	CLI 入口 (clap)	~80

Task 1: 搭建 Workspace 骨架

Files:

Create: QRGen/Cargo.toml
Create: QRGen/core/Cargo.toml
Create: QRGen/core/src/lib.rs
Create: QRGen/cli/Cargo.toml
Create: QRGen/cli/src/main.rs
Create: QRGen/core/src/ecc/mod.rs
Create: QRGen/core/src/encoder/mod.rs
Create: QRGen/core/src/matrix/mod.rs
Create: QRGen/core/src/render/mod.rs
Step 1: 创建 workspace 根 Cargo.toml

[workspace]
resolver = "2"
members = ["core", "cli"]

[workspace.package]
version = "0.1.0"
edition = "2021"
license = "MIT"
authors = ["刘航宇"]

Step 2: 创建 core/Cargo.toml

[package]
name = "qr-core"
version.workspace = true
edition.workspace = true
license.workspace = true
authors.workspace = true

[dependencies]
image = { version = "0.25", default-features = false, features = ["png"] }

[dev-dependencies]

Step 3: 创建 cli/Cargo.toml

[package]
name = "qrgen"
version.workspace = true
edition.workspace = true
license.workspace = true
authors.workspace = true

[[bin]]
name = "qrgen"
path = "src/main.rs"

[dependencies]
qr-core = { path = "../core" }
clap = { version = "4", features = ["derive"] }
anyhow = "1"

Step 4: 创建各模块的空 mod.rs 文件

core/src/lib.rs:

pub mod ecc;
pub mod encoder;
pub mod matrix;
pub mod render;
pub mod version;
pub mod qr;

core/src/ecc/mod.rs:

pub mod galois;
pub mod reed_solomon;

core/src/encoder/mod.rs:

pub mod mode;
pub mod segment;
pub mod bitstream;

core/src/matrix/mod.rs:

pub mod grid;
pub mod patterns;
pub mod placement;
pub mod mask;

core/src/render/mod.rs:

pub mod png;
pub mod svg;
pub mod ascii;

cli/src/main.rs:

fn main() {
    println!("QRGen - 开发中");
}

Step 5: 验证编译

cd D:\Code\doing_exercises\programs\QRGen && cargo build

Task 2: GF(2⁸) Galois 域

Files:

Create: QRGen/core/src/ecc/galois.rs
Step 1: 实现 Galois 域运算

/// GF(2⁸) Galois 域运算
/// 本原多项式: x⁸ + x⁴ + x³ + x² + 1 = 0x11D
/// 生成元 α = 0x02

/// 预计算的 exp 表: exp[i] = αⁱ
static EXP_TABLE: [u8; 512] = {
    let mut table = [0u8; 512];
    let mut x = 1u8;
    let mut i = 0;
    while i < 255 {
        table[i] = x;
        table[i + 255] = x; // 双倍长度避免 % 255
        x = if (x << 1) >= 0x100 {
            (x << 1) ^ 0x1D // x⁸ 溢出，减去本原多项式
        } else {
            x << 1
        };
        i += 1;
    }
    table[255 + 255] = table[255]; // 额外填充
    table
};

/// 预计算的 log 表: log[x] = i 使得 αⁱ = x (x > 0)
static LOG_TABLE: [u8; 256] = {
    let mut table = [0u8; 256];
    // EXP_TABLE 此时已初始化
    let mut i = 0usize;
    while i < 255 {
        // 需要运行时计算，这里用函数做
        i += 1;
    }
    table
};

/// GF(2⁸) 加法 = 异或
#[inline]
pub fn add(a: u8, b: u8) -> u8 {
    a ^ b
}

/// GF(2⁸) 减法 = 异或（同加法）
#[inline]
pub fn sub(a: u8, b: u8) -> u8 {
    a ^ b
}

/// GF(2⁸) 乘法
pub fn mul(a: u8, b: u8) -> u8 {
    if a == 0 || b == 0 {
        return 0;
    }
    let log_a = LOG_TABLE[a as usize] as usize;
    let log_b = LOG_TABLE[b as usize] as usize;
    EXP_TABLE[log_a + log_b]
}

/// GF(2⁸) 除法
pub fn div(a: u8, b: u8) -> u8 {
    if a == 0 {
        return 0;
    }
    if b == 0 {
        panic!("GF(2⁸) 除以零");
    }
    let log_a = LOG_TABLE[a as usize] as usize;
    let log_b = LOG_TABLE[b as usize] as usize;
    let diff = (log_a + 255 - log_b) % 255;
    EXP_TABLE[diff]
}

/// GF(2⁸) 幂运算
pub fn pow(base: u8, exp: usize) -> u8 {
    if exp == 0 {
        return 1;
    }
    if base == 0 {
        return 0;
    }
    let log_b = LOG_TABLE[base as usize] as usize;
    EXP_TABLE[(log_b * exp) % 255]
}

/// 懒初始化 log 表
fn init_log_table() -> [u8; 256] {
    let mut table = [0u8; 256];
    let mut x = 1u8;
    for i in 0..255 {
        table[x as usize] = i;
        x = if (x << 1) >= 0x100 {
            (x << 1) ^ 0x1D
        } else {
            x << 1
        };
    }
    table
}

EXP_TABLE 和 LOG_TABLE 不能用 const + 运行时计算，Rust 的 const fn 限制太多。需要改用 once_cell::sync::Lazy 或手工初始化。

修正方案 — 使用函数在首次调用时初始化：

use std::sync::OnceLock;

fn exp_table() -> &'static [u8; 512] {
    static TABLE: OnceLock<[u8; 512]> = OnceLock::new();
    TABLE.get_or_init(|| {
        let mut table = [0u8; 512];
        let mut x = 1u8;
        for i in 0..255 {
            table[i] = x;
            table[i + 255] = x;
            x = if (x << 1) >= 0x100 {
                (x << 1) ^ 0x1D
            } else {
                x << 1
            };
        }
        table[510] = table[255];
        table[511] = table[256];
        table
    })
}

fn log_table() -> &'static [u8; 256] {
    static TABLE: OnceLock<[u8; 256]> = OnceLock::new();
    TABLE.get_or_init(|| {
        let mut table = [0u8; 256];
        let mut x = 1u8;
        for i in 0..255 {
            table[x as usize] = i;
            x = if (x << 1) >= 0x100 {
                (x << 1) ^ 0x1D
            } else {
                x << 1
            };
        }
        table
    })
}

Step 2: 添加测试

在 galois.rs 末尾添加：

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_mul_basic() {
        // 2 * 3 = 6 in GF(2⁸)
        assert_eq!(mul(2, 3), 6);
        // 0xFF * 0x01 = 0xFF
        assert_eq!(mul(0xFF, 1), 0xFF);
        // 任何数乘 0 = 0
        assert_eq!(mul(0xA5, 0), 0);
    }

    #[test]
    fn test_mul_commutative() {
        for a in 0..=255u8 {
            for b in (a..=255u8).step_by(17) {
                assert_eq!(mul(a, b), mul(b, a),
                    "交换律失败: {:02X} * {:02X}", a, b);
            }
        }
    }

    #[test]
    fn test_mul_associative() {
        let cases = [(3, 5, 7), (0xFF, 2, 4), (1, 1, 1), (0x80, 0x40, 0x20)];
        for (a, b, c) in cases {
            assert_eq!(mul(mul(a, b), c), mul(a, mul(b, c)),
                "结合律失败: {:02X} * {:02X} * {:02X}", a, b, c);
        }
    }

    #[test]
    fn test_div_inverse() {
        for a in 1..=255u8 {
            let inv = div(1, a);
            assert_eq!(mul(a, inv), 1,
                "逆元失败: {:02X} * {:02X} != 1", a, inv);
        }
    }

    #[test]
    fn test_div_mul_consistency() {
        for a in 1..=255u8 {
            for b in (1..=255u8).step_by(17) {
                let q = div(a, b);
                assert_eq!(mul(q, b), a,
                    "除乘一致性失败: {:02X} / {:02X} = {:02X}", a, b, q);
            }
        }
    }

    #[test]
    fn test_add_sub() {
        for a in 0..=255u8 {
            for b in 0..=255u8 {
                assert_eq!(add(a, b), sub(a, b));
                assert_eq!(sub(add(a, b), b), a);
            }
        }
    }

    #[test]
    fn test_pow() {
        // α⁰ = 1
        assert_eq!(pow(2, 0), 1);
        // α¹ = 2
        assert_eq!(pow(2, 1), 2);
        // α⁷ * α² = α⁹ — 用 mul 验证
        assert_eq!(mul(pow(2, 7), pow(2, 2)), pow(2, 9));
    }
}

Step 3: 运行测试验证

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core ecc::galois

Expected: 7 tests pass

Step 4: 提交

git add . && git commit -m "feat: GF(2^8) Galois 域运算 + 预计算 exp/log 表"

Task 3: 版本参数表

Files:

Create: QRGen/core/src/version.rs
Step 1: 实现版本容量表

/// 纠错级别
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EcLevel {
    L, // 约 7%
    M, // 约 15%
    Q, // 约 25%
    H, // 约 30%
}

impl EcLevel {
    /// 格式信息中用到的指示位
    pub fn indicator_bits(self) -> u8 {
        match self {
            EcLevel::L => 0b01,
            EcLevel::M => 0b00,
            EcLevel::Q => 0b11,
            EcLevel::H => 0b10,
        }
    }
}

/// 版本号 1~40
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Version(pub u8);

impl Version {
    pub fn new(v: u8) -> Option<Self> {
        if (1..=40).contains(&v) { Some(Version(v)) } else { None }
    }

    /// QR 码边长（模块数）
    pub fn size(self) -> u8 {
        17 + self.0 * 4
    }

    /// 对齐图案位置列表（不含定位图案）
    pub fn alignment_positions(self) -> &'static [u8] {
        &ALIGNMENT_POSITIONS[self.0 as usize - 1]
    }

    /// 获取该版本+级别的纠错信息：
    /// (每组码字数, EC码字数, 组数1, 组1码字数, 组数2, 组2码字数)
    pub fn ec_info(self, level: EcLevel) -> EcInfo {
        let row = &VERSION_TABLE[self.0 as usize - 1];
        let (total, ec_per_block, g1_blocks, g1_data, g2_blocks, g2_data) = match level {
            EcLevel::L => (row.l_total, row.l_ec, row.l_g1, row.l_g1_data, row.l_g2, row.l_g2_data),
            EcLevel::M => (row.m_total, row.m_ec, row.m_g1, row.m_g1_data, row.m_g2, row.m_g2_data),
            EcLevel::Q => (row.q_total, row.q_ec, row.q_g1, row.q_g1_data, row.q_g2, row.q_g2_data),
            EcLevel::H => (row.h_total, row.h_ec, row.h_g1, row.h_g1_data, row.h_g2, row.h_g2_data),
        };
        EcInfo {
            total_codewords: total,
            ec_per_block,
            blocks: vec![
                BlockInfo { count: g1_blocks, data_codewords: g1_data },
                BlockInfo { count: g2_blocks, data_codewords: g2_data },
            ],
        }
    }
}

pub struct EcInfo {
    pub total_codewords: u16,
    pub ec_per_block: u8,
    pub blocks: Vec<BlockInfo>,
}

pub struct BlockInfo {
    pub count: u16,
    pub data_codewords: u16,
}

/// 单行版本数据
struct VersionRow {
    l_total: u16, l_ec: u8, l_g1: u16, l_g1_data: u16, l_g2: u16, l_g2_data: u16,
    m_total: u16, m_ec: u8, m_g1: u16, m_g1_data: u16, m_g2: u16, m_g2_data: u16,
    q_total: u16, q_ec: u8, q_g1: u16, q_g1_data: u16, q_g2: u16, q_g2_data: u16,
    h_total: u16, h_ec: u8, h_g1: u16, h_g1_data: u16, h_g2: u16, h_g2_data: u16,
}

/// ISO 18004 附录 I — 40 版本 × 4 纠错级别的容量表
/// 格式: (总码字数, ec_per_block, 组1数量, 组1数据码字数, 组2数量, 组2数据码字数)
static VERSION_TABLE: [VersionRow; 40] = [
    // 版本 1
    VersionRow {
        l_total: 26, l_ec: 7,  l_g1: 1, l_g1_data: 19,  l_g2: 0, l_g2_data: 0,
        m_total: 26, m_ec: 10, m_g1: 1, m_g1_data: 16,  m_g2: 0, m_g2_data: 0,
        q_total: 26, q_ec: 13, q_g1: 1, q_g1_data: 13,  q_g2: 0, q_g2_data: 0,
        h_total: 26, h_ec: 17, h_g1: 1, h_g1_data: 9,   h_g2: 0, h_g2_data: 0,
    },
    // 版本 2
    VersionRow {
        l_total: 44, l_ec: 10, l_g1: 1, l_g1_data: 34,  l_g2: 0, l_g2_data: 0,
        m_total: 44, m_ec: 16, m_g1: 1, m_g1_data: 28,  m_g2: 0, m_g2_data: 0,
        q_total: 44, q_ec: 22, q_g1: 1, q_g1_data: 22,  q_g2: 0, q_g2_data: 0,
        h_total: 44, h_ec: 28, h_g1: 1, h_g1_data: 16,  m_g2: 0, m_g2_data: 0,
    },
    // ... (后续版本 3-40，数据来自 ISO 18004 表 7/8/9)
    // 版本 3
    // 版本 4
    // ...
    // 版本 40
];

// 对齐图案中心位置表
static ALIGNMENT_POSITIONS: [&[u8]; 40] = [
    &[],                                    // v1
    &[6, 18],                               // v2
    &[6, 22],                               // v3
    &[6, 26],                               // v4
    &[6, 30],                               // v5
    &[6, 34],                               // v6
    &[6, 22, 38],                           // v7
    &[6, 24, 42],                           // v8
    &[6, 26, 46],                           // v9
    &[6, 28, 50],                           // v10
    &[6, 30, 54],                           // v11
    &[6, 32, 58],                           // v12
    &[6, 34, 62],                           // v13
    &[6, 26, 46, 66],                       // v14
    &[6, 26, 48, 70],                       // v15
    &[6, 26, 50, 74],                       // v16
    &[6, 30, 54, 78],                       // v17
    &[6, 30, 56, 82],                       // v18
    &[6, 30, 58, 86],                       // v19
    &[6, 34, 62, 90],                       // v20
    &[6, 28, 50, 72, 94],                   // v21
    &[6, 26, 50, 74, 98],                   // v22
    &[6, 30, 54, 78, 102],                  // v23
    &[6, 28, 54, 80, 106],                  // v24
    &[6, 32, 58, 84, 110],                  // v25
    &[6, 30, 58, 86, 114],                  // v26
    &[6, 34, 62, 90, 118],                  // v27
    &[6, 26, 50, 74, 98, 122],              // v28
    &[6, 30, 54, 78, 102, 126],             // v29
    &[6, 26, 52, 78, 104, 130],             // v30
    &[6, 30, 56, 82, 108, 134],             // v31
    &[6, 34, 60, 86, 112, 138],             // v32
    &[6, 30, 58, 86, 114, 142],             // v33
    &[6, 34, 62, 90, 118, 146],             // v34
    &[6, 30, 54, 78, 102, 126, 150],        // v35
    &[6, 24, 50, 76, 102, 128, 154],        // v36
    &[6, 28, 54, 80, 106, 132, 158],        // v37
    &[6, 32, 58, 84, 110, 136, 162],        // v38
    &[6, 26, 54, 82, 110, 138, 166],        // v39
    &[6, 30, 58, 86, 114, 142, 170],        // v40
];

/// 各版本+级别的数据比特容量表（不含纠错码字）
fn init_capacity_table() -> [[u16; 4]; 40] {
    let mut table = [[0u16; 4]; 40];
    for v in 1..=40u8 {
        let ver = Version(v);
        for (li, level) in [EcLevel::L, EcLevel::M, EcLevel::Q, EcLevel::H].iter().enumerate() {
            let info = ver.ec_info(*level);
            let total_data: u16 = info.blocks.iter()
                .map(|b| b.count * b.data_codewords)
                .sum();
            table[v as usize - 1][li] = total_data;
        }
    }
    table
}

pub fn get_data_capacity(version: Version, level: EcLevel) -> u16 {
    static CAPACITY: OnceLock<[[u16; 4]; 40]> = OnceLock::new();
    let cap = CAPACITY.get_or_init(init_capacity_table);
    cap[version.0 as usize - 1][level as usize]
}

/// 自动选择最小版本
pub fn pick_version(data_bits: u16, level: EcLevel) -> Option<Version> {
    for v in 1..=40 {
        let cap_bits = get_data_capacity(Version(v), level) * 8;
        if cap_bits >= data_bits {
            return Some(Version(v));
        }
    }
    None // 数据太长，超过 version 40 容量
}

注意：版本 3-40 的容量表数据需要从 ISO 18004 标准附录中完整填充。这里先留出结构。

Step 2: 添加版本查找测试

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_version_size() {
        assert_eq!(Version(1).size(), 21);
        assert_eq!(Version(40).size(), 177);
        assert_eq!(Version(2).size(), 25);
    }

    #[test]
    fn test_version_new_out_of_range() {
        assert!(Version::new(0).is_none());
        assert!(Version::new(41).is_none());
    }

    #[test]
    fn test_pick_version_l() {
        // Version 1 L 级: 19 数据码字 = 152 bits
        let v = pick_version(152, EcLevel::L);
        assert_eq!(v, Some(Version(1)));
    }
}

Step 3: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core version

Step 4: 提交

git add . && git commit -m "feat: 版本参数表 + 自动版本选择"

Task 4: Reed-Solomon 编码器

Files:

Create: QRGen/core/src/ecc/reed_solomon.rs
Step 1: 实现 RS 编码

use crate::ecc::galois;

/// 计算多项式相乘: a(x) * b(x) in GF(2⁸)
fn poly_mul(a: &[u8], b: &[u8]) -> Vec<u8> {
    let mut result = vec![0u8; a.len() + b.len() - 1];
    for (i, &ai) in a.iter().enumerate() {
        for (j, &bj) in b.iter().enumerate() {
            result[i + j] = galois::add(result[i + j], galois::mul(ai, bj));
        }
    }
    result
}

/// 构造 RS 生成多项式: ∏ᵢ₌₀ⁿ⁻¹ (x - αⁱ)
/// 参数 n: 纠错码字数
fn generator_polynomial(n: u8) -> Vec<u8> {
    let mut g = vec![1u8]; // 从 g(x) = 1 开始
    for i in 0..n {
        // g(x) *= (x - αⁱ) = (x + αⁱ) in GF(2⁸)
        let factor = vec![1u8, galois::pow(2, i as usize)];
        g = poly_mul(&g, &factor);
    }
    g
}

/// 多项式长除法: message(x) * xⁿ ÷ generator(x)，返回余数（即纠错码字）
/// message: 数据码字
/// ec_count: 纠错码字数量
pub fn compute_ec(data: &[u8], ec_count: u8) -> Vec<u8> {
    let gen = generator_polynomial(ec_count);
    // 构造被除数: data * x^ec_count
    let mut dividend = vec![0u8; data.len() + ec_count as usize];
    dividend[..data.len()].copy_from_slice(data);

    // 多项式长除法
    for i in 0..data.len() {
        let coef = dividend[i];
        if coef != 0 {
            for (j, &g) in gen.iter().enumerate() {
                dividend[i + j] = galois::add(dividend[i + j], galois::mul(coef, g));
            }
        }
    }

    // 余数 = 最后 ec_count 个系数
    dividend[data.len()..].to_vec()
}

/// 对一组数据块生成纠错码字并交错排列
/// blocks: 每个数据块的内容
/// ec_count: 每块纠错码字数
/// 返回: 数据码字交错 + 纠错码字交错
pub fn interleave(blocks: &[Vec<u8>], ec_count: u8) -> Vec<u8> {
    // 数据码字交错：取每块第1个，再取每块第2个...
    let max_data = blocks.iter().map(|b| b.len()).max().unwrap_or(0);
    let mut result = Vec::new();

    for i in 0..max_data {
        for block in blocks.iter() {
            if i < block.len() {
                result.push(block[i]);
            }
        }
    }

    // 对每个块计算 EC
    let ec_blocks: Vec<Vec<u8>> = blocks.iter()
        .map(|b| compute_ec(b, ec_count))
        .collect();

    // EC 码字交错
    for i in 0..ec_count as usize {
        for ec in ec_blocks.iter() {
            result.push(ec[i]);
        }
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_generator_polynomial_degree() {
        let g = generator_polynomial(7);
        // 7 个纠错码字 → 生成多项式应为 7 次，共 8 个系数
        assert_eq!(g.len(), 8);
    }

    #[test]
    fn test_compute_ec_known() {
        // 测试数据来自 ISO 18004 附录示例
        let data = vec![
            0x10, 0x20, 0x0C, 0x56, 0x61, 0x80, 0xEC, 0x11,
            0xEC, 0x11, 0xEC, 0x11, 0xEC, 0x11, 0xEC, 0x11,
            0xA3, 0x12, 0xD3
        ];
        let ec = compute_ec(&data, 7);
        // EC 码字应有 7 个
        assert_eq!(ec.len(), 7);
        // 验证内容（可根据已知正确值检查）
        // 期望: [0xD8, 0x8A, 0x87, 0x3E, 0xDF, 0x4B, 0xCE]
        assert_eq!(ec, vec![0xD8, 0x8A, 0x87, 0x3E, 0xDF, 0x4B, 0xCE]);
    }

    #[test]
    fn test_ec_corrects_zero_data() {
        // 全零数据 + EC → EC 应全零
        let ec = compute_ec(&vec![0u8; 19], 7);
        assert_eq!(ec, vec![0u8; 7]);
    }

    #[test]
    fn test_interleave() {
        let b1 = vec![1, 2, 3];
        let b2 = vec![4, 5];
        let result = interleave(&[b1, b2], 2);
        // 数据交错: 1, 4, 2, 5, 3
        // EC 交错: b1_ec[0], b2_ec[0], b1_ec[1], b2_ec[1]
        assert_eq!(&result[..5], &[1, 4, 2, 5, 3]);
    }
}

Step 2: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core ecc::reed_solomon

Step 3: 提交

git add . && git commit -m "feat: Reed-Solomon 纠错编码 + 数据交错"

Task 5: 编码模式实现

Files:

Create: QRGen/core/src/encoder/mode.rs
Step 1: 实现四种编码模式

/// 编码模式
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Mode {
    Numeric,
    Alphanumeric,
    Byte,
    Kanji,
}

impl Mode {
    /// 模式指示符（4 bit，标准规定）
    pub fn indicator(self) -> u8 {
        match self {
            Mode::Numeric => 0b0001,
            Mode::Alphanumeric => 0b0010,
            Mode::Byte => 0b0100,
            Mode::Kanji => 0b1000,
        }
    }

    /// 字符计数指示符长度（bit）
    pub fn count_bits(self, version: u8) -> u8 {
        match self {
            Mode::Numeric => {
                if version <= 9 { 10 } else if version <= 26 { 12 } else { 14 }
            }
            Mode::Alphanumeric => {
                if version <= 9 { 9 } else if version <= 26 { 11 } else { 13 }
            }
            Mode::Byte => {
                if version <= 9 { 8 } else { 16 }
            }
            Mode::Kanji => {
                if version <= 9 { 8 } else if version <= 26 { 10 } else { 12 }
            }
        }
    }
}

/// 数字模式编码: 每 3 位数字 → 10 bit
pub fn encode_numeric(input: &str) -> Vec<bool> {
    let mut bits = Vec::new();
    let chars: Vec<u8> = input.chars()
        .filter_map(|c| c.to_digit(10).map(|d| d as u8))
        .collect();

    for chunk in chars.chunks(3) {
        let s: String = chunk.iter().map(|d| (b'0' + d) as char).collect();
        let val: u16 = s.parse().unwrap_or(0);
        let bit_width = match chunk.len() {
            3 => 10,
            2 => 7,
            1 => 4,
            _ => 0,
        };
        for i in (0..bit_width).rev() {
            bits.push((val >> i) & 1 == 1);
        }
    }
    bits
}

/// 字母数字模式字符集
const ALPHANUMERIC_CHARS: &[u8] = b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";

/// 字母数字模式编码: 每 2 个字符 → 11 bit
pub fn encode_alphanumeric(input: &str) -> Vec<bool> {
    let values: Vec<u8> = input.chars()
        .filter_map(|c| {
            ALPHANUMERIC_CHARS.iter()
                .position(|&x| x == c as u8)
                .map(|i| i as u8)
        })
        .collect();

    let mut bits = Vec::new();
    for chunk in values.chunks(2) {
        if chunk.len() == 2 {
            let val = chunk[0] as u16 * 45 + chunk[1] as u16;
            for i in (0..11).rev() {
                bits.push((val >> i) & 1 == 1);
            }
        } else {
            // 单个字符 → 6 bit
            for i in (0..6).rev() {
                bits.push((chunk[0] as u16 >> i) & 1 == 1);
            }
        }
    }
    bits
}

/// 字节模式编码: 每字节 → 8 bit
pub fn encode_byte(input: &str) -> Vec<bool> {
    let mut bits = Vec::new();
    for &byte in input.as_bytes() {
        for i in (0..8).rev() {
            bits.push((byte >> i) & 1 == 1);
        }
    }
    bits
}

/// 汉字模式编码 (Shift JIS → 13 bit)
pub fn encode_kanji(input: &str) -> Vec<bool> {
    let mut bits = Vec::new();
    for c in input.chars() {
        // 尝试转 Shift JIS
        if let Some(code) = char_to_shift_jis(c) {
            let val: u16 = if code <= 0x9F {
                (code - 0x8140) as u16  // 差 = code - 0x8140
            } else {
                // 对于 code > 0x9F, 需要处理 0xE040 偏移
                (code - 0xC140) as u16  // code - 0xC140
            };

            let sjis_val = if code <= 0x9FFC {
                let hi = (code >> 8) as u16;
                let lo = (code & 0xFF) as u16;
                if hi >= 0x81 && hi <= 0x9F {
                    (hi - 0x81) * 0xC0 + (lo - 0x40)
                } else {
                    (hi - 0xC1) * 0xC0 + (lo - 0x40)
                }
            } else {
                let hi = (code >> 8) as u16;
                let lo = (code & 0xFF) as u16;
                if hi >= 0x81 && hi <= 0x9F {
                    (hi - 0x81) * 0xC0 + (lo - 0x40)
                } else {
                    (hi - 0xC1) * 0xC0 + (lo - 0x40)
                }
            };

            for i in (0..13).rev() {
                bits.push((sjis_val >> i) & 1 == 1);
            }
        } else {
            // 回退到字节模式
            let utf8_byte = c as u32;
            for i in (0..8).rev() {
                bits.push((utf8_byte as u8 >> i) & 1 == 1);
            }
        }
    }
    bits
}

/// 判断字符是否属于数字模式
pub fn is_numeric(c: char) -> bool {
    c.is_ascii_digit()
}

/// 判断字符是否属于字母数字模式
pub fn is_alphanumeric(c: char) -> bool {
    ALPHANUMERIC_CHARS.contains(&(c as u8))
}

/// 判断字符是否为 Shift JIS 汉字
pub fn is_kanji(c: char) -> bool {
    // 简易检测：CJK 统一汉字范围
    matches!(c,
        '\u{4E00}'..='\u{9FFF}' |   // CJK 统一汉字
        '\u{3400}'..='\u{4DBF}' |   // CJK 扩展 A
        '\u{3000}'..='\u{303F}'       // CJK 标点
    )
}

/// 字符转 Shift JIS 码
fn char_to_shift_jis(c: char) -> Option<u16> {
    // 仅处理常用汉字
    let code = c as u32;
    if code >= 0x4E00 && code <= 0x9FFF {
        // 简化映射：用 Unicode 码位的简单偏移
        // 真正的转换需要查表，这里先做近似
        let base = code - 0x4E00;
        let hi = 0x81 + (base / 0xC0) as u32;
        let lo = 0x40 + (base % 0xC0) as u32;
        Some(((hi << 8) | lo) as u16)
    } else {
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_numeric_encode() {
        let bits = encode_numeric("123");
        // 3 位数字 = 10 bit, 值 123, 二进制 0001111011
        assert_eq!(bits.len(), 10);
        assert_eq!(bits_to_u16(&bits), 123);
    }

    #[test]
    fn test_numeric_single_digit() {
        let bits = encode_numeric("5");
        assert_eq!(bits.len(), 4);
        assert_eq!(bits_to_u16(&bits), 5);
    }

    #[test]
    fn test_numeric_two_digits() {
        let bits = encode_numeric("45");
        assert_eq!(bits.len(), 7);
    }

    #[test]
    fn test_alphanumeric_encode() {
        let bits = encode_alphanumeric("AB");
        // A=10, B=11, val=10*45+11=461 → 11 bit
        assert_eq!(bits.len(), 11);
        assert_eq!(bits_to_u16(&bits), 461);
    }

    #[test]
    fn test_byte_encode() {
        let bits = encode_byte("Hi");
        assert_eq!(bits.len(), 16);
        assert_eq!(bits[..8].iter().filter(|&&b| b).count(), 3); // 'H' = 72
    }

    #[test]
    fn test_mode_indicator_values() {
        assert_eq!(Mode::Numeric.indicator(), 0b0001);
        assert_eq!(Mode::Byte.indicator(), 0b0100);
        assert_eq!(Mode::Kanji.indicator(), 0b1000);
    }

    fn bits_to_u16(bits: &[bool]) -> u16 {
        bits.iter().fold(0, |acc, &b| (acc << 1) | (b as u16))
    }
}

注意：Kanji 模式的 Shift JIS 转换是简化实现。真正的转换需要完整的 Unicode→Shift JIS 映射表。对于实际使用，可以在字节模式下处理中文（UTF-8 字节编码），这比 Kanji 模式更实用。

Step 2: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core encoder::mode

Step 3: 提交

git add . && git commit -m "feat: 四种编码模式（数字/字母/字节/汉字）"

Task 6: 数据分段 + 比特流

Files:

Create: QRGen/core/src/encoder/segment.rs
Create: QRGen/core/src/encoder/bitstream.rs
Step 1: 实现数据分段

// segment.rs
use crate::encoder::mode::{Mode, is_numeric, is_alphanumeric, is_kanji};

/// 数据段：一段连续使用同一种编码模式的数据
#[derive(Debug, Clone)]
pub struct Segment {
    pub mode: Mode,
    pub char_count: u16,
    pub data: String,
}

/// 分析字符串，生成最优分段
pub fn segment_text(text: &str) -> Vec<Segment> {
    if text.is_empty() {
        return vec![];
    }

    let chars: Vec<char> = text.chars().collect();
    let mut segments = Vec::new();
    let mut i = 0;

    while i < chars.len() {
        // 取当前位置开始的连续同类字符
        let range = find_best_run(&chars, i);
        let chunk: String = chars[i..range].iter().collect();
        let mode = char_mode(chars[i]);

        segments.push(Segment {
            mode,
            char_count: (range - i) as u16,
            data: chunk,
        });

        i = range;
    }

    segments
}

/// 找到从 pos 开始的最长同模式字符序列
fn find_best_run(chars: &[char], pos: usize) -> usize {
    if pos >= chars.len() {
        return pos;
    }

    let current_mode = char_mode(chars[pos]);
    let mut end = pos;

    for (i, &c) in chars[pos..].iter().enumerate() {
        if char_mode(c) != current_mode {
            break;
        }
        end = pos + i + 1;
    }

    end
}

/// 判断单个字符的最佳编码模式
fn char_mode(c: char) -> Mode {
    if is_numeric(c) {
        Mode::Numeric
    } else if is_alphanumeric(c) {
        Mode::Alphanumeric
    } else if is_kanji(c) {
        Mode::Kanji
    } else {
        Mode::Byte
    }
}

/// 计算段的比特长度
pub fn segment_bit_length(seg: &Segment, version: u8) -> u16 {
    let mode_bits = 4u16; // 模式指示符
    let count_bits = seg.mode.count_bits(version) as u16;
    let data_bits = match seg.mode {
        Mode::Numeric => {
            let groups_of_3 = seg.char_count / 3;
            let remainder = seg.char_count % 3;
            groups_of_3 * 10 + if remainder == 2 { 7 } else if remainder == 1 { 4 } else { 0 }
        }
        Mode::Alphanumeric => {
            let groups_of_2 = seg.char_count / 2;
            groups_of_2 * 11 + if seg.char_count % 2 == 1 { 6 } else { 0 }
        }
        Mode::Byte => seg.char_count * 8,
        Mode::Kanji => seg.char_count * 13,
    };
    mode_bits + count_bits + data_bits
}

Step 2: 实现比特流拼接

// bitstream.rs
use crate::encoder::mode::{Mode, encode_numeric, encode_alphanumeric, encode_byte, encode_kanji};
use crate::encoder::segment::{Segment, segment_text, segment_bit_length};
use crate::version::{Version, EcLevel, get_data_capacity, pick_version};
use crate::VersionMode;

/// 构建最终的码字序列
pub fn build_codewords(text: &str, version: Version, level: EcLevel) -> Vec<u8> {
    let segments = segment_text(text);
    let mut bits: Vec<bool> = Vec::new();

    // 1. 各段编码
    for seg in &segments {
        // 模式指示符 4 bit
        for i in (0..4).rev() {
            bits.push((seg.mode.indicator() >> i) & 1 == 1);
        }
        // 字符计数
        let count_bits = seg.mode.count_bits(version.0);
        for i in (0..count_bits).rev() {
            bits.push((seg.char_count >> i) & 1 == 1);
        }
        // 数据
        let data_bits = match seg.mode {
            Mode::Numeric => encode_numeric(&seg.data),
            Mode::Alphanumeric => encode_alphanumeric(&seg.data),
            Mode::Byte => encode_byte(&seg.data),
            Mode::Kanji => encode_kanji(&seg.data),
        };
        bits.extend(data_bits);
    }

    // 2. 终止符（最多 4 bit 0）
    let total_capacity = get_data_capacity(version, level) as usize * 8;
    let terminator_len = (4usize).min(total_capacity.saturating_sub(bits.len()));
    bits.extend(std::iter::repeat(false).take(terminator_len));

    // 3. 补零到 8-bit 边界
    while bits.len() % 8 != 0 {
        bits.push(false);
    }

    // 4. 填充码字 0xEC/0x11 交替
    let mut pad_byte = 0xECu8;
    while bits.len() < total_capacity {
        for i in (0..8).rev() {
            bits.push((pad_byte >> i) & 1 == 1);
        }
        pad_byte ^= 0xEC ^ 0x11; // 交替
    }

    // 5. 比特 → 字节
    bits_to_bytes(&bits)
}

fn bits_to_bytes(bits: &[bool]) -> Vec<u8> {
    bits.chunks(8)
        .map(|chunk| chunk.iter().fold(0u8, |acc, &b| (acc << 1) | (b as u8)))
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_build_codewords_simple() {
        let data = build_codewords("123", Version(1), EcLevel::L);
        // Version 1 L: 19 数据码字
        assert_eq!(data.len(), 19);
    }

    #[test]
    fn test_build_codewords_hello() {
        let data = build_codewords("HELLO", Version(1), EcLevel::M);
        assert_eq!(data.len(), 16);
    }

    #[test]
    fn test_terminator_and_padding() {
        // 短数据应该有填充
        let data = build_codewords("A", Version(1), EcLevel::L);
        assert_eq!(data.len(), 19);
    }
}

Step 3: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core encoder::

Step 4: 提交

git add . && git commit -m "feat: 字符串分段 + 比特流编码"

Task 7: 模块矩阵 + 功能图案

Files:

Create: QRGen/core/src/matrix/grid.rs
Create: QRGen/core/src/matrix/patterns.rs
Step 1: 定义矩阵网格

// grid.rs
/// QR 码模块矩阵
#[derive(Clone)]
pub struct Matrix {
    pub size: u8,
    pub modules: Vec<Vec<bool>>, // true=暗(黑), false=亮(白)
}

impl Matrix {
    pub fn new(size: u8) -> Self {
        let modules = vec![vec![false; size as usize]; size as usize];
        Matrix { size, modules }
    }

    pub fn get(&self, x: u8, y: u8) -> bool {
        self.modules[y as usize][x as usize]
    }

    pub fn set(&mut self, x: u8, y: u8, value: bool) {
        self.modules[y as usize][x as usize] = value;
    }

    pub fn is_valid(&self, x: i16, y: i16) -> bool {
        x >= 0 && y >= 0 && (x as u8) < self.size && (y as u8) < self.size
    }
}

Step 2: 绘制功能图案

// patterns.rs
use crate::matrix::grid::Matrix;

/// 放置定位图案（3 个角上的大回字形）
pub fn place_finder_patterns(matrix: &mut Matrix) {
    let positions = [
        (0, 0),                                    // 左上
        ((matrix.size - 7) as usize, 0),            // 右上
        (0, (matrix.size - 7) as usize),            // 左下
    ];

    for &(x, y) in &positions {
        for dy in 0..7 {
            for dx in 0..7 {
                let is_dark = match (dx, dy) {
                    // 外边框 (0 和 6)
                    (0, _) | (6, _) | (_, 0) | (_, 6) => true,
                    // 中间十字 (2-4, 2-4)
                    (2..=4, 2..=4) => true,
                    // 其余为亮
                    _ => false,
                };
                matrix.set((x + dx) as u8, (y + dy) as u8, is_dark);
            }
        }
    }
}

/// 放置时序图案（行 6 和列 6 的交替线）
pub fn place_timing_patterns(matrix: &mut Matrix) {
    // 水平时序线 (y = 6)
    for x in 8..(matrix.size - 8) as usize {
        matrix.set(x as u8, 6, x % 2 == 0);
    }
    // 垂直时序线 (x = 6)
    for y in 8..(matrix.size - 8) as usize {
        matrix.set(6, y as u8, y % 2 == 0);
    }
}

/// 放置对齐图案（回字形 5×5）
pub fn place_alignment_patterns(matrix: &mut Matrix, positions: &[u8]) {
    for &cy in positions {
        for &cx in positions {
            // 跳过与定位图案重叠的位置
            if is_near_finder(cx, cy, matrix.size) {
                continue;
            }
            place_single_alignment(matrix, cx, cy);
        }
    }
}

fn place_single_alignment(matrix: &mut Matrix, cx: u8, cy: u8) {
    let x0 = (cx - 2) as usize;
    let y0 = (cy - 2) as usize;
    for dy in 0..5 {
        for dx in 0..5 {
            let is_dark = match (dx, dy) {
                (0, _) | (4, _) | (_, 0) | (_, 4) => true,  // 外边框
                (2, 2) => true,                               // 中心
                _ => false,
            };
            matrix.set((x0 + dx) as u8, (y0 + dy) as u8, is_dark);
        }
    }
}

/// 检查坐标是否与定位图案重叠
fn is_near_finder(x: u8, y: u8, size: u8) -> bool {
    let s = size as i16;
    let x = x as i16;
    let y = y as i16;
    // 左上角定位图案区域 (0..7, 0..7)
    if x - 2 < 7 && y - 2 < 7 { return true; }
    // 右上角 (size-7..size, 0..7)
    if x + 2 >= s - 7 && y - 2 < 7 { return true; }
    // 左下角 (0..7, size-7..size)
    if x - 2 < 7 && y + 2 >= s - 7 { return true; }
    false
}

/// 放置暗模块 (版本 ≥ 2 时，在 (8, 4*ver+9) 处)
pub fn place_dark_module(matrix: &mut Matrix, version: u8) {
    // 暗模块总是位于 (8, 4*version + 9)
    // 注意：按标准，y 从底部算起，此处坐标体系可能需翻转
    let size = matrix.size;
    matrix.set(8, size - 8, true);
}

/// 预留格式信息区域（15 bit），先标记为 false（会被掩码后的最终格式信息覆盖）
pub fn reserve_format_areas(matrix: &mut Matrix) {
    let size = matrix.size;

    // 定位图案旁的格式信息条
    for i in 0..9 {
        // 左上水平 (0..8, 8) 跳过时序线交叉点
        if i != 6 { matrix.set(i, 8, false); }
        // 左上垂直 (8, 0..8)
        if i != 6 { matrix.set(8, i, false); }
        // 右上垂直 (8, size-8..size-1)
        if i != 6 && i + size - 8 < size { matrix.set(8, size - 1 - i, false); }
        // 左下水平 (size-8..size-1, 8)
        if i != 6 && i + size - 8 < size { matrix.set(size - 1 - i, 8, false); }
    }
    // 暗模块位置
    matrix.set(8, size - 8, true);
}

/// 预留版本信息区域（版本 ≥ 7，18 bit）
pub fn reserve_version_areas(matrix: &mut Matrix) {
    let size = matrix.size;
    // 版本信息在定位图案旁边，共 3×6 的两块
    for i in 0..6 {
        for j in 0..3 {
            // 右上角旁边
            matrix.set(size - 11 + j, i, false);
            // 左下角旁边
            matrix.set(i, size - 11 + j, false);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_finder_patterns_v1() {
        let mut m = Matrix::new(21);
        place_finder_patterns(&mut m);
        // 三个角的外边框应该有黑色模块
        assert!(m.get(0, 0));
        assert!(m.get(20, 0));
        assert!(m.get(0, 20));
        // 定位图案中心 (3,3) 是黑的
        assert!(m.get(3, 3));
    }

    #[test]
    fn test_timing_patterns_alternate() {
        let mut m = Matrix::new(21);
        place_timing_patterns(&mut m);
        assert!(m.get(8, 6));   // 偶数 = 暗
        assert!(!m.get(9, 6));  // 奇数 = 亮
    }
}

Step 3: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core matrix::patterns

Step 4: 提交

git add . && git commit -m "feat: QR 矩阵 + 功能图案绘制"

Task 8: 数据排列 + 掩码

Files:

Create: QRGen/core/src/matrix/placement.rs
Create: QRGen/core/src/matrix/mask.rs
Step 1: 蛇形数据排列

// placement.rs
use crate::matrix::grid::Matrix;

/// 将码字比特按蛇形路径放入矩阵数据区域
pub fn place_data(matrix: &mut Matrix, codewords: &[u8]) {
    let size = matrix.size as usize;
    // 比特流
    let mut bits: Vec<bool> = Vec::new();
    for &cw in codewords {
        for i in (0..8).rev() {
            bits.push((cw >> i) & 1 == 1);
        }
    }

    let mut bit_idx = 0;
    let mut col = (size - 1) as i16; // 从右下角开始
    let mut going_up = true; // 向上扫描

    while col >= 0 {
        // 跳过垂直时序线 (col=6)
        let actual_col = if col == 6 { 5 } else { col };

        if actual_col < 0 { break; }

        if going_up {
            for row in (0..size as i16).rev() {
                if bit_idx >= bits.len() { break; }
                if can_place(matrix, actual_col as u8, row as u8) {
                    matrix.set(actual_col as u8, row as u8, bits[bit_idx]);
                    bit_idx += 1;
                }
                if bit_idx >= bits.len() { break; }
                if can_place(matrix, (actual_col - 1) as u8, row as u8) {
                    matrix.set((actual_col - 1) as u8, row as u8, bits[bit_idx]);
                    bit_idx += 1;
                }
            }
        } else {
            for row in 0..size as i16 {
                if bit_idx >= bits.len() { break; }
                if can_place(matrix, actual_col as u8, row as u8) {
                    matrix.set(actual_col as u8, row as u8, bits[bit_idx]);
                    bit_idx += 1;
                }
                if bit_idx >= bits.len() { break; }
                if can_place(matrix, (actual_col - 1) as u8, row as u8) {
                    matrix.set((actual_col - 1) as u8, row as u8, bits[bit_idx]);
                    bit_idx += 1;
                }
            }
        }

        col -= 2;
        going_up = !going_up;
    }
}

/// 检查 (x, y) 是否为功能图案区域，功能图案区域不能放数据
fn can_place(matrix: &Matrix, x: u8, y: u8) -> bool {
    // 边界检查
    if x >= matrix.size || y >= matrix.size {
        return false;
    }
    // 如果已经设置了值（功能图案），跳过
    // 我们用一个辅助标记来追踪：数据区域初始化为一种状态，功能图案是另一种
    // 简化做法：总是返回 true，允许覆盖，掩码步骤会处理
    true
}

注意：can_place 需要知道哪些位置已经被功能图案占用。更好的做法是在 Matrix 中维护一个 is_reserved 数组。

Step 2: 改进 Matrix 支持保留区域跟踪

在 grid.rs 中增加：

impl Matrix {
    // ...
    pub fn new(size: u8) -> Self {
        let modules = vec![vec![false; size as usize]; size as usize];
        let reserved = vec![vec![false; size as usize]; size as usize];
        Matrix { size, modules, reserved }
    }

    /// 标记为功能图案区域
    pub fn reserve(&mut self, x: u8, y: u8) {
        if x < self.size && y < self.size {
            self.reserved[y as usize][x as usize] = true;
        }
    }

    /// 是否被功能图案占用
    pub fn is_reserved(&self, x: u8, y: u8) -> bool {
        x < self.size && y < self.size && self.reserved[y as usize][x as usize]
    }
}

同时更新 patterns.rs 中所有 matrix.set() 调用为先 matrix.set() 然后 matrix.reserve()。

Step 3: 实现掩码 + 评分

// mask.rs
use crate::matrix::grid::Matrix;

/// 掩码函数类型: f(x, y) = true 时翻转模块
type MaskFn = fn(u8, u8) -> bool;

/// 8 种标准掩码
pub const MASK_FNS: [MaskFn; 8] = [
    |x, y| (x + y) % 2 == 0,                    // 000
    |_, y| y % 2 == 0,                          // 001
    |x, _| x % 3 == 0,                          // 010
    |x, y| (x + y) % 3 == 0,                    // 011
    |x, y| ((y / 2) + (x / 3)) % 2 == 0,       // 100
    |x, y| (x * y) % 2 + (x * y) % 3 == 0,     // 101
    |x, y| ((x * y) % 2 + (x * y) % 3) % 2 == 0, // 110
    |x, y| ((x + y) % 2 + (x * y) % 3) % 2 == 0, // 111
];

/// 应用掩码到矩阵（仅数据区域，跳过功能图案）
pub fn apply_mask(matrix: &Matrix, mask_fn: MaskFn) -> Matrix {
    let mut result = matrix.clone();
    for y in 0..matrix.size {
        for x in 0..matrix.size {
            if !matrix.is_reserved(x, y) && mask_fn(x, y) {
                let current = result.get(x, y);
                result.set(x, y, !current);
            }
        }
    }
    result
}

/// 掩码惩罚评分（越低越好）
pub fn score(matrix: &Matrix) -> u32 {
    let mut penalty = 0u32;

    // 规则 1: 水平/垂直连续 5+ 同色
    penalty += score_rule1(matrix);
    // 规则 2: 同色 2×2 方块
    penalty += score_rule2(matrix);
    // 规则 3: 1011101 模式
    penalty += score_rule3(matrix);
    // 规则 4: 暗模块占比偏离 50%
    penalty += score_rule4(matrix);

    penalty
}

fn score_rule1(matrix: &Matrix) -> u32 {
    let mut penalty = 0u32;
    let n = matrix.size as usize;

    // 水平扫描
    for y in 0..n {
        let mut run = 0u32;
        let mut prev = matrix.get(0, y as u8);
        for x in 1..n {
            let cur = matrix.get(x as u8, y as u8);
            if cur == prev {
                run += 1;
            } else {
                if run >= 5 { penalty += 3 + run - 5; }
                run = 1;
                prev = cur;
            }
        }
        if run >= 5 { penalty += 3 + run - 5; }
    }

    // 垂直扫描
    for x in 0..n {
        let mut run = 0u32;
        let mut prev = matrix.get(x as u8, 0);
        for y in 1..n {
            let cur = matrix.get(x as u8, y as u8);
            if cur == prev {
                run += 1;
            } else {
                if run >= 5 { penalty += 3 + run - 5; }
                run = 1;
                prev = cur;
            }
        }
        if run >= 5 { penalty += 3 + run - 5; }
    }

    penalty
}

fn score_rule2(matrix: &Matrix) -> u32 {
    let mut count = 0u32;
    let n = matrix.size as u8;
    for y in 0..n-1 {
        for x in 0..n-1 {
            let v = matrix.get(x, y);
            if matrix.get(x+1, y) == v && matrix.get(x, y+1) == v && matrix.get(x+1, y+1) == v {
                count += 1;
            }
        }
    }
    count * 3
}

fn score_rule3(matrix: &Matrix) -> u32 {
    let pattern: [bool; 11] = [
        true, false, true, true, true, false, true,  // dark-light-dark-dark-dark-light-dark
        false, false, false, false,                    // 前面是 1 后面是 0
    ];
    let penalty_per = 40u32;

    let mut penalty = 0u32;
    let n = matrix.size as usize;

    // 水平
    for y in 0..n {
        for x in 0..n-10 {
            let matches = (0..11).all(|i| {
                matrix.get((x+i) as u8, y as u8) == pattern[i]
            });
            if matches { penalty += penalty_per; }
        }
    }
    // 垂直
    for x in 0..n {
        for y in 0..n-10 {
            let matches = (0..11).all(|i| {
                matrix.get(x as u8, (y+i) as u8) == pattern[i]
            });
            if matches { penalty += penalty_per; }
        }
    }

    penalty
}

fn score_rule4(matrix: &Matrix) -> u32 {
    let total = (matrix.size as u32) * (matrix.size as u32);
    let dark: u32 = (0..matrix.size).flat_map(|y|
        (0..matrix.size).map(move |x| matrix.get(x, y) as u32)
    ).sum();

    let pct = dark * 100 / total;
    let deviation = ((pct as i32 - 50).abs() as u32) / 5;
    deviation * 10
}

/// 评估所有掩码，返回最佳掩码编号 (0-7) 和对应矩阵
pub fn best_mask(matrix: &Matrix) -> (u8, Matrix) {
    let mut best_idx = 0u8;
    let mut best_score = u32::MAX;
    let mut best_matrix = matrix.clone();

    for i in 0..8 {
        let masked = apply_mask(matrix, MASK_FNS[i]);
        let s = score(&masked);
        if s < best_score {
            best_score = s;
            best_idx = i as u8;
            best_matrix = masked;
        }
    }

    (best_idx, best_matrix)
}

Step 4: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core matrix::

Step 5: 提交

git add . && git commit -m "feat: 蛇形数据排列 + 8 种掩码 + 评分"

Task 9: 格式信息 + 版本信息编码

Files:

Modify: QRGen/core/src/matrix/patterns.rs (追加)
Step 1: 添加格式信息编码

在 patterns.rs 末尾追加：

/// 格式信息 = 2 bit EC 级别 + 3 bit 掩码编号 → BCH(15,5) 编码 → 15 bit
pub fn encode_format_info(level: u8, mask: u8) -> u16 {
    let data = ((level & 0x03) << 3) | (mask & 0x07);
    let mut encoded = data as u16;

    // BCH(15,5) 编码：生成多项式 x¹⁰ + x⁸ + x⁵ + x⁴ + x² + x + 1 = 0x537
    let gen: u16 = 0x537;
    let mut val = encoded << 10;
    for i in (4..=14).rev() {
        if (val >> i) & 1 == 1 {
            val ^= gen << (i - 10);
        }
    }
    encoded = ((data as u16) << 10) | (val & 0x3FF);

    // XOR 掩码 0x5412
    encoded ^ 0x5412
}

/// 将格式信息写入矩阵
pub fn place_format_info(matrix: &mut Matrix, format: u16) {
    let size = matrix.size;

    // 坐标序列（15 个位置，x,y 坐标对）
    let coords = [
        (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),
    ];

    let coords2 = [
        (8, size - 1), (8, size - 2), (8, size - 3), (8, size - 4),
        (8, size - 5), (8, size - 6), (8, size - 7),
        (size - 8, 8), (size - 7, 8), (size - 6, 8), (size - 5, 8),
        (size - 4, 8), (size - 3, 8), (size - 2, 8), (size - 1, 8),
    ];

    for i in 0..15 {
        let bit = (format >> (14 - i)) & 1 == 1;
        let (x, y) = coords[i];
        matrix.set(x, y, bit);
        let (x2, y2) = coords2[i];
        matrix.set(x2, y2, bit);
    }
}

/// 版本信息编码 (版本 ≥ 7): BCH(18,6)
pub fn encode_version_info(version: u8) -> u32 {
    let data = version as u32;
    let gen: u32 = 0x1F25; // x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁵ + x² + 1
    let mut val = data << 12;
    for i in (5..=17).rev() {
        if (val >> i) & 1 == 1 {
            val ^= gen << (i - 12);
        }
    }
    (data << 12) | (val & 0xFFF)
}

/// 将版本信息写入矩阵
pub fn place_version_info(matrix: &mut Matrix, version_info: u32) {
    let size = matrix.size;
    // 在定位图案旁放置 6×3 的版本信息块
    for i in 0..6 {
        for j in 0..3 {
            let bit = (version_info >> (17 - (i * 3 + j))) & 1 == 1;
            // 右上角旁边
            matrix.set(size - 11 + j, i, bit);
            // 左下角旁边
            matrix.set(i, size - 11 + j, bit);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_format_info_known() {
        // M 级 (00) + mask 3 (011) → 预期值
        let info = encode_format_info(0b00, 0b011);
        // 验证 XOR 掩码后为非零值
        assert!(info > 0);
        assert_eq!(info & 0x7FFF, info); // 15 bit 内
    }

    #[test]
    fn test_version_info_known() {
        let info = encode_version_info(7);
        assert_eq!((info >> 12) & 0x3F, 7); // 前 6 bit 是版本号
    }
}

Step 2: 运行测试

cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core matrix::

Step 3: 提交

git add . && git commit -m "feat: 格式信息 BCH 编码 + 版本信息编码"

Task 10: 顶层 API + 渲染器

Files:

Create: QRGen/core/src/qr.rs
Create: QRGen/core/src/render/png.rs
Create: QRGen/core/src/render/svg.rs
Create: QRGen/core/src/render/ascii.rs
Step 1: 实现顶层 API

// qr.rs
use crate::version::{Version, EcLevel, pick_version, get_data_capacity};
use crate::encoder::bitstream::build_codewords;
use crate::encoder::segment::{segment_text, segment_bit_length};
use crate::ecc::reed_solomon;
use crate::matrix::grid::Matrix;
use crate::matrix::patterns::{
    place_finder_patterns, place_timing_patterns, place_alignment_patterns,
    place_dark_module, reserve_format_areas, reserve_version_areas,
    encode_format_info, encode_version_info, place_format_info, place_version_info,
};
use crate::matrix::placement::place_data;
use crate::matrix::mask::{best_mask, apply_mask, MASK_FNS};

#[derive(Debug, Clone)]
pub enum VersionMode {
    Auto,
    Fixed(u8),
}

#[derive(Debug, Clone)]
pub enum ModeHint {
    Auto,
    Numeric,
    Alphanumeric,
    Byte,
    Kanji,
}

#[derive(Debug, Clone)]
pub struct QrConfig {
    pub level: EcLevel,
    pub version: VersionMode,
    pub margin: u8, // 白边模块数
}

impl Default for QrConfig {
    fn default() -> Self {
        QrConfig {
            level: EcLevel::M,
            version: VersionMode::Auto,
            margin: 4,
        }
    }
}

pub struct QrCode {
    pub version: Version,
    pub level: EcLevel,
    pub mask: u8,
    matrix: Matrix,
    margin: u8,
}

impl QrCode {
    /// 编码字符串生成 QR 码
    pub fn encode(text: &str, config: QrConfig) -> Result<Self, String> {
        // 1. 分段
        let segments = segment_text(text);
        if segments.is_empty() {
            return Err("输入为空".into());
        }

        // 2. 确定版本
        let version = match config.version {
            VersionMode::Fixed(v) => Version::new(v).ok_or("无效版本号")?,
            VersionMode::Auto => {
                // 计算总比特数（近似），逐步尝试
                let mut selected = None;
                for v in 1..=40 {
                    let ver = Version(v);
                    let total_bits: u16 = segments.iter()
                        .map(|s| segment_bit_length(s, v))
                        .sum();
                    let cap = get_data_capacity(ver, config.level) as u32 * 8;
                    if cap >= total_bits as u32 {
                        selected = Some(ver);
                        break;
                    }
                }
                selected.ok_or("数据过长，超出 QR 码最大容量")?
            }
        };

        // 3. 构建数据码字
        let data = build_codewords(text, version, config.level);

        // 4. 纠错编码
        let ec_info = version.ec_info(config.level);
        let mut blocks: Vec<Vec<u8>> = Vec::new();
        let mut pos = 0;
        for binfo in &ec_info.blocks {
            for _ in 0..binfo.count {
                let end = pos + binfo.data_codewords as usize;
                blocks.push(data[pos..end].to_vec());
                pos = end;
            }
        }
        let final_data = reed_solomon::interleave(&blocks, ec_info.ec_per_block);

        // 5. 构建矩阵
        let mut matrix = Matrix::new(version.size());
        place_finder_patterns(&mut matrix);
        // 标记保留区域
        mark_reserved(&mut matrix, version);

        place_timing_patterns(&mut matrix);
        place_alignment_patterns(&mut matrix, version.alignment_positions());
        if version.0 >= 2 {
            place_dark_module(&mut matrix, version.0);
        }
        reserve_format_areas(&mut matrix);
        if version.0 >= 7 {
            reserve_version_areas(&mut matrix);
        }

        // 6. 放置数据
        place_data(&mut matrix, &final_data);

        // 7. 掩码评分
        let (best_idx, best_matrix) = best_mask(&matrix);

        // 8. 写入格式信息
        let format = encode_format_info(config.level.indicator_bits(), best_idx);
        place_format_info(&mut best_matrix.clone(), format); // 需要覆盖

        Ok(QrCode {
            version,
            level: config.level,
            mask: best_idx,
            matrix: best_matrix,
            margin: config.margin,
        })
    }

    pub fn modules(&self) -> &[Vec<bool>] {
        &self.matrix.modules
    }

    pub fn size(&self) -> u8 {
        self.matrix.size
    }

    pub fn to_svg(&self) -> String {
        crate::render::svg::render_svg(self)
    }

    pub fn to_ascii(&self, invert: bool) -> String {
        crate::render::ascii::render_ascii(self, invert)
    }

    pub fn to_png_bytes(&self, module_size: u8) -> Vec<u8> {
        crate::render::png::render_png(self, module_size)
    }
}

fn mark_reserved(matrix: &mut Matrix, version: Version) {
    let size = matrix.size;
    // 定位图案
    for &(fx, fy) in &[(0u8, 0u8), (size - 7, 0), (0, size - 7)] {
        for dy in 0..7u8 {
            for dx in 0..7u8 {
                matrix.reserve(fx + dx, fy + dy);
            }
        }
    }
    // 时序线
    for x in 8..size - 8 {
        matrix.reserve(x, 6);
        matrix.reserve(6, x);
    }
    // 对齐图案
    // ... 省略，根据实际需要调用
    // 格式信息区域
    // 版本信息区域
}

注意：mark_reserved 需要完整实现，在具体编码时补齐所有保留区域标记。

Step 2: 实现渲染器

// render/png.rs
use crate::qr::QrCode;
use image::{ImageBuffer, Luma};

pub fn render_png(qr: &QrCode, module_size: u8) -> Vec<u8> {
    let matrix_size = qr.size() as u32;
    let margin = qr.margin as u32;
    let total_size = matrix_size + 2 * margin;
    let img_size = total_size * module_size as u32;

    let mut img = ImageBuffer::new(img_size, img_size);

    for y in 0..total_size {
        for x in 0..total_size {
            let module_x = x.saturating_sub(margin);
            let module_y = y.saturating_sub(margin);

            let is_dark = if module_x < matrix_size && module_y < matrix_size {
                qr.modules()[module_y as usize][module_x as usize]
            } else {
                false // 白边
            };

            let px_val = if is_dark { 0u8 } else { 255u8 };
            for dy in 0..module_size as u32 {
                for dx in 0..module_size as u32 {
                    img.put_pixel(
                        x * module_size as u32 + dx,
                        y * module_size as u32 + dy,
                        Luma([px_val]),
                    );
                }
            }
        }
    }

    let mut buf = Vec::new();
    img.write_to(&mut std::io::Cursor::new(&mut buf), image::ImageFormat::Png)
        .expect("PNG 编码失败");
    buf
}

// render/svg.rs
use crate::qr::QrCode;

pub fn render_svg(qr: &QrCode) -> String {
    let matrix_size = qr.size() as u32;
    let margin = qr.margin as u32;
    let total = matrix_size + 2 * margin;

    let mut svg = String::new();
    svg.push_str(&format!(
        r#"<svg xmlns="http://www.w3.org/2000/svg" width="{}" height="{}" viewBox="0 0 {} {}">"#,
        total, total, total, total
    ));
    svg.push_str(&format!(
        r#"<rect width="{}" height="{}" fill="white"/>"#,
        total, total
    ));

    for y in 0..matrix_size {
        for x in 0..matrix_size {
            if qr.modules()[y as usize][x as usize] {
                svg.push_str(&format!(
                    r#"<rect x="{}" y="{}" width="1" height="1" fill="black"/>"#,
                    x + margin, y + margin
                ));
            }
        }
    }

    svg.push_str("</svg>");
    svg
}

// render/ascii.rs
use crate::qr::QrCode;

pub fn render_ascii(qr: &QrCode, invert: bool) -> String {
    let size = qr.size() as usize;
    let margin = qr.margin as usize;
    let total = size + 2 * margin;

    let dark_char = if invert { "  " } else { "██" };
    let light_char = if invert { "██" } else { "  " };

    let mut result = String::new();
    for y in 0..total {
        for x in 0..total {
            let mx = x.saturating_sub(margin);
            let my = y.saturating_sub(margin);
            let is_dark = if mx < size && my < size {
                qr.modules()[my][mx]
            } else {
                false
            };
            result.push_str(if is_dark { dark_char } else { light_char });
        }
        result.push('\n');
    }
    result
}

Step 3: 提交

git add . && git commit -m "feat: 顶层 API + PNG/SVG/ASCII 渲染器"

Task 11: CLI 工具

Files:

Modify: QRGen/cli/src/main.rs
Step 1: 实现 CLI

// cli/src/main.rs
use clap::Parser;
use qr_core::qr::{QrCode, QrConfig, VersionMode};
use qr_core::version::EcLevel;
use std::path::Path;

#[derive(Parser)]
#[command(name = "qrgen", about = "QR 码生成器")]
struct Args {
    /// 要编码的内容
    content: String,

    /// 输出文件 (.png 或 .svg)，不指定则输出终端 ASCII
    #[arg(short = 'o', long)]
    output: Option<String>,

    /// 纠错级别 [L/M/Q/H]
    #[arg(short = 'l', long, default_value = "M")]
    level: String,

    /// 手动指定版本 (1-40)，不指定则自动
    #[arg(short = 'v', long)]
    version: Option<u8>,

    /// 模块像素大小（仅 PNG）
    #[arg(short = 's', long, default_value = "4")]
    size: u8,

    /// 白边模块数
    #[arg(short = 'm', long, default_value = "4")]
    margin: u8,

    /// 反色
    #[arg(long)]
    invert: bool,
}

fn main() -> anyhow::Result<()> {
    let args = Args::parse();

    let level = match args.level.to_uppercase().as_str() {
        "L" => EcLevel::L,
        "M" => EcLevel::M,
        "Q" => EcLevel::Q,
        "H" => EcLevel::H,
        _ => anyhow::bail!("无效纠错级别: {}。支持 L/M/Q/H", args.level),
    };

    let version = match args.version {
        Some(v) => VersionMode::Fixed(v),
        None => VersionMode::Auto,
    };

    let config = QrConfig {
        level,
        version,
        margin: args.margin,
    };

    let qr = QrCode::encode(&args.content, config)
        .map_err(|e| anyhow::anyhow!("编码失败: {}", e))?;

    match args.output {
        Some(path) => {
            let ext = Path::new(&path)
                .extension()
                .and_then(|e| e.to_str())
                .unwrap_or("")
                .to_lowercase();

            match ext.as_str() {
                "png" => {
                    let bytes = qr.to_png_bytes(args.size);
                    std::fs::write(&path, bytes)?;
                    println!("已生成: {}", path);
                }
                "svg" => {
                    let svg = qr.to_svg();
                    std::fs::write(&path, svg)?;
                    println!("已生成: {}", path);
                }
                _ => anyhow::bail!("不支持的文件格式: .{}。支持 .png / .svg", ext),
            }
        }
        None => {
            // 终端 ASCII 输出
            println!("{}", qr.to_ascii(args.invert));
        }
    }

    Ok(())
}

Step 2: 构建并测试 CLI

cd D:\Code\doing_exercises\programs\QRGen
cargo build
cargo run -p qrgen -- "Hello World"                   # ASCII 输出
cargo run -p qrgen -- "Hello" -o test.png -s 10       # PNG 输出
cargo run -p qrgen -- "Hello" -o test.svg             # SVG 输出

Step 3: 提交

git add . && git commit -m "feat: CLI 工具 (clap + anyhow)"

Task 12: 集成测试 + 端到端验证

Files:

Modify: QRGen/core/Cargo.toml (添加 dev-dependencies)
Create: QRGen/core/tests/integration_test.rs
Step 1: 添加集成测试

在 core/Cargo.toml 中添加：

[dev-dependencies]

// core/tests/integration_test.rs
use qr_core::qr::{QrCode, QrConfig, VersionMode};
use qr_core::version::EcLevel;

#[test]
fn test_encode_simple_text() {
    let config = QrConfig::default();
    let qr = QrCode::encode("HELLO WORLD", config).unwrap();
    assert_eq!(qr.version.0, 1); // 短文本应该是 version 1
    assert_eq!(qr.size(), 21);
}

#[test]
fn test_all_levels() {
    for level in [EcLevel::L, EcLevel::M, EcLevel::Q, EcLevel::H] {
        let config = QrConfig { level, ..Default::default() };
        let qr = QrCode::encode("TEST", config).unwrap();
        assert!(qr.size() >= 21);
    }
}

#[test]
fn test_chinese_text() {
    let config = QrConfig::default();
    let qr = QrCode::encode("你好世界", config).unwrap();
    assert!(qr.size() >= 21);
}

#[test]
fn test_url() {
    let config = QrConfig::default();
    let qr = QrCode::encode("https://example.com/path?q=1", config).unwrap();
    assert!(qr.size() >= 21);
}

#[test]
fn test_numeric_only() {
    let mut config = QrConfig::default();
    config.version = VersionMode::Fixed(1);
    // 纯数字，Version 1 L 级够用
    let qr = QrCode::encode("12345678901234567890", config).unwrap();
    assert_eq!(qr.version.0, 1);
}

#[test]
fn test_fixed_version() {
    let config = QrConfig {
        version: VersionMode::Fixed(5),
        ..Default::default()
    };
    let qr = QrCode::encode("FIXED VERSION TEST", config).unwrap();
    assert_eq!(qr.version.0, 5);
}

#[test]
fn test_empty_input_fails() {
    let config = QrConfig::default();
    let result = QrCode::encode("", config);
    assert!(result.is_err());
}

#[test]
fn test_svg_output_contains_svg_tag() {
    let qr = QrCode::encode("TEST", QrConfig::default()).unwrap();
    let svg = qr.to_svg();
    assert!(svg.contains("<svg"));
    assert!(svg.contains("</svg>"));
}

#[test]
fn test_ascii_output_not_empty() {
    let qr = QrCode::encode("TEST", QrConfig::default()).unwrap();
    let ascii = qr.to_ascii(false);
    assert!(!ascii.is_empty());
    assert!(ascii.contains('\n'));
}

#[test]
fn test_png_output_has_size() {
    let qr = QrCode::encode("TEST", QrConfig::default()).unwrap();
    let png = qr.to_png_bytes(4);
    assert!(!png.is_empty());
    // PNG 文件应以 8 字节签名开头
    assert_eq!(&png[..8], &[137, 80, 78, 71, 13, 10, 26, 10]);
}

Step 2: 运行全部测试

cd D:\Code\doing_exercises\programs\QRGen
cargo test

Step 3: 提交

git add . && git commit -m "test: 集成测试 + 端到端验证"

实现顺序

Task 1  (骨架) ──→ Task 2  (Galois) ──→ Task 4  (RS)
                 ↘                   ↗
                  Task 3  (版本表) ──→ Task 5  (编码) ──→ Task 6  (分段+比特流)
                                                           ↓
Task 7 (矩阵+图案) ←── Task 8 (排列+掩码) ←── Task 9 (格式/版本信息)
        ↓
Task 10 (API+渲染) ──→ Task 11 (CLI) ──→ Task 12 (集成测试)

每个 Task 完成后运行 cargo test 确保不退化。

65 KiB Raw Permalink Blame History Unescape Escape

QR 码生成器 (QRGen) 实现计划

文件清单

Task 1: 搭建 Workspace 骨架

Task 2: GF(2⁸) Galois 域

Task 3: 版本参数表

Task 4: Reed-Solomon 编码器

Task 5: 编码模式实现

Task 6: 数据分段 + 比特流

Task 7: 模块矩阵 + 功能图案

Task 8: 数据排列 + 掩码

Task 9: 格式信息 + 版本信息编码

Task 10: 顶层 API + 渲染器

Task 11: CLI 工具

Task 12: 集成测试 + 端到端验证

实现顺序

65 KiB

Raw Permalink Blame History