Desinflar

Dentro de los bloques comprimidos, si se detecta una serie duplicada de bytes (una cadena repetida), se inserta una referencia inversa que enlaza con la ubicación anterior de esa cadena idéntica. Una coincidencia codificada con una cadena anterior consta de una longitud de 8 bits (3–258 bytes) y una distancia de 15 bits (1–32 768 bytes) hasta el inicio del duplicado. Se pueden realizar referencias inversas relativas a través de cualquier número de bloques, siempre que la distancia aparezca dentro de los últimos 32 KiB de datos decodificados sin comprimir (denominados ventana deslizante ). 

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

La búsqueda de subcadenas duplicadas en el texto precedente es la parte del algoritmo Deflate que requiere mayor capacidad de cálculo, y es la operación a la que afectan los ajustes del nivel de compresión.

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

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

• 0–255: representan los bytes/símbolos literales 0–255.
• 256: fin del bloque: detenga el procesamiento si es el último bloque; de ​​lo contrario, comience a procesar el siguiente bloque.
• 257–285: combinados con bits adicionales, una longitud de coincidencia de 3–258 bytes.
• 286, 287: no se utilizan, están reservados y son ilegales, pero siguen formando parte del árbol.

Un código de longitud de coincidencia siempre irá seguido de un código de distancia. En función del código de distancia leído, se pueden leer bits adicionales para obtener la distancia final. El árbol de distancias 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 se utilizan, están reservados y son ilegales, pero aún forman parte del árbol.

Para los símbolos de distancia de coincidencia 2–29, el número de bits adicionales se puede calcular como${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor -1}$.

Los dos códigos (el árbol literal de longitud de 288 símbolos y el árbol de distancia de 32 símbolos) se codifican como códigos Huffman canónicos , especificando la longitud de bits del código para cada símbolo. Estas longitudes de bits se codifican mediante codificación de longitud de ejecución para obtener una representación lo más compacta posible. Como alternativa a la inclusión de la representación en árbol, la opción "árbol estático" proporciona árboles Huffman fijos estándar. El tamaño comprimido mediante los árboles estáticos se puede calcular utilizando las mismas estadísticas (el número de veces que aparece cada símbolo) que se emplean para generar los árboles dinámicos, lo que facilita al compresor la elección del tamaño más pequeño.

Deflate64, especificado por PKWARE, es una variante propietaria 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 direccionar un rango de 64  KB, y el código de longitud, que se extiende a 16 bits , para que pueda definir longitudes de tres a 65.538 bytes. ^{[ 9 ]} Esto hace que Deflate64 tenga un tiempo de compresión más largo y, potencialmente, una relación de compresión ligeramente superior a la de Deflate. ^{[ 10 ]} Varios proyectos gratuitos y/o de código abierto admiten Deflate64, como 7-Zip , ^{[ 11 ]} mientras que otros, como zlib , no lo hacen, porque el procedimiento es propietario, ^{[ 12 ]} y el aumento de rendimiento con respecto a Deflate es pequeño. ^{[ 13 ]}

• PKZIP : la primera implementación, realizada originalmente por Phil Katz como parte de PKZip.
• zlib : implementación de referencia estándar adoptada en muchas aplicaciones debido a su licencia de código abierto y permisiva. Consulte Zlib §  Forks para ver bifurcaciones de mayor rendimiento.
• Crypto++ : contiene una implementación de dominio público en C++ destinada a reducir posibles vulnerabilidades de seguridad . El autor, Wei Dai, afirma: " Este código es menos sofisticado, pero esperamos que sea más comprensible y fácil de mantener [que zlib] ".
• 7-Zip : escrito por Igor Pavlov en C++ , esta versión tiene licencia libre y logra una mayor compresión que zlib a costa de un mayor uso de la unidad central de procesamiento (CPU). Incluye la opción de usar el formato de almacenamiento Deflate64.
• PuTTY 'sshzlib.c': una implementación independiente bajo la licencia MIT por Simon Tatham, tiene capacidad de decodificación completa, pero solo admite la creación de árboles estáticos.
• libflate: ^{[ 14 ]} parte del Plan 9 de Bell Labs , implementa la compresión deflate
• Hyperbac : utiliza su propia biblioteca de compresión propietaria (en C++ y lenguaje ensamblador) con una opción para implementar el formato de almacenamiento Deflate64.
• Zopfli : Implementación en C bajo la licencia Apache de Google ; logra una mayor compresión a costa de un mayor uso de la CPU. ZopfliPNG es una variante de Zopfli para usar con archivos PNG .
• igzip: un codificador escrito en lenguaje ensamblador x86 , publicado por Intel bajo la licencia MIT . 3 veces más rápido que zlib-1. Útil para comprimir datos genómicos. ^{[ 15 ]}
• libdeflate: ^{[ 16 ]} una biblioteca para compresión y descompresión rápida basada en Deflate de búfer completo. Libdeflate está altamente optimizada, especialmente en procesadores x86.

AdvanceCOMP utiliza las versiones de Deflate con mayor índice de compresión en 7-Zip, libdeflate y Zopfli para permitir la recompresión de archivos gzip , PNG , gráficos de red de imágenes múltiples (MNG) y ZIP con la posibilidad de obtener tamaños de archivo más pequeños que los que zlib puede lograr con la configuración máxima. ^{[ 17 ]}

• AHA361-PCIX/AHA362-PCIX de Comtech AHA Archivado el 08-12-2006 en Wayback Machine . 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 datos entrantes sin comprimir. Junto con el controlador de dispositivo del kernel de Linux para AHA361-PCIX hay una " " utilidad y " " personalizado capaz de usar la compresión de hardware de Apache . El hardware se basa en una matriz de puertas programables en campo (FPGA) Xilinx Virtex y cuatro circuitos integrados de aplicación específica (ASIC) AHA3601 personalizados. Las placas AHA361/AHA362 están limitadas a manejar solo bloques Huffman estáticos y requieren que se modifique el software para agregar soporte. Las tarjetas no podían admitir la especificación completa de Deflate, lo que significaba que solo podían decodificar de forma fiable su propia salida (una secuencia que no contenía ningún bloque dinámico de tipo 2 de Huffman).ahagzipmod_deflate_aha
• StorCompress 300 / MX3 de Indra Networks . Se trata de una gama de tarjetas PCI (PCI-ID: 17b4:0011) o PCI-X que incorporan entre uno y seis motores de compresión con velocidades de procesamiento declaradas de hasta 3,6  Gbit/s (450  MB/s). Existe una versión de estas tarjetas con la marca independiente WebEnhance, diseñada específicamente para servidores web en lugar de redes de área de almacenamiento (SAN) o copias de seguridad; también se fabrica una revisión PCI Express (PCIe), la MX4E .
• 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 codificador de hardware AHA3610. El nuevo chip fue diseñado para ser capaz de alcanzar una velocidad sostenida de 2,5  Gbit/s. Utilizando dos de estos chips, la tarjeta AHA363-PCIe puede procesar Deflate a una velocidad de hasta 5,0  Gbit/s (625 MB/s) utilizando los dos canales (dos de compresión y dos de descompresión). La variante AHA364-PCIe es una versión de la tarjeta solo de codificación diseñada para balanceadores de carga  salientes y, en su lugar, tiene múltiples conjuntos de registros para permitir 32 canales de compresión virtuales independientes que alimentan dos motores de compresión físicos. Hay controladores de dispositivo del kernel para Linux, Microsoft Windows y OpenSolaris disponibles para ambas tarjetas nuevas, junto con una biblioteca del sistema zlib modificada para que las aplicaciones vinculadas dinámicamente puedan usar automáticamente la compatibilidad del hardware sin modificaciones internas. La placa AHA367-PCIe ( ) es similar a la AHA363-PCIe, pero utiliza cuatro chips AHA3610 para una tasa de compresión sostenida de 10 Gbit/s (1250 MB/s). A diferencia de la AHA362-PCIX, los motores de descompresión de las placas AHA363-PCIe y AHA367-PCIe son totalmente compatibles con el estándar deflate.PCI-ID: 193f:0367  
• Los procesadores Nitrox y Octeon de Cavium, Inc. contienen motores de inflado y desinflado de hardware de alta velocidad compatibles con ZLIB y GZIP, y algunos dispositivos pueden manejar múltiples flujos de datos simultáneos.
• Implementación de HDL-Deflate GPL en FPGA.
• ZipAccel-C de CAST Inc. es un núcleo IP de silicio compatible con compresión Deflate, Zlib y Gzip . ZipAccel-C se puede implementar en ASIC o matrices de puertas programables en campo (FPGA), admite tablas Huffman dinámicas y estáticas, y puede proporcionar velocidades de transmisión superiores a 100  Gbit/s. La empresa ofrece diseños de referencia de placas aceleradoras de compresión/descompresión para FPGA de Intel ( ZipAccel-RD-INT ) y FPGA de Xilinx ( ZipAccel-RD-XIL ).
• El chipset Intel Communications Serie 89xx (Cave Creek) para los procesadores Intel Xeon  E5-2600 y E5-2400 (Sandy Bridge-EP/EN) admite compresión y descompresión por hardware mediante la tecnología QuickAssist. Según el chipset, se ofrecen velocidades de compresión y descompresión de 5 Gbit/s, 10  Gbit/s o 20  Gbit/s. ^{[ 18 ]}
• Las CPU IBM z15 incorporan una versión mejorada de la aceleración de hardware Nest Accelerator Unit (NXU) de las tarjetas de expansión de entrada/salida (E/S) zEDC Express utilizadas en los sistemas z14 para la compresión y descompresión de hardware Deflate según lo especificado por RFC1951. ^{[ 19 ] [ 20 ]}
• A partir de la arquitectura POWER9 , IBM añadió soporte de hardware para comprimir y descomprimir Deflate (según lo especificado por RFC 1951) al núcleo acelerador Nest (NX), anteriormente centrado en criptografía, introducido con POWER7 +. Este soporte está disponible para programas que se ejecutan 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. ^{[ 21 ] [ 22 ]}

La intención habitual con una implementación alternativa de Inflate es lograr una velocidad de decodificación altamente optimizada o un uso extremadamente predecible de la memoria de acceso aleatorio (RAM) para sistemas embebidos de microcontroladores .

• Asamblea
  • 6502 inflate , escrito por Piotr Fusik en lenguaje ensamblador 6502 .
  • SAMflate , escrito por Andrew Collier en lenguaje ensamblador Zilog Z80 con soporte opcional de paginación de memoria para el SAM Coupé , y publicado bajo una combinación de licencias de software : Berkeley Software Distribution ( BSD ), GNU General Public License (GPL), GNU Lesser General Public License (LGPL), Debian Free Software Guidelines (DFSG).
  • gunzip , escrito por Laurens Holst en lenguaje ensamblador Z80 para MSX , con licencia BSD .
  • inflate.asm , una implementación rápida y eficiente en lenguaje máquina Motorola 68000 , escrita por Keir Fraser y publicada en el dominio público .

• C , C++
  • Kunzip, creado por Michael Kohn y sin relación con "KZIP". Incluye código fuente en C bajo la Licencia Pública General Reducida de GNU (LGPL). Se utiliza en el instalador del Programa de Manipulación de Imágenes de GNU ( GIMP ).
  • puff.c ( zlib ), una implementación de referencia pequeña, sin restricciones y de un solo archivo incluida en el directorio /contrib/puff de la distribución zlib.
  • tinf, escrito por Jørgen Ibsen en ANSI C , viene con licencia zlib. Añade aproximadamente 2k de código.
  • tinfl.c ( miniz ), dominio público. Implementación de Inflate contenida completamente en una sola función C.
• PCDEZIP, Bob Flanders y Michael Holmes, publicado en PC Magazine el 11 de enero de 1994.
• inflate.cl de John Foderaro. Decodificador Common Lisp independiente distribuido bajo la Licencia Pública General Reducida de GNU (LGPL).
• pyflate , un decodificador independiente de Deflate ( gzip ) y bzip2 escrito completamente en Python por Paul Sladen. Escrito para investigación/prototipado y publicado bajo una combinación de licencias de software : Berkeley Software Distribution ( BSD ), GNU General Public License (GPL), GNU Lesser General Public License (LGPL) y Debian Free Software Guidelines (DFSG).
• deflatelua , una implementación en Lua puro de Deflate y descompresión gzip /zlib, por David Manura.
• Inflate, una implementación en JavaScript puro de Inflate por Chris Dickinson.
• pako : Versión de zlib optimizada para velocidad en JavaScript. Contiene una compilación separada con solo la función inflate.

• GPU Inflate serial de BitSim. Implementación de hardware de Inflate. Forma parte de la oferta de controladores Bitsim Accelerated Display Graphics Engine (BADGE) para sistemas embebidos.
• Implementación de HDL-Deflate GPL en FPGA.
• ZipAccel-D de CAST Inc. es un núcleo IP de silicio que admite la descompresión de archivos Deflate, Zlib y Gzip . El núcleo IP ZipAccel-D se puede implementar en ASIC o FPGA . La empresa ofrece diseños de referencia de placas aceleradoras de compresión/descompresión para FPGA de Intel ( ZipAccel-RD-INT ) y FPGA de Xilinx ( ZipAccel-RD-XIL ).
• Las CPU IBM z15 incorporan una versión mejorada de la aceleración de hardware Nest Accelerator Unit (NXU) de las tarjetas de expansión de entrada/salida (E/S) zEDC Express utilizadas en los sistemas z14 para la compresión y descompresión de hardware Deflate según lo especificado por RFC1951. ^{[ 19 ] [ 20 ]}
• A partir de la arquitectura POWER9 , IBM añadió soporte de hardware para comprimir y descomprimir Deflate (según lo especificado por RFC 1951) al núcleo acelerador Nest (NX), anteriormente centrado en criptografía, introducido con POWER7 +. Este soporte está disponible para programas que se ejecutan 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. ^{[ 21 ] [ 22 ]}