Aller au contenu principal

11. Considérations pour les implémentations de compresseur

11. Considérations pour les implémentations de compresseur (Considerations for Compressor Implementations)​

Étant donné que l'intention de ce document est de définir le format de données compressées brotli sans référence à un algorithme de compression particulier, le matériel de cette section ne fait pas partie de la définition du format, et un compresseur n'a pas besoin de le suivre pour être conforme.

11.1. Compresseur trivial (Trivial Compressor)​

Dans cette section, nous présentons un algorithme très simple qui produit un flux brotli valide représentant une séquence arbitraire d'octets non compressés sous la forme de la fonction en langage C++ suivante.

string BrotliCompressTrivial(const string& u) {
   if (u.empty()) {
      return string(1, 6);
   }
   int i;
   string c;
   c.append(1, 12);
   for (i = 0; i + 65535 < u.size(); i += 65536) {
      c.append(1, 248);
      c.append(1, 255);
      c.append(1, 15);
      c.append(&u[i], 65536);
   }
   if (i < u.size()) {
      int r = u.size() - i - 1;
      c.append(1, (r & 31) << 3);
      c.append(1, r >> 5);
      c.append(1, 8 + (r >> 13));
      c.append(&u[i], r + 1);
   }
   c.append(1, 3);
   return c;
}

Notez que cet algorithme simple ne compresse pas réellement les données, c'est-à-dire que la représentation brotli sera toujours plus grande que l'originale, mais il montre que chaque séquence de N octets non compressés peut être représentée avec un flux brotli valide qui n'est pas plus long que N + (3 * (N >> 16) + 5) octets.

11.2. Alignement des méta-blocs compressés sur les limites d'octets​

Comme décrit dans la section 9, seuls les méta-blocs qui suivent immédiatement un méta-bloc non compressé ou un méta-bloc de métadonnées sont garantis de commencer sur une limite d'octet. Dans certaines applications, il peut être nécessaire que chaque méta-bloc non-métadonnées commence sur une limite d'octet. Cela peut être réalisé en ajoutant un méta-bloc de métadonnées vide après chaque méta-bloc non-métadonnées qui ne se termine pas sur une limite d'octet.

11.3. Création de parties autonomes dans les données compressées​

Dans certaines implémentations d'encodeur, il peut être nécessaire de rendre une séquence d'octets dans un flux brotli autonome, c'est-à-dire qu'elle puisse être décompressée indépendamment des parties précédentes des données compressées. C'est une fonctionnalité utile pour trois raisons. Premièrement, si un grand fichier compressé est endommagé, il est possible de récupérer une partie du fichier après les dommages. Deuxièmement, c'est utile lors du transfert différentiel de données compressées. Si une séquence d'octets non compressés est inchangée et compressée indépendamment des données précédentes, alors la représentation compressée peut également être inchangée et peut donc être transférée à très bon marché. Troisièmement, si des séquences d'octets non compressés sont compressées indépendamment, cela permet la compression parallèle de ces séquences d'octets dans le même fichier, en plus de la compression parallèle de plusieurs fichiers.

Étant donné deux séquences d'octets non compressés, U0 et U1, nous allons maintenant décrire comment créer deux séquences d'octets compressés, C0 et C1, de sorte que la concaténation de C0 et C1 soit un flux brotli valide, et que C0 et C1 (avec le premier octet de C0 qui contient la taille de la fenêtre) puissent être décompressés indépendamment l'un de l'autre en U0 et U1.

Lors de la compression de la séquence d'octets U0 pour produire C0, nous pouvons utiliser n'importe quel compresseur qui fonctionne sur l'ensemble complet d'octets non compressés U0, avec les deux modifications suivantes. Premièrement, le bit ISLAST du dernier méta-bloc de C0 ne doit pas être défini. Deuxièmement, C0 doit se terminer à une limite d'octet, ce qui peut être assuré en lui ajoutant un méta-bloc de métadonnées vide, comme dans la section 11.2.

Lors de la compression de la séquence d'octets U1 pour produire C1, nous pouvons utiliser n'importe quel compresseur qui démarre un nouveau méta-bloc au début de U1 dans le flux d'entrée U0+U1, avec les deux modifications suivantes. Premièrement, les distances arrière dans C1 ne doivent pas faire référence à des mots du dictionnaire statique ou à des octets non compressés dans U0. Même si une séquence d'octets dans U1 correspondrait à un mot du dictionnaire statique, ou à une séquence d'octets qui chevauche U0, le compresseur doit représenter cette séquence d'octets avec une combinaison d'insertions littérales et de références arrière aux octets dans U1 à la place. Deuxièmement, le tampon circulaire des quatre dernières distances doit être rempli d'abord avec des distances dans C1 avant de l'utiliser pour encoder d'autres distances dans C1. Notez que les deux compresseurs produisant C0 et C1 doivent utiliser la même taille de fenêtre, mais l'en-tête de flux n'est émis que par le compresseur qui produit C0.

Notez que cette méthode peut être facilement généralisée à plus de deux séquences d'octets non compressés.

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

Dernière mise à jour le