X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=algorithm.doc;h=c8c3a92190ff0e0af0d5bb354d2c4ffe153b5be7;hb=dc84183747ce1703eb99685b5dbde1f65a143c06;hp=a62800c16d2bb75f622bd4313d3dc8f44c0c7ab2;hpb=a2016c1de6e4884f6c8ed5cc498f3bf821c25ca4;p=debian%2Fgzip diff --git a/algorithm.doc b/algorithm.doc index a62800c..c8c3a92 100644 --- a/algorithm.doc +++ b/algorithm.doc @@ -1,7 +1,7 @@ 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 @@ -57,6 +57,10 @@ but saves time since there are both fewer insertions and fewer searches. 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 @@ -68,12 +72,11 @@ following structure: 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 @@ -83,7 +86,7 @@ following structure: ? 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 @@ -128,7 +131,7 @@ compression format, regardless of the actual size of the compressed 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 @@ -145,20 +148,18 @@ a few bytes for the gzip file header, plus 5 bytes every 32K block, 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, . -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 .