Aller au contenu principal

3. Compression Algorithm (Algorithme de compression)

Cette section décrit l'algorithme Zstandard.

L'objectif de ce document est de définir un format de données compressées sans perte (Lossless Compressed Data Format) qui a) est indépendant du type de CPU, du système d'exploitation, du système de fichiers et du jeu de caractères, b) est approprié pour la compression de fichiers ainsi que la compression par pipe et flux (Pipe and Streaming Compression) utilisant l'algorithme Zstandard. Le texte de cette spécification suppose que le lecteur possède des connaissances de base en programmation au niveau des bits et autres représentations de données primitives.

Les données peuvent être générées ou consommées, même pour des flux de données d'entrée présentés séquentiellement de longueur arbitraire, en utilisant uniquement une quantité a priori limitée de stockage intermédiaire (A Priori Bounded Amount of Intermediate Storage); par conséquent, il peut être utilisé pour la communication de données. Le format utilise la méthode de compression Zstandard et la méthode de somme de contrôle xxHash-64 optionnelle [XXHASH] pour détecter la corruption de données (Data Corruption).

Le format de données défini dans cette spécification ne tente pas de permettre l'accès aléatoire (Random Access) aux données compressées.

Sauf indication contraire ci-dessous, un compresseur conforme (Compliant Compressor) doit générer des ensembles de données conformes aux spécifications établies ici. Cependant, il n'est pas nécessaire de prendre en charge toutes les options.

Un décompresseur conforme (Compliant Decompressor) doit être capable de décompresser au moins un ensemble de paramètres de travail conformes aux spécifications établies ici. Il peut également ignorer les champs informatifs (Informative Fields) tels que les sommes de contrôle. Chaque fois qu'il ne prend pas en charge un paramètre défini dans le flux compressé, il doit produire un code d'erreur non ambigu (Unambiguous Error Code) et un message d'erreur associé expliquant quel paramètre n'est pas pris en charge.

Cette spécification est destinée aux implémenteurs de logiciels qui souhaitent compresser des données au format Zstandard et/ou décompresser des données du format Zstandard. Le format Zstandard est pris en charge par une implémentation de référence open source écrite en langage C portable, disponible sur [ZSTD].

3.1 Frames (Trames)​

Les données compressées Zstandard se composent d'une ou plusieurs trames (Frames). Chaque trame est indépendante et peut être décompressée indépendamment des autres trames. Le contenu décompressé de plusieurs trames concaténées est la concaténation du contenu décompressé de chaque trame.

Deux formats de trame sont définis pour Zstandard: les trames Zstandard et les trames sautables (Skippable Frames). Les trames Zstandard contiennent des données compressées, tandis que les trames sautables contiennent des métadonnées utilisateur personnalisées (Custom User Metadata).

3.1.1 Zstandard Frames (Trames Zstandard)​

La structure d'une seule trame Zstandard est la suivante:

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

Tableau 1: Structure d'une seule trame Zstandard

Magic_Number (Nombre magique) : 4 octets, format little-endian. Valeur: 0xFD2FB528.

Frame_Header (En-tête de trame) : 2 à 14 octets, voir section 3.1.1.1.

Data_Block (Bloc de données) : Voir section 3.1.1.2. C'est là que les données apparaissent.

Content_Checksum (Somme de contrôle du contenu) : Somme de contrôle 32 bits facultative, présente uniquement si Content_Checksum_Flag est défini. La somme de contrôle du contenu est le résultat de la fonction de hachage XXH64() [XXHASH] avec les données d'origine (décodées) comme entrée et un seed de zéro. Les 4 octets inférieurs de la somme de contrôle sont stockés au format little-endian.

Le choix du nombre magique est conçu pour réduire la probabilité de le trouver au début d'un fichier arbitraire. Il évite les motifs triviaux (0x00, 0xFF, octets répétés, octets incrémentés, etc.), contient des valeurs d'octets en dehors de la plage ASCII et ne se mappe pas dans l'espace UTF-8, tout cela réduisant la probabilité qu'il apparaisse en haut d'un fichier texte.

3.1.1.1 Frame Header (En-tête de trame)​

La taille de l'en-tête de trame est variable, minimum 2 octets et maximum 14 octets, selon les paramètres facultatifs. La structure de Frame_Header est la suivante:

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

Tableau 2: Structure de Frame_Header

(Étant donné que le contenu de la section 3.1.1.1 et de ses sous-sections est trop long, veuillez vous référer au document RFC 8878 complet pour les descriptions détaillées des champs de bits, Window Descriptor, Dictionary_ID, Frame_Content_Size et autres détails techniques)

Note: La section 3 contient de nombreux détails techniques, notamment:

  • 3.1.1.2 Blocks (Structure de blocs)
  • 3.1.1.3 Compressed Blocks (Blocs compressés, contient Literals et Sequences)
  • 3.1.1.4 Sequence Execution (Exécution de séquence)
  • 3.1.1.5 Repeat Offsets (Décalages répétés)
  • 3.1.2 Skippable Frames (Trames sautables)

Pour les détails complets de l'implémentation technique, veuillez consulter le texte original RFC 8878: https://www.rfc-editor.org/rfc/rfc8878.txt

Dernière mise à jour le