Kodierung von Ganzzahlen variabler Länge

Die Speicherung von Ganzzahlen kann, je nach Datentypgröße viel Platz auf dem Datenträger oder im Speicher in Anspruch nehmen. Werden aber hauptsächlich kleine Werte erwartet, zum Beispiel bei Deltaeinträgen, ist der Großteil des Wertes nicht belegt. Hier springt diese Art der Kodierung ein und versucht die Werte soweit es geht zu kürzen.

Beispiel (Quellcode): vlq.cpp
Download (Quellcode): vlq.zip

Beschreibung

Die Ganzzahl wird in Teile (meist) gleicher Größe aufgeteilt. Alle oberen Teile die keine Bits gesetzt haben werden nicht in die Ausgabe geschrieben. Alle Teile, bis auf den Letzten, bekommen einen Marker, dass der nachfolgende Teil nicht das Ende darstellt. Häufig werden die Zahlen in 7-Bit Teile gebrochen und mit übrigen Bit des Ausgabebytes markiert.

Es gibt hier allerdings viele Varianten, die häufigsten Unterscheidungen sind:

• Richtung
  • höherwertiger Teil zuerst
  • niederwertiger Teil zuerst
• Position des Markers im Ausgabebyte
• Vorzeichenbehandlung
  • im ersten Teil gespeichert
  • absoluter Wert ein Bit nach links geschoben, letztes Bit definiert Vorzeichen
• Synchronisationsfähigkeit
  • keine
  • erstes Byte unterscheidet sich durch extra Bit von den folgenden des Wertes
  • erstes Byte enthält Länge der Sequenz

Durch den Beispielcode

Der Beispielcode, enthält eine Klasse (C++), die natürliche Zahlen (vorzeichenloser Integer) kodieren und dekodieren kann:

• der Konstruktor

  CVariableLengthInteger();
  CVariableLengthInteger(unsigned int nInteger);

  14
  15
  

  Die Klasse kann ohne Angabe eines Wertes konstruiert werden, intern ist dieser dann Null.

• Kodierungsfunktion

  size_t Encode(uint8_t* pBuffer, size_t nSize);

  29
  

  Zeiger auf den Ausgabepuffer und dessen Größe. Rückgabewert ist die Ausgabelänge des Wertes in der Klasse.

• Dekodierungsfunktion

  size_t Decode(const uint8_t* pBuffer, size_t nSize);

  48
  

  Zeiger auf den Eingabepuffer und dessen Größe. Rückgabewert ist die Eingabelänge des Wertes. Der Wert selbst wird hiernach in der Klasse gehalten.

Codeanmerkungen

1. Die Aufrufparameter des Programms werden als Eingabewerte kodiert und ausgegeben:

   for(int n=1; n<argc; n++)
   {
      CVariableLengthInteger vli(atoi(argv[n]));
      nBufferInput += vli.Encode(&buffer[nBufferInput], nBufferSize-nBufferInput);
   }

   77
   78
   79
   80
   81
   

   Der Übersichtlichkeit halber ist die Schleife auf mehrere Zeilen aufgespalten. Sie soll zeigen, dass die Eingabewerte in den Ausgabepuffer geschrieben werden wobei sich die Puffergröße dann verringert.

   So ergibt

   ./vlq 123213 21 221 130
   

   die Ausgabe

   Variable length integer test...
   
   Encoded byte stream:
    cd c2 07 15 dd 01 82 01
   
   Decoded values:
    1. 123213
    2. 21
    3. 221
    4. 130