idnits 2.17.1 draft-deutsch-gzip-spec-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 11 longer pages, the longest (page 2) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. == There are 2 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (21 Mar 1996) is 10235 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '256' is mentioned on line 542, but not defined == Unused Reference: '1' is defined on line 431, but no explicit reference was found in the text == Unused Reference: '2' is defined on line 437, but no explicit reference was found in the text == Unused Reference: '3' is defined on line 439, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 441, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 444, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 447, but no explicit reference was found in the text == Unused Reference: '7' is defined on line 450, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 453, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' Summary: 8 errors (**), 0 flaws (~~), 12 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT L. Peter Deutsch 2 GZIP 4.3 Aladdin Enterprises 3 Expires: 26 Sep 1996 21 Mar 1996 5 GZIP file format specification version 4.3 7 File draft-deutsch-gzip-spec-03.txt 9 Status of this Memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six months 17 and may be updated, replaced, or obsoleted by other documents at any 18 time. It is inappropriate to use Internet- Drafts as reference 19 material or to cite them other than as ``work in progress.'' 21 To learn the current status of any Internet-Draft, please check the 22 ``1id-abstracts.txt'' listing contained in the Internet- Drafts 23 Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 24 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 25 ftp.isi.edu (US West Coast). 27 Distribution of this memo is unlimited. 29 A pointer to the latest version of this and related documentation in 30 HTML format can be found at the URL 31 . 33 Notices 35 Copyright (c) 1996 L. Peter Deutsch 37 Permission is granted to copy and distribute this document for any 38 purpose and without charge, including translations into other 39 languages and incorporation into compilations, provided that the 40 copyright notice and this notice are preserved, and that any 41 substantive changes or deletions from the original are clearly 42 marked. 44 Deutsch [Page 1] 45 Abstract 47 This specification defines a lossless compressed data format that is 48 compatible with the widely used GZIP utility. The format includes a 49 cyclic redundancy check value for detecting data corruption. The 50 format presently uses the DEFLATE method of compression but can be 51 easily extended to use other compression methods. The format can be 52 implemented readily in a manner not covered by patents. 54 Table of Contents 56 1. Introduction ................................................... 2 57 1.1. Purpose ................................................... 2 58 1.2. Intended audience ......................................... 3 59 1.3. Scope ..................................................... 3 60 1.4. Compliance ................................................ 3 61 1.5. Definitions of terms and conventions used ................. 3 62 1.6. Changes from previous versions ............................ 3 63 2. Detailed specification ......................................... 4 64 2.1. Overall conventions ....................................... 4 65 2.2. File format ............................................... 5 66 2.3. Member format ............................................. 5 67 2.3.1. Member header and trailer ........................... 5 68 2.3.1.1. Extra field ................................... 8 69 2.3.1.2. Compliance .................................... 9 70 3. References .................................................. 9 71 4. Security considerations .................................... 10 72 5. Acknowledgements ........................................... 10 73 6. Author's address ........................................... 10 74 7. Appendix: Jean-loup Gailly's gzip utility .................. 11 75 8. Appendix: Sample CRC Code .................................. 11 77 1. Introduction 79 1.1. Purpose 81 The purpose of this specification is to define a lossless 82 compressed data format that: 84 * Is independent of CPU type, operating system, file system, 85 and character set, and hence can be used for interchange; 86 * Can compress or decompress a data stream (as opposed to a 87 randomly accessible file) to produce another data stream, 88 using only an a priori bounded amount of intermediate 89 storage, and hence can be used in data communications or 90 similar structures such as Unix filters; 91 * Compresses data with efficiency comparable to the best 92 currently available general-purpose compression methods, and 93 in particular considerably better than the 'compress' 94 program; 95 * Can be implemented readily in a manner not covered by 96 patents, and hence can be practiced freely; 98 Deutsch [Page 2] 99 * Is compatible with the file format produced by the current 100 widely used gzip utility, in that conforming decompressors 101 will be able to read data produced by the existing gzip 102 compressor. 104 The data format defined by this specification does not attempt to: 106 * Provide random access to compressed data; 107 * Compress specialized data (e.g., raster graphics) as well as 108 the best currently available specialized algorithms. 110 1.2. Intended audience 112 This specification is intended for use by implementors of software 113 to compress data into gzip format and/or decompress data from gzip 114 format. 116 The text of the specification assumes a basic background in 117 programming at the level of bits and other primitive data 118 representations. 120 1.3. Scope 122 The specification specifies a compression method and a file format 123 (the latter assuming only that a file can store a sequence of 124 arbitrary bytes). It does not specify any particular interface to 125 a file system or anything about character sets or encodings 126 (except for file names and comments, which are optional). 128 1.4. Compliance 130 Unless otherwise indicated below, a compliant decompressor must be 131 able to accept and decompress any file that conforms to all the 132 specifications presented here; a compliant compressor must produce 133 files that conform to all the specifications presented here. The 134 material in the appendices is not part of the specification per se 135 and is not relevant to compliance. 137 1.5. Definitions of terms and conventions used 139 byte: 8 bits stored or transmitted as a unit (same as an octet). 140 (For this specification, a byte is exactly 8 bits, even on 141 machines which store a character on a number of bits different 142 from 8.) See below for the numbering of bits within a byte. 144 1.6. Changes from previous versions 146 There have been no technical changes to the gzip format since 147 version 4.1 of this specification. In version 4.2, some 148 terminology was changed, and the sample CRC code was rewritten for 149 clarity and to eliminate the requirement for the caller to do pre- 150 and post-conditioning. Version 4.3 is a conversion of the 152 Deutsch [Page 3] 153 specification to Internet Draft style. 155 2. Detailed specification 157 2.1. Overall conventions 159 In the diagrams below, a box like this: 161 +---+ 162 | | <-- the vertical bars might be missing 163 +---+ 165 represents one byte; a box like this: 167 +==============+ 168 | | 169 +==============+ 171 represents a variable number of bytes. 173 Bytes stored within a computer do not have a 'bit order', since 174 they are always treated as a unit. However, a byte considered as 175 an integer between 0 and 255 does have a most- and least- 176 significant bit, and since we write numbers with the most- 177 significant digit on the left, we also write bytes with the most- 178 significant bit on the left. In the diagrams below, we number the 179 bits of a byte so that bit 0 is the least-significant bit, i.e., 180 the bits are numbered: 182 +--------+ 183 |76543210| 184 +--------+ 186 This document does not address the issue of the order in which 187 bits of a byte are transmitted on a bit-sequential medium, since 188 the data format described here is byte- rather than bit-oriented. 190 Within a computer, a number may occupy multiple bytes. All 191 multi-byte numbers in the format described here are stored with 192 the least-significant byte first (at the lower memory address). 193 For example, the decimal number 520 is stored as: 195 0 1 196 +--------+--------+ 197 |00001000|00000010| 198 +--------+--------+ 199 ^ ^ 200 | | 201 | + more significant byte = 2 x 256 202 + less significant byte = 8 204 Deutsch [Page 4] 205 2.2. File format 207 A gzip file consists of a series of "members" (compressed data 208 sets). The format of each member is specified in the following 209 section. The members simply appear one after another in the file, 210 with no additional information before, between, or after them. 212 2.3. Member format 214 Each member has the following structure: 216 +---+---+---+---+---+---+---+---+---+---+ 217 |ID1|ID2|CM |FLG| MTIME |XFL|OS | (more-->) 218 +---+---+---+---+---+---+---+---+---+---+ 220 (if FLG.FEXTRA set) 222 +---+---+=================================+ 223 | XLEN |...XLEN bytes of 'extra field'...| (more-->) 224 +---+---+=================================+ 226 (if FLG.FNAME set) 228 +=========================================+ 229 |...original file name, zero-terminated...| (more-->) 230 +=========================================+ 232 (if FLG.FCOMMENT set) 234 +===================================+ 235 |...file comment, zero-terminated...| (more-->) 236 +===================================+ 238 (if FLG.FHCRC set) 240 +---+---+ 241 | CRC16 | 242 +---+---+ 244 +=======================+ 245 |...compressed blocks...| (more-->) 246 +=======================+ 248 0 1 2 3 4 5 6 7 249 +---+---+---+---+---+---+---+---+ 250 | CRC32 | ISIZE | 251 +---+---+---+---+---+---+---+---+ 253 2.3.1. Member header and trailer 255 Deutsch [Page 5] 256 ID1 (IDentification 1) 257 ID2 (IDentification 2) 258 These have the fixed values ID1 = 31 (0x1f, \037), ID2 = 139 259 (0x8b, \213), to identify the file as being in gzip format. 261 CM (Compression Method) 262 This identifies the compression method used in the file. CM 263 = 0-7 are reserved. CM = 8 denotes the 'deflate' 264 compression method, which is the one customarily used by 265 gzip and which is documented elsewhere. 267 FLG (FLaGs) 268 This flag byte is divided into individual bits as follows: 270 bit 0 FTEXT 271 bit 1 FHCRC 272 bit 2 FEXTRA 273 bit 3 FNAME 274 bit 4 FCOMMENT 275 bit 5 reserved 276 bit 6 reserved 277 bit 7 reserved 279 If FTEXT is set, the file is probably ASCII text. This is 280 an optional indication, which the compressor may set by 281 checking a small amount of the input data to see whether any 282 non-ASCII characters are present. In case of doubt, FTEXT 283 is cleared, indicating binary data. For systems which have 284 different file formats for ascii text and binary data, the 285 decompressor can use FTEXT to choose the appropriate format. 286 We deliberately do not specify the algorithm used to set 287 this bit, since a compressor always has the option of 288 leaving it cleared and a decompressor always has the option 289 of ignoring it and letting some other program handle issues 290 of data conversion. 292 If FHCRC is set, a CRC16 for the gzip header is present, 293 immediately before the compressed data. The CRC16 consists 294 of the two least significant bytes of the CRC32 for all 295 bytes of the gzip header up to and not including the CRC16. 296 [The FHCRC bit was never set by versions of gzip up to 297 1.2.4, even though it was documented with a different 298 meaning in gzip 1.2.4.] 300 If FEXTRA is set, optional extra fields are present, as 301 described in a following section. 303 If FNAME is set, an original file name is present, 304 terminated by a zero byte. The name must consist of ISO 305 8859-1 (LATIN-1) characters; on operating systems using 306 EBCDIC or any other character set for file names, the name 307 must be translated to the ISO LATIN-1 character set. This 309 Deutsch [Page 6] 310 is the original name of the file being compressed, with any 311 directory components removed, and, if the file being 312 compressed is on a file system with case insensitive names, 313 forced to lower case. There is no original file name if the 314 data was compressed from a source other than a named file; 315 for example, if the source was stdin on a Unix system, there 316 is no file name. 318 If FCOMMENT is set, a zero-terminated file comment is 319 present. This comment is not interpreted; it is only 320 intended for human consumption. The comment must consist of 321 ISO 8859-1 (LATIN-1) characters. Line breaks should be 322 denoted by a single line feed character (10 decimal). 324 Reserved FLG bits must be zero. 326 MTIME (Modification TIME) 327 This gives the most recent modification time of the original 328 file being compressed. The time is in Unix format, i.e., 329 seconds since 00:00:00 GMT, Jan. 1, 1970. (Note that this 330 may cause problems for MS-DOS and other systems that use 331 local rather than Universal time.) If the compressed data 332 did not come from a file, MTIME is set to the time at which 333 compression started. MTIME = 0 means no time stamp is 334 available. 336 XFL (eXtra FLags) 337 These flags are available for use by specific compression 338 methods. The 'deflate' method (CM = 8) sets these flags as 339 follows: 341 XFL = 2 - compressor used maximum compression, 342 slowest algorithm 343 XFL = 4 - compressor used fastest algorithm 345 OS (Operating System) 346 This identifies the type of file system on which compression 347 took place. This may be useful in determining end-of-line 348 convention for text files. The currently defined values are 349 as follows: 351 Deutsch [Page 7] 352 0 - FAT filesystem (MS-DOS, OS/2, NT/Win32) 353 1 - Amiga 354 2 - VMS (or OpenVMS) 355 3 - Unix 356 4 - VM/CMS 357 5 - Atari TOS 358 6 - HPFS filesystem (OS/2, NT) 359 7 - Macintosh 360 8 - Z-System 361 9 - CP/M 362 10 - TOPS-20 363 11 - NTFS filesystem (NT) 364 12 - QDOS 365 13 - Acorn RISCOS 366 255 - unknown 368 XLEN (eXtra LENgth) 369 If FLG.FEXTRA is set, this gives the length of the optional 370 extra field. See below for details. 372 CRC32 (CRC-32) 373 This contains a Cyclic Redundancy Check value of the 374 uncompressed data computed according to CRC-32 algorithm 375 used in the ISO 3309 standard and in section 8.1.1.6.2 of 376 ITU-T recommendation V.42. (See http://www.iso.ch for 377 ordering ISO documents. See gopher://info.itu.ch for an 378 online version of ITU-T V.42.) 380 ISIZE (Input SIZE) 381 This contains the size of the original (uncompressed) input 382 data modulo 2^32. 384 2.3.1.1. Extra field 386 If the FLG.FEXTRA bit is set, an "extra field" is present in 387 the header, with total length XLEN bytes. It consists of a 388 series of subfields, each of the form: 390 +---+---+---+---+==================================+ 391 |SI1|SI2| LEN |... LEN bytes of subfield data ...| 392 +---+---+---+---+==================================+ 394 SI1 and SI2 provide a subfield ID, typically two ASCII letters 395 with some mnemonic value. Jean-loup Gailly 396 is maintaining a registry of subfield 397 IDs; please send him any subfield ID you wish to use. Subfield 398 IDs with SI2 = 0 are reserved for future use. The following 399 IDs are currently defined: 401 SI1 SI2 Data 402 ---------- ---------- ---- 403 0x41 ('A') 0x70 ('P') Apollo file type information 405 Deutsch [Page 8] 406 LEN gives the length of the subfield data, excluding the 4 407 initial bytes. 409 2.3.1.2. Compliance 411 A compliant compressor must produce files with correct ID1, 412 ID2, CM, CRC32, and ISIZE, but may set all the other fields in 413 the fixed-length part of the header to default values (255 for 414 OS, 0 for all others). The compressor must set all reserved 415 bits to zero. 417 A compliant decompressor must check ID1, ID2, and CM, and 418 provide an error indication if any of these have incorrect 419 values. It must examine FEXTRA/XLEN, FNAME, FCOMMENT and FHCRC 420 at least so it can skip over the optional fields if they are 421 present. It need not examine any other part of the header or 422 trailer; in particular, a decompressor may ignore FTEXT and OS 423 and always produce binary output, and still be compliant. A 424 compliant decompressor must give an error indication if any 425 reserved bit is non-zero, since such a bit could indicate the 426 presence of a new field that would cause subsequent data to be 427 interpreted incorrectly. 429 3. References 431 [1] "Information Processing - 8-bit single-byte coded graphic 432 character sets - Part 1: Latin alphabet No.1" (ISO 8859-1:1987). 433 The ISO 8859-1 (Latin-1) character set is a superset of 7-bit 434 ASCII. Files defining this character set may be obtained from 435 ftp.uu.net:/graphics/png/documents/iso_8859-1.* 437 [2] ISO 3309 439 [3] ITU-T recommendation V.42 441 [4] Deutsch, L.P.,"'Deflate' Compressed Data Format Specification", 442 available in ftp.uu.net:/pub/archiving/zip/doc/deflate-*.doc 444 [5] Gailly, J.-L., gzip documentation, available in 445 prep.ai.mit.edu:/pub/gnu/gzip-*.tar 447 [6] Sarwate, D.V., "Computation of Cyclic Redundancy Checks via Table 448 Look-Up", Communications of the ACM, 31(8), pp.1008-1013. 450 [7] Schwaderer, W.D., "CRC Calculation", April 85 PC Tech Journal, 451 pp.118-133. 453 [8] ftp.adelaide.edu.au:/pub/rocksoft/papers/crc_v3.txt, describing 454 the CRC concept. 456 Deutsch [Page 9] 457 4. Security considerations 459 Any data compression method involves the reduction of redundancy in 460 the data. Consequently, any corruption of the data is likely to have 461 severe effects and be difficult to correct. Uncompressed text, on 462 the other hand, will probably still be readable despite the presence 463 of some corrupted bytes. 465 It is recommended that systems using this data format provide some 466 means of validating the integrity of the compressed data, such as by 467 setting and checking the CRC-32 check value. 469 5. Acknowledgements 471 Trademarks cited in this document are the property of their 472 respective owners. 474 Jean-Loup Gailly designed the gzip format and wrote, with Mark Adler, 475 the related software described in this specification. Glenn 476 Randers-Pehrson converted this document to Internet Draft and HTML 477 format. 479 6. Author's address 481 L. Peter Deutsch 483 Aladdin Enterprises 484 203 Santa Margarita Ave. 485 Menlo Park, CA 94025 487 Phone: (415) 322-0103 (AM only) 488 FAX: (415) 322-1734 489 EMail: 491 Questions about the technical content of this specification can be 492 sent by email to 494 Jean-loup Gailly and 495 Mark Adler 497 Editorial comments on this specification can be sent by email to 499 L. Peter Deutsch and 500 Glenn Randers-Pehrson 502 Deutsch [Page 10] 503 7. Appendix: Jean-loup Gailly's gzip utility 505 The most widely used implementation of gzip compression, and the 506 original documentation on which this specification is based, were 507 created by Jean-loup Gailly . Since this 508 implementation is a de facto standard, we mention some more of its 509 features here. Again, the material in this section is not part of 510 the specification per se, and implementations need not follow it to 511 be compliant. 513 When compressing or decompressing a file, gzip preserves the 514 protection, ownership, and modification time attributes on the local 515 file system, since there is no provision for representing protection 516 attributes in the gzip file format itself. Since the file format 517 includes a modification time, the gzip decompressor provides a 518 command line switch that assigns the modification time from the file, 519 rather than the local modification time of the compressed input, to 520 the decompressed output. 522 8. Appendix: Sample CRC Code 524 The following sample code represents a practical implementation of 525 the CRC (Cyclic Redundancy Check). (See also ISO 3309 and ITU-T V.42 526 for a formal specification.) 528 The sample code is in the ANSI C programming language. Non C users 529 may find it easier to read with these hints: 531 & Bitwise AND operator. 532 ^ Bitwise exclusive-OR operator. 533 >> Bitwise right shift operator. When applied to an 534 unsigned quantity, as here, right shift inserts zero 535 bit(s) at the left. 536 ! Logical NOT operator. 537 ++ "n++" increments the variable n. 538 0xNNN 0x introduces a hexadecimal (base 16) constant. 539 Suffix L indicates a long value (at least 32 bits). 541 /* Table of CRCs of all 8-bit messages. */ 542 unsigned long crc_table[256]; 544 /* Flag: has the table been computed? Initially false. */ 545 int crc_table_computed = 0; 547 /* Make the table for a fast CRC. */ 548 void make_crc_table(void) 549 { 550 unsigned long c; 551 int n, k; 553 Deutsch [Page 11] 554 for (n = 0; n < 256; n++) { 555 c = (unsigned long) n; 556 for (k = 0; k < 8; k++) { 557 if (c & 1) { 558 c = 0xedb88320L ^ (c >> 1); 559 } else { 560 c = c >> 1; 561 } 562 } 563 crc_table[n] = c; 564 } 565 crc_table_computed = 1; 566 } 568 /* 569 Update a running crc with the bytes buf[0..len-1] and return 570 the updated crc. The crc should be initialized to zero. Pre- and 571 post-conditioning (one's complement) is performed within this 572 function so it shouldn't be done by the caller. Usage example: 574 unsigned long crc = 0L; 576 while (read_buffer(buffer, length) != EOF) { 577 crc = update_crc(crc, buffer, length); 578 } 579 if (crc != original_crc) error(); 580 */ 581 unsigned long update_crc(unsigned long crc, 582 unsigned char *buf, int len) 583 { 584 unsigned long c = crc ^ 0xffffffffL; 585 int n; 587 if (!crc_table_computed) 588 make_crc_table(); 589 for (n = 0; n < len; n++) { 590 c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8); 591 } 592 return c ^ 0xffffffffL; 593 } 595 /* Return the CRC of the bytes buf[0..len-1]. */ 596 unsigned long crc(unsigned char *buf, int len) 597 { 598 return update_crc(0L, buf, len); 599 } 601 Deutsch [Page 12]