LEB128

LEB128 o Little Endian Base 128, és una compressió de còdic de llongitut variable que s'utilisa per a almagasenar número entero arbitrariamente llargues en un número reduït de bytes. S'utilisa en el format d'archiu de depuració DWARF i en la codificació binaria WebAssembly para tots els lliterals sancers.

Format de codificació

El format LEB128 és molt similar al format de cantitat de llongitut variable (VLQ). La principal diferència radica que LEB128 és little-endian, mentres que les cantitats de llongitut variable són big-endian. Abdós permeten almagasenar números menuts en un sol byte, ademés de codificar números de llongitut arbitrària. Existixen dos versions de LEB128: LEB128 sense signe i LEB128 en signe. El decodificador deu saber si el valor codificat és LEB128 sense signe o en signe.

LEB128 sense signe

Per a codificar un número sense signe usant LEB128 sense signe (ULEB128) primer es deu representar el número en binario. Després, es convertix el número a un múltiple de 7 bits per mig d'extensió de zeros(de modo que si el número no és zero, els 7 bits més significatius no siguen tots 0). Dividix el número en grups de 7 bits. Genera un byte codificat per cada grup de 7 bits, des del menys significatiu fins al més significatiu. Cada byte contindrà el grup en els seus 7 bits menys significatius. Establix el bit més significatiu en cada byte, llevat en l'últim. El número zero se sol codificar com un sol byte 0x00. WebAssembly permet codificació alternatives per al zero (0x80 0x00, 0x80 0x80 0x00, ...).

Com a eixemple, aixina es codifica el número sense signe 624485:

MSB ------------------ LSB
10011000011101100101 En binario pur
010011000011101100101 Reblit a un múltiple de 7 bits
0100110 0001110 1100101 Dividit en grups de 7 bits
00100110 10001110 11100101 Se sumen els bits 1 més significatius a tots els grups llevat a l'últim (el més significatiu) per a formar bytes
0x26 0x8I 0xE5 En hexadecimal

→ 0xE5 0x8I 0x26 Fluix d'eixida (LSB a MSB)

Els formats LEB128 sense signe i VLQ (cantitat de llongitut variable) comprimixen qualsevol sancer dau no solament en la mateixa cantitat de bits, sino exactament en els mateixos bits; abdós formats diferixen únicament en la disposició de dits bits.

LEB128 en signe

Un número en signe es representa de forma similar: començant en Una representació $N$ de bits complement a dos, a on $N$ és un múltiple de 7, dividix el número en grups com en la codificació sense signe.

Per eixemple, el número en signe -123456 es codifica com 0xC0 0xBB 0x78:

MSB ------------------ LSB
11110001001000000 Codificació binaria de 123456
000011110001001000000 Com un número de 21 bits
111100001110110111111 Negació de tots els bits (complement a un)
11110000111011100000 Sumant un (complement a dos)
1111000 0111011 1.000.000 Dividir en grups de 7 bits
01111000 10111011 11000000 Sumar els bits 1 més significatius a tots els grups llevat a l'últim (el més significatiu) per a formar bytes
0x78 0xBB 0xC0 En hexadecimal

→ 0xC0 0xBB 0x78 Fluix d'eixida (LSB a MSB)

Decodificación ràpida

Una implementació escalar senzilla de la decodificación LEB128 és prou llenta, més encara en hardware modern a on la predicció errònea de branques és relativament costosa. Una série d'artículs presenta tècniques SIMD per a accelerar la decodificación (en estos artículs es diu VByte, pero és un atre nom per a la mateixa codificació ^{cita requerida}). El document "Vectorized VByte Decoding" va presentar "Masked VByte", que va demostrar velocitats de 6502700 millons de sancers per segon en hardware bàsic Haswell, depenent de la densitat de codificació.

Un artícul de seguiment va presentar una variant de codificació, "Stream VByte: Faster Byte Oriented Integer Compression", que va aumentar les velocitats a més de 4 mil millons de sancers per segon. Esta codificació de fluix separa el fluix de control de les senyes codificades, per lo que no és compatible binariamente en LEB128.

Vore també

• Format d'archiu de depuració DWARF
• UTF-7