Що таке 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 або більше, а це означає, що декодувальник може розрізнити два випадки, дивлячись лише на саме значення:
| Що бачить декодувальник | Спожиті біти | Чому |
|---|
| value & 8191 становить від 89 до 8191 | 13 біт | Значення від 89 і вище можуть походити лише від гілки з 13 бітами, бо 14-бітна група з таким високим нижнім 13-бітним вікном мала б бути щонайменше 8281 — чого жодна пара символів не може назвати. |
| value & 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 від Йоахіма Генке, поширюється під ліцензією BSD з 3 пунктами; «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) від Йоахіма Генке, що поширюється під ліцензією BSD з 3 пунктами, з алфавітом, надрукованим вище. Декодування приймає і ігнорує пробіли, як це робить еталонний інструмент.
Текст сторінки написано для цього сайту; алгоритм ніде не скопійовано. Значення кнопки «Приклад» — це один приклад, що йде з еталонним пакетом (позначений як «reference example»), плюс значення, отримані іншою незалежною реалізацією, яка зберігається в тестових інструментах цього сайту (позначені як «cross-check»).
