Hvad er Base91?
Base91 er en måde at skrive vilkårlige bytes på med kun udskrivbare ASCII-tegn — samme opgave, som Base64 udfører, men med flere bit i hvert tegn. I stedet for at dele inputtet op i 6-bit-grupper og udskrive ét tegn pr. gruppe, samler det bit, indtil der er mindst 13, og udskriver derefter to tegn, der tilsammen angiver værdien af de 13 (eller 14) bit.
To tegn ud af et alfabet på 91 kan angive 91 × 91 = 8281 forskellige værdier, og 213 = 8192, så to tegn har altid plads til 13 bit — med 89 værdier til overs. Det er hele tricket: 13 bit pr. 2 tegn er 6,5 bit pr. tegn, mod Base64s 6, og det giver ca. 23% overhead i stedet for 33%.
Versionen på 30 sekunder: test bliver til fPNKd, og Hello, World! bliver til >OwJh>}AQ;r@@Y?F. Dekodning er den nøjagtige omvendte proces, og den kræver det samme 91-tegnsalfabet — et andet alfabet giver et andet output fra de samme bytes.
Hvor de 13 og 14 bit kommer fra
91 × 91 = 8281 værdier kan angives med et par tegn, hvilket er mere end 213 = 8192, men mindre end 214 = 16384. Et par tegn kan derfor altid bære 13 bit og nogle gange 14. Koderen forsøger først 13 bit: hvis 13-bit-værdien er større end 88, udskriver den værdien som to tegn; ellers tager den en 14. bit og udskriver den resulterende 14-bit-værdi i stedet.
Grænsen ved 88 er ikke vilkårlig. Den største værdi, to tegn kan angive, er 90 + 91 × 90 = 8280, og 8192 + 89 = 8281 ligger allerede over den. Så ingen 14-bit-gruppe kan nogensinde have et lavt 13-bit-vindue på 89 eller mere, hvilket betyder, at dekoderen kan skelne de to tilfælde ved kun at se på selve værdien:
| Hvad dekoderen ser | Bit den bruger | Hvorfor |
|---|
| værdi & 8191 er 89 til 8191 | 13 bit | Værdier på 89 og op kan kun komme fra 13-bit-grenen, fordi en 14-bit-gruppe med et så højt lavt 13-bit-vindue skulle være mindst 8281 — hvilket intet par tegn kan angive. |
| værdi & 8191 er 0 til 88 | 14 bit | Koderen falder kun tilbage til 14 bit, når 13-bit-læsningen var 88 eller mindre, så denne gren er fallbacken og intet andet. |
Det, der er tilbage til sidst — alt fra 1 til 13 bit — udskrives som ét tegn, plus et andet tegn, når resten faktisk krævede mere end 7 bit. Derfor vokser den kodede længde i trin af to tegn og ender nogle gange på et ulige antal.
Alfabetet, og de tre tegn det udelader
Udskrivbar ASCII har 94 tegn, fra ! (0x21) til ~ (0x7E). Base91 bruger 91 af dem, og de tre, der udelades, er bindestregen -, apostroffen ' og omvendt skråstreg \. Bogstaver, cifre og næsten al tegnsætning findes i alfabetet præcis én gang, i rækkefølgen vist i tabellen ovenfor; det 92. til 94. udskrivbare tegn kan simpelthen ikke adresseres.
Fordi alfabetet har en fast rækkefølge, er tegnet for en værdi et opslag og ikke en formel. To implementeringer, der ordner alfabetet forskelligt, vil begge kalde sig "Base91" og ikke kunne læse hinandens output, hvilket er den hyppigste kilde til forvirrende resultater. Denne side udskriver sit alfabet, så outputtet altid kan spores tilbage til det.
Base91 sammenlignet med de andre udskrivbare kodninger
| Kodning | Bit pr. tegn | Størrelse i forhold til input | Noter |
|---|
| Base16 (hex) | 4 | 200% | To tegn pr. byte, trivielt at læse, intet alfabet at slå op i. |
| Base32 | 5 | 160% | Er ikke versalfølsom og velegnet til at diktere, men den mest spildende i gruppen. |
| Base58 | ~5,86 | ~137% | Valgt til adresser, ikke for tæthed: den undgår tegn, der ligner hinanden. |
| Base64 | 6 | 133% | Standarden alle steder: 4 tegn pr. 3 bytes, hvor de 6 ubrugte bit i det sidste tegn spildes. |
| Ascii85 / Base85 | 6,4 | 125% | 5 tegn pr. 4 bytes, ingen opslagstabel nødvendig, men den dividerer med 85 — se Ascii85-konverteren. |
| Base91 | ~6,5 | ~123% | Den tætteste af disse: 13 bit pr. 2 tegn, til gengæld for en 14-bit-gruppe her og der. |
De procentdele er de asymptotiske omkostninger for hver kodning, afrundet; de målte tegnantal for ét reelt input på 92 bytes står i tabellen længere oppe på siden. Base91 er tæt på det bedste, enhver kodning kan opnå med udskrivbar ASCII: 7 bit pr. tegn ville kræve 128 forskellige tegn, hvilket det udskrivbare område ikke kan levere.
Hvad Base91 ikke er
- Ingen standard. Der findes ingen RFC. Referenceimplementeringen er basE91 0.6.0 af Joachim Henke, udgivet under BSD 3-klausul-licensen; "Base91" bruges også om alfabeter, der ikke er dette.
- Ikke kryptering. Hvert tegn er en direkte omformning af inputbittene, og enhver, der kender alfabetet, kan vende processen i ét gennemløb.
- Ikke URL-sikker. Alfabetet indeholder
#, %, &, /, ? og ", og alle disse ændrer betydning i en URL. Base91-output skal derfor procentkodes, før det sættes i en forespørgselsstreng. - Ikke HTML-sikker. Det indeholder også
<, >, & og ", så en Base91-streng, der indsættes i markup, skal escapes med HTML-entitetskonverteren. - Ikke fast længde. Outputlængden afhænger af bitmønsteret, ikke kun af antallet af bytes, så to input af samme størrelse kan give ét tegn forskel.
Fælder, der faktisk bider
- Alfabetet på denne side er referencealfabetet. Hvis et andet værktøj giver andet output for samme input, skal dets alfabet sammenlignes, før man antager, at en af siderne er i stykker. De 91 tegn skal optræde i samme rækkefølge.
- Et enkelt forkert tegn kan ændre hele halen. Gruppegrænser afgøres af de værdier, der kom før, så en redigering tidligt i strengen forskyder alt efter den, og halen dekodes kun med de resterende bit fra den sidste gruppe.
- Ulige outputlængde er normal. Det betyder ikke, at strengen blev afkortet; den sidste gruppe udskriver ét tegn, når dens resterende værdi passer i 7 bit eller mindre.
- Et offentliggjort eksempel kan indeholde et linjeskift, der ikke blev skrevet. En shell-kommando, der tilføjer et linjeskift, er den almindelige årsag til, at en velkendt Base91-værdi er ét tegn længere end den samme tekst giver her:
echo "Hello, World!" giver koderen 14 bytes og udskriver >OwJh>}AQ;r@@Y?FF, mens de 13 bytes af selve teksten udskriver >OwJh>}AQ;r@@Y?F. Begge er korrekte, for forskellige bytetal, og tællingen under outputfeltet viser, hvilken af dem man har. - Dekodning af binære data som tekst virker ikke. Hvis de dekodede bytes ikke er gyldig UTF-8, er der ingen fornuftig tekst at vise, og netop dét er den hexadecimale outputtilstand til.
Hurtige svar
“Hvorfor viser denne side en værdi, der er ét tegn forskellig fra et andet Base91-værktøj?”
Næsten altid et andet alfabet. Den næsthyppigste årsag er et værktøj, der kun bruger 13-bit-grenen og aldrig 14-bit-fallbacken; den variant er mindre i koden, men giver et andet output end referencealgoritmen, der bruges her.
Der er også ét præcist tilfælde, der kan afgøres ved at tælle bytes, og det forklarer det mest citerede eksempel af alle: et efterstillet linjeskift. De fleste offentliggjorte vektorer blev produceret med en shell-kommando, og shellen tilføjer linjeskiftet, der afslutter linjen. De 13 bytes i Hello, World! udskrives her som 16 tegn, mens de 14 bytes i Hello, World! efterfulgt af et linjeskift udskriver de 17 tegn >OwJh>}AQ;r@@Y?FF. Indsæt en af værdierne under Dekod: denne side viser antallet af bytes, så de to læsninger kan skelnes i stedet for at diskuteres. Knappen Eksempel indlæser den af de to værdier, der hører til den læser, man bruger, og den følger skiftet Kod / Dekod og vælgeren Input er / Output som: tekstlæseren får 16-tegns-værdien, den hexadecimale læser får 17-tegns-værdien med sin efterstillede 0A-byte synlig, og koderen får den tekst, der skal kodes, i stedet for en Base91-streng.
“Er Base91 mindre end Base64?”
Ja, med cirka 8% af den kodede størrelse: 13 bit pr. 2 tegn mod 6 bit pr. tegn. På 92 bytes tekst udskriver Base64 124 tegn, og Base91 udskriver 114.
“Kan jeg dekode dette med en Base64-dekoder, eller omvendt?”
Nej. Alfabeterne overlapper i bogstaver og cifre, så en Base64-dekoder vil acceptere en Base91-streng som "gyldige" tegn og give lydløst affald. De to er kun enige om selve skemaets form.
“Slutter outputtet med padding ligesom Base64?”
Nej. Base91 har slet ingen padding-tegn: de resterende bit til sidst udskrives som den sidste gruppe, så intet skal tilføjes eller fjernes.
“Hvordan ved jeg, at resultatet på denne side er rigtigt?”
Tryk på Selvtest 0 til 64 bytes. Den koder og dekoder 130 bytemønstre, der dækker hver længde, hvor 13- og 14-bit-opdelingen ændrer sig, og sammenligner de bytes, der kommer tilbage, med dem, der blev sendt ind. Vektorerne på eksempelknappen krydstjekkes desuden mod en anden implementering, skrevet til denne sides testværktøjer.
Standarder og krediteringer
Denne side implementerer algoritmen fra basE91-referenceimplementeringen (version 0.6.0) af Joachim Henke, distribueret under BSD 3-klausul-licensen, med alfabetet vist ovenfor. Dekodning accepterer og ignorerer mellemrum, ligesom referenceværktøjet gør.
Sidens tekst er skrevet til denne side; algoritmen er ikke kopieret fra nogen steder. Eksempelknappens værdier er det ene eksempel, der følger med referencepakken (markeret "reference example"), samt værdier fra en anden, uafhængig implementering, som ligger i denne sides testværktøjer (markeret "cross-check").
