Zum Hauptinhalt springen

RFC 8878 - Zstandard-Kompression und 'application/zstd' Medientyp

  • Status: Informational
  • Veröffentlicht: February 2021
  • Stream: IETF
  • Ersetzt: RFC8478
  • Errata: Keine Errata

Zusammenfassung (Abstract)​

Zstandard, oder "zstd" (ausgesprochen "zee standard"), ist ein verlustfreier Datenkomprimierungsmechanismus (Lossless Data Compression Mechanism). Dieses Dokument beschreibt diesen Mechanismus und registriert den Medientyp (Media Type), die Inhaltskodierung (Content Encoding) und das strukturierte Syntaxsuffix (Structured Syntax Suffix), die bei der Übertragung von zstd-komprimierten Inhalten über MIME verwendet werden.

Obwohl der Name Zstandard das Wort "standard" enthält, sollten Leser beachten, dass dieses Dokument keine Internet Standards Track-Spezifikation ist; es wird nur zu Informationszwecken veröffentlicht.

Dieses Dokument ersetzt und macht RFC 8478 obsolet.

Inhaltsverzeichnis (Contents)​

Kernabschnitte​

Standardisierungsabschnitte​

Anhänge (Appendices)​

Referenzen​

Technische Highlights​

🔬 Kernalgorithmen​

FSE (Finite State Entropy)

  • ANS-basierter Entropie-Encoder
  • Zustandsmaschinengesteuertes Kodieren/Dekodieren
  • Optimierte Wahrscheinlichkeitsverteilungstabelle

Huffman-Kodierung

  • Präfixcode-Konstruktion
  • Gewicht-zu-Codewort-Konvertierung
  • Umgekehrtes Bitstrom-Lesen

📊 Leistungsmerkmale​

Kompressionslevelbereich: -5 bis 22
Standardlevel: 3 (ausgewogene Geschwindigkeit und Kompression)
Kompressionsgeschwindigkeit: 100-500 MB/s (Level 1-3)
Dekompressionsgeschwindigkeit: 1000-1500 MB/s
Maximale Fenstergröße: 128 MB

🎯 Anwendungsszenarien​

  • Web-Content-Kompression: HTTP-Antworten, statische Ressourcen
  • Dateisystem: Btrfs, ZFS transparente Kompression
  • Datenbank: Kafka, MySQL, Clickhouse
  • Netzwerkübertragung: HTTP/2, gRPC, WebSocket

Verwandte Ressourcen​

Dokumentstatus​

Übersetzungsversion: Deutsch
Übersetzungsstatus: 🔄 In Bearbeitung
Letzte Aktualisierung: 2024-12-25
Technische Überprüfung: Ausstehend

1. Introduction (Einleitung)​

Zstandard, oder "zstd" (ausgesprochen "zee standard"), ist ein Datenkomprimierungsmechanismus (Data Compression Mechanism), ähnlich wie gzip [RFC1952].

Trotz der Verwendung des Wortes "standard" als Teil seines Namens werden die Leser darauf hingewiesen, dass dieses Dokument keine Internet Standards Track Spezifikation ist; es wird nur zu Informationszwecken veröffentlicht.

Dieses Dokument beschreibt das Zstandard-Format. Um den Transport eines mit Zstandard komprimierten Datenobjekts zu ermöglichen, registriert dieses Dokument außerdem einen Medientyp (Media Type), eine Inhaltscodierung (Content Encoding) und ein strukturiertes Syntax-Suffix (Structured Syntax Suffix), die zur Identifizierung solcher Inhalte verwendet werden können, wenn sie in einer Nutzlast (Payload) verwendet werden.

2. Definitions (Definitionen)​

Einige Begriffe, die an anderer Stelle in diesem Dokument verwendet werden, werden hier zur Klarheit definiert.

uncompressed (unkomprimiert) : Beschreibt eine beliebige Menge von Bytes in ihrer ursprünglichen Form, bevor sie einer Komprimierung unterzogen werden.

compressed (komprimiert) : Beschreibt das Ergebnis der Verarbeitung einer Menge von Bytes durch diesen Mechanismus. Die ursprüngliche Eingabe wurde somit komprimiert.

decompressed (dekomprimiert) : Beschreibt das Ergebnis der Verarbeitung einer Menge von Bytes durch die Umkehrung dieses Mechanismus. Wenn dies erfolgreich ist, sind die dekomprimierte Nutzlast (Decompressed Payload) und die unkomprimierte Nutzlast (Uncompressed Payload) nicht zu unterscheiden.

encode (kodieren) : Der Prozess der Übersetzung von Daten von einer Form in eine andere; dies kann Komprimierung beinhalten oder sich auf andere Übersetzungen beziehen, die als Teil dieser Spezifikation durchgeführt werden.

decode (dekodieren) : Das Gegenteil von "encode"; beschreibt einen Prozess der Umkehrung einer vorherigen Kodierung, um den ursprünglichen Inhalt wiederherzustellen.

frame (Rahmen) : Mit Zstandard komprimierter Inhalt wird in einen Zstandard-Rahmen umgewandelt. Mehrere Rahmen können an eine einzelne Datei oder einen Stream angehängt werden. Ein Rahmen ist vollständig unabhängig, hat einen definierten Anfang und ein Ende und verfügt über eine Reihe von Parametern, die dem Decoder mitteilen, wie er dekomprimiert werden soll.

block (Block) : Ein Rahmen kapselt einen oder mehrere Blöcke. Jeder Block enthält beliebigen Inhalt, der durch seinen Header beschrieben wird, und hat eine garantierte maximale Inhaltsgröße, die von den Rahmenparametern abhängt. Im Gegensatz zu Rahmen hängt jeder Block von vorherigen Blöcken für die ordnungsgemäße Dekodierung ab. Allerdings kann jeder Block dekomprimiert werden, ohne auf seinen Nachfolger zu warten, wodurch Streaming-Operationen (Streaming Operations) ermöglicht werden.

natural order (natürliche Reihenfolge) : Eine Sequenz oder Reihenfolge von Objekten oder Werten, die typisch für diese Art von Objekt oder Wert ist. Eine Menge eindeutiger Ganzzahlen befindet sich beispielsweise in "natürlicher Reihenfolge", wenn beim Fortschreiten von einem Element in der Menge oder Sequenz zum nächsten niemals eine Wertabnahme auftritt.

Die Namenskonvention für Bezeichner innerhalb der Spezifikation ist Mixed_Case_With_Underscores (gemischte Groß-/Kleinschreibung mit Unterstrichen). Bezeichner in eckigen Klammern zeigen an, dass der Bezeichner im dargestellten Kontext optional ist.

3. Compression Algorithm (Komprimierungsalgorithmus)​

Dieser Abschnitt beschreibt den Zstandard-Algorithmus.

Der Zweck dieses Dokuments besteht darin, ein verlustfreies komprimiertes Datenformat (Lossless Compressed Data Format) zu definieren, das a) unabhängig von CPU-Typ, Betriebssystem, Dateisystem und Zeichensatz ist, b) für Dateikompression sowie Pipe- und Streaming-Kompression (Pipe and Streaming Compression) unter Verwendung des Zstandard-Algorithmus geeignet ist. Der Text dieser Spezifikation setzt voraus, dass der Leser über grundlegende Programmierkenntnisse auf Bitebene und anderen primitiven Datendarstellungen verfügt.

Daten können erzeugt oder konsumiert werden, selbst für beliebig lange sequenziell präsentierte Eingabedatenströme, unter Verwendung nur einer a priori begrenzten Menge an Zwischenspeicher (A Priori Bounded Amount of Intermediate Storage); daher kann es für Datenkommunikation verwendet werden. Das Format verwendet die Zstandard-Komprimierungsmethode und die optionale xxHash-64-Prüfsummenmethode [XXHASH], um Datenbeschädigung (Data Corruption) zu erkennen.

Das in dieser Spezifikation definierte Datenformat versucht nicht, Direktzugriff (Random Access) auf komprimierte Daten zu ermöglichen.

Sofern unten nicht anders angegeben, muss ein konformer Kompressor (Compliant Compressor) Datensätze erzeugen, die den hier festgelegten Spezifikationen entsprechen. Er muss jedoch nicht alle Optionen unterstützen.

Ein konformer Dekompressor (Compliant Decompressor) muss in der Lage sein, mindestens einen Satz von Arbeitsparametern zu dekomprimieren, der den hier festgelegten Spezifikationen entspricht. Er kann auch informative Felder (Informative Fields) wie Prüfsummen ignorieren. Wann immer er einen im komprimierten Stream definierten Parameter nicht unterstützt, muss er einen eindeutigen Fehlercode (Unambiguous Error Code) und eine zugehörige Fehlermeldung erzeugen, die erklärt, welcher Parameter nicht unterstützt wird.

Diese Spezifikation ist für Software-Implementierer gedacht, die Daten in das Zstandard-Format komprimieren und/oder aus dem Zstandard-Format dekomprimieren möchten. Das Zstandard-Format wird durch eine Open-Source-Referenzimplementierung unterstützt, die in portablem C geschrieben ist und unter [ZSTD] verfügbar ist.

3.1 Frames (Rahmen)​

Zstandard-komprimierte Daten bestehen aus einem oder mehreren Rahmen (Frames). Jeder Rahmen ist unabhängig und kann unabhängig von anderen Rahmen dekomprimiert werden. Der dekomprimierte Inhalt mehrerer verketteter Rahmen ist die Verkettung des dekomprimierten Inhalts jedes Rahmens.

Für Zstandard sind zwei Rahmenformate definiert: Zstandard-Rahmen und übersprungbare Rahmen (Skippable Frames). Zstandard-Rahmen enthalten komprimierte Daten, während übersprungbare Rahmen benutzerdefinierte Metadaten (Custom User Metadata) enthalten.

3.1.1 Zstandard Frames (Zstandard-Rahmen)​

Die Struktur eines einzelnen Zstandard-Rahmens ist wie folgt:

+--------------------+------------+
|| Magic_Number       | 4 bytes    |
+--------------------+------------+
|| Frame_Header       | 2-14 bytes |
+--------------------+------------+
|| Data_Block         | n bytes    |
+--------------------+------------+
|| [More Data_Blocks] |            |
+--------------------+------------+
|| [Content_Checksum] | 4 bytes    |
+--------------------+------------+

Tabelle 1: Struktur eines einzelnen Zstandard-Rahmens

Magic_Number (Magische Zahl) : 4 Bytes, Little-Endian-Format. Wert: 0xFD2FB528.

Frame_Header (Rahmen-Header) : 2 bis 14 Bytes, siehe Abschnitt 3.1.1.1.

Data_Block (Datenblock) : Siehe Abschnitt 3.1.1.2. Hier erscheinen die Daten.

Content_Checksum (Inhaltsprüfsumme) : Optionale 32-Bit-Prüfsumme, nur vorhanden, wenn Content_Checksum_Flag gesetzt ist. Die Inhaltsprüfsumme ist das Ergebnis der XXH64()-Hashfunktion [XXHASH] mit den ursprünglichen (dekodierten) Daten als Eingabe und Seed Null. Die unteren 4 Bytes der Prüfsumme werden im Little-Endian-Format gespeichert.

Die Wahl der magischen Zahl ist so getroffen, dass die Wahrscheinlichkeit verringert wird, sie am Anfang einer beliebigen Datei zu finden. Sie vermeidet triviale Muster (0x00, 0xFF, wiederholte Bytes, inkrementierende Bytes usw.), enthält Bytewerte außerhalb des ASCII-Bereichs und wird nicht in den UTF-8-Raum abgebildet, was alles die Wahrscheinlichkeit verringert, dass sie oben in einer Textdatei erscheint.

3.1.1.1 Frame Header (Rahmen-Header)​

Die Größe des Rahmen-Headers ist variabel, minimal 2 Bytes und maximal 14 Bytes, abhängig von optionalen Parametern. Die Struktur von Frame_Header ist wie folgt:

+-------------------------+-----------+
|| Frame_Header_Descriptor | 1 byte    |
+-------------------------+-----------+
|| [Window_Descriptor]     | 0-1 byte  |
+-------------------------+-----------+
|| [Dictionary_ID]         | 0-4 bytes |
+-------------------------+-----------+
|| [Frame_Content_Size]    | 0-8 bytes |
+-------------------------+-----------+

Tabelle 2: Struktur von Frame_Header

(Da der Inhalt von Abschnitt 3.1.1.1 und seinen Unterabschnitten zu lang ist, beziehen Sie sich bitte für detaillierte Beschreibungen der Bitfelder, Window Descriptor, Dictionary_ID, Frame_Content_Size und andere technische Details auf das vollständige RFC 8878-Dokument)

Hinweis: Abschnitt 3 enthält viele technische Details, einschließlich:

  • 3.1.1.2 Blocks (Blockstruktur)
  • 3.1.1.3 Compressed Blocks (Komprimierte Blöcke, enthält Literals und Sequences)
  • 3.1.1.4 Sequence Execution (Sequenzausführung)
  • 3.1.1.5 Repeat Offsets (Wiederholungsoffsets)
  • 3.1.2 Skippable Frames (Übersprungbare Rahmen)

Vollständige technische Implementierungsdetails finden Sie im RFC 8878-Originaltext: https://www.rfc-editor.org/rfc/rfc8878.txt

3.1.1.1. Frame Header (Rahmen-Header)​

Die Größe des Rahmen-Headers ist variabel, minimal 2 Byte und maximal 14 Byte, abhängig von optionalen Parametern. Die Struktur von Frame_Header ist wie folgt:

+-------------------------+-----------+
|| Frame_Header_Descriptor | 1 byte    |
+-------------------------+-----------+
|| [Window_Descriptor]     | 0-1 byte  |
+-------------------------+-----------+
|| [Dictionary_ID]         | 0-4 bytes |
+-------------------------+-----------+
|| [Frame_Content_Size]    | 0-8 bytes |
+-------------------------+-----------+

Tabelle 2: Struktur von Frame_Header

3.1.1.1.1. Frame_Header_Descriptor (Rahmen-Header-Descriptor)​

Das erste Byte des Headers wird als Frame_Header_Descriptor bezeichnet. Es beschreibt, welche anderen Felder vorhanden sind. Das Decodieren dieses Bytes reicht aus, um die Größe von Frame_Header zu bestimmen.

Bitnummer (Bit Number)Feldname (Field Name)
7-6Frame_Content_Size_Flag
5Single_Segment_Flag
4(unbenutzt, unused)
3(reserviert, reserved)
2Content_Checksum_Flag
1-0Dictionary_ID_Flag

Tabelle 3: Frame_Header_Descriptor

In Tabelle 3 ist Bit 7 das höchstwertige Bit und Bit 0 das niederwertigste Bit.

3.1.1.1.1.1. Frame_Content_Size_Flag (Rahmen-Inhaltsgröße-Flag)​

Dies ist ein 2-Bit-Flag (entspricht Frame_Header_Descriptor rechts verschoben um 6 Bits), das angibt, ob Frame_Content_Size (dekomprimierte Datengröße) im Header bereitgestellt wird. Frame_Content_Size_Flag liefert FCS_Field_Size, die Anzahl der Bytes, die Frame_Content_Size gemäß Tabelle 4 verwendet:

Frame_Content_Size_Flag0123
FCS_Field_Size0 oder 1248

Tabelle 4: Frame_Content_Size_Flag liefert FCS_Field_Size

Wenn Frame_Content_Size_Flag 0 ist, hängt FCS_Field_Size von Single_Segment_Flag ab: Wenn Single_Segment_Flag gesetzt ist, ist FCS_Field_Size 1. Andernfalls ist FCS_Field_Size 0; Frame_Content_Size wird nicht bereitgestellt.

3.1.1.1.1.2. Single_Segment_Flag (Einzelsegment-Flag)​

Wenn dieses Flag gesetzt ist, müssen die Daten in einem einzelnen zusammenhängenden Speichersegment regeneriert werden.

In diesem Fall wird das Window_Descriptor-Byte übersprungen, aber Frame_Content_Size muss vorhanden sein. Daher muss der Decoder ein Speichersegment zuweisen, dessen Größe gleich oder größer als Frame_Content_Size ist.

Um den Decoder vor unzumutbaren Speicheranforderungen zu schützen, ist es dem Decoder gestattet, komprimierte Rahmen abzulehnen, die Speichergrößen anfordern, die über den vom Decoder autorisierten Bereich hinausgehen.

Für eine breitere Kompatibilität wird empfohlen, dass Decoder mindestens eine Speichergröße von 8 MB unterstützen. Dies ist nur eine Empfehlung; jeder Decoder kann basierend auf lokalen Einschränkungen frei höhere oder niedrigere Grenzen unterstützen.

3.1.1.1.1.3. Unused Bit (Unbenutztes Bit)​

Ein Decoder, der dieser Version der Spezifikation entspricht, darf dieses Bit nicht interpretieren. Es kann in zukünftigen Versionen verwendet werden, um Attribute darzustellen, die für die korrekte Dekodierung des Rahmens nicht erforderlich sind. Ein Encoder, der dieser Spezifikation entspricht, muss dieses Bit auf Null setzen.

3.1.1.1.1.4. Reserved Bit (Reserviertes Bit)​

Dieses Bit ist für zukünftige Funktionen reserviert. Sein Wert muss Null sein. Ein Decoder, der dieser Version der Spezifikation entspricht, muss sicherstellen, dass es nicht gesetzt ist. Dieses Bit kann in zukünftigen Revisionen verwendet werden, um Funktionen darzustellen, die interpretiert werden müssen, um den Rahmen korrekt zu dekodieren.

3.1.1.1.1.5. Content_Checksum_Flag (Inhalts-Prüfsummen-Flag)​

Wenn dieses Flag gesetzt ist, ist am Ende des Rahmens eine 32-Bit-Content_Checksum vorhanden. Siehe die obige Beschreibung von Content_Checksum.

3.1.1.1.1.6. Dictionary_ID_Flag (Wörterbuch-ID-Flag)​

Dies ist ein 2-Bit-Flag (= Frame_Header_Descriptor & 0x3), das angibt, ob eine Wörterbuch-ID im Header bereitgestellt wird. Es gibt auch die Größe dieses Felds als DID_Field_Size an:

Dictionary_ID_Flag0123
DID_Field_Size0124

Tabelle 5: Dictionary_ID_Flag

3.1.1.1.2. Window Descriptor (Fenster-Descriptor)​

Dies bietet eine Garantie für den minimalen Speicherpuffer, der zum Dekomprimieren des Rahmens erforderlich ist. Diese Information ist wichtig, damit der Decoder ausreichend Speicher zuweisen kann.

Das Window_Descriptor-Byte ist optional. Wenn Single_Segment_Flag gesetzt ist, ist Window_Descriptor nicht vorhanden. In diesem Fall ist Window_Size gleich Frame_Content_Size, und sein Wert kann von 0 bis 2^64 - 1 Bytes (16 ExaBytes) reichen.

Bitnummer (Bit Number)7-32-0
Feldname (Field Name)ExponentMantissa (Mantisse)

Tabelle 6: Window_Descriptor

Die minimale Speicherpuffergröße wird als Window_Size bezeichnet. Sie wird durch folgende Formel beschrieben:

windowLog = 10 + Exponent;
windowBase = 1 << windowLog;
windowAdd = (windowBase / 8) * Mantissa;
Window_Size = windowBase + windowAdd;

Die minimale Window_Size beträgt 1 KB. Die maximale Window_Size beträgt (1<<41) + 7*(1<<38) Bytes, d.h. 3.75 TB.

Im Allgemeinen tendieren größere Window_Size-Werte dazu, das Kompressionsverhältnis zu verbessern, auf Kosten erhöhter Speichernutzung.

Um komprimierte Daten korrekt zu dekodieren, muss der Decoder einen Puffer von mindestens Window_Size Bytes zuweisen.

Um den Decoder vor unzumutbaren Speicheranforderungen zu schützen, ist es dem Decoder gestattet, komprimierte Rahmen abzulehnen, die Speichergrößen anfordern, die über den vom Decoder autorisierten Bereich hinausgehen.

Um die Interoperabilität zu verbessern, wird empfohlen, dass Decoder Window_Size-Werte bis zu 8 MB unterstützen und Encoder keine Rahmen generieren, die eine Window_Size von mehr als 8 MB erfordern. Dies ist nur eine Empfehlung, und Decoder können basierend auf lokalen Einschränkungen frei höhere oder niedrigere Grenzen unterstützen.

3.1.1.1.3. Dictionary_ID (Wörterbuch-ID)​

Dies ist ein Feld variabler Größe, das die Wörterbuch-ID enthält, die erforderlich ist, um den Rahmen korrekt zu dekodieren. Dieses Feld ist optional. Wenn es nicht vorhanden ist, liegt es am Decoder zu entscheiden, welches Wörterbuch verwendet werden soll.

Die Größe des Dictionary_ID-Felds wird von DID_Field_Size bereitgestellt. DID_Field_Size wird direkt vom Wert von Dictionary_ID_Flag abgeleitet. Ein Byte kann IDs von 0-255 darstellen; 2 Bytes können IDs von 0-65535 darstellen; 4 Bytes können IDs von 0-4294967295 darstellen. Das Format ist Little-Endian.

Es ist erlaubt, eine große 4-Byte-Wörterbuch-ID zu verwenden, um eine kleine ID (z.B. 13) darzustellen, auch wenn dies ineffizient ist.

In privaten Umgebungen kann jede Wörterbuch-ID verwendet werden. Für Rahmen und Wörterbücher, die im öffentlichen Raum verteilt werden, muss Dictionary_ID jedoch sorgfältig zugewiesen werden. Die folgenden Bereiche sind nur für bei IANA registrierte Wörterbücher reserviert (siehe Abschnitt 7.4):

  • Niedriger Bereich (low range): <= 32767
  • Hoher Bereich (high range): >= (1 << 31)

Jeder andere Wert von Dictionary_ID kann durch private Vereinbarung zwischen Teilnehmern verwendet werden.

Jede Nutzlast, die zur Dekompression eingereicht wird und auf eine nicht registrierte reservierte Wörterbuch-ID verweist, führt zu einem Fehler.

3.1.1.1.4. Frame_Content_Size (Rahmen-Inhaltsgröße)​

Dies ist die ursprüngliche (unkomprimierte) Größe. Diese Information ist optional. Frame_Content_Size verwendet eine variable Anzahl von Bytes, die von FCS_Field_Size bereitgestellt wird. FCS_Field_Size wird vom Wert von Frame_Content_Size_Flag bereitgestellt. FCS_Field_Size kann gleich 0 (nicht vorhanden), 1, 2, 4 oder 8 Bytes sein.

FCS Field Size (Feldgröße)Range (Bereich)
0unknown (unbekannt)
10 - 255
2256 - 65791
40 - 2^32 - 1
80 - 2^64 - 1

Tabelle 7: Frame_Content_Size

Das Frame_Content_Size-Format ist Little-Endian. Wenn FCS_Field_Size 1, 4 oder 8 Bytes beträgt, wird der Wert direkt gelesen. Wenn FCS_Field_Size 2 beträgt, wird ein Offset von 256 hinzugefügt. Es ist erlaubt, jede kompatible Variante zu verwenden, um eine kleine Größe (z.B. 18) darzustellen, auch wenn dies ineffizient ist.

3.1.1.2. Blocks (Blöcke)​

Nach Magic_Number und Frame_Header folgen mehrere Blöcke. Jeder Rahmen muss mindestens 1 Block haben, aber es gibt keine Obergrenze für die Anzahl der Blöcke pro Rahmen.

Die Struktur eines Blocks ist wie folgt:

+==============+===============+
|| Block_Header | Block_Content |
+==============+===============+
||   3 bytes    |    n bytes    |
+--------------+---------------+

Tabelle 8: Struktur eines Blocks

Block_Header verwendet 3 Bytes, geschrieben unter Verwendung der Little-Endian-Konvention. Es enthält drei Felder:

Last_BlockBlock_TypeBlock_Size
bit 0bits 1-2bits 3-23

Tabelle 9: Block_Header

3.1.1.2.1. Last_Block (Letzter Block)​

Das niedrigstwertige Bit (Last_Block) zeigt an, ob dies der letzte Block ist. Der Rahmen endet nach diesem letzten Block. Ihm kann eine optionale Content_Checksum folgen (siehe Abschnitt 3.1.1).

3.1.1.2.2. Block_Type (Blocktyp)​

Die nächsten 2 Bits repräsentieren den Block_Type. Es gibt vier Blocktypen:

Value (Wert)Block_Type (Blocktyp)
0Raw_Block (Rohblock)
1RLE_Block (RLE-Block)
2Compressed_Block (Komprimierter Block)
3Reserved (Reserviert)

Tabelle 10: Vier Blocktypen

Raw_Block (Rohblock) : Dies ist ein unkomprimierter Block. Block_Content enthält Block_Size Bytes.

RLE_Block (RLE-Block) : Dies ist ein einzelnes Byte, das Block_Size-mal wiederholt wird. Block_Content besteht aus einem einzelnen Byte. Auf der Dekompressionsseite muss dieses Byte Block_Size-mal wiederholt werden.

Compressed_Block (Komprimierter Block) : Dies ist der in Abschnitt 3.1.1.3 beschriebene komprimierte Block. Block_Size ist die Länge von Block_Content, d.h. der komprimierten Daten. Die dekomprimierte Größe ist unbekannt, aber ihr maximaler möglicher Wert ist garantiert (siehe unten).

Reserved (Reserviert) : Dies ist kein Block. Dieser Wert kann mit der aktuellen Spezifikation nicht verwendet werden. Wenn ein solcher Wert vorhanden ist, wird er als beschädigte Daten betrachtet, und ein spezifikationskonformer Decoder muss ihn ablehnen.

3.1.1.2.3. Block_Size (Blockgröße)​

Die oberen 21 Bits des Block_Header repräsentieren die Block_Size.

Wenn Block_Type Compressed_Block oder Raw_Block ist, ist Block_Size die Größe von Block_Content (enthält also nicht den Block_Header).

Wenn Block_Type RLE_Block ist, da die Größe von Block_Content immer 1 ist, repräsentiert Block_Size die Anzahl der Male, die dieses Byte wiederholt werden muss.

Block_Size wird durch Block_Maximum_Size begrenzt (siehe unten).

3.1.1.2.4. Block_Content and Block_Maximum_Size (Blockinhalt und maximale Blockgröße)​

Die Größe von Block_Content wird durch Block_Maximum_Size begrenzt, was das kleinere der beiden folgenden ist:

  • Window_Size
  • 128 KB

Block_Maximum_Size ist für einen gegebenen Rahmen konstant. Dieses Maximum gilt sowohl für die dekomprimierte Größe als auch für die komprimierte Größe eines beliebigen Blocks im Rahmen.

Die Begründung für diese Begrenzung ist, dass der Decoder diese Informationen zu Beginn des Rahmens lesen und sie verwenden kann, um Puffer zuzuweisen. Die Garantie der Blockgröße stellt sicher, dass der Puffer für alle nachfolgenden Blöcke eines gültigen Rahmens ausreichend ist.

Wenn ein komprimierter Block größer als ein unkomprimierter Block ist, wird empfohlen, stattdessen einen unkomprimierten Block (d.h. Raw_Block) zu senden.

3.1.1.3. Compressed Blocks (Komprimierte Blöcke)​

Um einen komprimierten Block zu dekomprimieren, muss die komprimierte Größe aus dem Block_Size-Feld innerhalb des Block_Header bereitgestellt werden.

Ein komprimierter Block besteht aus zwei Teilen: Literals_Section (Literal-Abschnitt, Abschnitt 3.1.1.3.1) und Sequences_Section (Sequenz-Abschnitt, Abschnitt 3.1.1.3.2). Die Ergebnisse dieser beiden Teile werden dann kombiniert, um in der Sequenzausführung (Abschnitt 3.1.1.4) dekomprimierte Daten zu erzeugen.

Um einen komprimierten Block zu dekodieren, werden folgende Elemente benötigt:

  • Zuvor dekodierte Daten, bis zu einer Entfernung von Window_Size oder dem Anfang des Rahmens, je nachdem, was kleiner ist. Im letzteren Fall wird Single_Segment_Flag gesetzt.

  • Liste "Neueste Offsets", aus dem vorherigen Compressed_Block.

  • Vorheriger Huffman-Baum, benötigt für Treeless_Literals_Block-Typ.

  • Vorherige Finite State Entropy (FSE) Dekodierungstabellen, benötigt für Repeat_Mode, für jeden Symboltyp (Literal-Längencodes, Übereinstimmungslängencodes, Offset-Codes).

Beachten Sie, dass Dekodierungstabellen nicht immer aus dem vorherigen Compressed_Block stammen:

  • Jede Dekodierungstabelle kann aus dem Wörterbuch stammen.
  • Der Huffman-Baum stammt aus dem vorherigen Compressed_Literals_Block.

3.1.1.3.1. Literals_Section_Header (Literal-Abschnitt-Header)​

Alle Literale werden im ersten Teil des Blocks neu zusammengesetzt. Sie können zuerst dekodiert und dann während der Sequenzausführung (siehe Abschnitt 3.1.1.4) kopiert werden, oder sie können während der Sequenzausführung on-the-fly dekodiert werden.

Literale können unkomprimiert gespeichert oder mit Huffman-Präfixcode komprimiert werden. Wenn komprimiert, kann eine optionale Baumbeschreibung vorhanden sein, gefolgt von 1 oder 4 Streams.

+----------------------------+
||  Literals_Section_Header   |
+----------------------------+
|| [Huffman_Tree_Description] |
+----------------------------+
||        [Jump_Table]        |
+----------------------------+
||          Stream_1          |
+----------------------------+
||         [Stream_2]         |
+----------------------------+
||         [Stream_3]         |
+----------------------------+
||         [Stream_4]         |
+----------------------------+

Tabelle 11: Komprimierte Literale

3.1.1.3.1.1. Literals_Section_Header (Literal-Abschnitt-Header)​

Dieses Feld beschreibt, wie Literale verpackt sind. Es ist ein byte-ausgerichtetes Bitfeld variabler Größe, das von 1 bis 5 Bytes reicht und die Little-Endian-Konvention verwendet.

FeldGröße
Literals_Block_Type2 bits
Size_Format1-2 bits
Regenerated_Size5-20 bits
[Compressed_Size]0-18 bits

Tabelle 12: Literals_Section_Header

In dieser Darstellung befinden sich die obersten Bits an der niedrigsten Position.

Das Literals_Block_Type-Feld verwendet die zwei niedrigsten Bits des ersten Bytes und beschreibt vier verschiedene Blocktypen:

Literals_Block_Type (Literal-Blocktyp)Value (Wert)
Raw_Literals_Block (Rohe Literale)0
RLE_Literals_Block (RLE-Literale)1
Compressed_Literals_Block (Komprimierte Literale)2
Treeless_Literals_Block (Baumlose Literale)3

Tabelle 13: Literals_Block_Type

Raw_Literals_Block (Rohe Literale) : Literale werden unkomprimiert gespeichert. Literals_Section_Content ist Regenerated_Size.

RLE_Literals_Block (RLE-Literale) : Literale bestehen aus einem einzelnen Bytewert, der Regenerated_Size-mal wiederholt wird. Literals_Section_Content ist 1.

Compressed_Literals_Block (Komprimierte Literale) : Dies ist ein Standard-Huffman-komprimierter Block, der mit einer Huffman-Baumbeschreibung beginnt. Details siehe unten. Literals_Section_Content ist Compressed_Size.

Treeless_Literals_Block (Baumlose Literale) : Dies ist ein Huffman-komprimierter Block, der den Huffman-Baum aus dem vorherigen Compressed_Literals_Block verwendet, oder wenn es keinen vorherigen Huffman-komprimierten Literal-Block gibt, aus dem Wörterbuch. Huffman_Tree_Description wird übersprungen. Beachten Sie, dass wenn dieser Modus ohne vorherige Huffman-Tabelle im Rahmen (oder Wörterbuch gemäß Abschnitt 5) ausgelöst wird, dies als Datenbeschädigung betrachtet werden sollte. Literals_Section_Content ist Compressed_Size.

Size_Format ist in zwei Familien unterteilt:

  • Für Raw_Literals_Block und RLE_Literals_Block muss nur Regenerated_Size dekodiert werden. Es gibt kein Compressed_Size-Feld.

  • Für Compressed_Block und Treeless_Literals_Block müssen sowohl Compressed_Size als auch Regenerated_Size (dekomprimierte Größe) dekodiert werden. Die Anzahl der Streams (1 oder 4) muss ebenfalls dekodiert werden.

Für Werte, die mehrere Bytes umfassen, ist die Konvention Little-Endian.

Size_Format für Raw_Literals_Block und RLE_Literals_Block verwendet 1 oder 2 Bits. Sein Wert ist (Literals_Section_Header[0]>>2) & 0x3.

  • Size_Format == 00 oder 10: Size_Format verwendet 1 Bit. Regenerated_Size verwendet 5 Bits (Wert 0-31). Literals_Section_Header verwendet 1 Byte. Regenerated_Size = Literal_Section_Header[0]>>3.

  • Size_Format == 01: Size_Format verwendet 2 Bits. Regenerated_Size verwendet 12 Bits (Wert 0-4095). Literals_Section_Header verwendet 2 Bytes. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4).

  • Size_Format == 11: Size_Format verwendet 2 Bits. Regenerated_Size verwendet 20 Bits (Wert 0-1048575). Literals_Section_Header verwendet 3 Bytes. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12).

Für diese Fälle existiert nur Stream_1. Beachten Sie, dass es erlaubt ist, ein langes Format zu verwenden, um einen kurzen Wert darzustellen (z.B. 13), auch wenn dies ineffizient ist.

Size_Format für Compressed_Literals_Block und Treeless_Literals_Block verwendet immer 2 Bits.

  • Size_Format == 00: Ein einzelner Stream. Sowohl Regenerated_Size als auch Compressed_Size verwenden 10 Bits (Wert 0-1023). Literals_Section_Header verwendet 3 Bytes.

  • Size_Format == 01: 4 Streams. Sowohl Regenerated_Size als auch Compressed_Size verwenden 10 Bits (Wert 0-1023). Literals_Section_Header verwendet 3 Bytes.

  • Size_Format == 10: 4 Streams. Sowohl Regenerated_Size als auch Compressed_Size verwenden 14 Bits (Wert 0-16383). Literals_Section_Header verwendet 4 Bytes.

  • Size_Format == 11: 4 Streams. Sowohl Regenerated_Size als auch Compressed_Size verwenden 18 Bits (Wert 0-262143). Literals_Section_Header verwendet 5 Bytes.

Sowohl Compressed_Size- als auch Regenerated_Size-Felder folgen der Little-Endian-Konvention. Beachten Sie, dass Compressed_Size, wenn vorhanden, die Größe der Huffman_Tree_Description einschließt.

3.1.1.3.1.2. Raw_Literals_Block (Rohe Literale)​

Die Daten in Stream_1 sind Regenerated_Size Bytes lang. Sie enthalten rohe Literaldaten, die während der Sequenzausführung (Abschnitt 3.1.1.3.2) verwendet werden.

3.1.1.3.1.3. RLE_Literals_Block (RLE-Literale)​

Stream_1 besteht aus einem einzelnen Byte, das Regenerated_Size-mal wiederholt werden sollte, um die dekodierten Literale zu erzeugen.

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block (Komprimierte und baumlose Literale)​

Beide Modi enthalten Huffman-kodierte Daten. Für Treeless_Literals_Block stammt die Huffman-Tabelle aus dem vorherigen komprimierten Literal-Block oder dem Wörterbuch; siehe Abschnitt 5.

3.1.1.3.1.5. Huffman_Tree_Description (Huffman-Baumbeschreibung)​

Dieser Teil ist nur vorhanden, wenn der Literals_Block_Type-Typ Compressed_Literals_Block (2) ist. Das Format der Huffman_Tree_Description finden Sie in Abschnitt 4.2.1. Die Größe der Huffman_Tree_Description wird während der Dekodierung bestimmt. Sie muss verwendet werden, um zu bestimmen, wo die Streams beginnen.

Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size

3.1.1.3.1.6. Jump_Table (Sprungtabelle)​

Die Jump_Table ist nur vorhanden, wenn es 4 Huffman-kodierte Streams gibt.

(Erinnerung: Huffman-komprimierte Daten bestehen aus 1 oder 4 Huffman-kodierten Streams.)

Wenn nur 1 Stream vorhanden ist, handelt es sich um einen einzelnen Bitstrom, der den verbleibenden gesamten Teil des Literal-Blocks einnimmt und wie in Abschnitt 4.2.2 beschrieben kodiert ist.

Wenn es 4 Streams gibt, bietet Literals_Section_Header nur genügend Informationen, um die dekomprimierte und komprimierte Größe aller 4 Streams kombiniert zu kennen. Die dekomprimierte Größe jedes Streams ist gleich (Regenerated_Size+3)/4, außer für den letzten Stream, der bis zu 3 Bytes kleiner sein kann, um die in Regenerated_Size angegebene Gesamtdekomprimierte Größe zu erreichen.

3.1.1.3.2. Sequences_Section (Sequenz-Abschnitt)​

Ein komprimierter Block ist ein Kontinuum von Sequenzen. Eine Sequenz ist ein Literal-Kopierbefehl, gefolgt von einem Übereinstimmungs-Kopierbefehl. Der Literal-Kopierbefehl gibt eine Länge an. Es ist die Anzahl der Bytes, die aus dem Literals_Section kopiert (oder extrahiert) werden sollen. Der Übereinstimmungs-Kopierbefehl gibt einen Offset und eine Länge an.

Wenn alle Sequenzen dekodiert wurden und im Literals_Section noch Literale übrig sind, werden diese Bytes am Ende des Blocks hinzugefügt.

Dies wird in Abschnitt 3.1.1.4 ausführlicher beschrieben.

Die Sequences_Section kombiniert alle zum Dekodieren der Befehle erforderlichen Symbole. Es gibt drei Symboltypen: Literal-Längencodes, Offset-Codes und Übereinstimmungslängencodes. Sie werden in einem einzelnen "Bitstrom" verschachtelt kodiert.

Die Sequences_Section beginnt mit einem Header, gefolgt von optionalen Wahrscheinlichkeitstabellen für jeden Symboltyp, dann dem Bitstrom.

Sequences_Section_Header
  [Literals_Length_Table]
  [Offset_Table]
  [Match_Length_Table]
  bitStream

Um die Sequences_Section zu dekodieren, muss ihre Größe bekannt sein. Diese Größe wird aus der Größe der Literals_Section abgeleitet:

Sequences_Section_Size = Block_Size - Literals_Section_Header 
                         - Literals_Section_Content

3.1.1.3.2.1. Sequences_Section_Header (Sequenz-Abschnitt-Header)​

Dieser Header besteht aus zwei Elementen:

  • Number_of_Sequences (Anzahl der Sequenzen)
  • Symbol_Compression_Modes (Symbol-Kompressionsmodi)

Number_of_Sequences​

Number_of_Sequences ist ein Feld variabler Größe, das 1 bis 3 Bytes verwendet. Wenn das erste Byte "byte0" ist:

  • if (byte0 == 0): Keine Sequenzen. Der Sequenzteil stoppt hier. Der dekomprimierte Inhalt ist vollständig als Literals_Section-Inhalt definiert. Im Repeat_Mode verwendete FSE-Tabellen werden nicht aktualisiert.

  • if (byte0 < 128): Number_of_Sequences = byte0. Verwendet 1 Byte.

  • if (byte0 < 255): Number_of_Sequences = ((byte0 - 128) << 8) + byte1. Verwendet 2 Bytes.

  • if (byte0 == 255): Number_of_Sequences = byte1 + (byte2 << 8) + 0x7F00. Verwendet 3 Bytes.

Symbol_Compression_Modes​

Symbol_Compression_Modes ist ein einzelnes Byte, das den Kompressionsmodus für jeden Symboltyp definiert.

Bitnummer (Bit Number)Feldname (Field Name)
7-6Literal_Lengths_Mode
5-4Offsets_Mode
3-2Match_Lengths_Mode
1-0Reserved (Reserviert)

Tabelle 14: Symbol_Compression_Modes

Das letzte Feld Reserved muss alles Null sein.

Literals_Lengths_Mode, Offsets_Mode und Match_Lengths_Mode definieren jeweils den Compression_Mode für Literal-Längencodes, Offset-Codes und Übereinstimmungslängencodes. Sie folgen derselben Aufzählung:

Value (Wert)Compression_Mode (Kompressionsmodus)
0Predefined_Mode (Vordefinierter Modus)
1RLE_Mode (RLE-Modus)
2FSE_Compressed_Mode (FSE-komprimierter Modus)
3Repeat_Mode (Wiederholungsmodus)

Tabelle 15: Literals_Lengths_Mode, Offsets_Mode und Match_Lengths_Mode

Predefined_Mode (Vordefinierter Modus) : Verwendet vordefinierte FSE (siehe Abschnitt 4.1) Verteilungstabelle, wie in Abschnitt 3.1.1.3.2.2 definiert. Es wird keine Verteilungstabelle vorhanden sein.

RLE_Mode (RLE-Modus) : Die Tabellenbeschreibung besteht aus einem Byte, das den Wert des Symbols enthält. Dieses Symbol wird für alle Sequenzen verwendet.

FSE_Compressed_Mode (FSE-komprimierter Modus) : Standard-FSE-Kompression. Es wird eine Verteilungstabelle vorhanden sein. Das Format dieser Verteilungstabelle wird in Abschnitt 4.1.1 beschrieben. Beachten Sie, dass die maximal zulässige Präzision für Literal-Längencodes und Übereinstimmungslängencodes-Tabellen 9 beträgt, und die maximale Präzision für Offset-Codes-Tabelle 8 beträgt. Wenn nur ein Symbol vorhanden ist, darf dieser Modus nicht verwendet werden; stattdessen sollte RLE_Mode verwendet werden (obwohl jeder andere Modus auch funktioniert).

Repeat_Mode (Wiederholungsmodus) : Die Tabelle, die im vorherigen Compressed_Block mit Number_Of_Sequences > 0 verwendet wurde, wird erneut verwendet, oder wenn dies der erste Block ist, die Tabelle aus dem Wörterbuch. Beachten Sie, dass dies RLE_Mode einschließt, so dass wenn Repeat_Mode RLE_Mode folgt, dasselbe Symbol wiederholt wird. Es schließt auch Predefined_Mode ein, in diesem Fall hat Repeat_Mode dasselbe Ergebnis wie Predefined_Mode. Es wird keine Verteilungstabelle vorhanden sein. Wenn dieser Modus verwendet wird, ohne dass eine vorherige Sequenztabelle im Rahmen (oder Wörterbuch; siehe Abschnitt 5) zu wiederholen ist, sollte dies als Beschädigung betrachtet werden.

3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets (Sequenzcodes für Längen und Offsets)​

Jedes Symbol ist ein Code in seinem eigenen Kontext, der Baseline (Basislinie) und Number_of_Bits (Anzahl der Bits) zum Hinzufügen angibt. Codes werden FSE-komprimiert und im selben Bitstrom mit den ursprünglichen zusätzlichen Bits verschachtelt.

Literals Length Codes (Literal-Längencodes)​

Literal-Längencodes sind Werte von 0 bis 35 (einschließlich). Sie definieren Längen von 0 bis 131071 Bytes. Die Literal-Länge entspricht der dekodierten Baseline plus dem Ergebnis des Lesens von Number_of_Bits Bits aus dem Bitstrom (als Little-Endian-Wert).

Literals_Length_CodeBaselineNumber_of_Bits
0-15length0
16161
17181
18201
19221
20242
21282
22323
23403
24484
25646
261287
272568
285129
29102410
30204811
31409612
32819213
331638414
343276815
356553616

Tabelle 16: Literal-Längencodes

Match Length Codes (Übereinstimmungslängencodes)​

Übereinstimmungslängencodes sind Werte von 0 bis 52 (einschließlich). Sie definieren Längen von 3 bis 131074 Bytes. Die Übereinstimmungslänge entspricht der dekodierten Baseline plus dem Ergebnis des Lesens von Number_of_Bits Bits aus dem Bitstrom (als Little-Endian-Wert).

Match_Length_CodeBaselineNumber_of_Bits
0-31Match_Length_Code + 30
32351
33371
34391
35411
36432
37472
38513
39593
40674
41834
42995
431317
442598
455159
46102710
47205111
48409912
49819513
501638714
513277115
526553916

Tabelle 17: Übereinstimmungslängencodes

Offset Codes (Offset-Codes)​

Offset-Codes sind Werte von 0 bis N.

Der Decoder kann frei sein maximales unterstütztes N begrenzen. Es wird empfohlen, mindestens einen Wert von 22 zu unterstützen. Zum Zeitpunkt des Schreibens beträgt der maximale N-Wert, den der Referenz-Decoder unterstützt, 31.

Offset-Code ist auch die Anzahl der zusätzlichen Bits, die im Little-Endian-Verfahren gelesen werden, kann mit folgender Formel in Offset_Value konvertiert werden:

Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) Offset = Offset_Value - 3;

Dies bedeutet, dass der maximale Offset_Value (2^(N+1)) - 1 beträgt und Rückwärtsreferenzabstände von bis zu (2^(N+1)) - 4 unterstützt werden, aber durch die maximale Rückwärtsreferenzabstand begrenzt sind (siehe Abschnitt 3.1.1.1.2).

Offset_Values von 1 bis 3 sind speziell: Sie definieren "Wiederholungscodes". Dies wird in Abschnitt 3.1.1.5 ausführlicher beschrieben.

3.1.1.3.2.2. Default Distributions (Standard-Verteilungen)​

Wenn Predefined_Mode für einen Symboltyp ausgewählt wird, wird seine FSE-Dekodierungstabelle aus der hier definierten vordefinierten Verteilungstabelle generiert. Details zur Konvertierung dieser Verteilung in eine Dekodierungstabelle finden Sie in Abschnitt 4.1.

3.1.1.3.2.2.1. Literals Length Codes (Literal-Längencodes)​

Die Dekodierungstabelle verwendet ein Präzisionslog von 6 Bits (64 Zustände).

short literalsLength_defaultDistribution[36] =
  { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
    -1,-1,-1,-1
  };

3.1.1.3.2.2.2. Match Length Codes (Übereinstimmungslängencodes)​

Die Dekodierungstabelle verwendet ein Präzisionslog von 6 Bits (64 Zustände).

short matchLengths_defaultDistribution[53] =
  { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
    -1,-1,-1,-1,-1
  };

3.1.1.3.2.2.3. Offset Codes (Offset-Codes)​

Die Dekodierungstabelle verwendet ein Präzisionslog von 5 Bits (32 Zustände) und unterstützt einen maximalen N-Wert von 28, was Offset-Werte bis zu 536.870.908 ermöglicht.

Wenn eine Sequenz im komprimierten Block einen größeren Offset benötigt, kann sie nicht mit der Standard-Verteilung dargestellt werden.

short offsetCodes_defaultDistribution[29] =
  { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1
  };

3.1.1.4. Sequence Execution (Sequenzausführung)​

Sobald sowohl Literale als auch Sequenzen dekodiert sind, werden sie kombiniert, um den dekodierten Inhalt des Blocks zu erzeugen.

Jede Sequenz besteht aus einem Tupel (literals_length, offset_value, match_length), das wie im Sequences_Section (Abschnitt 3.1.1.3.2) beschrieben dekodiert wurde. Um eine Sequenz auszuführen, werden zunächst literals_length Bytes aus den dekodierten Literalen zur Ausgabe kopiert.

Dann werden match_length Bytes aus zuvor dekodierten Daten kopiert. Der Offset, von dem kopiert werden soll, wird durch offset_value bestimmt:

  • if Offset_Value > 3: dann ist der Offset Offset_Value - 3;

  • if Offset_Value is from 1-3: der Offset ist ein spezieller Wiederholungsoffset-Wert. Siehe Abschnitt 3.1.1.5 für Informationen darüber, wie der Offset in diesem Fall bestimmt wird.

Der Offset wird von der aktuellen Position (nach dem Kopieren der Literale) definiert, sodass ein Offset von 6 und eine Übereinstimmungslänge von 3 bedeutet, dass 3 Bytes von 6 Bytes zuvor kopiert werden sollten. Beachten Sie, dass alle Offsets, die zu zuvor dekodierten Daten führen, kleiner als die Window_Size sein müssen, die im Frame_Header_Descriptor (Abschnitt 3.1.1.1.1) definiert ist.

Ausführungsfluss Beispiel​

Beispiel 1: Grundlegende Sequenzausführung​

Angenommen, die Sequenz ist (literals_length=5, offset_value=10, match_length=4):

  1. Literale kopieren: Kopiere 5 Bytes aus dem Literal-Abschnitt zur Ausgabe
  2. Offset berechnen: Offset_Value=10 > 3, also Offset = 10 - 3 = 7
  3. Übereinstimmung kopieren: Kopiere 4 Bytes von 7 Bytes vor der Ausgabeposition

Beispiel 2: Verwendung eines Wiederholungsoffsets​

Angenommen, die Sequenz ist (literals_length=3, offset_value=1, match_length=8):

  1. Literale kopieren: Kopiere 3 Bytes aus dem Literal-Abschnitt zur Ausgabe
  2. Wiederholungsoffset verwenden: offset_value=1 bedeutet Repeated_Offset1 verwenden
  3. Übereinstimmung kopieren: Kopiere 8 Bytes von der Repeated_Offset1-Position

Wichtige Einschränkungen​

  1. Window_Size-Begrenzung: Alle Offsets müssen < Window_Size sein
  2. Datenintegrität: Stellen Sie sicher, dass Offsets nicht den Bereich der dekodierten Daten überschreiten
  3. Literale erschöpft: Nach Ausführung aller Sequenzen werden verbleibende Literale am Ende der Ausgabe angehängt

3.1.1.5. Repeat Offsets (Wiederholungsoffsets)​

Wie oben beschrieben, definieren die ersten drei Werte Wiederholungsoffsets; wir bezeichnen sie als Repeated_Offset1, Repeated_Offset2 und Repeated_Offset3. Sie sind nach Aktualität geordnet, wobei Repeated_Offset1 "den neuesten" darstellt.

Wenn offset_value 1 ist, ist der verwendete Offset Repeated_Offset1, und so weiter.

Es gibt eine Ausnahme: Wenn die literals_length der aktuellen Sequenz 0 ist, werden die Wiederholungsoffsets um 1 verschoben, daher:

  • offset_value von 1 bedeutet Repeated_Offset2
  • offset_value von 2 bedeutet Repeated_Offset3
  • offset_value von 3 bedeutet Repeated_Offset1 - 1_byte

Initialisierung​

Für den ersten Block wird die Start-Offset-Historie mit folgenden Werten gefüllt:

  • Repeated_Offset1 = 1
  • Repeated_Offset2 = 4
  • Repeated_Offset3 = 8

Es sei denn, ein Wörterbuch wird verwendet, in diesem Fall stammen sie aus dem Wörterbuch.

Dann erhält jeder Block seine Start-Offset-Historie aus den Endwerten des neuesten Compressed_Block. Beachten Sie, dass Blöcke, die keine Compressed_Blocks sind, übersprungen werden; sie beeinflussen die Offset-Historie nicht.

Aktualisierungsregeln​

Während der Ausführung der Sequenzen eines Compressed_Block werden die Werte der Repeated_Offsets aktuell gehalten, sodass sie immer die drei zuletzt verwendeten Offsets darstellen. Um dies zu erreichen, werden sie nach Ausführung jeder Sequenz wie folgt aktualisiert:

Fall 1: Nicht-Wiederholungsoffset​

Wenn der offset_value der Sequenz nicht auf einen der Repeated_Offsets verweist (wenn er einen Wert größer als 3 hat oder wenn er den Wert 3 hat und die literals_length der Sequenz Null ist):

  • Die Werte der Repeated_Offsets werden um eins nach hinten verschoben
  • Repeated_Offset1 nimmt den Wert des gerade verwendeten Offsets an

Aktualisierungsformel:

Repeated_Offset3 = Repeated_Offset2
Repeated_Offset2 = Repeated_Offset1
Repeated_Offset1 = neuer Offset

Fall 2: Wiederholungsoffset​

Wenn der offset_value der Sequenz auf einen der Repeated_Offsets verweist (wenn er den Wert 1 oder 2 hat, oder wenn er den Wert 3 hat und die literals_length der Sequenz nicht null ist):

  • Die Repeated_Offsets werden neu geordnet
  • Repeated_Offset1 nimmt den Wert des verwendeten Repeated_Offset an
  • Vorhandene Werte werden vom ersten Repeated_Offset zurück zum vom offset_value gewählten Repeated_Offset verschoben

Dies führt effektiv eine einstufige Umhülldrehung dieser Offset-Werte durch, sodass ihre Reihenfolge wieder ihre Aktualität der Verwendung widerspiegelt.

Aktualisierungsbeispieltabelle​

Die folgende Tabelle zeigt die Werte bei Anwendung einer Reihe von Sequenzen auf Repeated_Offsets:

offset_valueliterals_lengthRepeated_Offset1Repeated_Offset2Repeated_Offset3Comment (Kommentar)
--148Startwert
111411111114Nicht-Wiederholung
122111114Wiederholung1; keine Änderung
222522222211111Nicht-Wiederholung
1114111111122221111Nicht-Wiederholung
333633333311112222Nicht-Wiederholung
222111133332222Wiederholung2; Tausch 1 und 2
333222211113333Wiederholung3; Rotation 3 zu 1
10222122221111Eingefügter analysierter Offset
10222222213333Wiederholung2

Tabelle 18: Repeated_Offsets

Sonderfallbehandlung​

Fall literals_length = 0​

Wenn literals_length = 0 ist, verschiebt sich die Interpretation von offset_value:

offset_valueTatsächlich verwendeter Offset
1Repeated_Offset2
2Repeated_Offset3
3Repeated_Offset1 - 1

Diese Sonderbehandlung dient der Optimierung aufeinanderfolgender Übereinstimmungskopiervorgänge.

Wichtige Erkenntnisse​

  1. Aktualitätsprinzip: Repeated_Offset1 ist immer der zuletzt verwendete Offset
  2. Automatische Aktualisierung: Offset-Historie wird nach jeder Sequenzausführung automatisch aktualisiert
  3. Wörterbuchunterstützung: Anfangswerte können aus dem Wörterbuch stammen
  4. Spezialverschiebung: Offset-Interpretation verschiebt sich, wenn literals_length=0

3.1.2. Skippable Frames (Überspringbare Rahmen)​

+==============+============+===========+
|| Magic_Number | Frame_Size | User_Data |
+==============+============+===========+
||   4 bytes    |  4 bytes   |  n bytes  |
+--------------+------------+-----------+

Tabelle 19: Überspringbare Rahmen

Überspringbare Rahmen ermöglichen das Einfügen von benutzerdefinierten Metadaten in einen Stream verketteter Rahmen.

Die in dieser Spezifikation definierten überspringbaren Rahmen sind mit überspringbaren Rahmen in [LZ4] kompatibel.

Aus Sicht eines kompatiblen Decoders müssen überspringbare Rahmen nur übersprungen werden, ihr Inhalt wird ignoriert, und die Dekodierung wird nach dem überspringbaren Rahmen fortgesetzt.

Es sollte beachtet werden, dass überspringbare Rahmen verwendet werden können, um verkettete Rahmenströme zu markieren, jeden Typ von Tracking-Informationen einzubetten (sogar nur einen Universally Unique Identifier (UUID)). Benutzer, die wachsam gegenüber solchen Möglichkeiten sind, sollten verkettete Rahmenströme scannen, um zu versuchen, solche Rahmen zur Analyse oder Entfernung zu erkennen.

Feldbeschreibungen​

Magic_Number (Magische Zahl)​

Größe: 4 Bytes, Little-Endian-Format
Wert: 0x184D2A5?, was jeden Wert von 0x184D2A50 bis 0x184D2A5F bedeutet

Alle 16 Werte identifizieren gültig überspringbare Rahmen. Diese Spezifikation legt keine spezifische Markierungsmethode für überspringbare Rahmen fest.

Bereich der magischen Zahl:

  • Minimalwert: 0x184D2A50
  • Maximalwert: 0x184D2A5F
  • Gesamt: 16 gültige magische Zahlen

Frame_Size (Rahmengröße)​

Größe: 4 Bytes, Little-Endian-Format, vorzeichenlose 32 Bit
Bedeutung: Die Größe der nachfolgenden User_Data in Bytes (ohne die magische Zahl und das Größenfeld selbst)

Dies bedeutet, dass User_Data nicht größer als (2^32 - 1) Bytes sein kann.

Maximale User_Data-Größe: 4.294.967.295 Bytes (ca. 4 GB)

User_Data (Benutzerdaten)​

Größe: Variabel (durch Frame_Size angegeben)
Inhalt: Beliebige Daten

Dieses Feld kann beliebigen Inhalt haben. Die Daten werden vom Decoder übersprungen.

Verwendungsszenarien​

1. Metadaten-Einbettung​

  • Versionsinformationen
  • Erstellungszeitstempel
  • Autorinformationen
  • Lizenzdaten

2. Wasserzeichen und Tracking​

  • UUID-Einbettung
  • Quellenverfolgung
  • Vertriebskanalidentifikation

3. Anwendungsspezifische Daten​

  • Benutzerdefinierte Header
  • Anwendungskonfiguration
  • Erweiterte Informationen

Kompatibilitätshinweise​

Decoder-Verhalten​

Ein spezifikationskonformer Decoder muss:

  1. Magische Zahl erkennen: Magische Zahlen im Bereich 0x184D2A5? erkennen
  2. Größe lesen: Das Frame_Size-Feld analysieren
  3. Daten überspringen: Frame_Size Bytes von User_Data überspringen
  4. Dekodierung fortsetzen: Nach dem überspringbaren Rahmen mit der Verarbeitung fortfahren

Encoder-Empfehlungen​

Encoder können:

  1. Beliebige Platzierung: Überspringbare Rahmen an jeder Position im Rahmenstrom einfügen
  2. Mehrere Rahmen: Mehrere überspringbare Rahmen einfügen
  3. Benutzerdefinierte Markierung: Eine der 16 magischen Zahlen für interne Markierung verwenden

Sicherheitsüberlegungen​

Datenschutzprobleme​

Überspringbare Rahmen können verwendet werden für:

  • Datenstrom-Tracking
  • Einbettung versteckter Informationen
  • Identifizierung der Datenquelle

Empfohlene Maßnahmen​

Für datenschutzbewusste Benutzer:

  1. Scan-Erkennung: Eingabestrom scannen, um überspringbare Rahmen zu erkennen
  2. Inhaltsanalyse: Inhalt von User_Data untersuchen
  3. Selektive Entfernung: Überspringbare Rahmen nach Bedarf entfernen
  4. Protokollierung: Erkannte überspringbare Rahmen zur Prüfung protokollieren

Beispiele​

UUID einbetten​

Magic_Number: 0x184D2A50
Frame_Size: 16 (0x10000000, Little-Endian)
User_Data: [16-Byte-UUID]

Zeitstempel einbetten​

Magic_Number: 0x184D2A51
Frame_Size: 8
User_Data: [8-Byte-Unix-Zeitstempel]

Kompatibilität mit LZ4​

Das Format überspringbarer Rahmen ist mit LZ4 kompatibel und ermöglicht:

  • Formatübergreifende Tool-Interoperabilität
  • Einheitliche Metadatenverarbeitung
  • Vereinfachte Decoder-Implementierung

Hinweis: Überspringbare Rahmen beeinflussen nicht den Inhalt der dekomprimierten Daten, nur die Metadaten des Streams.

4. Entropy Encoding (Entropiekodierung)​

Das Zstandard-Format verwendet zwei Arten der Entropiekodierung: FSE und Huffman-Kodierung. Huffman wird zur Komprimierung von Literalen (Literals) verwendet, während FSE für alle anderen Symbole (Literals_Length_Code, Match_Length_Code und Offset-Codes) und zur Komprimierung von Huffman-Headern verwendet wird.

4.1 FSE (Entropie mit endlichem Zustand)​

FSE, kurz für Finite State Entropy (Entropie mit endlichem Zustand), ist ein Entropie-Codec, der auf [ANS] basiert. Die FSE-Kodierung/Dekodierung beinhaltet einen Zustand (State), der zwischen Symbolen übertragen wird, daher muss die Dekodierung in entgegengesetzter Richtung zur Kodierung erfolgen. Daher werden alle FSE-Bitstreams vom Ende zum Anfang gelesen. Beachten Sie, dass die Reihenfolge der Bits im Stream nicht umgekehrt wird; sie werden einfach in umgekehrter Reihenfolge gelesen, als sie geschrieben wurden.

Weitere Details zu FSE finden Sie unter "FiniteStateEntropy" [FSE].

Die FSE-Dekodierung beinhaltet eine Dekodierungstabelle (Decoding Table), die eine Größe als Zweierpotenz hat und drei Elemente enthält: Symbol, Num_Bits (Anzahl der Bits) und Baseline (Basislinie). Der Logarithmus zur Basis 2 der Tabellengröße ist ihr Accuracy_Log (Genauigkeitsprotokoll). Ein FSE-Zustandswert repräsentiert einen Index in dieser Tabelle.

Um den anfänglichen Zustandswert zu erhalten, konsumieren Sie Accuracy_Log Bits aus dem Stream als Little-Endian-Wert. Das nächste Symbol im Stream ist das Symbol, das in der Tabelle für diesen Zustand angegeben ist. Um den nächsten Zustandswert zu erhalten, sollte der Decoder Num_Bits Bits aus dem Stream als Little-Endian-Wert konsumieren und diese zur Baseline hinzufügen.

4.1.1 FSE Table Description (FSE-Tabellenbeschreibung)​

Um FSE-Streams zu dekodieren, ist es notwendig, die Dekodierungstabelle zu konstruieren. Das Zstandard-Format kodiert FSE-Tabellenbeschreibungen wie hier beschrieben.

Eine FSE-Verteilungstabelle (Distribution Table) beschreibt die Wahrscheinlichkeiten aller Symbole von 0 bis zum letzten vorhandenen (einschließlich) auf einer normalisierten Skala von (1 &lt;&lt; Accuracy_Log). Beachten Sie, dass es zwei oder mehr Symbole mit von Null verschiedener Wahrscheinlichkeit geben muss.

Ein Bitstream wird vorwärts im Little-Endian-Stil gelesen. Es ist nicht notwendig, seine genaue Größe zu kennen, da die Größe vom Dekodierungsprozess entdeckt und gemeldet wird. Der Bitstream beginnt damit, auf welcher Skala er operiert. Wenn low4bits die niedrigsten 4 Bits des ersten Bytes bezeichnet, dann ist Accuracy_Log = low4bits + 5.

Darauf folgt jeder Symbolwert von 0 bis zum letzten vorhandenen. Die Anzahl der von jedem Feld verwendeten Bits ist variabel und hängt ab von:

Verbleibende Wahrscheinlichkeiten + 1 : Zum Beispiel, angenommen ein Accuracy_Log von 8 und angenommen, 100 Wahrscheinlichkeitspunkte wurden bereits verteilt, kann der Decoder jeden Wert von 0 bis (256 - 100 + 1) == 157, einschließlich, lesen. Daher muss er log₂(157) == 8 Bits lesen.

Dekodierter Wert : Kleine Werte verwenden 1 Bit weniger. Zum Beispiel, angenommen Werte von 0 bis 157, einschließlich, sind möglich, bleiben 255 - 157 = 98 Werte in einem 8-Bit-Feld übrig. Die ersten 98 Werte (also von 0 bis 97) verwenden nur 7 Bits, und Werte von 98 bis 157 verwenden 8 Bits. Dies wird durch das Schema in Tabelle 20 erreicht:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

Tabelle 20: Dekodierte Werte

Symbolwahrscheinlichkeiten werden nacheinander in Reihenfolge gelesen. Die Wahrscheinlichkeit wird aus dem dekodierten Wert (Value Decoded) unter Verwendung der Formel P = Value - 1 erhalten. Dies bedeutet, dass der Wert 0 zur negativen Wahrscheinlichkeit -1 wird. Dies ist eine spezielle Wahrscheinlichkeit, die "kleiner als 1" bedeutet. Ihre Auswirkung auf die Verteilungstabelle wird unten beschrieben. Zum Zweck der Berechnung der gesamten zugewiesenen Wahrscheinlichkeitspunkte zählt sie als 1.

Wenn ein Symbol eine Wahrscheinlichkeit von null hat, folgt ihm ein 2-Bit-Wiederholungsflag (Repeat Flag). Dieses Wiederholungsflag gibt an, wie viele Wahrscheinlichkeiten von Nullen dem aktuellen folgen. Es liefert eine Zahl von 0 bis 3. Wenn es eine 3 ist, folgt ein weiteres 2-Bit-Wiederholungsflag, und so weiter.

Wenn das letzte Symbol eine kumulative Summe von (1 &lt;&lt; Accuracy_Log) erreicht, ist die Dekodierung abgeschlossen. Wenn das letzte Symbol die kumulative Summe über (1 &lt;&lt; Accuracy_Log) hinausgehen lässt, wird die Verteilung als beschädigt betrachtet.

Schließlich kann der Decoder erkennen, wie viele Bytes in diesem Prozess verwendet wurden und wie viele Symbole vorhanden sind. Der Bitstream verbraucht eine runde Anzahl von Bytes. Jedes verbleibende Bit im letzten Byte wird einfach nicht verwendet.

Der Kontext, in dem die Tabelle verwendet werden soll, spezifiziert eine erwartete Anzahl von Symbolen. Diese erwartete Anzahl von Symbolen übersteigt niemals 256. Wenn die Anzahl der dekodierten Symbole nicht der erwarteten entspricht, sollte der Header als beschädigt betrachtet werden.

Die Verteilung normalisierter Wahrscheinlichkeiten reicht aus, um eine eindeutige Dekodierungstabelle zu erstellen. Die Tabelle hat eine Größe von (1 &lt;&lt; Accuracy_Log). Jede Zelle beschreibt das dekodierte Symbol und Anweisungen zum Erhalt des nächsten Zustands.

Symbole werden in ihrer natürlichen Reihenfolge nach "kleiner als 1"-Wahrscheinlichkeiten wie oben beschrieben gescannt. Symbolen mit dieser Wahrscheinlichkeit wird eine einzelne Zelle zugewiesen, beginnend am Ende der Tabelle und rückwärts gehend. Diese Symbole definieren eine vollständige Zustandsrücksetzung (Full State Reset), wobei Accuracy_Log Bits gelesen werden.

Alle verbleibenden Symbole werden in ihrer natürlichen Reihenfolge zugewiesen. Beginnend mit Symbol 0 und Tabellenposition 0 werden jedem Symbol so viele Zellen zugewiesen wie seine Wahrscheinlichkeit. Die Zellzuweisung ist verteilt, nicht linear; jede Nachfolgeposition folgt dieser Regel:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

Eine Position wird übersprungen, wenn sie bereits von einem Symbol mit "kleiner als 1"-Wahrscheinlichkeit belegt ist. Die Position wird zwischen Symbolen nicht zurückgesetzt; sie iteriert einfach durch jede Position in der Tabelle und wechselt zum nächsten Symbol, wenn genügend Zustände dem aktuellen zugewiesen wurden.

Das Ergebnis ist eine Liste von Zustandswerten. Jeder Zustand wird das aktuelle Symbol dekodieren.

Um die Number_of_Bits und Baseline zu erhalten, die für den nächsten Zustand erforderlich sind, ist es zunächst notwendig, alle Zustände in ihrer natürlichen Reihenfolge zu sortieren. Die niedrigeren Zustände benötigen 1 Bit mehr als höhere. Der Prozess wird für jedes Symbol wiederholt.

Zum Beispiel, angenommen ein Symbol hat eine Wahrscheinlichkeit von 5, erhält es fünf Zustandswerte. Zustände werden in natürlicher Reihenfolge sortiert. Die nächste Zweierpotenz ist 8. Der Wahrscheinlichkeitsraum wird in 8 gleiche Teile geteilt. Angenommen, der Accuracy_Log ist 7, definiert dies 128 Zustände, und jeder Anteil (geteilt durch 8) hat eine Größe von 16. Um 8 zu erreichen, zählen 8 - 5 = 3 niedrigste Zustände "doppelt", verdoppeln die Anzahl der Anteile (Breite 32) und benötigen im Prozess 1 Bit mehr.

Die Baseline wird beginnend von den höheren Zuständen mit weniger Bits zugewiesen und natürlich fortfahrend, dann beim ersten Zustand wieder aufnehmend, wobei jeder seine zugewiesene Breite von der Baseline nimmt.

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

Tabelle 21: Baseline-Zuweisungen

Der nächste Zustand wird aus dem aktuellen Zustand bestimmt, indem die erforderlichen Number_of_Bits gelesen und die angegebene Baseline hinzugefügt werden.

Siehe Anhang A für die Ergebnisse dieses Prozesses, die auf die Standardverteilungen angewendet werden.

4.2 Huffman Coding (Huffman-Kodierung)​

Zstandard Huffman-kodierte Streams werden rückwärts gelesen, ähnlich wie FSE-Bitstreams. Daher ist es notwendig, den Offset des letzten Bytes des Huffman-kodierten Streams zu kennen, um den Anfang des Bitstreams zu finden.

Nach dem Schreiben des letzten Bits, das Informationen enthält, schreibt der Kompressor ein einzelnes 1-Bit und füllt dann den Rest des Bytes mit 0-Bits. Das letzte Byte des komprimierten Bitstreams kann aus diesem Grund nicht 0 sein.

Beim Dekomprimieren ist das letzte Byte, das die Auffüllung enthält, das erste zu lesende Byte. Der Dekompressor muss bis zu 7 Bits der 0-Auffüllung sowie das erste auftretende 1-Bit überspringen. Danach beginnt der nützliche Teil des Bitstreams.

Der Bitstream enthält Huffman-kodierte Symbole in Little-Endian-Reihenfolge, mit den unten definierten Codes.

4.2.1 Huffman Tree Description (Huffman-Baumbeschreibung)​

Präfixkodierung (Prefix Coding) repräsentiert Symbole aus einem a priori bekannten Alphabet durch Bitsequenzen (Codewörter), ein Codewort für jedes Symbol, auf eine Weise, dass verschiedene Symbole durch Bitsequenzen unterschiedlicher Längen dargestellt werden können, aber ein Parser immer eindeutig eine kodierte Zeichenfolge Symbol für Symbol parsen kann.

Bei gegebenem Alphabet mit bekannten Symbolfrequenzen ermöglicht der Huffman-Algorithmus die Konstruktion eines optimalen Präfixcodes unter Verwendung der wenigsten Bits aller möglichen Präfixcodes für dieses Alphabet.

Der Präfixcode darf eine maximale Codelänge nicht überschreiten. Mehr Bits verbessern die Genauigkeit, führen aber zu einer größeren Header-Größe und erfordern mehr Speicher oder komplexere Dekodierungsoperationen. Diese Spezifikation begrenzt die maximale Codelänge auf 11 Bits.

Alle Literalwerte von null (einschließlich) bis zum letzten vorhandenen (ausschließlich) werden durch Weight (Gewicht) mit Werten von 0 bis Max_Number_of_Bits dargestellt. Die Transformation von Weight zu Number_of_Bits folgt diesem Pseudocode:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

Das Weight des letzten Symbols wird aus den zuvor dekodierten abgeleitet, indem zur nächsten Zweierpotenz vervollständigt wird. Diese Zweierpotenz ergibt Max_Number_of_Bits, die Tiefe des aktuellen Baums.

(Fortsetzung mit Tabellen 22-26 und Huffman-Kodierungsdetails)

5. Dictionary Format (Wörterbuchformat)​

Zstandard ist mit „Raw Content Dictionaries" (Rohinhaltswörterbüchern) kompatibel, ohne jegliche Formatbeschränkung, außer dass sie mindestens 8 Bytes groß sein müssen. Diese Wörterbücher funktionieren, als wären sie nur der Inhaltsteil eines formatierten Wörterbuchs.

Allerdings folgen die von zstd --train in der Referenzimplementierung erstellten Wörterbücher einem spezifischen Format, das hier beschrieben wird.

Wörterbücher sind nicht im komprimierten Inhalt enthalten, sondern werden out-of-band bereitgestellt. Das heißt, die Dictionary_ID identifiziert, welches Wörterbuch verwendet werden soll, aber diese Spezifikation beschreibt nicht den Mechanismus zum Abrufen des Wörterbuchs vor der Verwendung während der Kompression oder Dekompression.

Ein Wörterbuch hat eine Größe, die durch Puffergrenzen oder Dateigröße definiert ist. Das allgemeine Format ist:

+==============+===============+================+=========+
| Magic_Number | Dictionary_ID | Entropy_Tables | Content |
+==============+===============+================+=========+

Tabelle 27: Allgemeines Wörterbuchformat

Magic_Number (Magische Zahl) : 4-Byte-ID, Wert 0xEC30A437, Little-Endian-Format.

Dictionary_ID (Wörterbuch-ID) : 4 Bytes, im Little-Endian-Format gespeichert. Die Dictionary_ID kann jeden Wert haben, außer 0 (was anzeigt, dass keine Dictionary_ID vorhanden ist). Decoder verwenden diese, um zu überprüfen, ob sie das richtige Wörterbuch verwenden. Wenn der Frame in einer privaten Umgebung verteilt wird, kann jede Dictionary_ID verwendet werden. Für die öffentliche Verteilung komprimierter Frames sind jedoch die folgenden Bereiche reserviert und dürfen nicht verwendet werden:

  • Niedriger Bereich: &lt;= 32767
  • Hoher Bereich: >= 2³¹

Entropy_Tables (Entropietabellen) : Folgen dem gleichen Format wie Tabellen in komprimierten Blöcken. Informationen zum Dekodieren dieser Tabellen finden Sie in den entsprechenden FSE- und Huffman-Abschnitten. Sie werden in der folgenden Reihenfolge gespeichert: Huffman-Tabelle für Literale, FSE-Tabelle für Offsets, FSE-Tabelle für Match-Längen und FSE-Tabelle für Literal-Längen. Diese Tabellen füllen den Wiederholungsstatistik-Literal-Modus (Repeat Stats Literals Mode) und den Wiederholungsverteilungsmodus (Repeat Distribution Mode) der Sequenzdekodierung. Schließlich gibt es 3 Offset-Werte, die die wiederholten Offsets füllen (anstatt {1,4,8} zu verwenden), nacheinander gespeichert, jeweils 4 Bytes Little-Endian, insgesamt 12 Bytes. Jeder wiederholte Offset muss einen Wert kleiner als die Wörterbuchgröße haben.

Content (Inhalt) : Der Rest des Wörterbuchs ist sein Inhalt. Der Inhalt dient als „Vergangenheit" vor den zu komprimierenden oder dekomprimierenden Daten, sodass er in Sequenzbefehlen (Sequence Commands) referenziert werden kann. Solange die Menge der aus diesem Frame dekodierten Daten kleiner oder gleich Window_Size ist, können Sequenzbefehle einen Offset angeben, der länger ist als die Gesamtlänge der bisher dekodierten Ausgabe, um auf das Wörterbuch zurückzuverweisen, selbst auf Teile des Wörterbuchs mit Offsets größer als Window_Size. Nach Überschreiten der Window_Size in der Gesamtausgabe ist dies jedoch nicht mehr erlaubt, und das Wörterbuch ist nicht mehr zugänglich.

6. Use of Dictionaries (Verwendung von Wörterbüchern)​

Es laufen Untersuchungen zur Bereitstellung von Bestimmungen für die Verwendung von Wörterbüchern mit zstd. Siehe zum Beispiel [DICT-SEC]. Ein mögliches Ergebnis wäre ein Register gut getesteter Wörterbücher, die für verschiedene Anwendungsfälle optimiert sind, und ihrer Identifikatoren, möglicherweise zusammen mit einem privaten Verhandlungsmechanismus (Private Negotiation Mechanism) für die Verwendung nicht registrierter Wörterbücher.

Um die Kompatibilität mit zukünftigen Spezifikationen für die Verwendung von Wörterbüchern mit zstd-Payloads, insbesondere mit MIME-Kompatibilität, zu gewährleisten, SOLLTEN mit dem hier registrierten Medientyp kodierte Inhalte KEINE Wörterbücher verwenden. Eine Ausnahme von dieser Anforderung könnte die oben vorgeschlagene private Wörterbuchverhandlung sein, die nicht Teil dieser Spezifikation ist.

7. IANA Considerations (IANA-Überlegungen)​

Die IANA hat zwei zuvor bestehende Registrierungen aktualisiert und eine neue Registrierung vorgenommen, wie nachfolgend beschrieben.

7.1 The 'application/zstd' Media Type (Der 'application/zstd' Medientyp)​

Der application/zstd Medientyp identifiziert einen Datenblock, der mit zstd komprimiert wurde. Die Daten sind der Bytestream, der in diesem Dokument beschrieben wird. Die IANA hat Folgendes zum Register „Media Types" (Medientypen) hinzugefügt:

Type name (Typname) : application

Subtype name (Subtypname) : zstd

Required parameters (Erforderliche Parameter) : N/A

Optional parameters (Optionale Parameter) : N/A

Encoding considerations (Kodierungsüberlegungen) : binary

Security considerations (Sicherheitsüberlegungen) : Siehe Abschnitt 8 von RFC 8878.

Interoperability considerations (Interoperabilitätsüberlegungen) : N/A

Published specification (Veröffentlichte Spezifikation) : RFC 8878

Applications which use this media type (Anwendungen, die diesen Medientyp verwenden) : Überall dort, wo Datengröße ein Problem ist

Fragment identifier considerations (Fragmentbezeichner-Überlegungen) : Für diesen Typ sind keine Fragmentbezeichner definiert.

Additional information (Zusätzliche Informationen) :

  • Deprecated alias names for this type (Veraltete Aliasnamen für diesen Typ): N/A
  • Magic number(s) (Magische Zahl(en)): 4 Bytes, Little-Endian-Format. Wert: 0xFD2FB528
  • File extension(s) (Dateierweiterung(en)): zst
  • Macintosh file type code(s) (Macintosh-Dateitypcode(s)): N/A

Person & email address to contact for further information (Kontaktperson und E-Mail-Adresse für weitere Informationen) : Yann Collet &lt;[email protected]&gt;

Intended usage (Beabsichtigte Verwendung) : common (allgemein)

Restrictions on usage (Verwendungsbeschränkungen) : N/A

Author (Autor) : Murray S. Kucherawy

Change Controller (Änderungsverantwortlicher) : IETF

Provisional registration (Vorläufige Registrierung) : no

For further information (Für weitere Informationen) : Siehe [ZSTD]

7.2 Content Encoding (Inhaltskodierung)​

Die IANA hat den folgenden Eintrag zum „HTTP Content Coding Registry" (HTTP-Inhaltskodierungsregister) im Register „Hypertext Transfer Protocol (HTTP) Parameters" (Hypertext-Transfer-Protokoll (HTTP) Parameter) hinzugefügt:

Name : zstd

Description (Beschreibung) : Mit dem Zstandard-Protokoll komprimierter Bytestream

Reference (Referenz) : RFC 8878

7.3 Structured Syntax Suffix (Strukturiertes Syntaxsuffix)​

Die IANA hat Folgendes im Register „Structured Syntax Suffix" (Strukturiertes Syntaxsuffix) registriert:

Name : Zstandard

+suffix (Suffix) : +zstd

Encoding Considerations (Kodierungsüberlegungen) : binary

Interoperability Considerations (Interoperabilitätsüberlegungen) : N/A

Fragment Identifier Considerations (Fragmentbezeichner-Überlegungen) : Die Syntax und Semantik von Fragmentbezeichnern, die für +zstd angegeben sind, MÜSSEN mit denen für application/zstd übereinstimmen.

Security Considerations (Sicherheitsüberlegungen) : Siehe Abschnitt 8 von RFC 8878.

Contact (Kontakt) : Siehe Autor des application/zstd Medientyps.

Author/Change Controller (Autor/Änderungsverantwortlicher) : IETF

7.4 Dictionaries (Wörterbücher)​

Laufende Arbeiten umfassen die Entwicklung von Wörterbüchern, die die Kompression und Dekompression bestimmter Datentypen optimieren werden. Die Spezifikation solcher Wörterbücher für die öffentliche Verwendung würde die Registrierung von Codepunkten aus dem in Abschnitt 3.1.1.1.3 beschriebenen reservierten Bereich und deren Zuordnung zu einem bestimmten Wörterbuch erfordern.

Derzeit sind keine solchen Wörterbücher für die öffentliche Verwendung veröffentlicht, daher fordert dieses Dokument die IANA nicht unmittelbar zur Erstellung eines solchen Registers auf.

8. Security Considerations (Sicherheitserwägungen)​

Jede Datenkomprimierungsmethode beinhaltet die Reduzierung von Redundanz in den Daten. Zstandard ist keine Ausnahme, und die üblichen Vorsichtsmaßnahmen gelten.

Man sollte niemals eine Nachricht, deren Inhalt geheim bleiben muss, mit einer von einem Dritten generierten Nachricht komprimieren. Eine solche Komprimierung kann verwendet werden, um den Inhalt der geheimen Nachricht durch Entropiereduktionsanalyse (Entropy Reduction Analysis) zu erraten. Dies wurde beispielsweise im CRIME-Angriff (Compression Ratio Info-leak Made Easy) [CRIME] demonstriert.

Ein Decoder muss Fähigkeiten demonstrieren, um jede Art von Datenmanipulation im komprimierten Frame zu erkennen und zu verhindern, die Systemfehler auslösen könnte, wie das Lesen oder Schreiben außerhalb erlaubter Speicherbereiche. Dies kann entweder durch die Implementierungssprache oder durch sorgfältige Grenzprüfungen (Bound Checking) garantiert werden. Besonders hervorzuheben ist die Kodierung von Number_of_Sequences-Werten, die den Decoder dazu veranlassen, in den Block-Header (und darüber hinaus) zu lesen, sowie die Angabe einer Frame_Content_Size, die kleiner als die tatsächlich dekomprimierten Daten ist, in einem Versuch, einen Pufferüberlauf (Buffer Overflow) auszulösen. Es wird dringend empfohlen, Decoder-Implementierungen einem Fuzz-Test zu unterziehen (d.h. ungültige, unerwartete oder zufällige Eingaben bereitzustellen und den sicheren Betrieb zu überprüfen), um ihre Fähigkeit zu testen und zu härten, fehlerhafte Frames zu erkennen und ohne nachteilige Systemnebeneffekte damit umzugehen.

Ein Angreifer kann korrekt formatierte komprimierte Frames mit unvernünftigen Speicheranforderungen bereitstellen. Ein Decoder muss immer die Speicheranforderungen kontrollieren und einige (systemspezifische) Grenzen durchsetzen, um die Speichernutzung vor solchen Szenarien zu schützen.

Die Komprimierung kann optimiert werden, indem ein Wörterbuch auf einer Vielzahl verwandter Inhalts-Payloads trainiert wird. Dieses Wörterbuch muss dann beim Decoder verfügbar sein, damit die Dekomprimierung des Payloads möglich ist. Obwohl dieses Dokument nicht spezifiziert, wie ein Wörterbuch für einen gegebenen komprimierten Payload erworben wird, ist es erwähnenswert, dass Wörterbücher von Drittanbietern unerwartet mit einem Decoder interagieren können, was zu möglichen Speicher- oder anderen Ressourcenerschöpfungsangriffen (Resource-exhaustion Attacks) führen kann. Wir erwarten, dass solche Themen im Abschnitt Sicherheitserwägungen eines kommenden RFC über Wörterbucherwerb und -übertragung detaillierter diskutiert werden, heben dieses Problem jetzt aber aus Vorsicht hervor.

Wie in Abschnitt 3.1.2 besprochen, ist es möglich, beliebige Benutzermetadaten in überspringbaren Frames (Skippable Frames) zu speichern. Obwohl solche Frames während der Dekomprimierung der Daten ignoriert werden, können sie als Wasserzeichen (Watermark) verwendet werden, um den Pfad des komprimierten Payloads zu verfolgen.

Appendix A. Decoding Tables for Predefined Codes (Anhang A. Dekodierungstabellen für vordefinierte Codes)​

Dieser Anhang enthält die FSE-Dekodierungstabellen für vordefinierte Literal-Längen-, Übereinstimmungslängen- und Offset-Codes. Diese Tabellen werden unter Verwendung des in Abschnitt 4.1.1 angegebenen Algorithmus konstruiert. Die Tabellen hier können als Beispiel verwendet werden, um zu überprüfen, ob eine Implementierung ihre Dekodierungstabellen korrekt aufbaut.

A.1. Literals Length Code Table (Literal-Längencodes-Tabelle)​

State (Zustand)SymbolNumber_Of_Bits (Anzahl Bits)Base (Basis)
0000
0040
10416
21532
3350
4450
5650
6750
7950
81050
91250
101460
111650
121850
131950
142150
152250
162450
1725532
182650
192760
202960
213160
220432
23140
24250
254532
26550
277532
28850
2910532
301150
311360
3216532
331750
3419532
352050
3622532
372350
382540
3925416
4026532
412860
423060
430448
441416
452532
463532
475532
486532
498532
509532
5111532
5212532
531560
5417532
5518532
5620532
5721532
5823532
5924532
603560
613460
623360
633260

Tabelle 28: Literal-Längencodes-Tabelle

A.2. Match Length Code Table (Übereinstimmungslängencodes-Tabelle)​

State (Zustand)SymbolNumber_Of_Bits (Anzahl Bits)Base (Basis)
0000
0060
1140
22532
3350
4550
5650
6850
71060
81360
91660
101960
112260
122560
132860
143160
153360
163560
173760
183960
194160
204360
214560
221416
23240
243532
25450
266532
27750
28960
291260
301560
311860
322160
332460
342760
353060
363260
373460
383660
393860
404060
414260
424460
431432
441448
452416
464532
475532
487532
498532
501160
511460
521760
532060
542360
552660
562960
575260
585160
595060
604960
614860
624760
634660

Tabelle 29: Übereinstimmungslängencodes-Tabelle

A.3. Offset Code Table (Offset-Codes-Tabelle)​

State (Zustand)SymbolNumber_Of_Bits (Anzahl Bits)Base (Basis)
0000
0050
1640
2950
31550
42150
5350
6740
71250
81850
92350
10550
11840
121450
132050
14250
157416
161150
171750
182250
19450
208416
211350
221950
23150
246416
251050
261650
272850
282750
292650
302550
312450

Tabelle 30: Offset-Codes-Tabelle

Appendix B. Changes since RFC 8478 (Anhang B. Änderungen seit RFC 8478)​

Folgendes sind die Änderungen in diesem Dokument im Vergleich zu RFC 8478:

  • Anwendung der Errata [Err5786] und [Err6303].

  • Klarstellung der Vorwärtskompatibilität bezüglich Wörterbüchern.

  • Klarstellung der Anwendung von Block_Maximum_Size.

  • Hinzufügung der Registrierung des strukturierten Medientyp-Suffixes.

  • Klarstellung, dass die Inhaltsprüfsumme immer 4 Bytes beträgt.

  • Klarstellung der Behandlung reservierter und beschädigter Eingaben.

  • Hinzufügung von Fragmentbezeichner-Überlegungen zur Medientyp-Registrierung.

Acknowledgments (Danksagungen)​

zstd wurde von Yann Collet entwickelt.

Felix Handte und Nick Terrell gaben Feedback, das in diese Überarbeitung und RFC 8478 einfloss. RFC 8478 erhielt auch Beiträge von Bobo Bose-Kolanu, Kyle Nekritz und David Schleimer.

Authors' Addresses (Adressen der Autoren)​

Yann Collet
Facebook
1 Hacker Way
Menlo Park, CA 94025
Vereinigte Staaten von Amerika

Email: [email protected]

Murray S. Kucherawy (Herausgeber)
Facebook
1 Hacker Way
Menlo Park, CA 94025
Vereinigte Staaten von Amerika

Email: [email protected]