Vad är Base91?
Base91 är ett sätt att skriva godtyckliga byte med enbart utskrivbara ASCII-tecken, samma uppgift som Base64 löser, men det får plats med fler bitar i varje tecken. I stället för att hugga indata i sexbitarsgrupper och skriva ut ett tecken per grupp samlas bitar tills det finns minst 13 av dem, och sedan skrivs två tecken ut som tillsammans anger värdet för de 13 (eller 14) bitarna.
Två tecken ur ett alfabet på 91 kan ange 91 × 91 = 8281 olika värden, och 213 = 8192, så två tecken har alltid plats för 13 bitar — med 89 värden över. Det är hela tricket: 13 bitar per 2 tecken är 6,5 bitar per tecken, mot Base64:s 6, och det ger cirka 23 % överhead i stället för 33 %.
Versionen på 30 sekunder: test blir fPNKd, och Hello, World! blir >OwJh>}AQ;r@@Y?F. Avkodningen är exakt det omvända, och den kräver samma alfabet på 91 tecken — ett annat alfabet ger annan utdata från samma byte.
Var de 13 och 14 bitarna kommer från
91 × 91 = 8281 värden kan anges av ett par tecken, vilket är mer än 213 = 8192 men mindre än 214 = 16384. Ett par tecken kan alltså alltid bära 13 bitar, och ibland 14. Kodaren försöker 13 bitar först: om 13-bitarsvärdet är större än 88 skrivs det värdet ut som två tecken; annars tar den en 14:e bit och skriver ut det resulterande 14-bitarsvärdet i stället.
Gränsen vid 88 är inte godtycklig. Det största värdet två tecken kan ange är 90 + 91 × 90 = 8280, och 8192 + 89 = 8281 ligger redan utanför. Därför kan en 14-bitarsgrupp aldrig ha ett lågt 13-bitarsfönster på 89 eller mer, vilket betyder att avkodaren kan skilja de två fallen åt genom att titta enbart på värdet:
| Vad avkodaren ser | Bitar den förbrukade | Varför |
|---|
| värde & 8191 är 89 till 8191 | 13 bitar | Värden från 89 och uppåt kan bara komma från 13-bitarsgrenen, eftersom en 14-bitarsgrupp med ett lågt 13-bitarsfönster så högt skulle behöva vara minst 8281 — vilket inget par tecken kan ange. |
| värde & 8191 är 0 till 88 | 14 bitar | Kodaren faller bara tillbaka till 14 bitar när 13-bitarsläsningen var 88 eller lägre, så den här grenen är reservlösningen och inget annat. |
Det som blir över i slutet — allt från 1 till 13 bitar — skrivs ut som ett tecken, och ett andra tecken när resten verkligen behövde mer än 7 bitar. Därför växer den kodade längden i steg om två tecken och slutar ibland på ett udda antal.
Alfabetet och de tre tecken det utelämnar
Utskrivbar ASCII innehåller 94 tecken, från ! (0x21) till ~ (0x7E). Base91 använder 91 av dem, och de tre som utelämnas är bindestreck -, apostrof ' och omvänt snedstreck \. Bokstäver, siffror och nästan all interpunktion finns i alfabetet exakt en gång, i den ordning som visas i tabellen ovan; det 92:a till 94:e utskrivbara tecknet kan helt enkelt inte adresseras.
Eftersom alfabetet är en fast ordning är tecknet för ett värde ett uppslag och inte en formel. Två implementationer som ordnar alfabetet olika kommer båda att kalla sig "Base91" och kan inte läsa varandras utdata, vilket är den enskilt vanligaste orsaken till förvirrande resultat. Den här sidan skriver ut sitt alfabet så att utdata alltid kan spåras tillbaka till det.
Base91 jämfört med de andra utskrivbara kodningarna
| Kodning | Bitar per tecken | Storlek jämfört med indata | Anteckningar |
|---|
| Base16 (hex) | 4 | 200% | Två tecken per byte, lätt att läsa, inget alfabet att slå upp. |
| Base32 | 5 | 160% | Skiftlägesokänslig och säker för diktering, men den mest slösaktiga i gruppen. |
| Base58 | ~5,86 | ~137% | Vald för adresser, inte för täthet: den undviker lika utseende tecken. |
| Base64 | 6 | 133% | Standard överallt: 4 tecken per 3 byte, där de 6 oanvända bitarna i det sista tecknet går till spillo. |
| Ascii85 / Base85 | 6,4 | 125% | 5 tecken per 4 byte, ingen uppslagstabell behövs, men den dividerar med 85 — se Ascii85-konverteraren. |
| Base91 | ~6,5 | ~123% | Den tätaste av dessa: 13 bitar per 2 tecken, till priset av en 14-bitarsgrupp här och där. |
Procenttalen är den asymptotiska kostnaden för varje kodning, avrundad; de uppmätta teckenantalen för en verklig indata på 92 byte finns i tabellen längre upp på sidan. Base91 ligger nära det bästa som någon kodning kan göra med utskrivbar ASCII: 7 bitar per tecken skulle kräva 128 olika tecken, vilket det utskrivbara området inte kan ge.
Vad Base91 inte är
- Ingen standard. Det finns ingen RFC. Referensimplementeringen är basE91 0.6.0 av Joachim Henke, utgiven under BSD 3-klausullicensen; "Base91" används också för alfabet som inte är detta.
- Inte kryptering. Varje tecken är en rak omformning av indatabitarna, och den som har alfabetet kan vända det i ett pass.
- Inte URL-säker. Alfabetet innehåller
#, %, &, /, ? och ", och alla ändrar betydelse i en URL, så Base91-utdata måste procentkodas innan den läggs i en frågesträng. - Inte HTML-säker. Den innehåller även
<, >, & och ", så en Base91-sträng som läggs i markup måste escapas med HTML-entitetskonverteraren. - Inte fast längd. Utdatalängden beror på bitmönstret, inte bara på antalet byte, så två indata av samma storlek kan skrivas ut med ett tecken skillnad.
Fallgropar som faktiskt bits
- Alfabetet på den här sidan är referensalfabetet. Om ett annat verktyg ger annan utdata för samma indata, jämför dess alfabet innan någon av sidorna antas vara trasig. De 91 tecknen måste förekomma i samma ordning.
- Ett enda felaktigt tecken kan ändra hela slutet. Gränserna mellan grupperna avgörs av värdena som kom före, så en ändring tidigt i strängen förskjuter allt efter den, och slutet avkodas bara med de återstående bitarna i den sista gruppen.
- Udda utdatalängd är normalt. Det betyder inte att strängen är avklippt; den sista gruppen skriver ut ett tecken när dess rest ryms i 7 bitar eller färre.
- Ett publicerat exempel kan innehålla en radbrytning som inte skrevs in. Ett skalkommando som lägger till radslut är den vanliga orsaken till att ett välkänt Base91-värde är ett tecken längre än vad samma text ger här:
echo "Hello, World!" skickar 14 byte till kodaren och skriver ut >OwJh>}AQ;r@@Y?FF, medan de 13 byten i texten ensam skriver ut >OwJh>}AQ;r@@Y?F. Båda är korrekta, för olika byteantal, och antalet under utdatarutan anger vilket av dem man har. - Att avkoda binära data som text fungerar inte. Om de avkodade byten inte är giltig UTF-8 finns ingen rimlig text att visa, och det är vad hexadecimalläget för utdata är till för.
Snabba svar
“Varför visar den här sidan ett värde som skiljer sig med ett tecken från ett annat Base91-verktyg?”
Nästan alltid ett annat alfabet. Den näst vanligaste orsaken är ett verktyg som bara använder 13-bitarsgrenen och aldrig 14-bitars reservlösningen; den varianten är mindre i kod men ger annan utdata än referensalgoritmen som används här.
Det finns också ett exakt fall som kan avgöras genom att räkna byte, och det förklarar det mest citerade exemplet av alla: en avslutande radbrytning. De flesta publicerade vektorer togs fram med ett skalkommando, och skalet lägger till radslutet som avslutar raden. De 13 byten i Hello, World! skrivs ut som 16 tecken här, medan de 14 byten i Hello, World! följda av en radbrytning skrivs ut som de 17 tecknen >OwJh>}AQ;r@@Y?FF. Klistra in något av värdena i Avkoda: sidan anger byteantalet, så de två tolkningarna kan skiljas åt i stället för att diskuteras. Knappen Exempel läser in det av de två som hör till den läsare som används, och den följer växlaren Koda / Avkoda och väljaren Indata är / Utdata som: textläsaren får värdet med 16 tecken, hexadecimalläsaren får det med 17 tecken med dess avslutande byte 0A synlig, och kodaren får texten att koda i stället för en Base91-sträng.
“Är Base91 mindre än Base64?”
Ja, med cirka 8 % av den kodade storleken: 13 bitar per 2 tecken mot 6 bitar per tecken. På 92 byte text skriver Base64 ut 124 tecken och Base91 skriver ut 114.
“Kan jag avkoda detta med en Base64-avkodare, eller tvärtom?”
Nej. Alfabeten överlappar i bokstäverna och siffrorna, så en Base64-avkodare godtar en Base91-sträng som "giltiga" tecken och producerar tyst skräp. De är eniga om ingenting annat än kodningens form.
“Slutar utdata med utfyllnad som Base64?”
Nej. Base91 har inget utfyllnadstecken alls: de bitar som blir över i slutet skrivs ut som den sista gruppen, så ingenting behöver läggas till eller tas bort.
“Hur vet jag att resultatet på den här sidan är rätt?”
Tryck på Självtest 0 till 64 byte. Det kodar och avkodar 130 bytemönster som täcker varje längd där uppdelningen 13/14 bitar ändras, och jämför byten som kommer tillbaka med de byte som skickades in. Vektorerna på knappen Exempel korskontrolleras dessutom mot en andra implementering som skrevs för webbplatsens testverktyg.
Standarder och källhänvisningar
Den här sidan implementerar algoritmen i referensimplementeringen basE91 (version 0.6.0) av Joachim Henke, distribuerad under BSD 3-klausullicensen, med alfabetet som skrivs ut ovan. Avkodningen accepterar och ignorerar blanksteg, precis som referensverktyget gör.
Sidans text skrevs för den här webbplatsen; algoritmen kopierades inte från någonstans. Exempelvärdena för knappen Exempel är det ena exempel som medföljer referenspaketet (markerat "referensexempel") plus värden från en andra, oberoende implementering som finns i webbplatsens testverktyg (markerade "korskontroll").
