Aller au contenu principal

RFC 8878 - Compression Zstandard et type de média 'application/zstd'

  • Statut: Informational
  • Publié: February 2021
  • Stream: IETF
  • Remplace: RFC8478
  • Errata: Pas d'errata

Résumé (Abstract)​

Zstandard, ou "zstd" (prononcé "zee standard"), est un mécanisme de compression de données sans perte (Lossless Data Compression Mechanism). Ce document décrit ce mécanisme et enregistre le type de média (Media Type), l'encodage de contenu (Content Encoding) et le suffixe de syntaxe structurée (Structured Syntax Suffix) utilisés lors de la transmission de contenu compressé zstd via MIME.

Bien que le nom Zstandard utilise le mot "standard", les lecteurs doivent noter que ce document n'est pas une spécification Internet Standards Track; il est publié uniquement à des fins informatives.

Ce document remplace et rend obsolète RFC 8478.

Table des matières (Contents)​

Sections principales​

Sections de normalisation​

Annexes (Appendices)​

Références​

Points forts techniques​

🔬 Algorithmes principaux​

FSE (Entropie à états finis)

  • Encodeur entropique basé sur ANS
  • Codage/décodage piloté par machine à états
  • Table de distribution de probabilité optimisée

Codage Huffman

  • Construction de code préfixe
  • Conversion poids vers mot de code
  • Lecture de flux de bits inversé

📊 Caractéristiques de performance​

Plage de niveau de compression: -5 à 22
Niveau par défaut: 3 (vitesse et compression équilibrées)
Vitesse de compression: 100-500 MB/s (niveaux 1-3)
Vitesse de décompression: 1000-1500 MB/s
Taille de fenêtre maximale: 128 MB

🎯 Scénarios d'application​

  • Compression de contenu Web: Réponses HTTP, ressources statiques
  • Système de fichiers: Compression transparente Btrfs, ZFS
  • Base de données: Kafka, MySQL, Clickhouse
  • Transmission réseau: HTTP/2, gRPC, WebSocket

Ressources associées​

Statut du document​

Version de traduction: Français
Statut de traduction: 🔄 En cours
Dernière mise à jour: 2024-12-25
Revue technique: En attente

1. Introduction​

Zstandard, ou "zstd" (prononcé "zee standard"), est un mécanisme de compression de données (Data Compression Mechanism), similaire à gzip [RFC1952].

Malgré l'utilisation du mot "standard" dans son nom, les lecteurs sont avisés que ce document n'est pas une spécification de la piste des normes Internet (Internet Standards Track Specification) ; il est publié uniquement à des fins informatives.

Ce document décrit le format Zstandard. De plus, pour permettre le transport d'un objet de données compressé avec Zstandard, ce document enregistre un type de média (Media Type), un encodage de contenu (Content Encoding) et un suffixe de syntaxe structurée (Structured Syntax Suffix) qui peuvent être utilisés pour identifier un tel contenu lorsqu'il est utilisé dans une charge utile (Payload).

2. Definitions (Définitions)​

Certains termes utilisés ailleurs dans ce document sont définis ici pour plus de clarté.

uncompressed (non compressé) : Décrit un ensemble arbitraire d'octets dans leur forme originale, avant d'être soumis à la compression.

compressed (compressé) : Décrit le résultat du passage d'un ensemble d'octets à travers ce mécanisme. L'entrée originale a ainsi été compressée.

decompressed (décompressé) : Décrit le résultat du passage d'un ensemble d'octets à travers l'inverse de ce mécanisme. Lorsque cela réussit, la charge utile décompressée (Decompressed Payload) et la charge utile non compressée (Uncompressed Payload) sont indiscernables.

encode (encoder) : Le processus de traduction des données d'une forme à une autre ; cela peut inclure la compression, ou peut faire référence à d'autres traductions effectuées dans le cadre de cette spécification.

decode (décoder) : L'inverse de "encode" ; décrit un processus d'inversion d'un encodage antérieur pour récupérer le contenu original.

frame (trame) : Le contenu compressé par Zstandard est transformé en trame Zstandard. Plusieurs trames peuvent être ajoutées à un seul fichier ou flux. Une trame est complètement indépendante, a un début et une fin définis, et possède un ensemble de paramètres qui indique au décodeur (Decoder) comment la décompresser.

block (bloc) : Une trame encapsule un ou plusieurs blocs. Chaque bloc contient un contenu arbitraire, qui est décrit par son en-tête (Header), et possède une taille de contenu maximale garantie qui dépend des paramètres de la trame. Contrairement aux trames, chaque bloc dépend des blocs précédents pour un décodage approprié. Cependant, chaque bloc peut être décompressé sans attendre son successeur, permettant des opérations de streaming (Streaming Operations).

natural order (ordre naturel) : Une séquence ou un ordre d'objets ou de valeurs typique de ce type d'objet ou de valeur. Un ensemble d'entiers uniques, par exemple, est dans un "ordre naturel" si, lors de la progression d'un élément de l'ensemble ou de la séquence au suivant, il n'y a jamais de diminution de valeur.

La convention de nommage des identificateurs dans la spécification est Mixed_Case_With_Underscores (casse mixte avec traits de soulignement). Les identificateurs entre crochets indiquent que l'identificateur est optionnel dans le contexte présenté.

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

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

3.1.1.1.1. Frame_Header_Descriptor (Descripteur d'en-tête de trame)​

Le premier octet de l'en-tête est appelé Frame_Header_Descriptor. Il décrit quels autres champs sont présents. Le décodage de cet octet suffit pour déterminer la taille de Frame_Header.

Numéro de bit (Bit Number)Nom du champ (Field Name)
7-6Frame_Content_Size_Flag
5Single_Segment_Flag
4(inutilisé, unused)
3(réservé, reserved)
2Content_Checksum_Flag
1-0Dictionary_ID_Flag

Tableau 3: Frame_Header_Descriptor

Dans le tableau 3, le bit 7 est le bit de poids fort et le bit 0 est le bit de poids faible.

3.1.1.1.1.1. Frame_Content_Size_Flag (Indicateur de taille de contenu de trame)​

Il s'agit d'un indicateur de 2 bits (équivalent à Frame_Header_Descriptor décalé de 6 bits vers la droite), qui spécifie si Frame_Content_Size (taille des données décompressées) est fourni dans l'en-tête. Frame_Content_Size_Flag fournit FCS_Field_Size, le nombre d'octets utilisés par Frame_Content_Size selon le tableau 4:

Frame_Content_Size_Flag0123
FCS_Field_Size0 ou 1248

Tableau 4: Frame_Content_Size_Flag fournit FCS_Field_Size

Lorsque Frame_Content_Size_Flag est 0, FCS_Field_Size dépend de Single_Segment_Flag: si Single_Segment_Flag est défini, alors FCS_Field_Size est 1. Sinon, FCS_Field_Size est 0; Frame_Content_Size n'est pas fourni.

3.1.1.1.1.2. Single_Segment_Flag (Indicateur de segment unique)​

Si cet indicateur est défini, les données doivent être régénérées dans un seul segment de mémoire continu.

Dans ce cas, l'octet Window_Descriptor est ignoré, mais Frame_Content_Size doit être présent. Par conséquent, le décodeur doit allouer un segment de mémoire de taille égale ou supérieure à Frame_Content_Size.

Pour protéger le décodeur contre des demandes de mémoire déraisonnables, il est permis au décodeur de rejeter les trames compressées qui demandent des tailles de mémoire dépassant la plage autorisée du décodeur.

Pour une compatibilité plus large, il est recommandé que les décodeurs prennent en charge au moins une taille de mémoire de 8 Mo. Il ne s'agit que d'une recommandation; chaque décodeur peut librement prendre en charge des limites supérieures ou inférieures en fonction des contraintes locales.

3.1.1.1.1.3. Unused Bit (Bit inutilisé)​

Un décodeur conforme à cette version de la spécification ne doit pas interpréter ce bit. Il peut être utilisé dans les versions futures pour représenter des attributs qui ne sont pas essentiels pour décoder correctement la trame. Un encodeur conforme à cette spécification doit définir ce bit à zéro.

3.1.1.1.1.4. Reserved Bit (Bit réservé)​

Ce bit est réservé pour une future fonctionnalité. Sa valeur doit être zéro. Un décodeur conforme à cette version de la spécification doit s'assurer qu'il n'est pas défini. Ce bit peut être utilisé dans les révisions futures pour représenter des fonctionnalités qui doivent être interprétées pour décoder correctement la trame.

3.1.1.1.1.5. Content_Checksum_Flag (Indicateur de somme de contrôle du contenu)​

Si cet indicateur est défini, une Content_Checksum de 32 bits sera présente à la fin de la trame. Voir la description de Content_Checksum ci-dessus.

3.1.1.1.1.6. Dictionary_ID_Flag (Indicateur d'ID de dictionnaire)​

Il s'agit d'un indicateur de 2 bits (= Frame_Header_Descriptor & 0x3), qui indique si un ID de dictionnaire est fourni dans l'en-tête. Il spécifie également la taille de ce champ comme DID_Field_Size:

Dictionary_ID_Flag0123
DID_Field_Size0124

Tableau 5: Dictionary_ID_Flag

3.1.1.1.2. Window Descriptor (Descripteur de fenêtre)​

Cela fournit une garantie sur le tampon de mémoire minimum requis pour décompresser la trame. Cette information est importante pour que le décodeur alloue suffisamment de mémoire.

L'octet Window_Descriptor est facultatif. Lorsque Single_Segment_Flag est défini, Window_Descriptor n'est pas présent. Dans ce cas, Window_Size est égal à Frame_Content_Size, et sa valeur peut aller de 0 à 2^64 - 1 octets (16 ExaBytes).

Numéro de bit (Bit Number)7-32-0
Nom du champ (Field Name)Exponent (Exposant)Mantissa (Mantisse)

Tableau 6: Window_Descriptor

La taille minimale du tampon de mémoire est appelée Window_Size. Elle est décrite par la formule suivante:

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

La Window_Size minimale est de 1 Ko. La Window_Size maximale est de (1<<41) + 7*(1<<38) octets, soit 3,75 To.

En général, des valeurs de Window_Size plus grandes ont tendance à améliorer le taux de compression, au prix d'une utilisation accrue de la mémoire.

Pour décoder correctement les données compressées, le décodeur doit allouer un tampon d'au moins Window_Size octets.

Pour protéger le décodeur contre des demandes de mémoire déraisonnables, il est permis au décodeur de rejeter les trames compressées qui demandent des tailles de mémoire dépassant la plage autorisée du décodeur.

Pour améliorer l'interopérabilité, il est recommandé que les décodeurs prennent en charge des valeurs de Window_Size allant jusqu'à 8 Mo et que les encodeurs ne génèrent pas de trames nécessitant une Window_Size supérieure à 8 Mo. Il ne s'agit que d'une recommandation, et les décodeurs peuvent librement prendre en charge des limites supérieures ou inférieures en fonction des contraintes locales.

3.1.1.1.3. Dictionary_ID (ID de dictionnaire)​

Il s'agit d'un champ de taille variable qui contient l'ID de dictionnaire requis pour décoder correctement la trame. Ce champ est facultatif. S'il n'est pas présent, c'est au décodeur de décider quel dictionnaire utiliser.

La taille du champ Dictionary_ID est fournie par DID_Field_Size. DID_Field_Size est directement dérivé de la valeur de Dictionary_ID_Flag. Un octet peut représenter les ID 0-255; 2 octets peuvent représenter les ID 0-65535; 4 octets peuvent représenter les ID 0-4294967295. Le format est little-endian.

Il est permis d'utiliser un grand ID de dictionnaire de 4 octets pour représenter un petit ID (par exemple, 13), même si cela est inefficace.

Dans des environnements privés, tout ID de dictionnaire peut être utilisé. Cependant, pour les trames et les dictionnaires distribués dans l'espace public, Dictionary_ID doit être soigneusement attribué. Les plages suivantes sont réservées uniquement aux dictionnaires enregistrés auprès de l'IANA (voir section 7.4):

  • Plage basse (low range): <= 32767
  • Plage haute (high range): >= (1 << 31)

Toute autre valeur de Dictionary_ID peut être utilisée par arrangement privé entre participants.

Toute charge utile soumise pour décompression qui fait référence à un ID de dictionnaire réservé non enregistré entraînera une erreur.

3.1.1.1.4. Frame_Content_Size (Taille du contenu de trame)​

Il s'agit de la taille d'origine (non compressée). Cette information est facultative. Frame_Content_Size utilise un nombre variable d'octets, fourni par FCS_Field_Size. FCS_Field_Size est fourni par la valeur de Frame_Content_Size_Flag. FCS_Field_Size peut être égal à 0 (non présent), 1, 2, 4 ou 8 octets.

FCS Field Size (Taille du champ)Range (Plage)
0unknown (inconnu)
10 - 255
2256 - 65791
40 - 2^32 - 1
80 - 2^64 - 1

Tableau 7: Frame_Content_Size

Le format Frame_Content_Size est little-endian. Lorsque FCS_Field_Size est 1, 4 ou 8 octets, la valeur est lue directement. Lorsque FCS_Field_Size est 2, un décalage de 256 est ajouté. Il est permis d'utiliser n'importe quelle variante compatible pour représenter une petite taille (par exemple, 18), même si cela est inefficace.

3.1.1.2. Blocks (Blocs)​

Après Magic_Number et Frame_Header, il y a plusieurs blocs. Chaque trame doit avoir au moins 1 bloc, mais il n'y a pas de limite supérieure au nombre de blocs par trame.

La structure d'un bloc est la suivante:

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

Tableau 8: Structure d'un bloc

Block_Header utilise 3 octets, écrits en utilisant la convention little-endian. Il contient trois champs:

Last_BlockBlock_TypeBlock_Size
bit 0bits 1-2bits 3-23

Tableau 9: Block_Header

3.1.1.2.1. Last_Block (Dernier bloc)​

Le bit de poids faible (Last_Block) indique s'il s'agit du dernier bloc. La trame se terminera après ce dernier bloc. Il peut être suivi d'une Content_Checksum facultative (voir section 3.1.1).

3.1.1.2.2. Block_Type (Type de bloc)​

Les 2 bits suivants représentent le Block_Type. Il existe quatre types de blocs:

Value (Valeur)Block_Type (Type de bloc)
0Raw_Block (Bloc brut)
1RLE_Block (Bloc RLE)
2Compressed_Block (Bloc compressé)
3Reserved (Réservé)

Tableau 10: Quatre types de blocs

Raw_Block (Bloc brut) : Il s'agit d'un bloc non compressé. Block_Content contient Block_Size octets.

RLE_Block (Bloc RLE) : Il s'agit d'un seul octet, répété Block_Size fois. Block_Content est composé d'un seul octet. Du côté de la décompression, cet octet doit être répété Block_Size fois.

Compressed_Block (Bloc compressé) : Il s'agit du bloc compressé décrit dans la section 3.1.1.3. Block_Size est la longueur de Block_Content, c'est-à-dire les données compressées. La taille décompressée est inconnue, mais sa valeur maximale possible est garantie (voir ci-dessous).

Reserved (Réservé) : Ce n'est pas un bloc. Cette valeur ne peut pas être utilisée avec la spécification actuelle. Si une telle valeur est présente, elle est considérée comme des données corrompues, et un décodeur conforme à la spécification doit la rejeter.

3.1.1.2.3. Block_Size (Taille du bloc)​

Les 21 bits supérieurs du Block_Header représentent la Block_Size.

Lorsque Block_Type est Compressed_Block ou Raw_Block, Block_Size est la taille de Block_Content (n'inclut donc pas le Block_Header).

Lorsque Block_Type est RLE_Block, comme la taille de Block_Content est toujours 1, Block_Size représente le nombre de fois que cet octet doit être répété.

Block_Size est limité par Block_Maximum_Size (voir ci-dessous).

3.1.1.2.4. Block_Content and Block_Maximum_Size (Contenu du bloc et taille maximale du bloc)​

La taille de Block_Content est limitée par Block_Maximum_Size, qui est le plus petit des deux suivants:

  • Window_Size
  • 128 KB

Block_Maximum_Size est constant pour une trame donnée. Ce maximum s'applique à la fois à la taille décompressée et à la taille compressée de tout bloc dans la trame.

La justification de cette limitation est que le décodeur peut lire ces informations au début de la trame et les utiliser pour allouer des tampons. La garantie de la taille du bloc assure que le tampon est suffisant pour tous les blocs suivants d'une trame valide.

Si un bloc compressé est plus grand qu'un bloc non compressé, il est recommandé d'envoyer plutôt un bloc non compressé (c'est-à-dire Raw_Block).

3.1.1.3. Compressed Blocks (Blocs compressés)​

Pour décompresser un bloc compressé, la taille compressée doit être fournie à partir du champ Block_Size dans le Block_Header.

Un bloc compressé se compose de deux parties: Literals_Section (section des littéraux, section 3.1.1.3.1) et Sequences_Section (section des séquences, section 3.1.1.3.2). Les résultats de ces deux parties sont ensuite combinés pour générer les données décompressées dans l'exécution de séquence (section 3.1.1.4).

Pour décoder un bloc compressé, les éléments suivants sont nécessaires:

  • Données précédemment décodées, jusqu'à une distance de Window_Size, ou le début de la trame, selon ce qui est le plus petit. Dans ce dernier cas, Single_Segment_Flag sera défini.

  • Liste "décalages récents", du Compressed_Block précédent.

  • Arbre Huffman précédent, nécessaire pour le type Treeless_Literals_Block.

  • Tables de décodage Finite State Entropy (FSE) précédentes, nécessaires pour Repeat_Mode, pour chaque type de symbole (codes de longueur de littéral, codes de longueur de correspondance, codes de décalage).

Notez que les tables de décodage ne proviennent pas toujours du Compressed_Block précédent:

  • Chaque table de décodage peut provenir du dictionnaire.
  • L'arbre Huffman provient du Compressed_Literals_Block précédent.

3.1.1.3.1. Literals_Section_Header (En-tête de section des littéraux)​

Tous les littéraux sont réassemblés dans la première partie du bloc. Ils peuvent être décodés en premier, puis copiés pendant l'exécution de séquence (voir section 3.1.1.4), ou ils peuvent être décodés à la volée pendant l'exécution de séquence.

Les littéraux peuvent être stockés non compressés ou compressés en utilisant le code préfixe Huffman. Lorsqu'ils sont compressés, une description d'arbre facultative peut être présente, suivie de 1 ou 4 flux.

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

Tableau 11: Littéraux compressés

3.1.1.3.1.1. Literals_Section_Header (En-tête de section des littéraux)​

Ce champ décrit comment les littéraux sont emballés. Il s'agit d'un champ de bits de taille variable aligné sur les octets, allant de 1 à 5 octets, utilisant la convention little-endian.

ChampTaille
Literals_Block_Type2 bits
Size_Format1-2 bits
Regenerated_Size5-20 bits
[Compressed_Size]0-18 bits

Tableau 12: Literals_Section_Header

Dans cette représentation, les bits supérieurs sont à la position la plus basse.

Le champ Literals_Block_Type utilise les deux bits les plus bas du premier octet et décrit quatre types de blocs différents:

Literals_Block_Type (Type de bloc de littéraux)Value (Valeur)
Raw_Literals_Block (Littéraux bruts)0
RLE_Literals_Block (Littéraux RLE)1
Compressed_Literals_Block (Littéraux compressés)2
Treeless_Literals_Block (Littéraux sans arbre)3

Tableau 13: Literals_Block_Type

Raw_Literals_Block (Littéraux bruts) : Les littéraux sont stockés non compressés. Literals_Section_Content est Regenerated_Size.

RLE_Literals_Block (Littéraux RLE) : Les littéraux consistent en une valeur d'octet unique répétée Regenerated_Size fois. Literals_Section_Content est 1.

Compressed_Literals_Block (Littéraux compressés) : Il s'agit d'un bloc compressé Huffman standard, commençant par une description d'arbre Huffman. Voir les détails ci-dessous. Literals_Section_Content est Compressed_Size.

Treeless_Literals_Block (Littéraux sans arbre) : Il s'agit d'un bloc compressé Huffman utilisant l'arbre Huffman du Compressed_Literals_Block précédent, ou s'il n'y a pas de bloc de littéraux compressés Huffman précédent, du dictionnaire. Huffman_Tree_Description est ignorée. Notez que si ce mode est déclenché sans table Huffman précédente dans la trame (ou dictionnaire selon la section 5), cela devrait être considéré comme une corruption de données. Literals_Section_Content est Compressed_Size.

Size_Format se divise en deux familles:

  • Pour Raw_Literals_Block et RLE_Literals_Block, seul Regenerated_Size doit être décodé. Il n'y a pas de champ Compressed_Size.

  • Pour Compressed_Block et Treeless_Literals_Block, Compressed_Size et Regenerated_Size (taille décompressée) doivent être décodés. Le nombre de flux (1 ou 4) doit également être décodé.

Pour les valeurs couvrant plusieurs octets, la convention est little-endian.

Size_Format pour Raw_Literals_Block et RLE_Literals_Block utilise 1 ou 2 bits. Sa valeur est (Literals_Section_Header[0]>>2) & 0x3.

  • Size_Format == 00 ou 10: Size_Format utilise 1 bit. Regenerated_Size utilise 5 bits (valeur 0-31). Literals_Section_Header utilise 1 octet. Regenerated_Size = Literal_Section_Header[0]>>3.

  • Size_Format == 01: Size_Format utilise 2 bits. Regenerated_Size utilise 12 bits (valeur 0-4095). Literals_Section_Header utilise 2 octets. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4).

  • Size_Format == 11: Size_Format utilise 2 bits. Regenerated_Size utilise 20 bits (valeur 0-1048575). Literals_Section_Header utilise 3 octets. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12).

Pour ces cas, seul Stream_1 existe. Notez qu'il est permis d'utiliser un format long pour représenter une valeur courte (par exemple, 13), même si cela est inefficace.

Size_Format pour Compressed_Literals_Block et Treeless_Literals_Block utilise toujours 2 bits.

  • Size_Format == 00: Un seul flux. Regenerated_Size et Compressed_Size utilisent tous deux 10 bits (valeur 0-1023). Literals_Section_Header utilise 3 octets.

  • Size_Format == 01: 4 flux. Regenerated_Size et Compressed_Size utilisent tous deux 10 bits (valeur 0-1023). Literals_Section_Header utilise 3 octets.

  • Size_Format == 10: 4 flux. Regenerated_Size et Compressed_Size utilisent tous deux 14 bits (valeur 0-16383). Literals_Section_Header utilise 4 octets.

  • Size_Format == 11: 4 flux. Regenerated_Size et Compressed_Size utilisent tous deux 18 bits (valeur 0-262143). Literals_Section_Header utilise 5 octets.

Les champs Compressed_Size et Regenerated_Size suivent tous deux la convention little-endian. Notez que Compressed_Size, lorsqu'il est présent, inclut la taille de Huffman_Tree_Description.

3.1.1.3.1.2. Raw_Literals_Block (Littéraux bruts)​

Les données dans Stream_1 sont longues de Regenerated_Size octets. Elles contiennent les données littérales brutes utilisées pendant l'exécution de séquence (section 3.1.1.3.2).

3.1.1.3.1.3. RLE_Literals_Block (Littéraux RLE)​

Stream_1 se compose d'un seul octet qui doit être répété Regenerated_Size fois pour produire les littéraux décodés.

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block (Littéraux compressés et sans arbre)​

Ces deux modes contiennent des données codées Huffman. Pour Treeless_Literals_Block, la table Huffman provient du bloc de littéraux compressés précédent ou du dictionnaire; voir section 5.

3.1.1.3.1.5. Huffman_Tree_Description (Description d'arbre Huffman)​

Cette partie n'est présente que si le type Literals_Block_Type est Compressed_Literals_Block (2). Le format de Huffman_Tree_Description se trouve dans la section 4.2.1. La taille de Huffman_Tree_Description est déterminée pendant le décodage. Elle doit être utilisée pour déterminer où commencent les flux.

Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size

3.1.1.3.1.6. Jump_Table (Table de saut)​

La Jump_Table n'est présente que s'il y a 4 flux codés Huffman.

(Rappel: Les données compressées Huffman se composent de 1 ou 4 flux codés Huffman.)

S'il n'y a qu'1 flux, il s'agit d'un seul flux de bits occupant la totalité de la partie restante du bloc de littéraux, codé comme décrit dans la section 4.2.2.

S'il y a 4 flux, Literals_Section_Header fournit uniquement suffisamment d'informations pour connaître la taille décompressée et compressée de tous les 4 flux combinés. La taille décompressée de chaque flux est égale à (Regenerated_Size+3)/4, sauf pour le dernier flux, qui peut être jusqu'à 3 octets plus petit pour atteindre la taille décompressée totale spécifiée dans Regenerated_Size.

3.1.1.3.2. Sequences_Section (Section des séquences)​

Un bloc compressé est un continuum de séquences. Une séquence est une commande de copie de littéral, suivie d'une commande de copie de correspondance. La commande de copie de littéral spécifie une longueur. C'est le nombre d'octets à copier (ou extraire) de la Literals_Section. La commande de copie de correspondance spécifie un décalage et une longueur.

Lorsque toutes les séquences ont été décodées et qu'il reste des littéraux dans la Literals_Section, ces octets sont ajoutés à la fin du bloc.

Ceci est décrit plus en détail dans la section 3.1.1.4.

La Sequences_Section regroupe tous les symboles nécessaires pour décoder les commandes. Il existe trois types de symboles: codes de longueur de littéral, codes de décalage et codes de longueur de correspondance. Ils sont codés de manière entrelacée dans un seul "flux de bits".

La Sequences_Section commence par un en-tête, suivi de tables de probabilité facultatives pour chaque type de symbole, puis du flux de bits.

Sequences_Section_Header
  [Literals_Length_Table]
  [Offset_Table]
  [Match_Length_Table]
  bitStream

Pour décoder la Sequences_Section, sa taille doit être connue. Cette taille est déduite de la taille de la Literals_Section:

Sequences_Section_Size = Block_Size - Literals_Section_Header 
                         - Literals_Section_Content

3.1.1.3.2.1. Sequences_Section_Header (En-tête de section des séquences)​

Cet en-tête se compose de deux éléments:

  • Number_of_Sequences (Nombre de séquences)
  • Symbol_Compression_Modes (Modes de compression des symboles)

Number_of_Sequences​

Number_of_Sequences est un champ de taille variable utilisant 1 à 3 octets. Si le premier octet est "byte0":

  • if (byte0 == 0): Aucune séquence. La partie séquence s'arrête ici. Le contenu décompressé est entièrement défini comme le contenu de Literals_Section. Les tables FSE utilisées en Repeat_Mode ne sont pas mises à jour.

  • if (byte0 < 128): Number_of_Sequences = byte0. Utilise 1 octet.

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

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

Symbol_Compression_Modes​

Symbol_Compression_Modes est un seul octet définissant le mode de compression pour chaque type de symbole.

Numéro de bit (Bit Number)Nom du champ (Field Name)
7-6Literal_Lengths_Mode
5-4Offsets_Mode
3-2Match_Lengths_Mode
1-0Reserved (Réservé)

Tableau 14: Symbol_Compression_Modes

Le dernier champ Reserved doit être tout zéro.

Literals_Lengths_Mode, Offsets_Mode et Match_Lengths_Mode définissent respectivement le Compression_Mode pour les codes de longueur de littéral, les codes de décalage et les codes de longueur de correspondance. Ils suivent la même énumération:

Value (Valeur)Compression_Mode (Mode de compression)
0Predefined_Mode (Mode prédéfini)
1RLE_Mode (Mode RLE)
2FSE_Compressed_Mode (Mode compressé FSE)
3Repeat_Mode (Mode répétition)

Tableau 15: Literals_Lengths_Mode, Offsets_Mode et Match_Lengths_Mode

Predefined_Mode (Mode prédéfini) : Utilise la table de distribution FSE prédéfinie (voir section 4.1), telle que définie dans la section 3.1.1.3.2.2. Aucune table de distribution ne sera présente.

RLE_Mode (Mode RLE) : La description de la table consiste en un octet contenant la valeur du symbole. Ce symbole sera utilisé pour toutes les séquences.

FSE_Compressed_Mode (Mode compressé FSE) : Compression FSE standard. Une table de distribution sera présente. Le format de cette table de distribution est décrit dans la section 4.1.1. Notez que la précision maximale autorisée pour les tables de codes de longueur de littéral et de codes de longueur de correspondance est de 9, et la précision maximale pour la table de codes de décalage est de 8. Lorsqu'un seul symbole est présent, ce mode ne doit pas être utilisé; le mode RLE_Mode devrait être utilisé à la place (bien que tout autre mode fonctionne également).

Repeat_Mode (Mode répétition) : La table utilisée dans le Compressed_Block précédent avec Number_Of_Sequences > 0 sera réutilisée, ou si c'est le premier bloc, la table du dictionnaire. Notez que cela inclut RLE_Mode, donc si Repeat_Mode suit RLE_Mode, le même symbole sera répété. Cela inclut également Predefined_Mode, auquel cas Repeat_Mode aura le même résultat que Predefined_Mode. Aucune table de distribution ne sera présente. Si ce mode est utilisé sans qu'il y ait de table de séquence précédente à répéter dans la trame (ou dictionnaire; voir section 5), cela devrait être considéré comme une corruption.

3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets (Codes de séquence pour les longueurs et décalages)​

Chaque symbole est un code dans son propre contexte, spécifiant Baseline (ligne de base) et Number_of_Bits (nombre de bits) à ajouter. Les codes sont compressés FSE et entrelacés dans le même flux de bits avec les bits supplémentaires originaux.

Literals Length Codes (Codes de longueur de littéral)​

Les codes de longueur de littéral sont des valeurs de 0 à 35 (inclus). Ils définissent des longueurs de 0 à 131071 octets. La longueur de littéral est égale à la Baseline décodée plus le résultat de la lecture de Number_of_Bits bits du flux de bits (comme valeur little-endian).

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

Tableau 16: Codes de longueur de littéral

Match Length Codes (Codes de longueur de correspondance)​

Les codes de longueur de correspondance sont des valeurs de 0 à 52 (inclus). Ils définissent des longueurs de 3 à 131074 octets. La longueur de correspondance est égale à la Baseline décodée plus le résultat de la lecture de Number_of_Bits bits du flux de bits (comme valeur little-endian).

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

Tableau 17: Codes de longueur de correspondance

Offset Codes (Codes de décalage)​

Les codes de décalage sont des valeurs de 0 à N.

Le décodeur peut librement limiter son N maximum pris en charge. Il est recommandé de prendre en charge au moins une valeur de 22. Au moment de la rédaction, la valeur N maximale prise en charge par le décodeur de référence est 31.

Le code de décalage est également le nombre de bits supplémentaires lus en little-endian, peut être converti en Offset_Value avec la formule suivante:

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

Cela signifie que l'Offset_Value maximum est (2^(N+1)) - 1, prenant en charge des distances de référence arrière jusqu'à (2^(N+1)) - 4, mais limité par la distance de référence arrière maximale (voir section 3.1.1.1.2).

Les Offset_Values de 1 à 3 sont spéciaux: ils définissent des "codes de répétition". Ceci est décrit plus en détail dans la section 3.1.1.5.

3.1.1.3.2.2. Default Distributions (Distributions par défaut)​

Si Predefined_Mode est sélectionné pour un type de symbole, sa table de décodage FSE est générée à partir de la table de distribution prédéfinie définie ici. Pour plus de détails sur la façon de convertir cette distribution en table de décodage, voir la section 4.1.

3.1.1.3.2.2.1. Literals Length Codes (Codes de longueur de littéral)​

La table de décodage utilise un log de précision de 6 bits (64 états).

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 (Codes de longueur de correspondance)​

La table de décodage utilise un log de précision de 6 bits (64 états).

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 (Codes de décalage)​

La table de décodage utilise un log de précision de 5 bits (32 états) et prend en charge une valeur N maximale de 28, permettant des valeurs de décalage jusqu'à 536.870.908.

Si une séquence dans le bloc compressé nécessite un décalage plus grand que cela, elle ne peut pas être représentée avec la distribution par défaut.

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 (Exécution de séquence)​

Une fois que les littéraux et les séquences ont tous été décodés, ils sont combinés pour générer le contenu décodé du bloc.

Chaque séquence est composée d'un tuple (literals_length, offset_value, match_length), tel que décodé comme décrit dans Sequences_Section (section 3.1.1.3.2). Pour exécuter une séquence, copiez d'abord literals_length octets depuis les littéraux décodés vers la sortie.

Ensuite, copiez match_length octets à partir de données précédemment décodées. Le décalage à partir duquel copier est déterminé par offset_value:

  • if Offset_Value > 3: alors le décalage est Offset_Value - 3;

  • if Offset_Value is from 1-3: le décalage est une valeur de décalage répété spéciale. Voir la section 3.1.1.5 pour des informations sur la façon de déterminer le décalage dans ce cas.

Le décalage est défini à partir de la position actuelle (après avoir copié les littéraux), donc un décalage de 6 et une longueur de correspondance de 3 signifie que 3 octets doivent être copiés depuis 6 octets auparavant. Notez que tous les décalages menant à des données précédemment décodées doivent être inférieurs à Window_Size, défini dans Frame_Header_Descriptor (section 3.1.1.1.1).

Exemple de flux d'exécution​

Exemple 1: Exécution de séquence de base​

Supposons que la séquence soit (literals_length=5, offset_value=10, match_length=4):

  1. Copier les littéraux: Copiez 5 octets depuis la section des littéraux vers la sortie
  2. Calculer le décalage: Offset_Value=10 > 3, donc Offset = 10 - 3 = 7
  3. Copier la correspondance: Copiez 4 octets depuis 7 octets avant la position de sortie

Exemple 2: Utilisation d'un décalage répété​

Supposons que la séquence soit (literals_length=3, offset_value=1, match_length=8):

  1. Copier les littéraux: Copiez 3 octets depuis la section des littéraux vers la sortie
  2. Utiliser le décalage répété: offset_value=1 signifie utiliser Repeated_Offset1
  3. Copier la correspondance: Copiez 8 octets depuis la position Repeated_Offset1

Contraintes importantes​

  1. Limitation Window_Size: Tous les décalages doivent être < Window_Size
  2. Intégrité des données: Assurez-vous que les décalages ne dépassent pas la plage des données décodées
  3. Épuisement des littéraux: Après l'exécution de toutes les séquences, les littéraux restants sont ajoutés à la fin de la sortie

3.1.1.5. Repeat Offsets (Décalages répétés)​

Comme décrit ci-dessus, les trois premières valeurs définissent les décalages répétés; nous les appelons Repeated_Offset1, Repeated_Offset2 et Repeated_Offset3. Ils sont classés par ordre de récence, Repeated_Offset1 représentant "le plus récent".

Si offset_value est 1, le décalage utilisé est Repeated_Offset1, et ainsi de suite.

Il y a une exception: lorsque la literals_length de la séquence actuelle est 0, les décalages répétés sont décalés de 1, donc:

  • offset_value de 1 signifie Repeated_Offset2
  • offset_value de 2 signifie Repeated_Offset3
  • offset_value de 3 signifie Repeated_Offset1 - 1_byte

Initialisation​

Pour le premier bloc, l'historique des décalages de départ est rempli avec les valeurs suivantes:

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

Sauf si un dictionnaire est utilisé, auquel cas ils proviennent du dictionnaire.

Ensuite, chaque bloc obtient son historique de décalages de départ à partir des valeurs de fin du Compressed_Block le plus récent. Notez que les blocs qui ne sont pas des Compressed_Blocks sont ignorés; ils n'affectent pas l'historique des décalages.

Règles de mise à jour​

Pendant l'exécution des séquences d'un Compressed_Block, les valeurs des Repeated_Offsets sont maintenues à jour afin qu'elles représentent toujours les trois décalages les plus récemment utilisés. Pour y parvenir, ils sont mis à jour après l'exécution de chaque séquence de la manière suivante:

Cas 1: Décalage non répété​

Lorsque l'offset_value de la séquence ne fait pas référence à l'un des Repeated_Offsets (lorsqu'il a une valeur supérieure à 3, ou lorsqu'il a la valeur 3 et que la literals_length de la séquence est zéro):

  • Les valeurs des Repeated_Offsets sont décalées d'un vers l'arrière
  • Repeated_Offset1 prend la valeur du décalage qui vient d'être utilisé

Formule de mise à jour:

Repeated_Offset3 = Repeated_Offset2
Repeated_Offset2 = Repeated_Offset1
Repeated_Offset1 = nouveau décalage

Cas 2: Décalage répété​

Lorsque l'offset_value de la séquence fait référence à l'un des Repeated_Offsets (lorsqu'il a la valeur 1 ou 2, ou lorsqu'il a la valeur 3 et que la literals_length de la séquence est non nulle):

  • Les Repeated_Offsets sont réorganisés
  • Repeated_Offset1 prend la valeur du Repeated_Offset utilisé
  • Les valeurs existantes sont repoussées du premier Repeated_Offset vers le Repeated_Offset sélectionné par offset_value

Cela effectue efficacement une rotation d'enroulement en une étape de ces valeurs de décalage, de sorte que leur ordre reflète à nouveau leur récence d'utilisation.

Tableau d'exemple de mise à jour​

Le tableau suivant montre les valeurs lors de l'application d'une série de séquences aux Repeated_Offsets:

offset_valueliterals_lengthRepeated_Offset1Repeated_Offset2Repeated_Offset3Comment (Commentaire)
--148Valeur de départ
111411111114Non-répétition
122111114Répétition1; pas de changement
222522222211111Non-répétition
1114111111122221111Non-répétition
333633333311112222Non-répétition
222111133332222Répétition2; échange 1 et 2
333222211113333Répétition3; rotation 3 vers 1
10222122221111Décalage analysé inséré
10222222213333Répétition2

Tableau 18: Repeated_Offsets

Traitement des cas particuliers​

Cas literals_length = 0​

Lorsque literals_length = 0, l'interprétation d'offset_value est décalée:

offset_valueDécalage réellement utilisé
1Repeated_Offset2
2Repeated_Offset3
3Repeated_Offset1 - 1

Ce traitement spécial est destiné à optimiser les opérations de copie de correspondance consécutives.

Points clés​

  1. Principe de récence: Repeated_Offset1 est toujours le décalage le plus récemment utilisé
  2. Mise à jour automatique: L'historique des décalages est automatiquement mis à jour après chaque exécution de séquence
  3. Support de dictionnaire: Les valeurs initiales peuvent provenir du dictionnaire
  4. Décalage spécial: L'interprétation du décalage change lorsque literals_length=0

3.1.2. Skippable Frames (Trames sautables)​

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

Tableau 19: Trames sautables

Les trames sautables permettent d'insérer des métadonnées définies par l'utilisateur dans un flux de trames concaténées.

Les trames sautables définies dans cette spécification sont compatibles avec les trames sautables dans [LZ4].

Du point de vue d'un décodeur compatible, les trames sautables doivent simplement être sautées, leur contenu ignoré, et le décodage reprend après la trame sautable.

Il convient de noter que les trames sautables peuvent être utilisées pour ajouter un filigrane aux flux de trames concaténés, incorporer tout type d'informations de suivi (même juste un identifiant unique universel (UUID)). Les utilisateurs vigilants à l'égard de telles possibilités devraient scanner les flux de trames concaténés pour tenter de détecter de telles trames pour analyse ou suppression.

Descriptions des champs​

Magic_Number (Nombre magique)​

Taille: 4 octets, format little-endian
Valeur: 0x184D2A5?, signifiant toute valeur de 0x184D2A50 à 0x184D2A5F

Toutes les 16 valeurs identifient valablement les trames sautables. Cette spécification ne détaille aucune méthode de marquage spécifique pour les trames sautables.

Plage du nombre magique:

  • Valeur minimale: 0x184D2A50
  • Valeur maximale: 0x184D2A5F
  • Total: 16 nombres magiques valides

Frame_Size (Taille de la trame)​

Taille: 4 octets, format little-endian, 32 bits non signés
Signification: La taille des User_Data suivantes en octets (n'incluant pas le nombre magique et le champ de taille lui-même)

Cela signifie que User_Data ne peut pas être supérieur à (2^32 - 1) octets.

Taille maximale de User_Data: 4.294.967.295 octets (environ 4 Go)

User_Data (Données utilisateur)​

Taille: Variable (spécifiée par Frame_Size)
Contenu: Données arbitraires

Ce champ peut contenir n'importe quoi. Les données seront ignorées par le décodeur.

Scénarios d'utilisation​

1. Incorporation de métadonnées​

  • Informations de version
  • Horodatages de création
  • Informations sur l'auteur
  • Données de licence

2. Filigrane et suivi​

  • Incorporation UUID
  • Suivi de source
  • Identification du canal de distribution

3. Données spécifiques à l'application​

  • En-têtes personnalisés
  • Configuration de l'application
  • Informations étendues

Notes de compatibilité​

Comportement du décodeur​

Un décodeur conforme à la spécification doit:

  1. Reconnaître le nombre magique: Détecter les nombres magiques dans la plage 0x184D2A5?
  2. Lire la taille: Analyser le champ Frame_Size
  3. Sauter les données: Sauter Frame_Size octets de User_Data
  4. Continuer le décodage: Continuer le traitement après la trame sautable

Recommandations pour l'encodeur​

Les encodeurs peuvent:

  1. Placement arbitraire: Insérer des trames sautables à n'importe quelle position dans le flux de trames
  2. Plusieurs trames: Insérer plusieurs trames sautables
  3. Marquage personnalisé: Utiliser l'un des 16 nombres magiques pour le marquage interne

Considérations de sécurité​

Problèmes de confidentialité​

Les trames sautables peuvent être utilisées pour:

  • Suivre le flux de données
  • Incorporer des informations cachées
  • Identifier la source des données

Mesures recommandées​

Pour les utilisateurs soucieux de la confidentialité:

  1. Détection par scan: Scanner le flux d'entrée pour détecter les trames sautables
  2. Analyse du contenu: Examiner le contenu de User_Data
  3. Suppression sélective: Supprimer les trames sautables selon les besoins
  4. Journalisation: Enregistrer les trames sautables détectées pour audit

Exemples​

Incorporation d'UUID​

Magic_Number: 0x184D2A50
Frame_Size: 16 (0x10000000, little-endian)
User_Data: [UUID de 16 octets]

Incorporation d'horodatage​

Magic_Number: 0x184D2A51
Frame_Size: 8
User_Data: [Horodatage Unix de 8 octets]

Compatibilité avec LZ4​

Le format des trames sautables est compatible avec LZ4, permettant:

  • Interopérabilité des outils entre formats
  • Traitement unifié des métadonnées
  • Implémentation simplifiée du décodeur

Note: Les trames sautables n'affectent pas le contenu des données décompressées, seulement les métadonnées du flux.

4. Entropy Encoding (Codage d'entropie)​

Le format Zstandard utilise deux types de codage d'entropie : FSE et le codage de Huffman. Huffman est utilisé pour compresser les littéraux (Literals), tandis que FSE est utilisé pour tous les autres symboles (Literals_Length_Code, Match_Length_Code et codes d'offset) et pour compresser les en-têtes Huffman.

4.1 FSE (Entropie à États Finis)​

FSE, abréviation de Finite State Entropy (Entropie à États Finis), est un codec d'entropie basé sur [ANS]. L'encodage/décodage FSE implique un état (State) qui est transmis entre les symboles, donc le décodage doit être effectué dans la direction opposée à l'encodage. Par conséquent, tous les flux de bits FSE (Bitstreams) sont lus de la fin au début. Notez que l'ordre des bits dans le flux n'est pas inversé ; ils sont simplement lus dans l'ordre inverse de celui dans lequel ils ont été écrits.

Pour plus de détails sur FSE, voir "FiniteStateEntropy" [FSE].

Le décodage FSE implique une table de décodage (Decoding Table) qui a une taille en puissance de 2 et contient trois éléments : Symbol (Symbole), Num_Bits (Nombre de bits) et Baseline (Ligne de base). Le logarithme en base 2 de la taille de la table est son Accuracy_Log (Log de précision). Une valeur d'état FSE représente un index dans cette table.

Pour obtenir la valeur d'état initiale, consommez Accuracy_Log bits du flux en tant que valeur little-endian. Le symbole suivant dans le flux est le Symbol indiqué dans la table pour cet état. Pour obtenir la valeur d'état suivante, le décodeur doit consommer Num_Bits bits du flux en tant que valeur little-endian et l'ajouter à Baseline.

4.1.1 FSE Table Description (Description de la table FSE)​

Pour décoder les flux FSE, il est nécessaire de construire la table de décodage. Le format Zstandard encode les descriptions de table FSE comme décrit ici.

Une table de distribution FSE (Distribution Table) décrit les probabilités de tous les symboles de 0 au dernier présent (inclus) sur une échelle normalisée de (1 &lt;&lt; Accuracy_Log). Notez qu'il doit y avoir deux symboles ou plus avec une probabilité non nulle.

Un flux de bits est lu vers l'avant, de manière little-endian. Il n'est pas nécessaire de connaître sa taille exacte, car la taille sera découverte et rapportée par le processus de décodage. Le flux de bits commence par indiquer l'échelle sur laquelle il opère. Si low4bits désigne les 4 bits les plus bas du premier octet, alors Accuracy_Log = low4bits + 5.

Ceci est suivi par chaque valeur de symbole, de 0 au dernier présent. Le nombre de bits utilisés par chaque champ est variable et dépend de :

Probabilités restantes + 1 : Par exemple, en supposant un Accuracy_Log de 8 et en supposant que 100 points de probabilité ont déjà été distribués, le décodeur peut lire n'importe quelle valeur de 0 à (256 - 100 + 1) == 157, inclus. Par conséquent, il doit lire log₂(157) == 8 bits.

Valeur décodée : Les petites valeurs utilisent 1 bit de moins. Par exemple, en supposant que les valeurs de 0 à 157, inclus, sont possibles, 255 - 157 = 98 valeurs restent dans un champ de 8 bits. Les 98 premières valeurs (donc de 0 à 97) n'utilisent que 7 bits, et les valeurs de 98 à 157 utilisent 8 bits. Ceci est réalisé grâce au schéma du tableau 20 :

+============+===============+===========+
| 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     |
+------------+---------------+-----------+

Tableau 20 : Valeurs décodées

Les probabilités des symboles sont lues une par une, dans l'ordre. La probabilité est obtenue à partir de la valeur décodée (Value Decoded) en utilisant la formule P = Value - 1. Cela signifie que la valeur 0 devient la probabilité négative -1. Il s'agit d'une probabilité spéciale qui signifie "inférieur à 1". Son effet sur la table de distribution est décrit ci-dessous. Aux fins du calcul des points de probabilité totaux alloués, elle compte pour 1.

Lorsqu'un symbole a une probabilité de zéro, il est suivi d'un drapeau de répétition (Repeat Flag) de 2 bits. Ce drapeau de répétition indique combien de probabilités de zéros suivent celle en cours. Il fournit un nombre allant de 0 à 3. Si c'est un 3, un autre drapeau de répétition de 2 bits suit, et ainsi de suite.

Lorsque le dernier symbole atteint un total cumulé de (1 &lt;&lt; Accuracy_Log), le décodage est terminé. Si le dernier symbole fait dépasser le total cumulé (1 &lt;&lt; Accuracy_Log), la distribution est considérée comme corrompue.

Enfin, le décodeur peut déterminer combien d'octets ont été utilisés dans ce processus et combien de symboles sont présents. Le flux de bits consomme un nombre rond d'octets. Tout bit restant dans le dernier octet est simplement inutilisé.

Le contexte dans lequel la table doit être utilisée spécifie un nombre attendu de symboles. Ce nombre attendu de symboles ne dépasse jamais 256. Si le nombre de symboles décodés n'est pas égal à celui attendu, l'en-tête doit être considéré comme corrompu.

La distribution des probabilités normalisées est suffisante pour créer une table de décodage unique. La table a une taille de (1 &lt;&lt; Accuracy_Log). Chaque cellule décrit le symbole décodé et les instructions pour obtenir l'état suivant.

Les symboles sont scannés dans leur ordre naturel pour les probabilités "inférieures à 1" comme décrit ci-dessus. Les symboles avec cette probabilité se voient attribuer une seule cellule, en commençant par la fin de la table et en reculant. Ces symboles définissent une réinitialisation complète de l'état (Full State Reset), lisant Accuracy_Log bits.

Tous les symboles restants sont alloués dans leur ordre naturel. En commençant par le symbole 0 et la position de table 0, chaque symbole se voit allouer autant de cellules que sa probabilité. L'allocation de cellules est dispersée, non linéaire ; chaque position successeur suit cette règle :

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

Une position est ignorée si elle est déjà occupée par un symbole de probabilité "inférieure à 1". La position ne se réinitialise pas entre les symboles ; elle itère simplement à travers chaque position de la table, passant au symbole suivant lorsque suffisamment d'états ont été alloués à celui en cours.

Le résultat est une liste de valeurs d'état. Chaque état décodera le symbole actuel.

Pour obtenir le Number_of_Bits et la Baseline requis pour l'état suivant, il est d'abord nécessaire de trier tous les états dans leur ordre naturel. Les états inférieurs nécessiteront 1 bit de plus que les états supérieurs. Le processus est répété pour chaque symbole.

Par exemple, en supposant qu'un symbole a une probabilité de 5, il reçoit cinq valeurs d'état. Les états sont triés dans l'ordre naturel. La puissance de 2 suivante est 8. L'espace des probabilités est divisé en 8 parties égales. En supposant que l'Accuracy_Log est de 7, cela définit 128 états, et chaque part (divisée par 8) a une taille de 16. Pour atteindre 8, 8 - 5 = 3 états les plus bas compteront "double", doublant le nombre de parts (32 de largeur), nécessitant 1 bit de plus dans le processus.

La Baseline est attribuée en commençant par les états supérieurs utilisant moins de bits, puis en procédant naturellement, puis en reprenant au premier état, chacun prenant sa largeur allouée de Baseline.

+----------------+-------+-------+--------+------+-------+
|  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 |
+----------------+-------+-------+--------+------+-------+

Tableau 21 : Attributions de Baseline

L'état suivant est déterminé à partir de l'état actuel en lisant le Number_of_Bits requis et en ajoutant la Baseline spécifiée.

Voir l'annexe A pour les résultats de ce processus appliqués aux distributions par défaut.

4.2 Huffman Coding (Codage de Huffman)​

Les flux codés Huffman de Zstandard sont lus en arrière, similaires aux flux de bits FSE. Par conséquent, pour trouver le début du flux de bits, il est nécessaire de connaître le décalage du dernier octet du flux codé Huffman.

Après avoir écrit le dernier bit contenant des informations, le compresseur écrit un seul bit 1, puis remplit le reste de l'octet avec des bits 0. Le dernier octet du flux de bits compressé ne peut pas être 0 pour cette raison.

Lors de la décompression, le dernier octet contenant le rembourrage est le premier octet à lire. Le décompresseur doit ignorer jusqu'à 7 bits de rembourrage 0 ainsi que le premier bit 1 qui se produit. Ensuite, la partie utile du flux de bits commence.

Le flux de bits contient des symboles codés Huffman dans l'ordre little-endian, avec les codes définis par la méthode ci-dessous.

4.2.1 Huffman Tree Description (Description de l'arbre de Huffman)​

Le codage préfixe (Prefix Coding) représente les symboles d'un alphabet connu a priori par des séquences de bits (mots de code), un mot de code pour chaque symbole, de manière à ce que différents symboles puissent être représentés par des séquences de bits de différentes longueurs, mais qu'un analyseur puisse toujours analyser une chaîne codée sans ambiguïté, symbole par symbole.

Étant donné un alphabet avec des fréquences de symboles connues, l'algorithme de Huffman permet la construction d'un code préfixe optimal utilisant le moins de bits de tous les codes préfixes possibles pour cet alphabet.

Le code préfixe ne doit pas dépasser une longueur de code maximale. Plus de bits améliorent la précision mais donnent une taille d'en-tête plus grande et nécessitent plus de mémoire ou des opérations de décodage plus complexes. Cette spécification limite la longueur de code maximale à 11 bits.

Toutes les valeurs littérales de zéro (inclus) à la dernière présente (exclus) sont représentées par Weight (Poids) avec des valeurs de 0 à Max_Number_of_Bits. La transformation de Weight à Number_of_Bits suit ce pseudo-code :

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

Le Weight du dernier symbole est déduit de ceux précédemment décodés, en complétant à la puissance de 2 la plus proche. Cette puissance de 2 donne Max_Number_of_Bits, la profondeur de l'arbre actuel.

(Suite avec les tableaux 22-26 et les détails du codage de Huffman)

5. Dictionary Format (Format de dictionnaire)​

Zstandard est compatible avec les dictionnaires de "contenu brut" (Raw Content Dictionaries), sans aucune restriction de format, sauf qu'ils doivent faire au moins 8 octets. Ces dictionnaires fonctionnent comme s'ils n'étaient que la partie contenu d'un dictionnaire formaté.

Cependant, les dictionnaires créés par zstd --train dans l'implémentation de référence suivent un format spécifique, décrit ici.

Les dictionnaires ne sont pas inclus dans le contenu compressé mais sont plutôt fournis hors bande (Out of Band). C'est-à-dire que le Dictionary_ID identifie lequel doit être utilisé, mais cette spécification ne décrit pas le mécanisme par lequel le dictionnaire est obtenu avant utilisation pendant la compression ou la décompression.

Un dictionnaire a une taille, définie soit par une limite de tampon, soit par une taille de fichier. Le format général est :

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

Tableau 27 : Format général du dictionnaire

Magic_Number (Nombre magique) : ID de 4 octets, valeur 0xEC30A437, format little-endian.

Dictionary_ID (ID de dictionnaire) : 4 octets, stockés au format little-endian. Dictionary_ID peut être n'importe quelle valeur, sauf 0 (qui signifie pas de Dictionary_ID). Il est utilisé par les décodeurs pour vérifier qu'ils utilisent le bon dictionnaire. Si la trame doit être distribuée dans un environnement privé, n'importe quel Dictionary_ID peut être utilisé. Cependant, pour la distribution publique de trames compressées, les plages suivantes sont réservées et ne doivent pas être utilisées :

  • Plage basse : &lt;= 32767
  • Plage haute : >= 2³¹

Entropy_Tables (Tables d'entropie) : Suivent le même format que les tables dans les blocs compressés. Voir les sections FSE et Huffman pertinentes pour savoir comment décoder ces tables. Elles sont stockées dans l'ordre suivant : table Huffman pour les littéraux, table FSE pour les offsets, table FSE pour les longueurs de correspondance et table FSE pour les longueurs de littéraux. Ces tables remplissent le mode littéraux de statistiques répétées (Repeat Stats Literals Mode) et le mode de distribution répétée (Repeat Distribution Mode) pour le décodage de séquence. Elles sont finalement suivies de 3 valeurs d'offset, remplissant les offsets répétés (au lieu d'utiliser {1,4,8}), stockées dans l'ordre, 4 octets little-endian chacune, pour un total de 12 octets. Chaque offset répété doit avoir une valeur inférieure à la taille du dictionnaire.

Content (Contenu) : Le reste du dictionnaire est son contenu. Le contenu agit comme un "passé" devant les données à compresser ou à décompresser, de sorte qu'il puisse être référencé dans les commandes de séquence (Sequence Commands). Tant que la quantité de données décodées de cette trame est inférieure ou égale à Window_Size, les commandes de séquence peuvent spécifier des offsets plus longs que la longueur totale de sortie décodée jusqu'à présent pour référencer le dictionnaire, même les parties du dictionnaire avec des offsets supérieurs à Window_Size. Après que la sortie totale a dépassé Window_Size, cependant, cela n'est plus autorisé, et le dictionnaire n'est plus accessible.

6. Use of Dictionaries (Utilisation des dictionnaires)​

La mise à disposition de l'utilisation de dictionnaires avec zstd est en cours d'exploration. Voir, par exemple, [DICT-SEC]. Le résultat probable sera un registre de dictionnaires bien testés optimisés pour différents cas d'utilisation et des identificateurs pour chacun, éventuellement avec un mécanisme de négociation privée pour l'utilisation de dictionnaires non enregistrés.

Pour assurer la compatibilité avec la spécification future de l'utilisation de dictionnaires avec les charges utiles zstd, en particulier avec MIME, le contenu encodé avec le type de média enregistré ici ne devrait pas utiliser de dictionnaire. L'exception à cette exigence pourrait être une négociation de dictionnaire privée, suggérée ci-dessus, qui ne fait pas partie de cette spécification.

7. IANA Considerations (Considérations IANA)​

L'IANA a mis à jour deux enregistrements préexistants et effectué un nouvel enregistrement, comme décrit ci-dessous.

7.1 The 'application/zstd' Media Type (Le type de média 'application/zstd')​

Le type de média application/zstd identifie un bloc de données compressées en utilisant zstd. Les données sont le flux d'octets décrit dans ce document. L'IANA a ajouté ce qui suit au registre "Media Types" (types de médias):

Type name (Nom de type) : application

Subtype name (Nom de sous-type) : zstd

Required parameters (Paramètres requis) : N/A

Optional parameters (Paramètres facultatifs) : N/A

Encoding considerations (Considérations d'encodage) : binary

Security considerations (Considérations de sécurité) : Voir la section 8 de RFC 8878.

Interoperability considerations (Considérations d'interopérabilité) : N/A

Published specification (Spécification publiée) : RFC 8878

Applications which use this media type (Applications utilisant ce type de média) : Partout où la taille des données est un problème

Fragment identifier considerations (Considérations d'identificateur de fragment) : Aucun identificateur de fragment n'est défini pour ce type.

Additional information (Informations supplémentaires) :

  • Deprecated alias names for this type (Noms d'alias obsolètes pour ce type): N/A
  • Magic number(s) (Nombre(s) magique(s)): 4 octets, format little-endian. Valeur: 0xFD2FB528
  • File extension(s) (Extension(s) de fichier): zst
  • Macintosh file type code(s) (Code(s) de type de fichier Macintosh): N/A

Person & email address to contact for further information (Personne et adresse e-mail à contacter pour plus d'informations) : Yann Collet <[email protected]>

Intended usage (Usage prévu) : common (commun)

Restrictions on usage (Restrictions d'usage) : N/A

Author (Auteur) : Murray S. Kucherawy

Change Controller (Contrôleur de changements) : IETF

Provisional registration (Enregistrement provisoire) : no

For further information (Pour plus d'informations) : Voir [ZSTD]

7.2 Content Encoding (Encodage de contenu)​

L'IANA a ajouté l'entrée suivante au "HTTP Content Coding Registry" (registre d'encodage de contenu HTTP) dans le registre "Hypertext Transfer Protocol (HTTP) Parameters" (paramètres du protocole de transfert hypertexte (HTTP)):

Name (Nom) : zstd

Description (Description) : Un flux d'octets compressé en utilisant le protocole Zstandard

Reference (Référence) : RFC 8878

7.3 Structured Syntax Suffix (Suffixe de syntaxe structurée)​

L'IANA a enregistré ce qui suit dans le registre "Structured Syntax Suffix" (suffixe de syntaxe structurée):

Name (Nom) : Zstandard

+suffix (suffixe) : +zstd

Encoding Considerations (Considérations d'encodage) : binary

Interoperability Considerations (Considérations d'interopérabilité) : N/A

Fragment Identifier Considerations (Considérations d'identificateur de fragment) : La syntaxe et la sémantique des identificateurs de fragment spécifiés pour +zstd DOIVENT être identiques à celles spécifiées pour application/zstd.

Security Considerations (Considérations de sécurité) : Voir la section 8 de RFC 8878.

Contact (Contact) : Veuillez consulter l'auteur du type de média application/zstd.

Author/Change Controller (Auteur/Contrôleur de changements) : IETF

7.4 Dictionaries (Dictionnaires)​

Des travaux sont en cours pour développer des dictionnaires qui optimiseront la compression et la décompression de types spécifiques de données. La spécification de tels dictionnaires pour un usage public nécessitera l'enregistrement de points de code à partir de la plage réservée décrite dans la section 3.1.1.1.3 et leur association avec un dictionnaire spécifique.

Actuellement, aucun dictionnaire de ce type n'est publié pour un usage public, donc ce document ne demande pas immédiatement à l'IANA de créer un tel registre.

8. Security Considerations (Considérations de sécurité)​

Toute méthode de compression de données implique la réduction de la redondance dans les données. Zstandard ne fait pas exception, et les précautions habituelles s'appliquent.

On ne devrait jamais compresser un message dont le contenu doit rester secret avec un message généré par un tiers. Une telle compression peut être utilisée pour deviner le contenu du message secret par l'analyse de la réduction d'entropie (Entropy Reduction Analysis). Cela a été démontré dans l'attaque CRIME (Compression Ratio Info-leak Made Easy) [CRIME], par exemple.

Un décodeur doit démontrer des capacités pour détecter et prévenir tout type de falsification de données dans la trame compressée qui pourrait déclencher des défaillances système, telles que la lecture ou l'écriture au-delà des plages de mémoire autorisées. Cela peut être garanti soit par le langage d'implémentation, soit par des vérifications de limites (Bound Checking) soigneuses. Il convient de noter en particulier l'encodage des valeurs Number_of_Sequences qui font lire le décodeur dans l'en-tête de bloc (et au-delà), ainsi que l'indication d'un Frame_Content_Size inférieur aux données réellement décompressées, dans une tentative de déclencher un dépassement de tampon (Buffer Overflow). Il est fortement recommandé de tester par fuzzing (fuzz-test, c'est-à-dire fournir des entrées invalides, inattendues ou aléatoires et vérifier le fonctionnement sûr) les implémentations de décodeur pour tester et renforcer leur capacité à détecter les trames incorrectes et à les gérer sans aucun effet secondaire système indésirable.

Un attaquant peut fournir des trames compressées correctement formées avec des exigences mémoire déraisonnables. Un décodeur doit toujours contrôler les exigences mémoire et imposer certaines limites (spécifiques au système) afin de protéger l'utilisation de la mémoire contre de tels scénarios.

La compression peut être optimisée en entraînant un dictionnaire sur une variété de charges utiles de contenu connexes. Ce dictionnaire doit ensuite être disponible au décodeur pour que la décompression de la charge utile soit possible. Bien que ce document ne spécifie pas comment acquérir un dictionnaire pour une charge utile compressée donnée, il convient de noter que les dictionnaires tiers peuvent interagir de manière inattendue avec un décodeur, entraînant d'éventuelles attaques par épuisement de mémoire ou d'autres ressources (Resource-exhaustion Attacks). Nous nous attendons à ce que ces sujets soient discutés plus en détail dans la section Considérations de sécurité d'un RFC à venir sur l'acquisition et la transmission de dictionnaires, mais nous soulignons ce problème maintenant par excès de prudence.

Comme discuté dans la section 3.1.2, il est possible de stocker des métadonnées utilisateur arbitraires dans des trames ignorables (Skippable Frames). Bien que de telles trames soient ignorées lors de la décompression des données, elles peuvent être utilisées comme filigrane (Watermark) pour suivre le chemin de la charge utile compressée.

Appendix A. Decoding Tables for Predefined Codes (Annexe A. Tables de décodage pour les codes prédéfinis)​

Cette annexe contient les tables de décodage FSE pour les codes de longueur de littéral, de longueur de correspondance et d'offset prédéfinis. Ces tables sont construites en utilisant l'algorithme donné dans la section 4.1.1. Les tables ici peuvent être utilisées comme exemple pour vérifier de manière croisée qu'une implémentation construit correctement ses tables de décodage.

A.1. Literals Length Code Table (Table des codes de longueur de littéral)​

State (État)Symbol (Symbole)Number_Of_Bits (Nombre de bits)Base
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

Tableau 28: Table des codes de longueur de littéral

A.2. Match Length Code Table (Table des codes de longueur de correspondance)​

State (État)Symbol (Symbole)Number_Of_Bits (Nombre de bits)Base
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

Tableau 29: Table des codes de longueur de correspondance

A.3. Offset Code Table (Table des codes d'offset)​

State (État)Symbol (Symbole)Number_Of_Bits (Nombre de bits)Base
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

Tableau 30: Table des codes d'offset

Appendix B. Changes since RFC 8478 (Annexe B. Modifications depuis RFC 8478)​

Voici les modifications apportées dans ce document par rapport à RFC 8478:

  • Application des errata [Err5786] et [Err6303].

  • Clarification de la compatibilité avancée concernant les dictionnaires.

  • Clarification de l'application de Block_Maximum_Size.

  • Ajout de l'enregistrement du suffixe de type de média structuré.

  • Clarification que la somme de contrôle du contenu est toujours de 4 octets.

  • Clarification de la gestion des entrées réservées et corrompues.

  • Ajout de considérations sur les identificateurs de fragments à l'enregistrement du type de média.

Acknowledgments (Remerciements)​

zstd a été développé par Yann Collet.

Felix Handte et Nick Terrell ont fourni des commentaires qui ont été intégrés dans cette révision et RFC 8478. RFC 8478 a également reçu des contributions de Bobo Bose-Kolanu, Kyle Nekritz et David Schleimer.

Authors' Addresses (Adresses des Auteurs)​

Yann Collet
Facebook
1 Hacker Way
Menlo Park, CA 94025
États-Unis d'Amérique

Email: [email protected]

Murray S. Kucherawy (éditeur)
Facebook
1 Hacker Way
Menlo Park, CA 94025
États-Unis d'Amérique

Email: [email protected]