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-6 | Literal_Lengths_Mode |
| 5-4 | Offsets_Mode |
| 3-2 | Match_Lengths_Mode |
| 1-0 | Reserved (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) |
|---|---|
| 0 | Predefined_Mode (Mode prédéfini) |
| 1 | RLE_Mode (Mode RLE) |
| 2 | FSE_Compressed_Mode (Mode compressé FSE) |
| 3 | Repeat_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_Code | Baseline | Number_of_Bits |
|---|---|---|
| 0-15 | length | 0 |
| 16 | 16 | 1 |
| 17 | 18 | 1 |
| 18 | 20 | 1 |
| 19 | 22 | 1 |
| 20 | 24 | 2 |
| 21 | 28 | 2 |
| 22 | 32 | 3 |
| 23 | 40 | 3 |
| 24 | 48 | 4 |
| 25 | 64 | 6 |
| 26 | 128 | 7 |
| 27 | 256 | 8 |
| 28 | 512 | 9 |
| 29 | 1024 | 10 |
| 30 | 2048 | 11 |
| 31 | 4096 | 12 |
| 32 | 8192 | 13 |
| 33 | 16384 | 14 |
| 34 | 32768 | 15 |
| 35 | 65536 | 16 |
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_Code | Baseline | Number_of_Bits |
|---|---|---|
| 0-31 | Match_Length_Code + 3 | 0 |
| 32 | 35 | 1 |
| 33 | 37 | 1 |
| 34 | 39 | 1 |
| 35 | 41 | 1 |
| 36 | 43 | 2 |
| 37 | 47 | 2 |
| 38 | 51 | 3 |
| 39 | 59 | 3 |
| 40 | 67 | 4 |
| 41 | 83 | 4 |
| 42 | 99 | 5 |
| 43 | 131 | 7 |
| 44 | 259 | 8 |
| 45 | 515 | 9 |
| 46 | 1027 | 10 |
| 47 | 2051 | 11 |
| 48 | 4099 | 12 |
| 49 | 8195 | 13 |
| 50 | 16387 | 14 |
| 51 | 32771 | 15 |
| 52 | 65539 | 16 |
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
};