Una cantidad de longitud variable ( VLQ ) es un código universal que utiliza una cantidad arbitraria de octetos binarios ( bytes de ocho bits ) para representar un entero arbitrariamente grande . Un VLQ es esencialmente una representación en base 128 de un entero sin signo con la adición del octavo bit para marcar la continuación de bytes. VLQ es idéntico a LEB128 excepto en el orden de bytes . Vea el ejemplo a continuación.
La compresión Base-128 se conoce por muchos nombres: VB (Variable Byte), VByte , Varint , VInt , EncInt , etc. [1]
Se definió una cantidad de longitud variable ( VLQ ) para su uso en el formato de archivo MIDI estándar [2] para ahorrar espacio adicional para un sistema con recursos limitados, y también se utiliza en el posterior Formato de música extensible (XMF) .
Base-128 también se utiliza en la codificación BER ASN.1 para codificar números de etiqueta e identificadores de objetos . [3] También se utiliza en el entorno WAP , donde se denomina entero sin signo de longitud variable o uintvar . El formato de depuración DWARF [4] define una variante llamada LEB128 (o ULEB128 para números sin signo), donde el grupo menos significativo de 7 bits se codifica en el primer byte y los bits más significativos están en el último byte (por lo que efectivamente es el análogo little-endian de un VLQ). Los búferes de protocolo de Google utilizan un formato similar para tener una representación compacta de valores enteros, [5] al igual que Oracle Portable Object Format (POF) [6] y el "7-bit encoded int" de Microsoft .NET Framework en las clases BinaryReader y BinaryWriter . [7]
También se utiliza ampliamente en navegadores web para mapeo de fuentes (que contienen una gran cantidad de asignaciones de números enteros de líneas y columnas) para mantener el tamaño del mapa al mínimo. [8]
Los números enteros de ancho variable en LLVM utilizan un principio similar. Los fragmentos de codificación son little-endian y no necesitan tener un tamaño de 8 bits. La documentación de LLVM describe un campo que utiliza fragmentos de 4 bits, donde cada fragmento consta de 1 bit de continuación y 3 bits de carga útil. [9]
La codificación supone un octeto (un byte de 8 bits) donde el bit más significativo (MSB), también conocido comúnmente como bit de signo , está reservado para indicar si sigue otro octeto VLQ.
Si A es 0, entonces este es el último octeto VLQ del entero. Si A es 1, entonces sigue otro octeto VLQ.
B es un número de 7 bits [0x00, 0x7F] y n es la posición del octeto VLQ, donde B 0 es el menos significativo . Los octetos VLQ se ordenan de mayor a menor en un flujo.
La codificación VLQ general es simple, pero en su forma básica solo está definida para números enteros sin signo (no negativos, positivos o cero) y es algo redundante, ya que anteponer octetos 0x80 corresponde a un relleno de ceros. Existen varias representaciones de números con signo para manejar números negativos y técnicas para eliminar la redundancia.
Google desarrolló Group Varint Encoding (GVE) después de observar que la codificación VLQ tradicional genera muchas ramificaciones de CPU durante la descompresión. GVE utiliza un solo byte como encabezado para 4 valores uint32 de longitud variable. El byte de encabezado tiene 4 números de 2 bits que representan la longitud de almacenamiento de cada uno de los 4 uint32 siguientes. Este diseño elimina la necesidad de verificar y eliminar bits de continuación VLQ. Los bytes de datos se pueden copiar directamente a su destino. Este diseño reduce las ramificaciones de CPU , lo que hace que GVE sea más rápido que VLQ en las CPU con canalización modernas. [10]
PrefixVarint es un diseño similar pero con un máximo de uint64. Se dice que "se inventó varias veces de forma independiente". [11] Es posible convertirlo en una versión encadenada con infinitas continuaciones.
Los números negativos se pueden manejar utilizando un bit de signo , que solo necesita estar presente en el primer octeto.
En el formato de datos para paquetes Unreal que utiliza Unreal Engine , se utiliza un esquema de cantidad de longitud variable denominado Índices compactos [12] . La única diferencia en esta codificación es que el primer octeto VLQ tiene el sexto bit reservado para indicar si el entero codificado es positivo o negativo. Cualquier octeto VLQ consecutivo sigue la estructura general.
Si A es 0, entonces este es el último octeto VLQ del entero. Si A es 1, entonces sigue otro octeto VLQ.
Si B es 0, entonces el VLQ representa un entero positivo. Si B es 1, entonces el VLQ representa un número negativo.
C es el fragmento de número que se está codificando y n es la posición del octeto VLQ, donde C 0 es el menos significativo . Los octetos VLQ se ordenan de menor a mayor en un flujo.
Una forma alternativa de codificar números negativos es usar el bit menos significativo como signo. Esto se hace especialmente para los búferes de protocolo de Google y se conoce como codificación en zigzag para números enteros con signo . [13] Se pueden codificar los números de modo que el 0 codificado corresponda a 0, el 1 a −1, el 10 a 1, el 11 a −2, el 100 a 2, etc.: el conteo ascendente alterna entre no negativos (comenzando en 0) y negativos (ya que cada paso cambia el bit menos significativo, de ahí el signo), de ahí el nombre de "codificación en zigzag". Concretamente, se transforma el entero como para los enteros de k(n << 1) ^ (n >> k - 1) bits fijos .
LEB128 utiliza el complemento a dos para representar números con signo. En este esquema de representación, n bits codifican un rango de −2 n a 2 n − 1, y todos los números negativos comienzan con un 1 en el bit más significativo. En LEB128 con signo, la entrada se extiende al signo de modo que su longitud sea un múltiplo de 7 bits. A partir de ahí, la codificación continúa de la forma habitual. [14]
En LEB128, la secuencia se ordena con el orden menos significativo primero. [14]
Con la codificación VLQ descrita anteriormente, cualquier número que pueda codificarse con N octetos también puede codificarse con más de N octetos simplemente anteponiendo octetos 0x80 adicionales como relleno de ceros. Por ejemplo, el número decimal 358 puede codificarse como VLQ 0x8266 de 2 octetos, o el número 0358 puede codificarse como VLQ 0x808266 de 3 octetos, o 00358 como VLQ 0x80808266 de 4 octetos, y así sucesivamente.
Sin embargo, el formato VLQ utilizado en Git [15] elimina esta redundancia de anteposición y extiende el rango representable de VLQ más cortos agregando un desplazamiento a los VLQ de 2 o más octetos de tal manera que el valor más bajo posible para un VLQ de ( N + 1) octetos se convierte en exactamente uno más que el valor máximo posible para un VLQ de N octetos. En particular, dado que un VLQ de 1 octeto puede almacenar un valor máximo de 127, al VLQ mínimo de 2 octetos (0x8000) se le asigna el valor 128 en lugar de 0. Por el contrario, el valor máximo de un VLQ de 2 octetos (0xFF7F) es16 511 en lugar de solo16 383 . De manera similar, el VLQ mínimo de 3 octetos (0x808000) tiene un valor de16 512 en lugar de cero, lo que significa que el VLQ máximo de 3 octetos (0xFFFF7F) es2 113 663 en lugar de sólo2 097 151 .
De esta manera, existe una única codificación de cada número entero, convirtiéndose en una numeración biyectiva en base 128 .
A continuación se muestra un ejemplo resuelto para el número decimal 137 :
Otra forma de ver esto es representar el valor en base 128 y luego establecer el MSB de todos los dígitos de base 128 excepto el último en 1.
La especificación del formato de archivo MIDI estándar ofrece más ejemplos: [2] [16]