Для кодирования данных в десятичном формате требуется гораздо больше символов, чем для тех же данных, но закодированных в base64 — 06513249 против YWJj. Однако это правило не работает, когда речь идёт о QR-кодах. В них гораздо лучше работает использование десятичных чисел. Никакой магии, просто все дополнительные цифры сохраняются настолько эффективно, как если бы кодирования вообще не было. Десятичная кодировка позволяет QR-кодам хранить больше данных, а ещё их легче сканировать.

В статье расскажу:

• как на практике использование десятичной кодировки снижает (незначительно) плотность QR-кода, содержащего URL-адрес;

• почему это так работает: все десятичные данные безопасны для URL-адресов и эффективно сохраняются в числовом режиме QR-кода, в то время как base64 даёт 75% потерь, поскольку данные приходится хранить в двоичном формате;

• как запихнуть максимум данных в URL в QR-код.

В статье «Механическая симпатия к QR-кодам: улучшение регистрации в Новом Южном Уэльсе» я исследовал QR-коды, используемые для отслеживания контактов COVID. Оказывается, несколько штатов включили кучу информации в URL-адреса своих QR-кодов в виде JSON-объекта в кодировке Base64, предположительно потому, что это удобно.

Они использовали URL-адреса с 228-символами, типа такого: https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app?data=eyJ0IjoiY292aWQxOV9idXNpbmVzcyIsImJpZCI6IjEyMTMyMSIsImJuYW1lIjoiVGVzdCBOU1cgR292ZXJubWVudCBRUiBjb2RlIiwiYmFkZHJlc3MiOiJCdXNpbmVzcyBhZGRyZXNzIGdvZXMgaGVyZSAifQ== , причём это eyJ...был большим двоичным объектом. На уровне исправления ошибок H это можно закодировать в QR-код 81×81 (версия 16).

Если всё же нужно хранить данные в формате JSON (в статье описано, почему мы этого не делаем), есть способы эффективнее base64: переписав данные в десятичный формат, мы получим 353-символьный урл https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app?data=072685680885510189821994892577900638215789419258463239488533499278955911240512279111633336286737089008384293066931974311305533337894591404330656702603998035920596585517131555967430155259257402711671699276432408209151397638174974409842883898456527289026013404155725275860173673194594939.

Любой здравомыслящий человек скажет, что это на 50% длиннее. К счастью, для QR-кодов всё немного иначе, и там потребуется на 20% меньше модулей (квадратиков). Вышеуказанный урл умещается в QR-код 73×73 (версия 14).

QR-коды с меньшим количеством модулей легче сканировать.

Сложные данные в URL-адресах

QR-коды могут хранить произвольные данные, но обычно они используются для хранения URL-адреса, чтобы при сканировании можно было перейти на сайт и получить оттуда всю полезную информацию. С другой стороны, QR-код может быть размещён где-то, где нет доступа к интернету, и он тоже должен содержать достаточное количество полезной информации. Это приводит к появлению URL-адресов с большим количеством данных.

Однако URL-адрес — это ограниченный контейнер: попытка вставить в него произвольные данные может привести к проблемам, связанным с неправильной интерпретацией или искажением спецсимволов. К счастью, URL-адреса в основном представляют собой просто текст, а способов преобразования произвольных данных в текст существует множество: на странице Википедии о кодировании двоичных данных в текст описано аж 28 штук.

Один из самых распространённых, пожалуй, Base64: он встроен в каждый браузер. Например тот, с которого вы сейчас читаете эту статью. Base64 кодирует 3 байта в 4, выбранные из сокращённого 64-символьного алфавита. Это разумный выбор по умолчанию. Его можно включать в атрибуты JSON, HTML/XML, CSS и, конечно же, URL-адреса.

Всё это означает, что данные base64 могут оказаться в QR-кодах, где закодирован URL-адрес, содержащий большой объем данных. К сожалению, base64 — плохой метод кодирования двоичных данных в QR-коде: выбор алфавита вынуждает QR-код хранить данные неоправданно неэффективным способом.

Схемы кодирования

Существует огромное множество способов закодировать набор произвольных байтов в сокращённый набор символов. Мы подробно рассмотрим base64, base10 и base45 из RFC 9285, который разработан для QR-кодов (другие, такие как base16 (шестнадцатеричный), base32 или base36, явно хуже).

Некоторые из них являются безопасными URL: закодированные данные могут быть внесены непосредственно в URL-адрес, не требуя какого-либо специального экранирования или обработки, в то время как другие таковыми не являются или могут потребовать специальной обработки со стороны сервера. Мы собираемся размещать данные в URL-адресах, поэтому безопасность URL-адресов является обязательным требованием. Так что нам нужно рассматривать следующие варианты:

• base64url ( URL-безопасный вариант base64) и

• base10 (десятичный).

Я придумал «base10» благодаря тому, что рассматривал байты как огромное целое число (с прямым порядком байтов) по основанию 256, а затем напечатал целое число в другой системе счисления. Это не скейлится до больших данных, но отлично работает для пары килобайт, которые можно сохранить в QR-коде. Версия Python может быть такой:

import math

_DIGITS_PER_BYTE = math.log(2**8, 10)

def b10encode(data: bytes) -> str:

    raw = str(int.from_bytes(data, byteorder="little"))

    # Handle leading zeros so that, for instance, b"", b"\x00"

    # and b"\x00\x00" each have their own unique encoding, not

    # just "0".

    encoded_length = math.ceil(len(data) * _DIGITS_PER_BYTE)

    prefix = "0" * (encoded_length - len(raw))

    return prefix + raw

def b10decode(s: str) -> bytes:

    # Deduce the length of the result from the input, matching

    # b64encode's zero-padding (NB. a real implementation

    # should validate the length is valid)

    decoded_length = math.floor(len(s) / _DIGITS_PER_BYTE)

    return int(s).to_bytes(

        length=decoded_length,

        byteorder="little",

    )

В таблице в столбце «Соотношение ввода:вывода» показано, какое количество выходных символов потребуется (в среднем) свыше количества входных символов.

Например, при кодировании в base10 длинные входные данные практически соответствуют среднему значению, тогда как короткие входные данные могут различаться сильнее:

Режимы QR кодов

QR-код хранит данные в битовом потоке, а входные данные закодированы в сегментах. Каждый сегмент данных может быть закодирован в одном из четырёх различных режимов. Каждый режим поддерживает разные входные данные. Например, «буквенно-цифровой» режим, который поддерживает сохранение только цифр, заглавных букв и некоторых знаков препинания, определяя способ сопоставления этих символов с битами для хранения.

Для цифрового и буквенно-цифрового режимов несколько входных символов сохраняются вместе, что приводит к дробным битам для одного символа. Например, цифровой режим сохраняет группы из 3 цифр в 10 бит, например, 123456 кодируется двумя фрагментами, 123, а затем 456 — в 20 бит.

«Издержки», пусть и небольшие, будут, в любой кодировке. Удобно, что 10³ лишь немногим меньше 2¹⁰ , а 45² меньше 2¹¹.

Когда QR-код содержит несколько фрагментов данных, он все равно представляет собой один длинный поток символов, поэтому продуманный выбор фрагментов позволяет подобрать оптимальный режим для каждой значимой подстроки входных данных.

А-ля десятичный режим

Режим, необходимый для хранения закодированных данных, зависит от набора выходных символов. Для кодировок, которые мы рассмотрели выше:

Base64url содержит строчные буквы и поэтому при сохранении в QR-коде требует двоичного режима. 3 входных байта (24 входных бита) превращаются в 4 выходных символа, и эти 4 символа должны быть сохранены в 4×8 = 32 битах QR-кода. В итоге средние издержки составляют 33%: 1 входной байт сохраняется как 1,33 байта в QR-коде. Каждый байт может хранить до 256 различных значений, но кодировка base64 использует только 64 из них. Это приводит к потере 75% значений, или по 2 бита в каждом сохранённом байте.

Для base10 расчёт не так прост, но мы можем его выполнить

• Входными данными будет некоторое количество 8-битных байтов, каждый из которых имеет 2⁸ = 256 возможных значений.

• Каждый входной байт log(256, 10)в среднем превращается в ≈ 2,408 выходных цифр.

• 3 цифры хранятся в 10 битах.

• В сумме 10 / 3 * log(256, 10)для хранения каждого входного байта требуется ≈ 8,027 бит.

В результате 1 входной байт сохраняется в среднем как 1,0034 байта: издержки составляют 0,34%.

Это именно издержки самого цифрового режима. На этапе кодирования двоичного текста в кодировке Base10 издержки отсутствуют! Для кодирования тех же данных в Base10 требуется на 242% больше символов, но эти символы можно эффективно сохранить в QR-коде. При хранении не остаётся излишков.

Резюмируем

Давайте вернёмся к нашему URL-адресу, который был раньше: https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app?data=eyJ0IjoiY292aWQxOV9idXNpbmVzcyIsImJpZCI6IjEyMTMyMSIsImJuYW1lIjoiVGVzdCBOU1cgR292ZXJubWVudCBRUiBjb2RlIiwiYmFkZHJlc3MiOiJCdXNpbmVzcyBhZGRyZXNzIGdvZXMgaGVyZSAifQ==

Параметр “data=” содержит некоторый JSON в кодировке Base64. Это можно закодировать и получше, без JSON или base64, но давайте предположим, что нужно сделать именно JSON. Мы можем взять большой двоичный объект eyJ0I… и декодировать его в базовый JSON: {"t":"covid19_business","bid":"121321","bname":"Test NSW Government QR code","baddress":"Business address goes here "}.

Пропуск этих байтов через функцию b10encode даёт очень длинное число: 072685680885510189821994892577900638215789419258463239488533499278955911240512279111633336286737089008384293066931974311305533337894591404330656702603998035920596585517131555967430155259257402711671699276432408209151397638174974409842883898456527289026013404155725275860173673194594939.

Десятичная кодировка кажется человеку длинной, но для кодирования QR-кода она проще и занимает лишь немногим больше места, чем требуется необработанному JSON [^base16-base32-base36]:

Вы можете спросить о других кодировках, таких как base16 (шестнадцатеричная), base32 и base36 (которые подходят для буквенно-цифрового режима) или base 8 (подходят для цифрового режима, но с ними легче работать, чем с base10). Они менее эффективны для цифрового режима, чем base10, но в некоторых случаях потенциально более удобны.

В URL-адресе остальная часть не является чисто числовой, поэтому для того, чтобы увидеть преимущества этого кодирования, необходимо использовать два сегмента:

• один со «скучными» фрагментами URL-адреса в начале, вероятно, с использованием двоичного режима

• один с большим блоком данных в формате Base10, используя числовой режим

С использованием Segno 1.6.1 можно увидеть что-то типа такого:

url_prefix = "https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app?data="

encoded_data = b10encode(data)

# Two segments, so that they're encoded with separate modes

qr = segno.make([url_prefix, encoded_data])

В QR-кодах регистрации COVID Нового Южного Уэльса использовался уровень исправления ошибок H. Если взять это за основу и просто поменять кодировку параметра data, мы увидим результат из начала поста:

Крайние значения

Умение выбирать режимы, кодировки и сегменты позволяет удовлетворить ограничения формата QR-кода. QR-коды могут хранить до 23,6 килобит ≈ 3,0 КБ при использовании версии 40 с уровнем исправления ошибок L. Это соответствует примерно 7 тысячам десятичных цифр в числовом режиме или 3 тысячам байтов в двоичном режиме.

Мы можем попробовать это на нескольких тестовых URL-адресах типа http://example.com/{encoded_data}. Максимум, который мы можем уместить в QR-код, выглядит так:

Теоретически, гораздо более длинный URL base10 не имеет значения: благодаря QR-режиму он сжимается очень эффективно.

Однако после публикации этой статьи было отмечено, что iOS неправильно сканирует огромный URL-адрес base10, читая http://example.com вместо http://example.com/310....

Значит, длина URL имеет значение! Похоже, что это ограничение длины отличается от обычных ограничений URL, поскольку 8 КБ — это разумный нижний предел для «нормальных» браузеров в наши дни, так что 7 тыс. символов должны быть безопасными. Вставка той же ссылки в Safari напрямую работает отлично!

Так что лучше проведите собственное тестирование. 

Спасибо за внимание!