Préparer un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
199
Mois de parution
décembre 2016
Domaines


Résumé
Les articles précédents [1-6] vous ont donné envie de créer vos propres codes QR ? Ce sera chose faite ici même, pour le moment on prépare les données binaires.

Body

Dans cet article, on transforme le contenu d’un fichier en des données binaires directement collables dans un code QR.

Maintenant que nous savons lire le contenu des codes QR, même s’ils sont un peu entachés d’erreurs ou décorés d’un logo, nous allons faire l’inverse : créer un code QR avec un petit logo au milieu. N’en abusez pas, un code QR n’est lisible en pratique que par une application dédiée. Moi qui n’ai pas de téléphone portable, je déteste qu’on me propose un code QR tout nu sans explication comme au minimum l’adresse de la page ouèbe.

J’ai utilisé Wikiversity [7] et le QR-code tutorial [8] pour rédiger cet article. Les codes et fichiers sont sur le GitHub du magazine.

1. Préparation du tableau

On va reprendre en sens inverse (à peu près), les étapes de la lecture d’un code QR. Les fonctions et constantes communes ou utiles sont factorisées dans qrcodeoutils.py et dans qrcodestandard.py, je n’expliquerai leur contenu que s’il n’a pas déjà été étudié précédemment.

1.1. Initialisation

On va reprendre la structure de la classe qrdecode.py qui lit une image, mais en partant d’un fichier quelconque.

01: #!/usr/bin/python3
02: 
03: from PIL import Image
04: from sys import exit,stderr
05: from qrcorps import *
06: from qrcodestandard import *
07: from argparse import *

On importe les mêmes bibliothèques que lors de la lecture.

09: class qrencode:
10: 
11:   def __init__(self):
12:     [self.arguments,self.nivcor,self.masque,self.message,self.mode,self.longclair,
13:       self.version,self.longtoutclair,self.clair,self.longueur,
14:       self.tout,self.entrelac,self.dim,self.tabmat,self.gris,self.bontab]=[None]*16

Les noms des attributs sont encore parlants, ils sont donnés dans l’ordre de leur apparition dans le code.

1.2. Gestion des options

Je réutilise la bibliothèque argparse pour les options de la ligne de commandes.

01:   def options(self):
02:     parser=ArgumentParser(description="Crée un code QR.")
03:     parser.add_argument("-m",choices=["0","1","2","3","4","5","6","7"],help="Force le choix du masque.")
04:     parser.add_argument("-i",required=True,metavar="fichier",help="Fichier texte d’entrée.")
05:     parser.add_argument("-c",metavar="image",help="Imagette placée au milieu du code.")
06:     parser.add_argument("-t",type=int,metavar="N",default=4,help="Taille d’un module.")
07:     parser.add_argument("-o",required=True,metavar="image",help="Image de sortie.")
08:     parser.add_argument("-n",choices=["L","M","Q","H"],default="L",help="Niveau de correction.")
09:     parser.add_argument("-a",choices=["0","1"],default="0",help="Afficher l’image ou non.")
10:     self.arguments=parser.parse_args()

Ici :

- -m permet d’imposer le choix du masque, en son absence, le calcul du meilleur est effectué ;

- -i est le nom du fichier d’entrée (texte ou binaire) ;

- -c est le nom d’une éventuelle imagette décorative (canal alpha fonctionnel) collée au milieu de l’image du code QR ;

- -t précise la taille d’un module en pixels ;

- -o est le nom de l’image de sortie ;

- -n le niveau de correction (de Low à High) ;

- -a fait afficher l’image via la bibliothèque PIL [9].

Voici ce qu’affiche le programme en cas d’absence d’entrées :

> ./qrencode.py

usage: qrencode.py [-h] [-m {0,1,2,3,4,5,6,7}] -i fichier [-c image] [-t N] -o

                   image [-n {L,M,Q,H}] [-a {0,1}]

qrencode.py: error: the following arguments are required: -i, -o

Et l’aide :

> ./qrencode.py -h

usage: qrencode.py [-h] [-m {0,1,2,3,4,5,6,7}] -i fichier [-c image] [-t N] -o

                   image [-n {L,M,Q,H}] [-a {0,1}]

Crée un code QR.

optional arguments:

  -h, --help            show this help message and exit

  -m {0,1,2,3,4,5,6,7}  Force le choix du masque.

  -i fichier            Fichier texte d’entrée.

  -c image              Imagette placée au milieu du code.

  -t N                  Taille d’un module.

  -o image              Image de sortie.

  -n {L,M,Q,H}          Niveau de correction.

  -a {0,1}              Afficher l’image ou non.

Tâchons maintenant d’ouvrir le fichier donné en entrée et de traduire les options dans nos attributs.

12:   def entrees(self):

13:     if self.arguments is None:

14:       self.options()

16:     if self.arguments.t<=0:

17:       print("Il faut choisir une taille de module positive.")

18:       exit(1)

19:     self.nivcor=self.arguments.n

20:     if self.arguments.m is None:

21:       self.masque=None

22:     else:

23:       self.masque=int(self.arguments.m)

En fait, arguments est une instance de la classe argparse.Namespace et chacun de ses attributs est une option. Ainsi, arguments.n contient la chaîne de caractères pour le niveau de correction (stocké dans nivcor) et arguments.m une chaîne qui sera convertie en un entier pour le masque s’il y a lieu.

J’omettrai systématiquement le préfixe self. dans les noms des attributs et des méthodes donnés en explication.

Si l'on cherche à entrer une taille de module négative ligne 16 (les autres tests sont gérés par argparse), on sort.

24:     self.message=""

25:     try:

26:       with open(self.arguments.i,"r") as f:

27:         for l in f:

28:           self.message=self.message+l

29:     except IOError:

30:       print("Fichier %s inaccessible."%self.arguments.i)

31:       exit(1)

On teste si le fichier existe et est accessible (on lit alors le fichier ligne à ligne, on stocke son contenu binaire dans message), sinon on se plaint et on s’en va.

1.3. Détermination du mode

Selon le contenu du fichier envoyé, on détermine s’il faut utiliser le mode numérique, alphanumérique ou binaire (en fait, utf-8 et je rappelle que le mode kanji est laissé de côté, il est inclus dans le mode binaire).

01:   def carac(self):
02:     if None in [self.nivcor,self.masque,self.message]:
03:       self.entrees()
 
05:     caracteres=set(self.message)
 
07:     if self.message.isdecimal():
08:       self.mode=0
09:       q,r=divmod(len(self.message),3)
10:       self.longclair=10*q
11:       if r==1:
12:         self.longclair+=4
13:       elif r==2:
14:         self.longclair+=7

La méthode isdecimal retourne True si une chaîne de caractères ne contient que des chiffres décimaux. Si c’est le cas, on calcule le nombre de bits nécessaires pour les stocker.

Je rappelle qu’on utilise le fait que 10 bits suffisent à coder un nombre de trois chiffres, 7 pour un nombre à deux chiffres et 4 pour un nombre à un chiffre (voir les articles sur la lecture de codes QR [1-3]).

15:     elif caracteres.issubset(set(alphanum)):
16:       self.mode=1
17:       q,r=divmod(len(self.message),2)
18:       self.longclair=11*q+r*6

Dans qrcodestandard.py, alphanum="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:". On teste donc si tous les caractères y sont et dans ce cas, on calcule encore le nombre de bits nécessaires.

19:     else:
20:       self.mode=2
21:       self.message=self.message.encode("utf-8")
22:       self.longclair=len(self.message)*8

Enfin, dans le cas binaire ou kanji, on convertit le message unicode en une liste d’octets. En effet, len(" ") retourne 1 en Python 3 alors qu’il faut trois octets pour l’écrire (hex(ord(" ")) retourne '0x1f603').

1.4. Détermination de la version

On va déterminer la taille du code QR, c’est-à-dire le nombre de modules total du carré.

01:   def detversion(self):
02:     if None in [self.mode,self.longclair]:
03:       self.carac()
04:     for self.version in tableau:
05:       self.longtoutclair=8*sum(blocs(tableau[self.version][self.nivcor])[1::2])
06:       s=self.longtoutclair-4-longbin(self.version,self.mode)
07:       if s>self.longclair:
08:         break

blocs est une fonction présente dans qrcodestandard.py, présentée lors de la lecture :

def blocs(l):

  return list(eval(l.replace("×","*").replace("),",")+")))

Elle transforme le contenu brut du tableau en un équivalent exploitable par Python. Ici, elle transforme par exemple "2×(139,111),7×(140,112)" (version 22 et niveau de correction Low) en la liste [139,111,139,111,141,112,141,112,141,112,141,112,141,112,141,112,141,112]. On additionne ensuite les termes d’indice impairs (les longueurs des blocs de données, soit 2×111+7×112) et on multiplie par 8 pour obtenir le nombre total de bits utilisables ligne 5. On a donc le nombre de bits du message (longclair), à quoi il faut ajouter les quatre bits du mode et les bits codant la longueur du message ligne 6 (longbin est expliquée dans l’article sur le décodage [3]) pour tester si l’ensemble rentre ou non dans le code QR de la version testée de contenance longtoutclair.

Tant que le message est trop long, on passe à la version supérieure.

10:     if s<self.longclair:
11:       print("Le message est trop long, veuillez le raccourcir ou choisir un niveau de correction moins fort.")
12:       exit(1)

Si le message est toujours trop long (je n’ai pas codé la possibilité de créer un message découpé dans plusieurs codes QR consécutifs), on se plaint et on s’en va.

2. Construction des données

Il est temps de construire les données à écrire dans le code QR, tout est prêt.

2.1. Construction de la liste des données

Une fois la version choisie, on peut coder l’en-tête du code QR : le mode puis la longueur en caractères et non en bits ou en octets du message. Il est immédiatement suivi du message et complété éventuellement par un quadruplet de   et d’octets de bourrage. La correction d’erreur suit.

01:   def donnees(self):
02:     if None in [self.longtoutclair,self.version]:
03:       self.detversion()
04:     self.clair=[0]*(3-self.mode)+[1]+[0]*self.mode
05:     self.longueur=dec2bin(len(self.message),longbin(self.version,self.mode))
06:     self.clair+=self.longueur

Le mode est déterminé par la position du 1 dans le premier quadruplet et on code la longueur en sa valeur binaire.

08:     if self.mode==0:
09:       q,r=divmod(len(self.message),3)

10:       for i in range(q):
11:         self.clair+=dec2bin(int(self.message[i*3:i*3+3]),10)
12:       if r==1:
13:         self.clair+=dec2bin(int(self.message[-1]),4)
14:       elif r==2:
15:         self.clair+=dec2bin(int(self.message[-2:]),7)

Dans le mode numérique, on convertit chaque triplet de chiffres en sa valeur binaire ligne 10 en prenant soin de bien obtenir dix bits, c’est la raison d’être du deuxième argument de dec2bin. De même, un éventuel chiffre final est codé sur quatre bits et deux éventuels chiffres finaux sur sept bits.

16:     elif self.mode==1:
17:       q,r=divmod(len(self.message),2)

18:       for i in range(q):
19:         self.clair+=dec2bin(45*alphanum.index(self.message[2*i])\

20:                       +alphanum.index(self.message[2*i+1]),11)
21:       if r==1:
22:         self.clair+=dec2bin(alphanum.index(self.message[-1]),6)

On lit chaque paire de caractères pour coder la somme pondérée de leurs indices dans alphanum sur onze bits. Plus précisément, si i est l’indice du premier symbole et i celui du deuxième, alors on écrit la valeur en binaire de 45×i+i. S’il reste un caractère final, son indice est codé sur six bits.

23:     else:
24:       for b in self.message:
25:         self.clair+=dec2bin(b,8)

Enfin, dans le cas binaire, on code chaque octet en sa valeur binaire. Un message écrit en kanji utilisera ce mode.

27:   def fin(self):
28:     if None in [self.clair,self.longueur]:
29:       self.donnees()
30:     bourrage=dec2bin(0xec11,16)
31:     self.clair+=[0,0,0,0]

32: #    self.clair+=[0]*(8-len(self.clair)%8)
33:     while len(self.clair)<self.longtoutclair:
34:       self.clair+=bourrage
35:     self.clair=self.clair[:self.longtoutclair]

On termine le message par quatre zéros consécutifs, puis selon les sources, par un bourrage de zéros pour que la longueur du message soit un multiple de huit ou non. Enfin, on complète jusqu’à la longueur finale par une suite de 1110110000010001, soit ec11 en hexadécimal.

2.2. Calcul du code de Reed-Solomon

Le message est prêt à être découpé en blocs pour calculer les codes correcteurs de Reed-Solomon.

01:   def reedsolomon(self):
02:     if None in [self.clair,self.longueur]:
03:       self.fin()
04:     posclair,posredondant=court2blocs(tableau[self.version][self.nivcor])

court2blocs transforme la chaîne présente dans tableau ("2×(139,111),7×(140,112)" dans le cas d’une version 22 et de niveau de correction Low), la fonction est dans qrcodestandard.py :

def court2blocs(l):

  l1=blocs(l)

  for i in range(0,len(l1),2):

    l1[i:i+2]=l1[i:i+2][::-1]

  l2,l3=[0],[0]

  for i in range(len(l1)//2):

    l2.append(l2[-1]+l1[2*i])

    l3.append(l3[-1]+l1[2*i+1]-l1[2*i])

  return l2,l3

Elle retourne les positions des octets de début de chaque bloc de la partie en clair puis de la partie redondante, le dernier octet de la première liste est la longueur totale de la partie en clair, de même pour la partie redondante. Dans notre cas, elle retourne [0, 111, 222, 334, 446, 558, 670, 782, 894, 1006] [0, 28, 56, 84, 112, 140, 168, 196, 224, 252].

06:     blocsclair=[]
07:     for i in range(len(posclair)-1):
08:       blocsclair.append(self.clair[8*posclair[i]:8*posclair[i+1]])
09:     blocsredondant=[]

Ici, on crée chaque bloc de données, le premier contient les 111 premiers octets donc les 888 premiers bits, son bloc correcteur contiendra 28 octets, soit 224 bits.

10:     for i in range(len(blocsclair)):
11:       bloc=blocsclair[i]
12:       longredondant=8*(posredondant[i+1]-posredondant[i])
13:       polyclair=message2poly(bloc+[0]*longredondant)
14:       modulo=Polynome.construction([1])
15:       for i in range(longredondant//8):
16:         modulo*=Polynome.construction([1,F256.exp(i)])
17:       blocsredondant.append(poly2message(polyclair%modulo))

On calcule le complément correcteur de chaque bloc en clair qui n’est que le reste d’une division euclidienne de polynômes qu’on concatène aux données en clair, voir le détail dans la section sur la correction des erreurs [6].

19:     self.tout=[]
20:     for bloc in blocsclair:
21:       self.tout+=bloc
22:     for bloc in blocsredondant:
23:       self.tout+=bloc

On concatène tout en une seule liste, les blocs en clair à la queue leu leu suivis (dans le même ordre) par les blocs correcteurs.

2.3. Entrelacement du message binaire final

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 dans le dictionnaire tableau de qrcodestandard.pytableau[5]["L"] vaut "(134,108)" alors que tableau[6]["L"] vaut "2×(86,68)".

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 neuf blocs. On écrit les octets des neuf blocs dans un tableau comme ci-dessous :

Bloc

Octets

n°0

 

1

2

3

108

109

110

−1

n°1

111

112

113

114

219

220

221

−1

n°2

222

223

224

225

330

331

332

333

n°7

782

783

784

785

890

891

892

893

n°8

894

895

896

897

1002

1003

1004

1005

Le bloc n°0 contient les 111 premiers octets, soit les octets 0 à 110, le −1 signifie qu’il faut sauter ce rang et passer au bloc suivant. 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 valeurs négatives. Ainsi, la partie en clair entrelacée contient les octets 0, 111, 222, 334, 446, 558, 670, 782, 894, 1, 112, 223; … 892, 1004, 333, 445, 557, 669, 783, 893, 1005.

On fait la même chose pour les octets des blocs correcteurs qui ont tous la même taille.

01:   def entrelacement(self):
02:     if self.tout is None:
03:       self.reedsolomon()
04: 
05:     posclair,posredondant=court2long(tableau[self.version][self.nivcor])

On récupère, dans le tableau (qui est un dictionnaire de dictionnaires), la chaîne qui nous intéresse "2×(139,111),7×(140,112)" et on la transforme en son équivalent qui ne contient que des coordonnées absolues (plus un zéro initial). Les données en clair et leurs corrections sont regroupées en blocs pas trop grands pour des raisons de temps de calcul. Par exemple, pour le niveau de correction L de la version 22, les données sont en deux blocs de 139 octets dont les 111 premiers contiennent la partie en clair (il reste donc 28 octets pour la correction dans chacun) et les sept blocs suivants contiennent 140 octets dont les 112 premiers pour la partie en clair (et toujours 28 pour la correction).

Voici le début du contenu de tableau, stocké dans qrcodestandard.py :

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)"},

[…]

         22:{"L":"2×(139,111),7×(140,112)","M":"17×(74,46)","Q":"7×(54,24),16×(55,25)",[…]

Et ainsi de suite jusqu’à 40. J’ai graissé le niveau de correction illustré ci-dessus.

Plutôt que de transformer à la main les informations données dans [7], 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("),",")+")))

Dans notre cas, blocs retourne [139, 111, 139, 111, 140, 112, 140, 112, 140, 112, 140, 112, 140, 112, 140, 112, 140, 112], voir les articles précédents [1-6].

Comme la manière initiale, relative, n’est pas très utilisable, je l’ai convertie, à l’aide de la fonction court2long, en des nombres absolus directement utilisables par l’opérateur crochets [] de Python. Je prends l’exemple du niveau de correction Q de la version 3.

def court2long(l):

  l1=blocs(l)

  for i in range(0,len(l1),2):

    l1[i:i+2]=l1[i:i+2][::-1]

On permute les valeurs deux à deux, l1=[111, 139, 111, 139, 112, 140, 112, 140, 112, 140, 112, 140, 112, 140, 112, 140, 112, 140] après cette étape.

  l2=[[-1]]

  for i in range(len(l1)//2):

    l2.append([1+j+l2[-1][-1] for j in range(l1[2*i])])

  del l2[0]

On récupère la taille de chaque bloc de données en clair et on crée pour chaque valeur, une liste qui donne les positions des bits de chaque bloc. Par exemple, l2=[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,…,110],[111,112,113,114,…],[…,1002,1003,1004,1005]].

  l3=[]

  for i in range(max(len(l) for l in l2)):

    for j in range(len(l2)):

      try:

        l3.append(l2[j][i])

      except IndexError:

        l3.append(-1)

Ici, on crée l’enchevêtrement des bits des blocs : on écrit les listes ci-dessus les unes sur les autres dans un tableau et on le lit verticalement. Il s’agit donc d’un zip comme ci-dessus, mais on ne crée qu’une seule liste qui contient l’enchevêtrement. Ici, par exemple, l3=[[0,111,222,334,446,558,670,782,894,1,112,223,335,447,…,892,1004,-1,-1,333,445,557,669,781,893,1005]. Que se passe-t-il si les blocs n’ont pas la même longueur ? On remplace les valeurs manquantes par -1.

  l4=[[max(l3)]]

  for i in range(len(l1)//2):

    l4.append([1+j+l4[-1][-1] for j in range(l1[2*i+1]-l1[2*i])])

  del l4[0]

  l5=[]

  for i in range(max(len(l) for l in l4)):

    for j in range(len(l4)):

      l5.append(l4[j][i])

  return l3,l5

Et on fait la même chose pour les blocs de la correction d’erreur sans vérification des tailles, ils ont toujours tous la même longueur.

06:     pos=posclair+posredondant
07:     self.entrelac=[0]*len(self.tout)
08:     j=0
09:     for i in range(len(self.entrelac)//8):
10:       if pos[i]!=-1:
11:         self.entrelac[8*j:8+8*j]=self.tout[8*pos[i]:8+8*pos[i]]
12:         j+=1

Enfin, le j-ième octet du message entrelacé (partie en clair et correction) est le pos[i]-ième du message non entrelacé. i est la position dans la sortie de court2long alors que j est la position dans le message entrelacé, c’est pour cette raison que j n’est incrémenté que si pos[i] indique la position d’un octet (−1 indique qu’on est à la fin d’un bloc plus court).

Conclusion

On a calculé les blocs correcteurs de Reed-Solomon, les blocs sont entrelacés et le message binaire brut est prêt à être déversé dans notre matrice. Ce sera l’objet de notre tout dernier article en page suivante où nous allons dessiner notre code QR avec une petite cerise sur le gâteau.

Références

[1] PATROIS N., « Expliquer un code QR », GNU/Linux Magazine n°193, p. 22 à 26

[2] PATROIS N., « Déchiffrer un code QR », GNU/Linux Magazine n°193, p. 28 à 31

[3] PATROIS N., « Décoder un code QR », GNU/Linux Magazine n°194, p. 32 à 41

[4] PATROIS N., « Expliquer un corps fini », GNU/Linux Magazine n°195, p. 16 à 19

[5] PATROIS N., « Fabriquer un corps fini », GNU/Linux Magazine n°196, p. 32 à 37

[6] PATROIS N., « Réparer un code QR », GNU/Linux Magazine n°198, p. 34

[7] Reed–Solomon codes for coders : https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders et le complément plus précis https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders/Additional_information.

[8] QR Code tutorial : http://www.thonky.com/qr-code-tutorial/

[9] The Python Imaging Library Handbook : http://effbot.org/imagingbook/.




Articles qui pourraient vous intéresser...

Accélération de Python avec Numba

Magazine
Marque
GNU/Linux Magazine
Numéro
240
Mois de parution
septembre 2020
Domaines
Résumé

L’usage de Python est croissant depuis une dizaine d’années. L’engouement pour la fouille de données (data mining) et les réseaux de neurones profonds (deep learning) explique en partie ce dynamisme. L’un des rares reproches faits à Python est sa relative lenteur.

Python « moderne » : comment coder en Python en 2020 ?

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
110
Mois de parution
septembre 2020
Domaines
Résumé

Le langage Python évolue progressivement, version après version et de nouvelles fonctionnalités voient le jour et changent la manière dont le langage peut être appréhendé.Au-delà de la curiosité que ces changements provoquent, ils sont des révolutions silencieuses ayant un impact réel sur le style de codage.