LZMA

Los datos LZMA se decodifican al nivel más bajo, bit a bit, mediante el decodificador de rango, en la dirección del decodificador LZMA.

La decodificación de rango basada en contexto es invocada por el algoritmo LZMA pasándole una referencia al "contexto", que consiste en la variable sin signo de 11 bits prob (normalmente implementada usando un tipo de datos de 16 bits) que representa la probabilidad predicha de que el bit sea 0, que es leída y actualizada por el decodificador de rango (y debe inicializarse a ⁠${\displaystyle 2^{10}}$⁠ , que representa una probabilidad de 0,5).

La decodificación de rango de probabilidad fija asume una probabilidad de 0,5, pero funciona de forma ligeramente diferente a la decodificación de rango basada en el contexto.

El estado del decodificador de rango consta de dos variables sin signo de 32 bits: rango (que representa el tamaño del rango) y código (que representa el punto codificado dentro del rango).

La inicialización del decodificador de rango consiste en establecer el rango en 2 ³² − 1 y el código en el valor de 32 bits que comienza en el segundo byte en el flujo interpretado como big-endian; el primer byte en el flujo se ignora por completo.

La normalización se realiza de la siguiente manera:

1. Desplaza tanto el rango como el código 8 bits a la izquierda.
2. Lee un byte del flujo comprimido.
3. Establezca los 8 bits menos significativos del código al valor del byte leído.

La decodificación de rango basada en el contexto de un bit utilizando la variable de probabilidad prob procede de esta manera:

1. Si el rango es menor que ⁠${\displaystyle 2^{24}}$⁠ , realizar normalización
2. Establecer vinculado a ⁠${\displaystyle \lfloor rango/2^{11}\rfloor \times prob}$⁠
3. Si el código es menor que el límite :
   1. Establecer el rango al límite
   2. Establecer prob a prob + ⁠${\displaystyle \lfloor 2^{11}-prob\rfloor /2^{5}}$⁠
   3. Bit de retorno 0
4. De lo contrario (si el código es mayor o igual al límite ):
   1. Establecer rango al límite de rango
   2. Establecer código a código − vinculado
   3. Establecer probabilidad a​${\displaystyle prob-\lfloor prob/2^{5}\rfloor }$⁠
   4. Bit de retorno 1

La decodificación de un bit mediante un rango de probabilidad fija se realiza de la siguiente manera:

1. Si el rango es menor que ⁠${\displaystyle 2^{24}}$⁠ , realizar normalización
2. Establecer rango a​${\displaystyle \lfloor rango/2\rfloor }$⁠
3. Si el código es menor que el rango :
   1. Bit de retorno 0
4. En caso contrario (si el código es mayor o igual que el rango ):
   1. Establecer código a rango de código
   2. Bit de retorno 1

La implementación del kernel de Linux de la decodificación de probabilidad fija en rc_direct(), por razones de rendimiento, no incluye una bifurcación condicional, sino que resta rango del código incondicionalmente. El bit de signo resultante se utiliza tanto para decidir el bit a devolver como para generar una máscara que se combina con el código y se agrega a rango .

Tenga en cuenta que:

1. La división por${\displaystyle 2^{11}}$cuando el cálculo de la operación de límite y piso se realiza antes de la multiplicación, no después (aparentemente para evitar requerir soporte de hardware rápido para la multiplicación de 32 bits con un resultado de 64 bits).
2. La decodificación de probabilidad fija no es estrictamente equivalente a la decodificación de rango basada en contexto con cualquier valor de probabilidad , debido a que la decodificación de rango basada en contexto descarta los 11 bits inferiores del rango antes de multiplicarlos por la probabilidad , como se describió anteriormente, mientras que la decodificación de probabilidad fija solo descarta el último bit.

El decodificador de rango también proporciona las funciones de decodificación de árbol de bits, árbol de bits inverso y enteros de probabilidad fija, que se utilizan para decodificar enteros y generalizan la decodificación de un solo bit descrita anteriormente. Para decodificar enteros sin signo menores que límite , se proporciona una matriz de ( límite − 1) variables de probabilidad de 11 bits, que están organizadas conceptualmente como los nodos internos de un árbol binario completo con límite de hojas.

La decodificación de árboles de bits no inversa funciona manteniendo un puntero al árbol de variables, que comienza en la raíz. Mientras el puntero no apunte a una hoja, se decodifica un bit utilizando la variable indicada por el puntero, y este se mueve a los hijos izquierdo o derecho según si el bit es 0 o 1; cuando el puntero apunta a una hoja, se devuelve el número asociado a ella.

La decodificación del árbol de bits no inverso se produce, por lo tanto, desde el bit más significativo hasta el menos significativo, deteniéndose cuando solo es posible un valor en el rango válido (esto permite conceptualmente tener tamaños de rango que no son potencias de dos, aunque LZMA no hace uso de esto).

La decodificación inversa de árbol de bits decodifica desde el bit menos significativo hasta el más significativo, por lo que solo admite rangos que son potencias de dos y siempre decodifica la misma cantidad de bits. Es equivalente a realizar una decodificación de árbol de bits no inversa con un límite de potencia de dos _e invertir los últimos log₂ ( límite ) bits del resultado.

En la función rc_bittree del kernel de Linux, los enteros se devuelven en el rango [ límite , 2 × límite ) (con límite añadido al valor conceptual), y la variable en el índice 0 del array no se utiliza, mientras que la del índice 1 es la raíz, y los índices de los hijos izquierdo y derecho se calculan como 2i y 2i + 1. La función rc_bittree_reverse, en cambio, añade enteros en el rango [0, límite ) a una variable proporcionada por quien la llama, donde límite se representa implícitamente por su logaritmo, y tiene su propia implementación independiente por razones de eficiencia.

La decodificación de enteros de probabilidad fija simplemente realiza repetidamente una decodificación de bits de probabilidad fija, leyendo los bits desde el más significativo hasta el menos significativo.

El decodificador LZMA se configura mediante un byte de "propiedades" lclppb y un tamaño de diccionario. El valor del byte lclppb es , donde:lc + lp * 9 + pb * 9 * 5

• lc es el número de bits altos del byte anterior que se utilizarán como contexto para la codificación literal (el valor predeterminado utilizado por el SDK de LZMA es 3).
• lp es el número de bits bajos de la posición del diccionario que se incluirán en literal_pos_state (el valor predeterminado utilizado por el SDK de LZMA es 0).
• pb es el número de bits bajos de la posición del diccionario que se incluirán en pos_state (el valor predeterminado utilizado por el SDK de LZMA es 2).

En flujos que no son LZMA2, lc no debe ser mayor que 8, y lp y pb no deben ser mayores que 4; esto da como resultado un rango de 0 a 224. En flujos LZMA2, pb no debe ser mayor que 4; esto proporciona un conjunto mucho mayor de valores imposibles.lc + lp

En el formato de archivo LZMA de 7-zip, la configuración se realiza mediante una cabecera que contiene el byte "properties" seguido del tamaño del diccionario little-endian de 32 bits en bytes. En LZMA2, el byte properties puede modificarse opcionalmente al inicio de los paquetes LZMA2, mientras que el tamaño del diccionario se especifica en la cabecera LZMA2, como se describe más adelante.

El formato de paquete LZMA ya se ha descrito, y esta sección especifica cómo LZMA modela estadísticamente las secuencias codificadas con LZ, o en otras palabras, qué variables de probabilidad se pasan al decodificador de rango para decodificar cada bit.

Estas variables de probabilidad se implementan como matrices multidimensionales; antes de introducirlas, se definen algunos valores que se utilizan como índices en dichas matrices multidimensionales.

El valor del estado se basa conceptualmente en cuáles de los patrones de la siguiente tabla coinciden con los últimos 2 a 4 tipos de paquetes vistos, y se implementa como un estado de máquina de estados que se actualiza de acuerdo con la tabla de transiciones que aparece en la tabla cada vez que se emite un paquete.

El estado inicial es 0, por lo que se supone que los paquetes anteriores al inicio son paquetes LIT.

Los valores pos_state y literal_pos_state consisten respectivamente en los bits menos significativos pb y lp (hasta 4, según el encabezado LZMA o el paquete de propiedades LZMA2) de la posición del diccionario (el número de bytes codificados desde el último reinicio del diccionario, módulo el tamaño del diccionario). Cabe destacar que el tamaño del diccionario suele ser un múltiplo de una gran potencia de 2, por lo que estos valores se describen de forma equivalente como los bits menos significativos del número de bytes sin comprimir vistos desde el último reinicio del diccionario.

El valor prev_byte_lc_msbs se establece en los bits más significativos (hasta 4, según el encabezado LZMA o el paquete de propiedades LZMA2) del byte anterior sin comprimir .

El valor is_REP indica si un paquete que incluye una longitud es un LONGREP en lugar de un MATCH.

El valor match_byte es el byte que se habría decodificado si se hubiera utilizado un paquete SHORTREP (en otras palabras, el byte encontrado en el diccionario en la última distancia utilizada); solo se utiliza justo después de un paquete *MATCH.

literal_bit_mode es una matriz de 8 valores en el rango 0–2, uno para cada posición de bit en un byte, que son 1 o 2 si el paquete anterior fue un *MATCH y es la posición del bit más significativo o todos los bits más significativos en el literal a codificar/decodificar son iguales a los bits en las posiciones correspondientes en match_byte , mientras que en caso contrario es 0; la elección entre los valores 1 o 2 depende del valor del bit en la misma posición en match_byte .

El conjunto de variables literal/literal puede verse como un "pseudoárbol de bits" similar a un árbol de bits pero con 3 variables en lugar de 1 en cada nodo, elegidas en función del valor literal_bit_mode en la posición del bit del siguiente bit a decodificar después del contexto del árbol de bits denotado por el nodo.

La afirmación, que se encuentra en algunas fuentes, de que los literales después de un *MATCH se codifican como el XOR del valor del byte con match_byte es incorrecta; en cambio, se codifican simplemente como su valor de byte, pero utilizando el pseudoárbol de bits que se acaba de describir y el contexto adicional que se enumera en la tabla a continuación.

Los grupos de variables de probabilidad utilizados en LZMA son los siguientes:

El contenedor LZMA2 admite múltiples ejecuciones de datos LZMA comprimidos y sin comprimir. Cada ejecución comprimida de LZMA puede tener una configuración y un diccionario LZMA diferentes. Esto mejora la compresión de archivos parcial o totalmente incompresibles y permite la compresión y descompresión multihilo al dividir el archivo en secuencias que pueden comprimirse o descomprimirse de forma independiente y en paralelo.

El encabezado LZMA2 consta de un byte que indica el tamaño del diccionario:

• 40 indica un tamaño de diccionario de 4 GB − 1
• Incluso valores inferiores a 40 indican un tamaño de diccionario de 2v ^{/ 2 + 12} bytes.
• Los valores impares menores que 40 indican un tamaño de diccionario de 3×2 ^{( v − 1)/2 + 11} bytes.
• Los valores superiores a 40 no son válidos.

Los datos LZMA2 consisten en paquetes que comienzan con un byte de control, con los siguientes valores:

• 0 indica el final del archivo.
• 1 indica un reinicio del diccionario seguido de un fragmento sin comprimir.
• 2 indica un fragmento sin comprimir sin reinicio del diccionario.
• 3–0x7f son valores no válidos
• 0x80–0xff denota un bloque LZMA, donde los 5 bits menos significativos se utilizan como bits 16–20 del tamaño sin comprimir menos uno, y los bits 5–6 indican lo que se debe reiniciar.

Los bits 5 y 6 para los fragmentos LZMA pueden ser:

• 0: nada reiniciado
• 1: reinicio de estado
• 2: restablecimiento de estado, restablecimiento de propiedades mediante byte de propiedades
• 3: restablecimiento de estado, restablecimiento de propiedades mediante byte de propiedades, restablecimiento de diccionario

Los reinicios de estado de LZMA provocan un reinicio de todo el estado de LZMA excepto el diccionario, y específicamente:

• El codificador de rango
• El valor del estado
• Las últimas distancias para partidos repetidos
• Todas las probabilidades de LZMA

Los fragmentos sin comprimir constan de:

• Un valor big-endian de 16 bits que codifica el tamaño de los datos menos uno.
• Los datos que se copiarán textualmente en el diccionario y la salida

Los fragmentos de LZMA constan de:

• Un valor big-endian de 16 bits que codifica los 16 bits inferiores del tamaño sin comprimir menos uno.
• Un valor big-endian de 16 bits que codifica el tamaño comprimido menos uno.
• Un byte properties/lclppb si el bit 6 en el byte de control está activado.
• Los datos comprimidos LZMA, comenzando con los 5 bytes (de los cuales el primero se ignora) utilizados para inicializar el codificador de rango (que están incluidos en el tamaño comprimido).

El formato .xz , que puede contener datos LZMA2, está documentado en tukaani.org , ^{[ 11 ]} mientras que el formato de archivo .7z, que puede contener datos LZMA o LZMA2, está documentado en el archivo 7zformat.txt contenido en el SDK de LZMA. ^{[ 12 ]}