Co je Base91?
Base91 je způsob zápisu libovolných bajtů pouze tisknutelnými znaky ASCII, tedy stejná úloha jako u Base64, ale do každého znaku se vejde více bitů. Místo rozdělení vstupu na skupiny po 6 bitech a tisknutí jednoho znaku na skupinu sbírá bity, dokud jich nemá alespoň 13, a poté vytiskne dva znaky, které společně pojmenují hodnotu těchto 13 (nebo 14) bitů.
Dva znaky z abecedy o 91 znacích mohou pojmenovat 91 × 91 = 8281 různých hodnot a 213 = 8192, takže dva znaky vždy mají místo pro 13 bitů — s 89 hodnotami navíc. V tom je celý trik: 13 bitů na 2 znaky je 6,5 bitu na znak oproti 6 u Base64 a stojí to asi 23 % režie místo 33 %.
Verze na 30 sekund: test se stane fPNKd a Hello, World! se stane >OwJh>}AQ;r@@Y?F. Dekódování je přesně opačné a potřebuje tutéž abecedu 91 znaků — jiná abeceda z týchž bajtů udělá jiný výstup.
Odkud se berou 13 a 14 bitů
Dvojice znaků může pojmenovat 91 × 91 = 8281 hodnot, což je víc než 213 = 8192, ale méně než 214 = 16384. Dvojice znaků tedy vždy unese 13 bitů a někdy 14. Kodér nejprve zkusí 13 bitů: je-li hodnota 13bitové skupiny větší než 88, vytiskne ji jako dva znaky; jinak vezme ještě čtrnáctý bit a vytiskne výslednou 14bitovou hodnotu.
Hranice 88 není libovolná. Největší hodnota, kterou dva znaky mohou pojmenovat, je 90 + 91 × 90 = 8280, a 8192 + 89 = 8281 už ji přesahuje. Žádná 14bitová skupina proto nemůže mít spodní 13bitové okno 89 nebo více, takže dekodér rozliší oba případy pouhým pohledem na samotnou hodnotu:
| Co dekodér vidí | Spotřebované bity | Proč |
|---|
| hodnota & 8191 je 89 až 8191 | 13 bitů | Hodnoty od 89 výše mohou pocházet jen z 13bitové větve, protože 14bitová skupina se spodním 13bitovým oknem tak vysokým by musela být alespoň 8281 — což žádná dvojice znaků nemůže pojmenovat. |
| hodnota & 8191 je 0 až 88 | 14 bitů | Kodér přejde na 14 bitů jen tehdy, když bylo 13bitové čtení 88 nebo méně, takže tato větev je záložní a nic jiného. |
Cokoli zbude na konci — cokoli od 1 do 13 bitů — se vytiskne jako jeden znak, a druhý znak se přidá, pokud zbytek skutečně potřeboval více než 7 bitů. Proto délka zakódovaného výstupu roste po dvou znacích a někdy končí lichým počtem.
Abeceda a tři znaky, které vynechává
Tisknutelné ASCII má 94 znaků, od ! (0x21) po ~ (0x7E). Base91 jich používá 91 a tři, které vynechává, jsou pomlčka -, apostrof ' a zpětné lomítko \. Písmena, číslice a téměř všechna interpunkce jsou v abecedě přesně jednou, v pořadí uvedeném v tabulce výše; 92. až 94. tisknutelný znak prostě nelze adresovat.
Protože abeceda má pevné pořadí, je znak pro danou hodnotu vyhledání, nikoli vzorec. Dvě implementace, které seřadí abecedu jinak, budou obě „Base91“ a nebudou umět číst výstup jedna druhé, což je nejčastější zdroj matoucích výsledků. Tato stránka vypisuje svou abecedu, takže výstup lze vždy vysledovat zpět k ní.
Base91 vedle ostatních tisknutelných kódování
| Kódování | Bitů na znak | Velikost oproti vstupu | Poznámky |
|---|
| Base16 (hex) | 4 | 200% | Dva znaky na bajt, triviálně čitelné, žádná abeceda k vyhledání. |
| Base32 | 5 | 160% | Nerozlišuje velikost písmen a je bezpečná pro diktování, ale nejplýtvavější z této skupiny. |
| Base58 | ~5,86 | ~137% | Zvolena pro adresy, ne pro hustotu: vyhýbá se zaměnitelným znakům. |
| Base64 | 6 | 133% | Všude výchozí: 4 znaky na 3 bajty, přičemž nevyužité bity posledního znaku se ztrácejí. |
| Ascii85 / Base85 | 6,4 | 125% | 5 znaků na 4 bajty, bez vyhledávací tabulky, ale dělí se 85 — viz převodník Ascii85. |
| Base91 | ~6,5 | ~123% | Nejhustší z těchto: 13 bitů na 2 znaky, za cenu 14bitové skupiny tu a tam. |
Procenta jsou zaokrouhlené asymptotické náklady každého kódování; naměřené počty znaků pro jeden skutečný vstup o 92 bajtech jsou v tabulce výše na této stránce. Base91 je blízko nejlepšího, čeho lze s tisknutelným ASCII dosáhnout: 7 bitů na znak by znamenalo použít 128 různých znaků, což tisknutelný rozsah nemůže poskytnout.
Čím Base91 není
- Není to norma. Neexistuje RFC. Referenční implementací je basE91 0.6.0 od Joachima Henkeho, vydaná pod licencí BSD 3-clause; název „Base91“ se používá i pro jiné abecedy, než je tato.
- Není to šifrování. Každý znak je přímé přetvarování bitů vstupu a kdokoli s abecedou to zvrátí v jediném průchodu.
- Není bezpečné pro URL. Abeceda obsahuje
#, %, &, /, ? a ", které v URL mění význam, takže výstup Base91 je nutné procentuálně kódovat, než jej vložíte do dotazu. - Není bezpečné pro HTML. Obsahuje také
<, >, & a ", takže řetězec Base91 vložený do značek se musí escapovat pomocí převodníku HTML entit. - Nemá pevnou délku. Délka výstupu závisí na bitovém vzoru, nikoli jen na počtu bajtů, takže dva vstupy stejné velikosti mohou vytisknout o jeden znak rozdílnou délku.
Pasti, které opravdu kousnou
- Abeceda na této stránce je referenční. Pokud jiný nástroj vytvoří pro týž vstup jiný výstup, porovnejte nejprve jeho abecedu, než předpokládáte, že je rozbitá některá strana. Těch 91 znaků musí být ve stejném pořadí.
- Jediný špatný znak může změnit celý konec. Hranice skupin se určují podle hodnot, které předcházely, takže úprava na začátku řetězce posune vše za ní a konec se dekóduje jen se zbytkovými bity poslední skupiny.
- Lichá délka výstupu je normální. Neznamená, že byl řetězec zkrácen; poslední skupina vytiskne jeden znak, když její zbytková hodnota se vejde do 7 bitů nebo méně.
- Publikovaný příklad může obsahovat konec řádku, který jste nepsali. Shellový příkaz, který přidává konec řádku, je obvyklým důvodem, proč je známá hodnota Base91 o jeden znak delší, než dává tentýž text zde:
echo "Hello, World!" předá kodéru 14 bajtů a vytiskne >OwJh>}AQ;r@@Y?FF, zatímco samotných 13 bajtů textu vytiskne >OwJh>}AQ;r@@Y?F. Obě jsou správně, pro různé počty bajtů, a počet pod výstupním polem říká, kterou hodnotu držíte. - Dekódování binárních dat jako textu nefunguje. Pokud dekódované bajty nejsou platným UTF-8, nelze zobrazit smysluplný text; k tomu slouží hexadecimální režim výstupu.
Rychlé odpovědi
“Proč tato stránka ukazuje hodnotu, která se od jiného nástroje Base91 liší o jeden znak?”
Téměř vždy jiná abeceda. Druhou nejčastější příčinou je nástroj, který používá jen 13bitovou větev a nikdy 14bitový záložní postup; tato varianta je v kódu menší, ale produkuje jiný výstup než referenční algoritmus použitý zde.
Existuje také jeden přesný případ, který lze rozhodnout počítáním bajtů, a vysvětluje nejznámější citovaný příklad: koncový konec řádku. Většina publikovaných vektorů vznikla shellovým příkazem a shell přidává konec řádku, který řádek uzavírá. 13 bajtů Hello, World! se zde vytiskne jako 16 znaků, zatímco 14 bajtů Hello, World! následovaných koncem řádku vytiskne 17znakovou hodnotu >OwJh>}AQ;r@@Y?FF. Vložte kteroukoli hodnotu do dekódování: tato stránka uvádí počet bajtů, takže obě čtení lze rozlišit, místo aby se o nich hádalo. Tlačítko Ukázka načte tu z obou, která patří ke čtenáři, jenž je zrovna zvolen: textový čtenář dostane 16znakovou hodnotu, hexadecimální čtenář 17znakovou se stopou bajtu 0A na očích a kodér dostane text k zakódování, nikoli řetězec Base91; sleduje přepínač Kódovat / Dekódovat a volič Vstup je / Výstup jako.
“Je Base91 menší než Base64?”
Ano, zhruba o 8 % velikosti zakódovaného výstupu: 13 bitů na 2 znaky oproti 6 bitům na znak. U 92 bajtů textu Base64 vytiskne 124 znaků a Base91 vytiskne 114.
“Mohu to dekódovat dekodérem Base64, nebo naopak?”
Ne. Abecedy se překrývají v písmenech a číslicích, takže dekodér Base64 přijme řetězec Base91 jako „platné“ znaky a vyprodukuje tichý nesmysl. Obě se shodují jen v tvaru schématu.
“Končí výstup výplní jako Base64?”
Ne. Base91 nemá žádný výplňový znak: zbytkové bity na konci se vytisknou jako poslední skupina, takže se nic nedoplňuje ani neodebírá.
“Jak poznám, že výsledek na této stránce je správný?”
Stiskněte Autotest 0 až 64 bajtů. Zakóduje a dekóduje 130 bajtových vzorků pokrývajících každou délku, při které se dělení na 13 a 14 bitů mění, a porovná bajty, které se vrátí, s bajty, které vstoupily. Vektory tlačítka Ukázka jsou navíc zkřížené s druhou implementací napsanou pro testovací nástroje tohoto webu.
Normy a uznání
Tato stránka implementuje algoritmus referenční implementace basE91 (verze 0.6.0) od Joachima Henkeho, distribuované pod licencí BSD 3-clause, s abecedou vypsanou výše. Dekódování přijímá bílé znaky a ignoruje je, stejně jako referenční nástroj.
Texty stránky byly napsány pro tento web; algoritmus nebyl odnikud zkopírován. Hodnoty tlačítka Ukázka jsou jediný příklad, který dodává referenční balík (označen jako „reference example“), a hodnoty vytvořené druhou, nezávislou implementací uloženou v testovacích nástrojích webu (označeny jako „cross-check“).
