В этой заметке мы кратко рассмотрим реализацию QR-кода, использованную в данном релизе Subliminal Extacy. Это Z80-реализация QR-кода версии 3 с уровнем коррекции ошибок «L» (3-L), работающая в реальном времени. Исходный код доступен на GitHub.
Универсальная версия на Python3 с множеством функций находится здесь:
https://github.com/jounikor/qr_code/
«Полная» версия на ассемблере Z80 (3-L) доступна по ссылке:
https://github.com/jounikor/qr_code/tree/master/asm/
Версия в байтовом режиме с оптимизацией размера, использованная в Subliminal Extacy:
https://github.com/jounikor/qr_code/tree/bytemode/asm/
Алфавитно-цифровая версия с оптимизацией размера:
https://github.com/jounikor/qr_code/tree/sizeopt/asm
Subliminal Extacy использует версию в байтовом режиме из-за лучшей совместимости с некоторыми мобильными телефонами, которые (отчасти) не понимают, что заглавные буквы в хост-части URL являются валидными. Возможно, кто-то не читал RFC 3986 досконально, или, что вероятнее, существуют практики вне стандартов, и некоторые клиентские реализации просто лучше других.
Кстати, меня также просили предоставить версию кодировщика с оптимизацией размера (Lordcoxis любит просить коды, которые никогда не будут использованы)... Я сделал это, но ценой получитабельного кода и жесткой фиксации масок без расчета штрафных баллов.
Фиксация ограничений:
Генерация QR-кода чрезвычайно гибкая. Для наших ограниченных платформ имеет смысл немного упростить процесс и зафиксировать некоторые переменные. Как уже упоминалось, это QR-код 3-L. Более того, мы поддерживаем только алфавитно-цифровой или байтовый режимы. Это позволяет следующее:
- Зафиксировать размер QR-кода на 29x29 пикселей (не считая «тихой зоны»).
- Предварительно вычислить шаблон QR-кода, который включает:
- Позиции и количество выравнивающих паттернов;
- Позиционные паттерны;
- Синхронизирующие паттерны;
- Темные модули.
- Ограничить количество строк формата 8-ю (один уровень коррекции ошибок и 8 возможных масок) и предвычислить для них биты коррекции (таблица займет 16 байт).
- Нет необходимости вычислять информацию о версии (нужна только если версия >= 7).
- Использовать фиксированные значения для заполнения пикселей/модулей.
- Предвычислить порождающий полином для расчета кодов коррекции ошибок.
- Ограничить QR-код 55 байтами данных в одном блоке и 15 кодами коррекции ошибок на блок.
- При 3-L существует только один блок группы. Поскольку блок всего один, чередование данных и кодов коррекции можно пропустить, что значительно упрощает задачу.
- Знать максимальную длину входной строки: 76 или 55 символов в зависимости от режима.
Обе версии с оптимизацией размера отказываются от динамического вычисления штрафных баллов для поиска наиболее подходящей маски. Функция маскирования жестко закодирована либо на паттерн 0, либо на паттерн 1. Это дает значительную экономию места, но ценой потенциально менее оптимального паттерна. Замечу, что переход с алфавитно-цифрового кодирования на байтовый также позволяет сократить размер кода из-за простоты байтового режима (нет умножения на 45 и манипуляций с битами).
Заметка о предвычисленном шаблоне QR-кода. Он хранится в виде двух битовых карт. Одна определяет динамические части QR-кода, а другая содержит статические светлые и темные модули вне динамических зон. Размер одной карты — 4*29 (116) байт. Хранение шаблонов в виде битовых карт означает множество манипуляций на уровне битов при кодировании. Реализация QR-кода (без примера рендеринга для ZX Spectrum) не зависит от платформы. Около 20% финального размера кода приходится на один лишь предвычисленный шаблон.
Большинство вещей в «ванильной» Z80-реализации не захардкожены, за исключением версии, а для оптимизированных по размеру версий — уровня коррекции ошибок. Программист может выбрать один из 8 алгоритмов маскирования. Предупреждение: код не оптимизирован по скорости. Были предприняты попытки снизить использование RAM, но даже это не доведено до предела.
Стандарт QR-кода ISO/IEC 18004, к сожалению, скрыт за платным доступом. Однако в интернете есть несколько «резервных копий». Существует пара весьма информативных руководств по QR-кодам с уклоном в сторону программистов:
https://medium.com/p/5a33e1e882b5/
https://www.thonky.com/qr-code-tutorial/
Одной из самых захватывающих областей в QR-кодах является расчет кодов коррекции ошибок (Рида-Соломона). Я увлекся этим процессом, особенно написанием прекалькулятора полей Галуа и процедур деления многочленов.
Процедура деления polydiv() жестко закодирована под лимиты 3-L (55 байт данных, 15 байт коррекции) и не может обработать случай, когда полином короче порождающего.
Вся подготовка и кодирование происходят в буфере размером 4x29 байт. Здесь нет предвычисленного «зигзагообразного» пути, а используется простой конечный автомат, который перемещается по шаблону, просто избегая «постоянных» пикселей. Автомат знает, куда двигаться дальше. Если следующая позиция занята «постоянным пикселем», автомат вызывается снова, пока не будет найдено доступное место.
Финальное слово о ядрах маскирования: они используют деление по модулю 3.
Математика также включает умножение строк на столбцы. Поскольку шаблон имеет максимум 29x29, произведение 2828 превышает 8 бит. Впрочем, так как операции умножения и модуля взаимозаменяемы, мы используем:
(ab)%c == ((a%c)(b%c))%c == ((a%c)b)%c.
Это всегда помещается в 8-битный регистр. Существует реализация эффективной функции divmod3_A(), возвращающей остаток и частное. Максимальное значение для нее — 192.
Аналогично есть процедура умножения mul_B_C(), возвращающая (A*B)%256.
Уф... я дошел до этого момента, так и не сказав ничего действительно полезного в контексте реализации кодировщика на Z80.
Изучайте код и ссылки на GitHub. Он должен быть читабельным и даже содержать полезные комментарии ;)
Как я говорил раньше:
MOVEQ #0,D0
RTS ; Успешный выход
Поделитесь вашим мнением о статье