Пишем свой QR-Code генератор. Введение в QR-Code.

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

Итак, первое что нужно знать про QR код, что он стандартизован и стандарт называется ISO/IEC18004, его можно легко найти в интернете в виде pdf файла, и вобщем-то это единственная исчерпывающая документация по данному вопросу.

Шаги. Как превратить текст в QR-Code
Шаг 1. Определяем тип данных
В простом случае (а сложные я здесь не рассматриваю) существует четыре типа данных:

• Арабские цифры
• Арабские цифры + латинские заглавные буквы а также пробел, $%*-+/.:
• Бинарный - любая байтовая последовательность
• Канзи-иероглифы

Соответственно, чтобы продолжать работу, необходимо определить с каким типом данных мы работаем. Это легко делается c помощью QRegExp

Шаг 2. Определяем версию QR кода.

Теперь имея тип данных, длину данных и предположение о том какой уровень коррекции от ошибок нам необходим, мы можем выбрать версию QR-Code. Понятие "версия" в данном случае подразумевает размер символа (квадрата) QR кода. Всего существует 40 версий. Первая имеет размер 21x21 точек, каждая следующая на 4 больше. Существует 4 уровня коррекции ошибок:

Качество коррекции ошибок QR Code
Уровень L	~7%
Уровень M	~15%
Уровень Q	~25%
Уровень H	~30%

Для обычного использования в принципе достаточно уровня M, более высокие уровни нужны для печати наклеек для товаров, у которых есть вероятность стереться или повредиться при перевозке.

Теперь для того, чтобы вычислить версию, необходимо свериться с таблицей описанной здесь.

Шаг 3. Заполняем шаблон неизменяемыми служебными данными.

На картинки из wikipedia видно, что неизменяемыми являются элементы Position, которые всегда стоят в  трех углах, timing pattern и alignment pattern. На самом деле количество alignment элементов варьируется от версии, равно как и их место положение, о этом следующий шаг.

  

Шаг 4. Расставляем alignment элементы

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

В соответствие с таблицей:

Цифры написанные в колонках описывают координаты alignment блоков по принципу каждое с каждым, те элементы, координаты которых пересекаются с Position блоками, не ставятся.

Шаг 5. Информация о версии.

Информацию о версии можно вычислить, об этом смотрите стандарт, но в том же стандарте есть уже вычисленные числа для каждой версии. Я предпочел воспользоваться ими, кстати, для версии меньше седьмой информация о версии вообще не пишется. Для остальных версий эта информация записывается в блоки отмеченные на картинке выше синим цветом, оба блока идентичны, хотя порядок заполнения разный. Заполнение обоих блоков можно произвести за один проход:

void QRCodeMatrix::setVersionInformation()

{

    const int versionInfoBitStreamSize = 18;

    if (m_info.codeVersion() < 7)

        return;

    int versionInformation = m_versionInfo[m_info.codeVersion()];

    int firstCoordinate = symbolSizeForVersion(m_info.codeVersion()) - (positionSquareSize + 1) - 3;

    int secondCoordinate = 0;

    for (int i = 0; i < versionInfoBitStreamSize; ++i) {

        bool value = versionInformation % 2;

        versionInformation = versionInformation >> 1;

        setSystemPoint(firstCoordinate, secondCoordinate, value);

        setSystemPoint(secondCoordinate, firstCoordinate, value);

        ++firstCoordinate;

        if ((firstCoordinate - (symbolSizeForVersion(m_info.codeVersion())

            - (positionSquareSize + 1) - 3)) % 3 == 0) {

            firstCoordinate = symbolSizeForVersion(m_info.codeVersion()) 

            - (positionSquareSize + 1) - 3;

            ++secondCoordinate;

        }

        if (secondCoordinate % 6 == 0)

            secondCoordinate = 0;

    }

}

Про следующие шаги напишу в следующий раз. Однако, ниже их кратенький обзор.

Шаг 5. Вычисление битовой последовательности.

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

Шаг 6. Вычисление битовой последовательности корректирующих кодов.

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

Шаг 7. Заполнение данными

Данные разбиваются на блоки по 8 бит, расположение блоков может варьироваться друг относительно друга, на это в основном влияют смещения от  "препятствия" таких как alignment блоки.

Шаг 8. Вычисление оптимальной маски и ее наложение.

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

Существует восемь стандартных масок:

Шаг 9. Вычисление информации о формате.

Данный шаг очень сильно связан с предыдущими.Стоит добавить что позиции Format information на картинке выше отмечены красным цветом.

Шаг 10. Рендеринг

С рендерингом все достаточно просто, следует только не забывать что рекомендуемый размер одной точки не менее 4x4 пиксела. И что по все сторонам QR-Code необходимо оставить отступ шириной в 4 точки.