如何画出一个二维码?
只知道一半二维码,如何还原其中的信息?
本文将对二维码的各个部分进行详细介绍。
坏掉的迷宫。
基本介绍
版本
二维码一共有40个版本,设版本为 V,则该二维码的尺寸为:$((V-1)*4+21)^2$
定位图案
-
Position Detection Pattern (标记二维码矩形大小)
-
Timing Patterns (扫描标准线)
-
Alignment Pattern (Version 2+)
功能性数据
-
Format Information (存放格式化数据)
-
Version Information (Version 7+): 预留2块3 x 6的区域存放版本信息
其他
-
Data Code (数据码)
-
Error Correction Code (纠错码)
数据编码
在此提到四种,其中的举例基于 Version1 - H
数字编码(Numeric mode)
0-9
每三位数字编码成 10/12/14 bits (根据二维码版本有所不同),剩下的 1/2 位编为 4/7 bits。
-
举例:01234567
-
分组:012 345 67
-
转码:0000001100 0101011001 1000011
-
将数字总数转为二进制: 8 -> 0000001000
-
将数字编码的标志 0001 和数字总数加到前面:
0001 0000001000 0000001100 0101011001 1000011
-
字符编码(Alphanumeric mode)
0-9,A-Z, $%*+-./:
每两位字符转成下图中对应进制,再编码为 9/11/13 bits,剩下的 1 位编为 6bits。(SP 指空格)
- 举例:AC-42
- (10,12) (41,4) (2)
- 10*45+12->00111001110 41*45+4->11100111001 2->000010
- 同上
- 同上:0010 000000101 00111001110 11100111001 000010
字节编码(Byte mode)
可以是 0-255 的 ISO-8859-1 字符,或其他如 UTF-8。
双字节编码/(Kanji mode)
日文、中文都可用之。
日文和汉字的编码会减去一个值。如:在0x8140 - 0x9FFC 中的字符会减去 0x8140,在 0xE040 - 0xEBBF中的字符要减去 0xC140。然后把结果前 2 个 bits 乘以 0xC0,再加上后 2 个 bits,最后转成13bits 的编码。如下图示例:
附:格式编号、位数规范
中文的编号是 1101
结束符和补齐码
结束符
在最后加上 0000。然后添 0 至 8n bits,按每 8 bits 分组,命名为 codeword
补齐码
若仍未达到最大 bits 数限制,重复这 2 个 bytes: 11101100 00010001
纠错码
实现方式
里德-所罗门纠错算法
Wiki: Reed-Solomon error correction or here(Chinese)
纠错级别
L水平 | 7%的字码可被修正 |
---|---|
M水平 | 15%的字码可被修正 |
Q水平 | 25%的字码可被修正 |
H水平 | 30%的字码可被修正 |
分组编码方式
不同 Version 与 纠错级别 的表格参见 Error_crrection_table,这里拿 Version 5 + Q 来举例。
排列好以后,进行穿插放置:
对于数据码,把每个块的第 1 个 codewords 按顺序排列好,以此类推。以下是部分举例:
块 1 | 67 | 85 | 70 | 134 | 87 | 38 | 85 |
---|---|---|---|---|---|---|---|
块 2 | 246 | 246 | 66 | 7 | 118 | 134 | 242 |
块 3 | 182 | 230 | 247 | 119 | 50 | 7 | 118 |
块 4 | 70 | 247 | 118 | 86 | 194 | 6 | 151 |
对于纠错码也一样。
然后,再把这两组放在一起(纠错码放在数据码之后)得到:
67, 246, 182, 70, 85, 246, 230, 247, 70, 66, 247, 118, 134, 7, 119, 86, 87, 118, 50, 194, 38, 134, 7, 6, 85, 242, 118, 151, 194, 7, 134, 50, 119, 38, 87, 16, 50, 86, 38, 236, 6, 22, 82, 17, 18, 198, 6, 236, 6, 199, 134, 17, 103, 146, 151, 236, 38, 6, 50, 17, 7, 236, 213, 87, 148, 235, 199, 204, 116, 159, 11, 96, 177, 5, 45, 60, 212, 173, 115, 202, 76, 24, 247, 182, 133, 147, 241, 124, 75, 59, 223, 157, 242, 33, 229, 200, 238, 106, 248, 134, 76, 40, 154, 27, 195, 255, 117, 129, 230, 172, 154, 209, 189, 82, 111, 17, 10, 2, 86, 163, 108, 131, 161, 163, 240, 32, 111, 120, 192, 178, 39, 133, 141, 236
这就是数据区。
对于某些Version,不够长度时最后再加上 Remainder Bits,加 0 即可。
画图
Position Detection Pattern
Alignment Pattern (Version 2+)
关于 Alignment 的位置,可自查。下面是不完全表格:
例如:
Timing Pattern
Format Information
图 1 中蓝色部分即为 Format Information ,它是一个 15 bits 的信息,每一个 bit 的位置如下图 2 所示:(注意图中的 Dark Module,那是永远出现的)
- 5 Data bits: 2 bits for Error Correction Level, 3 bits for Mask
- 10 BCH bits
这 15 bits 还要 XOR 101010000010010 。这样就保证不会因为我们选用了 00 的纠错级别和 000 的Mask,从而造成全部为白色,这会增加我们的扫描器的图像识别的困难。
下面是一个示例:
Error Correction Level, Mask 编码:format-version-tables
Version Information (Version 7+)
图 1 中蓝色部分即为 Version Information ,它是一个 18 bits 的信息,每一个 bit 的位置如下图 2 所示:
- 6 Version bits
- 12 BCH bits
下面是一个示例:
数据和数据纠错码
最终编码的填充方式如下:从右下角开始沿红线填写 bits,1是黑色,0是白色。如果遇到了上面的非数据区,则跳过。
而 Mask 为了均衡图像,减少识别困难而产生,即和上图的数据区做 XOR 操作。
举例:
例题
BUUOJ - Misc - Beautiful_Side,或者 SECCON 2014 - qr_easy
自(手)动补全工具:qrazybox