Base91-Kodierung / -Dekodierung

Base91 ist eine Art, beliebige Bytes nur mit druckbaren ASCII-Zeichen zu schreiben, also dieselbe Aufgabe wie Base64, nur dass in jedes Zeichen mehr Bits passen. Statt die Eingabe in 6-Bit-Gruppen zu zerschneiden und pro Gruppe ein Zeichen zu drucken, sammelt es Bits, bis mindestens 13 vorhanden sind, und druckt dann zwei Zeichen, die zusammen den Wert dieser 13 (oder 14) Bits benennen.

Zwei Zeichen aus einem Alphabet von 91 können 91 × 91 = 8281 verschiedene Werte benennen, und 2¹³ = 8192; zwei Zeichen haben also immer Platz für 13 Bit — mit 89 Werten Reserve. Das ist der ganze Trick: 13 Bit pro 2 Zeichen sind 6,5 Bit pro Zeichen, gegenüber 6 bei Base64, und das bringt etwa 23% Mehraufwand statt 33%.

91 × 91 = 8281 Werte können durch ein Zeichenpaar benannt werden; das ist mehr als 2¹³ = 8192, aber weniger als 2¹⁴ = 16384. Ein Zeichenpaar kann also immer 13 Bit tragen und manchmal 14. Der Kodierer versucht zuerst 13 Bit: Ist der 13-Bit-Wert größer als 88, druckt er diesen Wert als zwei Zeichen; andernfalls nimmt er ein 14. Bit hinzu und druckt stattdessen den resultierenden 14-Bit-Wert.

Die Grenze bei 88 ist nicht willkürlich. Der größte Wert, den zwei Zeichen benennen können, ist 90 + 91 × 90 = 8280, und 8192 + 89 = 8281 liegt schon darüber. Eine 14-Bit-Gruppe kann also nie ein unteres 13-Bit-Fenster von 89 oder mehr haben, was bedeutet, dass der Dekodierer die beiden Fälle allein am Wert erkennt:

Was der Dekodierer sieht	Verbrauchte Bits	Warum
Wert & 8191 ist 89 bis 8191	13 Bit	Werte ab 89 können nur aus dem 13-Bit-Zweig stammen, denn eine 14-Bit-Gruppe mit einem so hohen unteren 13-Bit-Fenster müsste mindestens 8281 sein — was kein Zeichenpaar benennen kann.
Wert & 8191 ist 0 bis 88	14 Bit	Der Kodierer greift nur dann auf 14 Bit zurück, wenn die 13-Bit-Lesart 88 oder weniger war; dieser Zweig ist der Rückfall und nichts anderes.

Was am Ende übrig bleibt — 1 bis 13 Bit — wird als ein Zeichen gedruckt, plus ein zweites Zeichen, wenn der Rest wirklich mehr als 7 Bit brauchte. Deshalb wächst die kodierte Länge in Schritten von zwei Zeichen und endet manchmal auf eine ungerade Anzahl.

Druckbares ASCII umfasst 94 Zeichen, von ! (0x21) bis ~ (0x7E). Base91 verwendet 91 davon, und die drei, die es weglässt, sind der Bindestrich -, das Apostroph ' und der Backslash \. Buchstaben, Ziffern und fast alle Satzzeichen stehen genau einmal im Alphabet, in der Reihenfolge der Tabelle oben; das 92. bis 94. druckbare Zeichen ist schlicht nicht adressierbar.

Weil das Alphabet eine feste Reihenfolge hat, ist das Zeichen für einen Wert ein Nachschlagen und keine Formel. Zwei Implementierungen, die das Alphabet unterschiedlich ordnen, heißen beide „Base91“ und können die Ausgabe der anderen nicht lesen — das ist die häufigste Ursache verwirrender Ergebnisse. Diese Seite zeigt ihr Alphabet an, damit sich die Ausgabe immer darauf zurückführen lässt.

Kodierung	Bit pro Zeichen	Größe gegenüber der Eingabe	Hinweise
Base16 (Hex)	4	200%	Zwei Zeichen pro Byte, völlig lesbar, kein Alphabet nachzuschlagen.
Base32	5	160%	Groß-/Kleinschreibungsunabhängig und sicher beim Diktieren, aber die verschwenderischste der Gruppe.
Base58	~5,86	~137%	Für Adressen gewählt, nicht für Dichte: Es vermeidet leicht verwechselbare Zeichen.
Base64	6	133%	überall der Standard: 4 Zeichen pro 3 Byte, wobei die 6 ungenutzten Bit des letzten Zeichens verschwendet sind.
Ascii85 / Base85	6,4	125%	5 Zeichen pro 4 Byte, keine Nachschlagetabelle nötig, aber es teilt durch 85 — siehe Ascii85-Konverter.
Base91	~6,5	~123%	Die dichteste dieser Kodierungen: 13 Bit pro 2 Zeichen, um den Preis gelegentlicher 14-Bit-Gruppen.

Die Prozentwerte sind die asymptotischen Kosten jeder Kodierung, gerundet; die gemessenen Zeichenzahlen für eine echte 92-Byte-Eingabe stehen in der Tabelle weiter oben auf dieser Seite. Base91 liegt nahe an dem Besten, was eine Kodierung mit druckbarem ASCII leisten kann: 7 Bit pro Zeichen würden 128 verschiedene Zeichen erfordern, die der druckbare Bereich nicht bietet.

• Kein Standard. Es gibt keinen RFC. Die Referenzimplementierung ist basE91 0.6.0 von Joachim Henke, veröffentlicht unter der BSD-3-Clause-Lizenz; „Base91“ wird auch für Alphabete verwendet, die nicht dieses sind.
• Keine Verschlüsselung. Jedes Zeichen ist eine direkte Umformung der Eingabebits, und wer das Alphabet hat, kehrt sie in einem Durchgang um.
• Nicht URL-sicher. Das Alphabet enthält #, %, &, /, ? und ", die alle in einer URL ihre Bedeutung ändern. Base91-Ausgaben müssen deshalb prozentkodiert werden, bevor sie in eine Abfragezeichenkette kommen.
• Nicht HTML-sicher. Es enthält außerdem <, >, & und ", daher muss eine Base91-Zeichenkette, die in Markup steht, mit dem HTML-Entity-Konverter maskiert werden.
• Keine feste Länge. Die Ausgabelänge hängt vom Bitmuster ab, nicht nur von der Byteanzahl; zwei Eingaben gleicher Größe können deshalb um ein Zeichen abweichen.

• Das Alphabet dieser Seite ist das Referenzalphabet. Wenn ein anderes Werkzeug für dieselbe Eingabe eine andere Ausgabe erzeugt, vergleichen Sie zuerst dessen Alphabet, bevor Sie eine Seite für fehlerhaft halten. Die 91 Zeichen müssen in derselben Reihenfolge stehen.
• Ein einziges falsches Zeichen kann den ganzen Rest ändern. Die Gruppengrenzen werden durch die vorherigen Werte bestimmt; eine Änderung früh in der Zeichenkette verschiebt alles danach, und der Rest wird nur mit den übrigen Bits der letzten Gruppe dekodiert.
• Eine ungerade Ausgabelänge ist normal. Sie bedeutet nicht, dass die Zeichenkette abgeschnitten wurde; die letzte Gruppe druckt ein Zeichen, wenn ihr Restwert in 7 Bit oder weniger passt.
• Ein veröffentlichtes Beispiel kann einen Zeilenumbruch enthalten, den Sie nicht getippt haben. Ein Shell-Befehl, der einen Zeilenumbruch anhängt, ist der übliche Grund, warum ein bekannter Base91-Wert um ein Zeichen länger ist als der hier erzeugte: echo "Hello, World!" übergibt dem Kodierer 14 Byte und druckt >OwJh>}AQ;r@@Y?FF, während die 13 Byte des reinen Textes >OwJh>}AQ;r@@Y?F drucken. Beides ist korrekt, für verschiedene Byteanzahlen, und die Anzahl unter dem Ausgabefeld zeigt, welche Zeichenkette Sie vor sich haben.
• Binärdaten als Text zu dekodieren funktioniert nicht. Sind die dekodierten Bytes kein gültiges UTF-8, gibt es keinen sinnvollen Text zu zeigen; dafür ist der hexadezimale Ausgabemodus da.

„Warum zeigt diese Seite einen Wert, der sich um ein Zeichen von dem eines anderen Base91-Werkzeugs unterscheidet?“

Fast immer ein anderes Alphabet. Die zweithäufigste Ursache ist ein Werkzeug, das nur den 13-Bit-Zweig nutzt und nie den 14-Bit-Rückfall; diese Variante ist im Code kleiner, erzeugt aber eine andere Ausgabe als der hier verwendete Referenzalgorithmus.

Es gibt auch einen genauen Fall, der sich durch Zählen der Bytes klären lässt, und er erklärt das am häufigsten zitierte Beispiel überhaupt: ein abschließendes Zeilenende. Die meisten veröffentlichten Vektoren wurden von einem Shell-Befehl erzeugt, und die Shell fügt den Zeilenumbruch hinzu, der die Zeile abschließt. Die 13 Bytes von Hello, World! ergeben hier 16 Zeichen, während die 14 Bytes von Hello, World! gefolgt von einem Zeilenumbruch das 17-stellige >OwJh>}AQ;r@@Y?FF ergeben. Fügen Sie einen der beiden Werte in Dekodieren ein: Diese Seite meldet die Byteanzahl, sodass sich die beiden Lesarten unterscheiden lassen, statt darüber zu streiten. Die Schaltfläche Beispiel lädt denjenigen der beiden, der zu Ihrer Lesart gehört; sie folgt dem Schalter Kodieren/Dekodieren und der Auswahl Eingabe ist / Ausgabe als: Die Textlesart erhält den 16-stelligen Wert, die Hex-Lesart den 17-stelligen mit seinem abschließenden 0A-Byte gut sichtbar, und der Kodierer erhält den zu kodierenden Text statt einer Base91-Zeichenkette.

„Ist Base91 kleiner als Base64?“

Ja, um etwa 8% der kodierten Größe: 13 Bit pro 2 Zeichen gegenüber 6 Bit pro Zeichen. Bei 92 Byte Text druckt Base64 124 Zeichen, Base91 druckt 114.

„Kann ich das mit einem Base64-Dekodierer dekodieren oder umgekehrt?“

Nein. Die Alphabete überlappen sich bei Buchstaben und Ziffern, daher akzeptiert ein Base64-Dekodierer eine Base91-Zeichenkette als „gültige“ Zeichen und liefert stillschweigend Unsinn. Beide stimmen nur in der Form des Schemas überein.

„Endet die Ausgabe wie bei Base64 mit einer Auffüllung?“

Nein. Base91 hat überhaupt kein Auffüllzeichen: Die übrig gebliebenen Bits am Ende werden als letzte Gruppe gedruckt, daher muss nichts hinzugefügt oder entfernt werden.

„Woher weiß ich, dass das Ergebnis dieser Seite stimmt?“

Drücken Sie Selbsttest 0 bis 64 Byte. Er kodiert und dekodiert 130 Bytemuster, die jede Länge abdecken, bei der sich die Aufteilung in 13 und 14 Bit ändert, und vergleicht die zurückkommenden Bytes mit den hineingegebenen. Die Vektoren der Schaltfläche Beispiel werden zusätzlich gegen eine zweite Implementierung gegengeprüft, die für das Testwerkzeug dieser Website geschrieben wurde.

Diese Seite implementiert den Algorithmus der Referenzimplementierung basE91 (Version 0.6.0) von Joachim Henke, verteilt unter der BSD-3-Clause-Lizenz, mit dem oben gedruckten Alphabet. Das Dekodieren akzeptiert und ignoriert Leerzeichen, wie das Referenzwerkzeug auch.

Der Seitentext wurde für diese Website geschrieben; der Algorithmus wurde nirgends kopiert. Die Werte der Schaltfläche Beispiel sind das eine Beispiel, das dem Referenzpaket beiliegt (als „Referenzbeispiel“ gekennzeichnet), sowie Werte, die von einer zweiten, unabhängigen Implementierung erzeugt wurden, die im Testwerkzeug dieser Website liegt (als „Gegenprüfung“ gekennzeichnet).