Проблема
Штрихкод — классная штука для маркировки всего на свете, от товаров до людей. Сейчас в ходу около двух десятков стандартов двумерных штрихкодов, и ещё десятки неудачных, трагически непонятых, самопальных и внутренних корпоративных вариантов, большинство из которых с треском проигрывает обычному QR-коду. Распространённость и простота реализации сделали его самым популярным среди двумерных штрихкодов, но и у него есть недостаток, характерный для всех линейных собратьев: он вмещает очень мало информации. В 2-3 килобайта можно уместить ссылку или небольшой отрывок текста, но даже небольшая картинка или обычный документ уже не влезут даже в самый большой код.
Понятно, что вместимость обычного QR-подобного квадратика можно увеличить, увеличивая размер матрицы, добавляя цвета и играясь с формой ячеек. Единого стандарта для таких расширенных кодов нет, кроме проприетарного Microsoft Tag (HCCB) с неясными перспективами развития и использования. Расширение палитры и изменение пикселей также усложняет чтение кода в сложных условиях (плохая печать, цветное или недостаточное освещение), но всё равно даёт очень ограниченное увеличение ёмкости и не позволяет без боли передать даже мегабайт данных.
Хороший пример такого самодельного стандарта — Jabcode
Решить проблему уже давно предложили радикально: в отличие от линейных штрихкодов, QR встречаются не только в напечатанном виде, но и на экранах устройств в приложениях и на сайтах. Значит, если чем-то в стандарте придётся поступиться, пусть это будет возможность физической печати кода — сделаем его анимированным! Таким образом моментально превращаем статичный квадратик в источник неограниченного объёма данных, которые можно будет передавать по воздуху без подключения к любым сетям. Разумеется, скорость передачи будет невысокой, и обычная считывалка QR не сможет обработать такой код, но принцип раскодирования почти тот же и изобретать велосипед не придётся.
TXQR
Первой готовой и продуманной реализацией, из всех, что мне удалось найти, стал TXQR от Ивана Данилюка (блог, GitHub). В проекте есть спецификация и PoC на Go с приложением под iOS.
Сначала код TXQR просто прокручивал обычные QR-коды в цикле, а телефон старался их считать как можно точнее, получая коррекцию ошибок только при следующем повторении цикла. В тестах автор гонял файл на 13 килобайт, получив пиковую скорость 9 KB/s. В следующей итерации формат стал использовать фонтанные коды (точнее, Luby transform code), чтобы через избыточность позволить выполнять коррекцию ошибок в любых фреймах, не дожидаясь прокрутки цикла:
Если вкратце, исходные данные делятся на блоки, которые рандомно XOR-ятся в закодированные блоки, которые уже отправляются в фреймы. Некоторые блоки могут не склеиваться, что уменьшает оверхед. На клиенте получаемые из фреймов блоки XOR-ятся с уже полученными данными, в итоге получается проверенная на ошибки исходная структура данных. Больше почитать можно на вики и в статье Ивана про переход на фонтанные коды. В общем, несмотря на существенный оверхед, скорость декодирования данных существенно возросла:
Теперь в пике TXQR выдаёт около 25 KB/s при низком уровне коррекции ошибок. Запомним это значение и перейдём к его преемнику, созданному двумя годами позже. Встречайте,
Cimbar
Cimbar (Color Icon Matrix bar codes) ещё больше отошёл от стандарта QR-кода, сохранив только визуальное сходство. Этот формат выжимает как можно большую пропускную способность, используя сразу цвета, иконки 8х8 вместо обычных пикселей и, разумеется, анимацию. В одну клетку кодируется 4 бита информации, и еще 2 или 3 бита добавляется за счёт использования цветовой схемы (на 4 или 8 цветов), позволяя хранить до 7 бит в одной клетке:
Кодирование в cimbar происходит по алгоритму, схожему с хэшированием изображений: декодер сравнивает тайл 4х4 со словарем из 16 ожидаемых тайлов и выбирает тот, у которого оказывается самый близкий хэш. Аналогично, для каждого тайла берётся средний цвет и сравнивается со словарём ожидаемых цветов, затем выбирается ближайший. Затем полученные данные проходят проверку ошибок по комбинации кода Рида — Соломона, для фонтанных кодов используется wirehair. В текущем (не окончательном) формате размер сетки 1024х1024 символа, и при использовании на маленьких экранах или с плохой камерой код не всегда читается хорошо, поэтому разработчик обдумывает вариант пожертвовать пропускной способностью в угоду универсальности.
Выглядит итоговая картинка довольно жутко и эпилептично, но позволяет добиться при обычном уровне коррекции стабильных 700-800 KB/s! Это в 32 раза быстрее чем пиковая скорость TXQR при заниженной коррекции ошибок, и в этом можно убедиться самостоятельно:
- Заходим на cimbar.org и загружаем файл потяжелее. Сначала лучше не уходить в крайности, я разок попробовал загрузить 10-мегабайтный .apk и устал держать телефон на весу, пока он качался, поэтому начинать стоит с 500KB-2MB.
- Качаем приложение под Android
- Включаем режим полёта и сканируем код. Не забудьте выбрать нужную цветовую палитру, по умолчанию на сайте и в приложении стоит 4 цвета.
- Наслаждаемся магией!
Заключение
Пока проект существует как PoC, но разработчик явно хочет довести его до ума и развить в полезный стандарт. Доки и реализация на питоне лежат в основном репозитории, оптимизированная библиотека на C/C++ живёт отдельно, мобильное приложение здесь. На сайте cimbar.org кодировщик работает через wasm, репо найти не удалось.
Air-gapped передача данных это круто и всегда весело придумывать сценарии использования для них. Я уже попробовал передавать приложения через cimbar и вижу в этом много интересных возможностей. Если у вас тоже появились оригинальные идеи, обсудим в комментариях.
На правах рекламы
Наша компания предлагает аренду VPS для совершенно любых проектов. Предлагаем широкий выбор тарифных планов, максимальная конфигурация позволит разместить практически любой проект — 128 ядер CPU, 512 ГБ RAM, 4000 ГБ NVMe!
Автор: Mikhail
