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