Variabel längd kvantitet

En kvantitet med variabel längd ( VLQ ) är en universell kod som använder ett godtyckligt antal binära oktetter (åtta- bitars byte ) för att representera ett godtyckligt stort heltal . En VLQ är i huvudsak en bas-128-representation av ett heltal utan tecken med tillägg av den åttonde biten för att markera fortsättning av bytes. VLQ är identisk med LEB128 förutom i endianness . Se exemplet nedan.

Applikationer och historik

Base-128-komprimering är känd under många namn - VB (Variable Byte), VByte , Varint , VInt , EncInt etc.

En kvantitet med variabel längd ( VLQ ) definierades för användning i standard MIDI-filformat för att spara extra utrymme för ett resursbegränsat system, och används även i det senare Extensible Music Format (XMF) .

Base-128 används också i ASN.1 BER-kodning för att koda taggnummer och objektidentifierare . Det används också i WAP- miljön, där det kallas osignerat heltal med variabel längd eller uintvar . DWARF - felsökningsformatet definierar en variant som kallas LEB128 (eller ULEB128 för osignerade nummer), där den minst signifikanta gruppen på 7 bitar är kodad i den första byten, och de mest signifikanta bitarna finns i den sista byten (så effektivt är det den lilla- endian analog av en VLQ). Google Protocol Buffers använder ett liknande format för att ha en kompakt representation av heltalsvärden, liksom Oracle Portable Object Format (POF) och Microsoft .NET Framework "7-bit encoded int" i klasserna BinaryReader och BinaryWriter .

Den används också flitigt i webbläsare för källmappning – som innehåller många heltalslinje- och kolumnnummermappningar – för att hålla kartans storlek till ett minimum.

Heltal med variabel bredd i LLVM använder en liknande princip. Kodningsbitarna är små och behöver inte vara 8 bitar stora. LLVM-dokumentationen beskriver ett fält som använder 4-bitars chunk, där varje chunk består av 1 bit fortsättning och 3 bitars nyttolast.

Allmän struktur

Kodningen antar en oktett (en 8-bitars byte) där den mest signifikanta biten (MSB), även känd som teckenbiten, är reserverad för att indikera om en annan VLQ-oktett följer.

VLQ oktett
7	6	5	4	3	2	1	0
2 ⁷	2 ⁶	2 ⁵	2 ⁴	2 ³	2 ²	2 ¹	2⁰
A	B _n

Om A är 0, så är detta den sista VLQ-oktetten av heltal. Om A är 1, följer ytterligare en VLQ-oktett.

₀ B är ett 7-bitars tal [0x00, 0x7F], och n är positionen för VLQ-oktetten där B är den minst signifikanta . VLQ-oktetterna är mest betydande först i en ström.

Varianter

Den allmänna VLQ-kodningen är enkel, men definieras i grundläggande form endast för heltal utan tecken (icke-negativa, positiva eller noll), och är något överflödig, eftersom förekommande 0x80 oktetter motsvarar noll utfyllnad. Det finns olika signerade nummerrepresentationer för att hantera negativa tal, och tekniker för att ta bort redundansen.

Gruppvarintkodning

Google utvecklade Group Varit Encoding (GVE) efter att ha observerat att traditionell VLQ-kodning ådrar sig många CPU-grenar under dekompression. GVE använder en enda byte som ett huvud för 4 uint32-värden med variabel längd. Rubrikbyten har 4 2-bitars nummer som representerar lagringslängden för var och en av följande 4 uint32s. En sådan layout eliminerar behovet av att kontrollera och ta bort VLQ-fortsättningsbitar. Databytes kan kopieras direkt till sin destination. Denna layout minskar CPU-grenar , vilket gör GVE snabbare än VLQ på moderna pipeline-processorer.

PrefixVarint är en liknande design men med ett maximalt uint64. Det sägs ha "uppfunnits flera gånger oberoende". Det går att ändra till en kedjad version med oändligt många fortsättningar.

Signerade nummer

Sign bit

Negativa tal kan hanteras med en teckenbit , som bara behöver finnas i den första oktetten.

I dataformatet för Unreal Packages som används av Unreal Engine , används ett kvantitetsschema med variabel längd som kallas Compact Index. Den enda skillnaden i denna kodning är att den första VLQ-oktetten har den sjätte biten reserverad för att indikera om det kodade heltal är positivt eller negativt. Varje på varandra följande VLQ-oktett följer den allmänna strukturen.

Unreal Signerad VLQ
Första VLQ-oktetten								Andra VLQ-oktetter
7	6	5	4	3	2	1	0	7	6	5	4	3	2	1	0
2 ⁷	2 ⁶	2 ⁵	2 ⁴	2 ³	2 ²	2 ¹	2⁰	2 ⁷	2 ⁶	2 ⁵	2 ⁴	2 ³	2 ²	2 ¹	2⁰
A	B	C₀						A	C _n ( n > 0)

Om A är 0, så är detta den sista VLQ-oktetten av heltal. Om A är 1, följer ytterligare en VLQ-oktett.

Om B är 0, representerar VLQ ett positivt heltal. Om B är 1, representerar VLQ ett negativt tal.

₀ C är nummerbiten som kodas, och n är positionen för VLQ-oktetten där C är den minst signifikanta . VLQ-oktetterna arrangeras minst signifikant först i en ström.

Sicksack-kodning

Ett alternativt sätt att koda negativa tal är att använda den minst signifikanta biten för tecken. Detta görs särskilt för Google Protocol Buffers och är känt som en sicksackkodning för signerade heltal . Man kan koda siffrorna så att kodad 0 motsvarar 0, 1 till −1, 10 till 1, 11 till −2, 100 till 2, etc.: uppräkningen växlar mellan icke-negativ (börjar på 0) och negativ (sedan varje steg ändrar den minst signifikanta biten, därav tecknet), varav namnet "sicksackkodning". Konkret, transformera heltal som (n << 1) ^ (n >> k - 1) för fasta k -bitars heltal.

Tvås komplement

LEB128 använder tvås komplement för att representera tecken med tecken. I detta representationsschema n bitar ett intervall från −2 ⁿ till 2 ⁿ − 1, och alla negativa tal börjar med en 1 i den mest signifikanta biten. I Signed LEB128 är ingången teckenförlängd så att dess längd är en multipel av 7 bitar. Därifrån fortsätter kodningen som vanligt.

I LEB128 arrangeras strömmen minst signifikant först.

Ta bort redundans

Med VLQ-kodningen som beskrivits ovan kan alla tal som kan kodas med N oktetter också kodas med fler än N oktetter helt enkelt genom att lägga till ytterligare 0x80 oktetter som nollutfyllnad. Till exempel kan decimaltalet 358 kodas som 2-oktett VLQ 0x8266, eller talet 0358 kan kodas som 3-oktett VLQ 0x808266, eller 00358 som 4-oktett VLQ 0x80808266 och så vidare.

VLQ-formatet som används i Git tar dock bort denna förhandsredundans och utökar det representativa området av kortare VLQ:er genom att lägga till en offset till VLQ:er på 2 eller fler oktetter på ett sådant sätt att lägsta möjliga värde för en sådan (N + 1 ) -oktett VLQ blir exakt en mer än det maximalt möjliga värdet för en N -oktett VLQ. I synnerhet, eftersom en 1-oktett VLQ kan lagra ett maximalt värde på 127, tilldelas den minsta 2-oktett VLQ (0x8000) värdet 128 istället för 0. Omvänt, det maximala värdet för en sådan 2-oktett VLQ (0xFF7F) är 16 511 istället för bara 16 383 . På samma sätt har minsta 3-oktett VLQ (0x808000) ett värde på 16 512 istället för noll, vilket betyder att den maximala 3-oktett VLQ (0xFFFF7F) är 2 113 663 istället för bara 2 097 151 .

På detta sätt finns det en och endast en kodning av varje heltal, vilket gör detta till en bas-128 bijektiv numerering .

Exempel

Diagram som visar hur man konverterar 106 903 från decimal- till uintvar-representation

Här är ett utarbetat exempel för decimaltalet 137 :

Representera värdet i binär notation (t.ex. 137 som 10001001)
Dela upp den i grupper om 7 bitar med början från den lägsta signifikanta biten (t.ex. 137 som 0000001 0001001). Detta motsvarar att representera talet i basen 128.
0 Ta de lägsta 7 bitarna, och det ger dig den minst signifikanta byten ( 000 1001). Denna byte kommer sist.
0 För alla andra grupper om 7 bitar (i exemplet är detta 000 0001), sätt MSB till 1 (vilket ger 1 000 0001 i vårt exempel). Därmed blir 137 1 000 0001 000 1001, där bitarna i fet stil är något vi lagt till. Dessa tillagda bitar anger om det finns en annan byte att följa eller inte. Den allra sista byten i ett heltal med variabel längd kommer alltså per definition att ha 0 som MSB .

Ett annat sätt att se på detta är att representera värdet i bas-128 och sedan ställa in MSB för alla utom den sista bas-128-siffran till 1.

Standard MIDI-filformatspecifikationen ger fler exempel:

Heltal (decimal)	Heltal (hexadecimalt)	Heltal (binärt)	Variabel längd kvantitet (hexadecimal)	Variabel längd kvantitet (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
16 383	0x00003FFF	00000000 00000000 00111111 11111111	0xFF 0x7F	11111111 01111111
16 384	0x00004000	00000000 00000000 01000000 00000000	0x81 0x80 0x00	10000001 10000000 00000000
2 097 151	0x001FFFFF	00000000 00011111 11111111 11111111	0xFF 0xFF 0x7F	11111111 11111111 01111111
2 097 152	0x00200000	00000000 00100000 00000000 00000000	0x81 0x80 0x80 0x00	10000001 10000000 10000000 00000000
134 217 728	0x08000000	00001000 00000000 00000000 00000000	0xC0 0x80 0x80 0x00	11000000 10000000 10000000 00000000
268 435 455	0x0FFFFFFF	00001111 11111111 11111111 11111111	0xFF 0xFF 0xFF 0x7F	11111111 11111111 11111111 01111111

externa länkar

MIDI Manufacturers Association (MMA) - Källa för engelskspråkiga MIDI-specifikationer
Association of Musical Electronics Industry (AMEI) -Källa för japanskspråkiga MIDI-specifikationer