Serendipity/QRGen
1
1
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
v2.0
QRGen/docs/superpowers/plans/2026-06-16-qrcode-generator-plan.md
T

2423 lines
65 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
# 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**
```toml
[workspace]
resolver = "2"
members = ["core", "cli"]
[workspace.package]
version = "0.1.0"
edition = "2021"
license = "MIT"
authors = ["刘航宇"]
```
- [ ] **Step 2: 创建 core/Cargo.toml**
```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**
```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`:
```rust
pub mod ecc;
pub mod encoder;
pub mod matrix;
pub mod render;
pub mod version;
pub mod qr;
```
`core/src/ecc/mod.rs`:
```rust
pub mod galois;
pub mod reed_solomon;
```
`core/src/encoder/mod.rs`:
```rust
pub mod mode;
pub mod segment;
pub mod bitstream;
```
`core/src/matrix/mod.rs`:
```rust
pub mod grid;
pub mod patterns;
pub mod placement;
pub mod mask;
```
`core/src/render/mod.rs`:
```rust
pub mod png;
pub mod svg;
pub mod ascii;
```
`cli/src/main.rs`:
```rust
fn main() {
println!("QRGen - 开发中");
}
```
- [ ] **Step 5: 验证编译**
```bash
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 域运算**
```rust
/// 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` 或手工初始化。
修正方案 — 使用函数在首次调用时初始化：
```rust
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` 末尾添加：
```rust
#[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: 运行测试验证**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core ecc::galois
```
Expected: 7 tests pass
- [ ] **Step 4: 提交**
```bash
git add . && git commit -m "feat: GF(2^8) Galois 域运算 + 预计算 exp/log 表"
```
---
### Task 3: 版本参数表
**Files:**
- Create: `QRGen/core/src/version.rs`
- [ ] **Step 1: 实现版本容量表**
```rust
/// 纠错级别
#[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: 添加版本查找测试**
```rust
#[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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core version
```
- [ ] **Step 4: 提交**
```bash
git add . && git commit -m "feat: 版本参数表 + 自动版本选择"
```
---
### Task 4: Reed-Solomon 编码器
**Files:**
- Create: `QRGen/core/src/ecc/reed_solomon.rs`
- [ ] **Step 1: 实现 RS 编码**
```rust
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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core ecc::reed_solomon
```
- [ ] **Step 3: 提交**
```bash
git add . && git commit -m "feat: Reed-Solomon 纠错编码 + 数据交错"
```
---
### Task 5: 编码模式实现
**Files:**
- Create: `QRGen/core/src/encoder/mode.rs`
- [ ] **Step 1: 实现四种编码模式**
```rust
/// 编码模式
#[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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core encoder::mode
```
- [ ] **Step 3: 提交**
```bash
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: 实现数据分段**
```rust
// 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: 实现比特流拼接**
```rust
// 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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core encoder::
```
- [ ] **Step 4: 提交**
```bash
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: 定义矩阵网格**
```rust
// 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: 绘制功能图案**
```rust
// 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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core matrix::patterns
```
- [ ] **Step 4: 提交**
```bash
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: 蛇形数据排列**
```rust
// 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` 中增加：
```rust
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: 实现掩码 + 评分**
```rust
// 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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core matrix::
```
- [ ] **Step 5: 提交**
```bash
git add . && git commit -m "feat: 蛇形数据排列 + 8 种掩码 + 评分"
```
---
### Task 9: 格式信息 + 版本信息编码
**Files:**
- Modify: `QRGen/core/src/matrix/patterns.rs` (追加)
- [ ] **Step 1: 添加格式信息编码**
在 `patterns.rs` 末尾追加：
```rust
/// 格式信息 = 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: 运行测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen && cargo test -p qr-core matrix::
```
- [ ] **Step 3: 提交**
```bash
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**
```rust
// 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: 实现渲染器**
```rust
// 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
}
```
```rust
// 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
}
```
```rust
// 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: 提交**
```bash
git add . && git commit -m "feat: 顶层 API + PNG/SVG/ASCII 渲染器"
```
---
### Task 11: CLI 工具
**Files:**
- Modify: `QRGen/cli/src/main.rs`
- [ ] **Step 1: 实现 CLI**
```rust
// 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**
```bash
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: 提交**
```bash
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` 中添加：
```toml
[dev-dependencies]
```
```rust
// 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: 运行全部测试**
```bash
cd D:\Code\doing_exercises\programs\QRGen
cargo test
```
- [ ] **Step 3: 提交**
```bash
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` 确保不退化。
Reference in New Issue View Git Blame Copy Permalink