1. Einführung (Introduction)

1.1. Zweck (Purpose)

Der Zweck dieser Spezifikation ist es, ein verlustfreies komprimiertes Datenformat (Lossless Compressed Data Format) zu definieren, das:

unabhängig von CPU-Typ, Betriebssystem, Dateisystem und Zeichensatz ist; daher kann es für den Datenaustausch verwendet werden.
produziert oder konsumiert werden kann, selbst für einen beliebig langen, sequentiell präsentierten Eingabedatenstrom, unter Verwendung nur einer a priori begrenzten Menge an Zwischenspeicher; daher kann es in der Datenkommunikation oder ähnlichen Strukturen wie Unix-Filtern verwendet werden.
Daten mit einem Kompressionsverhältnis (Compression Ratio) komprimiert, das mit den besten derzeit verfügbaren Allzweck-Komprimierungsmethoden vergleichbar ist, insbesondere erheblich besser als das gzip-Programm.
wesentlich schneller dekomprimiert als aktuelle LZMA-Implementierungen.

Das durch diese Spezifikation definierte Datenformat versucht nicht:

zufälligen Zugriff auf komprimierte Daten zu ermöglichen.
spezialisierte Daten (z.B. Rastergrafiken) so dicht zu komprimieren wie die besten derzeit verfügbaren spezialisierten Algorithmen.

Dieses Dokument ist die maßgebliche Spezifikation des brotli-komprimierten Datenformats. Es definiert die Menge gültiger brotli-komprimierter Datenströme und einen Dekodieralgorithmus (Decoder Algorithm), der den unkomprimierten Datenstrom aus einem gültigen brotli-komprimierten Datenstrom erzeugt.

1.2. Zielgruppe (Intended Audience)

Diese Spezifikation richtet sich an Software-Implementierer zur Komprimierung von Daten in und/oder Dekomprimierung von Daten aus dem brotli-Format.

Der Text der Spezifikation setzt grundlegende Kenntnisse in der Programmierung auf der Ebene von Bits und anderen primitiven Datenrepräsentationen voraus. Vertrautheit mit der Technik der Huffman-Codierung (Huffman Coding) ist hilfreich, aber nicht erforderlich.

Diese Spezifikation verwendet (umfangreich) die Notationen und Terminologie, die in der DEFLATE-Formatspezifikation [RFC1951] eingeführt wurden. Der Vollständigkeit halber fügen wir immer den vollständigen Text der relevanten Teile von RFC 1951 bei; daher ist Vertrautheit mit dem DEFLATE-Format hilfreich, aber nicht erforderlich.

Das in dieser Spezifikation definierte komprimierte Datenformat ist ein integraler Bestandteil des WOFF-Dateiformats 2.0 [WOFF2]; daher richtet sich diese Spezifikation auch an Implementierer von WOFF 2.0-Kompressoren und -Dekompressoren.

1.3. Umfang (Scope)

Dieses Dokument spezifiziert eine Methode zur Darstellung einer Bytefolge (Sequence of Bytes) als eine (normalerweise kürzere) Bitfolge (Sequence of Bits) und eine Methode zum Packen der letzteren Bitfolge in Bytes.

1.4. Konformität (Compliance)

Sofern im Folgenden nicht anders angegeben, muss ein konformer Dekompressor (Compliant Decompressor) in der Lage sein, jeden Datensatz zu akzeptieren und zu dekomprimieren, der allen hier präsentierten Spezifikationen entspricht. Ein konformer Kompressor (Compliant Compressor) muss Datensätze erzeugen, die allen hier präsentierten Spezifikationen entsprechen.

1.5. Definitionen von Begriffen und verwendeten Konventionen (Definitions of Terms and Conventions Used)

Byte: 8 Bits, die als Einheit gespeichert oder übertragen werden (identisch mit einem Oktett). Für diese Spezifikation ist ein Byte genau 8 Bits, selbst auf Maschinen, die ein Zeichen auf einer von acht verschiedenen Anzahl von Bits speichern. Siehe unten für die Nummerierung von Bits innerhalb eines Bytes.

Zeichenfolge (String): eine Folge beliebiger Bytes.

In einem Computer gespeicherte Bytes haben keine "Bitreihenfolge", da sie immer als Einheit behandelt werden. Ein Byte, das als Ganzzahl zwischen 0 und 255 betrachtet wird, hat jedoch ein höchstwertiges Bit (msb) und ein niedrigstwertiges Bit (lsb), und da wir Zahlen mit der höchstwertigen Ziffer links schreiben, schreiben wir auch Bytes mit dem höchstwertigen Bit links. In den folgenden Diagrammen nummerieren wir die Bits eines Bytes so, dass Bit 0 das niedrigstwertige Bit ist, d.h. die Bits sind nummeriert:

+--------+
|76543210|
+--------+

In einem Computer kann eine Zahl mehrere Bytes belegen. Alle Mehrbyte-Zahlen in dem hier beschriebenen Format werden mit dem niedrigstwertigen Byte (Least-Significant Byte) zuerst (an der niedrigeren Speicheradresse) gespeichert. Zum Beispiel wird die Dezimalzahl 520 wie folgt gespeichert:

    0        1
+--------+--------+
|00001000|00000010|
+--------+--------+
 ^        ^
 |        |
 |        + more significant byte = 2 x 256
 + less significant byte = 8

1.5.1. Verpackung in Bytes (Packing into Bytes)

Dieses Dokument befasst sich nicht mit der Frage, in welcher Reihenfolge die Bits eines Bytes auf einem bitsequenziellen Medium übertragen werden, da das hier beschriebene endgültige Datenformat eher byte- als bitorientiert ist. Wir beschreiben jedoch das komprimierte Blockformat (Compressed Block Format) im Folgenden als eine Sequenz von Datenelementen verschiedener Bitlängen, nicht als eine Sequenz von Bytes. Wir müssen daher spezifizieren, wie diese Datenelemente in Bytes gepackt werden, um die endgültige komprimierte Byte-Sequenz zu bilden:

Datenelemente werden in Bytes in aufsteigender Reihenfolge der Bitnummer innerhalb des Bytes gepackt, d.h. beginnend mit dem niedrigstwertigen Bit des Bytes.
Datenelemente außer Huffman-Codes (Huffman Code) werden beginnend mit dem niedrigstwertigen Bit des Datenelements gepackt.
Huffman-Codes werden beginnend mit dem höchstwertigen Bit des Codes gepackt.

Mit anderen Worten, wenn man die komprimierten Daten als eine Sequenz von Bytes ausdrucken würde, beginnend mit dem ersten Byte am rechten Rand und nach links fortschreitend, mit dem höchstwertigen Bit jedes Bytes wie üblich links, könnte man das Ergebnis von rechts nach links analysieren, mit Elementen fester Breite in der korrekten MSB-zu-LSB-Reihenfolge und Huffman-Codes in bitumgekehrter Reihenfolge (d.h. mit dem ersten Bit des Codes in der relativen LSB-Position).

Als Beispiel betrachten Sie das Packen der folgenden Datenelemente in eine Sequenz von 3 Bytes:

2-Bit-Wert 1 (binär 01)
3-Bit-Wert 2 (binär 010)
5-Bit-Wert 6 (binär 00110)
4-Bit-Code mit Bitmuster 1011 (wobei das erste Bit 1, das zweite Bit 0, das dritte Bit 1 und das vierte Bit 1 ist)
2-Bit-Wert 0 (binär 00)
4-Bit-Code mit Bitmuster 0011
5-Bit-Wert 31 (binär 11111)

Das folgende Diagramm zeigt, wie diese Elemente gepackt werden:

       Byte 0           Byte 1           Byte 2
   +---------------+----------------+----------------+
   |0|1|1|0|0|0|1|0|1|1|0|1|1|0|0|0|0|1|1|1|1|1|1|1|
   +---------------+----------------+----------------+
    ^ ^ ^   ^     ^ ^     ^       ^   ^             ^
    | | |   |     | |     |       |   |             |
    | | |   |     | |     |       |   +-------------|---+ 5-bit value 31
    | | |   |     | |     |       +-----------------|---|-+ 4-bit code 0011
    | | |   |     | |     +-----------------------+     |
    | | |   |     | |                             |     | 2-bit value 0
    | | |   |     | +-----------------------------+-----+ 4-bit code 1011
    | | |   +---+ 5-bit value 6
    | | +-----+ 3-bit value 2
    | +---+ 2-bit value 1

Quelle (Source): RFC 7932, Section 1
Offizieller Text (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt