Čo je Base91?
Base91 je spôsob zápisu ľubovoľných bajtov iba tlačiteľnými znakmi ASCII, čo robí rovnakú prácu ako Base64, ale do každého znaku vtlačí viac bitov. Namiesto rozdelenia vstupu na skupiny po 6 bitoch a vypísania jedného znaku na skupinu zbiera bity, kým ich nemá aspoň 13, a potom vypíše dva znaky, ktoré spolu pomenujú hodnotu týchto 13 (alebo 14) bitov.
Dva znaky z abecedy 91 dokážu pomenovať 91 × 91 = 8281 rôznych hodnôt a 213 = 8192, takže dva znaky vždy majú miesto na 13 bitov — so 89 hodnotami navyše. V tom je celý trik: 13 bitov na 2 znaky je 6,5 bitu na znak oproti 6 pri Base64 a znamená to režijné náklady okolo 23% namiesto 33%.
Verzia na 30 sekúnd: test sa zmení na fPNKd a Hello, World! sa zmení na >OwJh>}AQ;r@@Y?F. Dekódovanie je presne opačný postup a potrebuje tú istú abecedu 91 znakov — iná abeceda dá z tých istých bajtov iný výstup.
Odkiaľ berú 13 a 14 bitov
Dvojica znakov dokáže pomenovať 91 × 91 = 8281 hodnôt, čo je viac než 213 = 8192, ale menej než 214 = 16384. Dvojica znakov teda vždy unesie 13 bitov a niekedy 14. Kodér najprv skúsi 13 bitov: ak je táto 13-bitová hodnota väčšia než 88, vypíše ju ako dva znaky; inak vezme štrnásty bit a vypíše výslednú 14-bitovú hodnotu.
Hranica pri 88 nie je ľubovoľná. Najväčšia hodnota, ktorú dva znaky dokážu pomenovať, je 90 + 91 × 90 = 8280, a 8192 + 89 = 8281 je už za ňou. Žiadna 14-bitová skupina preto nemôže mať nízke 13-bitové okno s hodnotou 89 alebo vyššou, čo znamená, že dekodér dokáže oba prípady rozlíšiť len podľa samotnej hodnoty:
| Čo dekodér vidí | Spotrebované bity | Prečo |
|---|
| hodnota & 8191 je 89 až 8191 | 13 bitov | Hodnoty od 89 vyššie môžu pochádzať len z 13-bitovej vetvy, pretože 14-bitová skupina s nízkym 13-bitovým oknom takej výšky by musela byť aspoň 8281 — čo žiadna dvojica znakov nedokáže pomenovať. |
| hodnota & 8191 je 0 až 88 | 14 bitov | Kodér prechádza na 14 bitov len vtedy, keď bolo 13-bitové čítanie 88 alebo menej, takže táto vetva je záložná a nič iné. |
Čokoľvek zostane na konci — ktorýkoľvek počet od 1 do 13 bitov — sa vypíše ako jeden znak, plus druhý znak, keď zvyšok naozaj potreboval viac než 7 bitov. Preto dĺžka zakódovaného výstupu rastie po dvoch znakoch a niekedy končí nepárnym počtom.
Abeceda a tri znaky, ktoré vynecháva
Tlačiteľné ASCII obsahuje 94 znakov, od ! (0x21) po ~ (0x7E). Base91 používa 91 z nich a tri, ktoré vynecháva, sú spojovník -, apostrof ' a opačná lomka \. Písmená, číslice a takmer všetka interpunkcia sú v abecede presne raz, v poradí uvedenom v tabuľke vyššie; 92. až 94. tlačiteľný znak sa jednoducho nedá adresovať.
Pretože je abeceda pevným poradím, znak pre hodnotu je vyhľadávanie, nie vzorec. Dve implementácie, ktoré usporiadajú abecedu inak, sa obe budú volať „Base91“ a nebudú schopné prečítať výstup jedna druhej, čo je najčastejší zdroj matúcich výsledkov. Táto stránka vypisuje svoju abecedu, aby sa výstup dal vždy vystopovať späť k nej.
Base91 vedľa ostatných tlačiteľných kódovaní
| Kódovanie | Bity na znak | Veľkosť voči vstupu | Poznámky |
|---|
| Base16 (hex) | 4 | 200% | Dva znaky na bajt, ľahko čitateľné, žiadna abeceda na vyhľadávanie. |
| Base32 | 5 | 160% | Nerozlišuje veľkosť písmen a je bezpečný na diktovanie, ale najplytvavejší v skupine. |
| Base58 | ~5,86 | ~137% | Vybraný pre adresy, nie pre hustotu: vyhýba sa podobne vyzerajúcim znakom. |
| Base64 | 6 | 133% | Predvolená voľba všade: 4 znaky na 3 bajty, pričom 6 nevyužitých bitov posledného znaku sa premárni. |
| Ascii85 / Base85 | 6,4 | 125% | 5 znakov na 4 bajty, netreba tabuľku vyhľadávania, ale delí 85 — súvisiace: konvertor Ascii85. |
| Base91 | ~6,5 | ~123% | Najhustejšie z týchto: 13 bitov na 2 znaky, s 14-bitovou skupinou tu a tam. |
Percentá sú asymptotické náklady každého kódovania, zaokrúhlené; skutočné počty znakov pre jeden reálny 92-bajtový vstup sú v tabuľke vyššie na tejto stránke. Base91 sa približuje k najlepšiemu, čo sa dá s tlačiteľným ASCII dosiahnuť: 7 bitov na znak by znamenalo použiť 128 rôznych znakov, čo tlačiteľný rozsah nedokáže poskytnúť.
Čím Base91 nie je
- Nie je to norma. Neexistuje žiadny RFC. Referenčná implementácia je basE91 0.6.0 od Joachima Henkeho, vydaná pod licenciou BSD 3-klauzula; označenie „Base91“ sa používa aj pre abecedy, ktoré nie sú táto.
- Nie je to šifrovanie. Každý znak je priame preskupenie bitov vstupu a ktokoľvek s abecedou to vie vrátiť späť jedným prechodom.
- Nie je bezpečné pre URL. Abeceda obsahuje
#, %, &, /, ? a ", a všetky menia význam v URL, takže výstup Base91 sa musí percent-kódovať, skôr než sa vloží do dotazu.
- Nie je bezpečné pre HTML. Obsahuje aj
<, >, & a ", takže reťazec Base91 vložený do značiek sa musí escapovať pomocou konvertora HTML entít.
- Nemá pevnú dĺžku. Dĺžka výstupu závisí od bitového vzoru, nielen od počtu bajtov, takže dva vstupy rovnakej veľkosti sa môžu líšiť o jeden znak.
Pasce, ktoré skutočne kusnú
- Abeceda na tejto stránke je referenčná. Ak iný nástroj vytvorí pre ten istý vstup iný výstup, pred predpokladom, že je pokazená niektorá strana, sa porovná jeho abeceda. Všetkých 91 znakov musí byť v tom istom poradí.
- Jediný zlý znak môže zmeniť celý koniec. Hranice skupín sa určujú hodnotami, ktoré predchádzali, takže úprava na začiatku reťazca posunie všetko za ňou a koniec sa dekóduje len so zvyškovými bitmi poslednej skupiny.
- Nepárna dĺžka výstupu je normálna. Neznamená to, že reťazec bol useknutý; posledná skupina vypíše jeden znak, keď sa jej zvyšková hodnota zmestí do 7 bitov alebo menej.
- Publikovaný príklad môže obsahovať nový riadok, ktorý nebol zadaný. Príkaz shellu, ktorý pridá ukončenie riadku, je bežný dôvod, prečo je známa hodnota Base91 o jeden znak dlhšia, než aká vznikne z rovnakého textu tu:
echo "Hello, World!" dá kodéru 14 bajtov a vypíše >OwJh>}AQ;r@@Y?FF, zatiaľ čo 13 bajtov samotného textu vypíše >OwJh>}AQ;r@@Y?F. Obe sú správne, pre rôzne počty bajtov, a počet pod výstupným políčkom ukazuje, ktorú hodnotu práve obsahuje.
- Dekódovanie binárnych dát ako textu nebude fungovať. Ak dekódované bajty nie sú platný text UTF-8, nie je čo rozumné zobraziť; na to slúži hexadecimálny režim výstupu.
Rýchle odpovede
„Prečo táto stránka ukazuje hodnotu, ktorá sa o jeden znak líši od iného nástroja Base91?“
Takmer vždy ide o inú abecedu. Druhou najčastejšou príčinou je nástroj, ktorý používa len vetvu 13 bitov a nikdy záložnú 14-bitovú vetvu; táto varianta je v kóde menšia, ale dáva iný výstup než referenčný algoritmus použitý tu.
Existuje aj jeden presný prípad, ktorý sa dá vyriešiť počítaním bajtov, a vysvetľuje najčastejšie citovaný príklad: koncový znak nového riadku. Väčšina publikovaných vektorov vznikla príkazom shellu a shell pridá ukončenie riadku. 13 bajtov Hello, World! sa tu vypíše ako 16 znakov, zatiaľ čo 14 bajtov Hello, World! nasledovaných novým riadkom sa vypíše ako 17-znakový >OwJh>}AQ;r@@Y?FF. Ktorúkoľvek z hodnôt možno vložiť do dekódovania: táto stránka hlási počet bajtov, takže sa dá rozlíšiť, ktoré čítanie je správne, namiesto hádania. Tlačidlo Ukážka načíta tú z dvoch hodnôt, ktorá patrí čitateľovi, ktorý sa používa; riadi sa prepínačom Kódovať / Dekódovať a voľbou Vstup je / Výstup ako: textový čitateľ dostane 16-znakovú hodnotu, hexadecimálny čitateľ 17-znakovú so spätným bajtom 0A na očiach, a kodér dostane text na kódovanie namiesto reťazca Base91.
„Je Base91 menší než Base64?“
Áno, zhruba o 8% zakódovanej veľkosti: 13 bitov na 2 znaky oproti 6 bitom na znak. Pri 92 bajtoch textu vypíše Base64 124 znakov a Base91 114.
„Dá sa to dekódovať dekodérom Base64 alebo naopak?“
Nie. Abecedy sa prekrývajú v písmenách a číslicach, takže dekodér Base64 prijme reťazec Base91 ako „platné“ znaky a vyprodukuje tichý šum. Obe sa zhodujú len v tvare schémy.
„Končí výstup výplňou ako Base64?“
Nie. Base91 nemá vôbec žiadny výplňový znak: zvyšné bity na konci sa vypíšu ako posledná skupina, takže sa nič nemusí pridávať ani odstraňovať.
„Ako viem, že výsledok na tejto stránke je správny?“
Kliknutím na Autotest 0 až 64 bajtov sa zakóduje a dekóduje 130 vzorov bajtov pokrývajúcich každú dĺžku, pri ktorej sa rozdelenie na 13 a 14 bitov mení, a porovná bajty, ktoré sa vrátia, s bajtmi, ktoré vstúpili. Vektory tlačidla Ukážka sa navyše porovnávajú s druhou implementáciou napísanou pre testovacie nástroje tejto lokality.
Normy a zdroje
Táto stránka implementuje algoritmus referenčnej implementácie basE91 (verzia 0.6.0) od Joachima Henkeho, distribuovanej pod licenciou BSD 3-klauzula, s abecedou vypísanou vyššie. Dekódovanie prijíma biele znaky a ignoruje ich, ako to robí referenčný nástroj.
Text stránky bol napísaný pre túto lokalitu; algoritmus nebol nikde skopírovaný. Hodnoty tlačidla Ukážka sú jediný príklad, ktorý sa dodáva s referenčným balíkom (označený „referenčný príklad“), plus hodnoty vytvorené druhou, nezávislou implementáciou uloženou v testovacích nástrojoch tejto lokality (označené „kontrolný výpočet“).
