Brotli Compressed Data Format
RFC 7932

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 00
• 01
• 02
• 03
• 04
• 05
• 06
• 07
• 08
• 09
• 10
• 11

Internet Engineering Task Force (IETF)                     J. Alakuijala
Request for Comments: 7932                                   Z. Szabadka
Category: Informational                                     Google, Inc.
ISSN: 2070-1721                                                July 2016

                     Brotli Compressed Data Format

Abstract

   This specification defines a lossless compressed data format that
   compresses data using a combination of the LZ77 algorithm and Huffman
   coding, with efficiency comparable to the best currently available
   general-purpose compression methods.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Engineering Task Force
   (IETF).  It has been approved for publication by the Internet
   Engineering Steering Group (IESG).  Not all documents approved by the
   IESG are a candidate for any level of Internet Standard; see Section
   2 of RFC 7841.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   http://www.rfc-editor.org/info/rfc7932.

Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://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.

Alakuijala & Szabadka         Informational                     [Page 1]
RFC 7932                         Brotli                        July 2016

Table of Contents

   1. Introduction ....................................................3
      1.1. Purpose ....................................................3
      1.2. Intended Audience ..........................................3
      1.3. Scope ......................................................4
      1.4. Compliance .................................................4
      1.5. Definitions of Terms and Conventions Used ..................4
           1.5.1. Packing into Bytes ..................................5
   2. Compressed Representation Overview ..............................6
   3. Compressed Representation of Prefix Codes ......................10
      3.1. Introduction to Prefix Coding .............................10
      3.2. Use of Prefix Coding in the Brotli Format .................11
      3.3. Alphabet Sizes ............................................13
      3.4. Simple Prefix Codes .......................................14
      3.5. Complex Prefix Codes ......................................15
   4. Encoding of Distances ..........................................17
   5. Encoding of Literal Insertion Lengths and Copy Lengths .........19
   6. Encoding of Block-Switch Commands ..............................22
   7. Context Modeling ...............................................23
      7.1. Context Modes and Context ID Lookup for Literals ..........23
      7.2. Context ID for Distances ..................................26
      7.3. Encoding of the Context Map ...............................26
   8. Static Dictionary ..............................................28
   9. Compressed Data Format .........................................31
      9.1. Format of the Stream Header ...............................31
      9.2. Format of the Meta-Block Header ...........................32
      9.3. Format of the Meta-Block Data .............................35
   10. Decoding Algorithm ............................................36
   11. Considerations for Compressor Implementations .................38
      11.1. Trivial Compressor .......................................39
      11.2. Aligning Compressed Meta-Blocks to Byte Boundaries .......39
      11.3. Creating Self-Contained Parts within the
            Compressed Data ..........................................40
   12. Security Considerations .......................................41
   13. IANA Considerations ...........................................42
   14. Informative References ........................................43
   Appendix A. Static Dictionary Data ................................44
   Appendix B. List of Word Transformations .........................124
   Appendix C. Computing CRC-32 Check Values ........................127
   Appendix D. Source Code ..........................................127
   Acknowledgments ..................................................127
   Authors' Addresses ...............................................128