LEB128
LEB128 o Little Endian Base 128 es una compresión de código de longitud variable que se utiliza para almacenar 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 mismo tiempo que permiten la codificación de números arbitrariamente largos. Hay 2 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 firmar usando LEB128 sin firmar ( ULEB128 ), primero represente el número en binario. Luego, el 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). Divida el número en grupos de 7 bits. Salida de un byte codificado para cada grupo de 7 bits, desde el grupo menos significativo al 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 se codifica como un solo byte 0x00.
LEB128 sin signo y VLQ ( cantidad de longitud variable ) comprimen cualquier entero dado no solo en el mismo número de bits, sino en exactamente los mismos bits; los dos formatos difieren solo en la forma exacta en que se organizan esos bits.
Un número con signo se representa de manera similar: comenzando con una representación de complemento a dos de -bit , donde es un múltiplo de 7, el número se divide en grupos como para la codificación sin signo.
Una implementación escalar sencilla de la decodificación LEB128 es bastante lenta, incluso más en hardware moderno donde la predicción errónea de rama es relativamente cara. Una serie de artículos presenta técnicas SIMD para acelerar la decodificación (se llama VByte en estos artículos, pero es otro nombre para la misma codificación). El artículo "Decodificación de VByte vectorizado" [4] presentó "VByte enmascarado", que demostró velocidades de 650-2700 millones de enteros por segundo en hardware básico Haswell, dependiendo de la densidad de codificación. Un artículo de seguimiento presentó una codificación variante, "Stream VByte: Compresión de enteros orientada a bytes más rápida", [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 binario compatible con LEB128.