] >
Paru dans GNU/Linux Magazine n°194 de juin 2016.
Protégé par la licence CC BY-NC-ND 2.0.
Une fois que l'on sait déchiffrer un code QR [1], il faut le décoder... et il y a encore du travail avant de pouvoir lire son contenu.
Nous allons décortiquer le code QR petit à petit pour en extraire les informations utiles à la lecture de son contenu. Le code et les fichiers utiles sont sur GitHub [2].
Je me suis servi des informations données sur Wikiversity [3] pour la rédaction de cet article.
Nous allons enfin pouvoir lire le contenu du message caché dans la bouillie de pixels de la figure 1. Pour cela, il faut lire le format (niveau de correction et masque) dans la petite zone dédiée. Ensuite, une fois l’image démasquée, on en extrait le message brut : les données en clair et de quoi le corriger. La partie en clair contient en son début les informations précises nécessaires à son interprétation.
Fig. 1 : Le code QR à décoder.
On commence par lire (voir figure 2) les deux zones de bits verts dans
Fig. 2 : Les quatre différentes zones d’un code QR.
La couleur rouge caractérise les cibles d’alignement, le bleu les pointillés, en vert les deux zones de format et en gris les données.
Je renuméroterai le code à partir de 01 à chaque section.
01: def formats(self): 02: if self.esttourne is None: 03: self.placeim() 04: self.form=[None,None] 05: self.form[0]=self.qr[8][:6]+self.qr[8][7:9]+[self.qr[7][8]] 06: for i in range(5,-1,-1): 07: self.form[0].append(self.qr[i][8]) 08: self.form[0]=[i^j for (i,j) in zip(self.form[0],masquef)] 09: self.form[1]=[self.qr[-i-1][8] for i in range(7)] 10: self.form[1]=self.form[1]+self.qr[8][-8:] 11: self.form[1]=[i^j for (i,j) in zip(self.form[1],masquef)]
Les formats, après lecture, valent
masquef=[int(i) for i in "101010000010010"]
En effet :
111110110101010 ^101010000010010 ---------------- 010100110111000
Notre zone de format est donc 010100110111000.
On se contente pour le moment de vérifier que
01: def verifformat(self): 02: if self.form is None: 03: self.formats() 04: if self.form[0]!=self.form[1]: 05: print("Formats différents.",file=stderr) 06: exit(1) 08: self.formatok=True
Et on dit qu’on est content, chantons sous la pluie...
Dans les images suivantes, la zone verte sera démasquée.
La partie grise et blanche ne contient pas tout à fait les données brutes, il faut composer avec un masque binaire pour les obtenir.
01: def demasque(self): 02: if self.formatok is None: 03: self.verifformat() 05: self.nivcor=niveaucorrection[tuple(self.form[0][:2])] 06: self.masque=masques[tuple(self.form[0][2:5])]
Les deux premiers bits du format donnent le niveau de correction des erreurs, du niveau L qui corrige le moins d’erreurs au niveau H qui en corrige le plus (les lettres signifient Low, Medium, Quality et High [4]). Ici, notre image utilise le niveau L.
niveaucorrection={(0,1):"L" ,(0,0):"M",(1,1):"Q",(1,0):"H"} masques={(0,0,0):lambda i,j:(i+j)%2==0, (0,0,1):lambda i,j:i%2==0,(0,1,0):lambda i,j:j%3==0 , (0,1,1):lambda i,j:(i+j)%3==0, (1,0,0):lambda i,j:(i//2+j//3)%2==0, (1,0,1):lambda i,j:(i*j)%2==0 and (i*j)%3==0, (1,1,0):lambda i,j:((i*j)%3+i*j)%2==0, (1,1,1):lambda i,j:((i*j)%3+i+j)%2==0 }
Le
08: self.dim=len(self.qr) 09: self.version=(self.dim-17)//4
On calcule le nombre de modules en hauteur (et donc en largeur), on en déduit la
10: self.gris=griser(self.dim,self.version)
La fonction
def griser(dimension,version): tablegris=[[False for _ in range(9)]+[True for _ in range(dimension-17)]+\ [False for _ in range(8)] for _ in range(6)] tablegris=tablegris+[[False for _ in range(dimension)]] tablegris=tablegris+[[False for _ in range(9)]+[True for _ in range(dimension-17)]+\ [False for _ in range(8)] for _ in range(2)] tablegris=tablegris+[[True for _ in range(6)]+[False]+\ [True for _ in range(dimension-7)] for _ in range(dimension-17)] tablegris=tablegris+[[False for _ in range(9)]+\ [True for _ in range(dimension-9)] for _ in range(8)]
Les trois premières lignes ajoutent les deux cibles du haut et la zone entre elles deux (la deuxième est la zone de pointillés horizontale). La suivante construit les lignes entre les cibles et la dernière les lignes inférieures avec la cible inférieure à gauche.
Quand
for ci in minicibles[version]: for cj in minicibles[version]: if (ci,cj) not in {(6,6),(6,max(minicibles[version])),(max(minicibles[version]),6)}: for i in range(ci-2,ci+3): tablegris[i][cj-2:cj+3]=[False]*5
Pour les petites cibles de 5 modules de côté, le dictionnaire
Voici le début du dictionnaire
minicibles={1:[], 2:[18],3:[22],4:[26],5:[30],6:[34], 7:[6,22,38],8:[6,24,42],9:[6,26,46],10:[6,28,50],11:[6,30,54],12:[6,32,58],13:[6,34,62], ... }
Et ainsi de suite jusqu’à 40, vous comprenez pourquoi je coupe, le chef et la PAO aussi.
La suite de la fonction
if version>=7: for i in range(6): tablegris[i][-11:-8]=[False]*3 for i in range(3): tablegris[-11+i][0:6]=[False]*6
Il s’agit des deux rectangles de 3×6 modules placés entre les pointillés, à gauche contre la cible de droite et au-dessus contre la cible du bas. Ils n’existent que pour les codes QR de
return tablegris
12: for i in range(self.dim): 13: for j in range(self.dim): 14: if self.gris[i][j]: 15: self.qr[i][j]^=self.masque(i,j)
Et enfin, on démasque bit à bit, le résultat est dans la figure 3 (la partie verte est démasquée, observez en bas et en haut
Fig. 3 : La partie grisée est démasquée.
Vous vous dites qu’on pourrait démasquer tout le tableau sans se soucier du
Il est temps d’extraire de la zone grise le message binaire et sa correction.
01: def messagebrut(self): 02: if None in [self.version,self.masque,self.dim,self.gris,self.nivcor]: 03: self.demasque() 04: i,j=self.dim-1,self.dim-1 05: self.code=[] 06: direction=-1
La suite de bits, en-tête, message et correction des deux, est dans
08: limite=(16*(4+self.version*(8+self.version))-25*(self.version>=2+self.version//7)**2-(self.version>=7)*(36+self.version//7*40))//8*8
Comme d’habitude en Python, un test vaut 1 s’il est vrai et 0 s’il est faux. Vous pouvez vous amuser à retrouver la raison de chaque terme dans cette formule, vous avez tout ce qu’il faut ici.
Bon, je vais vous aider à démontrer cette formule, appelons v la
On a au total 4v+17 modules en longueur et en hauteur donc (4v+17)2 modules en tout, ce à quoi il faut soustraire les trois cibles de 8×8=64 modules, les deux zones de format de 15 modules chacune, le module toujours noir et les pointillés bleus. On a donc, sans compter les mini-cibles et les zones complémentaires de 3×6 :
(4v+17)2−3×64−2×15−1−2×(4v+17−2×8)=16v2+128v+64=16(v2+8v+4).
La seconde expression compte le nombre de modules pris par les mini-cibles qui ne rencontrent pas les pointillés. Elles sont de 5×5, apparaissent à partir de la
Enfin, 36 compte les modules pris dans les deux rectangles de 3×6, 40 vient des mini-cibles qui chevauchent les pointillés bleus, donc qui prennent 2×(25−5)=40 modules supplémentaires.
On compte le nombre d’octets, on divise par 8 (euclidiennement) et j’ai remultiplié par 8 pour obtenir le nombre de bits.
Remarquez que dans notre cas, il reste 7 modules puisque la formule donne bien 560 alors que 29×29−3×64−2×15−1−2×13−25=567.
09: while len(self.code)<limite: 10: if self.gris[i][j]: 11: self.code.append(self.qr[i][j]) 12: i,j,direction=suivant(i,j,direction,self.dim)
On stocke le bit s’il est bien dans le
Et voici la partie délicate. On commence par le bit tout en bas à droite puis on remonte de droite à gauche une colonne de deux bits de largeur.
def suivant(i,j,direction,dimension): j-=1
On commence par reculer d’un module vers la gauche.
if j%2!=(dimension%2+(j<6))%2: j+=2 i+=direction
Si on a reculé deux fois, on change de ligne et on avance de deux modules pour rester dans la colonne.
if i==-1: j-=2 i=0 direction=1
Une fois arrivé en haut, on redescend la colonne suivante de deux modules de largeur, toujours de droite à gauche.
if i==dimension: j-=2 i=dimension-1 direction=-1
Et arrivé en bas, on remonte.
if j==6: j=5 return i,j,direction
À un détail près : on saute la septième colonne (d’indice 6) qui contient le segment pointillé bleu vertical. La variable
On peut remarquer que la fonction
On lira donc la suite de bits suivante pour la première colonne, en montant :
Fig. 4 : Comment lire les données brutes.
Pour qu’un petit dessin n’empêche pas la lecture du message d’un code QR, les données sont en fait entrelacées dès qu’un code QR est assez grand selon le tableau suivant :
Niveau de correction | Low | Medium | Quality | High |
---|---|---|---|---|
Entrelacement à partir de la version | 6 | 4 | 3 | 3 |
On le voit par exemple plus bas dans le dictionnaire
Les octets des blocs en clair puis correcteurs sont mélangés et donc distribués partout dans l’image. Dans notre cas, on a un seul bloc de 55 octets de données suivis de 15 octets correcteurs. Dans le cas dela
Bloc | Octets | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
n°0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
n°1 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
n°2 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 |
n°3 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 |
Le bloc n°0 contient les 11 premiers octets soit les octets 0 à 10, une case vide signifie qu’il faut la sauter et passer à la suivante. La partie en clair est construite orthogonalement : on lit le tableau de haut en bas d’abord puis de gauche à droite, il s’agit en quelque sorte du tableau transposé de celui-ci en sautant les cases vides. Ainsi, la partie en clair entrelacée contient les octets 0, 11, 22, 34, 1, 12, 23, …, 9, 20, 31, 43, 10, 21, 32, 44, 33, 45.
On fait la même chose pour les octets des blocs correcteurs qui ont tous la même taille.
14: posclair,lonredondant,lonclair,nbbloc=court2vf(tableau[self.version][self.nivcor])
On récupère, dans le
Voici le début du contenu de
tableau={1:{"L":"(26,19)","M":"(26,16)","Q":"(26,13)","H":"(26,9)"}, 2:{"L":"(44,34)","M":"(44,28)","Q":"(44,22)","H":"(44,16)"}, 3:{"L":"(70,55)" ,"M":"(70,44)","Q":"2×(35,17)" ,"H":"2×(35,13)"}, 4:{"L":"(100,80)","M":"2×(50,32)","Q":"2×(50,24)","H":"4×(25,9)"}, 5:{"L":"(134,108)","M":"2×(67,43)","Q":"2×(33,15),2×(34,16)","H":"2×(33,11),2×(34,12)" }, 6:{"L":"2×(86,68)","M":"4×(43,27)","Q":"4×(43,19)","H":"4×(43,15)"},
Et ainsi de suite jusqu’à 40. J’ai graissé les trois niveaux de correction illustrés dans cette section.
Plutôt que de transformer à la main les informations données dans [8], j’ai préféré créer des fonctions ad hoc qui le font à ma place, elles aussi dans qrcodestandard.py :
def blocs(l): return list(eval(l.replace("×","*").replace("),",")+")))
On remplace les × par * et les séparateurs
Comme la manière initiale, relative,n’est pas très utilisable, je l’ai convertie, à l’aide de la fonction
def court2vf(l): l1=blocs(l) clair=l1[1::2] M=max(clair) m=min(clair) s1=M*len(l1)//2 s2=sum(clair) l2=[True]*m*len(clair) l2+=[False]*(M-m)*l1.count(m) l2+=[True]*(M-m)*l1.count(M) l3=sum(l1[2*i]-l1[2*i+1] for i in range(len(clair))) return l2,l3,s1,len(l1)//2
Cette fonction retourne, dans le niveau de correction L de la
15: self.clair=[[] for _ in range(nbbloc)] 16: self.redondant=[[] for _ in self.clair]
Pour le moment,
17: j=0 18: for i in range(lonclair): 19: if posclair[i]: 20: self.clair[i%nbbloc]+=self.code[j*8:j*8+8] 21: j+=1 22: for i in range(lonredondant): 23: self.redondant[i%nbbloc]+=self.code[(i+j)*8:(i+j+1)*8]
Dans notre cas (
Voici le contenu hexadécimal de la partie en clair
Fig. 5 : Le découpage du message.
Les barres noires délimitent les zones importantes : l’en-tête, les données (avec bourrage), la correction et le supplément inutilisé. Les octets ou quadruplets sont délimités par les barres magenta.
On va se contenter de dire que tout va bien, le développement de la correction d’erreurs se fera plus loin après des préliminaires de rigueur.
01: def messagecorr(self): 02: if None in [self.clair,self.redondant]: 03: self.messagebrut() 04: compte=0 05: if self.corrige: 06: for i in range(len(self.clair)): 07: self.clair[i],self.redondant[i],c=corrige(self.clair[i],self.redondant[i]) 08: compte+=c 09: clair=[] 10: for l in self.clair: 11: clair+=l 12: self.clair=clair 13: redondant=[] 14: for l in self.redondant: 15: redondant+=l 16: self.redondant=redondant 17: if compte: 18: self.messageok=compte 19: else: 20: self.messakeok=True
Ligne 04, la variable
Enfin ! On va pouvoir savoir ce que contient notre exemple de code QR.
01: def decodeqr(self): 02: if self.messageok is None: 03: self.messagecorr() 05: self.mode=3-self.code[:4].index(1) 06: self.longueur=longbin(self.version,self.mode)
La sélection du
Voici la fonction
def longbin(version,mode): if version<=9: return {0:10,1:9,2:8,3:8}[mode] elif version<=26: return {0:12,1:11,2:16,3:10}[mode] return {0:14,1:13,2:16,3:12}[mode]
Selon le
def bin2dec(n): s=0 for b in n: s*=2 s+=b return s
Cette fonction utilise l’algorithme de Horner (William George, pas Yvette), rapide et simple à mettre en œuvre.
En effet, si (c’est l’écriture de n en base 2, chaque bi vaut 0 ou 1), on peut écrire que
n=b7 27+b6 26+b5 25+b4 24+b3 23+b2 22+b1 21+b0 20 =(((((((0×2+b7)×2+b6)×2+b5)×2+b4)×2+b3)×2+b2)×2+b1)×2+b0.
Pourquoi diable ? Pour économiser le nombre de multiplications effectuées. On a 29 multiplications par le calcul naïf en comptant le calcul des puissances (en O(n²), en gros proportionnel au carré du nombre de bits) et 8 par la méthode de Horner (en O(n), proportionnel au nombre de bits). La technique fonctionne aussi si on veut évaluer un polynôme (on remplace 2 par x), on la réutilisera plus loin.
20: self.longclair=bin2dec(self.clair[4:4+self.longueur])
On calcule donc la longueur exacte du message qui est, dans notre cas, de 37 caractères puisque les huit bits du champ sont
Suivent les fonctions des quatre modes. Le message est lu immédiatement après les bits de
22: def numeric(): 23: n="" 24: fin=self.longclair%3 25: self.longclair-=fin 26: i=4+self.longueur 27: while len(n)<self.longclair: 28: n=n+str(bin2dec(self.clair[i:i+10])) 29: i+=10 30: if fin==1: 31: n=n+str(bin2dec(self.clair[i:i+4])) 32: elif fin==2: 33: n=n+str(bin2dec(self.clair[i:i+7])) 34: return int(n)
Le format numérique ne permet de stocker que des nombres entiers positifs, par exemple de très grands nombres premiers. Comme 999<210=1024, il suffit de dix bits pour stocker trois chiffres en base 10, ce qui est bien mieux que 24 bits en ASCII. Que se passe-t-il si le nombre de chiffres n’est pas un multiple de 3 ? Si le nombre contient 3n + 1 chiffres, le dernier est codé sur 4 bits ligne 31 (car 23<9<24) et s’il en contient 3n + 2, les deux derniers sont codés sur 7 bits ligne 33 (car 26<99<27).
36: def alphanumeric(): 44: ch="" 45: fin=self.longclair%2 46: self.longclair-=fin 47: i=4+self.longueur 48: while len(ch)<self.longclair: 49: n=bin2dec(self.clair[i:i+11]) 50: q,r=divmod(n,45) 51: ch=ch+alphanum[q]+alphanum[r] 52: i+=11 53: if fin==1: 54: ch=ch+alphanum[bin2dec(self.clair[i:i+6])] 55: return ch
Le format alphanumérique permet d’écrire des URL ou du texte simple. Il contient 45 symboles : de 0 à 9, les chiffres, de 10 à 35, les lettres et enfin neuf symboles supplémentaires de 36 à 44 :
En fait, deux symboles sont codés sur 11 bits : le quotient et le reste de la division par 45 puisque 210<452=2025<211. Si le nombre de symboles est impair, le dernier est codé sur 6 bits ligne 54 (car 25<45<26).
57: def byte(): 58: return bytes([bin2dec(self.clair[i:i+8]) for i in range(4+self.longueur,4+self.longueur+self.longclair*8,8)]).decode("utf-8")
Là, c’est simple : chaque octet est lu tel quel, mais nous supposons ici que le message est encodé en utf-8, ce qui n’est pas le cas en général, les codes QR acceptent d’autres encodages. Notre message commence par
63: def kanji(): 64: raise NotImplementedError
Je ne connais rien aux kanjis donc j’ai préféré m’abstenir d’écrire un script faux même si j’ai déjà joué avec une Casio FX-850P.
66: self.message={0:numeric,1:alphanumeric,2:byt,3:kanji}[self.mode]()
Python permet ce genre de syntaxe concise et efficace. Le numéro du
Testons notre travail :
if __name__=="__main__": essai=qrdecode() essai.decodeqr() print(essai)
On initialise
> ./qrdecode.py -i glmf3.png -a 1 Fichier : glmf3.png Niveau de correction : Low Masque : █ █ █ █ █ █ █ █ █ █ █ █ Dimensions : 29×29 Version : 3 Mode : Byte Longueur du message : 37 Message : Lisez GNU/Linux magazine France. 😃
Et voilà, avec le beau sourilaid bien interprété, certains lecteurs transforment les sourilaids en une image.
Nous pouvons maintenant lire n’importe quel code QR bien carré, mais pas ceux munis d’un logo. Pour cela, il faut un détour par les mathématiques des corps finis et ça, ce sera pour un prochain article.