Passa al contenuto principale

RFC 8878 - Compressione Zstandard e tipo di media 'application/zstd'

  • Stato: Informational
  • Pubblicato: February 2021
  • Stream: IETF
  • Sostituisce: RFC8478
  • Errata: Nessun errata

Sommario (Abstract)​

Zstandard, o "zstd" (pronunciato "zee standard"), è un meccanismo di compressione dati senza perdita (Lossless Data Compression Mechanism). Questo documento descrive tale meccanismo e registra il tipo di media (Media Type), la codifica del contenuto (Content Encoding) e il suffisso di sintassi strutturata (Structured Syntax Suffix) utilizzati durante la trasmissione di contenuto compresso zstd tramite MIME.

Sebbene il nome Zstandard contenga la parola "standard", i lettori devono notare che questo documento non è una specifica Internet Standards Track; è pubblicato solo a scopo informativo.

Questo documento sostituisce e rende obsoleto RFC 8478.

Indice (Contents)​

Sezioni principali​

Sezioni di standardizzazione​

Appendici (Appendices)​

Riferimenti​

Caratteristiche tecniche principali​

🔬 Algoritmi principali​

FSE (Entropia a stati finiti)

  • Codificatore entropico basato su ANS
  • Codifica/decodifica guidata da macchina a stati
  • Tabella di distribuzione di probabilità ottimizzata

Codifica Huffman

  • Costruzione di codice prefisso
  • Conversione da peso a parola di codice
  • Lettura di flusso di bit inversa

📊 Caratteristiche di prestazione​

Intervallo livello di compressione: -5 a 22
Livello predefinito: 3 (velocità e compressione bilanciate)
Velocità di compressione: 100-500 MB/s (livelli 1-3)
Velocità di decompressione: 1000-1500 MB/s
Dimensione massima della finestra: 128 MB

🎯 Scenari di applicazione​

  • Compressione contenuti Web: Risposte HTTP, risorse statiche
  • File system: Compressione trasparente Btrfs, ZFS
  • Database: Kafka, MySQL, Clickhouse
  • Trasmissione di rete: HTTP/2, gRPC, WebSocket

Risorse correlate​

Stato del documento​

Versione traduzione: Italiano
Stato traduzione: 🔄 In corso
Ultimo aggiornamento: 2024-12-25
Revisione tecnica: In attesa

1. Introduction (Introduzione)​

Zstandard, o "zstd" (pronunciato "zee standard"), è un meccanismo di compressione dati (Data Compression Mechanism), simile a gzip [RFC1952].

Nonostante l'uso della parola "standard" come parte del suo nome, i lettori sono avvisati che questo documento non è una specifica dell'Internet Standards Track; viene pubblicato solo a scopo informativo.

Questo documento descrive il formato Zstandard. Inoltre, per consentire il trasporto di un oggetto dati compresso con Zstandard, questo documento registra un tipo di media (Media Type), una codifica del contenuto (Content Encoding) e un suffisso di sintassi strutturata (Structured Syntax Suffix) che possono essere utilizzati per identificare tale contenuto quando viene utilizzato in un payload.

2. Definitions (Definizioni)​

Alcuni termini utilizzati altrove in questo documento sono definiti qui per chiarezza.

uncompressed (non compresso) : Descrive un insieme arbitrario di byte nella loro forma originale, prima di essere sottoposti a compressione.

compressed (compresso) : Descrive il risultato del passaggio di un insieme di byte attraverso questo meccanismo. L'input originale è stato quindi compresso.

decompressed (decompresso) : Descrive il risultato del passaggio di un insieme di byte attraverso l'inverso di questo meccanismo. Quando questo ha successo, il payload decompresso (Decompressed Payload) e il payload non compresso (Uncompressed Payload) sono indistinguibili.

encode (codificare) : Il processo di traduzione dei dati da una forma all'altra; questo può includere la compressione, o può riferirsi ad altre traduzioni effettuate come parte di questa specifica.

decode (decodificare) : L'inverso di "encode"; descrive un processo di inversione di una codifica precedente per recuperare il contenuto originale.

frame (frame) : Il contenuto compresso da Zstandard viene trasformato in un frame Zstandard. Più frame possono essere aggiunti a un singolo file o stream. Un frame è completamente indipendente, ha un inizio e una fine definiti e ha un insieme di parametri che indica al decoder come decomprimerlo.

block (blocco) : Un frame incapsula uno o più blocchi. Ogni blocco contiene contenuto arbitrario, che è descritto dal suo header, e ha una dimensione massima del contenuto garantita che dipende dai parametri del frame. A differenza dei frame, ogni blocco dipende dai blocchi precedenti per una corretta decodifica. Tuttavia, ogni blocco può essere decompresso senza attendere il suo successore, consentendo operazioni di streaming (Streaming Operations).

natural order (ordine naturale) : Una sequenza o ordinamento di oggetti o valori tipico di quel tipo di oggetto o valore. Un insieme di interi univoci, ad esempio, è in "ordine naturale" se, quando si procede da un elemento nell'insieme o nella sequenza al successivo, non c'è mai una diminuzione di valore.

La convenzione di denominazione per gli identificatori all'interno della specifica è Mixed_Case_With_Underscores (maiuscole miste con trattini bassi). Gli identificatori tra parentesi quadre indicano che l'identificatore è opzionale nel contesto presentato.

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

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

3.1.1.1.1. Frame_Header_Descriptor (Descrittore intestazione frame)​

Il primo byte dell'intestazione è chiamato Frame_Header_Descriptor. Descrive quali altri campi sono presenti. La decodifica di questo byte è sufficiente per determinare la dimensione di Frame_Header.

Numero di bit (Bit Number)Nome del campo (Field Name)
7-6Frame_Content_Size_Flag
5Single_Segment_Flag
4(inutilizzato, unused)
3(riservato, reserved)
2Content_Checksum_Flag
1-0Dictionary_ID_Flag

Tabella 3: Frame_Header_Descriptor

Nella tabella 3, il bit 7 è il bit più significativo e il bit 0 è il bit meno significativo.

3.1.1.1.1.1. Frame_Content_Size_Flag (Flag dimensione contenuto frame)​

Si tratta di un flag a 2 bit (equivalente a Frame_Header_Descriptor spostato di 6 bit a destra), che specifica se Frame_Content_Size (dimensione dati decompressi) è fornito nell'intestazione. Frame_Content_Size_Flag fornisce FCS_Field_Size, il numero di byte utilizzati da Frame_Content_Size secondo la tabella 4:

Frame_Content_Size_Flag0123
FCS_Field_Size0 o 1248

Tabella 4: Frame_Content_Size_Flag fornisce FCS_Field_Size

Quando Frame_Content_Size_Flag è 0, FCS_Field_Size dipende da Single_Segment_Flag: se Single_Segment_Flag è impostato, allora FCS_Field_Size è 1. Altrimenti, FCS_Field_Size è 0; Frame_Content_Size non è fornito.

3.1.1.1.1.2. Single_Segment_Flag (Flag segmento singolo)​

Se questo flag è impostato, i dati devono essere rigenerati in un singolo segmento di memoria contiguo.

In questo caso, il byte Window_Descriptor viene saltato, ma Frame_Content_Size deve essere presente. Pertanto, il decodificatore deve allocare un segmento di memoria di dimensione uguale o superiore a Frame_Content_Size.

Per proteggere il decodificatore da richieste di memoria irragionevoli, è consentito al decodificatore rifiutare frame compressi che richiedono dimensioni di memoria superiori all'intervallo autorizzato del decodificatore.

Per una compatibilità più ampia, si raccomanda che i decodificatori supportino almeno una dimensione di memoria di 8 MB. Questa è solo una raccomandazione; ogni decodificatore può liberamente supportare limiti superiori o inferiori in base ai vincoli locali.

3.1.1.1.1.3. Unused Bit (Bit inutilizzato)​

Un decodificatore conforme a questa versione della specifica non deve interpretare questo bit. Può essere utilizzato nelle versioni future per rappresentare attributi che non sono essenziali per decodificare correttamente il frame. Un codificatore conforme a questa specifica deve impostare questo bit a zero.

3.1.1.1.1.4. Reserved Bit (Bit riservato)​

Questo bit è riservato per future funzionalità. Il suo valore deve essere zero. Un decodificatore conforme a questa versione della specifica deve assicurarsi che non sia impostato. Questo bit può essere utilizzato nelle revisioni future per rappresentare funzionalità che devono essere interpretate per decodificare correttamente il frame.

3.1.1.1.1.5. Content_Checksum_Flag (Flag checksum contenuto)​

Se questo flag è impostato, una Content_Checksum a 32 bit sarà presente alla fine del frame. Vedere la descrizione di Content_Checksum sopra.

3.1.1.1.1.6. Dictionary_ID_Flag (Flag ID dizionario)​

Si tratta di un flag a 2 bit (= Frame_Header_Descriptor & 0x3), che indica se un ID dizionario è fornito nell'intestazione. Specifica anche la dimensione di questo campo come DID_Field_Size:

Dictionary_ID_Flag0123
DID_Field_Size0124

Tabella 5: Dictionary_ID_Flag

3.1.1.1.2. Window Descriptor (Descrittore finestra)​

Questo fornisce una garanzia sul buffer di memoria minimo richiesto per decomprimere il frame. Questa informazione è importante affinché il decodificatore allochi memoria sufficiente.

Il byte Window_Descriptor è facoltativo. Quando Single_Segment_Flag è impostato, Window_Descriptor non è presente. In questo caso, Window_Size è uguale a Frame_Content_Size, e il suo valore può variare da 0 a 2^64 - 1 byte (16 ExaByte).

Numero di bit (Bit Number)7-32-0
Nome del campo (Field Name)Exponent (Esponente)Mantissa

Tabella 6: Window_Descriptor

La dimensione minima del buffer di memoria è chiamata Window_Size. È descritta dalla seguente formula:

windowLog = 10 + Exponent;
windowBase = 1 << windowLog;
windowAdd = (windowBase / 8) * Mantissa;
Window_Size = windowBase + windowAdd;

La Window_Size minima è 1 KB. La Window_Size massima è (1<<41) + 7*(1<<38) byte, ovvero 3,75 TB.

In generale, valori di Window_Size più grandi tendono a migliorare il rapporto di compressione, a scapito di un maggiore utilizzo della memoria.

Per decodificare correttamente i dati compressi, il decodificatore deve allocare un buffer di almeno Window_Size byte.

Per proteggere il decodificatore da richieste di memoria irragionevoli, è consentito al decodificatore rifiutare frame compressi che richiedono dimensioni di memoria superiori all'intervallo autorizzato del decodificatore.

Per migliorare l'interoperabilità, si raccomanda che i decodificatori supportino valori di Window_Size fino a 8 MB e che i codificatori non generino frame che richiedono una Window_Size superiore a 8 MB. Questa è solo una raccomandazione, e i decodificatori possono liberamente supportare limiti superiori o inferiori in base ai vincoli locali.

3.1.1.1.3. Dictionary_ID (ID dizionario)​

Questo è un campo di dimensione variabile che contiene l'ID dizionario richiesto per decodificare correttamente il frame. Questo campo è facoltativo. Se non è presente, spetta al decodificatore decidere quale dizionario utilizzare.

La dimensione del campo Dictionary_ID è fornita da DID_Field_Size. DID_Field_Size è derivato direttamente dal valore di Dictionary_ID_Flag. Un byte può rappresentare ID 0-255; 2 byte possono rappresentare ID 0-65535; 4 byte possono rappresentare ID 0-4294967295. Il formato è little-endian.

È consentito utilizzare un grande ID dizionario a 4 byte per rappresentare un piccolo ID (ad esempio, 13), anche se questo è inefficiente.

In ambienti privati, può essere utilizzato qualsiasi ID dizionario. Tuttavia, per frame e dizionari distribuiti nello spazio pubblico, Dictionary_ID deve essere assegnato con attenzione. I seguenti intervalli sono riservati solo ai dizionari registrati presso IANA (vedere sezione 7.4):

  • Intervallo basso (low range): <= 32767
  • Intervallo alto (high range): >= (1 << 31)

Qualsiasi altro valore di Dictionary_ID può essere utilizzato tramite accordo privato tra partecipanti.

Qualsiasi payload inviato per la decompressione che fa riferimento a un ID dizionario riservato non registrato comporterà un errore.

3.1.1.1.4. Frame_Content_Size (Dimensione contenuto frame)​

Questa è la dimensione originale (non compressa). Questa informazione è facoltativa. Frame_Content_Size utilizza un numero variabile di byte, fornito da FCS_Field_Size. FCS_Field_Size è fornito dal valore di Frame_Content_Size_Flag. FCS_Field_Size può essere uguale a 0 (non presente), 1, 2, 4 o 8 byte.

FCS Field Size (Dimensione campo)Range (Intervallo)
0unknown (sconosciuto)
10 - 255
2256 - 65791
40 - 2^32 - 1
80 - 2^64 - 1

Tabella 7: Frame_Content_Size

Il formato Frame_Content_Size è little-endian. Quando FCS_Field_Size è 1, 4 o 8 byte, il valore viene letto direttamente. Quando FCS_Field_Size è 2, viene aggiunto un offset di 256. È consentito utilizzare qualsiasi variante compatibile per rappresentare una piccola dimensione (ad esempio, 18), anche se questo è inefficiente.

3.1.1.2. Blocks (Blocchi)​

Dopo Magic_Number e Frame_Header, ci sono diversi blocchi. Ogni frame deve avere almeno 1 blocco, ma non c'è un limite superiore al numero di blocchi per frame.

La struttura di un blocco è la seguente:

+==============+===============+
|| Block_Header | Block_Content |
+==============+===============+
||   3 bytes    |    n bytes    |
+--------------+---------------+

Tabella 8: Struttura di un blocco

Block_Header utilizza 3 byte, scritti utilizzando la convenzione little-endian. Contiene tre campi:

Last_BlockBlock_TypeBlock_Size
bit 0bits 1-2bits 3-23

Tabella 9: Block_Header

3.1.1.2.1. Last_Block (Ultimo blocco)​

Il bit meno significativo (Last_Block) indica se questo è l'ultimo blocco. Il frame terminerà dopo questo ultimo blocco. Può essere seguito da una Content_Checksum opzionale (vedere sezione 3.1.1).

3.1.1.2.2. Block_Type (Tipo di blocco)​

I successivi 2 bit rappresentano il Block_Type. Ci sono quattro tipi di blocchi:

Value (Valore)Block_Type (Tipo di blocco)
0Raw_Block (Blocco grezzo)
1RLE_Block (Blocco RLE)
2Compressed_Block (Blocco compresso)
3Reserved (Riservato)

Tabella 10: Quattro tipi di blocchi

Raw_Block (Blocco grezzo) : Si tratta di un blocco non compresso. Block_Content contiene Block_Size byte.

RLE_Block (Blocco RLE) : Si tratta di un singolo byte, ripetuto Block_Size volte. Block_Content è composto da un singolo byte. Sul lato della decompressione, questo byte deve essere ripetuto Block_Size volte.

Compressed_Block (Blocco compresso) : Si tratta del blocco compresso descritto nella sezione 3.1.1.3. Block_Size è la lunghezza di Block_Content, ovvero i dati compressi. La dimensione decompressa è sconosciuta, ma il suo valore massimo possibile è garantito (vedere di seguito).

Reserved (Riservato) : Questo non è un blocco. Questo valore non può essere utilizzato con la specifica attuale. Se tale valore è presente, viene considerato come dati corrotti, e un decodificatore conforme alla specifica deve rifiutarlo.

3.1.1.2.3. Block_Size (Dimensione blocco)​

I 21 bit superiori del Block_Header rappresentano la Block_Size.

Quando Block_Type è Compressed_Block o Raw_Block, Block_Size è la dimensione di Block_Content (quindi non include il Block_Header).

Quando Block_Type è RLE_Block, poiché la dimensione di Block_Content è sempre 1, Block_Size rappresenta il numero di volte che questo byte deve essere ripetuto.

Block_Size è limitato da Block_Maximum_Size (vedere di seguito).

3.1.1.2.4. Block_Content and Block_Maximum_Size (Contenuto blocco e dimensione massima blocco)​

La dimensione di Block_Content è limitata da Block_Maximum_Size, che è il minore dei due seguenti:

  • Window_Size
  • 128 KB

Block_Maximum_Size è costante per un dato frame. Questo massimo si applica sia alla dimensione decompressa che alla dimensione compressa di qualsiasi blocco nel frame.

La motivazione per questa limitazione è che il decodificatore può leggere queste informazioni all'inizio del frame e utilizzarle per allocare buffer. La garanzia della dimensione del blocco assicura che il buffer sia sufficiente per tutti i blocchi successivi di un frame valido.

Se un blocco compresso è più grande di un blocco non compresso, si raccomanda di inviare invece un blocco non compresso (ovvero Raw_Block).

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.

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-6Literal_Lengths_Mode
5-4Offsets_Mode
3-2Match_Lengths_Mode
1-0Reserved (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)
0Predefined_Mode (Modo predefinito)
1RLE_Mode (Modo RLE)
2FSE_Compressed_Mode (Modo compresso FSE)
3Repeat_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_CodeBaselineNumber_of_Bits
0-15length0
16161
17181
18201
19221
20242
21282
22323
23403
24484
25646
261287
272568
285129
29102410
30204811
31409612
32819213
331638414
343276815
356553616

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_CodeBaselineNumber_of_Bits
0-31Match_Length_Code + 30
32351
33371
34391
35411
36432
37472
38513
39593
40674
41834
42995
431317
442598
455159
46102710
47205111
48409912
49819513
501638714
513277115
526553916

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
  };

3.1.1.4. Sequence Execution (Esecuzione sequenza)​

Una volta decodificati sia i letterali che le sequenze, vengono combinati per generare il contenuto decodificato del blocco.

Ogni sequenza è composta da una tupla (literals_length, offset_value, match_length), decodificata come descritto in Sequences_Section (sezione 3.1.1.3.2). Per eseguire una sequenza, copiare prima literals_length byte dai letterali decodificati all'output.

Quindi, copiare match_length byte da dati precedentemente decodificati. L'offset da cui copiare è determinato da offset_value:

  • if Offset_Value > 3: allora l'offset è Offset_Value - 3;

  • if Offset_Value is from 1-3: l'offset è un valore di offset ripetuto speciale. Vedere la sezione 3.1.1.5 per informazioni su come determinare l'offset in questo caso.

L'offset è definito dalla posizione corrente (dopo aver copiato i letterali), quindi un offset di 6 e una lunghezza di corrispondenza di 3 significa che 3 byte devono essere copiati da 6 byte prima. Si noti che tutti gli offset che portano a dati precedentemente decodificati devono essere inferiori a Window_Size, definito in Frame_Header_Descriptor (sezione 3.1.1.1.1).

Esempio di flusso di esecuzione​

Esempio 1: Esecuzione sequenza base​

Supponiamo che la sequenza sia (literals_length=5, offset_value=10, match_length=4):

  1. Copiare letterali: Copia 5 byte dalla sezione letterali all'output
  2. Calcolare offset: Offset_Value=10 > 3, quindi Offset = 10 - 3 = 7
  3. Copiare corrispondenza: Copia 4 byte da 7 byte prima della posizione output

Esempio 2: Utilizzo di un offset ripetuto​

Supponiamo che la sequenza sia (literals_length=3, offset_value=1, match_length=8):

  1. Copiare letterali: Copia 3 byte dalla sezione letterali all'output
  2. Utilizzare offset ripetuto: offset_value=1 significa utilizzare Repeated_Offset1
  3. Copiare corrispondenza: Copia 8 byte dalla posizione Repeated_Offset1

Vincoli importanti​

  1. Limitazione Window_Size: Tutti gli offset devono essere < Window_Size
  2. Integrità dati: Assicurarsi che gli offset non superino l'intervallo dei dati decodificati
  3. Esaurimento letterali: Dopo l'esecuzione di tutte le sequenze, i letterali rimanenti vengono aggiunti alla fine dell'output

3.1.1.5. Repeat Offsets (Offset ripetuti)​

Come descritto sopra, i primi tre valori definiscono gli offset ripetuti; li chiamiamo Repeated_Offset1, Repeated_Offset2 e Repeated_Offset3. Sono ordinati per recenza, con Repeated_Offset1 che rappresenta "il più recente".

Se offset_value è 1, l'offset utilizzato è Repeated_Offset1, e così via.

C'è un'eccezione: quando la literals_length della sequenza corrente è 0, gli offset ripetuti vengono spostati di 1, quindi:

  • offset_value di 1 significa Repeated_Offset2
  • offset_value di 2 significa Repeated_Offset3
  • offset_value di 3 significa Repeated_Offset1 - 1_byte

Inizializzazione​

Per il primo blocco, la cronologia degli offset iniziali viene riempita con i seguenti valori:

  • Repeated_Offset1 = 1
  • Repeated_Offset2 = 4
  • Repeated_Offset3 = 8

A meno che non venga utilizzato un dizionario, nel qual caso provengono dal dizionario.

Quindi ogni blocco ottiene la sua cronologia degli offset iniziali dai valori finali del Compressed_Block più recente. Si noti che i blocchi che non sono Compressed_Blocks vengono saltati; non influenzano la cronologia degli offset.

Regole di aggiornamento​

Durante l'esecuzione delle sequenze di un Compressed_Block, i valori dei Repeated_Offsets vengono mantenuti aggiornati in modo che rappresentino sempre i tre offset utilizzati più di recente. Per ottenere ciò, vengono aggiornati dopo l'esecuzione di ogni sequenza nel modo seguente:

Caso 1: Offset non ripetuto​

Quando l'offset_value della sequenza non fa riferimento a uno dei Repeated_Offsets (quando ha un valore maggiore di 3, o quando ha il valore 3 e la literals_length della sequenza è zero):

  • I valori dei Repeated_Offsets vengono spostati indietro di uno
  • Repeated_Offset1 assume il valore dell'offset appena utilizzato

Formula di aggiornamento:

Repeated_Offset3 = Repeated_Offset2
Repeated_Offset2 = Repeated_Offset1
Repeated_Offset1 = nuovo offset

Caso 2: Offset ripetuto​

Quando l'offset_value della sequenza fa riferimento a uno dei Repeated_Offsets (quando ha il valore 1 o 2, o quando ha il valore 3 e la literals_length della sequenza è diversa da zero):

  • I Repeated_Offsets vengono riordinati
  • Repeated_Offset1 assume il valore del Repeated_Offset utilizzato
  • I valori esistenti vengono respinti dal primo Repeated_Offset al Repeated_Offset selezionato da offset_value

Questo effettua efficacemente una rotazione avvolgente a un passo di questi valori di offset, in modo che il loro ordine rifletta nuovamente la loro recenza di utilizzo.

Tabella di esempio di aggiornamento​

La seguente tabella mostra i valori quando si applica una serie di sequenze ai Repeated_Offsets:

offset_valueliterals_lengthRepeated_Offset1Repeated_Offset2Repeated_Offset3Comment (Commento)
--148Valore iniziale
111411111114Non-ripetizione
122111114Ripetizione1; nessun cambiamento
222522222211111Non-ripetizione
1114111111122221111Non-ripetizione
333633333311112222Non-ripetizione
222111133332222Ripetizione2; scambio 1 e 2
333222211113333Ripetizione3; rotazione 3 a 1
10222122221111Offset analizzato inserito
10222222213333Ripetizione2

Tabella 18: Repeated_Offsets

Gestione dei casi speciali​

Caso literals_length = 0​

Quando literals_length = 0, l'interpretazione di offset_value si sposta:

offset_valueOffset effettivamente utilizzato
1Repeated_Offset2
2Repeated_Offset3
3Repeated_Offset1 - 1

Questo trattamento speciale è destinato a ottimizzare le operazioni di copia di corrispondenza consecutive.

Punti chiave​

  1. Principio di recenza: Repeated_Offset1 è sempre l'offset utilizzato più di recente
  2. Aggiornamento automatico: La cronologia degli offset viene aggiornata automaticamente dopo ogni esecuzione di sequenza
  3. Supporto dizionario: I valori iniziali possono provenire dal dizionario
  4. Spostamento speciale: L'interpretazione dell'offset cambia quando literals_length=0

3.1.2. Skippable Frames (Frame saltabili)​

+==============+============+===========+
|| Magic_Number | Frame_Size | User_Data |
+==============+============+===========+
||   4 bytes    |  4 bytes   |  n bytes  |
+--------------+------------+-----------+

Tabella 19: Frame saltabili

I frame saltabili consentono di inserire metadati definiti dall'utente in un flusso di frame concatenati.

I frame saltabili definiti in questa specifica sono compatibili con i frame saltabili in [LZ4].

Dal punto di vista di un decodificatore compatibile, i frame saltabili devono semplicemente essere saltati, il loro contenuto ignorato, e la decodifica riprende dopo il frame saltabile.

Va notato che i frame saltabili possono essere utilizzati per aggiungere filigrane ai flussi di frame concatenati, incorporare qualsiasi tipo di informazione di tracciamento (anche solo un identificatore univoco universale (UUID)). Gli utenti vigili su tali possibilità dovrebbero scansionare i flussi di frame concatenati per tentare di rilevare tali frame per analisi o rimozione.

Descrizioni dei campi​

Magic_Number (Numero magico)​

Dimensione: 4 byte, formato little-endian
Valore: 0x184D2A5?, che significa qualsiasi valore da 0x184D2A50 a 0x184D2A5F

Tutti i 16 valori identificano validamente i frame saltabili. Questa specifica non dettaglia alcun metodo di marcatura specifico per i frame saltabili.

Intervallo del numero magico:

  • Valore minimo: 0x184D2A50
  • Valore massimo: 0x184D2A5F
  • Totale: 16 numeri magici validi

Frame_Size (Dimensione frame)​

Dimensione: 4 byte, formato little-endian, 32 bit senza segno
Significato: La dimensione dei User_Data successivi in byte (non include il numero magico e il campo dimensione stesso)

Ciò significa che User_Data non può essere maggiore di (2^32 - 1) byte.

Dimensione massima User_Data: 4.294.967.295 byte (circa 4 GB)

User_Data (Dati utente)​

Dimensione: Variabile (specificata da Frame_Size)
Contenuto: Dati arbitrari

Questo campo può contenere qualsiasi cosa. I dati verranno saltati dal decodificatore.

Scenari di utilizzo​

1. Incorporazione di metadati​

  • Informazioni sulla versione
  • Timestamp di creazione
  • Informazioni sull'autore
  • Dati di licenza

2. Filigrana e tracciamento​

  • Incorporazione UUID
  • Tracciamento della fonte
  • Identificazione del canale di distribuzione

3. Dati specifici dell'applicazione​

  • Intestazioni personalizzate
  • Configurazione dell'applicazione
  • Informazioni estese

Note di compatibilità​

Comportamento del decodificatore​

Un decodificatore conforme alla specifica deve:

  1. Riconoscere il numero magico: Rilevare numeri magici nell'intervallo 0x184D2A5?
  2. Leggere la dimensione: Analizzare il campo Frame_Size
  3. Saltare i dati: Saltare Frame_Size byte di User_Data
  4. Continuare la decodifica: Continuare l'elaborazione dopo il frame saltabile

Raccomandazioni per il codificatore​

I codificatori possono:

  1. Posizionamento arbitrario: Inserire frame saltabili in qualsiasi posizione nel flusso di frame
  2. Frame multipli: Inserire più frame saltabili
  3. Marcatura personalizzata: Utilizzare uno qualsiasi dei 16 numeri magici per la marcatura interna

Considerazioni sulla sicurezza​

Problemi di privacy​

I frame saltabili possono essere utilizzati per:

  • Tracciare il flusso di dati
  • Incorporare informazioni nascoste
  • Identificare la fonte dei dati

Misure raccomandate​

Per gli utenti attenti alla privacy:

  1. Rilevamento tramite scansione: Scansionare il flusso di input per rilevare frame saltabili
  2. Analisi del contenuto: Esaminare il contenuto di User_Data
  3. Rimozione selettiva: Rimuovere i frame saltabili secondo necessità
  4. Registrazione: Registrare i frame saltabili rilevati per audit

Esempi​

Incorporare UUID​

Magic_Number: 0x184D2A50
Frame_Size: 16 (0x10000000, little-endian)
User_Data: [UUID di 16 byte]

Incorporare timestamp​

Magic_Number: 0x184D2A51
Frame_Size: 8
User_Data: [Timestamp Unix di 8 byte]

Compatibilità con LZ4​

Il formato dei frame saltabili è compatibile con LZ4, consentendo:

  • Interoperabilità degli strumenti tra formati
  • Gestione uniforme dei metadati
  • Implementazione semplificata del decodificatore

Nota: I frame saltabili non influenzano il contenuto dei dati decompressi, solo i metadati del flusso.

4. Entropy Encoding (Codifica dell'entropia)​

Il formato Zstandard utilizza due tipi di codifica dell'entropia: FSE e codifica di Huffman. Huffman viene utilizzato per comprimere i letterali (Literals), mentre FSE viene utilizzato per tutti gli altri simboli (Literals_Length_Code, Match_Length_Code e codici di offset) e per comprimere gli header Huffman.

4.1 FSE (Entropia a Stati Finiti)​

FSE, abbreviazione di Finite State Entropy (Entropia a Stati Finiti), è un codec di entropia basato su [ANS]. La codifica/decodifica FSE coinvolge uno stato (State) che viene trasportato tra i simboli, quindi la decodifica deve essere eseguita nella direzione opposta rispetto alla codifica. Pertanto, tutti i flussi di bit FSE (Bitstreams) vengono letti dalla fine all'inizio. Si noti che l'ordine dei bit nel flusso non è invertito; vengono semplicemente letti nell'ordine inverso rispetto a quello in cui sono stati scritti.

Per ulteriori dettagli su FSE, vedere "FiniteStateEntropy" [FSE].

La decodifica FSE coinvolge una tabella di decodifica (Decoding Table) che ha una dimensione in potenza di 2 e contiene tre elementi: Symbol (Simbolo), Num_Bits (Numero di bit) e Baseline (Linea di base). Il logaritmo in base 2 della dimensione della tabella è il suo Accuracy_Log (Log di precisione). Un valore di stato FSE rappresenta un indice in questa tabella.

Per ottenere il valore di stato iniziale, consumare Accuracy_Log bit dal flusso come valore little-endian. Il simbolo successivo nel flusso è il Symbol indicato nella tabella per quello stato. Per ottenere il valore di stato successivo, il decoder dovrebbe consumare Num_Bits bit dal flusso come valore little-endian e aggiungerlo a Baseline.

4.1.1 FSE Table Description (Descrizione della tabella FSE)​

Per decodificare i flussi FSE, è necessario costruire la tabella di decodifica. Il formato Zstandard codifica le descrizioni delle tabelle FSE come descritto qui.

Una tabella di distribuzione FSE (Distribution Table) descrive le probabilità di tutti i simboli da 0 all'ultimo presente (incluso) su una scala normalizzata di (1 &lt;&lt; Accuracy_Log). Si noti che devono esserci due o più simboli con probabilità diversa da zero.

Un flusso di bit viene letto in avanti, in modo little-endian. Non è necessario conoscerne la dimensione esatta, poiché la dimensione sarà scoperta e riportata dal processo di decodifica. Il flusso di bit inizia riportando su quale scala opera. Se low4bits designa i 4 bit più bassi del primo byte, allora Accuracy_Log = low4bits + 5.

Questo è seguito da ciascun valore di simbolo, da 0 all'ultimo presente. Il numero di bit utilizzati da ciascun campo è variabile e dipende da:

Probabilità rimanenti + 1 : Ad esempio, presumendo un Accuracy_Log di 8 e presumendo che siano già stati distribuiti 100 punti di probabilità, il decoder può leggere qualsiasi valore da 0 a (256 - 100 + 1) == 157, incluso. Pertanto, deve leggere log₂(157) == 8 bit.

Valore decodificato : I valori piccoli usano 1 bit in meno. Ad esempio, presumendo che i valori da 0 a 157, inclusi, siano possibili, rimangono 255 - 157 = 98 valori in un campo di 8 bit. I primi 98 valori (quindi da 0 a 97) usano solo 7 bit, e i valori da 98 a 157 usano 8 bit. Questo è ottenuto attraverso lo schema nella tabella 20:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

Tabella 20: Valori decodificati

Le probabilità dei simboli vengono lette una per una, in ordine. La probabilità è ottenuta dal valore decodificato (Value Decoded) usando la formula P = Value - 1. Questo significa che il valore 0 diventa la probabilità negativa -1. Questa è una probabilità speciale che significa "minore di 1". Il suo effetto sulla tabella di distribuzione è descritto di seguito. Ai fini del calcolo dei punti di probabilità totali allocati, conta come 1.

Quando un simbolo ha una probabilità di zero, è seguito da un flag di ripetizione (Repeat Flag) di 2 bit. Questo flag di ripetizione indica quante probabilità di zero seguono quella corrente. Fornisce un numero che va da 0 a 3. Se è un 3, segue un altro flag di ripetizione di 2 bit, e così via.

Quando l'ultimo simbolo raggiunge un totale cumulativo di (1 &lt;&lt; Accuracy_Log), la decodifica è completa. Se l'ultimo simbolo fa superare il totale cumulativo (1 &lt;&lt; Accuracy_Log), la distribuzione è considerata corrotta.

Infine, il decoder può determinare quanti byte sono stati utilizzati in questo processo e quanti simboli sono presenti. Il flusso di bit consuma un numero intero di byte. Qualsiasi bit rimanente nell'ultimo byte è semplicemente inutilizzato.

Il contesto in cui la tabella deve essere utilizzata specifica un numero atteso di simboli. Quel numero atteso di simboli non supera mai 256. Se il numero di simboli decodificati non è uguale a quello atteso, l'header dovrebbe essere considerato corrotto.

La distribuzione delle probabilità normalizzate è sufficiente per creare una tabella di decodifica unica. La tabella ha una dimensione di (1 &lt;&lt; Accuracy_Log). Ogni cella descrive il simbolo decodificato e le istruzioni per ottenere lo stato successivo.

I simboli vengono scansionati nel loro ordine naturale per le probabilità "minore di 1" come descritto sopra. Ai simboli con questa probabilità viene assegnata una singola cella, partendo dalla fine della tabella e retrocedendo. Questi simboli definiscono un reset completo dello stato (Full State Reset), leggendo Accuracy_Log bit.

Tutti i simboli rimanenti vengono allocati nel loro ordine naturale. Partendo dal simbolo 0 e dalla posizione di tabella 0, ogni simbolo riceve tante celle quante la sua probabilità. L'allocazione delle celle è distribuita, non lineare; ogni posizione successiva segue questa regola:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

Una posizione viene saltata se è già occupata da un simbolo con probabilità "minore di 1". La posizione non si resetta tra i simboli; itera semplicemente attraverso ogni posizione nella tabella, passando al simbolo successivo quando sono stati allocati abbastanza stati a quello corrente.

Il risultato è una lista di valori di stato. Ogni stato decodificherà il simbolo corrente.

Per ottenere il Number_of_Bits e la Baseline richiesti per lo stato successivo, è prima necessario ordinare tutti gli stati nel loro ordine naturale. Gli stati inferiori avranno bisogno di 1 bit in più rispetto a quelli superiori. Il processo viene ripetuto per ogni simbolo.

Ad esempio, presumendo che un simbolo abbia una probabilità di 5, riceve cinque valori di stato. Gli stati vengono ordinati in ordine naturale. La potenza di 2 successiva è 8. Lo spazio delle probabilità è diviso in 8 parti uguali. Presumendo che l'Accuracy_Log sia 7, questo definisce 128 stati, e ogni quota (divisa per 8) ha una dimensione di 16. Per raggiungere 8, 8 - 5 = 3 stati più bassi conteranno "doppio", raddoppiando il numero di quote (larghezza 32), richiedendo 1 bit in più nel processo.

La Baseline viene assegnata partendo dagli stati superiori che usano meno bit, procedendo naturalmente, quindi riprendendo dal primo stato, ognuno prendendo la sua larghezza allocata dalla Baseline.

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

Tabella 21: Assegnazioni Baseline

Lo stato successivo è determinato dallo stato corrente leggendo il Number_of_Bits richiesto e aggiungendo la Baseline specificata.

Vedere l'Appendice A per i risultati di questo processo applicati alle distribuzioni predefinite.

4.2 Huffman Coding (Codifica di Huffman)​

I flussi codificati Huffman di Zstandard vengono letti all'indietro, simili ai flussi di bit FSE. Pertanto, per trovare l'inizio del flusso di bit, è necessario conoscere l'offset dell'ultimo byte del flusso codificato Huffman.

Dopo aver scritto l'ultimo bit contenente informazioni, il compressore scrive un singolo bit 1 e quindi riempie il resto del byte con bit 0. L'ultimo byte del flusso di bit compresso non può essere 0 per questo motivo.

Durante la decompressione, l'ultimo byte contenente il riempimento è il primo byte da leggere. Il decompressore deve saltare fino a 7 bit di riempimento 0 così come il primo bit 1 che si verifica. Successivamente, inizia la parte utile del flusso di bit.

Il flusso di bit contiene simboli codificati Huffman in ordine little-endian, con i codici definiti dal metodo seguente.

4.2.1 Huffman Tree Description (Descrizione dell'albero di Huffman)​

La codifica a prefisso (Prefix Coding) rappresenta i simboli da un alfabeto noto a priori mediante sequenze di bit (parole di codice), una parola di codice per ogni simbolo, in modo tale che simboli diversi possano essere rappresentati da sequenze di bit di lunghezze diverse, ma un parser possa sempre analizzare una stringa codificata in modo inequivocabile, simbolo per simbolo.

Dato un alfabeto con frequenze di simboli note, l'algoritmo di Huffman consente la costruzione di un codice a prefisso ottimale utilizzando il minor numero di bit di tutti i possibili codici a prefisso per quell'alfabeto.

Il codice a prefisso non deve superare una lunghezza massima del codice. Più bit migliorano la precisione ma producono una dimensione dell'header maggiore e richiedono più memoria o operazioni di decodifica più complesse. Questa specifica limita la lunghezza massima del codice a 11 bit.

Tutti i valori letterali da zero (incluso) all'ultimo presente (escluso) sono rappresentati da Weight (Peso) con valori da 0 a Max_Number_of_Bits. La trasformazione da Weight a Number_of_Bits segue questo pseudocodice:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

Il Weight dell'ultimo simbolo è dedotto da quelli precedentemente decodificati, completando alla potenza di 2 più vicina. Questa potenza di 2 fornisce Max_Number_of_Bits, la profondità dell'albero corrente.

(Continuazione con tabelle 22-26 e dettagli della codifica Huffman)

5. Dictionary Format (Formato Dizionario)​

Zstandard è compatibile con i "dizionari di contenuto grezzo (Raw Content Dictionaries)", senza alcuna restrizione di formato, tranne che devono essere almeno 8 byte. Questi dizionari funzionano come se fossero solo la parte di contenuto di un dizionario formattato.

Tuttavia, i dizionari creati da zstd --train nell'implementazione di riferimento seguono un formato specifico, descritto qui.

I dizionari non sono inclusi nel contenuto compresso, ma forniti fuori banda (out of band). Cioè, Dictionary_ID identifica quale dizionario deve essere utilizzato, ma questa specifica non descrive il meccanismo per ottenere il dizionario prima dell'uso durante la compressione o decompressione.

Un dizionario ha una dimensione, definita dai limiti del buffer o dalla dimensione del file. Il formato generale è:

+==============+===============+================+=========+
| Magic_Number | Dictionary_ID | Entropy_Tables | Content |
+==============+===============+================+=========+

Tabella 27: Formato Generale Dizionario

Magic_Number (Numero Magico) : ID di 4 byte, valore 0xEC30A437, formato little-endian.

Dictionary_ID (ID Dizionario) : 4 byte, memorizzati in formato little-endian. Dictionary_ID può essere qualsiasi valore, tranne 0 (che indica l'assenza di Dictionary_ID). I decoder lo utilizzano per verificare di utilizzare il dizionario corretto. Se il frame viene distribuito in un ambiente privato, può essere utilizzato qualsiasi Dictionary_ID. Tuttavia, per la distribuzione pubblica di frame compressi, i seguenti intervalli sono riservati e non devono essere utilizzati:

  • Intervallo basso: &lt;= 32767
  • Intervallo alto: >= 2³¹

Entropy_Tables (Tabelle di Entropia) : Seguono lo stesso formato delle tabelle nei blocchi compressi. Per informazioni su come decodificare queste tabelle, consultare le sezioni FSE e Huffman pertinenti. Sono memorizzate nel seguente ordine: tabella Huffman per i letterali, tabella FSE per gli offset, tabella FSE per le lunghezze di corrispondenza e tabella FSE per le lunghezze dei letterali. Queste tabelle riempiono la modalità letterali con statistiche ripetute (Repeat Stats Literals Mode) e la modalità distribuzione ripetuta (Repeat Distribution Mode) della decodifica delle sequenze. Infine, ci sono 3 valori di offset che riempiono gli offset ripetuti (invece di usare {1,4,8}), memorizzati in sequenza, ciascuno 4 byte little-endian, per un totale di 12 byte. Ogni offset ripetuto deve avere un valore inferiore alla dimensione del dizionario.

Content (Contenuto) : Il resto del dizionario è il suo contenuto. Il contenuto funge da "passato" prima dei dati da comprimere o decomprimere, in modo che possa essere referenziato nei comandi di sequenza (Sequence Commands). Finché la quantità di dati decodificati da questo frame è minore o uguale a Window_Size, i comandi di sequenza possono specificare un offset più lungo della lunghezza totale dell'output decodificato finora per fare riferimento al dizionario, anche a parti del dizionario con offset maggiori di Window_Size. Tuttavia, dopo che l'output totale supera Window_Size, questo non è più consentito e il dizionario non è più accessibile.

6. Use of Dictionaries (Uso dei Dizionari)​

Sono in corso esplorazioni per fornire disposizioni per l'uso dei dizionari con zstd. Ad esempio, vedere [DICT-SEC]. Un possibile risultato sarebbe un registro di dizionari ben testati, ottimizzati per diversi casi d'uso, e i loro identificatori, possibilmente insieme a un meccanismo di negoziazione privata (Private Negotiation Mechanism) per l'uso di dizionari non registrati.

Per garantire la compatibilità con le specifiche future per l'uso dei dizionari con i payload zstd, in particolare con la compatibilità MIME, i contenuti codificati utilizzando il tipo di media registrato qui NON DOVREBBERO (SHOULD NOT) utilizzare dizionari. Un'eccezione a questo requisito potrebbe essere la negoziazione privata del dizionario suggerita sopra, che non fa parte di questa specifica.

7. IANA Considerations (Considerazioni IANA)​

IANA ha aggiornato due registrazioni preesistenti ed effettuato una nuova registrazione, come descritto di seguito.

7.1 The 'application/zstd' Media Type (Il Tipo Media 'application/zstd')​

Il tipo media application/zstd identifica un blocco di dati compresso utilizzando zstd. I dati sono il flusso di byte descritto in questo documento. IANA ha aggiunto quanto segue al registro "Media Types" (Tipi Media):

Type name (Nome tipo) : application

Subtype name (Nome sottotipo) : zstd

Required parameters (Parametri richiesti) : N/A

Optional parameters (Parametri opzionali) : N/A

Encoding considerations (Considerazioni sulla codifica) : binary

Security considerations (Considerazioni sulla sicurezza) : Vedere la Sezione 8 di RFC 8878.

Interoperability considerations (Considerazioni sull'interoperabilità) : N/A

Published specification (Specifica pubblicata) : RFC 8878

Applications which use this media type (Applicazioni che utilizzano questo tipo media) : Ovunque la dimensione dei dati sia un problema

Fragment identifier considerations (Considerazioni sull'identificatore di frammento) : Nessun identificatore di frammento è definito per questo tipo.

Additional information (Informazioni aggiuntive) :

  • Deprecated alias names for this type (Nomi alias obsoleti per questo tipo): N/A
  • Magic number(s) (Numero(i) magico(i)): 4 byte, formato little-endian. Valore: 0xFD2FB528
  • File extension(s) (Estensione(i) file): zst
  • Macintosh file type code(s) (Codice(i) tipo file Macintosh): N/A

Person & email address to contact for further information (Persona e indirizzo email da contattare per ulteriori informazioni) : Yann Collet &lt;[email protected]&gt;

Intended usage (Uso previsto) : common (comune)

Restrictions on usage (Restrizioni sull'uso) : N/A

Author (Autore) : Murray S. Kucherawy

Change Controller (Controllore delle modifiche) : IETF

Provisional registration (Registrazione provvisoria) : no

For further information (Per ulteriori informazioni) : Vedere [ZSTD]

7.2 Content Encoding (Codifica Contenuto)​

IANA ha aggiunto la seguente voce al registro "HTTP Content Coding Registry" (Registro Codifica Contenuto HTTP) nel registro "Hypertext Transfer Protocol (HTTP) Parameters" (Parametri Protocollo di Trasferimento Ipertesto (HTTP)):

Name (Nome) : zstd

Description (Descrizione) : Flusso di byte compresso utilizzando il protocollo Zstandard

Reference (Riferimento) : RFC 8878

7.3 Structured Syntax Suffix (Suffisso Sintassi Strutturata)​

IANA ha registrato quanto segue nel registro "Structured Syntax Suffix" (Suffisso Sintassi Strutturata):

Name (Nome) : Zstandard

+suffix (Suffisso) : +zstd

Encoding Considerations (Considerazioni sulla Codifica) : binary

Interoperability Considerations (Considerazioni sull'Interoperabilità) : N/A

Fragment Identifier Considerations (Considerazioni sull'Identificatore di Frammento) : La sintassi e la semantica degli identificatori di frammento specificati per +zstd DEVONO essere le stesse di quelle specificate per application/zstd.

Security Considerations (Considerazioni sulla Sicurezza) : Vedere la Sezione 8 di RFC 8878.

Contact (Contatto) : Vedere l'autore del tipo media application/zstd.

Author/Change Controller (Autore/Controllore delle Modifiche) : IETF

7.4 Dictionaries (Dizionari)​

I lavori in corso includono lo sviluppo di dizionari che ottimizzeranno la compressione e decompressione di tipi specifici di dati. Specificare tali dizionari per uso pubblico richiederebbe la registrazione di punti codice dall'intervallo riservato descritto nella Sezione 3.1.1.1.3 e la loro associazione a un dizionario specifico.

Attualmente, nessun dizionario di questo tipo è pubblicato per uso pubblico, quindi questo documento non richiede immediatamente a IANA di creare un tale registro.

8. Security Considerations (Considerazioni sulla sicurezza)​

Qualsiasi metodo di compressione dei dati comporta la riduzione della ridondanza nei dati. Zstandard non fa eccezione e si applicano le solite precauzioni.

Non si dovrebbe mai comprimere un messaggio il cui contenuto deve rimanere segreto con un messaggio generato da terze parti. Tale compressione può essere utilizzata per indovinare il contenuto del messaggio segreto attraverso l'analisi della riduzione dell'entropia (Entropy Reduction Analysis). Questo è stato dimostrato nell'attacco CRIME (Compression Ratio Info-leak Made Easy) [CRIME], ad esempio.

Un decoder deve dimostrare capacità di rilevare e prevenire qualsiasi tipo di manomissione dei dati nel frame compresso che possa scatenare guasti del sistema, come la lettura o la scrittura oltre gli intervalli di memoria consentiti. Questo può essere garantito dal linguaggio di implementazione o da attenti controlli dei limiti (Bound Checking). Di particolare nota è la codifica dei valori Number_of_Sequences che causano la lettura del decoder nell'intestazione del blocco (e oltre), così come l'indicazione di una Frame_Content_Size inferiore ai dati effettivamente decompressi, nel tentativo di innescare un overflow del buffer (Buffer Overflow). Si raccomanda vivamente di eseguire test di fuzzing (fuzz-test, ovvero fornire input non validi, imprevisti o casuali e verificare il funzionamento sicuro) sulle implementazioni del decoder per testare e rafforzare la loro capacità di rilevare frame errati e gestirli senza alcun effetto collaterale negativo sul sistema.

Un attaccante può fornire frame compressi correttamente formati con requisiti di memoria irragionevoli. Un decoder deve sempre controllare i requisiti di memoria e imporre alcuni limiti (specifici del sistema) per proteggere l'utilizzo della memoria da tali scenari.

La compressione può essere ottimizzata addestrando un dizionario su una varietà di payload di contenuti correlati. Questo dizionario deve quindi essere disponibile al decoder affinché la decompressione del payload sia possibile. Sebbene questo documento non specifichi come acquisire un dizionario per un dato payload compresso, vale la pena notare che i dizionari di terze parti possono interagire in modo imprevisto con un decoder, portando a possibili attacchi di esaurimento della memoria o di altre risorse (Resource-exhaustion Attacks). Ci aspettiamo che tali argomenti vengano discussi più dettagliatamente nella sezione Considerazioni sulla sicurezza di un prossimo RFC sull'acquisizione e trasmissione di dizionari, ma evidenziamo questo problema ora per eccesso di cautela.

Come discusso nella sezione 3.1.2, è possibile memorizzare metadati utente arbitrari in frame ignorabili (Skippable Frames). Mentre tali frame vengono ignorati durante la decompressione dei dati, possono essere utilizzati come filigrana (Watermark) per tracciare il percorso del payload compresso.

Appendix A. Decoding Tables for Predefined Codes (Appendice A. Tabelle di decodifica per codici predefiniti)​

Questa appendice contiene le tabelle di decodifica FSE per codici lunghezza letterale, codici lunghezza corrispondenza e codici offset predefiniti. Queste tabelle sono costruite utilizzando l'algoritmo fornito nella sezione 4.1.1. Le tabelle qui possono essere utilizzate come esempio per verificare in modo incrociato che un'implementazione costruisca correttamente le sue tabelle di decodifica.

A.1. Literals Length Code Table (Tabella codici lunghezza letterale)​

State (Stato)Symbol (Simbolo)Number_Of_Bits (Numero di bit)Base
0000
0040
10416
21532
3350
4450
5650
6750
7950
81050
91250
101460
111650
121850
131950
142150
152250
162450
1725532
182650
192760
202960
213160
220432
23140
24250
254532
26550
277532
28850
2910532
301150
311360
3216532
331750
3419532
352050
3622532
372350
382540
3925416
4026532
412860
423060
430448
441416
452532
463532
475532
486532
498532
509532
5111532
5212532
531560
5417532
5518532
5620532
5721532
5823532
5924532
603560
613460
623360
633260

Tabella 28: Tabella codici lunghezza letterale

A.2. Match Length Code Table (Tabella codici lunghezza corrispondenza)​

State (Stato)Symbol (Simbolo)Number_Of_Bits (Numero di bit)Base
0000
0060
1140
22532
3350
4550
5650
6850
71060
81360
91660
101960
112260
122560
132860
143160
153360
163560
173760
183960
194160
204360
214560
221416
23240
243532
25450
266532
27750
28960
291260
301560
311860
322160
332460
342760
353060
363260
373460
383660
393860
404060
414260
424460
431432
441448
452416
464532
475532
487532
498532
501160
511460
521760
532060
542360
552660
562960
575260
585160
595060
604960
614860
624760
634660

Tabella 29: Tabella codici lunghezza corrispondenza

A.3. Offset Code Table (Tabella codici offset)​

State (Stato)Symbol (Simbolo)Number_Of_Bits (Numero di bit)Base
0000
0050
1640
2950
31550
42150
5350
6740
71250
81850
92350
10550
11840
121450
132050
14250
157416
161150
171750
182250
19450
208416
211350
221950
23150
246416
251050
261650
272850
282750
292650
302550
312450

Tabella 30: Tabella codici offset

Appendix B. Changes since RFC 8478 (Appendice B. Modifiche da RFC 8478)​

Di seguito sono riportate le modifiche in questo documento rispetto a RFC 8478:

  • Applicazione degli errata [Err5786] e [Err6303].

  • Chiarimento della compatibilità futura riguardo ai dizionari.

  • Chiarimento dell'applicazione di Block_Maximum_Size.

  • Aggiunta della registrazione del suffisso del tipo di media strutturato.

  • Chiarimento che il checksum del contenuto è sempre di 4 byte.

  • Chiarimento della gestione degli input riservati e corrotti.

  • Aggiunta di considerazioni sugli identificatori di frammento alla registrazione del tipo di media.

Acknowledgments (Ringraziamenti)​

zstd è stato sviluppato da Yann Collet.

Felix Handte e Nick Terrell hanno fornito feedback che è stato incorporato in questa revisione e RFC 8478. RFC 8478 ha anche ricevuto contributi da Bobo Bose-Kolanu, Kyle Nekritz e David Schleimer.

Authors' Addresses (Indirizzi degli Autori)​

Yann Collet
Facebook
1 Hacker Way
Menlo Park, CA 94025
Stati Uniti d'America

Email: [email protected]

Murray S. Kucherawy (editore)
Facebook
1 Hacker Way
Menlo Park, CA 94025
Stati Uniti d'America

Email: [email protected]