C语言从零实现二维码生成算法：编码、纠错与掩码全解析

简介二维码生成算法堪称 C/C 开发者的实用学习案例完整演示从输入字符串到输出二维码样式的全过程先识别编码模式再按长度选择合适版本将数据转换为二进制位流并通过多项式生成纠错码随后把数据与纠错码按规则排布拼接定位、时序和格式信息。资源共 8 个文件以 2 个 cpp 与 1 个 h 源码为主体附带 Visual Studio 解决方案 sln、vcxproj、filters 等工程配置文件另含 exe 可执行程序便于直接查看命令行输出效果压缩包仅 41KB。整个工程结构紧凑、代码模块划分清晰既有 QRcode 库实现也有 main 调用演示。目前已吸引 4489 人学习下载适合希望从算法底层理解二维码机制并基于 C/C 进行二次开发和功能扩展的入门至中级读者。1. 二维码生成算法为什么值得从 C/C 源码自己写扫码识别工具遍地都是但把一段字符串变成能扫的二维码是另一条技术线。生成器要依次处理编码、Reed-Solomon 纠错、矩阵布局和掩码一步出错成品要么扫不出来要么容错大幅下降。用 C 语言从零实现 QRcode 生成算法收益不只是省一个库的依赖嵌入式设备、离线内网、需要把二维码画进自有渲染管线的 C 项目都适合保留一份自包含源码。下面按规范把生成算法拆成可编译、可调试的 C 代码给出容量表、关键函数和参数口径。适合想把原理彻底吃透的 C/C 开发者也适合准备 c面试时把「二维码怎么生成」当设计题来回答的人平时只调现成库的话理解这些步骤也能帮你判断 API 参数该怎么设。2. 先算数据二维码从字符到 bit 流的 C 语言编码2.1 先按容量表定版本二维码矩阵要做多大任何生成算法的第一步都是选 version。version 1 是 21×21 模块每升一版边长加 4即 size 17 4×version。版本决定数据容量容量又取决于纠错级别所以「选版本」本质是在数据长度和容错之间取折中。下表是 byte 模式下各版本能容纳的字符数已计入模式指示符与长度域开销版本模块数L(7%)M(15%)Q(25%)H(30%)121×211714117225×2532262014329×2953423224433×3378624634537×37106846044641×411341067458745×451541228664849×4919215210884953×53230180130981057×57271213151119我一般先按内容长度和纠错级别查最小版本再留 10% 余量。比如 URL 场景固定走 byte 模式25 个字符选 version 2-M二维码要印在瓶盖这类曲面上就提到 Q 级户外标牌直接 H 级代价是同样内容要升两三个版本。numeric 模式的容量约为 byte 的 3 倍alphanumeric 约 2 倍所以长数字串一定要自动选 numeric而不是按 ASCII 逐字节编码。2.2 二维码的三种编码模式mode indicator 与 put_bits二维码默认三种常用模式numeric0-9、alphanumeric0-9、A-Z、空格及 $%*-./: 共 45 个字符、byte按 ISO-8859-1 解释中文等非 ASCII 实际按 UTF-8 写入。每种模式在 bit 流里先写 4 bit 模式指示符再写长度域最后写数据。长度域宽度随版本分组version 1-9 的 byte 模式是 8 bitnumeric 是 10 bitversion 10-26 分别换成 16 和 12 bit编码前要先查这张小表。所有编码都建立在同一个 bit 写入器上字节序错误会直接导致整张码失效typedef struct { uint8_t *bytes; /* 输出缓冲区bit 流按字节存储 */ int bits; /* 已写入的 bit 数 */ } qr_bits; static void put_bits(qr_bits *b, uint32_t val, int n) { while (n--) { if (b-bits % 8 0) b-bytes[b-bits / 8] 0; /* 新字节先清零 */ if (val (1u n)) b-bytes[b-bits / 8] | (0x80 (b-bits % 8)); b-bits; } }put_bits 从 val 的最高位开始写目标字节也从最高位填与规范里 bit 流的书写顺序一致方便逐 bit 对照文档调试。n 最大用到 16所以 uint32_t 足够。调用前要按「字符数 × 该模式最大 bit 开销 16」预分配缓冲区这是 c语言内存管理里最容易翻车的地方堆上建议直接 calloc省得 memset。numeric 编码把数字每 3 位一组转成 10 bit余 2 位转 7 bit余 1 位转 4 bitstatic void encode_numeric(qr_bits *b, const char *s, int len) { int i 0; put_bits(b, 0x1, 4); /* 模式指示符 0001 */ put_bits(b, (uint32_t)len, 10); /* 长度域version 1-9 用 10 bit */ for (; i 3 len; i 3) { int v (s[i] - 0) * 100 (s[i1] - 0) * 10 (s[i2] - 0); put_bits(b, (uint32_t)v, 10); /* 每 3 位十进制数打包成 10 bit */ } if (len - i 2) put_bits(b, (uint32_t)((s[i] - 0) * 10 s[i1] - 0), 7); else if (len - i 1) put_bits(b, (uint32_t)(s[i] - 0), 4); }压缩率来自「最大 999 的十进制数刚好塞进 10 bit」。alphanumeric 模式先把每个字符映射成 0-44 的编号0 对应 0A 对应 10: 对应 44每两个字符一组按 c1×45c2 转 11 bit单个字符转 6 bit。byte 模式最直接逐字节写 8 bit处理中文时必须先把字符串按 UTF-8 转成字节再逐字节写不能直接写 wchar_t 的内存表示。2.3 填满数据码字terminator、对齐与填充字节数据段写完要追加最多 4 bit 的 0000 终止符再补 0 对齐到字节边界然后用交替的 0xEC、0x11 填充到该版本和纠错级别要求的总码字数。填充是规范强制的顺序也是强制的先 0xEC 再 0x11不能只补 0。这一步做错的典型现象是生成的图偶尔能扫、偶尔不能因为码字总数对不上时后面的纠错分块整体偏移。得到完整数据码字序列后按规范表拆成若干块每块独立计算 Reed-Solomon 纠错码最后按块交织输出。交织把突发错误分散到不同块是二维码抗局部污损的关键设计。比如 version 5-M 拆成 2 块每块 43 个数据码字加 24 个纠错码字交织后输出 2×67134 个码字。分块参数我习惯内联成常量表用 version 和纠错级别做下标不要在运行时推公式推错一个边界整张图就废。注意封装顺序是「先数据后纠错、按块交替」不是整段数据接整段纠错。解码器对交织顺序是强校验的这里错位会整张识别失败。3. 二维码纠错码GF(256) 与 Reed-Solomon 的 C 实现3.1 先建 GF(256) 查表0x11D 本原多项式是硬参数纠错码的本质是多项式除法余式数据码字作为 GF(256) 上多项式的系数除以生成多项式 g(x)余数就是纠错码字。GF(256) 是 8 bit 有限域加法是异或乘法要模一个本原多项式。二维码规范固定用 x^8x^4x^3x^21即 0x11D这是和所有扫码器对齐的硬参数换成别的多项式生成的纠错码全部不兼容。static uint8_t gf_exp[512], gf_log[256]; static void gf_init(void) { int x 1; for (int i 0; i 255; i) { gf_exp[i] (uint8_t)x; gf_log[x] (uint8_t)i; x 1; if (x 0x100) x ^ 0x11D; /* 溢出则模 x^8x^4x^3x^21 */ } for (int i 255; i 512; i) gf_exp[i] gf_exp[i - 255]; /* 指数周期 255翻倍避免查表取模 */ } static int gf_mul(int a, int b) { if (a 0 || b 0) return 0; return gf_exp[gf_log[a] gf_log[b]]; }gf_init 只跑一次之后所有乘法都是查表。gf_exp 开 512 的长度让指数相加后直接越界取到周期内的值省一次取模运算这在嵌入式平台上收益明显。注意 gf_log 以小端方式把「值」映射成「指数」和 gf_exp 互为逆关系查表前必须确认两个参数都不是 0否则表里没有定义。3.2 生成多项式与除法求余构建去首项系数的 divisor生成多项式是 (x-α^0)(x-α^1)...(x-α^(n-1)) 的展开n 是纠错码字数。α 就是 gf_exp[1]2。迭代展开时利用 GF(2) 上减等于加的性质全程无借位#define MAX_DEG 255 /* 生成 monic 多项式 g(x)系数按升幂存放g[degree]1 */ static void rs_gen_poly(int degree, uint8_t g[MAX_DEG 1]) { memset(g, 0, (size_t)degree 1); g[0] 1; /* 初始多项式为常数 1 */ for (int i 0; i degree; i) { int m i; /* 当前最高次数 */ g[m 1] g[m]; /* 最高次项透传保证首项系数为 1 */ for (int j m; j 0; j--) g[j] (uint8_t)(g[j] ^ gf_mul(g[j - 1], gf_exp[i])); g[0] (uint8_t)gf_mul(g[0], gf_exp[i]); } } /* 求 data 除以 g(x) 的余式g 只传去掉首项 1 的 degree 个系数 */ static void rs_remainder(const uint8_t *msg, int mlen, const uint8_t *g, int degree, uint8_t *rem) { memset(rem, 0, (size_t)degree); for (int i 0; i mlen; i) { uint8_t f (uint8_t)(msg[i] ^ rem[0]); memmove(rem, rem 1, (size_t)degree - 1); rem[degree - 1] 0; for (int j 0; j degree; j) rem[j] (uint8_t)(rem[j] ^ gf_mul(g[j], f)); } }rs_gen_poly 每乘一个新因子 (x-α^i)系数从高位到低位就地更新因为生成多项式首项系数是 1除法竖式里最高次那一步等效于直接移位所以 rs_remainder 只需要 degree 个非首项系数参与异或。rem 数组每次调用前必须清零连续处理多个块时残留上一次余数是高频 bug。degree 对应纠错码字数version 5-M 每块 24 个纠错码字degree 就是 24。3.3 纠错级别与分块表L/M/Q/H 怎么配合纠错级别和分块参数是配套的。级别越高每块纠错码字越多能容忍的损伤越大但能装的数据越少纠错级别可恢复码字比例典型场景L约 7%打印质量稳定、屏幕截图M约 15%一般单据、标签纸Q约 25%小面积、曲面、可能污损H约 30%户外标牌、长期磨损环境同一版本下选 H 级容量会明显缩水比如 version 5 在 L 级能放 106 字节H 级只有 44 字节。付款二维码这类高频扫描场景通常选 M 或 Q在码元尺寸和容错之间取平衡。我习惯把分块表内联成static const uint16_t rs_block_tab[40][4]每项存数据码字数、块数、每块码字数、每块纠错码字数用 version 和纠错级别做下标这样求余、交织、掩码三段代码互相独立可以单独写测试用例验证。4. 把二维码画到矩阵布局、zigzag 填充与掩码4.1 定位图案与功能图形二维码矩阵的「地基」矩阵初始化为全白后第一步铺功能图形。三个角的定位图案是 7×7 同心方块扫码器靠它确定方向和旋转对齐图案是 5×5 同心方块version 2 以上分布在矩阵内部时序图案是第 6 行和第 6 列的黑白交替线。这些位置由规范硬性规定数据填充必须绕开typedef struct { int size; /* 边长 17 4*version */ uint8_t m[64][64]; /* 0 白 1 黑支持到 version 11 */ } qr_ctx; static int is_function(const qr_ctx *q, int i, int j) { if (i 9 j 9) return 1; /* 左上定位图案 */ if (i 9 j q-size - 8) return 1; /* 右上定位图案 */ if (i q-size - 8 j 9) return 1; /* 左下定位图案 */ if (i 6 || j 6) return 1; /* 时序图案行列 */ if (i 8 || j 8) return 1; /* 格式信息区域 */ /* version 7 以上的版本信息块、各对齐图案位置需另加判断 */ return 0; }is_function 返回 1 的模块在数据填充和掩码阶段一律跳过。用「前 9 行前 9 列」圈定位区域是工程上的常见近似完整实现要逐点校验 7×7 图案与间隔模块同时把格式信息占用的第 8 行、第 8 列标成功能模块。漏掉任何一块数据就会盖住功能图形扫码器直接无法定位。4.2 zigzag 填充从右下角绕开功能图形的路径数据码字按两列一组、从右下角向上蛇形填充遇到功能模块就跳过static void place_data(qr_ctx *q, const uint8_t *data, int len) { int upward 1; int i q-size - 1, j q-size - 1; int bit 0; while (j 0) { if (j 6) j--; /* 跳过时序列 */ for (int k 0; k 2; k, j--) { if (!is_function(q, i, j) bit len * 8) { q-m[i][j] (uint8_t)((data[bit / 8] (7 - bit % 8)) 1); bit; } } i upward ? -1 : 1; /* 纵向移动一格 */ if (i 0) { /* 到达上边界换向 */ upward 0; i 1; j - 2; /* 再往左挪一列 */ if (j 6) j--; } else if (i q-size) { /* 到达下边界换向 */ upward 1; i q-size - 2; j - 2; if (j 6) j--; } } }循环退出条件是 j 0因为最左侧两列填完矩阵就满了。i 到边界后要「回退一格再换列」否则下一列会从错误的行开始。bit 取用顺序是 MSB first与 put_bits 写入方向一致这里写反整张图数据全错位。数据长度 len 对应(数据码字数纠错码字数)剩余没填到的模块保持白规范里叫 remainder bits空着即可。4.3 掩码与格式信息8 个候选里挑惩罚分最低的数据填完的矩阵往往有大片同色区域直接输出会让扫码器误判。规范定义 8 个掩码模式按坐标 (i,j) 判断该模块是否取反static int mask_bit(int mask, int i, int j) { switch (mask) { case 0: return (i j) % 2 0; case 1: return i % 2 0; case 2: return j % 3 0; case 3: return (i j) % 3 0; case 4: return (i / 2 j / 3) % 2 0; case 5: return (i * j) % 2 (i * j) % 3 0; case 6: return ((i * j) % 2 (i * j) % 3) % 2 0; case 7: return ((i j) % 2 (i * j) % 3) % 2 0; } return 0; }掩码条件成立时数据模块取反。8 个模式全部试一遍每张矩阵算惩罚分选最低的作为最终掩码。惩罚分有四条规则按顺序检查规则检查内容罚分N1横向或纵向连续 ≥5 个同色模块3 超出数量N2出现 2×2 同色块每块 3 分N3出现 1011101 特征两侧各带 4 个浅色每个 40 分N4深色模块占比偏离 50%每 5% 记 10 分掩码编号和纠错级别要写进格式信息格式信息用 BCH(15,5) 编码成 15 bit再异或固定掩码 0x5412static uint16_t fmt_bch(int ec_bits, int mask) { int data (ec_bits 3) | mask; /* 5 bit2 位级别 3 位掩码 */ uint16_t v (uint16_t)(data 10); for (int i 14; i 10; i--) if (v (1 i)) v ^ (uint16_t)(0x537 (i - 10)); return (uint16_t)(((uint16_t)data 10) | v) ^ 0x5412; }ec_bits 的映射和直觉相反L01、M00、Q11、H10不要按 0、1、2、3 直接填。BCH(15,5) 的生成多项式是 0x537循环从 bit 14 往 bit 10 除余数落进低 10 位最后异或 0x5412。格式信息要放两份在定位图案旁保证任何一个角缺损时另一份还能被读出。version 7 以上还需在右上、左下各写一份 18 bit 版本信息用 BCH(18,6)、生成多项式 0x1F25这两块区域在 is_function 里也要标注为功能模块。5. 二维码生成后的验证闭环命令行解码与三个高频坑5.1 用本地解码器做回归zbarimg 一条命令生成器写完不要只看图先跑命令行验证。常见做法是让生成器输出 PBM 位图再交给本地解码器解码./qrgen https://example.com -o qr.pbm convert qr.pbm qr.png zbarimg qr.pngzbarimg 能原样解出字符串说明整条链路通了。vscode配置c/c环境后可以在 put_bits 入口下断点逐字节核对 bit 流内容和规范附录里的示例数据比对。测试内容至少三组纯数字串触发 numeric、带符号的 URL触发 alphanumeric、中文文本必须 byte 模式按 UTF-8 写入。每一组都对应不同的编码分支漏测哪支那一支的 bug 就可能一直躺着。5.2 三个高频坑与排查入口第一个是版本容量溢出数据长度超过该版本容量时编码阶段就要报错不要在填充阶段才暴露。写一个 capacity 检查函数在编码入口调用报错信息带上「所需最小版本号」。第二个是交织顺序错误症状是生成的码偶尔能扫、偶尔不能用规范附录的码字顺序表逐字节比对重点看分块边界和块间交替的位置。第三个是格式信息 BCH 算错或 ec_bits 映射错症状是多数扫码器能扫、个别严格实现的扫不出因为格式信息校验失败会导致整个解码流程直接中止用 fmt_bch 的 32 个输出值做成静态表比每次都现算更不容易错还能在调试时直接按 (ec_bits, mask) 查表对照。5.3 quiet zone 与渲染 scale 是最后两个参数算法输出的是「单位格」矩阵渲染层至少留 4 模块宽的静区quiet zone白边不足是扫码失败的常见原因。缩放倍数 scale 必须保证每个模块是整数像素不要用非整数倍插值否则模块边界模糊、窄条图案粘连。我给渲染层留两个配置项scale 与 quiet_zonequiet_zone 默认 4scale 提供 4 到 8 可调。小尺寸贴纸用 scale4屏幕展示用 6-8把 scale 从 4 调到 8 各生成一版隔 30cm 用手机或 chrome 的扫码功能实测对比哪个倍数在目标环境下识别最快就把哪个值固化进渲染配置而不是回头改算法层的任何参数。本文还有配套的精品资源点击获取