Desinflar

En informática, Deflate (estilizado como DEFLATE) es un formato de archivo de compresión de datos sin pérdidas que utiliza una combinación de codificación LZ77 y Huffman. Fue diseñado por Phil Katz, para la versión 2 de su herramienta de archivo PKZIP. Deflate se especificó más tarde en RFC 1951 (1996).

Katz también diseñó el algoritmo original utilizado para construir flujos Deflate. Este algoritmo fue patentado como U.S. Patente 5,051,745, y asignada a PKWARE, Inc. Como se indica en el documento RFC, se pensaba ampliamente que un algoritmo que producía archivos Deflate se podía implementar de una manera que no estaba cubierta por patentes. Esto condujo a su uso generalizado, por ejemplo, en archivos comprimidos gzip y archivos de imagen PNG, además del formato de archivo ZIP para el que Katz lo diseñó originalmente. La patente ha expirado desde entonces.

Formato de transmisión

Un flujo de Deflate consta de una serie de bloques. Cada bloque está precedido por un encabezado de 3 bits:

• Primer bit: Marcador de última apertura en corriente:
  • 1: Este es el último bloque del arroyo.
  • 0: Hay más bloques para procesar después de éste.
• Segunda y tercera parte: Método de codificación utilizado para este tipo de bloque:
  • 00: Una sección almacenada (a.k.a. cruda o literal), entre 0 y 65.535 bytes de longitud
  • 01A Huffman estático bloque comprimido, utilizando un árbol de Huffman pre-agregado definido en el RFC
  • 10A dinámico Huffman bloque comprimido, completo con la tabla Huffman suministrado
  • 11: Reservado - no usar.

La opción de bloque almacenado agrega una sobrecarga mínima y se usa para datos que no se pueden comprimir.

La mayoría de los datos comprimibles terminarán siendo codificados usando el método 10, la codificación dinámica Huffman, que produce un árbol Huffman optimizado personalizado para cada bloque de datos individualmente. Las instrucciones para generar el árbol de Huffman necesario siguen inmediatamente al encabezado del bloque. La opción Huffman estática se usa para mensajes cortos, donde el ahorro fijo obtenido al omitir el árbol supera el porcentaje de pérdida de compresión debido al uso de un código no óptimo (por lo tanto, no técnicamente Huffman).

La compresión se logra a través de dos pasos:

• La combinación y sustitución de cadenas duplicadas con punteros.
• Replacing símbolos con símbolos nuevos y ponderados basados en la frecuencia de uso.

Eliminación de cadenas duplicadas

Dentro de los bloques comprimidos, si se detecta una serie duplicada de bytes (una cadena repetida), entonces se inserta una referencia inversa, vinculando a la ubicación anterior de esa cadena idéntica en su lugar. Una coincidencia codificada con una cadena anterior consta de una longitud de 8 bits (3 a 258 bytes) y una distancia de 15 bits (1 a 32 768 bytes) al comienzo del duplicado. Las referencias anteriores relativas se pueden realizar en cualquier cantidad de bloques, siempre que la distancia aparezca dentro de los últimos 32 KiB de datos sin comprimir decodificados (denominados ventana deslizante).

Si la distancia es menor que la longitud, el duplicado se superpone, lo que indica repetición. Por ejemplo, una serie de 10 bytes idénticos se puede codificar como un byte, seguido de un duplicado de 9 de longitud, comenzando con el byte anterior.

Buscar subcadenas duplicadas en el texto anterior es la parte computacionalmente más costosa del algoritmo DEFLATE y la operación a la que afecta la configuración del nivel de compresión.

Reducción de bits

La segunda etapa de compresión consiste en reemplazar los símbolos de uso común con representaciones más cortas y los símbolos de uso menos común con representaciones más largas. El método utilizado es la codificación de Huffman, que crea un árbol sin prefijo de intervalos que no se superponen, donde la longitud de cada secuencia es inversamente proporcional al logaritmo de la probabilidad de que ese símbolo deba codificarse. Cuanto más probable sea que un símbolo tenga que ser codificado, más corta será su secuencia de bits.

Se crea un árbol que contiene espacio para 288 símbolos:

• 0–255: representan los bytes/symbols literales 0–255.
• 256: final de bloque – dejar de procesar si el último bloque, de lo contrario empezar a procesar el siguiente bloque.
• 257–285: combinado con extra-bits, una longitud de partido de 3–258 bytes.
• 286, 287: no utilizado, reservado e ilegal, pero todavía parte del árbol.

Un código de duración de la coincidencia siempre estará seguido de un código de distancia. Basado en el código de distancia leído, más "extra" se pueden leer bits para producir la distancia final. El árbol de distancia contiene espacio para 32 símbolos:

• 0–3: distancias 1–4
• 4–5: distancias 5–8, 1 bit extra
• 6–7: distancias 9–16, 2 bits adicionales
• 8–9: distancias 17–32, 3 bits adicionales
• ...
• 26–27: distancias 8,193–16,384, 12 bits adicionales
• 28–29: distancias 16,385–32,768, 13 bits adicionales
• 30–31: no utilizado, reservado e ilegal, pero todavía parte del árbol.

Tenga en cuenta que para los símbolos de distancia del partido 2–29, el número de bits adicionales se puede calcular como ${displaystyle leftlfloor {frac {n}{2}rightrfloor -1}$.

Los dos códigos (el árbol de longitud/literal de 288 símbolos y el árbol de distancia de 32 símbolos) están codificados como códigos Huffman canónicos al proporcionar la longitud en bits del código para cada símbolo. Las longitudes de bit están codificadas en longitud de ejecución para producir una representación lo más compacta posible. Como alternativa a incluir la representación de árbol, el "árbol estático" La opción proporciona árboles Huffman fijos estándar. El tamaño comprimido que usa los árboles estáticos se puede calcular usando las mismas estadísticas (la cantidad de veces que aparece cada símbolo) que se usan para generar los árboles dinámicos, por lo que es fácil para un compresor elegir el que sea más pequeño.

Codificador/compresor

Durante la etapa de compresión, es el codificador el que elige la cantidad de tiempo dedicado a buscar cadenas coincidentes. La implementación de referencia de zlib/gzip permite al usuario seleccionar de una escala variable de nivel de compresión resultante probable frente a la velocidad de codificación. Las opciones van desde 0 (no intente comprimir, solo almacene sin comprimir) a 9 que representa la capacidad máxima de la implementación de referencia en zlib/gzip.

Se han producido otros codificadores Deflate, todos los cuales también producirán un flujo de bits compatible capaz de ser descomprimido por cualquier decodificador Deflate existente. Es probable que diferentes implementaciones produzcan variaciones en el flujo de bits codificado final producido. El enfoque con las versiones que no son zlib de un codificador normalmente ha sido producir un flujo codificado más pequeño y comprimido de manera más eficiente.

Deflate64/Desinflado mejorado

Deflate64, especificado por PKWARE, es una variante patentada de Deflate. Es fundamentalmente el mismo algoritmo. Lo que ha cambiado es el aumento del tamaño del diccionario de 32 KB a 64 KB, una extensión de los códigos de distancia a 16 bits para que puedan abordar un rango de 64 KB y el código de longitud, que se amplía a 16 bits para que puede definir longitudes de tres a 65.538 bytes. Esto lleva a que Deflate64 tenga un tiempo de compresión más largo y potencialmente una relación de compresión ligeramente más alta que Deflate. Varios proyectos gratuitos y/o de código abierto admiten Deflate64, como 7-Zip, mientras que otros, como zlib, no lo hacen, como resultado de la naturaleza propietaria del procedimiento y el aumento de rendimiento muy modesto con respecto a Deflate.

Uso de Deflate en software nuevo

Las implementaciones de Deflate están disponibles gratuitamente en muchos idiomas. Las aplicaciones escritas en C normalmente usan la biblioteca zlib (bajo la licencia zlib permisiva). Las aplicaciones en Borland Pascal y (idiomas compatibles) pueden usar paszlib. Las aplicaciones en C++ pueden aprovechar la biblioteca Deflate mejorada en 7-Zip. Tanto Java como.NET Framework ofrecen soporte listo para usar para Deflate en sus bibliotecas (respectivamente, java.util.zip y System.IO.Compression). Las aplicaciones en Ada pueden usar Zip-Ada (puro) o ZLib-Ada.

Implementaciones de codificador

• PKZIP: la primera implementación, realizada originalmente por Phil Katz como parte de PKZip
• zlib: aplicación de referencia estándar adoptada en muchas aplicaciones debido a su licencia de código abierto y permisivo
• zlib-ng: tenedor más rápido de zlib, usando la intrínseca CPU moderna.
• Crypto++: contiene una implementación de dominio público en C++ para reducir vulnerabilidades de seguridad potenciales. El autor, Wei Dai declara "Este código es menos inteligente, pero espero que sea más comprensible y sostenible [than zlib]".
• 7-Zip: escrito por Igor Pavlov en C++, esta versión está licenciada libremente y consigue una compresión más alta que zlib a expensas del uso de CPU. Tiene la opción de utilizar el formato de almacenamiento DEFLATE64.
• PuTTY 'sshzlib.c': una implementación independiente bajo la licencia MIT de Simon Tatham, tiene plena capacidad de decodificación, pero sólo admite la creación de árboles estáticos
• libflate: parte del Plan 9 de Bell Labs, implementa la compresión deflate
• Hyperbac: utiliza su propia biblioteca de compresión patentada (en C++ y Assembly) con la opción de implementar el formato de almacenamiento DEFLATE64
• Zopfli: Implementación C bajo la Licencia Apache de Google; consigue la compresión más alta a expensas del uso de CPU. ZopfliPNG es una variación de Zopfli para su uso con archivos PNG.
• igzip: un encoder escrito en el lenguaje de montaje x86, publicado por Intel bajo la licencia MIT. 3x más rápido que zlib -1. Útil para comprimir datos genómicos.

AdvanceCOMP utiliza la versión de mayor relación de compresión de Deflate implementada por 7-Zip (u opcionalmente Zopfli en versiones recientes) para permitir la recompresión de archivos gzip, PNG, MNG y ZIP con la posibilidad de tamaños de archivo más pequeños que los que zlib puede lograr en los ajustes máximos.

Codificadores de hardware

• AHA361-PCIX/AHA362-PCIX de Comtech AHA. Comtech produjo una tarjeta PCI-X (PCI-ID: 193f:0001) capaz de comprimir flujos usando Deflate a una velocidad de hasta 3.0 Gbit/s (375 MB/s) para la entrada de datos no comprimidos. Acompañar al controlador del kernel de Linux para el AHA361-PCIX es un "ahagzip" utilitario y personalizado"mod_deflate_aha" capaz de utilizar la compresión de hardware de Apache. El hardware está basado en un Xilinx Virtex FPGA y cuatro ASIC AHA3601 personalizados. Las tablas AHA361/AHA362 se limitan a sólo manejar bloques Huffman estáticos y requieren que se modifique el software para añadir soporte; las tarjetas no pudieron soportar la especificación Deflate completa, lo que significa que sólo podían descifrar su propia salida (una corriente que no contenía ningún Huffman dinámico tipo 2 bloques).
• StorCompress 300/MX3 de Indra Networks. Esta es una gama de PCI (PCI-ID: 17b4:0011) o tarjetas PCI-X que ofrecen entre uno y seis motores de compresión con velocidades de procesamiento reclamadas de hasta 3.6 Gbit/s (450 MB/s). Una versión de las tarjetas están disponibles con la marca separada WebEnhance específicamente diseñado para el uso de servicios web en lugar de utilizar SAN o backup; una revisión PCIe, el MX4E también se produce.
• AHA363-PCIe/AHA364-PCIe/AHA367-PCIe. En 2008, Comtech comenzó a producir dos tarjetas PCIe (PCI-ID: 193f:0363/193f:0364) con un nuevo chip de encoder AHA3610 hardware. El nuevo chip fue diseñado para ser capaz de un 2,5 Gbit/s sostenido. Utilizando dos de estos chips, la junta AHA363-PCIe puede procesar Deflar a una velocidad de hasta 5.0 Gbit/s (625 MB/s) utilizando los dos canales (dos compresión y dos descompresión). La variante AHA364-PCIe es una versión código-sólo de la tarjeta diseñada para equilibradores de carga salientes y en su lugar tiene múltiples conjuntos de registro para permitir 32 independientes virtual canales de compresión alimentando dos motores de compresión físicos. Linux, Microsoft Windows y OpenSolaris Los controladores de dispositivos del núcleo están disponibles para ambas tarjetas nuevas, junto con una biblioteca de sistema de zlib modificada para que las aplicaciones dinámicamente vinculadas puedan utilizar automáticamente el soporte de hardware sin modificaciones internas. La junta AHA367-PCIe (AHA367-PCIe)PCI-ID: 193f:0367) es similar a la AHA363-PCIe pero utiliza cuatro chips AHA3610 para una velocidad de compresión sostenida de 10 Gbit/s (1250 MB/s). A diferencia de la AHA362-PCIX, los motores de descompresión en las tablas AHA363-PCIe y AHA367-PCIe son totalmente deflados.
• Los procesadores Nitrox y Octeon de Cavium, Inc. contienen motores deflados e inflados de hardware de alta velocidad compatibles con ZLIB y GZIP con algunos dispositivos capaces de manejar múltiples flujos de datos simultáneos.
• Aplicación HDL-Deflate GPL FPGA.
• ZipAccel-C de CAST Inc. Este es un núcleo IP de silicona que soporta compresión Deflate, Zlib y Gzip. ZipAccel-C se puede implementar en ASIC o FPGAs, soporta tanto las tablas dinámicas como estaticas Huffman, y puede proporcionar rendimientos superiores a 100Gbps. La empresa ofrece diseños de referencia de tableros aceleradores de compresión/decompresión para Intel FPGA (ZipAccel-RD-INT) y Xilinx FPGAs (ZipAccel-RD-XIL).
• Intel Communications Chipset 89xx Series (Cave Creek) para la serie de procesadores Intel Xeon E5-2600 y E5-2400 (Sandy Bridge-EP/EN) admite compresión y descompresión de hardware utilizando tecnología QuickAssist. Dependiendo del chipset, las tasas de compresión y descompresión de 5Gbit/s, 10Gbit/s, o 20Gbit/s están disponibles.
• Las CPUs IBM z15 incorporan una versión mejorada de la aceleración de hardware de Nest Accelerator Unit (NXU) de las tarjetas de expansión I/O de zEDC Express utilizadas en sistemas z14 para la compresión y descompresión de hardware Deflate según lo especificado por RFC1951.
• A partir de la arquitectura POWER9, IBM agregó soporte de hardware para comprimir y descomprimir Deflate (como se especifica en RFC 1951) al antiguo acelerador de nido críptico (NX) introducido con POWER7+. Este soporte está disponible para programas que funcionan con AIX 7.2 Technology Level 4 Expansion Pack o AIX 7.2 Technology Level 5 Service Pack 2 a través de la biblioteca zlibNX.

Decodificador/descompresor

Inflate es el proceso de decodificación que toma un flujo de bits de Deflate para descomprimirlo y produce correctamente los datos o archivos originales de tamaño completo.

Implementaciones de solo inflación

La intención normal con una implementación alternativa de Inflate es una velocidad de decodificación altamente optimizada o un uso de RAM extremadamente predecible para sistemas integrados con microcontroladores.

• Asamblea General
  • 6502 inflar, escrito por Piotr Fusik en 6502 lenguaje de montaje.
  • SAMflate, escrito por Andrew Collier en lenguaje de montaje Z80 con soporte opcional de paging de memoria para el SAM Coupé, y disponible bajo las licencias BSD/GPL/LGPL/DFSG.
  • gunzip, escrito por Laurens Holst en Z80 lenguaje de montaje para el MSX, licenciado bajo BSD.
  • inflate.asm, una implementación rápida y eficiente en M68000 machine language, escrito por Keir Fraser y publicado en el dominio público.

• C/C++
  • kunzip de Michael Kohn y no relacionado con "KZIP". Viene con código fuente C bajo la licencia GNU LGPL. Se utiliza en el instalador GIMP.
  • puff.c (zlib), una pequeña, no acumulada, aplicación de referencia de un solo fichero incluida en el directorio /contrib/puff de la distribución zlib.
  • tinf escrito por Jørgen Ibsen en ANSI C y viene con licencia de zlib. Añade un código de 2 k.
  • tinfl.c (miniz), dominio público Implementación inflada contenida enteramente en una sola función C.
• PCDEZIP, Bob Flanders y Michael Holmes, publicado en PC Magazine 1994-01-11.
• inflate.cl por John Foderaro. Decodificador de Lisp Común independiente distribuido con licencia GNU LGPL.
• inflate.s7i/gzip.s7i, una aplicación pura-Seed7 de descompresión deflada y gzip, por Thomas Mertes. Hecho disponible bajo la licencia GNU LGPL.
• Pyflate, un puro pitón independiente Deflate (gzip) y bzip2 decodificador por Paul Sladen. Escrito para investigación/prototipado y puesto a disposición bajo las licencias BSD/GPL/LGPL/DFSG.
• deflatelua, una implementación pura-Lua de la descompresión Deflate y gzip/zlib, por David Manura.
• inflar una implementación pura-Javascript de Inflate por Chris Dickinson
• pako: Puerto optimizado de velocidad JavaScript de zlib. Contiene construcción separada con inflado solamente.

Descodificadores de hardware

• GPU Inflado en serie de BitSim. Aplicación de hardware de Inflate. Parte de BitSim BADGE (Bitsim Acelerated Display Graphics Engine) controlador ofrece para sistemas integrados.
• Aplicación HDL-Deflate GPL FPGA.
• ZipAccel-D de CAST Inc. Este es un núcleo IP de silicona que soporta la descompresión de archivos Deflate, Zlib y Gzip. El núcleo IP ZipAccel-D que se puede implementar en ASIC o FPGAs. La empresa ofrece diseños de referencia de tableros aceleradores de compresión/decompresión para Intel FPGA (ZipAccel-RD-INT) y Xilinx FPGAs (ZipAccel-RD-XIL).
• Las CPUs IBM z15 incorporan una versión mejorada de la aceleración de hardware de Nest Accelerator Unit (NXU) de las tarjetas de expansión I/O de zEDC Express utilizadas en sistemas z14 para la compresión y descompresión de hardware Deflate según lo especificado por RFC1951.
• A partir de la arquitectura POWER9, IBM agregó soporte de hardware para comprimir y descomprimir Deflate (como se especifica en RFC 1951) al antiguo acelerador de nido críptico (NX) introducido con POWER7+. Este soporte está disponible para programas que funcionan con AIX 7.2 Technology Level 4 Expansion Pack o AIX 7.2 Technology Level 5 Service Pack 2 a través de la biblioteca zlibNX.