Алгоритмы QR и коррекция ошибок: почему успешного чтения недостаточно для валидации кодировщика

Алгоритмы QR и коррекция ошибок: почему успешного чтения недостаточно для валидации кодировщика

Разработка легковесного генератора штрихкодов кажется типовой задачей: стандарт QR Model 2 детально описан, а отказ от лишних зависимостей в пользу компактного JavaScript-модуля выглядит естественным решением для микросервисов. Однако генерация двухмерных матриц таит алгоритмические ловушки, в которых стандартные тесты дают ложное ощущение надежности.

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

Анатомия матрицы и математика стандарта

Код QR Model 2 оперирует модулями — черными и белыми точками растра. Стандарт определяет 40 версий (от 1 размером 21×21 до 40 размером 177×177) и четыре уровня коррекции ошибок: L (до 7% повреждений), M (до 15%), Q (до 25%) и H (до 30%).

Пространство матрицы разделено на зоны:

• Служебные шаблоны: три поисковых маркера по углам (finder patterns), узоры синхронизации (timing patterns), маркеры выравнивания (alignment patterns) и полосы информации о формате и версии.
• Область полезной нагрузки: остальная площадь растра, заполняемая кодовыми словами (байтами по 8 бит).

Для версии 8 (сторона 49 модулей) общее число доступных кодовых слов строго зафиксировано стандартом ISO/IEC 18004 и равно 242 байтам. Кодирование выполняется в несколько этапов: полезная нагрузка переводится в поток битов, дополняется служебными заголовками и байтами заполнения (0xEC, 0x11), разбивается на блоки данных, для каждого блока вычисляются проверочные слова Рида — Соломона, после чего блоки перемежаются и накладывается маска.

Табличная ловушка версии 8-H

В разрабатываемом модуле возникла скрытая ошибка: в конфигурационной таблице параметров для версии 8 с максимальным уровнем коррекции H было указано 5 блоков вместо положенных 6.

Сравнение параметров показывает, почему дефект не проявился при базовых проверках:

Арифметика сошлась: 112 слов данных плюс 130 слов коррекции дали 242 байта. Проверки выхода за границы буфера не сработали. Визуально матрица выглядела рабочей: размер 49×49 модулей, правильные маркеры, а число темных точек отличалось от эталона всего на 36 (1286 против 1250 из 2401).

Однако ни один стандартный декодер (ни jsQR 1.4.0, ни @zxing/library 0.21.3) не смог прочитать из матрицы ни байта, завершая работу с ошибкой контрольной суммы ChecksumException.

Механизм сбоя: разрушение чередования Рида — Соломона

Причина сбоя крылась в алгоритме чередования (interleaving). В спецификации QR слова блоков не укладываются в растр последовательно. Иначе царапина или блик уничтожили бы один блок целиком, превысив лимит коррекции.

Стандарт требует побайтового чередования: в матрицу помещается первое слово блока 1, затем первое слово блока 2, и так далее до последнего блока N. Затем укладываются вторые слова всех блоков, а после по той же схеме перемежаются проверочные слова Рида — Соломона.

Декодер читает растр в обратном порядке: он ожидает встретить перемежение 6 блоков. Но кодировщик чередовал поток из расчета на 5 блоков. Порядок байтов сместился: проверочные слова одного блока интерпретировались как данные другого, границы полиномов разрушились, а алгоритм коррекции получил цифровой шум.

Вторая опасность ошибки — искажение выбора версии. Генератор посчитал, что версия 8-H вмещает 110 байт полезного текста вместо реального предела в 84 байта. При автоматическом подборе версии для строки длиной 95 байт кодировщик выбрал бы версию 8-H вместо более просторной 9-H, создав нечитаемый код.

Ловушка успешного чтения сканером

Расследование выявило изъян в популярном подходе к тестированию: сгенерировать изображение и убедиться, что библиотека чтения вернула исходную строку.

Алгоритмы Рида — Соломона созданы для исправления физических повреждений: потертостей бумаги, расфокусировки камеры, бликов и деформаций. Если кодировщик допускает программный дефект (сдвиг индекса, неверный заголовок или маску), сильный декодер может распознать текст, израсходовав на это весь запас избыточности.

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

Двухуровневая регрессионная проверка

Для валидации генератора была разработана сквозная методология тестирования из двух уровней контроля.

Уровень 1: Сквозной Round-Trip по 160 комбинациям

Была скомпилирована тестовая матрица из 160 возможных сочетаний стандарта: 40 версий на 4 уровня коррекции (L, M, Q, H). Для каждого сочетания генерировались строки предельной длины.

Каждое изображение независимо проверялось декодерами jsQR и ZXing. Из 160 комбинаций 158 прочитали оба декодера. Однако в двух случаях возникли показательные расхождения:

1. Версия 23-L: библиотека ZXing успешно восстановила строку, а jsQR 1.4.0 завершилась падением. Анализ исходного кода выявил баг в декодере jsQR: в таблице координат маркеров выравнивания для версии 23 была указана координата 74 вместо 78.
2. Версия 36-L: декодер jsQR успешно прочитал матрицу, а ZXing вернул NotFoundException на всех масштабах растеризации.

Этот опыт доказал: декодеры не могут выступать абсолютным оракулом истины, поскольку сами содержат таблицы констант и потенциальные ошибки.

Уровень 2: Попиксельное сравнение с эталоном Nayuki

Для исключения погрешностей декодеров был реализован дифференциальный тест против эталонного кодировщика Nayuki QR Code generator (библиотека без внешних зависимостей).

Параметры были жестко зафиксированы:

• Использовался режим байтовых сегментов (byte mode).
• Задавалась точная версия, уровень коррекции и идентификатор маски (mask pattern).
• У эталона Nayuki было принудительно отключено автоматическое повышение уровня коррекции (automatic ECC boosting).

В тестовый набор вошли 4 семейства граничных строк на пределе емкости каждой версии (640 тестов), а также нагрузки на 1 и 2 байта ниже лимита (320 тестов). Суммарно 960 матриц совпали с эталоном Nayuki попиксельно, модуль за модулем.

Чеклист для разработчиков графических кодов

Опыт верификации формирует правила для создания надежных кодировщиков:

1. Используйте проверенные эталоны. Перед написанием собственного модуля оцените эталонные открытые библиотеки (например, Nayuki).
2. Изолируйте проверку таблиц. Конфигурационные таблицы блоков, емкостей и координат маркеров должны тестироваться отдельными юнит-тестами против стандарта ISO/IEC 18004.
3. Контролируйте граничные условия емкости. Проверяйте выбор версии на строках предельной длины и на значениях, превышающих лимит ровно на 1 байт.
4. Применяйте перекрестное декодирование. Тестируйте растр как минимум двумя независимыми библиотеками декодирования, сохраняя отчеты о расхождениях.
5. Внедряйте побитовое сравнение матриц. Сверяйте расположение модулей с независимым эталоном при одинаковых параметрах маски и уровня коррекции.
6. Разделяйте логику и оптику. После валидации чистого цифрового растра проводите отдельные испытания физической читаемости: проверку углов наклона, масштабирования, печати и контрастности.