Проблема
Штрихкод классная штука для маркировки всего на свете, от товаров до людей. Сейчас в ходу около двух десятков стандартов двумерных штрихкодов, и ещё десятки неудачных, трагически непонятых, самопальных и внутренних корпоративных вариантов, большинство из которых с треском проигрывает обычному 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!
