坏掉的迷宫。

QR_Code

基本介绍

版本

二维码一共有40个版本,设版本为 V,则该二维码的尺寸为:$((V-1)*4+21)^2$

定位图案

功能性数据

其他

数据编码

在此提到四种,其中的举例基于 Version1 - H

数字编码(Numeric mode)

0-9

每三位数字编码成 10/12/14 bits (根据二维码版本有所不同),剩下的 1/2 位编为 4/7 bits。

字符编码(Alphanumeric mode)

0-9,A-Z, $%*+-./:

每两位字符转成下图中对应进制,再编码为 9/11/13 bits,剩下的 1 位编为 6bits。(SP 指空格)

QR_Code

字节编码(Byte mode)

可以是 0-255 的 ISO-8859-1 字符,或其他如 UTF-8。

双字节编码/(Kanji mode)

日文、中文都可用之。

日文和汉字的编码会减去一个值。如:在0x8140 - 0x9FFC 中的字符会减去 0x8140,在 0xE040 - 0xEBBF中的字符要减去 0xC140。然后把结果前 2 个 bits 乘以 0xC0,再加上后 2 个 bits,最后转成13bits 的编码。如下图示例:

QR_Code

附:格式编号、位数规范

中文的编号是 1101

QR_Code

结束符和补齐码

结束符

在最后加上 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 来举例。

QR_Code

QR_Code

排列好以后,进行穿插放置:

对于数据码,把每个块的第 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

Position_Detection_Pattern

Alignment Pattern (Version 2+)

Alignment_Pattern

关于 Alignment 的位置,可自查。下面是不完全表格:

Alignment-Position

例如:

alignment-example

Timing Pattern

Timing-Pattern

Format Information

图 1 中蓝色部分即为 Format Information ,它是一个 15 bits 的信息,每一个 bit 的位置如下图 2 所示:(注意图中的 Dark Module,那是永远出现的)

这 15 bits 还要 XOR 101010000010010 。这样就保证不会因为我们选用了 00 的纠错级别和 000 的Mask,从而造成全部为白色,这会增加我们的扫描器的图像识别的困难。

Format-Information

Format-Info-bits-postion

下面是一个示例:

Format-Information-Example

Error Correction Level, Mask 编码:format-version-tables

Error-Correction-Indicator-Code

Mask-Pattern-Code

Version Information (Version 7+)

图 1 中蓝色部分即为 Version Information ,它是一个 18 bits 的信息,每一个 bit 的位置如下图 2 所示:

Version-Information

Version-Information-Position

下面是一个示例:

Version-Information-Example

数据和数据纠错码

最终编码的填充方式如下:从右下角开始沿红线填写 bits,1是黑色,0是白色。如果遇到了上面的非数据区,则跳过。

Data-Placement

而 Mask 为了均衡图像,减少识别困难而产生,即和上图的数据区做 XOR 操作。

masking-pattern

举例:

Masking-Examples

例题

BUUOJ - Misc - Beautiful_Side,或者 SECCON 2014 - qr_easy

自(手)动补全工具:qrazybox