Zahlen variabler Länge

Anleitung

Implementiere die Kodierung und Dekodierung von Variable-Length-Quantity-Werten.

Das Ziel dieser Übung ist es, die VLQ-Kodierung und -Dekodierung zu implementieren.

Kurz gesagt: Das Ziel dieser Kodierung ist es, Ganzzahlwerte so zu kodieren, dass Bytes gespart werden. Nur die ersten 7 Bits jedes Bytes sind signifikant (rechtsbündig; ähnlich wie bei einem ASCII-Byte). Wenn du also einen 32-Bit-Wert hast, musst du ihn in eine Reihe von 7-Bit-Bytes zerlegen. Natürlich hängt die Anzahl der Bytes von deiner Ganzzahl ab. Um anzuzeigen, welches Byte das letzte der Reihe ist, lässt du Bit Nr. 7 ungesetzt. In allen vorhergehenden Bytes setzt du Bit Nr. 7.

Eine Ganzzahl zwischen 0-127 lässt sich also als ein einzelnes Byte darstellen. Obwohl VLQ mit Zahlen beliebiger Größe umgehen kann, beschränken wir uns in dieser Übung auf Zahlen, die in eine vorzeichenlose 32-Bit-Ganzzahl passen. Hier sind Beispiele für Ganzzahlen als 32-Bit-Werte und die Variable-Length-Quantity-Kodierungen, in die sie übersetzt werden:

 NUMBER        VARIABLE QUANTITY
00000000              00
00000040              40
0000007F              7F
00000080             81 00
00002000             C0 00
00003FFF             FF 7F
00004000           81 80 00
00100000           C0 80 00
001FFFFF           FF FF 7F
00200000          81 80 80 00
08000000          C0 80 80 00
0FFFFFFF          FF FF FF 7F

---

Quelle

Ein armer Splice-Entwickler, der MIDI-Kodierung/-Dekodierung implementieren musste.