< draft-alakuijala-brotli-10.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: November 4, 2016 May 2016 Expires: November 24, 2016 May 2016
Brotli Compressed Data Format Brotli Compressed Data Format
draft-alakuijala-brotli-10 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 November 4, 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 . . . . . . . . . . . . . . . . . . . . 29 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 . . . . . . . . . . . . . 30 9.2. Format of the meta-block header . . . . . . . . . . . . . 30
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.
 End of changes. 7 change blocks. 
10 lines changed or deleted 15 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/