Lire un QR code sans ordinateur

 (qr.blinry.org)
4 points par GN⁺ 2024-01-23 | 1 commentaires | Partager sur WhatsApp
  • Présente une procédure pas à pas pour décoder un QR code à la main, depuis la structure 21×21 modules de la version 1 jusqu’au démasquage et à la conversion en octets
  • Les zones spéciales comme les motifs de repérage, les motifs de synchronisation, les informations de format et la quiet zone sont nécessaires à la reconnaissance, mais doivent être ignorées lors de la lecture des données elles-mêmes
  • Les données sont restaurées après avoir identifié le motif de masque et le niveau de correction d’erreurs dans les informations de format, puis en inversant les modules du QR code à chaque position où le masque contient un module noir
  • On commence en bas à droite et on lit deux colonnes à la fois en zigzag ; en mode Byte, les groupes de 8 bits qui suivent les 8 bits de longueur deviennent les octets des caractères
  • Il n’est pas nécessaire de résoudre à la main la zone de correction d’erreurs : pour un QR code simple, il suffit de lire autant d’octets qu’indiqué par le champ de longueur, puis de les convertir avec la table ASCII

Préparer un QR code à lire à la main

  • Il existe trois façons de préparer un QR code d’entraînement
    • Saisir un texte quelconque pour mettre à jour le QR code décrit ci-dessous
    • Scanner un QR code existant avec la caméra afin d’apprendre à le lire
    • S’entraîner avec un mot anglais aléatoire, le mot n’étant pas affiché afin de servir d’exercice
  • L’exemple de QR code mesure 21×21 modules
  • Dans un QR code, l’unité équivalente à un pixel s’appelle un module
  • La taille d’un QR code est distinguée par sa version
    • La plus petite version mesure 21×21 modules
    • À chaque version suivante, la longueur d’un côté augmente de 4
    • Un QR code de 21×21 modules est une version 1

Zones spéciales à ignorer dans un QR code

  • Les motifs de repérage (finder pattern) aident le scanner à identifier d’abord le QR code
  • Les lignes vides autour des motifs de repérage doivent être ignorées lors de la lecture du contenu
  • Un QR code de version 1 ne comporte pas de motif d’alignement (alignment pattern)
    • Le motif d’alignement est un motif supplémentaire qui aide le scanner à lire correctement le QR code
  • Les motifs de synchronisation (timing pattern) sont deux lignes où les modules noirs et blancs alternent toujours ; ils aident le scanner à lire correctement le QR code
  • Les informations de format déterminent le motif de masque et le niveau de correction d’erreurs
    • Il existe des informations de format verticales et horizontales
    • Le motif de synchronisation traverse en interrompant ces deux lignes
  • La quiet zone est la bordure blanche autour du QR code
    • Elle aide le scanner à identifier le début et la fin du QR code

Retirer le motif de masque

  • Les QR codes utilisent un masque (mask) pour éviter les grands blocs noirs ou blancs
  • Il existe au total 8 choix de masque
  • Dans l’exemple, on lit les modules noirs comme 1 et les modules blancs comme 0 pour vérifier les bits du motif de masque
    • Les bits de l’exemple sont le binaire 110
    • 110 correspond au nombre décimal 6
  • Chaque type de masque possède un motif prédéfini
  • Le motif du QR code d’exemple ressemble à une partie d’un arc-en-ciel noir et blanc
  • On place le masque de façon répétée sur la zone de données, puis on inverse les modules du QR code à chaque position où le masque contient un module noir
  • Un DIY zine contenant une antisèche pour tous les types de masque est fourni

Mode d’encodage et ordre de lecture

  • Le décodage du contenu commence par l’identification du mode d’encodage
  • L’information d’encodage se trouve toujours dans le coin inférieur droit
  • Le mode d’encodage doit lui aussi être d’abord démasqué en appliquant le masque
    • Dans l’exemple, on consulte l’antisèche et on applique un XOR aux deux cases
  • Les modes d’encodage comprennent notamment Numeric, Alphanumeric, Byte, ECI et Kanji
  • Le mode d’encodage du QR code d’exemple est Byte (4)
  • Le contenu commence dans le coin inférieur droit
    • On lit en remontant en zigzag entre deux colonnes
    • Puis on redescend en zigzag dans les deux colonnes suivantes à gauche
    • Toutes les zones spéciales sont toujours ignorées

Longueur et décodage des octets

  • Les 4 premiers bits indiquent le mode d’encodage
  • En mode Byte, les 8 bits suivants indiquent la longueur du contenu
  • Ensuite, chaque groupe de 8 bits devient un octet de contenu
  • L’information de longueur doit elle aussi être démasquée en appliquant le masque
  • Dans l’exemple, l’information de longueur démasquée est 00001100
    • En décimal, cela donne 12
    • Cela signifie que la longueur totale du contenu est de 12 octets
  • Le premier octet démasqué est 01001000
    • En hexadécimal, 0x48
    • Le caractère ASCII correspondant est H
  • Le deuxième octet démasqué est 01100101
    • En hexadécimal, 0x65
    • Le caractère ASCII correspondant est e
  • Les octets restants sont laissés comme exercice ; on peut s’arrêter après avoir lu le nombre de caractères indiqué par le champ de longueur lu précédemment

Table ASCII et correction d’erreurs

  • On peut utiliser la table ASCII pour convertir les valeurs hexadécimales en caractères
  • Les minuscules commencent avec a à 0x61 et se terminent avec z à 0x7A
    • Les caractères intermédiaires peuvent être trouvés en les comptant
  • Toutes les zones restantes ne sont pas du contenu
  • Les QR codes incluent aussi une correction d’erreurs (error correction)
    • Elle permet de lire le QR code même si certaines parties sont endommagées, floues ou manquantes
    • La correction d’erreurs est générée mathématiquement, mais elle n’est pas traitée dans le cadre d’une lecture à la main
  • Après avoir appris la procédure pour décoder à la main un QR code simple, on peut s’entraîner avec de courts mots anglais via le bouton de code aléatoire, ou scanner un vrai QR code avec le bouton Scan code
  • Le code source se trouve sur Codeberg
    • Les PR expliquant le mode d’encodage UTF-8 sont particulièrement bienvenues

À lire aussi

1 commentaires

 
GN⁺ 2024-01-23
Avis sur Hacker News

  • À la fin des années 90 ou au début des années 2000, je voulais transférer le contenu de disquettes Atari 8 bits vers un PC.
    Je connaissais le câble et le logiciel SIO2PC permettant de relier le port SIO de l’Atari au port série du PC, mais à l’époque je n’avais pas les compétences en électronique pour en fabriquer un moi-même.
    Au final, j’ai écrit un programme Basic sur l’Atari pour lire les disquettes secteur par secteur, afficher les données à l’écran sous forme de gros pixels en 4 couleurs en mode graphique 3, puis j’ai connecté l’Atari à la carte TV du PC et créé un programme Delphi qui prenait continuellement des captures d’écran pour décoder les données.
    Comme les secteurs vides décalaient la correction de position des pixels, j’ai ajouté un motif de masque, une somme de contrôle et même l’adresse du secteur, et avec cette méthode j’ai pu transférer tout le contenu de toutes les disquettes vers le PC.
    Encore aujourd’hui, je considère cela comme ma plus grande réussite d’ingénierie.
    Une dizaine d’années plus tard, j’ai créé un programme SIO2PC nommé AspeQt, et son fork communautaire plus récent, RespeQt, reste l’outil le plus utilisé dans ce domaine ; il a même un sous-forum dédié sur AtariAge : https://forums.atariage.com/forum/184-respeqt-sio2pc-softwar...

    • Cela me rappelle la manière dont le firmware et les clés de l’iPod de première génération ont été rétro-ingénierés.
      Apparemment, ils faisaient clignoter des motifs de bits avec le rétroéclairage LCD et lisaient ces données avec une caméra : https://mastodon.social/@bagder/111538350617290554
    • À mesure que les systèmes verrouillés deviennent plus courants, ce type d’exfiltration de données via l’affichage semble clairement avoir de l’avenir.

  • L’explication selon laquelle « la correction d’erreurs relève de mathématiques complexes, donc on ne s’en occupe pas pour une lecture à la main » mériterait un peu plus de détails.
    Je comprends que les maths soient difficiles, mais j’aimerais au moins savoir si les données de correction d’erreurs sont ajoutées à la fin, après chaque octet, ou insérées au milieu.
    J’aimerais aussi savoir si, pour un QR code intact, on peut quand même le lire à la main malgré la correction d’erreurs, en sautant simplement la partie mathématique.

    • Les codes-barres utilisent le dernier chiffre comme somme de contrôle : on additionne et multiplie les chiffres, puis on fait un calcul du type % 10 pour obtenir un chiffre entre 0 et 9.
      Il y a donc une probabilité de 1/10 que les données soient erronées mais que la somme de contrôle tombe quand même juste, et de toute façon le dernier chiffre n’est pas important pour l’identifiant unique réel du produit dans le code-barres.
      Un jour, le code-barres d’un article que je rapportais chez Home Depot était déchiré et le chiffre de somme de contrôle était abîmé ; j’ai essayé désespérément de le recalculer avant que l’employé ne fasse une recherche manuelle, mais l’employé a gagné, et je ne l’ai jamais oublié.
      https://www.gs1.org/services/how-calculate-check-digit-manua...
      https://www.simplybarcodes.com/barcode_check_digit_calculato...
    • Les données dans un QR code sont encodées sous forme de flux de bits dans l’un de plusieurs alphabets, les octets n’étant qu’un cas parmi d’autres.
      Ensuite, selon la taille et le niveau de correction d’erreurs, le flux de bits est divisé en blocs, les données de correction d’erreurs sont calculées pour chaque bloc, puis les blocs sont entrelacés.
      Cette méthode échoue donc au-delà de la version 5 des QR codes, quel que soit le niveau de correction d’erreurs, et échoue aussi pour les versions 3 à 5 si le niveau de correction d’erreurs est élevé.
    • An Artisanal QR Code montre comment calculer une somme de contrôle à la main avec une arithmétique proche de la division longue.
      En pratique, deux codes légèrement différents sont utilisés selon le type d’information : Reed-Solomon et BCH.
      https://www.quaxio.com/an_artisanal_qr_code.html

  • Articles liés :
    Decoding small QR codes by hand (2012) - https://news.ycombinator.com/item?id=36173441 - juin 2023, 69 commentaires
    How a QR code works - https://news.ycombinator.com/item?id=32837565 - septembre 2022, 114 commentaires
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=24119124 - août 2020, 41 commentaires
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=18360847 - novembre 2018, 34 commentaires

  • L’article lui-même est excellent, mais le fait que toutes les illustrations soient générées dynamiquement en fonction de l’entrée est encore plus impressionnant.

  • J’ai apprécié l’explication sur la manière de lire un QR code, et pour un article sur le décodage des codes-barres unidimensionnels courants comme les UPC, celui-ci est aussi pas mal :
    https://scanbot.io/blog/how-do-barcodes-work/

  • Il y a une dizaine d’années, j’ai essayé de lire un QR code à la main, mais j’ai abandonné à cause du motif de masquage
    Il faut appliquer ce motif de masquage par XOR avant même d’identifier le type de données
    Je me demande à quel point ce motif de masquage aide réellement les lecteurs de QR codes
    Le mois dernier, j’ai cherché les paramètres optimaux de correction d’erreurs, mais dans un cas non dégradé comme une matrice intacte affichée à l’écran, la réponse était « aucun », et cette conclusion n’a pas été facile à trouver
    Je n’ai pas trouvé de ressources comparant, en conditions réelles, différents réglages et différentes implémentations de scan ; j’ai donc affiché moi-même de petits QR codes à l’écran avec plusieurs niveaux de correction d’erreurs, puis j’ai secoué la caméra pour simuler des problèmes de lecture, mais je n’ai pas vu de différence significative entre les réglages
    Avec au moins quatre marqueurs d’alignement, une grande marge et même des motifs de synchronisation, je me demande si l’apparition d’un gros bloc blanc faute de masquage ferait vraiment une grande différence
    La deuxième raison pour laquelle j’ai renoncé à lire visuellement les QR codes, c’est que l’URL était généralement écrite en texte alternatif juste en dessous ; depuis, j’ai bien vu quelques cas sans texte alternatif, mais c’est très rare

    • La correction d’erreurs est étrange
      Si on ne l’utilise pas, le message prend moins de place et le QR code devient plus petit
      Quand il faut tenir dans un espace fixe, comme pour l’impression d’un autocollant, on peut rendre les pixels physiquement plus grands, et pour une lecture fiable, des pixels plus grands se sont révélés plus utiles que la correction d’erreurs
      Selon la longueur du message, il arrive qu’on puisse augmenter le niveau de correction d’erreurs sans changer la taille finale du QR code ; dans ce cas, on gagne sur les deux tableaux
    • La correction d’erreurs n’est pas faite pour les gens qui se demandent « comment rendre le message plus petit afin d’améliorer la lisibilité du QR code »
      Elle est faite pour ceux qui mettent une URL complète bourrée de paramètres de suivi dans un code version 25 de 117x117, l’affichent sur une grande enseigne, et veulent que les données survivent même si une fiente d’oiseau tombe dessus ou si quelqu’un y colle un autocollant
    • J’ai fait une expérience similaire l’an dernier, et au moins pour les QR codes imprimés en 3D, l’absence de correction d’erreurs était ce qui marchait le mieux
      L’expérience consistait à voir jusqu’à quelle petite taille ils restaient détectables, et comme le dit un commentaire voisin, cela semble dû au fait que chaque pixel devient plus grand

  • Une vidéo d’il y a environ 10 ans sur le décodage des QR codes : https://www.youtube.com/watch?v=KA8hDldvfv0 (20 min)
    J’ai aussi une page web interactive qui crée un QR code étape par étape. C’est essentiellement le processus inverse : https://www.nayuki.io/page/creating-a-qr-code-step-by-step

  • Je me suis intéressé à la correction d’erreurs, et il paraît que les QR codes peuvent être conçus avec un taux récupérable allant de 7 % à 30 %
    Intéressant : https://docs.beaconstac.com/en/articles/6018654-what-is-erro...

    • La correction d’erreurs est vraiment un sujet passionnant
      Shannon en a trouvé les limites théoriques au milieu du XXe siècle, mais personne ne savait comment les atteindre
      Dans les années 1990, les turbo codes brevetés se sont soudain approchés de cette limite, ce que le monde académique a eu du mal à croire
      Bien sûr, c’est grâce à ce genre de technologies que les réseaux mobiles rapides et fiables sont devenus possibles

  • Dans l’un des puzzles dérivés du Mystery Hunt 2023, il fallait décoder à la main un QR code tellement abîmé que même la correction d’erreurs ne pouvait pas le récupérer
    J’ai parcouru tous les guides mentionnés dans ces commentaires ; ils étaient utiles, mais pas excellents
    Je suis donc content de voir davantage d’articles plus détaillés comme celui-ci, et celui-ci semble clairement très abouti
    Si ça vous intéresse, le puzzle est ici, et le décodage du QR code intervient vers la fin : https://puzzles.mit.edu/2023/abcde.puzzlefactory.place/puzzl...

  • D’après Wikipedia, le QR code a été inventé en 1994 par un fabricant japonais de pièces automobiles pour étiqueter des pièces automobiles
    Je me demande s’il aurait pu être amélioré s’il avait été inventé aujourd’hui
    Aurait-on pu le rendre plus compact ou plus facile à lire ?

    • Rien n’empêche de concevoir quelque chose de nettement meilleur
      En 1994, les codes-barres étaient déjà partout, mais cela n’a pas empêché le QR code de s’imposer
      Peut-être qu’il n’y a pas tant de marge d’amélioration que ça, sauf à changer fortement de concept pour aller vers quelque chose comme le NFC
    • S’il avait été inventé aujourd’hui, il aurait probablement été hexagonal