二維碼又稱 QR Code，QR 全稱 Quick Response，是一個(gè)近幾年來移動(dòng)設(shè)備上超流行的一種編碼方式，它比傳統(tǒng)的 Bar Code 條形碼能存更多的信息，也能表示更多的數(shù)據(jù)類型：比如：字符，數(shù)字，日文，中文等等。這兩天學(xué)習(xí)了一下二維碼圖片生成的相關(guān)細(xì)節(jié)，覺得這個(gè)玩意就是一個(gè)密碼算法，在此寫一這篇文章 ，揭露一下。供好學(xué)的人一同學(xué)習(xí)之。

　　關(guān)于 QR Code Specification，可參看這個(gè) PDF：http://raidenii.net/files/datasheets/misc/qr_code.pdf 

　　基礎(chǔ)知識

　　首先，我們先說一下二維碼一共有 40 個(gè)尺寸。官方叫版本 Version。Version 1 是 21 x 21 的矩陣，Version 2 是 25 x 25 的矩陣，Version 3 是 29 的尺寸，每增加一個(gè) version，就會(huì)增加 4 的尺寸，公式是：(V-1)*4 + 21（V是版本號） 最高 Version 40，(40-1)*4+21 = 177，所以最高是 177 x 177 的正方形。

　　下面我們看看一個(gè)二維碼的樣例：

　　定位圖案

• Position Detection Pattern 是定位圖案，用于標(biāo)記二維碼的矩形大小。這三個(gè)定位圖案有白邊叫 Separators for Postion Detection Patterns。之所以三個(gè)而不是四個(gè)意思就是三個(gè)就可以標(biāo)識一個(gè)矩形了。
• Timing Patterns 也是用于定位的。原因是二維碼有 40 種尺寸，尺寸過大了后需要有根標(biāo)準(zhǔn)線，不然掃描的時(shí)候可能會(huì)掃歪了。
• Alignment Patterns 只有 Version 2 以上（包括 Version2）的二維碼需要這個(gè)東東，同樣是為了定位用的。

　　功能性數(shù)據(jù)

• Format Information 存在于所有的尺寸中，用于存放一些格式化數(shù)據(jù)的。
• Version Information 在 >= Version 7 以上，需要預(yù)留兩塊 3 x 6 的區(qū)域存放一些版本信息。

　　數(shù)據(jù)碼和糾錯(cuò)碼

• 除了上述的那些地方，剩下的地方存放 Data Code 數(shù)據(jù)碼和 Error Correction Code 糾錯(cuò)碼。

　　數(shù)據(jù)編碼

　　我們先來說說數(shù)據(jù)編碼。QR 碼支持如下的編碼：

　　Numeric mode 數(shù)字編碼，從 0 到9。如果需要編碼的數(shù)字的個(gè)數(shù)不是 3 的倍數(shù)，那么，最后剩下的 1 或 2 位數(shù)會(huì)被轉(zhuǎn)成 4 或 7bits，則其它的每 3 位數(shù)字會(huì)被編成 10，12，14bits，編成多長還要看二維碼的尺寸（下面有一個(gè)表 Table 3 說明了這點(diǎn)）

　　Alphanumeric mode 字符編碼。包括 0-9，大寫的A到Z（沒有小寫），以及符號$ % * + – . / : 包括空格。這些字符會(huì)映射成一個(gè)字符索引表。如下所示：（其中的 SP 是空格，Char 是字符，Value 是其索引值） 編碼的過程是把字符兩兩分組，然后轉(zhuǎn)成下表的 45 進(jìn)制，然后轉(zhuǎn)成 11bits 的二進(jìn)制，如果最后有一個(gè)落單的，那就轉(zhuǎn)成 6bits 的二進(jìn)制。而編碼模式和字符的個(gè)數(shù)需要根據(jù)不同的 Version 尺寸編成9, 11 或 13 個(gè)二進(jìn)制（如下表中 Table 3）

　　Byte mode, 字節(jié)編碼，可以是0-255 的 ISO-8859-1 字符。有些二維碼的掃描器可以自動(dòng)檢測是否是 UTF-8 的編碼。

　　Kanji mode 這是日文編碼，也是雙字節(jié)編碼。同樣，也可以用于中文編碼。日文和漢字的編碼會(huì)減去一個(gè)值。如：在 0X8140 to 0X9FFC 中的字符會(huì)減去 8140，在 0XE040 到 0XEBBF 中的字符要減去 0XC140，然后把前兩位拿出來乘以 0XC0，然后再加上后兩位，最后轉(zhuǎn)成 13bit 的編碼。如下圖示例：

　　Extended Channel Interpretation (ECI) mode 主要用于特殊的字符集。并不是所有的掃描器都支持這種編碼。

　　Structured Append mode 用于混合編碼，也就是說，這個(gè)二維碼中包含了多種編碼格式。

　　FNC1 mode 這種編碼方式主要是給一些特殊的工業(yè)或行業(yè)用的。比如 GS1 條形碼之類的。

　　簡單起見，后面三種不會(huì)在本文中討論。

　　下面兩張表中，

• Table 2 是各個(gè)編碼格式的“編號”，這個(gè)東西要寫在 Format Information 中。注：中文是 1101
• Table 3 表示了，不同版本（尺寸）的二維碼，對于，數(shù)字，字符，字節(jié)和 Kanji 模式下，對于單個(gè)編碼的 2 進(jìn)制的位數(shù)。（在二維碼的規(guī)格說明書中，有各種各樣的編碼規(guī)范表，后面還會(huì)提到）

　　下面我們看幾個(gè)示例，

　　示例一：數(shù)字編碼

　　在 Version 1 的尺寸下，糾錯(cuò)級別為H的情況下，編碼： 01234567

　　1. 把上述數(shù)字分成三組: 012 345 67

　　2. 把他們轉(zhuǎn)成二進(jìn)制:  012 轉(zhuǎn)成 0000001100；  345 轉(zhuǎn)成 0101011001；  67 轉(zhuǎn)成 1000011。

　　3. 把這三個(gè)二進(jìn)制串起來: 0000001100 0101011001 1000011

　　4. 把數(shù)字的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (version 1-H 是 10 bits ): 8 個(gè)數(shù)字的二進(jìn)制是 0000001000

　　5. 把數(shù)字編碼的標(biāo)志 0001 和第 4 步的編碼加到前面:  0001 0000001000 0000001100 0101011001 1000011

　　示例二：字符編碼

　　在 Version 1 的尺寸下，糾錯(cuò)級別為H的情況下，編碼: AC-42

　　1. 從字符索引表中找到 AC-42 這五個(gè)字條的索引 (10,12,41,4,2)

　　2. 兩兩分組: (10,12) (41,4) (2)

　　3. 把每一組轉(zhuǎn)成 11bits 的二進(jìn)制:

　　(10,12) 10*45+12 等于 462 轉(zhuǎn)成 00111001110

　　(41,4) 41*45+4 等于 1849 轉(zhuǎn)成 11100111001

　　(2) 等于 2 轉(zhuǎn)成 000010

　　4. 把這些二進(jìn)制連接起來：00111001110 11100111001 000010

　　5. 把字符的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (Version 1-H 為 9 bits ): 5 個(gè)字符，5 轉(zhuǎn)成 000000101

　　6. 在頭上加上編碼標(biāo)識 0010 和第 5 步的個(gè)數(shù)編碼:  0010 000000101 00111001110 11100111001 000010

　　結(jié)束符和補(bǔ)齊符

　　假如我們有個(gè) HELLO WORLD 的字符串要編碼，根據(jù)上面的示例二，我們可以得到下面的編碼，

　　注：二維碼的糾錯(cuò)碼主要是通過 Reed-Solomon error correction（里德-所羅門糾錯(cuò)算法）來實(shí)現(xiàn)的。對于這個(gè)算法，對于我來說是相當(dāng)?shù)膹?fù)雜，里面有很多的數(shù)學(xué)計(jì)算，比如：多項(xiàng)式除法，把1-255 的數(shù)映射成 2 的n次方（0<=n<=255）的伽羅瓦域 Galois Field 之類的神一樣的東西，以及基于這些基礎(chǔ)的糾錯(cuò)數(shù)學(xué)公式，因?yàn)槲业臄?shù)據(jù)基礎(chǔ)差，對于我來說太過復(fù)雜，所以我一時(shí)半會(huì)兒還有點(diǎn)沒搞明白，還在學(xué)習(xí)中，所以，我在這里就不展開說這些東西了。還請大家見諒了。（當(dāng)然，如果有朋友很明白，也繁請教教我）

　　最終編碼

　　穿插放置

　　如果你以為我們可以開始畫圖，你就錯(cuò)了。二維碼的混亂技術(shù)還沒有玩完，它還要把數(shù)據(jù)碼和糾錯(cuò)碼的各個(gè) codewords 交替放在一起。如何交替呢，規(guī)則如下：

　　對于數(shù)據(jù)碼：把每個(gè)塊的第一個(gè) codewords 先拿出來按順度排列好，然后再取第一塊的第二個(gè)，如此類推。如：上述示例中的 Data Codewords 如下：

塊 1	67	85	70	134	87	38	85	194	119	50	6	18	6	103	38
塊 2	246	246	66	7	118	134	242	7	38	86	22	198	199	146	6
塊 3	182	230	247	119	50	7	118	134	87	38	82	6	134	151	50	7
塊 4	70	247	118	86	194	6	151	50	16	236	17	236	17	236	17	236

　　我們先取第一列的：67， 246， 182， 70

　　然后再取第二列的：67， 246， 182， 70， 85，246，230 ，247

　　如此類推：67， 246， 182， 70， 85，246，230 ，247 ………  ……… ，38，6，50，17，7，236

　　對于糾錯(cuò)碼，也是一樣：

塊 1	213	199	11	45	115	247	241	223	229	248	154	117	154	111	86	161	111	39
塊 2	87	204	96	60	202	182	124	157	200	134	27	129	209	17	163	163	120	133
塊 3	148	116	177	212	76	133	75	242	238	76	195	230	189	10	108	240	192	141
塊 4	235	159	5	173	24	147	59	33	106	40	255	172	82	2	131	32	178	236

　　和數(shù)據(jù)碼取的一樣，得到：213，87，148，235，199，204，116，159，…… …… 39，133，141，236

　　然后，再把這兩組放在一起（糾錯(cuò)碼放在數(shù)據(jù)碼之后）得到：

　　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

　　Remainder Bits

　　最后再加上 Reminder Bits，對于某些 Version 的 QR，上面的還不夠長度，還要加上 Remainder Bits，比如：上述的 5Q 版的二維碼，還要加上 7 個(gè) bits，Remainder Bits 加零就好了。關(guān)于哪些 Version 需要多少個(gè) Remainder bit，可以參看 QR Code Spec 的第 15 頁的 Table-1 的定義表。

　　畫二維碼圖

　　Position Detection Pattern

　　首先，先把 Position Detection 圖案畫在三個(gè)角上。

　　Alignment Pattern

　　然后，再把 Alignment 圖案畫上

　　關(guān)于 Alignment 的位置，可以查看 QR Code Spec 的第 81 頁的 Table-E.1 的定義表（下表是不完全表格）

　　下圖是根據(jù)上述表格中的 Version8 的一個(gè)例子（6，24，42）

　　Timing Pattern

　　接下來是 Timing Pattern 的線（這個(gè)不用多說了）

　　Format Information

　　再接下來是 Formation Information，下圖中的藍(lán)色部分。

　　Format Information 是一個(gè) 15 個(gè) bits 的信息，每一個(gè) bit 的位置如下圖所示：（注意圖中的 Dark Module，那是永遠(yuǎn)出現(xiàn)的）

　　這 15 個(gè) bits 中包括：

• 5 個(gè)數(shù)據(jù) bits：其中，2 個(gè) bits 用于表示使用什么樣的 Error Correction Level， 3 個(gè) bits 表示使用什么樣的 Mask
• 10 個(gè)糾錯(cuò) bits。主要通過 BCH Code 來計(jì)算

　　然后 15 個(gè) bits 還要與 101010000010010 做 XOR 操作。這樣就保證不會(huì)因?yàn)槲覀冞x用了 00 的糾錯(cuò)級別，以及 000 的 Mask，從重造成全部為白色，這會(huì)增加我們的掃描器的圖像識別的困難。

　　下面是一個(gè)示例：

　　關(guān)于 Error Correction Level 如下表所示：

　　關(guān)于 Mask 圖案如后面的 Table 23 所示。

　　Version Information

　　再接下來是 Version Information（版本 7 以后需要這個(gè)編碼），下圖中的藍(lán)色部分。

　　Version Information 一共是 18 個(gè) bits，其中包括 6 個(gè) bits 的版本號以及 12 個(gè) bits 的糾錯(cuò)碼，下面是一個(gè)示例：

　　而其填充位置如下：

　　數(shù)據(jù)和數(shù)據(jù)糾錯(cuò)碼

　　然后是填接我們的最終編碼，最終編碼的填充方式如下：從左下角開始沿著紅線填我們的各個(gè) bits，1 是黑色，0 是白色。如果遇到了上面的非數(shù)據(jù)區(qū)，則繞開或跳過。

　　掩碼圖案

　　這樣下來，我們的圖就填好了，但是，也許那些點(diǎn)并不均衡，所以，我們還要做 Masking 操作（靠，還嫌不復(fù)雜）QR 的 Spec 中說了，QR 有 8 個(gè) Mask 你可以使用，如下所示：其中，各個(gè) mask 的公式在各個(gè)圖下面。所謂 mask，說白了，就是和上面生成的圖做 XOR 操作。Mask 只會(huì)和數(shù)據(jù)區(qū)進(jìn)行 XOR，不會(huì)影響功能區(qū)。

　　其 Mask 的標(biāo)識碼如下所示：（其中的i,j分別對應(yīng)于上圖的x，y）

　　下面是 Mask 后的一些樣子，我們可以看到被某些 Mask XOR 了的數(shù)據(jù)變得比較零散了。

　　Mask 過后的二維碼就成最終的圖了。

　　好了，大家可以去嘗試去寫一下 QR 的編碼程序，當(dāng)然，你可以用網(wǎng)上找個(gè) Reed Soloman 的糾錯(cuò)算法的庫，或是看看別人的源代碼是怎么實(shí)現(xiàn)這個(gè)繁鎖的編碼。

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。