Ce este Base91?
Base91 este o modalitate de a scrie octeți arbitrari folosind doar caractere ASCII tipăribile, același rol pe care îl are Base64, dar încape mai mulți biți în fiecare caracter. În loc să taie intrarea în grupuri de 6 biți și să tipărească un caracter pe grup, colectează biți până are cel puțin 13, apoi tipărește două caractere care, împreună, numesc valoarea acelor 13 (sau 14) biți.
Două caractere dintr-un alfabet de 91 pot numi 91 × 91 = 8281 de valori diferite, iar 213 = 8192, deci două caractere au întotdeauna loc pentru 13 biți — cu 89 de valori în plus. Asta este tot trucul: 13 biți la 2 caractere înseamnă 6,5 biți pe caracter, față de 6 la Base64, și oferă aproximativ 23% de supradimensionare în loc de 33%.
Versiunea de 30 de secunde: test devine fPNKd, iar Hello, World! devine >OwJh>}AQ;r@@Y?F. Decodarea este inversul exact și are nevoie de același alfabet de 91 de caractere — un alt alfabet dă alt rezultat din aceiași octeți.
De unde vin cei 13 și cei 14 biți
91 × 91 = 8281 de valori pot fi numite de o pereche de caractere, ceea ce este mai mult decât 213 = 8192, dar mai puțin decât 214 = 16384. Deci o pereche de caractere poate purta întotdeauna 13 biți și uneori 14. Codorul încearcă mai întâi 13 biți: dacă valoarea de 13 biți este mai mare decât 88, o tipărește ca două caractere; altfel ia un al 14-lea bit și tipărește valoarea rezultată de 14 biți.
Limita de 88 nu este arbitrară. Cea mai mare valoare pe care o pot numi două caractere este 90 + 91 × 90 = 8280, iar 8192 + 89 = 8281 o depășește deja. Deci niciun grup de 14 biți nu poate avea o fereastră inferioară de 13 biți de 89 sau mai mult, ceea ce înseamnă că decodorul poate distinge cele două cazuri uitându-se doar la valoarea în sine:
| Ce vede decodorul | Cantitate de biți | De ce |
|---|
| valoarea & 8191 este între 89 și 8191 | 13 biți | Valorile de la 89 în sus pot veni doar din ramura de 13 biți, pentru că un grup de 14 biți cu o fereastră inferioară de 13 biți atât de mare ar trebui să fie cel puțin 8281 — ceea ce nicio pereche de caractere nu poate numi. |
| valoarea & 8191 este între 0 și 88 | 14 biți | Codorul trece la 14 biți doar când citirea pe 13 biți a fost 88 sau mai puțin, deci această ramură este varianta de rezervă și nimic altceva. |
Ce rămâne la final — orice între 1 și 13 biți — se tipărește ca un caracter, plus un al doilea caracter atunci când restul avea nevoie de mai mult de 7 biți. De aceea lungimea codificată crește în pași de câte două caractere și uneori se termină cu un număr impar.
Alfabetul și cele trei caractere pe care le lasă deoparte
ASCII tipăribil are 94 de caractere, de la ! (0x21) la ~ (0x7E). Base91 folosește 91 dintre ele, iar cele trei lăsate deoparte sunt cratima -, apostroful ' și bara inversă \. Literele, cifrele și aproape toată punctuația sunt în alfabet o singură dată, în ordinea arătată în tabelul de mai sus; caracterele 92 până la 94 din domeniul tipăribil pur și simplu nu pot fi adresate.
Pentru că alfabetul are o ordine fixă, caracterul pentru o valoare se găsește printr-o căutare, nu printr-o formulă. Două implementări care ordonează alfabetul diferit vor fi amândouă „Base91” și nu își vor putea citi reciproc ieșirea, ceea ce este cea mai frecventă sursă de rezultate confuze. Pagina își tipărește alfabetul, astfel încât ieșirea să poată fi mereu urmărită înapoi până la el.
Base91 alături de celelalte codificări tipăribile
| Codificare | Biți pe caracter | Dimensiune față de intrare | Note |
|---|
| Base16 (hexazecimal) | 4 | 200% | Două caractere pe octet, ușor de citit, fără tabel de căutare. |
| Base32 | 5 | 160% | Insensibilă la majuscule și sigură la dictare, dar cea mai risipitoare din grup. |
| Base58 | ~5,86 | ~137% | Aleasă pentru adrese, nu pentru densitate: evită caracterele care se confundă vizual. |
| Base64 | 6 | 133% | Implicită peste tot: 4 caractere la 3 octeți, iar ultimul caracter irosește o parte din biți. |
| Ascii85 / Base85 | 6,4 | 125% | 5 caractere la 4 octeți, fără tabel de căutare, dar împarte la 85 — vezi convertorul Ascii85. |
| Base91 | ~6,5 | ~123% | Cea mai densă dintre acestea: 13 biți la 2 caractere, cu prețul unui grup de 14 biți din când în când. |
Procentele sunt costul asimptotic al fiecărei codificări, rotunjite; numărul măsurat de caractere pentru o intrare reală de 92 de octeți se află în tabelul de mai sus de pe pagină. Base91 este aproape de ce poate face orice codificare cu caractere ASCII tipăribile: 7 biți pe caracter ar presupune 128 de caractere distincte, pe care domeniul tipăribil nu le poate oferi.
Ce nu este Base91
- Nu este un standard. Nu există RFC. Implementarea de referință este basE91 0.6.0 de Joachim Henke, distribuită sub licența BSD cu 3 clauze; „Base91” este folosit și pentru alte alfabete, nu doar pentru acesta.
- Nu este criptare. Fiecare caracter este o simplă reașezare a biților din intrare, iar oricine are alfabetul o poate inversa dintr-o singură trecere.
- Nu este sigur pentru URL. Alfabetul conține
#, %, &, /, ? și ", care își schimbă sensul într-un URL, deci ieșirea Base91 trebuie codificată procentual înainte de a fi pusă într-un șir de interogare.
- Nu este sigur pentru HTML. Conține și
<, >, & și ", deci un șir Base91 pus în marcaj trebuie escapat cu convertorul de entități HTML.
- Nu are lungime fixă. Lungimea ieșirii depinde de modelul biților, nu doar de numărul de octeți, deci două intrări de aceeași dimensiune pot tipări un caracter în plus sau în minus.
Capcane care chiar mușcă
- Alfabetul din pagină este cel de referință. Dacă alt instrument produce altă ieșire pentru aceeași intrare, se compară alfabetul lui înainte de a presupune că una dintre părți este defectă. Cele 91 de caractere trebuie să apară în aceeași ordine.
- Un singur caracter greșit poate schimba toată coada. Limitele grupurilor sunt decise de valorile dinainte, deci o modificare de la început deplasează tot ce urmează, iar coada se decodează doar cu biții rămași din ultimul grup.
- Lungimea impară a ieșirii este normală. Nu înseamnă că șirul a fost tăiat; ultimul grup tipărește un caracter când valoarea rămasă încape în 7 biți sau mai puțin.
- Un exemplu publicat poate avea un rând nou care nu a fost tastat. O comandă de shell care adaugă un terminator de linie este motivul obișnuit pentru care o valoare Base91 cunoscută este cu un caracter mai lungă decât produce același text aici:
echo "Hello, World!" îi dă codorului 14 octeți și tipărește >OwJh>}AQ;r@@Y?FF, în timp ce cei 13 octeți doar ai textului tipăresc >OwJh>}AQ;r@@Y?F. Ambele sunt corecte, pentru numere diferite de octeți, iar numărul de sub caseta de ieșire arată care dintre cele două valori este cea obținută.
- Decodarea datelor binare ca text nu va funcționa. Dacă octeții obținuți la decodare nu sunt UTF-8 valid, nu există un text rezonabil de arătat, pentru asta există modul de ieșire hexazecimal.
Răspunsuri rapide
„De ce arată această pagină o valoare cu un caracter diferit față de alt instrument Base91?”
Aproape întotdeauna un alt alfabet. A doua cauză cea mai frecventă este un instrument care folosește doar ramura de 13 biți și niciodată varianta de rezervă de 14 biți; acea variantă este mai mică în cod, dar produce altă ieșire decât algoritmul de referință folosit aici.
Există și un caz exact care poate fi lămurit numărând octeții, și explică cel mai citat exemplu din toate: un rând nou final. Majoritatea vectorilor din publicații au fost produși printr-o comandă de shell, iar shell-ul adaugă terminatorul de linie care încheie rândul. Cei 13 octeți ai lui Hello, World! tipăresc aici 16 caractere, în timp ce cei 14 octeți ai lui Hello, World! plus un rând nou tipăresc cele 17 caractere >OwJh>}AQ;r@@Y?FF. Se lipește oricare valoare în Decodare: pagina raportează numărul de octeți, astfel încât cele două citiri pot fi deosebite fără discuții. Butonul Exemplu încarcă cea care aparține cititorului utilizat și urmează comutatorul Codificare / Decodare și selectorul Intrarea este / Ieșire ca: cititorul de text primește valoarea de 16 caractere, cititorul hexazecimal pe cea de 17 caractere, cu octetul 0A final vizibil, iar codificatorul primește textul de codificat și nu un șir Base91.
„Este Base91 mai mic decât Base64?”
Da, cu aproximativ 8% din dimensiunea codificată: 13 biți la 2 caractere, față de 6 biți pe caracter. Pentru 92 de octeți de text, Base64 tipărește 124 de caractere, iar Base91 tipărește 114.
„Pot decoda asta cu un decodor Base64 sau invers?”
Nu. Alfabetele se suprapun la litere și cifre, deci un decodor Base64 va accepta un șir Base91 drept caractere „valide” și va produce gunoi fără vreo eroare. Cele două coincid doar în forma schemei.
„Se termină ieșirea cu umplutură, ca Base64?”
Nu. Base91 nu are deloc caracter de umplutură: biții rămași la final sunt scriși ca ultimul grup, deci nu trebuie adăugat sau eliminat nimic.
„De unde știu că rezultatul de pe această pagină este corect?”
Se apasă butonul Autotest de la 0 la 64 de octeți. Acesta codifică și decodifică 130 de modele de octeți care acoperă fiecare lungime la care se schimbă împărțirea pe 13 și 14 biți și compară octeții care revin cu cei care au intrat. Vectorii butonului Exemplu sunt în plus supuși unei verificări încrucișate cu o a doua implementare scrisă pentru uneltele de test ale acestui site.
Standarde și creditare
Pagina implementează algoritmul din implementarea de referință basE91 (versiunea 0.6.0) a lui Joachim Henke, distribuită sub licența BSD cu 3 clauze, cu alfabetul tipărit mai sus. Decodarea acceptă și ignoră spațiile albe, ca instrumentul de referință.
Textul paginii a fost scris pentru acest site; algoritmul nu a fost copiat de nicăieri. Valorile butonului Exemplu sunt exemplul unic livrat cu pachetul de referință (marcat „exemplu de referință”) plus valori produse de o a doua implementare independentă, păstrată în uneltele de test ale acestui site (marcate „verificare încrucișată”).
