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 grandes en una pequeña cantidad de bytes. LEB128 se utiliza en el formato de archivo de depuración DWARF [1] [2] y la codificación binaria WebAssembly para todos los literales enteros. [3]
El formato LEB128 es muy similar al formato de cantidad de longitud variable (VLQ); la principal diferencia es 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, al tiempo que permiten la codificación de números arbitrariamente largos. Hay dos versiones de LEB128: LEB128 sin firmar y LEB128 firmada. El decodificador debe saber si el valor codificado es LEB128 sin signo o LEB128 con signo.
Para codificar un número sin signo utilizando LEB128 sin signo ( ULEB128 ), primero represente el número en binario. Luego , cero extiende el número hasta un múltiplo de 7 bits (de modo que si el número es distinto de cero, los 7 bits más significativos no son todos 0). Divide el número en grupos de 7 bits. Genere un byte codificado para cada grupo de 7 bits, desde el grupo menos significativo hasta el más significativo. Cada byte tendrá el grupo en sus 7 bits menos significativos. Establezca el bit más significativo en cada byte excepto el último byte. El número cero está codificado como un solo byte 0x00.
Como ejemplo, así es como se codifica el número sin firmar 624485:
MSB ------------------ LSB 10011000011101100101 En binario sin formato 010011000011101100101 Rellenado a un múltiplo de 7 bits 0100110 0001110 1100101 Dividido en grupos de 7 bits00100110 10001110 11100101 Agregue bits 1 altos en todos los grupos excepto el último (el más significativo) para formar bytes 0x26 0x8E 0xE5 En hexadecimal→ 0xE5 0x8E 0x26 Flujo de salida (LSB a MSB)
LEB128 sin signo y VLQ ( cantidad de longitud variable ) comprimen cualquier número entero dado no solo en el mismo número de bits, sino exactamente en los mismos bits; los dos formatos difieren sólo en cómo se organizan exactamente esos bits.
Un número con signo se representa de manera similar: comenzando con una representación en complemento a dos de bits , donde es un múltiplo de 7, el número se divide en grupos como para la codificación sin signo.
Por ejemplo, el número con signo -123456 está codificado como 0xC0 0xBB 0x78:
MSB ------------------ LSB 11110001001000000 Codificación binaria de 123456 000011110001001000000 Como número de 21 bits 111100001110110111111 Negando todos los bits ( complemento a unos ) 111100001110111000000 Sumando uno (complemento a dos) 1111000 0111011 1000000 Dividido en grupos de 7 bits01111000 10111011 11000000 Agregue bits 1 altos en todos los grupos excepto el último (el más significativo) para formar bytes 0x78 0xBB 0xC0 En hexadecimal→ 0xC0 0xBB 0x78 Flujo de salida (LSB a MSB)
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 artículo "Vectorized VByte Decoding" [4] presentó "Masked VByte", que demostró velocidades de 650 a 2700 millones de enteros por segundo en hardware Haswell básico , 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", [5] 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.
do { byte = 7 bits de valor de orden bajo ; valor >>= 7 ; if ( value != 0 ) /* vienen más bytes */ establece el bit de byte de orden superior ; emitir byte ; } mientras ( valor ! = 0 ); más = 1 ; negativo = ( valor < 0 ); /* el tamaño en bits del valor de la variable, por ejemplo, 64 si el tipo del valor es int64_t */ size = no . de bits en entero con signo ; while ( more ) { byte = 7 bits de valor de orden inferior ; valor >>= 7 ; /* lo siguiente sólo es necesario si la implementación de >>= utiliza un desplazamiento lógico en lugar de un desplazamiento aritmético para un operando izquierdo con signo */ if ( negativo ) valor |= ( ~ 0 << ( tamaño - 7 )); /* firmar extender */ /* el bit de signo del byte es el segundo bit de orden superior (0x40) */ if (( valor == 0 && el bit de signo del byte está claro ) || ( valor == -1 && el bit de signo del byte está establecido )) más = 0 ; de lo contrario, establece un bit de byte de orden superior ; emitir byte ; } resultado = 0 ; cambio = 0 ; while ( verdadero ) { byte = siguiente byte en la entrada ; resultado |= ( 7 bits de byte de orden bajo ) << cambio ; if ( bit de byte de orden superior == 0 ) break ; cambio += 7 ; } resultado = 0 ; cambio = 0 ; /* el tamaño en bits de la variable de resultado, por ejemplo, 64 si el tipo de resultado es int64_t */ tamaño = número de bits en entero con signo ; hacer { byte = siguiente byte en la entrada ; resultado |= ( 7 bits de byte de orden bajo << cambio ); cambio += 7 ; } while ( bit de byte de orden superior ! = 0 ); /* el bit de signo del byte es el segundo bit de orden superior (0x40) */ if (( cambio < tamaño ) && ( el bit de signo del byte está establecido )) /* extensión del signo */ resultado |= ( ~ 0 << cambio ) ; const encodeSignedLeb128FromInt32 = ( valor ) => { valor |= 0 ; resultado constante = []; mientras ( verdadero ) { const byte_ = valor & 0x7f ; valor >>= 7 ; if ( ( valor === 0 && ( byte_ & 0x40 ) === 0 ) || ( valor === - 1 && ( byte_ & 0x40 ) !== 0 ) ) { resultado . empujar ( byte_ ); resultado de retorno ; } resultado . empujar ( byte_ | 0x80 ); } }; const decodeSignedLeb128 = ( entrada ) => { dejar resultado = 0 ; dejar cambio = 0 ; mientras ( verdadero ) { byte constante = entrada . cambio (); resultado |= ( byte & 0x7f ) << cambio ; cambio += 7 ; if (( 0x80 & byte ) === 0 ) { if ( shift < 32 && ( byte & 0x40 ) !== 0 ) { devolver resultado | ( ~ 0 << cambio ); } devolver resultado ; } } }; {{cite journal}}: Citar diario requiere |journal=( ayuda )