| < draft-alakuijala-brotli-09.txt | draft-alakuijala-brotli-11.txt > | |||
|---|---|---|---|---|
| Network Working Group J. Alakuijala | Network Working Group J. Alakuijala | |||
| Internet-Draft Z. Szabadka | Internet-Draft Z. Szabadka | |||
| Intended Status: Informational Google, Inc | Intended Status: Informational Google, Inc | |||
| Expires: October 19, 2016 April 2016 | Expires: November 24, 2016 May 2016 | |||
| Brotli Compressed Data Format | Brotli Compressed Data Format | |||
| draft-alakuijala-brotli-09 | draft-alakuijala-brotli-11 | |||
| Abstract | Abstract | |||
| This specification defines a lossless compressed data format that | This specification defines a lossless compressed data format that | |||
| compresses data using a combination of the LZ77 algorithm and Huffman | compresses data using a combination of the LZ77 algorithm and Huffman | |||
| coding, with efficiency comparable to the best currently available | coding, with efficiency comparable to the best currently available | |||
| general-purpose compression methods. | general-purpose compression methods. | |||
| Status of this Memo | Status of this Memo | |||
| skipping to change at page 1, line 33 ¶ | skipping to change at page 1, line 33 ¶ | |||
| Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||
| Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||
| working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||
| Drafts is at http://datatracker.ietf.org/drafts/current/. | Drafts is at http://datatracker.ietf.org/drafts/current/. | |||
| Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||
| and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||
| time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||
| material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||
| This Internet-Draft will expire on October 19, 2016. | This Internet-Draft will expire on November 24, 2016. | |||
| Copyright Notice | Copyright Notice | |||
| Copyright (c) 2016 IETF Trust and the persons identified as the | Copyright (c) 2016 IETF Trust and the persons identified as the | |||
| document authors. All rights reserved. | document authors. All rights reserved. | |||
| This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||
| Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||
| (http://trustee.ietf.org/license-info) in effect on the date of | (http://trustee.ietf.org/license-info) in effect on the date of | |||
| publication of this document. Please review these documents | publication of this document. Please review these documents | |||
| skipping to change at page 2, line 10 ¶ | skipping to change at page 2, line 10 ¶ | |||
| to this document. Code Components extracted from this document must | to this document. Code Components extracted from this document must | |||
| include Simplified BSD License text as described in Section 4.e of | include Simplified BSD License text as described in Section 4.e of | |||
| the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||
| described in the Simplified BSD License. | described in the Simplified BSD License. | |||
| Table of Contents | Table of Contents | |||
| 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 | |||
| 1.1. Purpose . . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1.1. Purpose . . . . . . . . . . . . . . . . . . . . . . . . . 3 | |||
| 1.2. Intended audience . . . . . . . . . . . . . . . . . . . . 3 | 1.2. Intended audience . . . . . . . . . . . . . . . . . . . . 3 | |||
| 1.3. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1.3. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 4 | |||
| 1.4. Compliance . . . . . . . . . . . . . . . . . . . . . . . . 4 | 1.4. Compliance . . . . . . . . . . . . . . . . . . . . . . . . 4 | |||
| 1.5. Definitions of terms and conventions used . . . . . . . . 4 | 1.5. Definitions of terms and conventions used . . . . . . . . 4 | |||
| 1.5.1. Packing into bytes . . . . . . . . . . . . . . . . . 4 | 1.5.1. Packing into bytes . . . . . . . . . . . . . . . . . 5 | |||
| 2. Compressed representation overview . . . . . . . . . . . . . . 5 | 2. Compressed representation overview . . . . . . . . . . . . . . 6 | |||
| 3. Compressed representation of prefix codes . . . . . . . . . . . 9 | 3. Compressed representation of prefix codes . . . . . . . . . . 10 | |||
| 3.1. Introduction to prefix coding . . . . . . . . . . . . . . 9 | 3.1. Introduction to prefix coding . . . . . . . . . . . . . . 10 | |||
| 3.2. Use of prefix coding in the brotli format . . . . . . . . 10 | 3.2. Use of prefix coding in the brotli format . . . . . . . . 11 | |||
| 3.3. Alphabet sizes . . . . . . . . . . . . . . . . . . . . . 12 | 3.3. Alphabet sizes . . . . . . . . . . . . . . . . . . . . . 12 | |||
| 3.4. Simple prefix codes . . . . . . . . . . . . . . . . . . . 13 | 3.4. Simple prefix codes . . . . . . . . . . . . . . . . . . . 13 | |||
| 3.5. Complex prefix codes . . . . . . . . . . . . . . . . . . 14 | 3.5. Complex prefix codes . . . . . . . . . . . . . . . . . . 14 | |||
| 4. Encoding of distances . . . . . . . . . . . . . . . . . . . . 16 | 4. Encoding of distances . . . . . . . . . . . . . . . . . . . . 17 | |||
| 5. Encoding of literal insertion lengths and copy lengths . . . . 18 | 5. Encoding of literal insertion lengths and copy lengths . . . . 18 | |||
| 6. Encoding of block switch commands . . . . . . . . . . . . . . 20 | 6. Encoding of block switch commands . . . . . . . . . . . . . . 20 | |||
| 7. Context modeling . . . . . . . . . . . . . . . . . . . . . . . 22 | 7. Context modeling . . . . . . . . . . . . . . . . . . . . . . . 22 | |||
| 7.1. Context modes and context ID lookup for literals . . . . 22 | 7.1. Context modes and context ID lookup for literals . . . . 22 | |||
| 7.2. Context ID for distances . . . . . . . . . . . . . . . . 24 | 7.2. Context ID for distances . . . . . . . . . . . . . . . . 24 | |||
| 7.3. Encoding of the context map . . . . . . . . . . . . . . . 24 | 7.3. Encoding of the context map . . . . . . . . . . . . . . . 24 | |||
| 8. Static dictionary . . . . . . . . . . . . . . . . . . . . . . 26 | 8. Static dictionary . . . . . . . . . . . . . . . . . . . . . . 26 | |||
| 9. Compressed data format . . . . . . . . . . . . . . . . . . . . 28 | 9. Compressed data format . . . . . . . . . . . . . . . . . . . . 29 | |||
| 9.1. Format of the stream header . . . . . . . . . . . . . . . 29 | 9.1. Format of the stream header . . . . . . . . . . . . . . . 29 | |||
| 9.2. Format of the meta-block header . . . . . . . . . . . . . 29 | 9.2. Format of the meta-block header . . . . . . . . . . . . . 30 | |||
| 9.3. Format of the meta-block data . . . . . . . . . . . . . . 32 | 9.3. Format of the meta-block data . . . . . . . . . . . . . . 32 | |||
| 10. Decoding algorithm . . . . . . . . . . . . . . . . . . . . . 33 | 10. Decoding algorithm . . . . . . . . . . . . . . . . . . . . . 34 | |||
| 11. Considerations for compressor implementations . . . . . . . . 36 | 11. Considerations for compressor implementations . . . . . . . . 36 | |||
| 11.1. Trivial compressor . . . . . . . . . . . . . . . . . . . 36 | 11.1. Trivial compressor . . . . . . . . . . . . . . . . . . . 36 | |||
| 11.2. Aligning compressed meta-blocks to byte boundaries . . . 37 | 11.2. Aligning compressed meta-blocks to byte boundaries . . . 37 | |||
| 11.3. Creating self-contained parts within the compressed data 37 | 11.3. Creating self-contained parts within the compressed data 37 | |||
| 12. Security Considerations . . . . . . . . . . . . . . . . . . . 38 | 12. Security Considerations . . . . . . . . . . . . . . . . . . . 38 | |||
| 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 | 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 40 | |||
| 14. Informative References . . . . . . . . . . . . . . . . . . . 40 | 14. Informative References . . . . . . . . . . . . . . . . . . . 40 | |||
| 15. Source code . . . . . . . . . . . . . . . . . . . . . . . . . 40 | 15. Source code . . . . . . . . . . . . . . . . . . . . . . . . . 40 | |||
| 16. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 40 | 16. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 41 | |||
| Appendix A. Static dictionary data . . . . . . . . . . . . . . . 40 | Appendix A. Static dictionary data . . . . . . . . . . . . . . . 41 | |||
| Appendix B. List of word transformations . . . . . . . . . . . . 121 | Appendix B. List of word transformations . . . . . . . . . . . . 121 | |||
| Appendix C. Computing CRC-32 check values . . . . . . . . . . . 124 | ||||
| Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124 | |||
| 1. Introduction | 1. Introduction | |||
| 1.1. Purpose | 1.1. Purpose | |||
| The purpose of this specification is to define a lossless compressed | The purpose of this specification is to define a lossless compressed | |||
| data format that: | data format that: | |||
| * Is independent of CPU type, operating system, file system, | * Is independent of CPU type, operating system, file system, | |||
| skipping to change at page 3, line 30 ¶ | skipping to change at page 3, line 30 ¶ | |||
| best currently available general-purpose compression methods, | best currently available general-purpose compression methods, | |||
| and in particular, considerably better than the gzip program; | and in particular, considerably better than the gzip program; | |||
| * Decompresses much faster than current LZMA implementations. | * Decompresses much faster than current LZMA implementations. | |||
| The data format defined by this specification does not attempt to: | The data format defined by this specification does not attempt to: | |||
| * Allow random access to compressed data; | * Allow random access to compressed data; | |||
| * Compress specialized data (e.g., raster graphics) as well | * Compress specialized data (e.g., raster graphics) as well | |||
| as the best currently available specialized algorithms. | as the best currently available specialized algorithms. | |||
| This document is the authoritative specification of the brotli | ||||
| compressed data format. It defines the set of valid brotli compressed | ||||
| data streams and a decoder algorithm that produces the uncompressed | ||||
| data stream from a valid brotli compressed data stream. | ||||
| 1.2. Intended audience | 1.2. Intended audience | |||
| This specification is intended for use by software implementers to | This specification is intended for use by software implementers to | |||
| compress data into and/or decompress data from the brotli format. | compress data into and/or decompress data from the brotli format. | |||
| The text of the specification assumes a basic background in | The text of the specification assumes a basic background in | |||
| programming at the level of bits and other primitive data | programming at the level of bits and other primitive data | |||
| representations. Familiarity with the technique of Huffman coding is | representations. Familiarity with the technique of Huffman coding is | |||
| helpful but not required. | helpful but not required. | |||
| skipping to change at page 24, line 13 ¶ | skipping to change at page 24, line 13 ¶ | |||
| 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, | 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, | |||
| 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | |||
| 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | |||
| 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | |||
| 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, | |||
| 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | |||
| 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | |||
| 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | |||
| 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7 | |||
| The lengths and the zlib CRC-32 (ITU-T Recommendation V.42) check | The lengths and the CRC-32 check values (see Appendix C.) of each of | |||
| values of each of these tables as a sequence of bytes are as follows: | these tables as a sequence of bytes are as follows: | |||
| Table Length CRC-32 | Table Length CRC-32 | |||
| ----- ------ ------ | ----- ------ ------ | |||
| Lut0 256 0x8e91efb7 | Lut0 256 0x8e91efb7 | |||
| Lut1 256 0xd01a32f4 | Lut1 256 0xd01a32f4 | |||
| Lut2 256 0x0dd7a0d6 | Lut2 256 0x0dd7a0d6 | |||
| Given p1 is the last uncompressed byte and p2 is the second-to-last | Given p1 is the last uncompressed byte and p2 is the second-to-last | |||
| uncompressed byte, the context IDs can be computed as follows: | uncompressed byte, the context IDs can be computed as follows: | |||
| skipping to change at page 27, line 45 ¶ | skipping to change at page 27, line 45 ¶ | |||
| greater than 120, or the length is smaller than 4 or greater than 24, | greater than 120, or the length is smaller than 4 or greater than 24, | |||
| then the compressed stream should be rejected as invalid. | then the compressed stream should be rejected as invalid. | |||
| Each word transformation has the following form: | Each word transformation has the following form: | |||
| transform_i(word) = prefix_i + T_i(word) + suffix_i | transform_i(word) = prefix_i + T_i(word) + suffix_i | |||
| where the _i subscript denotes the transform_id above. Each T_i is | where the _i subscript denotes the transform_id above. Each T_i is | |||
| one of the following 21 elementary transforms: | one of the following 21 elementary transforms: | |||
| Identity, UppercaseFirst, UppercaseAll, | Identity, FermentFirst, FermentAll, | |||
| OmitFirst1, ..., OmitFirst9, OmitLast1, ..., OmitLast9 | OmitFirst1, ..., OmitFirst9, OmitLast1, ..., OmitLast9 | |||
| The form of these elementary transforms is as follows: | The form of these elementary transforms is as follows: | |||
| Identity(word) = word | Identity(word) = word | |||
| UppercaseFirst(word) = first UTF-8 character of word upper-cased | FermentFirst(word) = see below | |||
| UppercaseAll(word) = all UTF-8 characters of word upper-cased | FermentAll(word) = see below | |||
| OmitFirstk(word) = the last (length(word) - k) bytes of word, or | OmitFirstk(word) = the last (length(word) - k) bytes of word, or | |||
| empty string if length(word) < k | empty string if length(word) < k | |||
| OmitLastk(word) = the first (length(word) - k) bytes of word, or | OmitLastk(word) = the first (length(word) - k) bytes of word, or | |||
| empty string if length(word) < k | empty string if length(word) < k | |||
| For the purposes of UppercaseAll, word is parsed into UTF-8 | We define the FermentFirst and FermentAll transforms used in this | |||
| characters and converted to upper-case by taking 1..3 bytes at a | specification by the following C language functions: | |||
| time, using the algorithm below: | ||||
| i = 0 | int Ferment(uint8_t* word, int word_len, int pos) { | |||
| while i < length(word): | if (word[pos] < 192) { | |||
| if word[i] < 192: | if (word[pos] >= 97 and word[pos] <= 122) { | |||
| if word[i] >= 97 and word[i] <= 122: | word[pos] = word[pos] ^ 32; | |||
| word[i] = word[i] ^ 32 | } | |||
| i = i + 1 | return 1; | |||
| else if word[i] < 224: | } else if (word[pos] < 224) { | |||
| if i + 1 < length(word): | if (pos + 1 < word_len) { | |||
| word[i + 1] = word[i + 1] ^ 32 | word[pos + 1] = word[pos + 1] ^ 32; | |||
| i = i + 2 | } | |||
| else: | return 2; | |||
| if i + 2 < length(word): | } else { | |||
| word[i + 2] = word[i + 2] ^ 5 | if (pos + 2 < word_len) { | |||
| i = i + 3 | word[pos + 2] = word[pos + 2] ^ 5; | |||
| } | ||||
| return 3; | ||||
| } | ||||
| } | ||||
| For UppercaseFirst, the same algorithm is used, but the loop is | void FermentFirst(uint8_t* word, int word_len) { | |||
| executed only once. | if (word_len > 0) { | |||
| Ferment(word, word_len, 0); | ||||
| } | ||||
| } | ||||
| void FermentAll(uint8_t* word, int word_len) { | ||||
| int i = 0; | ||||
| while (i < word_len) { | ||||
| i += Ferment(word, word_len, i); | ||||
| } | ||||
| } | ||||
| Appendix B. contains the list of transformations by specifying the | Appendix B. contains the list of transformations by specifying the | |||
| prefix, elementary transform and suffix components of each of them. | prefix, elementary transform and suffix components of each of them. | |||
| Note that the OmitFirst8 elementary transform is not used in the list | Note that the OmitFirst8 elementary transform is not used in the list | |||
| of transformations. The strings in Appendix B. are in C string format | of transformations. The strings in Appendix B. are in C string format | |||
| with respect to escape (backslash) characters. | with respect to escape (backslash) characters. | |||
| The maximum number of additional bytes that a transform may add to a | The maximum number of additional bytes that a transform may add to a | |||
| base word is 13. Since the largest base word is 24 bytes long, a | base word is 13. Since the largest base word is 24 bytes long, a | |||
| buffer of 38 bytes is sufficient to store any transformed words | buffer of 38 bytes is sufficient to store any transformed words | |||
| skipping to change at page 38, line 24 ¶ | skipping to change at page 38, line 41 ¶ | |||
| only by the compressor that produces C0. | only by the compressor that produces C0. | |||
| Note that this method can be easily generalized to more than two | Note that this method can be easily generalized to more than two | |||
| sequences of uncompressed bytes. | sequences of uncompressed bytes. | |||
| 12. Security Considerations | 12. Security Considerations | |||
| As with any compressed file formats, decompressor implementations | As with any compressed file formats, decompressor implementations | |||
| should handle all compressed data byte sequences, not only those that | should handle all compressed data byte sequences, not only those that | |||
| conform to this specification, where non-conformant compressed data | conform to this specification, where non-conformant compressed data | |||
| sequences should be discarded. | sequences should be rejected as invalid. | |||
| A possible attack against a system containing a decompressor | A possible attack against a system containing a decompressor | |||
| implementation (e.g. a web browser) is to exploit a buffer overflow | implementation (e.g. a web browser) is to exploit a buffer overflow | |||
| triggered by invalid compressed data. Therefore decompressor | triggered by invalid compressed data. Therefore decompressor | |||
| implementations should perform bounds-checking for each memory access | implementations should perform bounds-checking for each memory access | |||
| that result from values decoded from the compressed stream and | that result from values decoded from the compressed stream and | |||
| derivatives therof. | derivatives therof. | |||
| Another possible attack against a system containing a decompressor | Another possible attack against a system containing a decompressor | |||
| implementation is to provide it (either valid or invalid) compressed | implementation is to provide it (either valid or invalid) compressed | |||
| skipping to change at page 40, line 48 ¶ | skipping to change at page 41, line 16 ¶ | |||
| The authors would like to thank Mark Adler, Robert Obryk, Thomas | The authors would like to thank Mark Adler, Robert Obryk, Thomas | |||
| Pickert, and Joe Tsai for providing helpful review comments, | Pickert, and Joe Tsai for providing helpful review comments, | |||
| validating the specification by writing an independent decompressor, | validating the specification by writing an independent decompressor, | |||
| and suggesting improvements to the format and the text of the | and suggesting improvements to the format and the text of the | |||
| specification. | specification. | |||
| Appendix A. Static dictionary data | Appendix A. Static dictionary data | |||
| The hexadecimal form of the DICT array is the following, where the | The hexadecimal form of the DICT array is the following, where the | |||
| length is 122,784 bytes and the zlib CRC-32 of the byte sequence is | length is 122,784 bytes and the CRC-32 of the byte sequence is | |||
| 0x5136cb04. | 0x5136cb04. | |||
| 74696d65646f776e6c6966656c6566746261636b636f64656461746173686f77 | 74696d65646f776e6c6966656c6566746261636b636f64656461746173686f77 | |||
| 6f6e6c7973697465636974796f70656e6a7573746c696b6566726565776f726b | 6f6e6c7973697465636974796f70656e6a7573746c696b6566726565776f726b | |||
| 74657874796561726f766572626f64796c6f7665666f726d626f6f6b706c6179 | 74657874796561726f766572626f64796c6f7665666f726d626f6f6b706c6179 | |||
| 6c6976656c696e6568656c70686f6d65736964656d6f7265776f72646c6f6e67 | 6c6976656c696e6568656c70686f6d65736964656d6f7265776f72646c6f6e67 | |||
| 7468656d7669657766696e64706167656461797366756c6c686561647465726d | 7468656d7669657766696e64706167656461797366756c6c686561647465726d | |||
| 656163686172656166726f6d747275656d61726b61626c6575706f6e68696768 | 656163686172656166726f6d747275656d61726b61626c6575706f6e68696768 | |||
| 646174656c616e646e6577736576656e6e65787463617365626f7468706f7374 | 646174656c616e646e6577736576656e6e65787463617365626f7468706f7374 | |||
| 757365646d61646568616e6468657265776861746e616d654c696e6b626c6f67 | 757365646d61646568616e6468657265776861746e616d654c696e6b626c6f67 | |||
| skipping to change at page 121, line 17 ¶ | skipping to change at page 121, line 33 ¶ | |||
| Appendix B. List of word transformations | Appendix B. List of word transformations | |||
| The string literals are in C format, with respect to the use of | The string literals are in C format, with respect to the use of | |||
| backslash escape characters. | backslash escape characters. | |||
| In order to generate a length and check value, the transforms can be | In order to generate a length and check value, the transforms can be | |||
| converted to a series of bytes, where each transform is the prefix | converted to a series of bytes, where each transform is the prefix | |||
| sequence of bytes plus a terminating zero byte, a single byte value | sequence of bytes plus a terminating zero byte, a single byte value | |||
| identifying the transform, and the suffix sequence of bytes plus a | identifying the transform, and the suffix sequence of bytes plus a | |||
| terminating zero. The value for the transforms are 0 for Identity, 1 for | terminating zero. The value for the transforms are 0 for Identity, 1 for | |||
| UppercaseFirst, 2 for UppercaseAll, 3 to 11 for OmitFirst1 to | FermentFirst, 2 for FermentAll, 3 to 11 for OmitFirst1 to OmitFirst9, | |||
| OmitFirst9, and 12 to 20 for OmitLast1 to OmitLast9. The byte sequences | and 12 to 20 for OmitLast1 to OmitLast9. The byte sequences that | |||
| that represent the 121 transforms are then concatenated to a single | represent the 121 transforms are then concatenated to a single sequence | |||
| sequence of bytes. The length of that sequence is 648 bytes, and the | of bytes. The length of that sequence is 648 bytes, and the CRC-32 is | |||
| zlib CRC is 0x3d965f81. | 0x3d965f81. | |||
| ID Prefix Transform Suffix | ID Prefix Transform Suffix | |||
| -- ------ --------- ------ | -- ------ --------- ------ | |||
| 0 "" Identity "" | 0 "" Identity "" | |||
| 1 "" Identity " " | 1 "" Identity " " | |||
| 2 " " Identity " " | 2 " " Identity " " | |||
| 3 "" OmitFirst1 "" | 3 "" OmitFirst1 "" | |||
| 4 "" UppercaseFirst " " | 4 "" FermentFirst " " | |||
| 5 "" Identity " the " | 5 "" Identity " the " | |||
| 6 " " Identity "" | 6 " " Identity "" | |||
| 7 "s " Identity " " | 7 "s " Identity " " | |||
| 8 "" Identity " of " | 8 "" Identity " of " | |||
| 9 "" UppercaseFirst "" | 9 "" FermentFirst "" | |||
| 10 "" Identity " and " | 10 "" Identity " and " | |||
| 11 "" OmitFirst2 "" | 11 "" OmitFirst2 "" | |||
| 12 "" OmitLast1 "" | 12 "" OmitLast1 "" | |||
| 13 ", " Identity " " | 13 ", " Identity " " | |||
| 14 "" Identity ", " | 14 "" Identity ", " | |||
| 15 " " UppercaseFirst " " | 15 " " FermentFirst " " | |||
| 16 "" Identity " in " | 16 "" Identity " in " | |||
| 17 "" Identity " to " | 17 "" Identity " to " | |||
| 18 "e " Identity " " | 18 "e " Identity " " | |||
| 19 "" Identity "\"" | 19 "" Identity "\"" | |||
| 20 "" Identity "." | 20 "" Identity "." | |||
| 21 "" Identity "\">" | 21 "" Identity "\">" | |||
| 22 "" Identity "\n" | 22 "" Identity "\n" | |||
| 23 "" OmitLast3 "" | 23 "" OmitLast3 "" | |||
| 24 "" Identity "]" | 24 "" Identity "]" | |||
| 25 "" Identity " for " | 25 "" Identity " for " | |||
| 26 "" OmitFirst3 "" | 26 "" OmitFirst3 "" | |||
| 27 "" OmitLast2 "" | 27 "" OmitLast2 "" | |||
| 28 "" Identity " a " | 28 "" Identity " a " | |||
| 29 "" Identity " that " | 29 "" Identity " that " | |||
| 30 " " UppercaseFirst "" | 30 " " FermentFirst "" | |||
| 31 "" Identity ". " | 31 "" Identity ". " | |||
| 32 "." Identity "" | 32 "." Identity "" | |||
| 33 " " Identity ", " | 33 " " Identity ", " | |||
| 34 "" OmitFirst4 "" | 34 "" OmitFirst4 "" | |||
| 35 "" Identity " with " | 35 "" Identity " with " | |||
| 36 "" Identity "'" | 36 "" Identity "'" | |||
| 37 "" Identity " from " | 37 "" Identity " from " | |||
| 38 "" Identity " by " | 38 "" Identity " by " | |||
| 39 "" OmitFirst5 "" | 39 "" OmitFirst5 "" | |||
| 40 "" OmitFirst6 "" | 40 "" OmitFirst6 "" | |||
| 41 " the " Identity "" | 41 " the " Identity "" | |||
| 42 "" OmitLast4 "" | 42 "" OmitLast4 "" | |||
| 43 "" Identity ". The " | 43 "" Identity ". The " | |||
| 44 "" UppercaseAll "" | 44 "" FermentAll "" | |||
| 45 "" Identity " on " | 45 "" Identity " on " | |||
| 46 "" Identity " as " | 46 "" Identity " as " | |||
| 47 "" Identity " is " | 47 "" Identity " is " | |||
| 48 "" OmitLast7 "" | 48 "" OmitLast7 "" | |||
| 49 "" OmitLast1 "ing " | 49 "" OmitLast1 "ing " | |||
| 50 "" Identity "\n\t" | 50 "" Identity "\n\t" | |||
| 51 "" Identity ":" | 51 "" Identity ":" | |||
| 52 " " Identity ". " | 52 " " Identity ". " | |||
| 53 "" Identity "ed " | 53 "" Identity "ed " | |||
| 54 "" OmitFirst9 "" | 54 "" OmitFirst9 "" | |||
| 55 "" OmitFirst7 "" | 55 "" OmitFirst7 "" | |||
| 56 "" OmitLast6 "" | 56 "" OmitLast6 "" | |||
| 57 "" Identity "(" | 57 "" Identity "(" | |||
| 58 "" UppercaseFirst ", " | 58 "" FermentFirst ", " | |||
| 59 "" OmitLast8 "" | 59 "" OmitLast8 "" | |||
| 60 "" Identity " at " | 60 "" Identity " at " | |||
| 61 "" Identity "ly " | 61 "" Identity "ly " | |||
| 62 " the " Identity " of " | 62 " the " Identity " of " | |||
| 63 "" OmitLast5 "" | 63 "" OmitLast5 "" | |||
| 64 "" OmitLast9 "" | 64 "" OmitLast9 "" | |||
| 65 " " UppercaseFirst ", " | 65 " " FermentFirst ", " | |||
| 66 "" UppercaseFirst "\"" | 66 "" FermentFirst "\"" | |||
| 67 "." Identity "(" | 67 "." Identity "(" | |||
| 68 "" UppercaseAll " " | 68 "" FermentAll " " | |||
| 69 "" UppercaseFirst "\">" | 69 "" FermentFirst "\">" | |||
| 70 "" Identity "=\"" | 70 "" Identity "=\"" | |||
| 71 " " Identity "." | 71 " " Identity "." | |||
| 72 ".com/" Identity "" | 72 ".com/" Identity "" | |||
| 73 " the " Identity " of the " | 73 " the " Identity " of the " | |||
| 74 "" UppercaseFirst "'" | 74 "" FermentFirst "'" | |||
| 75 "" Identity ". This " | 75 "" Identity ". This " | |||
| 76 "" Identity "," | 76 "" Identity "," | |||
| 77 "." Identity " " | 77 "." Identity " " | |||
| 78 "" UppercaseFirst "(" | 78 "" FermentFirst "(" | |||
| 79 "" UppercaseFirst "." | 79 "" FermentFirst "." | |||
| 80 "" Identity " not " | 80 "" Identity " not " | |||
| 81 " " Identity "=\"" | 81 " " Identity "=\"" | |||
| 82 "" Identity "er " | 82 "" Identity "er " | |||
| 83 " " UppercaseAll " " | 83 " " FermentAll " " | |||
| 84 "" Identity "al " | 84 "" Identity "al " | |||
| 85 " " UppercaseAll "" | 85 " " FermentAll "" | |||
| 86 "" Identity "='" | 86 "" Identity "='" | |||
| 87 "" UppercaseAll "\"" | 87 "" FermentAll "\"" | |||
| 88 "" UppercaseFirst ". " | 88 "" FermentFirst ". " | |||
| 89 " " Identity "(" | 89 " " Identity "(" | |||
| 90 "" Identity "ful " | 90 "" Identity "ful " | |||
| 91 " " UppercaseFirst ". " | 91 " " FermentFirst ". " | |||
| 92 "" Identity "ive " | 92 "" Identity "ive " | |||
| 93 "" Identity "less " | 93 "" Identity "less " | |||
| 94 "" UppercaseAll "'" | 94 "" FermentAll "'" | |||
| 95 "" Identity "est " | 95 "" Identity "est " | |||
| 96 " " UppercaseFirst "." | 96 " " FermentFirst "." | |||
| 97 "" UppercaseAll "\">" | 97 "" FermentAll "\">" | |||
| 98 " " Identity "='" | 98 " " Identity "='" | |||
| 99 "" UppercaseFirst "," | 99 "" FermentFirst "," | |||
| 100 "" Identity "ize " | 100 "" Identity "ize " | |||
| 101 "" UppercaseAll "." | 101 "" FermentAll "." | |||
| 102 "\xc2\xa0" Identity "" | 102 "\xc2\xa0" Identity "" | |||
| 103 " " Identity "," | 103 " " Identity "," | |||
| 104 "" UppercaseFirst "=\"" | 104 "" FermentFirst "=\"" | |||
| 105 "" UppercaseAll "=\"" | 105 "" FermentAll "=\"" | |||
| 106 "" Identity "ous " | 106 "" Identity "ous " | |||
| 107 "" UppercaseAll ", " | 107 "" FermentAll ", " | |||
| 108 "" UppercaseFirst "='" | 108 "" FermentFirst "='" | |||
| 109 " " UppercaseFirst "," | 109 " " FermentFirst "," | |||
| 110 " " UppercaseAll "=\"" | 110 " " FermentAll "=\"" | |||
| 111 " " UppercaseAll ", " | 111 " " FermentAll ", " | |||
| 112 "" UppercaseAll "," | 112 "" FermentAll "," | |||
| 113 "" UppercaseAll "(" | 113 "" FermentAll "(" | |||
| 114 "" UppercaseAll ". " | 114 "" FermentAll ". " | |||
| 115 " " UppercaseAll "." | 115 " " FermentAll "." | |||
| 116 "" UppercaseAll "='" | 116 "" FermentAll "='" | |||
| 117 " " UppercaseAll ". " | 117 " " FermentAll ". " | |||
| 118 " " UppercaseFirst "=\"" | 118 " " FermentFirst "=\"" | |||
| 119 " " UppercaseAll "='" | 119 " " FermentAll "='" | |||
| 120 " " UppercaseFirst "='" | 120 " " FermentFirst "='" | |||
| Appendix C. Computing CRC-32 check values | ||||
| For the purpose of this specification, we define the CRC-32 check value | ||||
| of a byte sequence with the following C language function: | ||||
| uint32_t CRC32(const uint8_t* v, const int len) { | ||||
| const uint32_t poly = 0xedb88320UL; | ||||
| uint32_t crc, c; | ||||
| int i, k; | ||||
| crc = 0xffffffffUL; | ||||
| for (i = 0; i < len; ++i) { | ||||
| c = (crc ^ v[i]) & 0xff; | ||||
| for (k = 0; k < 8; k++) c = c & 1 ? poly ^ (c >> 1) : c >> 1; | ||||
| crc = c ^ (crc >> 8); | ||||
| } | ||||
| return crc ^ 0xffffffffUL; | ||||
| } | ||||
| Authors' Addresses | Authors' Addresses | |||
| Jyrki Alakuijala | Jyrki Alakuijala | |||
| Google, Inc | Google, Inc | |||
| Email: jyrki@google.com | Email: jyrki@google.com | |||
| Zoltan Szabadka | Zoltan Szabadka | |||
| Google, Inc | Google, Inc | |||
| End of changes. 43 change blocks. | ||||
| 87 lines changed or deleted | 124 lines changed or added | |||
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||