Что такое Base91?
Base91 — способ записи произвольных байтов, используя только печатные символы ASCII; та же задача, что и у Base64, но он помещает больше бит в каждый символ. Вместо того чтобы нарезать вход на группы по 6 бит и печатать по одному символу на группу, он собирает биты, пока их не станет не меньше 13, а затем печатает два символа, которые вместе задают значение этих 13 (или 14) бит.
Два символа из алфавита в 91 символ могут задать 91 × 91 = 8281 различных значений, а 213 = 8192, поэтому два символа всегда имеют место для 13 бит — с 89 значениями в запасе. В этом весь приём: 13 бит на 2 символа — это 6,5 бита на символ против 6 у Base64, и накладные расходы примерно 23% вместо 33%.
Версия на 30 секунд: test превращается в fPNKd, а Hello, World! — в >OwJh>}AQ;r@@Y?F. Декодирование — точный обратный ход, и ему нужен тот же алфавит из 91 символа: другой алфавит даёт из тех же байтов другой результат.
Откуда берутся 13 и 14 бит
Пара символов может задать 91 × 91 = 8281 значение, что больше 213 = 8192, но меньше 214 = 16384. Поэтому пара символов всегда может нести 13 бит, а иногда и 14. Кодировщик сначала пробует 13 бит: если значение из 13 бит больше 88, он печатает это значение двумя символами; иначе он берёт 14-й бит и печатает полученное 14-битное значение.
Граница 88 не случайна. Наибольшее значение, которое могут задать два символа, — это 90 + 91 × 90 = 8280, а 8192 + 89 = 8281 уже выходит за него. Поэтому никакая группа из 14 бит никогда не может иметь младшее 13-битное окно 89 или больше, а значит, декодер различает два случая, глядя только на само значение:
| Что видит декодер | Съеденные биты | Почему |
|---|
| значение & 8191 равно от 89 до 8191 | 13 бит | Значения от 89 и выше могут появиться только из ветки 13 бит, потому что 14-битная группа с младшим 13-битным окном такой величины должна была бы быть не меньше 8281 — а такое число не может задать никакая пара символов. |
| значение & 8191 равно от 0 до 88 | 14 бит | Кодировщик переходит к 14 битам, только если чтение в 13 бит дало 88 или меньше, поэтому эта ветка является запасной и ничем иным не бывает. |
Всё, что остаётся в конце — от 1 до 13 бит, — печатается одним символом, а вторым символом, когда остаток действительно требовал больше 7 бит. Поэтому длина закодированной строки растёт шагами по два символа и иногда заканчивается нечётным количеством.
Алфавит и три символа, которые он опускает
Печатный ASCII содержит 94 символа, от ! (0x21) до ~ (0x7E). Base91 использует 91 из них, а три оставшихся — дефис -, апостроф ' и обратная косая черта \. Буквы, цифры и почти вся пунктуация входят в алфавит ровно один раз, в порядке, показанном в таблице выше; с 92-го по 94-й печатные символы просто не используются.
Поскольку алфавит — фиксированный порядок, символ для значения находится поиском, а не по формуле. Две реализации, которые упорядочивают алфавит по-разному, обе будут называться «Base91» и не смогут прочитать вывод друг друга — это самый частый источник запутанных результатов. Эта страница печатает свой алфавит, чтобы результат всегда можно было проследить до него.
Base91 рядом с другими печатными кодировками
| Кодировка | Бит на символ | Размер относительно входа | Примечания |
|---|
| Base16 (hex) | 4 | 200% | Два символа на байт, тривиально читается, алфавита искать не нужно. |
| Base32 | 5 | 160% | Без учёта регистра и безопасна для продиктовывания, но самая расточительная в группе. |
| Base58 | ~5,86 | ~137% | Выбран для адресов, а не для плотности: он избегает похожих символов. |
| Base64 | 6 | 133% | По умолчанию везде: 4 символа на 3 байта, при этом 6 неиспользуемых бит последнего символа пропадают. |
| Ascii85 / Base85 | 6,4 | 125% | 5 символов на 4 байта, таблица поиска не нужна, но он делит на 85 — см. конвертер Ascii85. |
| Base91 | ~6,5 | ~123% | Самый плотный из них: 13 бит на 2 символа, ценой группы из 14 бит время от времени. |
Проценты — асимптотическая стоимость каждого кодирования, округлённая; измеренные количества символов для одного реального входа из 92 байт приведены в таблице выше на этой странице. Base91 близок к лучшему, что возможно в печатном ASCII: 7 бит на символ означали бы использование 128 различных символов, а печатный диапазон этого не даёт.
Чем Base91 не является
- Не стандарт. RFC нет. Эталонная реализация — basE91 0.6.0 Joachim Henke, распространяемая по лицензии BSD 3-clause; название «Base91» также используется для алфавитов, которые не совпадают с этим.
- Не шифрование. Каждый символ — прямое переупаковывание битов входа, и любой, у кого есть алфавит, обращает его за один проход.
- Не безопасен для URL. Алфавит содержит
#, %, &, /, ? и ", и все они меняют смысл в URL, поэтому вывод Base91 нужно кодировать процентами, прежде чем помещать его в строку запроса. - Не безопасен для HTML. Он также содержит
<, >, & и ", поэтому строку Base91, которую помещают в разметку, нужно экранировать с помощью конвертера HTML-сущностей. - Не фиксированной длины. Длина вывода зависит от битового шаблона, а не только от количества байтов, поэтому два входа одного размера могут отличаться на один символ.
Ловушки, которые действительно кусают
- Алфавит на этой странице — эталонный. Если другой инструмент выдаёт другой результат для того же входа, сравните его алфавит, прежде чем считать сломанной какую-либо из сторон. 91 символ должен идти в том же порядке.
- Один неверный символ может изменить весь хвост. Границы групп определяются предыдущими значениями, поэтому правка в начале строки сдвигает всё, что после неё, а хвост декодируется только остатком бит последней группы.
- Нечётная длина вывода — нормальна. Это не значит, что строка обрезана; последняя группа печатает один символ, если её остаток помещается в 7 бит или меньше.
- Опубликованный пример может содержать перевод строки, который вы не набирали. Командная оболочка, которая добавляет окончание строки, — обычная причина того, что известное значение Base91 на один символ длиннее того, что даёт тот же текст здесь:
echo "Hello, World!" передаёт кодировщику 14 байт и печатает >OwJh>}AQ;r@@Y?FF, а 13 байт одного текста печатают >OwJh>}AQ;r@@Y?F. Оба результата верны для разного количества байтов, и счётчик под полем вывода показывает, какой из них у вас. - Декодирование двоичных данных как текста не сработает. Если декодированные байты не являются корректным UTF-8, разумного текста показать нельзя, для этого и предназначен режим вывода в шестнадцатеричном виде.
Краткие ответы
«Почему эта страница показывает значение, отличающееся на один символ от другого инструмента Base91?»
Почти всегда из-за другого алфавита. Вторая по частоте причина — инструмент, который использует только ветку 13 бит и никогда не использует запасной вариант 14 бит; такой вариант короче в коде, но даёт иной результат, чем эталонный алгоритм, используемый здесь.
Есть и один точный случай, который можно решить подсчётом байтов, и он объясняет самый часто цитируемый пример: завершающий перевод строки. Большинство опубликованных векторов получено командной оболочкой, а она добавляет окончание строки. 13 байт Hello, World! печатаются здесь 16 символами, а 14 байт Hello, World! с переводом строки печатаются 17-символьной строкой >OwJh>}AQ;r@@Y?FF. Вставьте любое из этих значений в декодирование: эта страница показывает количество байт, поэтому два прочтения можно различить, а не спорить о них. Кнопка Пример загружает то из двух значений, которое относится к выбранному вами читателю, и следует переключателю «Кодировать / Декодировать» и селектору Вход в виде / Результат в виде: текстовый читатель получает 16-символьное значение, читатель шестнадцатеричного вида получает 17-символьное с завершающим байтом 0A на виду, а кодировщик получает текст для кодирования, а не строку Base91.
«Base91 короче Base64?»
Да, примерно на 8% от размера закодированного: 13 бит на 2 символа против 6 бит на символ. На 92 байтах текста Base64 печатает 124 символа, а Base91 — 114.
«Можно ли декодировать это декодером Base64 или наоборот?»
Нет. Алфавиты пересекаются в буквах и цифрах, поэтому декодер Base64 примет строку Base91 как «допустимые» символы и выдаст молчаливый мусор. Они согласуются лишь в самой схеме построения.
«Заканчивается ли вывод заполнением, как у Base64?»
Нет. У Base91 вообще нет символа заполнения: оставшиеся в конце биты печатаются как последняя группа, поэтому ничего не нужно добавлять или удалять.
«Откуда мне знать, что результат на этой странице верен?»
Нажмите Самопроверка от 0 до 64 байт. Она кодирует и декодирует 130 байтовых шаблонов, покрывающих каждую длину, при которой меняется разбиение на 13 и 14 бит, и сравнивает байты, которые возвращаются, с байтами, которые были на входе. Значения кнопки «Пример» дополнительно сверены со второй реализацией, написанной для инструментов тестирования этого сайта.
Стандарты и источники
Эта страница реализует алгоритм эталонной реализации basE91 (версия 0.6.0) Joachim Henke, распространяемой по лицензии BSD 3-clause, с алфавитом, приведённым выше. Декодирование принимает и игнорирует пробельные символы, как это делает эталонный инструмент.
Текст страницы написан для этого сайта; алгоритм нигде не копировался. Значения кнопки «Пример» — это единственный пример, поставляемый с эталонным пакетом (помечен «эталонный пример»), плюс значения, полученные второй независимой реализацией, хранящейся в инструментах тестирования этого сайта (помечены «перекрёстная проверка»).
