LEB128 o Little Endian Base 128, es una compresión de código de longitud variable que se utiliza para almacenar números enteros arbitrariamente largas en un número reducido de bytes. Se utiliza en el formato de archivo de depuración DWARF y en la codificación binaria WebAssembly para todos los literales enteros.
Formato de codificación El formato LEB128 es muy similar al formato de cantidad de longitud variable (VLQ). La principal diferencia radica en que LEB128 es little-endian, mientras que las cantidades de longitud variable son big-endian. Ambos permiten almacenar números pequeños en un solo byte, además de codificar números de longitud arbitraria. Existen dos versiones de LEB128: LEB128 sin signo y LEB128 con signo. El decodificador debe saber si el valor codificado es LEB128 sin signo o con signo.
LEB128 sin signo Para codificar un número sin signo usando LEB128 sin signo (ULEB128) primero se debe representar el número en binario. Luego, se convierte el número a un múltiplo de 7 bits mediante extensión de ceros(de modo que si el número no es cero, los 7 bits más significativos no sean todos 0). Divide el número en grupos de 7 bits. Genera un byte codificado por cada grupo de 7 bits, desde el menos significativo hasta el más significativo. Cada byte contendrá el grupo en sus 7 bits menos significativos. Establece el bit más significativo en cada byte, excepto en el último. El número cero se suele codificar como un solo byte 0x00. WebAssembly permite codificaciones alternativas para el cero (0x80 0x00, 0x80 0x80 0x00, ...).
Como ejemplo, así se codifica el número sin signo 624485:
MSB ------------------ LSB 10011000011101100101 En binario puro 010011000011101100101 Rellenado a un múltiplo de 7 bits 0100110 0001110 1100101 Dividido en grupos de 7 bits 00100110 10001110 11100101 Se suman los bits 1 más significativos a todos los grupos excepto al último (el más significativo) para formar bytes 0x26 0x8E 0xE5 En hexadecimal
→ 0xE5 0x8E 0x26 Flujo de salida (LSB a MSB)
Los formatos LEB128 sin signo y VLQ (cantidad de longitud variable) comprimen cualquier entero dado no solo en la misma cantidad de bits, sino exactamente en los mismos bits; ambos formatos difieren únicamente en la disposición de dichos bits.
LEB128 con signo Un número con signo se representa de forma similar: comenzando con Una representación de bits complemento a dos, donde es un múltiplo de 7, divide el número en grupos como en la codificación sin signo.
Por ejemplo, el número con signo -123456 se codifica como 0xC0 0xBB 0x78:
MSB ------------------ LSB 11110001001000000 Codificación binaria de 123456 000011110001001000000 Como un número de 21 bits 111100001110110111111 Negación de todos los bits (complemento a uno) 11110000111011100000 Sumando uno (complemento a dos) 1111000 0111011 1.000.000 Dividir en grupos de 7 bits 01111000 10111011 11000000 Sumar los bits 1 más significativos a todos los grupos excepto al último (el más significativo) para formar bytes 0x78 0xBB 0xC0 En hexadecimal
→ 0xC0 0xBB 0x78 Flujo de salida (LSB a MSB)
Decodificación rápida
Una implementación escalar sencilla de la decodificación LEB128 es bastante lenta, más aún en hardware moderno donde la predicción errónea de ramas es relativamente costosa. Una serie de artículos presenta técnicas SIMD para acelerar la decodificación (en estos artículos se llama VByte, pero es otro nombre para la misma codificación ). El documento "Vectorized VByte Decoding" presentó "Masked VByte", que demostró velocidades de 6502700 millones de enteros por segundo en hardware básico Haswell, dependiendo de la densidad de codificación.
Un artículo de seguimiento presentó una variante de codificación, "Stream VByte: Faster Byte Oriented Integer Compression", que aumentó las velocidades a más de 4 mil millones de enteros por segundo. Esta codificación de flujo separa el flujo de control de los datos codificados, por lo que no es compatible binariamente con LEB128.
Pseudocódigo tipo C
Codificar entero sin signo do { byte= value & 0x7f; /* low-order 7 bits of value */ value >>= 7; if (value != 0) /* more bytes to come */ byte|= 0x80; /* set high-order bit of byte */ emit(byte); } while (value != 0);
Codificar entero con signo more= 1; negative= (value < 0);
/* the size in bits of the variable "value", e.g., 64 if value's type is int64_t */ size= sizeof(value) * CHAR_BITS; /* no. of bits in signed integer */
while (more) { byte= value & 0x7f; /* low-order 7 bits of value */ value >>= 7; /* the following is only necessary if the implementation of >>= uses a logical shift rather than an arithmetic shift for a signed left operand this does not happen on most programming languages if "value" is in a signed type to begin with */ if (negative) value|= (~0 << (size - 7)); /* sign extend */
/* sign bit of byte is second high-order bit (0x40) */ sign_bit= byte & 0x40; if ((value== 0 && sign_bit== 0)||(value== -1 && sign_bit != 0)) more= 0; else byte|= 0x80; /* set high-order bit of byte */ emit(byte); }
Decodificar entero sin signo result= 0; shift= 0; unsigned char byte; do { byte= get_next_byte_in_input(); result|= (byte & 0x7f) << shift; /* low-order 7 bits of byte */ shift += 7; } while ((byte & 0x80) != 0); /* get high-order bit of byte */
Decodificar entero con signo result= 0; shift= 0;
/* the size in bits of the result variable, e.g., 64 if result's type is int64_t */ size= sizeof(result) * CHAR_BITS; /* no. of bits in signed integer */
/* will be assigned inside the do-while loop, but referenced afterwards */ unsigned char byte;
do { byte= get_next_byte_in_input(); result|= (byte & 0x7f) << shift; /* low-order 7 bits of byte */ shift += 7; } while ((byte & 0x80) != 0); /* get high-order bit of byte */
/* sign bit of byte is second high-order bit (0x40) */ if ((shift < size) && ((byte & 0x40) != 0)) /* sign extend */ result|= (~0 << shift);
Código en JavaScript
Codificar entero grande con signo const encodeSignedLeb128FromBigInt= (value)=> { value= BigInt(value); const result= []; while (true) { const byte_= Number(value & 0x7fn); value >>= 7n; if ( (value=== 0n && (byte_ & 0x40)=== 0)|| (value=== -1n && (byte_ & 0x40) !== 0) ) { result.push(byte_); return result;
result.push(byte_|0x80);
Decodificar entero grande con signo const decodeSignedBigInt= (input)=> { let result= 0n; let shift= 0; while (true) { const byte= input.shift(); result|= BigInt((byte & 0x7f) << shift); shift += 7; if ((byte & 0x80)=== 0) { // "sign-extending" does not apply to bigint because it has no fixed size // instead, we work by handling it as a two's complement of "shift" bits long, // which is provided by BigInt.asIntN return BigInt.asIntN(shift, result);
Aplicaciones El proyecto Android utiliza LEB128 en su formato de archivo ejecutable Dalvik (.dex). Compresión de tablas en Hewlett-Packard IA-64 para el manejo de excepciones. El formato de archivo DWARF utiliza codificación LEB128 con y sin signo para diversos campos. LLVM, en su formato de mapeo de cobertura la implementación de codificación y decodificación LEB128 de LLVM resulta útil junto con pseudocódigo mencionado anteriormente. .NET Core admite un formato de "entero codificado de 7 bits" en las clases BinaryReader y BinaryWriter.System.IO.BinaryWriter.Write7BitEncodedInt(int) method and System.IO.BinaryReader.Read7BitEncodedInt() method. Al escribir una cadena en un BinaryWriter, la longitud de la cadena se codifica con este método. Minecraft utiliza LEB128 en su protocolo para medir la longitud de los datos dentro de los paquetes. La herramienta de depuración mpatrol utiliza LEB128 en su formato de archivo de rastreo. osu! utiliza LEB128 en su formato de repetición de osu! (.osr). W3C Efficient XML Interchange (EXI) representa enteros sin signo utilizando LEB128, exactamente de la misma manera que se describe aquí. WebAssembly, en su codificación binaria portátil de los módulos. En xZ Utils
Codificaciones relacionadas Codificación de enteros de longitud variable de Dlugosz (original) utiliza múltiplos de 7 bits para los tres primeros intervalos de tamaño, pero a partir de ahí los incrementos varían. Además, coloca todos los bits de prefijo al principio de la palabra, en lugar de al principio de cada byte. Los bytes del descriptor de informe HID utilizan un campo de bits de conteo de bytes de 2 bits para codificar el tamaño del siguiente entero de cero, uno, dos o cuatro bytes, siempre little endian. El signo, es decir, si se expande el entero acortado con signo o no, depende del tipo de descriptor. El formato de archivo de código de bits LLVM utiliza una técnica similar a la, excepto que el valor se divide en grupos de bits de tamaño dependiente del contexto, donde el bit más significativo indica una continuación, en lugar de 7 bits fijos. Protocol Buffers (Protobuf) utiliza la misma codificación para enteros sin signo, pero codifica los enteros con signo anteponiendo el signo como el bit menos significativo del primer byte. ASN.1 BER, DER Codifica los valores de cada tipo ASN.1 como una cadena de octetos de ocho bits.
Referencias
Véase también Formato de archivo de depuración DWARF UTF-7
Categoría:Algoritmos de compresión sin pérdida