Menge variabler Länge – Wikipedia

before-content-x4

EIN Menge variabler Länge ((VLQ) ist ein universeller Code, der eine beliebige Anzahl von binären Oktetten (8-Bit-Bytes) verwendet, um eine beliebig große Ganzzahl darzustellen. Ein VLQ ist im Wesentlichen eine Basis-128-Darstellung einer vorzeichenlosen Ganzzahl mit dem Zusatz des achten Bits, um die Fortsetzung von Bytes zu markieren. VLQ ist mit LEB128 identisch, außer in Endianness. Siehe das folgende Beispiel.

Anwendungen und Geschichte[edit]

Die Base-128-Komprimierung ist unter vielen Namen bekannt – VB (Variable Byte), VByte, Varint, VInt, EncInt usw.[1]

EIN Menge variabler Länge ((VLQ) wurde für die Verwendung im Standard-MIDI-Dateiformat definiert[2] um zusätzlichen Speicherplatz für ein System mit eingeschränkten Ressourcen zu sparen, und wird auch im späteren XMF (Extensible Music Format) verwendet.

Basis-128 wird auch in der ASN.1-BER-Codierung verwendet, um Tag-Nummern und Objekt-IDs zu codieren.[3] Es wird auch in der WAP-Umgebung verwendet, in der es aufgerufen wird Ganzzahl ohne Vorzeichen mit variabler Länge oder uintvar. Das DWARF-Debugging-Format[4] definiert eine Variante namens LEB128 (oder ULEB128 für vorzeichenlose Zahlen), wobei die niedrigstwertige Gruppe von 7 Bits im ersten Byte und die höchstwertigen Bits im letzten Byte codiert sind (so effektiv ist es das Little-Endian-Analogon eines VLQ). Google-Protokollpuffer verwenden ein ähnliches Format, um ganzzahlige Werte kompakt darzustellen.[5] ebenso wie das Oracle Portable Object Format (POF)[6] und das Microsoft .NET Framework “7-Bit codiert int” in der BinaryReader und BinaryWriter Klassen.[7]

Es wird auch häufig in Webbrowsern für die Quellzuordnung verwendet, die viele Zuordnungen von ganzzahligen Zeilen- und Spaltennummern enthält, um die Größe der Zuordnung auf ein Minimum zu beschränken.[8]

Ganzzahlen mit variabler Breite in LLVM verwenden ein ähnliches Prinzip. Die Codierungsblöcke sind Little-Endian-Blöcke und müssen nicht 8 Bit groß sein. Die LLVM-Dokumentation beschreibt ein Feld, das einen 4-Bit-Block verwendet, wobei jeder Block aus 1-Bit-Fortsetzung und 3-Bit-Nutzdaten besteht.[9]

Allgemeine Struktur[edit]

Die Codierung setzt ein Oktett (ein Acht-Bit-Byte) voraus, wobei das höchstwertige Bit (MSB), auch allgemein als Vorzeichenbit bekannt, reserviert ist, um anzuzeigen, ob ein anderes VLQ-Oktett folgt.

VLQ Octet
7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20
EIN B.n

Wenn A 0 ist, ist dies das letzte VLQ-Oktett der Ganzzahl. Wenn A 1 ist, folgt ein weiteres VLQ-Oktett.

B ist eine 7-Bit-Zahl [0x00, 0x7F] und n ist die Position des VLQ-Oktetts, an der B.0 ist am wenigsten signifikant. Die VLQ-Oktette werden zuerst in einem Stream am wichtigsten angeordnet.

Varianten[edit]

Die allgemeine VLQ-Codierung ist einfach, wird jedoch in der Grundform nur für vorzeichenlose Ganzzahlen (nicht negativ, positiv oder null) definiert und ist etwas redundant, da das Voranstellen von 0x80-Oktetten dem Auffüllen mit Null entspricht. Es gibt verschiedene vorzeichenbehaftete Zahlendarstellungen, um negative Zahlen zu verarbeiten, und Techniken, um die Redundanz zu beseitigen.

Gruppen-Varint-Codierung[edit]

Google entwickelte die Group Varint Encoding (GVE), nachdem festgestellt wurde, dass bei der herkömmlichen VLQ-Codierung während der Dekomprimierung viele CPU-Verzweigungen auftreten. GVE verwendet ein einzelnes Byte als Header für 4 uint32-Werte variabler Länge. Das Header-Byte hat 4 2-Bit-Zahlen, die die Speicherlänge jeder der folgenden 4 uint32s darstellen. Ein solches Layout macht das Überprüfen und Entfernen von VLQ-Fortsetzungsbits überflüssig. Datenbytes können direkt an ihr Ziel kopiert werden. Dieses Layout reduziert die CPU-Verzweigungen und macht GVE auf modernen Pipeline-CPUs schneller als VLQ.[10]

PrefixVarint ist ein ähnliches Design, jedoch mit einem Maximum von uint64. Es soll “mehrfach unabhängig voneinander erfunden worden sein”.[11] Es ist möglich, in eine verkettete Version mit unendlich vielen Fortsetzungen geändert zu werden.

Signierte Nummern[edit]

Zeichenbit[edit]

Negative Zahlen können mit einem Vorzeichenbit behandelt werden, das nur im ersten Oktett vorhanden sein muss.

Im Datenformat für unwirkliche Pakete, das von der Unreal Engine verwendet wird, ein Mengenschema mit variabler Länge, das als kompakte Indizes bezeichnet wird[12] wird eingesetzt. Der einzige Unterschied bei dieser Codierung besteht darin, dass für das erste VLQ das sechste Bit reserviert ist, um anzuzeigen, ob die codierte Ganzzahl positiv oder negativ ist. Jedes aufeinanderfolgende VLQ-Oktett folgt der allgemeinen Struktur.

Unreal Signed VLQ
Erstes VLQ-Oktett Andere VLQ-Oktette
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 27 26 25 24 23 22 21 20
EIN B. C.0 EIN C.n (n> 0)

Wenn A 0 ist, ist dies das letzte VLQ-Oktett der Ganzzahl. Wenn A 1 ist, folgt ein weiteres VLQ-Oktett.

Wenn B 0 ist, repräsentiert der VLQ eine positive ganze Zahl. Wenn B 1 ist, repräsentiert der VLQ eine negative Zahl.

C ist der zu codierende Zahlenblock und n ist die Position des VLQ-Oktetts, an der C.0 ist am wenigsten signifikant. Die VLQ-Oktette werden zuerst in einem Stream am wichtigsten angeordnet.[dubious ]

Zick-Zack-Codierung[edit]

Eine alternative Möglichkeit, negative Zahlen zu codieren, besteht darin, das niedrigstwertige Bit für das Vorzeichen zu verwenden. Dies geschieht insbesondere für Google-Protokollpuffer und wird als bezeichnet Zick-Zack-Codierung für vorzeichenbehaftete ganze Zahlen.[13] Man kann die Zahlen so codieren, dass die codierte 0 0, 1 bis -1, 10 bis 1, 11 bis -2, 100 bis 2 usw.: Das Aufzählen wechselt zwischen nicht negativ (beginnend bei 0) und negativ (seit jedem Schritt) ändert das niedrigstwertige Bit (daher das Vorzeichen), woher der Name “Zick-Zack-Codierung” stammt. Konkret transformieren Sie die Ganzzahl als (n << 1) ^ (n >> k - 1) für fest k-bit ganze Zahlen.

Zwei ergänzen[edit]

LEB128 verwendet das Zweierkomplement, um vorzeichenbehaftete Zahlen darzustellen. In diesem Darstellungsschema codieren n Bits einen Bereich von -2n zu 2n-1, und alle negativen Zahlen beginnen mit einer 1 im höchstwertigen Bit. In Signed LEB128 ist der Eingang vorzeichenerweitert, sodass seine Länge ein Vielfaches von 7 Bits beträgt. Von dort geht die Codierung wie gewohnt weiter.[14]

In LEB128 ist der Strom zuerst am wenigsten signifikant angeordnet.[14]

Redundanz entfernen[edit]

Mit der oben beschriebenen VLQ-Codierung kann jede Zahl, die mit N Oktetten codiert werden kann, auch mit mehr als N Oktetten codiert werden, indem einfach zusätzliche 0x80-Oktette als Null-Padding vorangestellt werden. Beispielsweise kann die Dezimalzahl 358 als 2-Oktett-VLQ 0x8266 oder die Zahl 0358 als 3-Oktett-VLQ 0x808266 oder 00358 als 4-Oktett-VLQ 0x80808266 usw. codiert werden.

Das in Git verwendete VLQ-Format[15] Entfernt diese vorangestellte Redundanz und erweitert den darstellbaren Bereich kürzerer VLQs durch Hinzufügen eines Versatzes zu VLQs von 2 oder mehr Oktetten, so dass der niedrigstmögliche Wert für einen solchen (N + 1) -Octet-VLQ genau eins mehr als das Maximum wird möglicher Wert für einen N-Oktett-VLQ. Da ein 1-Oktett-VLQ einen Maximalwert von 127 speichern kann, wird dem minimalen 2-Oktett-VLQ (0x8000) der Wert 128 anstelle von 0 zugewiesen. Umgekehrt wird dem Maximalwert eines solchen 2-Oktett-VLQ (0xff7f) zugewiesen. ist 16511 anstelle von nur 16383. In ähnlicher Weise hat der minimale 3-Oktett-VLQ (0x808000) einen Wert von 16512 anstelle von Null, was bedeutet, dass der maximale 3-Oktett-VLQ (0xffff7f) 2113663 anstelle von nur 2097151 ist.

Auf diese Weise gibt es eine und nur eine Codierung für jede Ganzzahl, was dies zu einer bijektiven Basis-128-Nummerierung macht.

Beispiele[edit]

Diagramm, das zeigt, wie 106.903 von einer Dezimal- in eine Uintvar-Darstellung konvertiert werden

Hier ist ein ausgearbeitetes Beispiel für die Dezimalzahl 137:

  • Stellen Sie den Wert in binärer Notation dar (z. B. 137 als 10001001).
  • Teilen Sie es in Gruppen von 7 Bits auf, beginnend mit dem niedrigstwertigen Bit (z. B. 137 als 0000001 0001001). Dies entspricht der Darstellung der Zahl in der Basis 128.
  • Nehmen Sie die niedrigsten 7 Bits und Sie erhalten das niedrigstwertige Byte (0000 1001). Dieses Byte kommt zuletzt.
  • Setzen Sie für alle anderen Gruppen von 7 Bits (im Beispiel ist dies 000 0001) das MSB auf 1 (was ergibt 1000 0001 in unserem Beispiel). So wird 137 1000 0001 0000 1001, wobei die fett gedruckten Bits etwas sind, das wir hinzugefügt haben. Diese hinzugefügten Bits geben an, ob ein weiteres Byte folgen soll oder nicht. Per Definition hat das allerletzte Byte einer Ganzzahl variabler Länge 0 als MSB.

Eine andere Möglichkeit, dies zu betrachten, besteht darin, den Wert in Basis-128 darzustellen und dann das MSB aller bis auf die letzte Basis-128-Ziffer auf 1 zu setzen.

Die Standard-MIDI-Dateiformatspezifikation enthält weitere Beispiele:[2][16]

Ganzzahl (dezimal) Ganzzahl (hexadezimal) Ganzzahl (binär) Menge variabler Länge (hexadezimal) Menge variabler Länge (binär)
0 0x00000000
00000000 00000000 00000000 00000000
0x00
                           00000000
127 0x0000007F
00000000 00000000 00000000 01111111
0x7F
                           01111111
128 0x00000080
00000000 00000000 00000000 10000000
0x81 0x00
                  10000001 00000000
8192 0x00002000
00000000 00000000 00100000 00000000
0xC0 0x00
                  11000000 00000000
16383 0x00003FFF
00000000 00000000 00111111 11111111
0xFF 0x7F
                  11111111 01111111
16384 0x00004000
00000000 00000000 01000000 00000000
0x81 0x80 0x00
         10000001 10000000 00000000
2097151 0x001FFFFF
00000000 00011111 11111111 11111111
0xFF 0xFF 0x7F
         11111111 11111111 01111111
2097152 0x00200000
00000000 00100000 00000000 00000000
0x81 0x80 0x80 0x00
10000001 10000000 10000000 00000000
134217728 0x08000000
00001000 00000000 00000000 00000000
0xC0 0x80 0x80 0x00
11000000 10000000 10000000 00000000
268435455 0x0FFFFFFF
00001111 11111111 11111111 11111111
0xFF 0xFF 0xFF 0x7F
11111111 11111111 11111111 01111111

Verweise[edit]

Externe Links[edit]

after-content-x4