Pour cette troisième étape, nous allons finir le placement des modules du QR-code à générer. Les modules restant à placer sont les modules qui représentent le message du QR-code (que ce soit une URL ou tout autre texte) ainsi que les modules de correction d'erreurs. La première partie de cette étape consistera au placement des modules de données étant donné un message déjà encodé sous forme d'octets.
En seconde partie de cette troisième étape, nous allons aussi calculer une première partie des octets du message encodé. Le calcul des octets pour la partie correction d'erreurs sera le sujet des deux dernières étapes du projet.
Les QR-codes contiennent tous un message qui peut être lu en scannant le QR-code. Ce message est généralement une URL, mais peut être n'importe quel texte.
Par exemple, un QR-code peut contenir le message Bravo !, qui est une suite de 7 caractères, l'espace et la ponctuation comptant chacun comme un caractère.
À ce message correspondent une suite d'octets qui encode ce message. On appelle cette suite d'octets le message encodé. Dans le cas du message Bravo ! la suite d'octets du message encodé est la suivante : 64, 116, 39, 38, 23, 102, 242, 2, 16, 236, 17, 236, 17, 236, 17, 236, 17, 236, 17, 154, 167, 72, 123, 58, 205, 160. Cette suite de 26 octets de long représente le message. Elle contient des informations sur le message ainsi que des octets de correction d'erreur.
Dans le cadre de ce projet, les messages encodés feront toujours 26 octets de long. Le message, une fois encodé, est inséré dans le QR-code de la façon dont nous allons discuter.
Sur le QR-code à générer, il nous reste un total de 208 modules à placer. Ces modules serviront à afficher le message encodé. Sur l'image suivante, les modules à placer sont affichés en gris:
Comme nous le verrons sous peu, les modules de données sont regroupés en 26 groupes de 8 modules. Chaque groupe correspond à un octet (8 bits) du message encodé (26 octets au total), chaque module correspondant donc à un bit du message encodé. La signification de chaque bit du message encodé nous importe peu pour cette première partie, nous allons simplement implémenter la logique de placement des modules en fonction des octets à afficher. Le calcul des octets sera abordé plus tard!
Pour cette troisième étape, vous allez coder la logique de placement des 208 modules restant, ainsi que, dans une seconde partie, déterminer les 19 octets du message encodé. Le calcul des 7 octets restant, qui servent à la correction d'erreurs, sera le sujet des deux dernières étapes du projet.
Les bits du message encodé correspondent à des modules sur la matrice du QR-code. La couleur du module indique la valeur du bit correspondant. On pourrait s'attendre à ce qu'un bit à 0 corresponde à un module blanc, et qu'un module à 1 corresponde à un module noir. En réalité, la détermination de la couleur est un peu plus compliquée : Normalement, un bit à 0 correspond bien à un module blanc, alors qu'un module à 1 correspond bien à un module noir, et ce sauf dans le cas où la somme des coordonnées x et y du module est un multiple de 3. Dans ce cas-là, les couleurs sont inversées. On parle ici d'un masque.
Le format QR-code spécifie un total de 8 différents masques. Dans le cadre de ce projet, nous utiliserons uniquement le masque précédement mentionné (masque numéro 3). En pratique, il est possible de choisir le masque afin d'éviter certains artefacts problèmatiques pour la lecture du QR-code. Nous ne nous soucierons pas de ce détail.
Dans le fichier qr.py, veuillez ajouter les deux fonctions suivantes :
def applique_masque(x, y, b):
m = 1 if (x + y) % 3 == 0 else 0
return b ^ m
def placer_module_donnee(img, x, y, b):
placer_module(img, x, y, couleur_module(applique_masque(x, y, b)))La fonction placer_module_donnee permet de placer un module dans l'image img au coordonnées x et y étant donné un bit b à afficher. La fonction tient compte du masque à appliquer pour le choix de la couleur du module. La fonction applique_masque, utilisée par placer_module_donnee, sert à tenir compte du masque.
Chaque octet du message encodé correspond à un groupe de 8 modules. Ces groupes sont numérotés de 0 à 25. Ainsi, le groupe 0 correspond au premier octet du message encodé, le groupe 1 au second et ainsi de suite.
Le groupes sont agencés selon la façon suivante :
Les groupes en rouge (00, 01, 02, 06, 07, 08, 12, 13, 14, 15, 16, 22, 24) sont en configuration montante, alors que les groupes en bleu (03, 04, 05, 09, 10, 11, 17, 18, 19, 20, 21, 23, 25) sont en configuration descendante. L'ordre des bits à l'intérieur d'un groupe dépend de la configuration du groupe.
Pour les groupes en configuration montante, les bits sont affichés de gauche à droite et de haut en bas, en commençant par le bit 0. Pour rappel, le bit 0 est le bit le plus à droite de l'octet.
À l'inverse pour les groupes en configuration descendante, les bits sont affichés de gauche à droite, mais de bas en haut, toujours en commençant par le bit 0.
En plus de cela, les groupe 15 et 18 sont particuliers: Ils sont traversés par les modules de cadencement.
L'image suivante récapitule le placement des bits en fonction des différents types de groupes :
Veuillez implémenter la logique de placement des modules de données dans la fonction placer_modules_donnees dans le fichier qr.py. La fonction prend en argument l'image img sur laquelle placer les modules, ainsi qu'une liste d'octets appelée octets. La signature de la fonction, que vous pouvez copier dans le fichier qr.py, est la suivante :
def placer_modules_donnees(img, octets):
passPour vous aider à implémenter cette fonction, nous vous suggérons de vous aider des fonctions auxiliaires suivantes, qu'il faudrait alors aussi implémenter :
def placer_octet_montant(img, octet, x, y):
pass
def placer_octet_descendant(img, octet, x, y):
pass
def placer_octet_montant_separe(img, octet, x, y):
pass
def placer_octet_descendant_separe(img, octet, x, y):
passChacune des fonctions sert à placer un type de groupe de module. Les coordonnées x et y correspondent aux coodonnées du module en haut à gauche du groupe. À l'intérieur de ces fonctions, vous pouvez faire usage de la fonction placer_module_donnee discutée plus haut.
Vous pouvez tester votre code en exécutant le script generer-qr.py avec l'argument --etape 3.
Le résultat attendu est le suivant:
Si vous scannez le QR-code obtenu, vous devriez normalement voir s'afficher le message Bravo !. Félicitations, votre programme vient de générer son premier QR-code !
Si vous obtenez un autre résultat, vous pouvez vous aider de l'option --numeros afin d'afficher les graduations d'axes sur les cotés du QR-code. Ce qui donne, pour une implémentation correcte:
Maintenant que nous avons implémenté la logique de placement des modules, il nous reste à encoder le message sous forme d'une suite d'octets, 26 dans notre cas. Dans cette partie, nous allons voir comment convertir le message que nous souhaitons mettre dans le QR-code en une séquence d'octets qui pourront ensuite être placés sur le QR-code en tant que modules.
Dans notre cas, ces 26 octets sont décomposés de la manière suivantes:
0b0100 ou 4, pour iso-8859-1).Ci-dessous sont présentés les 26 octets pour le message Bravo !.
La chaîne de caractère Bravo ! correspond, selon l'encodage iso-8859-1 qui est utilisé dans ce cas, à 7 octets, soit un par caractère du message.
Ces 7 octets apparaissent dans le message encodé après le mode (4) sur 4 bits et la longueur (7) sur 8 bits. À cause du demi-octet de décalage, les 7 octets du message en iso-8859-1 ne sont pas alignés avec les octets du message encodé.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]
0100 0000 0111 0100 0010 0111 0010 0110 0001 0111 0110 0110 1111 0010 0000 0010 0001 0000
[ 4] [ 7 ] [ B ] [ r ] [ a ] [ v ] [ o ] [ ␠ ] [ ! ] [ ] Ensuite viennent 10 octets de rembourrage afin que la longueur totale du message encodé fasse 26 octets (19 sans la correction d'erreur). Ces octets alternent entre 0b11101100 (236) et 0b00010001 (17). Ces valeurs sont spécifiées dans la norme pour les QR-codes et ne sont pas libres.
[ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ]
1110 1100 0001 0001 1110 1100 0001 0001 1110 1100 0001 0001 1110 1100 0001 0001 1110 1100 0001 0001
[ 236 ] [ 17 ] [ 236 ] [ 17 ] [ 236 ] [ 17 ] [ 236 ] [ 17 ] [ 236 ] [ 17 ]Ensuite arrivent les 7 octets de correction d'erreurs. Le calcul de la valeur de ces octets sera le sujet des deux prochaines étapes du projet.
[ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ]
1001 1010 1010 0111 0100 1000 0111 1011 0011 1010 1100 1101 1010 0000
[ 154 ] [ 167 ] [ 72 ] [ 123 ] [ 58 ] [ 205 ] [ 160 ]Pour cette partie, nous ne nous soucierons pas encore de la partie de correction d'erreurs, que nous aborderons dans les deux prochains jours. Nous nous concentrerons donc simplement sur les 18 premiers octets du message encodé.
Ouvrez le fichier encodeur.py et ajoutez-y la fonction suivante, qui est à compléter:
def encode_message(message):
bits = 0b0100 # Le mode d'encodage, sur 4 bits.
octets_message = message.encode('iso-8859-1')
longueur = len(octets_message)
if longueur > 17:
raise ValueError('Le message est trop long')
# Ajouter la longueur du message, sur 8 bits.
# Ajouter les octets du message.
# Ajouter 4 bits à zéro.
# Ajouter les octets de "rembourrage".
# Regroupement des bits en octets.
octets = []
for i in range(19):
octets.insert(0, bits & 255)
bits >>= 8
return octetsLe but de cette fonction est de prendre un message, sous forme de chaîne de caractères, et de le transformer en une liste d'octets.
Pour faciliter cette conversion, nous allons passer par une représentation intermédiaire des octets sous forme d'un nombre bits.
Ainsi, si vous souhaitez ajouter des bits à la fin de la séquence de bits, il suffit de décaler les bits sur la gauche d'un certain nombre de positions, puis d'affecter les derniers bits aux valeurs attendues.
bits <<= 8 # Décalage de 8 positions sur la gauche.
bits ^= 17 # Affectation des bits à droite à 0b10001 (= 17).Les quelques dernières lignes de la fonction encode_message servent à convertir ce nombre en liste d'octets. Vous n'avez pas besoin de modifier cette partie.
Le format QR-code supporte normalement différent mode d'encodage. Dans le cadre de ce projet, nous allons nous concentrer uniquement sur le mode d'encodage utilisé pour des textes sur un alphabète "latin", c'est à dire l'encodage iso-8859-1.
La première ligne de la fonction encode_message spécifie que la séquence de bits commence par 0b0100.
La longueur du message est ensuite à ajouter. Pour cela, il faut ajouter 8 bits à la fin de la séquence bits à l'aide du décalage à gauche, puis affecter ces derniers bits à la valeur attendue (ici la longueur du message) à l'aide, par exemple, de l'opération "ou-exclusif". La variable longueur contient la longueur du message.
Si cette longueur est supérieure à 17, alors une exception est lancée pour que le code s'arrête et reporte une erreur.
Ensuite, les octets du message sont ajoutés. Ces octets ont été obtenus par encodage en 'iso-8859-1'. Pour chaque octet, il faut décaler bits de 8 positions sur la gauche, puis d'affecter ces derniers bits aux bits de l'octet. Dans le code qui vous est fourni, la variable octets_message contient les octets du message.
Ensuite, 4 bits à 0 sont ajouté à la fin de bits.
Jusqu'à présent, nous avons ajouté (longueur + 2) octets (1 demi-octet pour le mode d'encodage, 1 octet pour la longueur du message, les octets du message, 1 demi-octet de 0). Si ce nombre d'octets ne correspond pas exactement au nombre d'octets attendus (19), il faut ajouter des octets de rembourage jusqu'à atteindre la longueur attendue. Les octets de rembourrage alternent entre 0b11101100 (= 236) et 0b00010001 (= 17). Cela signifie que le premier octet de rembourage est 236, puis le second 17, le troisième 236, etc. jusqu'à atteindre la longueur désirée (ici 19).
À la fin de cette troisième étape du projet, vous pouvez exécuter la commande suivante depuis le Terminal pour vérifier si vous avez bien implémenté les fonctionnalités attendues:
python -m unittest test.Etape3