Die variable 7-Bit-Kodierung für Integer-Werte

Die variable 7-Bit-Kodierung für Integer-Werte ähnelt der UTF-8-Kodierung. Je nach zu kodierendem Wert werden 1 bis n Byte belegt. Das höchste Bit eines jeden Bytes gibt an, ob zur Abbildung eines Wertes ein weiteres Byte verwendet wurde.

Im Gegensatz zum UTF-8-Verfahren befinden sich die niederwertigsten Bits eines Wertes immer im ersten Byte. Außerdem kann jedes Byte exakt 7 Nutzbits aufnehmen. Die variable 7-Bit-Kodierung ist somit etwas effizienter. Auch ist keine kodierungstechnische Wertbegrenzung vorhanden.

Möglichkeiten sinnvoller Wertebereich binäre Kodierung
27 0 – 127 0xxxxxxx
214 128 – 16383 1xxxxxxx 0xxxxxxx
221 16384 – 2097151 1xxxxxxx 1xxxxxxx 0xxxxxxx
228 2097152 – 2,68·108 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
235 2,68·108 – 3,44·1010 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx

Kodierung negativer Integer-Werte

Mit Hilfe eines Versatzes können negative Werte abgebildet werden. Der Offset kann beliebig gewählt werden. Er muss jedoch beim Kodieren und Dekodieren bekannt sein, da er sich nicht explizit aus dem Kodierungsverfahren ergibt. Ein Versatz eignet sich prinzipiell immer dann, wenn der Wertebereich nicht bei Null beginnt.

Eine andere Möglichkeit negative Werte zu kodieren besteht darin, den Wert vorher in eine vorzeichenlose Zahl umzuwandeln. Die maximale Bitanzahl wird dadurch automatisch festgelegt. Aufgrund des für negative Zahlen immer gesetzten höchstwertigen Bits wird beim Kodieren immer die maximale Anzahl Bytes benötigt. Vorzeichenbehaftete 32-Bit-Werte belegen daher immer 5 Byte.

Einsatzgebiete der variablen 7-Bit-Kodierung

Das variable 7-Bit-Kodierungsverfahren eignet sich insbesondere dann, wenn negative oder Werte größer gleich 228 nur selten auftreten. Ein praktisches Einsatzgebiet ist die Serialisierung bzw. Deserialisierung von Zeichenketten, wenn hierbei als erstes die Länge geschrieben bzw. gelesen wird. Die Länge der Zeichenkette kann mit dem Verfahren effizient kodiert werden, da kleinere Werte wesentlich wahrscheinlicher sind als größere.

Das .NET Framework stellt beispielsweise zwei auf der variablen 7-Bit-Kodierung basierende Funktionen für 32-Bit-Werte bereit. Die Funktion Read7BitEncodedInt gehört zur Klasse System.IO.BinaryReader, die Funktion Write7BitEncodedInt zu System.IO.BinaryWriter. Allerdings sind beide Funktionen geschützt (protected), so dass sie nur durch abgeleitete Klassen genutzt werden können.

Implementierung für 32- und 64-Bit-Integer in C#

Die folgende Bibliothek enthält u.a. die Implementierung der variablen 7-Bit-Kodierung. Ein Modultest belegt die korrekte Funktion der Kodierung und Dekodierung.

Liersch.Utilities.zip herunterladen

Ähnliche Artikel

Schreiben Sie einen Kommentar