Una cantidad de longitud variable ( VLQ ) es un código universal que usa un número arbitrario 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 los bytes. VLQ es idéntica a LEB128 excepto en endianness . Vea el ejemplo a continuación.
Aplicaciones e historia
La compresión Base-128 se conoce por muchos nombres: VB (Byte variable), VByte , Varint , VInt , EncInt , etc. [1]
Se definió una cantidad de longitud variable ( VLQ ) para usar en el formato de archivo MIDI estándar [2] para ahorrar espacio adicional para un sistema con recursos limitados, y también se usa en el formato de música extensible (XMF) posterior .
Base-128 también se utiliza en la codificación ASN.1 BER para codificar números de etiqueta e identificadores de objeto . [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 (así que efectivamente es el análogo little-endian de un VLQ). Los búferes de protocolo de Google usan un formato similar para tener una representación compacta de valores enteros, [5] al igual que Oracle Portable Object Format (POF) [6] y Microsoft .NET Framework "7-bit encoded int" en las clases BinaryReader y BinaryWriter . [7]
También se utiliza ampliamente en los navegadores web para el mapeo de fuentes, que contienen muchos mapeos de números de columnas y líneas enteras, para mantener el tamaño del mapa al mínimo. [8]
Los enteros de ancho variable en LLVM utilizan un principio similar. Los fragmentos de codificación son little-endian y no es necesario que tengan un tamaño de 8 bits. La documentación de LLVM describe un campo que utiliza un fragmento de 4 bits, y cada fragmento consta de una continuación de 1 bit y una carga útil de 3 bits. [9]
Estructura general
La codificación asume un octeto (un byte de ocho 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.
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
---|---|---|---|---|---|---|---|
2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 |
A | B n |
Si A es 0, este es el último octeto VLQ del entero. Si A es 1, sigue otro octeto VLQ.
B es un número de 7 bits [0x00, 0x7F] yn es la posición del octeto VLQ donde B 0 es el menos significativo . Los octetos VLQ se ordenan primero más significativos en una secuencia.
Variantes
La codificación general de VLQ es simple, pero en forma básica solo se define para enteros sin signo (no negativos, positivos o cero), y es algo redundante, ya que anteponer 0x80 octetos corresponde a relleno de ceros. Hay varias representaciones de números con signo para manejar números negativos y técnicas para eliminar la redundancia.
Codificación Varint de grupo
Google desarrolló Group Varint Encoding (GVE) después de observar que la codificación VLQ tradicional incurre en muchas ramas 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 siguientes 4 uint32s. Este diseño elimina la necesidad de verificar y eliminar los bits de continuación de VLQ. Los bytes de datos se pueden copiar directamente a su destino. Este diseño reduce las ramas de la 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 ha inventado varias veces de forma independiente". [11] Se puede cambiar a una versión encadenada con infinitas continuaciones.
Números firmados
Bit de signo
Los números negativos se pueden manejar usando un bit de signo , que solo necesita estar presente en el primer octeto.
En el formato de datos de Unreal Packages utilizado por Unreal Engine , se utiliza un esquema de cantidad de longitud variable llamado Compact Indices [12] . La única diferencia en esta codificación es que el primer VLQ tiene el sexto bit reservado para indicar si el entero codificado es positivo o negativo. Cualquier octeto VLQ consecutivo sigue la estructura general.
Primer octeto VLQ | Otros octetos de VLQ | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 | 2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 |
A | B | C 0 | A | C n (n> 0) |
Si A es 0, este es el último octeto VLQ del entero. Si A es 1, sigue otro octeto VLQ.
Si B es 0, entonces el VLQ representa un número entero positivo. Si B es 1, entonces el VLQ representa un número negativo.
C es el fragmento numérico que se codifica y n es la posición del octeto VLQ donde C 0 es el menos significativo . Los octetos VLQ se ordenan primero más significativos en una secuencia. [ dudoso ]
Codificación en zigzag
Una forma alternativa de codificar números negativos es usar el bit menos significativo para el signo. Esto se hace en particular para los búferes de protocolo de Google y se conoce como codificación en zigzag para enteros firmados . [13] Uno puede codificar los números de modo que el 0 codificado corresponda a 0, 1 a -1, 10 a 1, 11 a -2, 100 a 2, etc .: el conteo alterna entre no negativo (comenzando en 0) y negativo ( ya que cada paso cambia el bit menos significativo, de ahí el signo), de ahí el nombre "codificación en zigzag". Concretamente, transforme el entero como (n << 1) ^ (n >> k - 1)
para enteros fijos de k bits.
Complemento a dos
LEB128 usa 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 Signed LEB128, la entrada se amplía con el signo para que su longitud sea un múltiplo de 7 bits. A partir de ahí, la codificación procede como de costumbre. [14]
En LEB128, la secuencia se ordena primero menos significativa. [14]
Eliminar la redundancia
Con la codificación VLQ descrita anteriormente, cualquier número que pueda codificarse con N octetos también se puede codificar con más de N octetos simplemente añadiendo 0x80 octetos adicionales como relleno de ceros. Por ejemplo, el número decimal 358 se puede codificar como VLQ de 2 octetos 0x8266 o el número 0358 se puede codificar como VLQ de 3 octetos 0x808266 o 00358 como VLQ de 4 octetos 0x80808266 y así sucesivamente.
Sin embargo, el formato VLQ usado en Git [15] elimina esta redundancia antepuesta y extiende el rango representable de VLQ más cortos agregando un desplazamiento a VLQ de 2 o más octetos de tal manera que el valor más bajo posible para tal (N + 1 ) -octeto VLQ se convierte exactamente en 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. A la inversa, el valor máximo de dicho VLQ de 2 octetos (0xff7f) es 16511 en lugar de solo 16383. De manera similar, el VLQ mínimo de 3 octetos (0x808000) tiene un valor de 16512 en lugar de cero, lo que significa que el VLQ máximo de 3 octetos (0xffff7f) es 2113663 en lugar de solo 2097151.
De esta manera, hay una y solo una codificación de cada entero, lo que lo convierte en una numeración biyectiva en base 128 .
Ejemplos de
Aquí hay un ejemplo resuelto para el número decimal 137 :
- Representa el valor en notación binaria (por ejemplo, 137 como 10001001)
- Divídalo en grupos de 7 bits comenzando desde el bit significativo más bajo (por ejemplo, 137 como 0000001 0001001). Esto equivale a representar el número en base 128.
- Tome los 7 bits más bajos y eso le da el byte menos significativo ( 0 000 1001). Este byte es el último.
- Para todos los demás grupos de 7 bits (en el ejemplo, es 000 0001), establezca el MSB en 1 (lo que da 1 000 0001 en nuestro ejemplo). Por lo tanto, 137 se convierte en 1 000 0001 0 000 1001 donde los bits en negrita son algo que agregamos. Estos bits añadidos indican si hay otro byte a seguir o no. Por lo tanto, por definición, el último byte de un entero de longitud variable tendrá 0 como su MSB .
Otra forma de ver esto es representar el valor en base 128 y luego establecer el MSB de todos menos el último dígito base 128 en 1.
La especificación de formato de archivo MIDI estándar ofrece más ejemplos: [2] [16]
Entero (decimal) | Entero (hexadecimal) | Entero (binario) | Cantidad de longitud variable (hexadecimal) | Cantidad de longitud variable (binaria) |
---|---|---|---|---|
0 | 0x00000000 | 00000000 00000000 00000000 00000000 | 0x00 | 00000000 |
127 | 0x0000007F | 00000000 00000000 00000000 01111111 | 0x7F | 01111111 |
128 | 0x00000080 | 00000000 00000000 00000000 10000000 | 0x81 0x00 | 10000001 00000000 |
8192 | 0x00002000 | 00000000 00000000 00100000 00000000 | 0xC0 0x00 | 11000000 00000000 |
16383 | 0x00003FFF | 00000000 00000000 00111111 11111111 | 0xFF 0x7F | 11111111 01111111 |
16384 | 0x00004000 | 00000000 00000000 01000000 00000000 | 0x81 0x80 0x00 | 10000001 10000000 00000000 |
2097151 | 0x001FFFFF | 00000000 00011111 11111111 11111111 | 0xFF 0xFF 0x7F | 11111111 11111111 01111111 |
2097152 | 0x00200000 | 00000000 00100000 00000000 00000000 | 0x81 0x80 0x80 0x00 | 10000001 10000000 10000000 00000000 |
134217728 | 0x08000000 | 00001000 00000000 00000000 00000000 | 0xC0 0x80 0x80 0x00 | 11000000 10000000 10000000 00000000 |
268435455 | 0x0FFFFFFF | 00001111 11111111 11111111 11111111 | 0xFF 0xFF 0xFF 0x7F | 11111111 11111111 11111111 01111111 |
Referencias
- ^ Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson. "Un estudio experimental de la compresión de mapa de bits frente a la compresión de lista invertida" . 2017. doi : 10.1145 / 3035918.3064007
- ^ a b Formato de archivo MIDI: Cantidades variables
- ^ http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf
- ^ Estándar DWARF
- ^ Búferes de protocolo de Google
- ^ Formato de objeto portátil de Oracle (POF)
- ^ Método System.IO.BinaryWriter.Write7BitEncodedInt (int) y método System.IO.BinaryReader.Read7BitEncodedInt ()
- ^ Introducción a los mapas de código fuente javascript
- ^ "Formato de archivo de código de bits LLVM", sección "Enteros de ancho variable" . Consultado el 1 de octubre de 2019.
- ^ Jeff Dean. "Desafíos en la construcción de sistemas de recuperación de información a gran escala" (PDF) . pag. 58 . Consultado el 30 de mayo de 2020 .
- ^ Olesen, Jakob Stoklund (31 de mayo de 2020). "stoklund / varint" .
- ^ http://unreal.epicgames.com/Packages.htm
- ^ Búferes de protocolo: codificación: enteros firmados
- ^ a b Free Standards Group (diciembre de 2005). "Especificación de formato de información de depuración de DWARF versión 3.0" (PDF) . pag. 70 . Consultado el 19 de julio de 2009 .
- ^ https://github.com/git/git/blob/7fb6aefd2aaffe66e614f7f7b83e5b7ab16d4806/varint.c#L4
- ^ Especificación de formato de archivo MIDI estándar. 1.1 (PDF)
enlaces externos
- Asociación de fabricantes MIDI (MMA): fuente de especificaciones MIDI en inglés
- Association of Musical Electronics Industry (AMEI): fuente de especificaciones MIDI en japonés