1. Algorithm
-The deflation algorithm used by zip and gzip is a variation of LZ77
-(Lempel-Ziv 1977, see reference below). It finds duplicated strings in
+The deflation algorithm used by zip and gzip is a variation of
+Lempel-Ziv 1977 [LZ77]. It finds duplicated strings in
the input data. The second occurrence of a string is replaced by a
pointer to the previous string, in the form of a pair (distance,
length). Distances are limited to 32K bytes, and lengths are limited
2. gzip file format
+The gzip file format was standardized in Internet RFC 1952 [RFC1952].
+This section briefly describes the format and comments on some
+implementation details.
+
The pkzip format imposes a lot of overhead in various headers, which
are useful for an archiver but not necessary when only one file is
compressed. gzip uses a much simpler structure. Numbers are in little
1 byte compression method (0..7 reserved, 8 = deflate)
1 byte flags
bit 0 set: file probably ascii text
- bit 1 set: continuation of multi-part gzip file
+ bit 1 set: header CRC-16 present
bit 2 set: extra field present
bit 3 set: original file name present
bit 4 set: file comment present
- bit 5 set: file is encrypted
- bit 6,7: reserved
+ bit 5,6,7: reserved
4 bytes file modification time in Unix format
1 byte extra flags (depend on compression method)
1 byte operating system on which compression took place
? bytes optional extra field
? bytes optional original file name, zero terminated
? bytes optional file comment, zero terminated
-12 bytes optional encryption header
+2 bytes optional 16-bit header CRC
? bytes compressed data
4 bytes crc32
4 bytes uncompressed input size modulo 2^32
data. If the compressed data cannot fit in one file (in particular for
diskettes), each part starts with a header as described above, but
only the last part has the crc32 and uncompressed size. A decompressor
-may prompt for additional data for multipart compressed files. It is
+may prompt for additional data for multi-part compressed files. It is
desirable but not mandatory that multiple parts be extractable
independently so that partial data can be recovered if one of the
parts is damaged. This is possible only if no compression state is
or an expansion ratio of 0.015% for large files. Note that the actual
number of used disk blocks almost never increases.
-The encryption is that of zip 1.9. For the encryption check, the
-last byte of the decoded encryption header must be zero. The time
-stamp of an encrypted file might be set to zero to avoid giving a clue
-about the construction of the random header.
-
Jean-loup Gailly
gzip@gnu.org
References:
[LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
-Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3,
-pp. 337-343.
+Compression", IEEE Transactions on Information Theory, Vol. 23, No. 3,
+May 1977, pp. 337-343.
+
+[RFC1952] Deutsch P., "GZIP file format specification version 4.3",
+Internet RFC 1952, May 1996, <http://www.ietf.org/rfc/rfc1952.txt>.
-APPNOTE.TXT documentation file in PKZIP 1.93a. It is available by
-ftp in ftp.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59]
-Use "unzip pkz193a.exe APPNOTE.TXT" to extract (note: unzip, not gunzip).
+APPNOTE.TXT documentation file in PKZIP 1.93a (October 1991). This
+version no longer seems to be available online; the latest version is
+in <http://www.pkware.com/documents/casestudies/APPNOTE.TXT>.