Aller au contenu principal

1. Introduction

1. Introduction​

1.1. Objectif (Purpose)​

L'objectif de cette spécification est de définir un format de données compressées sans perte (Lossless Compressed Data Format) qui :

  • est indépendant du type de CPU, du système d'exploitation, du système de fichiers et du jeu de caractères ; il peut donc être utilisé pour l'échange de données.

  • peut être produit ou consommé, même pour un flux de données d'entrée arbitrairement long présenté de manière séquentielle, en utilisant uniquement une quantité de stockage intermédiaire limitée a priori ; il peut donc être utilisé dans les communications de données ou des structures similaires, telles que les filtres Unix.

  • compresse les données avec un ratio de compression (Compression Ratio) comparable aux meilleures méthodes de compression à usage général actuellement disponibles, en particulier considérablement mieux que le programme gzip.

  • décompresse beaucoup plus rapidement que les implémentations LZMA actuelles.

Le format de données défini par cette spécification ne tente pas de :

  • permettre l'accès aléatoire aux données compressées.

  • compresser les données spécialisées (par exemple, les graphiques raster) aussi densément que les meilleurs algorithmes spécialisés actuellement disponibles.

Ce document est la spécification faisant autorité du format de données compressées brotli. Il définit l'ensemble des flux de données compressées brotli valides et un algorithme de décodeur (Decoder Algorithm) qui produit le flux de données non compressées à partir d'un flux de données compressées brotli valide.

1.2. Public visé (Intended Audience)​

Cette spécification est destinée aux développeurs de logiciels pour compresser des données dans et/ou décompresser des données du format brotli.

Le texte de la spécification suppose une formation de base en programmation au niveau des bits et autres représentations de données primitives. La familiarité avec la technique de codage de Huffman (Huffman Coding) est utile mais non requise.

Cette spécification utilise (de manière intensive) les notations et la terminologie introduites dans la spécification du format DEFLATE [RFC1951]. Par souci d'exhaustivité, nous incluons toujours le texte complet des parties pertinentes de la RFC 1951 ; par conséquent, la familiarité avec le format DEFLATE est utile mais non requise.

Le format de données compressées défini dans cette spécification fait partie intégrante du format de fichier WOFF 2.0 [WOFF2] ; par conséquent, cette spécification est également destinée aux développeurs de compresseurs et décompresseurs WOFF 2.0.

1.3. Portée (Scope)​

Ce document spécifie une méthode pour représenter une séquence d'octets (Sequence of Bytes) sous la forme d'une séquence de bits (Sequence of Bits) (généralement plus courte) et une méthode pour empaqueter cette dernière séquence de bits dans des octets.

1.4. Conformité (Compliance)​

Sauf indication contraire ci-dessous, un décompresseur conforme (Compliant Decompressor) doit être capable d'accepter et de décompresser tout ensemble de données conforme à toutes les spécifications présentées ici. Un compresseur conforme (Compliant Compressor) doit produire des ensembles de données conformes à toutes les spécifications présentées ici.

1.5. Définitions des termes et conventions utilisées (Definitions of Terms and Conventions Used)​

Octet (Byte) : 8 bits stockés ou transmis en tant qu'unité (identique à un octet). Pour cette spécification, un octet contient exactement 8 bits, même sur les machines qui stockent un caractère sur un nombre de bits différent de huit. Voir ci-dessous pour la numérotation des bits dans un octet.

Chaîne (String) : une séquence d'octets arbitraires.

Les octets stockés dans un ordinateur n'ont pas d'"ordre de bits", car ils sont toujours traités comme une unité. Cependant, un octet considéré comme un entier entre 0 et 255 a un bit le plus significatif (msb) et le moins significatif (lsb), et puisque nous écrivons les nombres avec le chiffre le plus significatif à gauche, nous écrivons également les octets avec le bit le plus significatif à gauche. Dans les diagrammes ci-dessous, nous numérotons les bits d'un octet de sorte que le bit 0 soit le bit le moins significatif, c'est-à-dire que les bits sont numérotés :

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

Dans un ordinateur, un nombre peut occuper plusieurs octets. Tous les nombres multi-octets du format décrit ici sont stockés avec l'octet le moins significatif (Least-Significant Byte) en premier (à l'adresse mémoire inférieure). Par exemple, le nombre décimal 520 est stocké comme suit :

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

1.5.1. Empaquetage dans les octets (Packing into Bytes)​

Ce document n'aborde pas la question de l'ordre dans lequel les bits d'un octet sont transmis sur un support bit-séquentiel, car le format de données final décrit ici est orienté octet plutôt que bit. Cependant, nous décrivons le format de bloc compressé (Compressed Block Format) ci-dessous comme une séquence d'éléments de données de longueurs de bits variables, et non comme une séquence d'octets. Nous devons donc spécifier comment empaqueter ces éléments de données dans des octets pour former la séquence d'octets compressés finale :

  • Les éléments de données sont empaquetés dans les octets dans l'ordre croissant du numéro de bit dans l'octet, c'est-à-dire en commençant par le bit le moins significatif de l'octet.

  • Les éléments de données autres que les codes de Huffman (Huffman Code) sont empaquetés en commençant par le bit le moins significatif de l'élément de données.

  • Les codes de Huffman sont empaquetés en commençant par le bit le plus significatif du code.

En d'autres termes, si l'on devait imprimer les données compressées sous forme de séquence d'octets, en commençant par le premier octet à la marge droite et en progressant vers la gauche, avec le bit le plus significatif de chaque octet à gauche comme d'habitude, on pourrait analyser le résultat de droite à gauche, avec les éléments de largeur fixe dans l'ordre MSB à LSB correct et les codes de Huffman dans l'ordre inversé de bits (c'est-à-dire avec le premier bit du code en position LSB relative).

À titre d'exemple, considérons l'empaquetage des éléments de données suivants dans une séquence de 3 octets :

  • Valeur 2 bits 1 (binaire 01)
  • Valeur 3 bits 2 (binaire 010)
  • Valeur 5 bits 6 (binaire 00110)
  • Code 4 bits avec motif de bits 1011 (le premier bit étant 1, le deuxième bit étant 0, le troisième bit étant 1 et le quatrième bit étant 1)
  • Valeur 2 bits 0 (binaire 00)
  • Code 4 bits avec motif de bits 0011
  • Valeur 5 bits 31 (binaire 11111)

Le diagramme suivant montre comment ces éléments sont empaquetés :

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

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

Dernière mise à jour le