DEFLATE
Encyclopedia
Deflate is a lossless data compression
algorithm
that uses a combination of the LZ77
algorithm and Huffman coding
. It was originally defined by Phil Katz
for version 2 of his PKZIP
archiving tool and was later specified in RFC 1951.
The original algorithm as designed by Katz was patented as and assigned to PKWARE. Deflate is widely thought to be free of any subsisting patent
s and was so at a time before the patent on LZW (which is used in the GIF file format) expired. This has led to its use in gzip
compressed files and PNG image files in addition to the ZIP
file format for which Katz originally designed it.
header:
Most blocks will end up being encoded using method
Compression is achieved through two steps
is inserted, linking to the previous location of that identical string instead. An encoded match to an earlier string consists of a length (3–258 bytes) and a distance (1–32,768 bytes). Relative back-references can be made across any number of blocks, as long as the distance appears within the last 32 kB of uncompressed data decoded (termed the sliding window).
which creates an unprefixed tree of non-overlapping intervals, where the length of each sequence is inversely proportional to the probability of that symbol needing to be encoded. The more likely a symbol has to be encoded, the shorter its bit-sequence will be.
A tree is created which contains space for 288 symbols:
A match length code will always be followed by a distance code. Based on the distance code read, further "extra" bits may be read in order to produce the final distance. The distance tree contains space for 32 symbols:
Note that for the match distance symbols 2–29, the number of extra bits can be calculated as
.
Other Deflate encoders have been produced, all of which will also produce a compatible bitstream
capable of being decompressed by any existing Deflate decoder. Differing implementations will likely produce variations on the final encoded bit-stream produced. The focus with non-zlib versions of an encoder has normally been to produce a more efficiently compressed and smaller encoded stream.
, while others, such as zlib
, do not, as a result of the proprietary nature of the procedure and the very modest performance increase over Deflate.
dialects of Pascal can use paszlib, a C++
library is included as part of 7-Zip
/AdvanceCOMP
. Java includes support as part of the standard library (in java.util.zip). Microsoft .NET Framework 2.0 base class library supports it in the System.IO.Compression namespace.
AdvanceCOMP
uses the higher compression ratio version of Deflate as implemented by 7-Zip to enable recompression of gzip
, PNG, MNG and ZIP files with the possibility of achieving smaller file sizes than zlib is able to at maximum settings. An even more effective (but also more user-input-demanding and CPU intensive) Deflate encoder is employed inside Ken Silverman
's KZIP and PNGOUT
utilities.
Lossless data compression
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be reconstructed, in exchange...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that uses a combination of the LZ77
LZ77 and LZ78
LZ77 and LZ78 are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively. These two algorithms form the basis for most of the LZ variations including LZW, LZSS, LZMA and...
algorithm and Huffman coding
Huffman coding
In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol where the variable-length code table has been derived in a particular way based on...
. It was originally defined by Phil Katz
Phil Katz
Phillip Walter Katz was a computer programmer best known as the co-creator of the zip file format for data compression, and the author of PKZIP, a program for creating zip files which ran under DOS.- Career :...
for version 2 of his PKZIP
PKZIP
PKZIP is an archiving tool originally written by Phil Katz and marketed by his company PKWARE, Inc. The common "PK" prefix used in both PKZIP and PKWARE stands for "Phil Katz".-History:...
archiving tool and was later specified in RFC 1951.
The original algorithm as designed by Katz was patented as and assigned to PKWARE. Deflate is widely thought to be free of any subsisting patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
s and was so at a time before the patent on LZW (which is used in the GIF file format) expired. This has led to its use in gzip
Gzip
Gzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
compressed files and PNG image files in addition to the ZIP
ZIP (file format)
Zip is a file format used for data compression and archiving. A zip file contains one or more files that have been compressed, to reduce file size, or stored as is...
file format for which Katz originally designed it.
Stream format
A Deflate stream consists of a series of blocks. Each block is preceded by a 3-bitBit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
header:
- 1 bit: Last-block-in-stream marker:
-
1: this is the last block in the stream. -
0: there are more blocks to process after this one.
-
- 2 bits: Encoding method used for this block type:
-
00: a stored/raw/literal section, between 0 and 65,535 bytes in length. -
01: a static Huffman compressed block, using a pre-agreed Huffman tree. -
10: a compressed block complete with the Huffman table supplied. -
11: reserved, don't use.
-
Most blocks will end up being encoded using method
10, the dynamic Huffman encoding, which produces an optimised Huffman tree customised for each block of data individually. Instructions to generate the necessary Huffman tree immediately follow the block header.Compression is achieved through two steps
- The matching and replacement of duplicate strings with pointers.
- Replacing symbols with new, weighted symbols based on frequency of use.
Duplicate string elimination
Within compressed blocks, if a duplicate series of bytes is spotted (a repeated string), then a back-referenceReference (computer science)
In computer science, a reference is a value that enables a program to indirectly access a particular data item, such as a variable or a record, in the computer's memory or in some other storage device. The reference is said to refer to the data item, and accessing those data is called...
is inserted, linking to the previous location of that identical string instead. An encoded match to an earlier string consists of a length (3–258 bytes) and a distance (1–32,768 bytes). Relative back-references can be made across any number of blocks, as long as the distance appears within the last 32 kB of uncompressed data decoded (termed the sliding window).
Bit reduction
The second compression stage consists of replacing commonly used symbols with shorter representations and less commonly used symbols with longer representations. The method used is Huffman codingHuffman coding
In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol where the variable-length code table has been derived in a particular way based on...
which creates an unprefixed tree of non-overlapping intervals, where the length of each sequence is inversely proportional to the probability of that symbol needing to be encoded. The more likely a symbol has to be encoded, the shorter its bit-sequence will be.
A tree is created which contains space for 288 symbols:
- 0–255: represent the literal bytes/symbols 0–255.
- 256: end of block – stop processing if last block, otherwise start processing next block.
- 257–285: combined with extra-bits, a match length of 3–258 bytes.
- 286, 287: not used, reserved and illegal but still part of the tree.
A match length code will always be followed by a distance code. Based on the distance code read, further "extra" bits may be read in order to produce the final distance. The distance tree contains space for 32 symbols:
- 0–3: distances 1–4
- 4–5: distances 5–8, 1 extra bit
- 6–7: distances 9–16, 2 extra bits
- 8–9: distances 17–32, 3 extra bits
- ...
- 26–27: distances 8,193–16,384, 12 extra bits
- 28–29: distances 16,385–32,768, 13 extra bits
- 30–31: not used, reserved and illegal but still part of the tree.
Note that for the match distance symbols 2–29, the number of extra bits can be calculated as
.Encoder/compressor
During the compression stage, it is the encoder that chooses the amount of time spent looking for matching strings. The zlib/gzip reference implementation allows the user to select from a sliding scale of likely resulting compression-level vs. speed of encoding. Options range from-0 (do not attempt compression, just store uncompressed) to -9 representing the maximum capability of the reference implementation in zlib/gzip.Other Deflate encoders have been produced, all of which will also produce a compatible bitstream
Bitstream
A bitstream or bit stream is a time series of bits.A bytestream is a series of bytes, typically of 8 bits each, and can be regarded as a special case of a bitstream....
capable of being decompressed by any existing Deflate decoder. Differing implementations will likely produce variations on the final encoded bit-stream produced. The focus with non-zlib versions of an encoder has normally been to produce a more efficiently compressed and smaller encoded stream.
Deflate64/Enhanced Deflate
Deflate64, specified by PKWare, is a proprietary variant of the Deflate procedure. The fundamental mechanisms remain the same. What has changed is the increase in dictionary size from 32kB to 64kB, an addition of 14 bits to the distance codes so that they may address a range of 64kB, and the length code has been extended by 16 bits so that it may define lengths of 3 to 65538 bytes. This leads to Deflate64 having a slightly higher compression ratio and a slightly lower compression time than Deflate. Several free and/or open source projects support Deflate64, such as 7-Zip7-Zip
7-Zip is an open source file archiver. 7-Zip operates with the 7z archive format, but can read and write several other archive formats. The program can be used from a command line interface, graphical user interface, or with Microsoft Windows shell integration. 7-Zip began in 1999 and is actively...
, while others, such as zlib
Zlib
zlib is a software library used for data compression. zlib was written by Jean-Loup Gailly and Mark Adler and is an abstraction of the DEFLATE compression algorithm used in their gzip file compression program. Zlib is also a crucial component of many software platforms including Linux, Mac OS X,...
, do not, as a result of the proprietary nature of the procedure and the very modest performance increase over Deflate.
Using Deflate in new software
Implementations of Deflate are freely available in many languages. C programs typically use the zlib library (under the old BSD license without advertising clause). Programs written using the BorlandBorland
Borland Software Corporation is a software company first headquartered in Scotts Valley, California, Cupertino, California and finally Austin, Texas. It is now a Micro Focus subsidiary. It was founded in 1983 by Niels Jensen, Ole Henriksen, Mogens Glad and Philippe Kahn.-The 1980s:...
dialects of Pascal can use paszlib, a C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
library is included as part of 7-Zip
7-Zip
7-Zip is an open source file archiver. 7-Zip operates with the 7z archive format, but can read and write several other archive formats. The program can be used from a command line interface, graphical user interface, or with Microsoft Windows shell integration. 7-Zip began in 1999 and is actively...
/AdvanceCOMP
AdvanceCOMP
AdvanceCOMP is a set of cross-platform command line data compression tools. The utilities allow modifying an already-compressed file, with the intent of reducing the file-size by optimising the compressed representation...
. Java includes support as part of the standard library (in java.util.zip). Microsoft .NET Framework 2.0 base class library supports it in the System.IO.Compression namespace.
Encoder implementations
- PKZIPPKZIPPKZIP is an archiving tool originally written by Phil Katz and marketed by his company PKWARE, Inc. The common "PK" prefix used in both PKZIP and PKWARE stands for "Phil Katz".-History:...
: the first implementation, originally done by Phil KatzPhil KatzPhillip Walter Katz was a computer programmer best known as the co-creator of the zip file format for data compression, and the author of PKZIP, a program for creating zip files which ran under DOS.- Career :...
as part of PKZipPKZIPPKZIP is an archiving tool originally written by Phil Katz and marketed by his company PKWARE, Inc. The common "PK" prefix used in both PKZIP and PKWARE stands for "Phil Katz".-History:...
. - zlibZlibzlib is a software library used for data compression. zlib was written by Jean-Loup Gailly and Mark Adler and is an abstraction of the DEFLATE compression algorithm used in their gzip file compression program. Zlib is also a crucial component of many software platforms including Linux, Mac OS X,...
/gzipGzipGzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
: standard reference implementation used in a huge amount of software, owing to public availability of the source code and a license allowing inclusion into other software.- jzlib: Rewrite/re-implementation/port of the
zlibencoder into pure JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and distributed under a BSD license. (Fully featured replacement forjava.util.zip). - PasZLIB: Translation/port of the
zlibcode into PascalPascal (programming language)Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
source code by Jacques Nomssi-Nzali. - gziplite: Minimalist rework of
gzip/gunzipwith minimal memory requirement, also supporting on-the-fly data compression/decompression (no need to bufferize all input) and input/output to/from memory.
- jzlib: Rewrite/re-implementation/port of the
- KZIP/PNGOUTPNGOUTPNGOUT is a freeware command line optimizer for PNG images written by Ken Silverman. The compression is lossless, meaning that the resulting image will have exactly the same appearance as the source image...
: an encoder by the game-programmer Ken SilvermanKen SilvermanKen Silverman is a game programmer, best known for writing the Build engine used in Duke Nukem 3D, Shadow Warrior, Blood, and more than a dozen other games in the mid- to late-1990s...
using "an exhaustive search of all patterns" and "[an] advanced block splitter". - PuZip: designed for Commodore 64Commodore 64The Commodore 64 is an 8-bit home computer introduced by Commodore International in January 1982.Volume production started in the spring of 1982, with machines being released on to the market in August at a price of US$595...
/C128Commodore 128The Commodore 128 home/personal computer was the last 8-bit machine commercially released by Commodore Business Machines...
computers. PuZip is limited to an 8kB LZ77 window size, with only the store (type00) and fixed Huffman (type01) methods. - BigSpeed Deflate: "Tiny in-memory compression library" available as a MS Windows DLL limited to 32kB blocks at a time and three compression settings.
- BJWFlate & DeflOpt/DeflOpt: Ben Jos Walbeehm's utilities "designed to attempt to squeeze every possible byte out of the files it compresses". Note that the author has stopped development on BJWFlate (but not DeflOpt) in March 2004.
- Crypto++Crypto++Crypto++ is a free and open source C++ class library of cryptographic algorithms and schemes written by Wei Dai. Crypto++ has been widely used in academia, student projects, open source and non-commercial projects, as well as businesses...
: contains a public domain implementation in C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
aimed mainly at reducing potential security vulnerabilitiesVulnerability (computing)In computer security, a vulnerability is a weakness which allows an attacker to reduce a system's information assurance.Vulnerability is the intersection of three elements: a system susceptibility or flaw, attacker access to the flaw, and attacker capability to exploit the flaw...
. The author, Wei Dai states "This code is less clever, but hopefully more understandable and maintainable [than zlib]". - DeflateStream - an implementation of a stream that performs DEFLATE compression, it is packaged with the Base Class Library included with the .NET Framework.
- ParallelDeflateOutputStream - an open source stream that implements a parallel (multi-thread) deflating stream, for use in .NET programs.
- 7-Zip7-Zip7-Zip is an open source file archiver. 7-Zip operates with the 7z archive format, but can read and write several other archive formats. The program can be used from a command line interface, graphical user interface, or with Microsoft Windows shell integration. 7-Zip began in 1999 and is actively...
/AdvanceCOMPAdvanceCOMPAdvanceCOMP is a set of cross-platform command line data compression tools. The utilities allow modifying an already-compressed file, with the intent of reducing the file-size by optimising the compressed representation...
: written by Igor Pavlov in C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, this version is freely licensed and tends to achieve higher compression than zlib at the expense of CPU usage. Has an option to use the DEFLATE64 storage format.
- PuTTYPuTTYPuTTY is a free and open source terminal emulator application which can act as a client for the SSH, Telnet, rlogin, and raw TCP computing protocols and as a serial console client...
`sshzlib.c`: a standalone implementation, capable of full decode, but static tree only creation, by Simon Tatham. MIT licensedMIT LicenseThe MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms...
. - Halibut `deflate.c`: a standalone implementation capable of full decode. Forked from PuTTY's `sshzlib.c`, but extended to write dynamic Huffman trees and provides Adler-32 and CRC-32 checksum support.
- Plan 9 from Bell LabsPlan 9 from Bell LabsPlan 9 from Bell Labs is a distributed operating system. It was developed primarily for research purposes as the successor to Unix by the Computing Sciences Research Center at Bell Labs between the mid-1980s and 2002...
operating system's libflate implements deflate compression. - Hyperbac : uses its own proprietary lossless compression library (written in C++ and Assembly) with an option to implement the DEFLATE64 storage format.
AdvanceCOMP
AdvanceCOMP
AdvanceCOMP is a set of cross-platform command line data compression tools. The utilities allow modifying an already-compressed file, with the intent of reducing the file-size by optimising the compressed representation...
uses the higher compression ratio version of Deflate as implemented by 7-Zip to enable recompression of gzip
Gzip
Gzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
, PNG, MNG and ZIP files with the possibility of achieving smaller file sizes than zlib is able to at maximum settings. An even more effective (but also more user-input-demanding and CPU intensive) Deflate encoder is employed inside Ken Silverman
Ken Silverman
Ken Silverman is a game programmer, best known for writing the Build engine used in Duke Nukem 3D, Shadow Warrior, Blood, and more than a dozen other games in the mid- to late-1990s...
's KZIP and PNGOUT
PNGOUT
PNGOUT is a freeware command line optimizer for PNG images written by Ken Silverman. The compression is lossless, meaning that the resulting image will have exactly the same appearance as the source image...
utilities.
Hardware encoders
- AHA361-PCIX/AHA362-PCIX from Comtech AHA. Comtech produced a PCI-XPCI-XPCI-X, short for PCI-eXtended, is a computer bus and expansion card standard that enhances the 32-bit PCI Local Bus for higher bandwidth demanded by servers. It is a double-wide version of PCI, running at up to four times the clock speed, but is otherwise similar in electrical implementation and...
card (PCI-ID:193f:0001) capable of compressing streams using Deflate at a rate of up to 3.0 Gbit/s (375 MB/s) for incoming uncompressed data. Accompanying the Linux kernel driverDevice driverIn computing, a device driver or software driver is a computer program allowing higher-level computer programs to interact with a hardware device....
for the AHA361-PCIX is an 'ahagzip' utility and customised 'mod_deflate_aha' capable of using the hardware compression from ApacheApache HTTP ServerThe Apache HTTP Server, commonly referred to as Apache , is web server software notable for playing a key role in the initial growth of the World Wide Web. In 2009 it became the first web server software to surpass the 100 million website milestone...
. The hardware is based on a XilinxXilinxXilinx, Inc. is a supplier of programmable logic devices. It is known for inventing the field programmable gate array and as the first semiconductor company with a fabless manufacturing model....
VirtexVirtex* Virtex , a series of FPGAs produced by Xilinx* Virtex, a series of comic books published by Oktomica Comics* Virtex L, otherwise known as sodium dithionite...
FPGA and four custom AHA3601 ASICsApplication-specific integrated circuitAn application-specific integrated circuit is an integrated circuit customized for a particular use, rather than intended for general-purpose use. For example, a chip designed solely to run a cell phone is an ASIC...
. The AHA361/AHA362 boards are limited to only handling static Huffman blocks and require software to be modified to add support—the cards were not able to support the full Deflate specification meaning they could only reliably decode their own output (a stream that did not contain any dynamic Huffman type 2 blocks). - StorCompress 300/MX3 from Indra Networks. This is a range of PCI (PCI-ID:
17b4:0011) or PCI-X cards featuring between one and six compression engines with claimed processing speeds of up to 3.6 Gbit/s (450 MB/s). A version of the cards are available with the separate brand WebEnhance specifically designed for web-serving use rather than SANStorage area networkA storage area network is a dedicated network that provides access to consolidated, block level data storage. SANs are primarily used to make storage devices, such as disk arrays, tape libraries, and optical jukeboxes, accessible to servers so that the devices appear like locally attached devices...
or backup use; a PCIe revision, the MX4E is also produced. - 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.5Gbit/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 WindowsMicrosoft WindowsMicrosoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
, and OpenSolarisOpenSolarisOpenSolaris was an open source computer operating system based on Solaris created by Sun Microsystems. It was also the name of the project initiated by Sun to build a developer and user community around the software...
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.
Decoder/decompressor
Inflate is the decoding process that takes a Deflate bit stream for decompression and correctly produces the original full-size data or file.Inflate-only implementations
The normal intent with an alternative Inflate implementation is highly optimised decoding speed, or extremely predictable RAM usage for micro-controller embedded systems.- AssemblyAssembly languageAn assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
- 6502 inflate, written by Piotr Fusik in 6502MOS Technology 6502The MOS Technology 6502 is an 8-bit microprocessor that was designed by Chuck Peddle and Bill Mensch for MOS Technology in 1975. When it was introduced, it was the least expensive full-featured microprocessor on the market by a considerable margin, costing less than one-sixth the price of...
assembly language. - Elektronika MK-90 inflate, the above 6502 program ported by Piotr Piatek to the PDP-11 architecturePDP-11 architectureThe PDP-11 architecture is an instruction set architecture developed by Digital Equipment Corporation . It is implemented by central processing units and microprocessors used in minicomputers of the same name. Additional information is found in DEC's PDP-11 Processor Handbook .-Memory...
. - SAMflate, written by Andrew Collier in Z80 assembly language with optional memory paging support for the SAM CoupéSAM CoupéThe SAM Coupé is an 8-bit British home computer that was first released in late 1989. It is commonly considered a clone of the Sinclair ZX Spectrum computer, since it features a compatible screen mode and emulated compatibility, and it was marketed as a logical upgrade from the Spectrum...
, and made available under the BSD/GPLGNU General Public LicenseThe GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
/LGPLGNU Lesser General Public LicenseThe GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
/DFSGDebian Free Software GuidelinesThe Debian Free Software Guidelines is a set of guidelines that the Debian Project uses to determine whether a software license is a free software license, which in turn is used to determine whether a piece of software can be included in Debian...
licenses.
- 6502 inflate, written by Piotr Fusik in 6502
- CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
/C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
- kunzip by Michael Kohn and unrelated to "KZIP". Comes with CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
source-code under the GNU LGPL license. Used in the GIMPGIMPGIMP is a free software raster graphics editor. It is primarily employed as an image retouching and editing tool and is freely available in versions tailored for most popular operating systems including Microsoft Windows, Apple Mac OS X, and Linux.In addition to detailed image retouching and...
installer. - lodepng by Lode Vandevenne. A BSD-licensed single file PNG file reader with built-in C++ Inflate implementation and no external dependencies.
- puff.c (zlibZlibzlib is a software library used for data compression. zlib was written by Jean-Loup Gailly and Mark Adler and is an abstraction of the DEFLATE compression algorithm used in their gzip file compression program. Zlib is also a crucial component of many software platforms including Linux, Mac OS X,...
), a small, unencumbered, single-file reference implementation included in the /contrib/puff directory of the zlib distribution. - tinf written by Jørgen Ibsen in ANSI C and comes with zlib license. Adds about 2k code.
- kunzip by Michael Kohn and unrelated to "KZIP". Comes with C
-
PCDEZIP, Bob Flanders and Michael Holmes, published in PC Magazine 1994–01–11. - inflate.cl by John Foderaro. Self-standing Common LispCommon LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
decoder distributed with a GNU LGPL license. - pyflate, a pure-PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
stand-alone Deflate (gzipGzipGzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
) and bzip2Bzip2bzip2 is a free and open source implementation of the Burrows–Wheeler algorithm. It is developed and maintained by Julian Seward. Seward made the first public release of bzip2, version 0.15, in July 1996.-Compression efficiency:...
decoder by Paul Sladen. Written for research/prototyping and made available under the BSD/GPLGNU General Public LicenseThe GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
/LGPLGNU Lesser General Public LicenseThe GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
/DFSGDebian Free Software GuidelinesThe Debian Free Software Guidelines is a set of guidelines that the Debian Project uses to determine whether a software license is a free software license, which in turn is used to determine whether a piece of software can be included in Debian...
licenses. - deflatelua, a pure-Lua implementation of Deflate and gzipGzipGzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
/zlib decompression, by David Manura.
Hardware decoders
- Serial Inflate GPU from BitSim. Hardware implementation of Inflate. Part of BitSim's BADGE (Bitsim Accelerated Display Graphics Engine) controller offering for embedded systems.
See also
- List of archive formats
- List of file archivers
- Comparison of file archiversComparison of file archiversThe following tables compare general and technical information for a number of file archivers. Please see the individual products' articles for further information. They are neither all-inclusive nor are some entries necessarily up to date...
External links
- PKWARE's
appnote.txt, .ZIP File Format Specification; Section 10, X. Deflating - Method 8. - RFC 1951 – Deflate Compressed Data Format Specification version 1.3
- zlib Home Page
- An Explanation of the Deflate Algorithm by Antaeus Feldspar.
- Extended Application of Suffix Trees to Data Compression An excellent algorithm to implement Deflate by Jesper Larsson