Consignes

Le TP est à rendre, avant le mercredi 31 octobre minuit... (Attention, c'est pendant les vacances !)

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier .c contenant le code des fonctions demandées.

Vous pouvez utiliser le fichier Makefile fournit pour faciliter la compilation.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal.

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

votre fichier devra s'appeler "tp1-nom.c",
chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,
votre code doit compiler avec les options -Wall -Werror -Wextra -pedantic -std=c99,
une exécution des fonctions de test et de décodage / information du programme principal ne devra pas provoquer d'erreur sur les fichiers de test fournis.

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

l'architecture de votre programme (code découpé en fonctions etc.),
la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
la présence de commentaires aux endroits appropriés,
la présence de documentation pour vos fonctions.

Liens utiles

QR codes - partie 1 : décodage

Préliminaires

Les QR codes (Quick Response Codes) sont un type de code barres à 2 dimensions développés par Toyota en 1994. L'objectif original était de pouvoir suivre les pièces de véhicules (à travers notamment de numéros de séries) lors du processus de construction. Ils sont maintenant largement utilisés à des fins commerciales pour permettre aux utilisateurs de smartphone d'accéder facilement à des adresses web automatiquement. Les spécifications des QR codes font l'objet d'une norme ISO : ISO/IEC 18004:2006 et ils sont dans le domaine publique.

Par exemple, le QR code suivant contient le texte "INFO528 - TP1 : QR codes" :

Il existe d'autres types de codes barres bidimensionnels :

codes « Aztec » (norme ISO/IEC 24778:2008, domaine publique), utilisés par exemple sur les billets de train IDTGV,
« Data Matrix »,
« MaxiCode » (norme ISO/IEC 16023, domaine publique),
« PDF417 » (norme ISO 15438),
...

Tous ces codes incorporent des codes correcteurs d'erreurs permettant de retrouver l'information même lorsque qu'une partie du code est abimée / manquante. Par exemple, cette version du QR code précédent contient encore le texte "INFO528 - TP1 : QR codes" malgré la déformation et les parasites !

Dans ce TP, nous allons commencer par décoder les petits QR codes, sans nous occuper de la correction des erreurs. Les petits QR codes (version 1) peuvent uniquement contenir au plus 17 caractères ASCII, ou 25 caractères alphanumériques (lettres majuscules / chiffres / ponctuation) ou 41 chiffres. Voici quelques exemples :


ASCII	alphanumérique	chiffres
"`Vive les maths !`"	"`INFO428 : QRCODES / 2012`"	"`31415926535`"

Types de données

Le TP sera fait en utilisant le langage C. L'archive du TP contient quelques définitions de types et fonctions que vous devrez utiliser. Le fichier "qrcodes.h" contient les entêtes des fonctions avec des commentaires. Reportez vous y en cas de problèmes.

Les points importants sont :

la bibliothèque "netpbm" définit un type "bit" pouvant contenir "0" ou "1".
Un QR code sera représenté par un tableau de bits bidimensionnel, c'est à dire par un double pointeur. Le type "QRCode" est un synonyme pour ce type. Attention, un QR code est un tableau de lignes, ce qui implique que si "qr" est de type "QRCode", alors "qr[i][j]" est le bit contenu sur la ligne "i" et la colonne "j".
La fonction "alloc_qrcode" permet de réserver la mémoire pour un QR code. Elle prend la taille du QR code en argument. Dans notre cas, vous devrez utiliser la constante "SIZE_V1" comme taille (cette constante vaut 21 pour les QR codes de version 1).
N'oubliez pas de libérer la mémoire avec "free_qrcode" lorsque vous n'avez plus besoin d'un QR code.
Si vous disposez d'une image de QR code au format PBM, vous pouvez la convertir en un QR code avec la fonction "pbm_to_qrcode_version1". Reportez-vous aux commentaires dans le fichier "qrcodes.h" pour plus de détails
Vous pouvez créer des images de QR codes avec l'utilitaire "qrencode". Par exemple, l'exemple précédent à été créé avec
```
$ qrencode -o exemple-ASCII.png "info428 TP1 2012"
```
Reportez-vous au manuel de la commande "qrencode" pour plus de détails.
Attention, la commande "qrencode" crée des images au format PNG. Il faut donc les convertir au format PBM avec une commande supplémentaire :
```
$ convert exemple-ASCII.png exemple-ASCII.pbm
```
Réciproquement, la commande "qrcode_version1_to_pbm" permet de transformer un QR code (en C) en une image au format PBM.

Partie standard (fixe) du QR code

Les QR codes comportent tous des parties fixes qui ne contiennent aucune information. Pour les QR codes de version 1, les partie fixes, avec leurs couleurs, sont :

La fonction "check_fixed_bits_version1" compte le nombre d'erreurs dans les bits fixes. Elle prends en argument un "QRCode".

Complétez le code de la fonction

int check_fixed_bits_version1(QRCode qr);

Pour tester, vous devez :

modifier la fonction "do_test" du fichier "tests.c",
recompiler le programme,
lancer la commande
```
$ ./qrcodes -T
...
```

Par exemple, vous pouvez utiliser la fonction "do_test1". Vous devriez obtenir :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
nombre d'erreurs	0	3	0

Format du QR code

Récupérer les bits

Le format (taux de correction d'erreurs et numéro du masque à appliquer) est contenu sur 5 bits de données + 10 bits de redondance, soit un total de 15 bits numérotés de 0 à 14. Comme ces 15 bits sont très importants, il sont stockés à deux endroits dans le QR code :

Écrivez la fonction

void get_raw_format_bits(QRCode qr, bit format[2][15]);

Pour tester :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
`raw_format`-1	`110110001000001`	`111011111000110`	`001001110111110`
`raw_format`-2	`110110001000001`	`111011111000101`	`001001110111110`

Appliquer le masque

Pour éviter que les 15 bits de formats soit égales à 000000000000000 ou 111111111111111, on applique également un masque aux 15 bits du format avant de le stocker. Le masque appliqué est donné par 101010000010010 : le i-ème bit du format est modifié exactement lorsque le i-ème bit du masque est un "1".

Le plus simple pour appliquer un masque est d'utiliser l'opération XOR (notée "^" en C) entre les bits du format et les bits du masque. Ceci fonctionne car un XOR entre un bit b et "0" donne simplement b, alors qu'un XOR entre b et "1" renvoie le complément de b.

Complétez le corps de la fonction

void get_format_bits(QRCode qr, bit format[2][15]);

Pour tester :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
`raw_format`-1	`011100001010011`	`010001111010100`	`100011110101100`
`raw_format`-2	`011100001010011`	`010001111010111`	`100011110101100`

Vous pouvez utiliser la fonction "print_bits_array" (c.f. le fichier "qrcodes.h" pour afficher un tableau de bits.

Récupérer le taux de correction et le numéro du masque des données

Pour le moment, nous ne pouvons pas corriger les erreurs dans les 15 bits du format, mais nous pouvons repérer (au moins) une erreur en comparant les deux copies du format. Nous allons vérifier qu'il n'y a pas eu d'erreur et récupérer les bits 0 et 1 pour le taux de compression, ainsi que les bits 2, 3 et 4 pour le numéro du masque.

Pour transformer un tableau de 2 ou 3 bits en valeur de type "int", on peut :

traiter tous les cas possible un par un (mais ce n'est pas pratique si le tableau fait plus de 3 bits),
ou utiliser les opérations booléennes bit à bit : si "n" et "m" sont des entiers positifs,
- "m & n" est le et bit à bit entre "m" et "n" : 10 & 3 --> 2 car 10 est simplement 00001010 en base 2, et 3 est 00000011 en base 2, et on a
```
   00001010
 & 00000011  
------------
   00000010
```
- "m | n" est le ou bit à bit et "m ^ s" est le XOR bit à bit : 10 | 3 --> 11 et 10 ^ 3 --> 9
- "m<<i" est le décalage i fois à gauche, et m>>i est le décalage i fois à droite. Par exemple 11<<2 --> 44 et 11>>2 --> 2.

On peut transformer une suite b0, b1, b2, b3, b4 de bits en un nombre entier de la maniere suivante :

on part de n = 0, c'est à dire 00000000 en base 2,
on fait n = n | b4 pour mettre b4 dans le bit de poids faible de n,
on fait n = n | (b3<<1) pour mettre b3 dans le deuxième bit (en partant de la droite) de n,
on fait n = n | (b2<<2), puis n = n | (b1<<3) et enfin n = n | (b0<<4).

Écrivez la fonction correspondante :

 int get_format(QRCode qr, int *correction_level, int *mask);

Elle

vérifie que les deux copies du format sont identiques,
met le taux de correction dans "correction_level" et le numéro du masque dans "mask" (passage par adresse),
renvoie "-1" s'il y avait une erreur dans le format (deux copies non-identiques) et renvoie "0" sinon.

Attention à ne pas confondre les bits de poids faible et les bits de poids fort : si les bits 0 à 4 du format sont 10110, le taux de correction est 10, c'est à dire 2 et le numéro du masque est 110, c'est à dire 6.

Pour tester :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
formats identiques	oui	non	oui
taux / masque	1 / 6	1 / 0	2 / 1

Données du QR code

Masque

Comme le format, les données sont masquées pour éviter des grandes plages uniformes (et d'autres motifs qui pourraient empêcher de lire facilement le QR code). Alors que le format était toujours masqué avec le même masque, les données peuvent utiliser 8 masques différents :

bits masqués
masque	`000`	`001`	`010`	`011`
formule	`(i+j)%2 == 0`	`i%2 == 0`	`j%3 == 0`	`(i+j)%3 == 0`

bits masqués
masque	`100`	`101`	`110`	`111`
formule	`(i/2+j/3)%2 == 0`	`(ij)%2+(ij)%3 == 0`	`((ij)%3+ij)%2 == 0`	`((i*j)%3+i+j)%2== 0`

Programmez la fonction

void data_mask(QRCode qr, int m);

qui applique le masque approprié sur le QR code "qr".

Remarque : comme on ne se servira plus du format ou des parties fixes du QR code, on peut masquer le QR code entier sans se préoccuper des coordonnées.

Pour tester :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
fichier masqué

Récupération des octets

La zone de données d'un QR code est découpé en octet que l'on lit de la manière suivante :

Notez bien les points suivants :

les octets ne sont pas lu de la même manière en montant et en descendant,
il y a deux octets qui sont découpés en deux parties,
le premier bit (en bas à droite) correspond au bit de poids fort du l'octet numéro 0.

Le type "byte" est défini comme un synonyme de unsigned char. Il s'agit donc simplement d'un nombre entre 0 et 255, codé sur 8 bits. On peut facilement convertir un tableau de 8 bits en un octet avec les opérations bit à bit en utilisant la méthode détaillée plus haut.

Programmer les deux fonctions (très similaires) qui permettent de récupérer un octet de données.

byte get_upward_byte(QRCode qr, int i, int j);
byte get_downward_byte(QRCode qr, int i, int j);

Les arguments "i" et "j" correspondent aux coordonnées (ligne/colonne) du bit en haut à gauche du rectangle correspondant à l'octet. Par exemple, pour lire le premier octet, on appellera la fonction "get_upward_byte avec i=17 et j=19.

Attention, n'oubliez pas les deux cas particuliers où l'octet est découpé en deux morceaux. Ils correspondent aux cas où i==4 et j==11 (en montant) et i==4 et j==9 en descendant.

Vous pouvez maintenant utiliser la fonction

void get_data_bytes(QRCode qr, byte *data);

(déjà définie) pour lire tous les octets d'un QR code. (Cette fonction appelle les fonctions "get_upward_byte" et "get_downward_byte".)

Pour tester :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
données	`41 05 66 97 66 52 06 c6 57 32 06 d6 17 46 87 32 02 10 ec a6 2a c7 d8 91 0a e6`	`20 c3 41 57 62 d8 c6 7e 09 5a 8d 12 bd 10 f6 61 68 17 80 7d 66 85 bb 5c 3b bc`	`10 2d 3a 27 d0 94 60 ec 11 61 7a 85 11 1f fd 16 b0 29 47 41 72 7b 42 bc 84 6e`

Décodage

La macro "BIT(u,i)" permet de récupérer le i-ème bit (en partant de la droite) d'un nombre positif u. Par exemple, BIT(10,0) --> 0 et BIT(10,1) --> 1 car 10 est 00001010 en base 2. Cette macro est définie dans qrcodes.h comme un synonyme de u>>i & 1.

Nous allons avoir besoin de récupérer des bits arbitraires dans un tableau d'octets. Il faut donc aller chercher le bit approprié dans la case appropriée :

Écrivez la fonction

bit get_bit(const byte *data, int nb) ;

qui donne le nb-ème bit de données.

Attention, à l'intérieur d'un octet, les bits sont numérotés à partir de la gauche ! Pour obtenir le tout premier bit de données, il faut donc utiliser BIT(data[0],7).

Il est maintenant facile de récupérer quelques bits au milieu des données et de les combiner en un nombre entier comme vu plus haut (avec les opérations bit à bit).

Écrivez la fonction

unsigned int get_bits(const byte *data, int offset, int nb);

qui renvoie l'entier correspondant aux nb bits commençant à offset dans les données.

Par exemple, pour récupérer le mode de codage (4 premiers bits), il faudra appeler

  code = get_bits(data, 0, 4);

et dans le cas d'octets, pour récupérer le nombre d'octets (taille du message, codée sur 8 bits), il faudra faire

  taille = get_bits(data, 4, 8);

Les premiers bits de données donnent :

le mode de codage (ASCII, alphanumérique ou numérique) sur 4 bits,
le nombre de caractères codés dans ce mode sur :
- 8 bits pour l'ASCII,
- 9 bits pour l'alphanumérique,
- 10 bits pour le numérique.

Les fonctions

int get_mode(const byte *data, int offset);
int get_length(const byte *data, int offset, int m);

sont déjà écrites : elles permettent de récupérer le mode de codage ainsi que le nombre de caractères du message. Le paramètre "offset" peut être ignoré pour le moment : il doit valoir 0 pour toutes les applications de ce TP.

Pour tester :


fichier	`exemple-ASCII.pbm`	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
mode / taille	4 / 16	2 / 24	1 / 11

Nous avons maintenant tous les ingrédients nécessaires pour récupérer le message complet : il suffit d'appeler la fonction get_bits(data, ..., 8) pour récupérer chaque octet au bon endroit dans les données.

Attention : pour l'ASCII, les vraies données commencent au bit 12, car les bits de 0 à 11 servent à donner le mode et le nombre de caractères. Le premier octet de données est donc obtenu avec get_bits(data, 12, 8).

Écrivez la fonction

char *decode_bytes(const byte *data, int offset, int nb);

qui va chercher chaque charactère (octet) dans les données et renvoie la chaine de caractères correspondante.

Attention, la chaine de caractères "result" doit être allouée dans la fonction, et sa taille est nb+1 car le dernier octet d'une chaine est forcément le caractère nul ("'\0'"). N'oubliez donc pas de mettre ce caractère en fin de chaine !

Pour tester :


fichier	`exemple-ASCII.pbm`
message	"`Vive les maths !`"

(Bonus)

Écrivez les fonction permettant de décoder le mode numérique et le mode alphanumérique

char *decode_numeric(const byte *data, int offset, int nb);
char *decode_alphanumeric(const byte *data, int offset, int nb);

Note : le codage des modes numérique et alpha-numérique est expliqué en commentaire dans le corps des fonctions "decode_numeric" et "decode_alphanumeric".

Pour tester :


fichier	`exemple-alphanumerique.pbm`	`exemple-numerique.pbm`
message	"`INFO428`"	"`31415926535`"

(Bonus)

Après un message de taille t, il peut y avoir une suite codée avec un autre mode. Il suffit de prendre les 4 bits suivant pour avoir le mode et continuer comme précédemment. Lorsque le mode devient "0000", c'est que le message est vraiment fini.

Modifier la fonction

char *decode_bytes(const byte *data, int offset, int nb);

pour qu'elle décode aussi les messages multi-modes.

Pour tester :


fichier	`exemple-2modes.pbm`
message	"`info428 TP1 2012`"

Fonction principale

La fonction principale a deux modes de fonctionnement :

le mode décodage, activé avec l'argument "-d",
le mode informatif, activé avec l'argument "-i".

Vous pouvez utiliser l'argument "-h" pour avoir un petit message d'aide sur les autres arguments.

Le mode de décodage appelle la fonction "decode_file" et le mode informatif appelle la fonction "info_file"...

Complétez les deux fonctions

void info_file(const char *filename, int margin_size, int module_size);
void decode_file(const char *filename, int margin_size, int module_size);

et testez le programme sur des petits QR codes que vous générerez avec la commande "qrencode".

TP1 : décodage des QR code (version 1)

info-528 : mathématiques pour l'informatique

Hivers 2012

Consignes

Liens utiles

QR codes - partie 1 : décodage

Préliminaires

Types de données

Partie standard (fixe) du QR code

Format du QR code

Récupérer les bits

Appliquer le masque

Récupérer le taux de correction et le numéro du masque des données

Données du QR code

Masque

Récupération des octets

Décodage

Fonction principale