9. Formato dei dati compressi (Compressed Data Format)
9. Formato dei dati compressi (Compressed Data Format)
In questa sezione, descriviamo il formato dell'insieme di dati compressi in termini del formato dei singoli elementi di dati descritti nelle sezioni precedenti.
9.1. Formato dell'intestazione del flusso (Format of the Stream Header)
L'intestazione del flusso (Stream Header) ha solo il seguente campo:
1..7 bit: WBITS, un valore nell'intervallo 10..24, codificato con il
seguente codice a lunghezza variabile (come appare nei dati
compressi, dove i bit sono analizzati da destra a sinistra):
Value Bit Pattern
----- -----------
10 0100001
11 0110001
12 1000001
13 1010001
14 1100001
15 1110001
16 0
17 0000001
18 0011
19 0101
20 0111
21 1001
22 1011
23 1101
24 1111
Si noti che il pattern di bit 0010001 è non valido e non deve
essere utilizzato.
La dimensione della finestra scorrevole (Sliding Window), che è il valore massimo di qualsiasi distanza all'indietro di riferimento non-dizionario (Non-Dictionary Reference Backward Distance), è data dalla seguente formula:
window size = (1 << WBITS) - 16
9.2. Formato dell'intestazione del meta-blocco (Format of the Meta-Block Header)
Un insieme di dati compressi conforme ha almeno un meta-blocco (Meta-Block). Ogni meta-blocco contiene un'intestazione con informazioni sulla lunghezza non compressa del meta-blocco e un bit che segnala se il meta-blocco è l'ultimo. Il formato dell'intestazione del meta-blocco è il seguente:
1 bit: ISLAST, impostato a 1 se questo è l'ultimo meta-blocco
1 bit: ISLASTEMPTY, se impostato a 1, il meta-blocco è vuoto; questo campo
è presente solo se il bit ISLAST è impostato -- se è 1, allora il
meta-blocco e il flusso brotli terminano a quel bit, con i bit
rimanenti nell'ultimo byte del flusso compresso riempiti con zeri
(se i bit di riempimento non sono zero, allora il flusso dovrebbe
essere rifiutato come non valido)
2 bit: MNIBBLES, numero di nibble per rappresentare la lunghezza non
compressa, codificato con il seguente codice a lunghezza fissa:
Value Bit Pattern
----- -----------
0 11
4 00
5 01
6 10
Se MNIBBLES è 0, il meta-blocco è vuoto, cioè non genera alcun dato
non compresso. In questo caso, il resto del meta-blocco ha il
seguente formato:
1 bit: riservato, deve essere zero
2 bit: MSKIPBYTES, numero di byte per rappresentare la lunghezza
dei metadati
MSKIPBYTES * 8 bit: MSKIPLEN - 1, dove MSKIPLEN è il numero di
byte di metadati; questo campo è presente solo se
MSKIPBYTES è positivo; altrimenti, MSKIPLEN è 0 (se
MSKIPBYTES è maggiore di 1 e l'ultimo byte è tutto zeri,
allora il flusso dovrebbe essere rifiutato come non valido)
0..7 bit: bit di riempimento fino al prossimo limite di byte,
devono essere tutti zeri
MSKIPLEN byte di metadati, non parte dei dati non compressi o
della finestra scorrevole
MNIBBLES * 4 bit: MLEN - 1, dove MLEN è la lunghezza dei dati non compressi
del meta-blocco in byte (se MNIBBLES è maggiore di 4 e l'ultimo
nibble è tutto zeri, allora il flusso dovrebbe essere rifiutato come
non valido)
1 bit: ISUNCOMPRESSED, se impostato a 1, qualsiasi bit di dati compressi
fino al prossimo limite di byte viene ignorato, e il resto del
meta-blocco contiene MLEN byte di dati letterali; questo campo è
presente solo se il bit ISLAST non è impostato (se i bit ignorati
non sono tutti zeri, il flusso dovrebbe essere rifiutato come non
valido)
1..11 bit: NBLTYPESL, numero di tipi di blocchi letterali (Literal Block Types),
codificato con il seguente codice a lunghezza variabile (come appare
nei dati compressi, dove i bit sono analizzati da destra a sinistra,
quindi 0110111 ha il valore 12):
Value Bit Pattern
----- -----------
1 0
2 0001
3..4 x0011
5..8 xx0101
9..16 xxx0111
17..32 xxxx1001
33..64 xxxxx1011
65..128 xxxxxx1101
129..256 xxxxxxx1111
Codice prefisso sull'alfabeto del codice di tipo di blocco per i tipi di
blocchi letterali, appare solo se NBLTYPESL >= 2
Codice prefisso sull'alfabeto del codice di conteggio di blocchi per i
conteggi di blocchi letterali, appare solo se NBLTYPESL >= 2
Codice di conteggio di blocchi + bit extra per il primo conteggio di
blocchi letterali, appare solo se NBLTYPESL >= 2
1..11 bit: NBLTYPESI, numero di tipi di blocchi inserimento-copia
(Insert-and-Copy Block Types), codificato con lo stesso codice a
lunghezza variabile di cui sopra
Codice prefisso sull'alfabeto del codice di tipo di blocco per i tipi di
blocchi inserimento-copia, appare solo se NBLTYPESI >= 2
Codice prefisso sull'alfabeto del codice di conteggio di blocchi per i
conteggi di blocchi inserimento-copia, appare solo se NBLTYPESI >= 2
Codice di conteggio di blocchi + bit extra per il primo conteggio di
blocchi inserimento-copia, appare solo se NBLTYPESI >= 2
1..11 bit: NBLTYPESD, numero di tipi di blocchi di distanza
(Distance Block Types), codificato con lo stesso codice a lunghezza
variabile di cui sopra
Codice prefisso sull'alfabeto del codice di tipo di blocco per i tipi di
blocchi di distanza, appare solo se NBLTYPESD >= 2
Codice prefisso sull'alfabeto del codice di conteggio di blocchi per i
conteggi di blocchi di distanza, appare solo se NBLTYPESD >= 2
Codice di conteggio di blocchi + bit extra per il primo conteggio di
blocchi di distanza, appare solo se NBLTYPESD >= 2
2 bit: NPOSTFIX, parametro utilizzato nella codifica di distanza
4 bit: quattro bit più significativi di NDIRECT, per ottenere il valore
effettivo del parametro NDIRECT, spostare a sinistra questo numero di
quattro bit di NPOSTFIX bit
NBLTYPESL * 2 bit: modo di contesto per ogni tipo di blocco letterale
1..11 bit: NTREESL, numero di alberi prefissi letterali, codificato con lo
stesso codice a lunghezza variabile di NBLTYPESL
Mappa di contesto letterale, codificata come descritto nella sezione 7.3,
appare solo se NTREESL >= 2; altrimenti, la mappa di contesto ha solo
valori zero
1..11 bit: NTREESD, numero di alberi prefissi di distanza, codificato con lo
stesso codice a lunghezza variabile di NBLTYPESD
Mappa di contesto di distanza, codificata come descritto nella sezione 7.3,
appare solo se NTREESD >= 2; altrimenti, la mappa di contesto ha solo
valori zero
NTREESL codici prefissi per i letterali
NBLTYPESI codici prefissi per le lunghezze inserimento-copia
NTREESD codici prefissi per le distanze
9.3. Formato dei dati del meta-blocco (Format of the Meta-Block Data)
La parte di dati compressi di un meta-blocco consiste in una serie di comandi (Commands). Ogni comando ha il seguente formato:
Codice di tipo di blocco per il prossimo tipo di blocco inserimento-copia,
appare solo se NBLTYPESI >= 2 e il conteggio di blocchi inserimento-copia
precedente è zero
Codice di conteggio di blocchi + bit extra per il prossimo conteggio di
blocchi inserimento-copia, appare solo se NBLTYPESI >= 2 e il conteggio
di blocchi inserimento-copia precedente è zero
Lunghezza inserimento-copia, codificata come nella sezione 5, utilizzando
il codice prefisso di lunghezza inserimento-copia con l'indice di tipo
di blocco inserimento-copia corrente
Numero di lunghezza di inserimento di letterali, con il seguente formato:
Codice di tipo di blocco per il prossimo tipo di blocco letterale,
appare solo se NBLTYPESL >= 2 e il conteggio di blocchi letterali
precedente è zero
Codice di conteggio di blocchi + bit extra per il prossimo conteggio di
blocchi letterali, appare solo se NBLTYPESL >= 2 e il conteggio di
blocchi letterali precedente è zero
Prossimo byte dei dati non compressi, codificato con il codice prefisso
letterale con l'indice determinato dai due byte precedenti dei dati
non compressi, il tipo di blocco letterale corrente e la mappa di
contesto, come descritto nella sezione 7.3
Codice di tipo di blocco per il prossimo tipo di blocco di distanza, appare
solo se NBLTYPESD >= 2 e il conteggio di blocchi di distanza precedente
è zero
Codice di conteggio di blocchi + bit extra per il prossimo conteggio di
blocchi di distanza, appare solo se NBLTYPESD >= 2 e il conteggio di
blocchi di distanza precedente è zero
Codice di distanza, codificato come nella sezione 4, utilizzando il codice
prefisso di distanza con l'indice determinato dalla lunghezza di copia,
il tipo di blocco di distanza corrente e la mappa di contesto di distanza,
come descritto nella sezione 7.3, appare solo se il codice di distanza
non è uno 0 implicito, come indicato dal codice di lunghezza inserimento-
copia
Il numero di comandi nel meta-blocco è tale che la somma dei byte non compressi prodotti (cioè il numero di letterali inseriti più il numero di byte copiati da dati passati o generati dal dizionario statico) su tutti i comandi fornisce la lunghezza non compressa MLEN codificata nell'intestazione del meta-blocco.
Se il numero totale di byte non compressi prodotti dopo la parte di inserimento dell'ultimo comando è uguale a MLEN, allora la lunghezza di copia dell'ultimo comando viene ignorata e non produrrà alcun output non compresso. In questo caso, la lunghezza di copia dell'ultimo comando può avere qualsiasi valore. In qualsiasi altro caso, se il numero di letterali da inserire, la lunghezza di copia o la lunghezza della parola del dizionario risultante causasse il superamento di MLEN, allora il flusso dovrebbe essere rifiutato come non valido.
Se l'ultimo comando dell'ultimo meta-blocco non vuoto non termina su un limite di byte, i bit inutilizzati nell'ultimo byte devono essere zeri.
Fonte (Source): RFC 7932, Section 9
Testo ufficiale (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt