Base91 coderen / decoderen

Base91 is een manier om willekeurige bytes te schrijven met uitsluitend afdrukbare ASCII-tekens, hetzelfde werk als Base64, maar het past meer bits in elk teken. In plaats van de invoer in groepen van 6 bits te hakken en per groep één teken af te drukken, verzamelt het bits totdat er minstens 13 zijn, en drukt dan twee tekens af die samen de waarde van die 13 (of 14) bits benoemen.

Twee tekens uit een alfabet van 91 kunnen 91 × 91 = 8281 verschillende waarden benoemen, en 2¹³ = 8192, dus twee tekens hebben altijd ruimte voor 13 bits — met 89 waarden over. Dat is de hele truc: 13 bits per 2 tekens is 6,5 bits per teken, tegenover 6 bij Base64, en het levert ongeveer 23% overhead op in plaats van 33%.

91 × 91 = 8281 waarden kunnen door een paar tekens worden benoemd, wat meer is dan 2¹³ = 8192 maar minder dan 2¹⁴ = 16384. Een paar tekens kan dus altijd 13 bits dragen, en soms 14. De encoder probeert eerst 13 bits: als de 13-bitwaarde groter is dan 88, drukt hij die waarde als twee tekens af; anders neemt hij een veertiende bit en drukt de resulterende 14-bitwaarde af.

De grens bij 88 is niet willekeurig. De grootste waarde die twee tekens kunnen benoemen is 90 + 91 × 90 = 8280, en 8192 + 89 = 8281 ligt daar al voorbij. Dus geen 14-bitgroep kan ooit een laag 13-bitvenster van 89 of meer hebben, wat betekent dat de decoder de twee gevallen kan onderscheiden door alleen naar de waarde zelf te kijken:

Wat de decoder ziet	Verbruikte bits	Waarom
waarde & 8191 is 89 tot 8191	13 bits	Waarden van 89 en hoger kunnen alleen uit de 13-bitvertakking komen, want een 14-bitgroep met een laag 13-bitvenster zo hoog zou minstens 8281 moeten zijn — wat geen paar tekens kan benoemen.
waarde & 8191 is 0 tot 88	14 bits	De encoder valt alleen terug op 14 bits wanneer de 13-bitlezing 88 of lager was, dus deze vertakking is de terugval en niets anders.

Wat aan het eind overblijft — alles van 1 tot 13 bits — wordt afgedrukt als één teken, plus een tweede teken wanneer de rest echt meer dan 7 bits nodig had. Daarom groeit de gecodeerde lengte in stappen van twee tekens en eindigt hij soms op een oneven aantal.

Afdrukbare ASCII heeft 94 tekens, van ! (0x21) tot ~ (0x7E). Base91 gebruikt er 91 ervan, en de drie die het weglaat zijn het koppelteken -, het apostrof ' en de backslash \. Letters, cijfers en bijna alle leestekens staan precies één keer in het alfabet, in de volgorde die in de tabel hierboven is getoond; het 92e tot en met 94e afdrukbare teken is gewoon niet adresseerbaar.

Omdat het alfabet een vaste volgorde heeft, is het teken voor een waarde een opzoeking en geen formule. Twee implementaties die het alfabet anders ordenen, zijn beide "Base91" en kunnen elkaars uitvoer niet lezen, wat de meest voorkomende bron van verwarrende resultaten is. Deze pagina drukt zijn alfabet af, zodat de uitvoer altijd tot het alfabet te herleiden is.

Codering	Bits per teken	Grootte ten opzichte van de invoer	Opmerkingen
Base16 (hex)	4	200%	Twee tekens per byte, triviaal leesbaar, geen alfabet om op te zoeken.
Base32	5	160%	Hoofdletterongevoelig en veilig om te dicteren, maar de verspillendste van de groep.
Base58	~5,86	~137%	Gekozen voor adressen, niet voor dichtheid: het vermijdt op elkaar lijkende tekens.
Base64	6	133%	De standaard overal: 4 tekens per 3 bytes, met de 6 ongebruikte bits van het laatste teken verspild.
Ascii85 / Base85	6,4	125%	5 tekens per 4 bytes, geen opzoektabel nodig, maar het deelt door 85 — zie de Ascii85-converter.
Base91	~6,5	~123%	De dichtste van deze: 13 bits per 2 tekens, tegen de prijs van hier en daar een 14-bitgroep.

De percentages zijn de asymptotische kosten van elke codering, afgerond; de gemeten tekenaantallen voor één echte invoer van 92 bytes staan in de tabel hierboven op deze pagina. Base91 zit dicht bij het beste wat een codering met afdrukbare ASCII kan doen: 7 bits per teken zou 128 verschillende tekens vereisen, wat het afdrukbare bereik niet kan leveren.

• Geen standaard. Er is geen RFC. De referentie-implementatie is basE91 0.6.0 van Joachim Henke, uitgebracht onder de BSD 3-clausulelicentie; "Base91" wordt ook gebruikt voor alfabetten die niet dit zijn.
• Geen versleuteling. Elk teken is een rechtstreekse herschikking van de invoerbits, en iedereen met het alfabet kan dat in één keer terugdraaien.
• Niet URL-veilig. Het alfabet bevat #, %, &, /, ? en ", die allemaal een betekenis in een URL veranderen, dus Base91-uitvoer moet met percentcodering worden gecodeerd voordat het in een queryreeks komt.
• Niet HTML-veilig. Het bevat ook <, >, & en ", dus een Base91-tekenreeks die in opmaak wordt geplaatst, moet met de HTML-entiteitenconverter worden ge-escaped.
• Geen vaste lengte. De uitvoerlengte hangt af van het bitpatroon, niet alleen van het aantal bytes, dus twee invoeren van dezelfde grootte kunnen één teken verschillen.

• Het alfabet op deze pagina is het referentiealfabet. Als een ander hulpmiddel andere uitvoer geeft voor dezelfde invoer, vergelijk dan eerst het alfabet voordat u aanneemt dat een van beide kanten kapot is. De 91 tekens moeten in dezelfde volgorde voorkomen.
• Eén verkeerd teken kan de hele staart veranderen. Groepsgrenzen worden bepaald door de waarden die ervoor kwamen, dus een bewerking vroeg in de tekenreeks verschuift alles daarna, en de staart wordt alleen met de overgebleven bits van de laatste groep gedecodeerd.
• Oneven uitvoerlengte is normaal. Het betekent niet dat de tekenreeks is afgekapt; de laatste groep drukt één teken af wanneer de overgebleven waarde in 7 bits of minder past.
• Een gepubliceerd voorbeeld kan een regeleinde bevatten dat u niet hebt getypt. Een shell-commando dat een regeleinde toevoegt, is de gebruikelijke reden dat een bekende Base91-waarde één teken langer is dan dezelfde tekst hier oplevert: echo "Hello, World!" geeft de encoder 14 bytes en drukt >OwJh>}AQ;r@@Y?FF af, terwijl de 13 bytes van alleen de tekst >OwJh>}AQ;r@@Y?F afdrukken. Beide zijn correct, voor verschillende bytetellingen, en de telling onder het uitvoervak vertelt welke u vasthoudt.
• Binaire gegevens als tekst decoderen werkt niet. Als de gedecodeerde bytes geen geldige UTF-8 zijn, is er geen zinvolle tekst om te tonen; daarvoor is de hexadecimale uitvoermodus bedoeld.

“Waarom toont deze pagina een waarde die één teken verschilt van een andere Base91-tool?”

Bijna altijd een ander alfabet. De op één na meest voorkomende oorzaak is een hulpmiddel dat alleen de 13-bitvertakking gebruikt en nooit de 14-bitterugval; die variant is kleiner in code, maar produceert andere uitvoer dan het referentie-algoritme dat hier wordt gebruikt.

Er is ook één exact geval dat door tellen van bytes kan worden opgelost, en het verklaart het meest geciteerde voorbeeld van allemaal: een afsluitend regeleinde. De meeste gepubliceerde vectoren zijn geproduceerd door een shell-commando, en de shell voegt het regeleinde toe dat de regel afsluit. De 13 bytes van Hello, World! drukken hier 16 tekens af, terwijl de 14 bytes van Hello, World! gevolgd door een regeleinde het 17-tekenresultaat >OwJh>}AQ;r@@Y?FF afdrukken. Plak een van beide waarden in Decoderen: deze pagina meldt het aantal bytes, zodat de twee lezingen van elkaar te onderscheiden zijn in plaats van dat erover wordt gediscussieerd. De knop Voorbeeld laadt degene die bij de gebruikte lezer hoort, en volgt de schakelaar Coderen / Decoderen en de keuzelijst Invoer is / Uitvoer als: de tekstlezer krijgt de waarde van 16 tekens, de hexadecimale lezer de 17-tekenwaarde met de afsluitende 0A-byte duidelijk zichtbaar, en de encoder krijgt de tekst om te coderen in plaats van een Base91-tekenreeks.

“Is Base91 kleiner dan Base64?”

Ja, met ongeveer 8% van de gecodeerde grootte: 13 bits per 2 tekens tegenover 6 bits per teken. Bij 92 bytes tekst drukt Base64 124 tekens af en Base91 114.

“Kan ik dit met een Base64-decoder decoderen, of andersom?”

Nee. De alfabetten overlappen in de letters en cijfers, dus een Base64-decoder accepteert een Base91-tekenreeks als "geldige" tekens en levert stille onzin op. De twee zijn het alleen eens over de vorm van het schema.

“Eindigt de uitvoer met opvulling zoals Base64?”

Nee. Base91 heeft helemaal geen opvultekens: de overgebleven bits aan het eind worden als laatste groep afgedrukt, dus er hoeft niets te worden toegevoegd of verwijderd.

“Hoe weet ik dat het resultaat op deze pagina klopt?”

Druk op Zelftest 0 tot 64 bytes. Die codeert en decodeert 130 bytepatronen die elke lengte dekken waarbij de 13- en 14-bitsplitsing verandert, en vergelijkt de teruggekregen bytes met de bytes die erin gingen. De vectoren van de knop Voorbeeld worden daarnaast gekruisgecontroleerd tegen een tweede implementatie die voor de testtools van deze site is geschreven.

Deze pagina implementeert het algoritme van de referentie-implementatie basE91 (versie 0.6.0) van Joachim Henke, verspreid onder de BSD 3-clausulelicentie, met het hierboven afgedrukte alfabet. Decoderen accepteert witruimte en negeert die, zoals het referentiehulpmiddel doet.

De paginatekst is voor deze site geschreven; het algoritme is nergens vandaan gekopieerd. De waarden van de knop Voorbeeld zijn het ene voorbeeld dat in het referentiepakket wordt meegeleverd (gemarkeerd als "referentievoorbeeld") plus waarden die door een tweede, onafhankelijke implementatie zijn geproduceerd, bewaard in de testtools van deze site (gemarkeerd als "kruiscontrole").