Passa al contenuto principale

3.1.1.3. Compressed Blocks (Blocchi compressi)

Per decomprimere un blocco compresso, la dimensione compressa deve essere fornita dal campo Block_Size nel Block_Header.

Un blocco compresso è composto da due parti: Literals_Section (sezione letterali, sezione 3.1.1.3.1) e Sequences_Section (sezione sequenze, sezione 3.1.1.3.2). I risultati di queste due parti vengono quindi combinati per generare dati decompressi nell'esecuzione della sequenza (sezione 3.1.1.4).

Per decodificare un blocco compresso, sono necessari i seguenti elementi:

  • Dati precedentemente decodificati, fino a una distanza di Window_Size, o l'inizio del frame, a seconda di quale sia minore. In quest'ultimo caso, Single_Segment_Flag sarà impostato.

  • Elenco "offset recenti", dal Compressed_Block precedente.

  • Albero Huffman precedente, necessario per il tipo Treeless_Literals_Block.

  • Tabelle di decodifica Finite State Entropy (FSE) precedenti, necessarie per Repeat_Mode, per ogni tipo di simbolo (codici lunghezza letterale, codici lunghezza corrispondenza, codici offset).

Si noti che le tabelle di decodifica non provengono sempre dal Compressed_Block precedente:

  • Ogni tabella di decodifica può provenire dal dizionario.
  • L'albero Huffman proviene dal Compressed_Literals_Block precedente.

3.1.1.3.1. Literals_Section_Header (Intestazione sezione letterali)​

Tutti i letterali vengono riassemblati nella prima parte del blocco. Possono essere decodificati per primi, quindi copiati durante l'esecuzione della sequenza (vedere sezione 3.1.1.4), oppure possono essere decodificati al volo durante l'esecuzione della sequenza.

I letterali possono essere memorizzati non compressi o compressi utilizzando il codice prefisso Huffman. Quando compressi, può essere presente una descrizione dell'albero opzionale, seguita da 1 o 4 flussi.

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

Tabella 11: Letterali compressi

3.1.1.3.1.1. Literals_Section_Header (Intestazione sezione letterali)​

Questo campo descrive come sono impacchettati i letterali. È un campo di bit di dimensione variabile allineato ai byte, che va da 1 a 5 byte, utilizzando la convenzione little-endian.

CampoDimensione
Literals_Block_Type2 bit
Size_Format1-2 bit
Regenerated_Size5-20 bit
[Compressed_Size]0-18 bit

Tabella 12: Literals_Section_Header

In questa rappresentazione, i bit superiori sono nella posizione più bassa.

Il campo Literals_Block_Type utilizza i due bit più bassi del primo byte e descrive quattro tipi di blocchi diversi:

Literals_Block_Type (Tipo blocco letterali)Value (Valore)
Raw_Literals_Block (Letterali grezzi)0
RLE_Literals_Block (Letterali RLE)1
Compressed_Literals_Block (Letterali compressi)2
Treeless_Literals_Block (Letterali senza albero)3

Tabella 13: Literals_Block_Type

Raw_Literals_Block (Letterali grezzi) : I letterali sono memorizzati non compressi. Literals_Section_Content è Regenerated_Size.

RLE_Literals_Block (Letterali RLE) : I letterali consistono in un singolo valore di byte ripetuto Regenerated_Size volte. Literals_Section_Content è 1.

Compressed_Literals_Block (Letterali compressi) : Si tratta di un blocco compresso Huffman standard, che inizia con una descrizione dell'albero Huffman. Vedere i dettagli di seguito. Literals_Section_Content è Compressed_Size.

Treeless_Literals_Block (Letterali senza albero) : Si tratta di un blocco compresso Huffman che utilizza l'albero Huffman dal Compressed_Literals_Block precedente, o se non c'è un blocco di letterali compressi Huffman precedente, dal dizionario. Huffman_Tree_Description viene saltata. Si noti che se questa modalità viene attivata senza alcuna tabella Huffman precedente nel frame (o dizionario secondo la sezione 5), ciò dovrebbe essere considerato come corruzione dei dati. Literals_Section_Content è Compressed_Size.

Size_Format si divide in due famiglie:

  • Per Raw_Literals_Block e RLE_Literals_Block, solo Regenerated_Size deve essere decodificato. Non c'è campo Compressed_Size.

  • Per Compressed_Block e Treeless_Literals_Block, sia Compressed_Size che Regenerated_Size (dimensione decompressa) devono essere decodificati. Anche il numero di flussi (1 o 4) deve essere decodificato.

Per i valori che coprono più byte, la convenzione è little-endian.

Size_Format per Raw_Literals_Block e RLE_Literals_Block utilizza 1 o 2 bit. Il suo valore è (Literals_Section_Header[0]>>2) & 0x3.

  • Size_Format == 00 o 10: Size_Format utilizza 1 bit. Regenerated_Size utilizza 5 bit (valore 0-31). Literals_Section_Header utilizza 1 byte. Regenerated_Size = Literal_Section_Header[0]>>3.

  • Size_Format == 01: Size_Format utilizza 2 bit. Regenerated_Size utilizza 12 bit (valore 0-4095). Literals_Section_Header utilizza 2 byte. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4).

  • Size_Format == 11: Size_Format utilizza 2 bit. Regenerated_Size utilizza 20 bit (valore 0-1048575). Literals_Section_Header utilizza 3 byte. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12).

Per questi casi, esiste solo Stream_1. Si noti che è consentito utilizzare un formato lungo per rappresentare un valore breve (ad esempio, 13), anche se ciò è inefficiente.

Size_Format per Compressed_Literals_Block e Treeless_Literals_Block utilizza sempre 2 bit.

  • Size_Format == 00: Un singolo flusso. Sia Regenerated_Size che Compressed_Size utilizzano 10 bit (valore 0-1023). Literals_Section_Header utilizza 3 byte.

  • Size_Format == 01: 4 flussi. Sia Regenerated_Size che Compressed_Size utilizzano 10 bit (valore 0-1023). Literals_Section_Header utilizza 3 byte.

  • Size_Format == 10: 4 flussi. Sia Regenerated_Size che Compressed_Size utilizzano 14 bit (valore 0-16383). Literals_Section_Header utilizza 4 byte.

  • Size_Format == 11: 4 flussi. Sia Regenerated_Size che Compressed_Size utilizzano 18 bit (valore 0-262143). Literals_Section_Header utilizza 5 byte.

Sia i campi Compressed_Size che Regenerated_Size seguono la convenzione little-endian. Si noti che Compressed_Size, quando presente, include la dimensione di Huffman_Tree_Description.

3.1.1.3.1.2. Raw_Literals_Block (Letterali grezzi)​

I dati in Stream_1 sono lunghi Regenerated_Size byte. Contengono i dati letterali grezzi utilizzati durante l'esecuzione della sequenza (sezione 3.1.1.3.2).

3.1.1.3.1.3. RLE_Literals_Block (Letterali RLE)​

Stream_1 è composto da un singolo byte che deve essere ripetuto Regenerated_Size volte per produrre i letterali decodificati.

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block (Letterali compressi e senza albero)​

Entrambe le modalità contengono dati codificati Huffman. Per Treeless_Literals_Block, la tabella Huffman proviene dal blocco di letterali compressi precedente o dal dizionario; vedere sezione 5.

3.1.1.3.1.5. Huffman_Tree_Description (Descrizione albero Huffman)​

Questa parte è presente solo se il tipo Literals_Block_Type è Compressed_Literals_Block (2). Il formato di Huffman_Tree_Description si trova nella sezione 4.2.1. La dimensione di Huffman_Tree_Description è determinata durante la decodifica. Deve essere utilizzata per determinare dove iniziano i flussi.

Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size

3.1.1.3.1.6. Jump_Table (Tabella di salto)​

La Jump_Table è presente solo se ci sono 4 flussi codificati Huffman.

(Promemoria: I dati compressi Huffman sono composti da 1 o 4 flussi codificati Huffman.)

Se c'è solo 1 flusso, è un singolo flusso di bit che occupa l'intera parte rimanente del blocco di letterali, codificato come descritto nella sezione 4.2.2.

Se ci sono 4 flussi, Literals_Section_Header fornisce solo informazioni sufficienti per conoscere la dimensione decompressa e compressa di tutti e 4 i flussi combinati. La dimensione decompressa di ciascun flusso è uguale a (Regenerated_Size+3)/4, tranne per l'ultimo flusso, che può essere fino a 3 byte più piccolo per raggiungere la dimensione decompressa totale specificata in Regenerated_Size.

Ultimo aggiornamento il