3.1.1.3.2. Sequences_Section (Sezione sequenze)
Un blocco compresso è un continuum di sequenze. Una sequenza è un comando di copia letterale, seguito da un comando di copia di corrispondenza. Il comando di copia letterale specifica una lunghezza. È il numero di byte da copiare (o estrarre) dalla Literals_Section. Il comando di copia di corrispondenza specifica un offset e una lunghezza.
Quando tutte le sequenze sono state decodificate e ci sono ancora letterali rimasti nella Literals_Section, questi byte vengono aggiunti alla fine del blocco.
Questo è descritto più in dettaglio nella sezione 3.1.1.4.
La Sequences_Section raggruppa tutti i simboli necessari per decodificare i comandi. Ci sono tre tipi di simboli: codici lunghezza letterale, codici offset e codici lunghezza corrispondenza. Sono codificati in modo interlacciato in un singolo "flusso di bit".
La Sequences_Section inizia con un'intestazione, seguita da tabelle di probabilità facoltative per ogni tipo di simbolo, quindi dal flusso di bit.
Sequences_Section_Header
[Literals_Length_Table]
[Offset_Table]
[Match_Length_Table]
bitStream
Per decodificare la Sequences_Section, la sua dimensione deve essere conosciuta. Questa dimensione è derivata dalla dimensione della Literals_Section:
Sequences_Section_Size = Block_Size - Literals_Section_Header
- Literals_Section_Content
3.1.1.3.2.1. Sequences_Section_Header (Intestazione sezione sequenze)
Questa intestazione è composta da due elementi:
- Number_of_Sequences (Numero di sequenze)
- Symbol_Compression_Modes (Modi di compressione simboli)
Number_of_Sequences
Number_of_Sequences è un campo di dimensione variabile che utilizza da 1 a 3 byte. Se il primo byte è "byte0":
-
if (byte0 == 0): Nessuna sequenza. La parte sequenza si ferma qui. Il contenuto decompresso è interamente definito come il contenuto di Literals_Section. Le tabelle FSE utilizzate in Repeat_Mode non vengono aggiornate.
-
if (byte0 < 128): Number_of_Sequences = byte0. Utilizza 1 byte.
-
if (byte0 < 255): Number_of_Sequences =
((byte0 - 128) << 8) + byte1. Utilizza 2 byte. -
if (byte0 == 255): Number_of_Sequences =
byte1 + (byte2 << 8) + 0x7F00. Utilizza 3 byte.
Symbol_Compression_Modes
Symbol_Compression_Modes è un singolo byte che definisce il modo di compressione per ogni tipo di simbolo.
| Numero di bit (Bit Number) | Nome del campo (Field Name) |
|---|---|
| 7-6 | Literal_Lengths_Mode |
| 5-4 | Offsets_Mode |
| 3-2 | Match_Lengths_Mode |
| 1-0 | Reserved (Riservato) |
Tabella 14: Symbol_Compression_Modes
L'ultimo campo Reserved deve essere tutto zero.
Literals_Lengths_Mode, Offsets_Mode e Match_Lengths_Mode definiscono rispettivamente il Compression_Mode per i codici lunghezza letterale, i codici offset e i codici lunghezza corrispondenza. Seguono la stessa enumerazione:
| Value (Valore) | Compression_Mode (Modo di compressione) |
|---|---|
| 0 | Predefined_Mode (Modo predefinito) |
| 1 | RLE_Mode (Modo RLE) |
| 2 | FSE_Compressed_Mode (Modo compresso FSE) |
| 3 | Repeat_Mode (Modo ripetizione) |
Tabella 15: Literals_Lengths_Mode, Offsets_Mode e Match_Lengths_Mode
Predefined_Mode (Modo predefinito) : Utilizza la tabella di distribuzione FSE predefinita (vedere sezione 4.1), come definito nella sezione 3.1.1.3.2.2. Non sarà presente alcuna tabella di distribuzione.
RLE_Mode (Modo RLE) : La descrizione della tabella consiste in un byte che contiene il valore del simbolo. Questo simbolo sarà utilizzato per tutte le sequenze.
FSE_Compressed_Mode (Modo compresso FSE) : Compressione FSE standard. Sarà presente una tabella di distribuzione. Il formato di questa tabella di distribuzione è descritto nella sezione 4.1.1. Si noti che la precisione massima consentita per le tabelle dei codici lunghezza letterale e dei codici lunghezza corrispondenza è 9, e la precisione massima per la tabella dei codici offset è 8. Quando è presente un solo simbolo, questo modo non deve essere utilizzato; dovrebbe essere utilizzato invece RLE_Mode (sebbene qualsiasi altro modo funzioni anche).
Repeat_Mode (Modo ripetizione) : La tabella utilizzata nel Compressed_Block precedente con Number_Of_Sequences > 0 sarà riutilizzata, o se questo è il primo blocco, la tabella dal dizionario. Si noti che questo include RLE_Mode, quindi se Repeat_Mode segue RLE_Mode, lo stesso simbolo sarà ripetuto. Include anche Predefined_Mode, nel qual caso Repeat_Mode avrà lo stesso risultato di Predefined_Mode. Non sarà presente alcuna tabella di distribuzione. Se questo modo viene utilizzato senza che ci sia una tabella di sequenza precedente da ripetere nel frame (o dizionario; vedere sezione 5), questo dovrebbe essere considerato come corruzione.
3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets (Codici sequenza per lunghezze e offset)
Ogni simbolo è un codice nel proprio contesto, specificando Baseline (linea di base) e Number_of_Bits (numero di bit) da aggiungere. I codici sono compressi FSE e interlacciati nello stesso flusso di bit con i bit aggiuntivi originali.
Literals Length Codes (Codici lunghezza letterale)
I codici lunghezza letterale sono valori da 0 a 35 (incluso). Definiscono lunghezze da 0 a 131071 byte. La lunghezza letterale è uguale alla Baseline decodificata più il risultato della lettura di Number_of_Bits bit dal flusso di bit (come valore 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 |
Tabella 16: Codici lunghezza letterale
Match Length Codes (Codici lunghezza corrispondenza)
I codici lunghezza corrispondenza sono valori da 0 a 52 (incluso). Definiscono lunghezze da 3 a 131074 byte. La lunghezza corrispondenza è uguale alla Baseline decodificata più il risultato della lettura di Number_of_Bits bit dal flusso di bit (come valore 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 |
Tabella 17: Codici lunghezza corrispondenza
Offset Codes (Codici offset)
I codici offset sono valori da 0 a N.
Il decodificatore può liberamente limitare il suo N massimo supportato. Si raccomanda di supportare almeno un valore di 22. Al momento della scrittura, il valore N massimo supportato dal decodificatore di riferimento è 31.
Il codice offset è anche il numero di bit aggiuntivi letti in little-endian, può essere convertito in Offset_Value con la seguente formula:
Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) Offset = Offset_Value - 3;
Ciò significa che l'Offset_Value massimo è (2^(N+1)) - 1, supportando distanze di riferimento all'indietro fino a (2^(N+1)) - 4, ma limitato dalla distanza di riferimento all'indietro massima (vedere sezione 3.1.1.1.2).
Gli Offset_Values da 1 a 3 sono speciali: definiscono "codici di ripetizione". Questo è descritto più in dettaglio nella sezione 3.1.1.5.
3.1.1.3.2.2. Default Distributions (Distribuzioni predefinite)
Se Predefined_Mode è selezionato per un tipo di simbolo, la sua tabella di decodifica FSE viene generata dalla tabella di distribuzione predefinita definita qui. Per dettagli su come convertire questa distribuzione in una tabella di decodifica, vedere la sezione 4.1.
3.1.1.3.2.2.1. Literals Length Codes (Codici lunghezza letterale)
La tabella di decodifica utilizza un log di precisione di 6 bit (64 stati).
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 (Codici lunghezza corrispondenza)
La tabella di decodifica utilizza un log di precisione di 6 bit (64 stati).
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 (Codici offset)
La tabella di decodifica utilizza un log di precisione di 5 bit (32 stati) e supporta un valore N massimo di 28, consentendo valori offset fino a 536.870.908.
Se una sequenza nel blocco compresso richiede un offset maggiore di questo, non può essere rappresentata con la distribuzione predefinita.
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
};