有些時候二維碼被嚴(yán)重破壞導(dǎo)致無法掃描，促使我去學(xué)習(xí)了一波關(guān)于二維碼的知識。二維碼一共有40個尺寸。V 1是21 x 21的矩陣，V2是 25 x 25的矩陣，V3是29的尺寸，每增加一個等級，就會增加4的尺寸，公式是：(V-1)*4 + 21 最高V 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。
二維碼格式示例如下：
定位圖案
定位圖案，就是每個二維碼都有的左上、左下和右上三個角的“回”字形的標(biāo)志。用于標(biāo)記二維碼的矩形大小他的尺寸都是7*7的模塊。
功能性數(shù)據(jù)：存在于所有的尺寸中，用于存放一些格式化數(shù)據(jù)的，主要內(nèi)容為“糾錯碼等級（3bit）+掩碼類別（2bit）+BCH code(10bit,用于糾錯)”，然后這15個bits還要與101010000010010做XOR操作，主要是為了如果選用了00的糾錯級別和000的Mask，從而造成全部為白色，這會增加掃描器的圖像識別的困難。比如：
而這15個bit在format information區(qū)域內(nèi)的分布如下：
在 Version 7以上，需要預(yù)留兩塊3 x 6的區(qū)域存放一些版本信息。
數(shù)據(jù)碼和糾錯碼
除了上述的那些地方，剩下的地方存放 數(shù)據(jù)碼 和糾錯碼。就是最前面兩張圖的深灰色區(qū)域，一般數(shù)據(jù)都是從右下角開始填充，先填充數(shù)據(jù)碼，數(shù)據(jù)碼填充完畢之后再填充糾錯碼，以v1為例，數(shù)據(jù)的填充順序，是這樣的：
數(shù)據(jù)編碼
QR碼支持如下的編碼：
數(shù)字編碼：從0到9；
字符編碼：包括 0-9，大寫的A到Z（沒有小寫），以及符號$ % * + – . / : 包括空格；
字節(jié)編碼：可以是0-255的ISO-8859-1字符；
日文編碼:也是雙字節(jié)編碼；
Extended ChannelInterpretation (ECI) mode 主要用于特殊的字符集。并不是所有的掃描器都支持這種編碼；
Structured Appendmode 用于混合編碼，也就是說，這個二維碼中包含了多種編碼格式；
FNC1 mode 這種編碼方式主要是給一些特殊的工業(yè)或行業(yè)用的。比如GS1條形碼之類的
下表是每個模式的編碼相對應(yīng)的“編號”，這個編號，存在于format information區(qū)域。
因為種類較多較復(fù)雜，而且為了方便大家理解，我們在這里值選擇數(shù)字編碼和字符編碼舉例，其它的編碼，有興趣的同學(xué)可以查看官方文檔。示例一：
數(shù)字編碼，從0到9。如果需要編碼的數(shù)字的個數(shù)不是3的倍數(shù)，那么，最后剩下的1或2位數(shù)會被轉(zhuǎn)成4或7bits，則其它的每3位數(shù)字會被編成10位的二進(jìn)制數(shù)，最后將這些二進(jìn)制數(shù)據(jù)連接起來并在前面加上編碼模式的編號和字符計數(shù)指示符（就是表示了被編碼的信息有多少個字符），字符計數(shù)指示符的長度取決于編碼的模式和所要編成二維碼的版本，在數(shù)字編碼中，字符計數(shù)指示符如下表對應(yīng)的有10、12或14位：
比如在Version 1的尺寸下，糾錯級別為H（糾錯級別我們會在下面講到）的情況下，我們要編碼： 01234567
（1）把上述數(shù)字分成三組: 012 345 67
（2）把他們轉(zhuǎn)成10bit二進(jìn)制: 012 轉(zhuǎn)成 0000001100；345 轉(zhuǎn)成 0101011001；67 轉(zhuǎn)成1000011。
（3）把這三個二進(jìn)制串起來: 0000001100 0101011001 1000011
（4）把數(shù)字的個數(shù)轉(zhuǎn)成二進(jìn)制 (version 1-H是10 bits ): 8個數(shù)字的二進(jìn)制是0000001000
（5）把數(shù)字編碼的標(biāo)志0001和第4步的編碼加到前面: 0001 00000010000000001100 0101011001 1000011
示例二：
字符編碼（也叫字母數(shù)字編碼）。包括 0-9，大寫的A到Z（沒有小寫），以及符號$ % *+ – . / : 包括空格。這些字符會映射成一個字符索引表。如下所示（兩個表，中英文對照）：（其中的SP是空格，Char是字符，Value是其索引值）,編碼的過程是把字符兩兩分組，然后轉(zhuǎn)成下表的45進(jìn)制，然后轉(zhuǎn)成11bits的二進(jìn)制，如果最后有一個落單的，那就轉(zhuǎn)成6bits的二進(jìn)制。而字符計數(shù)指示符需要根據(jù)不同的Version尺寸編成9, 11或13個二進(jìn)制（如上表）。
在V 1的尺寸下，糾錯級別為H的情況下，編碼: AC-42
（1）從字符索引表中找到 AC-42 這五個字條的索引 (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；
（4）把這些二進(jìn)制連接起來：00111001110 11100111001 000010
（5）把字符的個數(shù)轉(zhuǎn)成二進(jìn)制 (Version 1-H為9 bits ): 5個字符，5轉(zhuǎn)成 000000101
（6）在頭上加上編碼標(biāo)識 0010 和第5步的個數(shù)編碼: 0010 00000010100111001110 11100111001 000010
結(jié)束符和補(bǔ)齊符
以上述示例一為基礎(chǔ)，在編碼結(jié)束后，我們得到了如下編碼：
然后，我們還要加上結(jié)束符，表示真正的額數(shù)據(jù)已經(jīng)結(jié)束。
編碼 字符數(shù) HELLO WORLD的編碼
0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101
我們還要加上結(jié)束符：
編碼 字符數(shù) HELLO WORLD的編碼 結(jié)束
0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101 0000
按每組8個bit分組，如果所有的編碼加起來不是8個倍數(shù)我們還要在后面加上足夠的0，比如上面一共有45個bit，所以，我們還要加上3個0，然后按8個bits分好組：0001000000100000 00001100 01010110 01100001 10000000
接著就是補(bǔ)齊符，如果還沒有達(dá)到我們最大的bits數(shù)的限制，我們還要加一些補(bǔ)齊碼就是重復(fù)下面的兩個bytes：11101100 00010001。（使用這兩個字節(jié)的主要原因是，為了防止在填入數(shù)據(jù)時出現(xiàn)大片的深色或淺色區(qū)域，對掃描器產(chǎn)生干擾，使得二維碼難以正常掃描），至于要補(bǔ)多少個補(bǔ)齊符，需要查看文檔中相應(yīng)的字符數(shù)和數(shù)據(jù)容量對應(yīng)表，在官方文檔中，相對應(yīng)的是表7-表11
從表中，我們可以知道，v1-H的數(shù)據(jù)容量為9個數(shù)據(jù)碼字（每個數(shù)據(jù)碼字為8位），而我們上面已經(jīng)有了6個數(shù)據(jù)碼字，所以要補(bǔ)充三個8bit，補(bǔ)充完畢如下：0001000000100000 0000110001010110 01100001 10000000 11101100 00010001 11101100 上面的每一組數(shù)據(jù)為一個數(shù)據(jù)碼字，Data Codewords，現(xiàn)在也只是原始數(shù)據(jù)，還需要對其加上糾錯碼。
糾錯碼
上面我們提到了糾錯級別，二維碼中有四種級別的糾錯（從低到高為L、M、Q、H），這就是為什么有人在二維碼的中心位置加入圖標(biāo)，也依舊能夠掃描（就是二維碼殘缺量不超過所對應(yīng)的糾錯等級能允許的范圍時，使用掃描工具依舊能掃描出內(nèi)容的原因）。
至于糾錯碼是如何計算的，這涉及到里德-所羅門糾錯算法，里德-所羅門碼是定長碼。這個比較復(fù)雜，但是萬能的Pythom里面有一個交reedsolo的庫可以直接調(diào)用。這意味著一個固定長度輸入的數(shù)據(jù)將被處理成一個固定長度的輸出數(shù)據(jù)。在最常用的（255,223）里所碼中，223個里德-所羅門輸入符號（每個符號有8個 位元）被編碼成255個輸出符號。大多數(shù)里所錯誤校正編碼流程是成體系的。這意味著輸出的碼字中有一部分包含著輸入數(shù)據(jù)的原始形式。符號大小為8位元的里所碼迫使碼長（編碼長度）最長為255個符號。標(biāo)準(zhǔn)的（255,223）里所碼可以在每個碼字中校正最多16個里所符號的錯誤。由于每個符號事實上是8個位元，這意味著這個碼可以校正最多16個短爆發(fā)性錯誤。里德-所羅門碼，如同卷積碼一樣，是一種透明碼。這代表如果信道符號在隊列的某些地方被反轉(zhuǎn)，解碼器一樣可以工作。解碼結(jié)果將是原始數(shù)據(jù)的補(bǔ)充。但是，里所碼在縮短后會失去透明性。在縮短了的碼中，“丟失”的比特需要被0或者1替代，這由數(shù)據(jù)是否需要補(bǔ)足而決定。（如果符號這時候反轉(zhuǎn)，替代的0需要變成1）。這樣就需要在里所解碼前對數(shù)據(jù)進(jìn)行強(qiáng)制性的偵測決定。
我們有現(xiàn)成的python模塊來運(yùn)算出糾錯碼——python的reedsolo模塊。我們可以對照官方文檔中的糾錯特性表。以下表為例：
以版本1-H為例進(jìn)行解釋，從表中，我們可以清晰的知道，糾錯碼字?jǐn)?shù)應(yīng)該為17個，糾錯的塊數(shù)為1（表示這個版本要編碼的數(shù)據(jù)只會分為一個數(shù)據(jù)塊），（26,9,8）表示，這個版本的二維碼總共可以存放26個碼字，但是這26個碼字中，有9個碼字為數(shù)據(jù)碼字，17個為糾錯碼字（8*2+1=17），8位糾錯容量。每個表的下方否有注釋信息：
這也是為什么糾錯碼字?jǐn)?shù)為r*2，當(dāng)后面有一個箭頭時，表示r*2之后還要加1。在給數(shù)據(jù)碼字添加糾錯碼時，還有對數(shù)據(jù)碼字分塊的操作，因為version1的二維碼對數(shù)據(jù)碼字之分一個塊，不夠明顯，所以我們采用網(wǎng)上的一個例子：
上述的Version 5 + Q糾錯級：需要4個塊（2個塊為一組，共兩組），頭一組的兩個Blocks中各15個字節(jié)（數(shù)據(jù)碼字）數(shù)據(jù) 加上 各 9個字節(jié)的糾錯容量（18個字節(jié)的糾錯碼字）。因為二進(jìn)制寫起來會讓表格太大，所以，都用了十進(jìn)制來表示，我們可以看到每一個數(shù)據(jù)塊的糾錯碼有18個字節(jié)，也就是18個8bits的二進(jìn)制數(shù)。
5. 最終編碼，穿插放置。
此時，編碼的過程，只剩下最后一步。
對于數(shù)據(jù)碼字：把每個塊的第一個codewords先拿出來按順度排列好，然后再取第一塊的第二個，如此類推。上述示例中的Data Codewords如下：
我們先取第一列的：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
對于糾錯碼，也是一樣：
和數(shù)據(jù)碼取的一樣，得到：213，87，148，235，199，204，116，159，…… …… 39，133，141，236
然后，再把這兩組放在一起（糾錯碼放在數(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
剩余位
最后再加上Reminder Bits，對于某些Version的QR，上面的還不夠長度，還要加上Remainder Bits，比如：上述的5Q版的二維碼，還要加上7個bits，Remainder Bits加零就好了。關(guān)于哪些Version需要多少個Remainder bit，可以參看官方文檔的表一（這里列出一部分）。
掩碼（也叫掩模）
編碼的步驟是完成了，但是要想生成一個完好的二維碼，還需要先將現(xiàn)在所擁有的數(shù)據(jù)填入提前準(zhǔn)備的空白模板后，選擇一個合適的掩碼，將原模板的數(shù)據(jù)與掩碼進(jìn)行異或運(yùn)算，最后，再將format information填進(jìn)去就生成了二維碼。掩碼存在的意義：二維碼是要拿來掃描的，而掃描怕的就是無法清晰地分辨出編碼信息的每一位。要是二維碼中黑白點(diǎn)數(shù)量不均，或是空間分布不均都會導(dǎo)致大色塊區(qū)域的出現(xiàn)，而大色塊區(qū)域的出現(xiàn)會增加掃描時定位的難度，從而降低掃描的效率。更嚴(yán)重的情況下，如果數(shù)據(jù)填入后碰巧出現(xiàn)了功能性標(biāo)識，比如定位標(biāo)識的圖樣，還會干擾正常功能性標(biāo)識的作用，導(dǎo)致QR碼無法掃描。在計算機(jī)科學(xué)中，掩碼就是一個二進(jìn)制串，通過和數(shù)據(jù)進(jìn)行異或運(yùn)算來變換數(shù)據(jù)。在QR碼中，掩碼也是通過異或運(yùn)算來變換數(shù)據(jù)矩陣。所以你可能已經(jīng)猜到了，QR碼的掩碼就是預(yù)先定義好的矩陣。QR標(biāo)準(zhǔn)通過生成規(guī)則定義了八個數(shù)據(jù)掩碼：
前面的三位二進(jìn)制的數(shù)據(jù)就是每個模式掩碼相對應(yīng)的編號，這個信息也是要填入format information中的。
從這個圖我們就可以直觀的看到每種掩碼的模板樣子，以掩碼2（編號為010）為例，j mod 3 = 0 就是表示從左變開始數(shù)，能被3整除的列，都要取逆（黑塊變白塊，白塊變黑塊），當(dāng)然二維碼的固定格式區(qū)域的信息時不用取逆的，所以要使用掩碼2，需要取逆的列數(shù)為：0、3、6、9…..。
當(dāng)然，官方規(guī)定在進(jìn)行異或時，原始的數(shù)據(jù)模板要與每個掩碼模板進(jìn)行異或運(yùn)算后，要進(jìn)行如下的規(guī)則進(jìn)行計分（處罰），最后選擇分?jǐn)?shù)最低的一個作為最佳的掩碼選擇。
另外，使用python的reedsolo模塊，能夠在二維碼損壞超出相應(yīng)級別的容錯范圍時也能夠恢復(fù)數(shù)據(jù)。
Python2環(huán)境下的reedsolo模塊基本使用方式
1. 首先安裝reedsolo模塊，python官方下載的reedsolo模塊版本為0.3，不是很好用，這次使用的reedsolo模塊存放在下載包中的reedsolomon-master.zip，解壓后在該路徑下運(yùn)行cmd命令python setup.py install即可。
2. 進(jìn)入python環(huán)境，導(dǎo)入reedsolo模塊。定義一個對象，設(shè)置生成的糾錯碼個數(shù)為10個。
3. 為字符串“hello world”編碼，生成糾錯碼。
4. 進(jìn)行解碼
5. 現(xiàn)在大致了解了reedsolo模塊的使用方法，那現(xiàn)在了解一下糾錯碼的作用，比如，我們現(xiàn)在將“hello world”寫成錯誤的“hellx xorld”，這里我們出現(xiàn)了兩個錯誤，配上之前生成的糾錯碼進(jìn)行解碼，輸出的就是正確的字符串，糾錯碼就是這樣了。
6. 糾錯碼算法是對所要糾錯的內(nèi)容一個字節(jié)一個字節(jié)地進(jìn)行編碼，所以編碼后生成的是一個字節(jié)數(shù)組。
7. 將編碼后的內(nèi)容轉(zhuǎn)化為十進(jìn)制輸出
學(xué)以致用，復(fù)現(xiàn)MMA2015-MISC400-qr的二維碼恢復(fù)挑戰(zhàn)的解題步驟，原版write-up地址為：https://github.com/pwning/public-writeup/blob/master/mma2015/misc400-qr/writeup.md
1. 題目給出的二維碼如下圖
這是一個25*25的二維碼，也就是version2的二維碼，二位從它能看見的部分我們可以得到format information的一部分信息：??????011011010
2. 對照下面這個網(wǎng)址所給出的對應(yīng)表，可以知道這個二維碼使用了什么編碼模式和使用了哪一個掩碼
https://www.thonky.com/qr-code-tutorial/format-version-tables#list-of-all-format-information-strings
經(jīng)對照可知，完整的format information信息應(yīng)該是：010111011011010。且可以得到的信息還有該二維碼使用的掩碼為6，所對應(yīng)的糾錯等級為Q。
3. 將被遮擋的固定信息部分以及format information信息補(bǔ)充完整。
與相對應(yīng)的掩碼進(jìn)行異或運(yùn)算，得到原始的數(shù)據(jù)中的一部分?jǐn)?shù)據(jù)碼字和糾錯碼字。下圖就是掩碼6相對應(yīng)的圖案。
4. 將掩碼應(yīng)用到我們補(bǔ)充完的二維碼上，翻轉(zhuǎn)與掩碼中深色區(qū)域相對應(yīng)的區(qū)域的顏色，并用灰色將format information覆蓋，方便讀取數(shù)據(jù)，如下圖。
5. 從右下角開始，按下圖的蛇形順序讀取數(shù)據(jù)碼字和糾錯碼字的信息，至于不同區(qū)域塊的信息讀取順序，可以參考官方文檔。
且相對應(yīng)的數(shù)據(jù)塊分布應(yīng)該如下圖所示：
6. 將全部可讀的信息讀取出來：
7. 根據(jù)官方文檔的糾錯特性表，可知version2-Q的糾錯碼字?jǐn)?shù)有22個，數(shù)據(jù)碼字?jǐn)?shù)也有22個，在Q級別，它可以恢復(fù)不超過25%的損壞的字節(jié)，但是我們只有16個完整的字節(jié)，即超過63%的字節(jié)丟失，仔細(xì)查看Reed-Solomon的糾錯能力，并意識到它可以糾正多達(dá)兩倍的擦除——也就是說，如果 它知道錯誤在哪里，那么糾錯能力就強(qiáng)得多。這意味著我們的代碼可以從丟失的字節(jié)的50%恢復(fù)過來！但這意味著我們只能糾正多達(dá)22個丟失的字節(jié)，但是我們目前依然只有16個完整的字節(jié)，所以我們要想辦法恢復(fù)一部分字節(jié)使得達(dá)到22個字節(jié)這個最低要求。
8. 我們先將獲得的可讀取數(shù)據(jù)整理一下：
0010：【編碼模式=字符編碼（字母數(shù)字模式）】
000010100：【9個bit長度的字符計數(shù)標(biāo)識符=20個字符】
01010111000：【FL】
00111010010：【AG】
11001100110：【 I】
1010001000？：【S?】
我們計算一下，22個數(shù)據(jù)碼字，就是176個bit，而20個字符，在編碼的時候分為10組，每組11個bit，所以4+9+10*11=123個bit，123/8=15余3，再加上4個0（結(jié)束符） ，以及8bit重組時需要補(bǔ)充為8的倍數(shù)，8-3-4=1，所以還需要加1個0。這時候總共也就16個數(shù)據(jù)碼字，22-16=6，所以還要加上6個 字節(jié)的 補(bǔ)齊碼，如下（紅色的是原本被遮住的數(shù)據(jù)）：
00100000 10100010 10111000 00111010 01011001 10011010 10001000 ???????????????? ???????? ???????? ???????? ???????? ???????? ???????? ??000000 1110110000010001 11101100 00010001 11101100 00010001
這樣，我們就回復(fù)了6個字節(jié)的數(shù)據(jù)，此時我們丟失的字節(jié)就只剩下22個了，正好達(dá)到了最低的要求。我們就可以使用糾錯碼恢復(fù)原本的數(shù)據(jù)。
9. 編寫腳本利用python的reedsolo模塊進(jìn)行糾錯。
10. 得到全部的信息。
11. 拆分和解碼
參考文獻(xiàn)：
https://zhuanlan.zhihu.com/p/21463650
https://coolshell.cn/articles/10590.html
官方文檔（中文版）：
https://wenku.baidu.com/view/ef77275f312b3169a451a4a4.html?pn=50
里德-所羅門碼：
https://www.jianshu.com/p/8208aad537bb
https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#Encoding_outline
https://stackoverflow.com/questions/30363903/optimizing-a-reed-solomon-encoder-polynomial-division
MMA2015-MISC400-qr的write up：
https://github.com/pwning/public-writeup/blob/master/mma2015/misc400-qr/writeup.md
合天智匯：
http://www.hetianlab.com/expc.do?ec=ECID3581-0d42-4928-b602-ddd8e61b24a3
點(diǎn)贊的會變好看也會世界和平，關(guān)注的會大富大貴！底部小廣告路過不要錯過，恭喜發(fā)財。
