Passa al contenuto principale

3. Compression Algorithm (Algoritmo di compressione)

Questa sezione descrive l'algoritmo Zstandard.

Lo scopo di questo documento è definire un formato di dati compressi senza perdita (Lossless Compressed Data Format) che a) è indipendente dal tipo di CPU, sistema operativo, file system e set di caratteri, b) è appropriato per la compressione di file e la compressione tramite pipe e stream (Pipe and Streaming Compression) utilizzando l'algoritmo Zstandard. Il testo di questa specifica presuppone che il lettore abbia una conoscenza di base della programmazione a livello di bit e altre rappresentazioni di dati primitive.

I dati possono essere generati o consumati, anche per flussi di dati di input presentati sequenzialmente di lunghezza arbitraria, utilizzando solo una quantità a priori limitata di archiviazione intermedia (A Priori Bounded Amount of Intermediate Storage); pertanto, può essere utilizzato per la comunicazione dati. Il formato utilizza il metodo di compressione Zstandard e il metodo di checksum xxHash-64 opzionale [XXHASH] per rilevare la corruzione dei dati (Data Corruption).

Il formato dati definito in questa specifica non tenta di consentire l'accesso casuale (Random Access) ai dati compressi.

Salvo diversamente indicato di seguito, un compressore conforme (Compliant Compressor) deve generare set di dati conformi alle specifiche stabilite qui. Tuttavia, non è necessario supportare tutte le opzioni.

Un decompressore conforme (Compliant Decompressor) deve essere in grado di decomprimere almeno un set di parametri di lavoro conformi alle specifiche stabilite qui. Può anche ignorare i campi informativi (Informative Fields) come i checksum. Ogni volta che non supporta un parametro definito nel flusso compresso, deve produrre un codice di errore non ambiguo (Unambiguous Error Code) e un messaggio di errore associato che spiega quale parametro non è supportato.

Questa specifica è destinata agli implementatori di software che desiderano comprimere i dati nel formato Zstandard e/o decomprimere i dati dal formato Zstandard. Il formato Zstandard è supportato da un'implementazione di riferimento open source scritta in linguaggio C portabile, disponibile su [ZSTD].

3.1 Frames (Frame)​

I dati compressi Zstandard sono composti da uno o più frame (Frames). Ogni frame è indipendente e può essere decompresso indipendentemente dagli altri frame. Il contenuto decompresso di più frame concatenati è la concatenazione del contenuto decompresso di ciascun frame.

Due formati di frame sono definiti per Zstandard: frame Zstandard e frame saltabili (Skippable Frames). I frame Zstandard contengono dati compressi, mentre i frame saltabili contengono metadati utente personalizzati (Custom User Metadata).

3.1.1 Zstandard Frames (Frame Zstandard)​

La struttura di un singolo frame Zstandard è la seguente:

+--------------------+------------+
|| Magic_Number       | 4 bytes    |
+--------------------+------------+
|| Frame_Header       | 2-14 bytes |
+--------------------+------------+
|| Data_Block         | n bytes    |
+--------------------+------------+
|| [More Data_Blocks] |            |
+--------------------+------------+
|| [Content_Checksum] | 4 bytes    |
+--------------------+------------+

Tabella 1: Struttura di un singolo frame Zstandard

Magic_Number (Numero magico) : 4 byte, formato little-endian. Valore: 0xFD2FB528.

Frame_Header (Intestazione frame) : 2 a 14 byte, vedere sezione 3.1.1.1.

Data_Block (Blocco dati) : Vedere sezione 3.1.1.2. Qui appaiono i dati.

Content_Checksum (Checksum contenuto) : Checksum a 32 bit facoltativo, presente solo se Content_Checksum_Flag è impostato. Il checksum del contenuto è il risultato della funzione hash XXH64() [XXHASH] con i dati originali (decodificati) come input e seed zero. I 4 byte inferiori del checksum sono memorizzati in formato little-endian.

La scelta del numero magico è progettata per ridurre la probabilità di trovarlo all'inizio di un file arbitrario. Evita pattern banali (0x00, 0xFF, byte ripetuti, byte incrementanti, ecc.), contiene valori di byte al di fuori dell'intervallo ASCII e non si mappa nello spazio UTF-8, tutto questo riducendo la probabilità che appaia in cima a un file di testo.

3.1.1.1 Frame Header (Intestazione frame)​

La dimensione dell'intestazione del frame è variabile, minimo 2 byte e massimo 14 byte, a seconda dei parametri facoltativi. La struttura di Frame_Header è la seguente:

+-------------------------+-----------+
|| Frame_Header_Descriptor | 1 byte    |
+-------------------------+-----------+
|| [Window_Descriptor]     | 0-1 byte  |
+-------------------------+-----------+
|| [Dictionary_ID]         | 0-4 bytes |
+-------------------------+-----------+
|| [Frame_Content_Size]    | 0-8 bytes |
+-------------------------+-----------+

Tabella 2: Struttura di Frame_Header

(Poiché il contenuto della sezione 3.1.1.1 e delle sue sottosezioni è troppo lungo, consultare il documento RFC 8878 completo per descrizioni dettagliate dei campi bit, Window Descriptor, Dictionary_ID, Frame_Content_Size e altri dettagli tecnici)

Nota: La sezione 3 contiene molti dettagli tecnici, tra cui:

  • 3.1.1.2 Blocks (Struttura blocchi)
  • 3.1.1.3 Compressed Blocks (Blocchi compressi, contiene Literals e Sequences)
  • 3.1.1.4 Sequence Execution (Esecuzione sequenza)
  • 3.1.1.5 Repeat Offsets (Offset ripetuti)
  • 3.1.2 Skippable Frames (Frame saltabili)

Per i dettagli completi dell'implementazione tecnica, consultare il testo originale RFC 8878: https://www.rfc-editor.org/rfc/rfc8878.txt

Ultimo aggiornamento il