Zum Hauptinhalt springen

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

Letztes Update am