Алгоритм генерации QR-кода

QR код — это монохромная картинка, на которой некоторые устройства (например смартфон со специальным приложением) распознают текст. Этим текстом может быть не только простая фраза, но и, хоть это и не входит в официальную спецификацию, ссылка, номер телефона или визитная карточка. Такие коды чаще всего используют, чтобы закодировать ссылку и распечатать её на плакате или визитке.

Эта статья — подробная инструкция по созданию QR кода с примерами на каждом шаге, которая требует от вас только базового умения работать с бинарными данными и владения любым языком программирования (если вы хотите создать автоматический генератор QR кода).

За основу этой статьи взят цикл статей «QR Code Demystified» Джейсона Брауна (Jason Brown). В этих статьях опущено много нюансов, что вызвало у меня некоторые проблемы. Все эти нюансы учтены и упомянуты здесь.



Процесс генерации QR кода делится на несколько чётких шагов:

1. Кодирование данных.
2. Добавление служебной информации и заполнения.
3. Разделение информации на блоки.
4. Создание байтов коррекции.
5. Объединение блоков.
6. Размещение информации на QR коде.

Кодирование данных

QR код поддерживает несколько способов кодирования данных, в зависимости от того, какие символы используются: цифровое, буквенно-цифровое, кандзи (китайско-японские иероглифы) и побайтовое кодирование. Цифровое кодирование подразумевает использования только цифр от 0 до 9, буквенно цифровое — прописные буквы латинского алфавита, цифры и символы $%*+-./: и пробел, кандзи я рассматривать не буду, а байты кодирования не требуют вообще. Сначала вам надо создать пустую последовательность бит, которая дальше будет заполняться.

Цифровое кодирование

Этот тип кодирования требует 10 бит на 3 символа. Вся последовательность символов разбивается на группы по 3 цифры, и каждая группа (трёхзначное число) переводится в 10-битное двоичное число и добавляется к последовательности бит. Если общее количество символов не кратно 3, то если в конце остаётся 2 символа, полученное двузначное число кодируется 7 битами, а если 1 символ, то 4 битами.

Например, есть строка «12345678», которую надо закодировать. Мы разбиваем её на числа: 123, 456 и 78, затем переводим каждое из них в двоичный вид: 0001111011, 0111001000 и 1001110, и объединяем это в один поток: 000111101101110010001001110.

Буквенно-цифровое кодирование

В этом случае на 2 символа требуется 11 бит информации. Входной поток символов разделяется на группы по 2, в группе каждый символ кодируется согласно таблице внизу, значение первого символа в группе умножается на 45 и прибавляется к значение второго символа. Полученное число переводится в 11-битное двоичное число и добавляется к последовательности бит. Если в последней группе 1 символ, то его значение сразу кодируется 6-битным числом и добавляется к последовательности бит.



Например, строка «HELLO» кодируется следующим образом. Разбиваем на группы: HE, LL, O; находим соответствующее значение символам в каждой группе: (17, 14), (21, 21), (24); находим значение для каждой группы: 17 * 45 + 14 = 779, 21 * 45 + 21 = 966, 24 = 24; переводим каждое значение в двоичный вид: 779 = 01100001011, 966 = 01111000110, 24 = 011000; и объединяем всё это в одну последовательность бит: 0110000101101111000110011000.

Побайтовое кодирование

Это универсальный способ кодирования, которым можно закодировать любые символы. Единственным недостатком метода является относительно низкая плотность информации. В этом случае текст кодируется в любой кодировке (рекомендуемо в UTF-8) и полученная последовательность байт берётся в неизменном виде.

Например, строка «Хабр», закодированния кодировкой UTF-8, состоит из следующих байт: 11010000, 10100101, 11010000, 10110000, 11010000, 10110001, 11010001 и 10000000. Их надо просто объединить в один поток бит: 1101000010100101110100001011000011010000101100011101000110000000.

Добавление служебной информации

На этом этапе надо определиться с уровнем коррекции: чем выше этот уровень, тем выше допустимый уровень повреждения изображения и тем меньше информации при равном размере. Всего есть 4 уровня корекции: L (допустимо максимум 7% повреждений), M (15%), Q (25%) и H (30%). Чаще всего используется уровень M. Если вы хотите добавить на QR код свой рисунок (на Хабре есть несколько статей на эту тему), то используйте уровень H.

Ещё одно свойство QR кода — его версия (чем она больше, тем больше размер). Всего существует 40 версий. Номер версии зависит от количества кодируемой информации и от уровня коррекции. В таблице 2 указано максимальное количество полезной информации вместе со служебной (в битах), которое можно закодировать в QR коде этой версии. Из этой таблицы определется версия нашего QR кода.

Добавление служебных полей

К этому моменту уже должен быть выбран уровень коррекции и определена версия. Теперь надо перед последоветельностью бит, полученной в предыдущем пункте, добавить в начале два поля: способ кодирования и количество данных. Способ кодирования — поле длиной 4 бита, которое имеет следующие значения: 0001 для цифрового кодирования, 0010 для буквенно-цифрового и 0100 для побайтового. Количество данных — это количество кодируемых символов, а для побайтового — количество байт (а не бит в полученной последовательности), представленное в виде двоичного числа определённой длины (определяется по таблице 3).



Например, дана строка длиной 100 байт, закодированная побайтово, уровень коррекции — M. Длина последовательности бит этой строки — 800 бит. Воспользовавшись таблицей 2 можно определить, что оптимальнее всего будет использовать 6-ю версию. Длина поля, определяющего количество данных в нашем случае — 8 бит (таблица 3). Поле, определяющее способ кодирование имеет вид 0100, поле количества данных — 01100100 (100 в двоичном виде). В итоге получится последовательность бит 010001100100<исходная последовательность>.

Если длина полученной последовательности бит оказалась больше допустимой для выбранной версии, то версию надо увеличить на одну и проделать добавление служебных полей заново.

Спецификация допускает использование смешанного кодирования. Это значит, что несколько групп данных можно закодировать разными способами и объединить их в одну последовательность. Это делается следующим образом: <способ кодирования данных 1><количество данных 1><данные 1><способ кодирования данных 2><количество данных 2><данные 2> и так далее.

Заполнение

На данном этапе у нас есть последовательность бит данных, количество бит в которой наверняка не кратно 8. Надо дополнить её нулями так, чтобы её длина стала кратна 8. Теперь нашу последовательность бит можно разбить на группы по 8 бит и представить в виде последовательности байт (далее мы так и будем делать). Если количество бит в текущей последовательности байт меньше того, которое нужно для выбранной версии, то её надо дополнить чередующимися байтами 11101100 и 00010001. Таким образом, у нас получилась последовательность байт, длина которой соответствует выбранной версии QR кода.

Пример. Есть последовательность: <последовательность бит, длина которой кратна 8> 10101011101; дополняем её нулями, чтобы её длина стала кратна 8: <последовательность бит, длина которой кратна 8> 10101011101 00000; теперь предположим, что её длина — 104 бита, а для выбранной версии необходимо 128 бит, тогда для заполнения нужно добавить 24 «заполняющих» бита (3 байта): <последовательность бит, длина которой кратна 8> 10101011101 00000 11101100 00010001 11101100. Готово.

Разделение информации на блоки

Последовательность байт, полученная на предыдущем этапе, (далее данные) разделяется на обределённое для версии и уровня коррекции количество блоков, которое приведено в таблице 4. Если количество блоков равно одному, то этот этап можно пропустить.

Определение количество байт в каждом блоке

Для этого надо разделить всё количество байт (можно определить количество байт в данных или разделить число из таблицы 2 на восемь) на количество блоков данных. Если это число не целое, то надо определить остаток от деления. Этот остаток определяет сколько блоков из всех дополнены (такие блоки, количество байт в которых больше на один чем в остальных). Вопреки ожиданию, дополненными блоками должны быть не первые блоки, а последние.

Например, для версии 9 и уровня коррекции M количестов данных — 182 байта, количество блоков — 5. Деля количество байт данных на количество блоков, получаем 36 байт и 2 байта в остатке. Это значит, что блоки данных будут иметь следующие размеры: 36, 36, 36, 37, 37 (байт). Если бы остатка не было, что все 5 блоков имели бы размер 36 байт.

Заполнение блоков

Блок заполняется байтами из данных полностью. Когда текущий блок полностью заполняется, очередь переходит к следующему. Байтов данных должно хватить ровно на все блоки, ни больше и ни меньше.

Создание байтов коррекции

Следующий алгоритм применяется к каждому блоку данных (если блок данных один, то просто к данным).

Этот алгоритм основан на алгоритме Рида–Соломона. Первое что надо сделать — определать сколько байтов коррекции надо создать (таблица 5). По количеству байтов коррекции определяется так называемый генерирующий многочлен (таблица 6). Многочленом он называется, потому что оригинальный метод использует многочлен с теми же коэффициентами.





Перед выполнением цикла надо подготовить массив, длина которого равна максимуму из количества байтов в текущем блоке и количества байтов коррекции, и заполнить его начало байтами из текущего блока, а конец нулями.

Цикл, описанный в этом списке, повторяется столько раз, сколько байтов данных содержится в текущем блоке.

1. Берём первый элемент массива, сохраняем его значение в переменной А и удаляем его из массива (все следующие значения сдвигаются на одну ячейку влево, последний элемент заполняется нулём).
2. Если А равно нулю, то пропустить следующие действия (до конца списка) и перейти к следующей итерации цикла.
3. Находим соответствующее числу А число в таблице 8, заносим его в переменную Б.
4. Далее для N первых элементов, где N — количество байтов коррекции, i — счётчик цикла:
   
   • К i-му значению генерирующего многочлена надо прибавить значение Б и записать эту сумму в переменную В (сам многочлен не изменять).
   • Если В больше 254, надо использовать её остаток при делении на 255 (именно 255, а не 256).
   • Найти соответствующее В значение в таблице 7 и произвести опеацию побитового сложения по модулю 2 (XOR, во многих языках программирования оператор ^) с i-м значением подготовленного массива и записать полученное значение в i-ю ячейку подготовленного массива.

Первые N байтов подготовленного массива после этого цикла — и есть байты коррекции. Для каждого блока данных получится соответствующий блок байтов коррекции.

Ничего не понятно? Мне тоже. Посмотрите на пример и всё станет ясно.





Пример. Здесь все байты я буду представлять в виде десятичных чисел от 0 до 255. Исходный блок данных:
 64 196 132  84 196 196 242 194   4 132  20  37  34  16 236  17
Используется 2-я версия с уровнем коррекции H. В этом случае надо создать 28 байтов коррекции (таблица 5) и использовать генерирующий многочлен (таблица 6):
168 223 200 104 224 234 108 180 110 190 195 147 205  27 232 201  21  43 245  87  42 195 212 119 242  37   9 123
Создадим массив (подготовленный массив) на 28 элементов и заполним его байтами данных:
 64 196 132  84 196 196 242 194   4 132  20  37  34  16 236  17   0   0   0   0   0   0   0   0   0   0   0   0
Я подробно распишу первый шаг цикла, остальные в виде готового массива. Первый элемент массива — 64. Убираем его из подготовленного массива:
196 132  84 196 196 242 194   4 132  20  37  34  16 236  17   0   0   0   0   0   0   0   0   0   0   0   0   0
В таблице 8 находим ему соответствие — 6; прибавляем по модулю 255 это число к каждому числу генерирующего многочлена:
174 229 206 110 230 240 114 186 116 196 201 153 211  33 238 207  27  49 251  93  48 201 218 125 248  43  15 129
Для каждого числа гененирующего многочлена находим соответствие в таблице 7:
241 122  83 103 244  44  62 110 248 200  56 146 178  39  11 166  12 140 216 182  70  56  43  51  27 119  38  23
И почленно производим операцию побитового сложения по модулю 2 с подготовленным массивом:
 53 254   7 163  48 222 252 106 124 220  29 176 162 203  26 166  12 140 216 182  70  56  43  51  27 119  38  23
Повторяем эти действия 16 раз (16 байт данных). В итоге получатся следующие байты коррекции:
 16  85  12 231  54  54 140  70 118  84  10 174 235 197  99 218  12 254 246   4 190  56  39 217 115 189 193  24

Объединение блоков

У нас имеется несколько блоков данных и столько же блоков байтов коррекции, их надо объединить в один поток байт. Делается это следующим образом: из каждого блока данных по очереди берётся один байт информации, когда очередь доходит до последнего блока, из него берётся байт и очередь переходит к первому блоку. Так продолжается до тех пор, пока в каждом блоке не кончатся байты. Если в текущем блоке уже нет байт, то он пропускается (такое происходит, когда обычные блоки уже пусты, а в дополненных ещё есть по одному байту). Аналогичным образом надо сделать с блоками байтов коррекции. Они берутся в том же порядке, что и соответствующие блоки данных.

В итоге должно получиться что-то подобное: <1-й байт 1-го блока данных><1-й байт 2-го блока данных>...<1-й байт n-го блока данных><2-й байт 1-го блока данных>...<(m — 1)-й байт 1-го блока данных>...<(m — 1)-й байт n-го блока данных><m-й байт k-го блока данных>...<m-й байт n-го блока данных><1-й байт 1-го блока байтов коррекции><1-й байт 2-го блока байтов коррекции>...<1-й байт n-го блока байтов коррекции><2-й байт 1-го блока байтов коррекции>...<l-й байт 1-го блока байтов коррекции>...<l-й байт n-го блока байтов коррекции>. Здесь n — количество блоков данных, m — количество байтов на блок данных у обычных блоков, l — количество байтов коррекции, k — количество блоков данных минус количество дополненных блоков данных (тех, у которых на 1 байт больше).

Размещение информации на QR коде

У нас есть последовательность байт, которая готова для того, чтобы её поместили на холст. Холст состоит из модулей — элементарных квадратов.

Базовые элементы

Размер QR кода зависит только от версии. Для первой версии это 21 модуль, а размеры старших версий определяются из таблицы 9. Вобще в ней указаны места расположения выравнивающих узоров (об этом чуть позже), но размер холста можно определить как последнее число + 7 модулей. Хочу обратить ваше внимание, что отступ, рамка из белых модулей шириной 4 модуля, — полноценная часть QR кода, и её нельзя не учитывать. Несмотря на это, я указываю высоту ширину именно части с чёрными модулями и начинаю отчёт с её верхнего левого угла ((0, 0) — верхний левый модуль верхнего левого поискового узора).

Поисковые узоры

Это узоры, которые представляют из себя чёрный квадрат размером 3 на 3 модуля, который окружён рамкой из белых модулей, которая окружена рамкой из чёрных модулей, которая окружена рамкой из белых модулей только с тех сторон, где нет отступа. Поисковые узоры располагаются в верхних и левых углах (всего 3).

Выравнивающие узоры

Используются начиная с 2-й версии, представляют из себя чёрный квадрат размером 1 на 1 модуль, который окружён рамкой из белых модулей, которая окружена рамкой из чёрных модулей, в итоге этот узор имеет размер 5 на 5. Места, где располагаются выравнивающие узоры, указаны в таблице 9. Точнее там указаны узлы сетки по вертикали и горизонтали, где располагаются центральные модули узоров. Например, если в таблице написано 6, 22, 38, это значит, что центры модулей должны располагаться в следующих точках: (6, 6), (6, 22), (6, 38), (22, 6), (22, 22), (22, 38), (38, 6), (38, 22), (38, 38). Есть одно важное условие: выравнивающие узоры не должны наслаиваться на поисковые узоры. То есть, когда версия больше 6, в точках (первая, первая), (первая, последняя) и (последняя, первая) выравнивающих узоров не должно быть. В нашем примере это (6, 6), (6, 38) и (38, 6).

Полосы синхронизации

Здесь всё просто. Полосы начинаются от самого нижнего правого чёрного модуля верхнего левого поискового узора и идут, чередуя чёрные и белые модули, вниз и вправо до противоположных поисковых узоров. При наслоении на выравнивающий узор он должен остаться без изменений.

Код версии

Эти элементы используются начиная с 7-й версии. Код версии дублируется в 2-х местах, причём зеркально, то есть указав цвет модуля в координатах (x, y), можно смело указывать такой же цвет в координатах (y, x). Модули в этих местах выстраиваются согласно рисунку ниже и таблице 10 (1 — чёрный, 0 — белый).

Код маски и уровня коррекции

Этот код, так же как и предыдущий, дублируется в 2-х местах: рядом с верхним левым поисковым узором и рядом с нижним и правым поисковыми узорами (элемент терпит разрыв). В нём особым образом зашифрованы код маски (об этом чуть позже) и код уровня коррекции. Готовые коды приведены в таблице 11. Маска определяется на самом последнем шаге, когда всё остальное свободное пространство заполняется данными. Из за того, что маска выбирается на основе лучшего варианта (для этого надо перебрать все маски), к добавлению кода маски и уровня коррекции придётся не раз возвращаться. Пока что не добавляйте этот элемент. На рисунке изображено где именно и в каком направлении выстраиваются модули этого элемента, а также красным отмечен модуль, который всегда чёрный.

Добавление данных

Всё оставшееся свободное пространство на холсте разбивается на столбики: каждые 2 модуля, не важно что находится в этих модулях, кроме вертикильной полосы синхронизации, которая просто пропускается. Заполнение начинается с правого нижнего угла, идёт в пределах столбика справа налево, снизу вверх. Если текущий модуль занят (например полосой синхронизации или выравнивающим узором), то он просто пропускается. Если достигнут верх столбика, то движение продолжается с верхнего правого угла столбика, который расположен левее, и идёт сверху вниз. Достигнув низа, движение продолжается от нижнего правого угла столбика, который расположен левее, и идёт снизу вверх. И так далее, пока всё свободное пространство не будет заполнено.



Заполнение происходит бит за битом из байтов данных, при этом 1 это чёрный модуль, а 0 — белый. Если данных не хватает, то оставшееся пространство заполняется нулевыми модулями.

При этом на каждый модуль накладывается одна из масок. Всего масок 8 штук (от 0 до 7), их список в таблице 12. Если выражение из таблицы равно нулю, то цвет модуля инвертируется, иначе остаётся неизменным. Маска применяется только к модулям данных.



Маска выбирается по разному: некоторые всегда используют одну и ту же, другие каждый раз случайную, но спецификация настаивает, чтобы каждая маска оценивалась и выбиралась самая оптимальная. Способ с оценкой требует больше времени, но нет ничего страшного, если будет выбрана не оптимальная маска, поэтому не обязательно использовать именно его, но я всё равно расскажу о нём. От выбранной маски зависит код маски и уровня коррекции (см. выше), сейчас самое время добавить этот элемент.

Выбор лучшей маски

Эта часть не обязательна, и, если вы уже определились с выбором маски и добавили на холст данные, ваш QR код готов.

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

Правило 1

По горизонтали и вертикали за каждые 5 и больше идущих подряд модулей одного цвета начисляется количество очков, равное длине этого участка минус 2. В этом и во всех остальных правилах отступ не рассматривается, всё ограничивается основным полем.

Правило 2

За каждый квадрат модулей одного цвета размером 2 на 2 начисляется по 3 очка.

Правило 3

За каждую последовательность модулей ЧБЧЧЧБЧ, с 4-мя белыми модулями с одной из сторон (или с 2-х сразу), добавляется 40 очков (по вертикали или горизонтали). Проще говоря, за эти элементы:



В нашем примере всего 3 таких элемента, за что он получает 120 дополнительных очков (не обязательно эти элементы должны пересекаться с поисковым узором):

Правило 4

Количество очков на этом шаге зависит от соотношения количества чёрных и белых модулей. Чем ближе оно к соотношению 50% на 50%, тем лучше. Первое что надо сделать — поделить количество чёрных модулей на общее количество модулей (опять же, отступ не считается).
203 / 441 = 0.46032
Далее умножить полученный результат на 100 и отнять 50.
0.46032 * 100 - 50 = -3.986
Отбросить десятичную часть и взять число по модулю.
-3.986 -> 3
Умножить полученное число на 2.
3 * 2 = 6
Прибавить это число к общему количеству штрафных очков.

Итог

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

Статьи, взятые за основу

• QR Code Demystified — Part 1
• QR Code Demystified — Part 2
• QR Code Demystified — Part 3
• QR Code Demystified — Part 4
• QR Code Demystified — Part 5
• QR Code Demystified — Part 6