Источник Habrahabr

Иногда возникают такие ситуации, когда нужно прочитать QR код, а смартфона под рукой нет. Что же делать? В голову приходит лишь попробовать прочитать вручную. Если кто-нибудь сталкивался с такими ситуациями или кому просто интересно как же читается QR код машинами, то данная статья поможет вам разобраться в этой проблеме.

В статье рассмотрены базовые особенности QR кодов и методика дешифрирования информации без использования вычислительных машин.

Решение задачи непосредственного чтения информации с QR-картинки рассмотрим на примере двух кодов.

Чтобы понять, как извлечь данные из кода, нужно разобраться в алгоритме. Существует несколько стандартов в семействе QR кодов, с их базовыми принципами можно ознакомиться в спецификациях. Кратко поясню: данные, которые необходимо закодировать, разбиваются на блоки в зависимости от режима кодирования. К разбитым по блокам данным прибавляется заголовок, указывающий режим и количество блоков. Существуют и такие режимы, в которых используется более сложная структура размещения информации. Данные режимы рассматривать не будем, в виду того, что извлекать вручную из них информацию нецелесообразно. Однако, основываясь на тех принципах, что описаны ниже, можно адаптироваться и к этим режимам.

На случай некорректного чтения данных в QR применяются специальные коды, которые способны исправить недочёты при чтении. Это так называемые коды Рида-Соломона. Принцип вычисления кодов, а также исправление ошибок в блоках информации рассматривать не будем, это тема отдельной статьи. Корректирующие ошибки коды Рида-Соломона (RS) записываются после всех информационных данных. Это очень упрощает задачу непосредственного чтения информации: можно просто считать данные, не трогая коды. Как показывает практика, обычно бОльшую часть QR -матрицы занимают корректирующие RS-коды.

По стандарту, данные с RS-кодами перед записью в картинку «перемешиваются». Для этих целей используют специальные маски. Существует 8 алгоритмов, среди которых выбирается наилучший. Критерии выбора основаны на системе штрафов, о которых можно также почитать в спецификации.

«Перемешанные» данные записываются в особой последовательности на шаблонную картинку, куда добавляется техническая информация для декодирующих устройств. Исходя из описанного алгоритма, можно выделить схему извлечения данных из QR кода:

Здесь зелёным фломастером подчёркнуты пункты, которые нужно будет реализовать при непосредственном чтении кода. Остальные пункты можно опустить в виду того, что считывание производит человек.

Шаг 0. QR код

Взглянув на картинки, можно заметить несколько отчётливых областей. Эти области используются для детектирования QR кода. Эти данные не представляют интереса с точки зрения записанной информации, но их нужно вычеркнуть или просто запомнить их расположение, чтобы они не мешали. Всё остальное поле кода несёт уже полезную информацию. Её можно разбить на две части: системная информация и данные. Также существует информация о версии кода. От версии кода зависит максимальный объём данных, которые могут быть записаны в код. При повышении версии – добавляются специальные блоки, например как здесь:

По ним можно сориентироваться и понять какая версия QR перед вами. Коды высоких версий обычно также нецелесообразно считывать вручную.

Размещение системной информации показано на рисунке:

Системная информация дублируется, что позволяет значительно понизить вероятность возникновения ошибок при детектировании кода и считывании. Системная информация – это 15 бит данных, среди которых первые 5 — это полезная информация, а остальные 10 – это BCH (15,5) код, который позволяет исправлять ошибки в системных данных. К классу BCH кодов относят и RS коды. Обратите внимание, что на рисунке две полоски по 15 бит не пересекаются.

Шаг 1. Чтение 5 бит системной информации

\ Как уже говорилось, интерес представляют только первые 5 бит.
Из которых 2 бита показывают уровень коррекции ошибок, а остальные 3 бита показывают какая маска из доступных 8 применяется к данным. В рассматриваемых QR кодах системная информация содержит:

Шаг 2. Маска для системной информации

Кроме уже озвученных схем зашиты системной информации, в добавок, используется статическая маска, которая применяется к любой системной информации.
Она имеет вид: 101010000010010.
Так как имеет интерес только первые 5 бит, то маску можно сократить и легко запомнить: 10101 (десять-сто один).
После применения операции «исключающего или» (xor) получаем информацию.

Возможные уровни коррекции ошибок:

L	01
M	00
Q	11
H	10

Возможные маски:

000	(i + j) mod 2 = 0
001	i mod 2 = 0
010	j mod 3 = 0
011	(i + j) mod 3 = 0
100	((i div 2) + (j div 3)) mod 2 = 0
101	(i j) mod 2 + (i j) mod 3 = 0
110	((i j) mod 2 + (i j) mod 3) mod 2 = 0
111	((i+j) mod 2 + (i j) mod 3) mod 2 = 0

Шаг 3. Чтение заголовка данных

Чтобы понять с какими данными предстоит иметь дело, необходимо изначально прочитать 4-х битный заголовок, который содержит в себе информацию о режиме. Специфика чтения данных изображена на картинке:

Список возможных режимов:

ECI	0111
Числовые	0001
Буквенно-числовые	0010
8-битный (байтный)	0100
Kanji	1000
Структурированное дополнение	0011
FNC1	0101 (1-я позиция) 1001 (2-я позиция)

Шаг 4. Применение маски к заголовку

После извлечения 4-х бит, описывающих режим, необходимо к ним применить маску.
В нашем случае для двух кодов используются разные маски. Маска определяется выражением, приведённым в таблице выше. Если данное выражение сводится к TRUE (верное) для бита с координатами (i,j), то бит инвертируется, иначе всё остаётся без изменений. Начало координат в левом верхнем углу (0,0). Взглянув на выражения, можно заметить в них закономерности. Для рассматриваемых QR кодов, маски будут выглядеть так:

Получим режимы:

Шаг 5. Чтение данных

После получения данных о режиме можно приступать к чтению информации. Надо оговорить, что наиболее интересно считывать числовые и буквенно-числовые данные, так как они легко интерпретируются. Но также не стоит бояться 8-битных. Это может быть также легко интерпретируемая информация. Например, многие онлайн генераторы QR текст кодируют в этом режиме, используя ASCII. Ещё одна причина, почему следует изначально прочитать режим это то, что от него зависит количество пакетов данных. Которая также зависит и от версии кода. Для версий с первой по девятую длины блоков для более читабельных режимов:

Числовые	10 бит / 4 бита
Буквенно-числовые	9 бит
8-битный (байтный)	8 бит

Первый блок после указателя режима – это количество символов. Для числового режима количество закодировано в 10 следующих битах, а для 8-битного режима в 8 битах (прошу прощения за тавтологию).

На рисунке видно, что в левом QR коде, как и отмечалось, записана цифра 5. Это видно по указателю количества символов и последующим после него 4 битам. В числовом режиме наряду с 10-битными блоками используются 4-х битные блоки для экономии места, если в 10-битном объёме нет необходимости. В правом коде, зашифровано 4 символа. На данный момент неизвестно, что зашифровано в нём. Поэтому необходимо перейти к чтению следующего столбца для извлечения всех 4-х блок информации.

На рисунке видно, все 4 пакета представляют собой коды ASCII латинских букв, образующие слово «habr»

Естественно наилучшим способом остаётся достать телефон из кармана и, наведя камеру на QR-картинку, считать всю информацию. Однако в экстренных случаях может пригодиться и описанная методика. Конечно, в голове не удержишь все указатели режимов и типов масок, а также ASCII символы, но популярные комбинации запомнить (хотя бы те, что рассмотрены в статье) под силу.

Спецификация:

BS ISO/IEC 18004:2006. Information technology. Automatic identification and data capture techniques. QR Code 2005 bar code symbology specification. London: BSI. 2007. p. 126. ISBN 978-0-580-67368-9.

P.S. Соблюдайте правила ресурса и условия Creative Commons Attribution 3.0 Unported (CC BY 3.0)