A tecnologia para ler códigos QR sem computador

 (qr.blinry.org)
4 pontos por GN⁺ 2024-01-23 | 1 comentários | Compartilhar no WhatsApp
  • O texto organiza um procedimento passo a passo para decodificar um QR Code versão 1 com estrutura de 21×21 módulos manualmente, desde a remoção da máscara até a conversão em bytes
  • Áreas especiais como finder pattern, timing pattern, informações de formato e quiet zone são necessárias para o reconhecimento, mas devem ser ignoradas na leitura dos dados
  • Os dados são restaurados verificando o padrão de máscara e o nível de correção de erros nas informações de formato, e então invertendo os módulos do QR Code onde a máscara tem módulos pretos
  • A leitura começa no canto inferior direito em ordem de zigue-zague de duas colunas por vez e, no modo Byte, os grupos de 8 bits após os 8 bits de comprimento se tornam bytes de caracteres
  • Não é necessário resolver manualmente a área de correção de erros; em QRs simples, basta ler a quantidade de bytes indicada pelo campo de comprimento e converter usando a tabela ASCII para decodificar

Preparando um QR Code para ler à mão

  • Há três formas de preparar um QR Code para praticar
    • Inserir um texto qualquer para atualizar o QR Code explicado abaixo
    • Escanear um QR Code existente com a câmera para aprender como ler
    • Praticar com palavras aleatórias em inglês, que não são exibidas e podem ser usadas para treinamento
  • O QR Code de exemplo tem tamanho 21×21 módulos
  • No QR Code, a unidade correspondente a um pixel é chamada de módulo (module)
  • O tamanho do QR Code é classificado por versão (version)
    • A menor versão tem 21×21 módulos
    • Depois disso, cada versão aumenta 4 unidades em cada lado
    • Um QR Code de 21×21 módulos é a versão 1

Áreas especiais a ignorar no QR Code

  • O finder pattern ajuda o scanner a identificar primeiro o QR Code
  • A linha vazia ao redor do finder pattern deve ser ignorada ao ler o conteúdo
  • O QR Code versão 1 não tem alignment pattern
    • O alignment pattern é um padrão adicional que ajuda o scanner a ler o QR Code corretamente
  • O timing pattern consiste em duas linhas em que módulos pretos e brancos sempre se alternam, ajudando o scanner a ler o QR Code corretamente
  • As informações de formato determinam o padrão de máscara e o nível de correção de erros
    • Há informações de formato na vertical e na horizontal
    • O timing pattern atravessa e interrompe essas duas linhas
  • A quiet zone é a borda branca ao redor do QR Code
    • Ela ajuda o scanner a identificar o começo e o fim do QR Code

Removendo o padrão de máscara

  • O QR Code usa uma máscara (mask) para evitar grandes blocos pretos ou brancos
  • Existem 8 opções de máscara ao todo
  • No exemplo, lê-se módulo preto como 1 e módulo branco como 0 para verificar os bits do padrão de máscara
    • Os bits de exemplo são 110
    • 110 corresponde ao decimal 6
  • Cada tipo de máscara tem um padrão predefinido
  • O padrão do QR Code de exemplo parece parte de um arco-íris em preto e branco
  • Depois de posicionar a máscara repetidamente sobre a área de dados, invertem-se os módulos do QR Code nas posições em que a máscara tem módulos pretos
  • É fornecido um DIY zine com uma folha de consulta de todos os tipos de máscara

Modo de codificação e ordem de leitura

  • A decodificação do conteúdo começa verificando primeiro o modo de codificação
  • A informação de codificação fica sempre no canto inferior direito
  • O modo de codificação também precisa ser desfeito aplicando primeiro a máscara
    • No exemplo, consulta-se a folha de referência e faz-se XOR entre os dois blocos
  • Entre os modos de codificação estão Numeric, Alphanumeric, Byte, ECI e Kanji
  • O modo de codificação do QR Code de exemplo é Byte (4)
  • O conteúdo começa no canto inferior direito
    • Lê-se subindo em zigue-zague entre duas colunas
    • Depois, continua-se descendo em zigue-zague nas próximas duas colunas à esquerda
    • Todas as áreas especiais são sempre ignoradas

Decodificando comprimento e bytes

  • Os primeiros 4 bits são o modo de codificação
  • No modo Byte, os 8 bits seguintes indicam o comprimento do conteúdo
  • Depois disso, cada 8 bits formam um byte do conteúdo
  • A informação de comprimento também precisa ser desfeita aplicando a máscara
  • No exemplo, a informação de comprimento sem máscara é 00001100
    • Em decimal, 12
    • Isso significa que o conteúdo total tem 12 bytes
  • O primeiro byte sem máscara é 01001000
    • Em hexadecimal, 0x48
    • O caractere ASCII correspondente é H
  • O segundo byte sem máscara é 01100101
    • Em hexadecimal, 0x65
    • O caractere ASCII correspondente é e
  • Os bytes restantes ficam como prática, e é possível parar ao ler a quantidade de caracteres indicada pelo campo de comprimento lido anteriormente

Tabela ASCII e correção de erros

  • É possível usar a tabela ASCII para converter valores hexadecimais em caracteres
  • As letras minúsculas começam com a em 0x61 e terminam com z em 0x7A
    • Os caracteres intermediários podem ser encontrados contando
  • Nem toda a área restante é conteúdo
  • O QR Code também inclui correção de erros (error correction)
    • Isso permite ler o QR Code mesmo se parte dele estiver danificada, borrada ou faltando
    • A correção de erros é gerada por matemática, mas não é tratada aqui para o objetivo de leitura manual
  • Depois de aprender o procedimento para decodificar manualmente um QR Code simples, é possível praticar palavras curtas em inglês com o botão de código aleatório ou escanear um QR Code real com o botão Scan code
  • O código-fonte está no Codeberg
    • PRs explicando especialmente o modo de codificação UTF-8 são muito bem-vindos

Leituras relacionadas

1 comentários

 
GN⁺ 2024-01-23
Opiniões no Hacker News

  • No fim dos anos 90 ou começo dos anos 2000, eu queria transferir o conteúdo de discos Atari de 8 bits para um PC
    Eu conhecia o cabo SIO2PC e o software que conectavam a porta SIO do Atari à porta serial do PC, mas na época não tinha conhecimento de eletrônica para fazer isso por conta própria
    No fim, escrevi um programa em Basic no Atari para ler o disco setor por setor e desenhá-lo na tela com pixels grandes de 4 cores no modo gráfico 3; conectei o Atari à placa de TV do PC e fiz um programa em Delphi tirar screenshots continuamente para decodificar os dados
    Como setores vazios faziam a correção de posição dos pixels sair do alinhamento, incluí um padrão de máscara, checksums e até endereços de setores; com esse método consegui transferir todo o conteúdo dos discos para o PC
    Ainda hoje considero isso minha maior realização de engenharia
    Cerca de 10 anos depois, criei um programa SIO2PC chamado AspeQt; um fork mais recente da comunidade, o RespeQt, ainda é a ferramenta mais usada nessa área e há até um subfórum dedicado no AtariAge: https://forums.atariage.com/forum/184-respeqt-sio2pc-softwar...

    • Isso me lembra a forma como fizeram engenharia reversa do firmware e das chaves do iPod de 1ª geração
      Dizem que fizeram a luz de fundo do LCD piscar padrões de bits e leram esses dados com uma câmera: https://mastodon.social/@bagder/111538350617290554
    • À medida que sistemas bloqueados se tornam mais comuns, esse tipo de exfiltração de dados baseada em display claramente parece ter futuro

  • A explicação de que “correção de erros é matemática complicada, então não nos preocupamos com isso na leitura manual” deveria ter mais detalhes
    Entendo que a matemática seja difícil, mas gostaria de saber ao menos se os dados de correção de erros ficam anexados no fim, depois de cada byte ou no meio
    Também queria saber se, em um QR code sem danos, mesmo com correção de erros, dá para lê-lo manualmente simplesmente pulando a parte matemática

    • Códigos de barras usam o último dígito como checksum; somam e multiplicam os números e fazem algum cálculo como % 10, resultando em um valor de 0 a 9
      Então há 1 chance em 10 de os dados estarem errados e, por acaso, o checksum ainda bater; de todo modo, o último dígito não é importante para o ID único real do código de barras do produto
      Uma vez, em uma devolução na Home Depot, o código de barras de um item estava rasgado e o dígito do checksum tinha se desgastado; tentei desesperadamente calculá-lo antes que o funcionário fizesse a consulta manual, mas no fim ele ganhou, e nunca esqueci isso
      https://www.gs1.org/services/how-calculate-check-digit-manua...
      https://www.simplybarcodes.com/barcode_check_digit_calculato...
    • Os dados dentro de um QR code são codificados como um fluxo de bits em um entre vários alfabetos, e bytes são apenas uma dessas opções
      Em seguida, dependendo do tamanho e do nível de correção de erros, o fluxo de bits é dividido em blocos; os dados de correção de erros são calculados para cada bloco e então os blocos são intercalados
      Por isso, esse método falha acima da versão 5 de QR independentemente do nível de correção de erros, e também falha nas versões 3 a 5 se o nível de correção de erros for alto
    • An Artisanal QR Code mostra como calcular o checksum manualmente com uma aritmética parecida com divisão longa
      Na prática, são usados dois códigos ligeiramente diferentes, Reed-Solomon e BCH, dependendo do tipo de informação
      https://www.quaxio.com/an_artisanal_qr_code.html

  • Posts relacionados:
    Decoding small QR codes by hand (2012) - https://news.ycombinator.com/item?id=36173441 - junho de 2023, 69 comentários
    How a QR code works - https://news.ycombinator.com/item?id=32837565 - setembro de 2022, 114 comentários
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=24119124 - agosto de 2020, 41 comentários
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=18360847 - novembro de 2018, 34 comentários

  • O texto em si já é excelente, mas o fato de todas as imagens serem geradas dinamicamente conforme a entrada é ainda mais bacana

  • Gostei da explicação sobre como ler QR codes, e este também é um bom texto para decodificar códigos de barras unidimensionais comuns, como UPC:
    https://scanbot.io/blog/how-do-barcodes-work/

  • Há uns 10 anos, tentei ler um QR code à mão, mas desisti por causa do padrão de máscara
    Mesmo antes de descobrir o tipo de dado, é preciso aplicar o padrão de máscara com XOR
    Fico curioso sobre o quanto esse padrão de máscara realmente ajuda em leitores de QR code de verdade
    No mês passado, fui procurar as configurações ideais de correção de erros, mas, em casos sem danos, como uma matriz íntegra exibida na tela, a resposta era “nenhuma”, e não foi fácil chegar a essa conclusão
    Não encontrei materiais comparando várias configurações e implementações de escaneamento em ambientes reais; eu mesmo exibi pequenos QRs na tela com vários níveis de correção de erros e balancei a câmera para simular problemas de leitura, mas não vi diferença significativa entre as configurações
    Com pelo menos quatro marcadores de alinhamento, margens grandes e até padrões de temporização, fico me perguntando se a falta de máscara, criando blocos brancos, realmente faria uma diferença tão grande
    O segundo motivo pelo qual desisti de tentar ler QRs visualmente foi que, em geral, o URL estava escrito abaixo como texto alternativo; depois disso, até vi alguns casos sem texto alternativo, mas foram raríssimos

    • Correção de erros é estranha
      Se você não a usa, a mensagem ocupa menos espaço e o QR fica menor
      Se for preciso caber em um espaço fixo, como na impressão de adesivos, dá para tornar os pixels fisicamente maiores, e, para uma leitura confiável, pixels maiores ajudaram mais do que a correção de erros
      Dependendo do tamanho da mensagem, há casos em que é possível aumentar o nível de correção de erros sem alterar o tamanho final do QR; aí você ganha os dois
    • A correção de erros não é para quem está pensando “como faço para deixar a mensagem menor e aumentar a legibilidade do QR code?”
      Ela é para quem coloca um URL inteiro cheio de parâmetros de rastreamento em um código versão 25, 117x117, põe isso em uma placa grande e quer que os dados sobrevivam mesmo que caia cocô de passarinho ou alguém cole um adesivo por cima
    • Fiz um experimento parecido no ano passado e, pelo menos em QR codes impressos em 3D, a melhor opção foi não usar correção de erros
      Era um experimento para ver até que tamanho pequeno ainda dava para detectar, e, como no comentário ao lado, parece ser porque os pixels individuais ficam maiores

  • Um vídeo de decodificação de QR de cerca de 10 anos atrás: https://www.youtube.com/watch?v=KA8hDldvfv0 (20 min)
    Também tenho uma página web interativa que cria QR codes passo a passo. Basicamente, é o processo inverso: https://www.nayuki.io/page/creating-a-qr-code-step-by-step

  • Fiquei curioso sobre correção de erros, e dizem que QR codes podem ser projetados com diferentes taxas recuperáveis, de 7% a 30%
    Interessante: https://docs.beaconstac.com/en/articles/6018654-what-is-erro...

    • Correção de erros é um tema realmente interessante
      Shannon descobriu os limites teóricos em meados do século 20, mas ninguém sabia como chegar a esses limites
      Quando, nos anos 1990, as patentes de códigos turbo de repente chegaram perto desses limites, a academia reagiu com descrença
      Claro que tecnologias assim tornaram possíveis redes móveis rápidas e confiáveis

  • Em um dos puzzles derivados do Mystery Hunt de 2023, havia um problema em que era preciso decodificar à mão um QR code danificado a ponto de nem a correção de erros conseguir recuperá-lo
    Consultei todos os guias mencionados nesta seção de comentários e eles foram úteis, mas não excelentes
    Por isso, é bom ver textos mais detalhados como este aparecendo, e este artigo certamente parece bem completo
    Se tiver curiosidade, o puzzle está aqui, e a decodificação do QR aparece na parte final: https://puzzles.mit.edu/2023/abcde.puzzlefactory.place/puzzl...

  • Pela Wikipedia, o QR code foi inventado em 1994 por uma fabricante japonesa de autopeças para etiquetar peças de automóveis
    Fico curioso se, caso fosse inventado hoje, ele poderia ter sido melhorado
    Daria para torná-lo menor ou mais fácil de ler?

    • Nada impede um novo projeto suficientemente melhor
      Em 1994, códigos de barras já estavam por toda parte, mas isso não impediu o QR code de se popularizar
      Talvez simplesmente não haja muito espaço para melhorias, a menos que se mude bastante o conceito e se vá para algo como NFC
    • Se fosse inventado hoje, acho que seria hexagonal