Deflate
In computing, Deflate (stylized as DEFLATE) is a lossless data compression algorithm that uses a combination of LZ77 and Huffman coding.
≈ 5 min read
Deflate. encyclopegia.org, snapshot enwiki-001377071705. /a/deflate
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computing, Deflate (stylized as DEFLATE) is a lossless data compression algorithm that uses a combination of LZ77 and Huffman coding. It was designed by Phil Katz, for version 2 of his PKZIP archiving tool. Deflate was later specified in Request for Comments (RFC) 1951 (1996).
Katz also designed the original algorithm used to construct Deflate streams. This algorithm received software patent , assigned to PKWare, Inc. As stated in the RFC document, an algorithm producing Deflate files was widely thought to be implementable in a manner not covered by patents.
This led to its widespread use; for example, in the zlib data format, gzip file format, Portable Network Graphics (PNG) image file, and the ZIP file format for which Katz originally designed it. The patent has since expired.
Block structure
Deflate compression takes any sequence of bytes and outputs a sequence of blocks (commonly called Deflate stream). Deflate decompression takes a sequence of blocks and outputs the original sequence of bytes. Endianness is little-endian.
Bit 0 is the least significant bit in a byte. Each block has a 3-bit header with two fields: BFINAL (first bit): 1 if this is the last block in the sequence, else 0 . BTYPE (next two bits): Block type 00 : No compression (sometimes called stored).
Any bits up to the next byte boundary are ignored. The rest of the block consists of 16-bit LEN, 16-bit NLEN (one's complement of LEN), and LEN bytes of uncompressed data, i.e. up to 65,535 ( ) bytes. Useful for incompressible data (e.g. high-entropy, random, or already compressed), adding minimal overhead (i.e. ~5 bytes per block).
01 : A static Huffman compressed block, using a pre-agreed Huffman tree defined in the RFC. 10 : A dynamic Huffman compressed block, complete with the Huffman table supplied. 11 : Reserved (error).
Most compressible data will end up being encoded using method 10 , the dynamic Huffman encoding, which produces an optimized Huffman tree customized for each block of data individually. Instructions to generate the necessary Huffman tree immediately follow the block header.
The static Huffman option is used for short messages, where the fixed saving gained by omitting the tree outweighs the percentage compression loss due to using a non-optimal (thus, not technically Huffman) code. Compression is achieved through two steps: Matching and replacing duplicate strings with pointers Replacing symbols with new, weighted symbols based on use frequency AHA363-PCIe/AHA364-PCIe/AHA367-PCIe.
In 2008, Comtech started producing two PCIe cards ( PCI-ID: 193f:0363 / 193f:0364 ) with a new hardware AHA3610 encoder chip. The new chip was designed to be capable of a sustained 2.5 Gbit/s. Using two of these chips, the AHA363-PCIe board can process Deflate at a rate of up to 5.0 Gbit/s (625 MB/s) using the two channels (two compression and two decompression).
The AHA364-PCIe variant is an encode-only version of the card designed for out-going load balancers and instead has multiple register sets to allow 32 independent virtual compression channels feeding two physical compression engines. Linux, Microsoft Windows, and OpenSolaris kernel device drivers are available for both of the new cards, along with a modified zlib system library so that dynamically linked applications can automatically use the hardware support without internal modification.
The AHA367-PCIe board ( PCI-ID: 193f:0367 ) is similar to the AHA363-PCIe but uses four AHA3610 chips for a sustained compression rate of 10 Gbit/s (1250 MB/s). Unlike the AHA362-PCIX, the decompression engines on the AHA363-PCIe and AHA367-PCIe boards are fully deflate compliant. Nitrox and Octeon processors from Cavium, Inc. contain high-speed hardware deflate and inflate engines compatible with both ZLIB and GZIP with some devices able to handle multiple simultaneous data streams.
HDL-Deflate GPL FPGA implementation. ZipAccel-C from CAST Inc. This is a Silicon IP core supporting Deflate, Zlib and Gzip compression.
ZipAccel-C can be implemented in ASIC or field-programmable gate array (FPGAs), supports both Dynamic and Static Huffman tables, and can provide throughputs in excess of 100 Gbit/s. The company offers compression/decompression accelerator board reference designs for Intel FPGA (ZipAccel-RD-INT) and Xilinx FPGAs (ZipAccel-RD-XIL). Intel Communications Chipset 89xx Series (Cave Creek) for the Intel Xeon E5-2600 and E5-2400 Processor Series (Sandy Bridge-EP/EN) supports hardware compression and decompression using QuickAssist Technology.
Depending on the chipset, compression and decompression rates of 5 Gbit/s, 10 Gbit/s, or 20 Gbit/s are available. IBM z15 CPUs incorporate an improved version of the Nest Accelerator Unit (NXU) hardware acceleration from the zEDC Express input/output (I/O) expansion cards used in z14 systems for hardware Deflate compression and decompression as specified by RFC1951.
Starting with the POWER9 architecture, IBM added hardware support for compressing and decompressing Deflate (as specified by RFC 1951) to the formerly crypto-centric Nest accelerator (NX) core introduced with POWER7+. This support is available to programs running with AIX 7.2 Technology Level 4 Expansion Pack or AIX 7.2 Technology Level 5 Service Pack 2 through the zlibNX library.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1377071705 under CC BY-SA 4.0; modifications have been made.