1. Introduzione (Introduction)

1.1. Scopo (Purpose)

Lo scopo di questa specifica è definire un formato di dati compressi senza perdita (Lossless Compressed Data Format) che:

sia indipendente dal tipo di CPU, sistema operativo, file system e set di caratteri; pertanto, può essere utilizzato per lo scambio di dati.
possa essere prodotto o consumato, anche per un flusso di dati di input arbitrariamente lungo presentato in modo sequenziale, utilizzando solo una quantità di archiviazione intermedia limitata a priori; pertanto, può essere utilizzato nelle comunicazioni dati o strutture simili, come i filtri Unix.
comprima i dati con un rapporto di compressione (Compression Ratio) paragonabile ai migliori metodi di compressione generica attualmente disponibili, in particolare, notevolmente migliore del programma gzip.
decomprima molto più velocemente delle attuali implementazioni LZMA.

Il formato dati definito da questa specifica non tenta di:

consentire l'accesso casuale ai dati compressi.
comprimere dati specializzati (ad esempio, grafica raster) in modo denso come i migliori algoritmi specializzati attualmente disponibili.

Questo documento è la specifica autorevole del formato dati compressi brotli. Definisce l'insieme di flussi di dati compressi brotli validi e un algoritmo di decodifica (Decoder Algorithm) che produce il flusso di dati non compressi da un flusso di dati compressi brotli valido.

1.2. Pubblico di destinazione (Intended Audience)

Questa specifica è destinata agli sviluppatori di software per comprimere dati nel formato brotli e/o decomprimere dati dal formato brotli.

Il testo della specifica presuppone una conoscenza di base della programmazione a livello di bit e altre rappresentazioni di dati primitivi. La familiarità con la tecnica della codifica di Huffman (Huffman Coding) è utile ma non richiesta.

Questa specifica utilizza (ampiamente) le notazioni e la terminologia introdotte nella specifica del formato DEFLATE [RFC1951]. Per completezza, includiamo sempre il testo completo delle parti pertinenti della RFC 1951; pertanto, la familiarità con il formato DEFLATE è utile ma non richiesta.

Il formato dati compressi definito in questa specifica è parte integrante del formato di file WOFF 2.0 [WOFF2]; pertanto, questa specifica è destinata anche agli implementatori di compressori e decompressori WOFF 2.0.

1.3. Ambito (Scope)

Questo documento specifica un metodo per rappresentare una sequenza di byte (Sequence of Bytes) come una sequenza di bit (Sequence of Bits) (solitamente più corta) e un metodo per impacchettare quest'ultima sequenza di bit in byte.

1.4. Conformità (Compliance)

Salvo diversa indicazione di seguito, un decompressore conforme (Compliant Decompressor) deve essere in grado di accettare e decomprimere qualsiasi set di dati conforme a tutte le specifiche qui presentate. Un compressore conforme (Compliant Compressor) deve produrre set di dati conformi a tutte le specifiche qui presentate.

1.5. Definizioni di termini e convenzioni utilizzate (Definitions of Terms and Conventions Used)

Byte: 8 bit memorizzati o trasmessi come unità (uguale a un ottetto). Per questa specifica, un byte è esattamente 8 bit, anche su macchine che memorizzano un carattere su un numero di bit diverso da otto. Vedere di seguito per la numerazione dei bit all'interno di un byte.

Stringa (String): una sequenza di byte arbitrari.

I byte memorizzati in un computer non hanno un "ordine dei bit", poiché sono sempre trattati come unità. Tuttavia, un byte considerato come un intero tra 0 e 255 ha un bit più significativo (msb) e meno significativo (lsb), e poiché scriviamo i numeri con la cifra più significativa a sinistra, scriviamo anche i byte con il bit più significativo a sinistra. Nei diagrammi seguenti, numeriamo i bit di un byte in modo che il bit 0 sia il bit meno significativo, cioè i bit sono numerati:

+--------+
|76543210|
+--------+

All'interno di un computer, un numero può occupare più byte. Tutti i numeri multi-byte nel formato qui descritto sono memorizzati con il byte meno significativo (Least-Significant Byte) per primo (all'indirizzo di memoria inferiore). Ad esempio, il numero decimale 520 è memorizzato come:

    0        1
+--------+--------+
|00001000|00000010|
+--------+--------+
 ^        ^
 |        |
 |        + more significant byte = 2 x 256
 + less significant byte = 8

1.5.1. Impacchettamento in byte (Packing into Bytes)

Questo documento non affronta la questione dell'ordine in cui i bit di un byte vengono trasmessi su un mezzo bit-sequenziale, poiché il formato dati finale qui descritto è orientato ai byte piuttosto che ai bit. Tuttavia, descriviamo il formato di blocco compresso (Compressed Block Format) di seguito come una sequenza di elementi di dati di varie lunghezze di bit, non una sequenza di byte. Dobbiamo quindi specificare come impacchettare questi elementi di dati in byte per formare la sequenza finale di byte compressi:

Gli elementi di dati vengono impacchettati in byte in ordine di numero di bit crescente all'interno del byte, cioè iniziando con il bit meno significativo del byte.
Gli elementi di dati diversi dai codici di Huffman (Huffman Code) vengono impacchettati iniziando con il bit meno significativo dell'elemento di dati.
I codici di Huffman vengono impacchettati iniziando con il bit più significativo del codice.

In altre parole, se si dovesse stampare i dati compressi come una sequenza di byte, iniziando con il primo byte sul margine destro e procedendo verso sinistra, con il bit più significativo di ogni byte a sinistra come al solito, si potrebbe analizzare il risultato da destra a sinistra, con elementi a larghezza fissa nell'ordine MSB-LSB corretto e codici di Huffman in ordine di bit invertito (cioè con il primo bit del codice nella posizione LSB relativa).

Come esempio, consideriamo l'impacchettamento dei seguenti elementi di dati in una sequenza di 3 byte:

Valore a 2 bit 1 (binario 01)
Valore a 3 bit 2 (binario 010)
Valore a 5 bit 6 (binario 00110)
Codice a 4 bit con schema di bit 1011 (con il primo bit che è 1, il secondo bit che è 0, il terzo bit che è 1 e il quarto bit che è 1)
Valore a 2 bit 0 (binario 00)
Codice a 4 bit con schema di bit 0011
Valore a 5 bit 31 (binario 11111)

Il seguente diagramma mostra come vengono impacchettati questi elementi:

       Byte 0           Byte 1           Byte 2
   +---------------+----------------+----------------+
   |0|1|1|0|0|0|1|0|1|1|0|1|1|0|0|0|0|1|1|1|1|1|1|1|
   +---------------+----------------+----------------+
    ^ ^ ^   ^     ^ ^     ^       ^   ^             ^
    | | |   |     | |     |       |   |             |
    | | |   |     | |     |       |   +-------------|---+ 5-bit value 31
    | | |   |     | |     |       +-----------------|---|-+ 4-bit code 0011
    | | |   |     | |     +-----------------------+     |
    | | |   |     | |                             |     | 2-bit value 0
    | | |   |     | +-----------------------------+-----+ 4-bit code 1011
    | | |   +---+ 5-bit value 6
    | | +-----+ 3-bit value 2
    | +---+ 2-bit value 1

Fonte (Source): RFC 7932, Section 1
Testo ufficiale (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt