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.

Champ	Taille
Literals_Block_Type	2 bits
Size_Format	1-2 bits
Regenerated_Size	5-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.

---