< 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/