Passa al contenuto principale

11. Considerazioni per le implementazioni del compressore

11. Considerazioni per le implementazioni del compressore (Considerations for Compressor Implementations)​

Poiché l'intenzione di questo documento è definire il formato dei dati compressi brotli senza riferimento a un particolare algoritmo di compressione, il materiale in questa sezione non fa parte della definizione del formato e un compressore non ha bisogno di seguirlo per essere conforme.

11.1. Compressore banale (Trivial Compressor)​

In questa sezione, presentiamo un algoritmo molto semplice che produce un flusso brotli valido che rappresenta una sequenza arbitraria di byte non compressi, nella forma della seguente funzione in linguaggio C++.

string BrotliCompressTrivial(const string& u) {
   if (u.empty()) {
      return string(1, 6);
   }
   int i;
   string c;
   c.append(1, 12);
   for (i = 0; i + 65535 < u.size(); i += 65536) {
      c.append(1, 248);
      c.append(1, 255);
      c.append(1, 15);
      c.append(&u[i], 65536);
   }
   if (i < u.size()) {
      int r = u.size() - i - 1;
      c.append(1, (r & 31) << 3);
      c.append(1, r >> 5);
      c.append(1, 8 + (r >> 13));
      c.append(&u[i], r + 1);
   }
   c.append(1, 3);
   return c;
}

Si noti che questo semplice algoritmo non comprime effettivamente i dati, cioè la rappresentazione brotli sarà sempre più grande dell'originale, ma mostra che ogni sequenza di N byte non compressi può essere rappresentata con un flusso brotli valido che non è più lungo di N + (3 * (N >> 16) + 5) byte.

11.2. Allineamento dei meta-blocchi compressi ai limiti di byte (Aligning Compressed Meta-Blocks to Byte Boundaries)​

Come descritto nella sezione 9, solo i meta-blocchi che seguono immediatamente un meta-blocco non compresso o un meta-blocco di metadati sono garantiti per iniziare su un limite di byte. In alcune applicazioni, potrebbe essere necessario che ogni meta-blocco non di metadati inizi su un limite di byte. Questo può essere ottenuto aggiungendo un meta-blocco di metadati vuoto dopo ogni meta-blocco non di metadati che non termina su un limite di byte.

11.3. Creazione di parti autonome all'interno dei dati compressi (Creating Self-Contained Parts within the Compressed Data)​

In alcune implementazioni di codificatori, potrebbe essere necessario rendere autonoma una sequenza di byte in un flusso brotli, cioè dovrebbe essere in grado di essere decompressa indipendentemente dalle parti precedenti dei dati compressi. Questa è una caratteristica utile per tre motivi. Primo, se un grande file compresso è danneggiato, è possibile recuperare una parte del file dopo il danno. Secondo, è utile quando si effettua il trasferimento differenziale di dati compressi. Se una sequenza di byte non compressi è invariata ed è stata compressa indipendentemente dai dati precedenti, allora la rappresentazione compressa potrebbe anche essere invariata e quindi può essere trasferita in modo molto economico. Terzo, se le sequenze di byte non compressi sono compresse indipendentemente, ciò consente la compressione parallela di queste sequenze di byte nello stesso file, oltre alla compressione parallela di più file.

Date due sequenze di byte non compressi, U0 e U1, ora descriveremo come creare due sequenze di byte compressi, C0 e C1, in modo tale che la concatenazione di C0 e C1 sia un flusso brotli valido, e che C0 e C1 (insieme al primo byte di C0 che contiene la dimensione della finestra) possano essere decompressi indipendentemente l'uno dall'altro in U0 e U1.

Quando si comprime la sequenza di byte U0 per produrre C0, possiamo utilizzare qualsiasi compressore che opera sull'insieme completo di byte non compressi U0, con le seguenti due modifiche. Primo, il bit ISLAST dell'ultimo meta-blocco di C0 non deve essere impostato. Secondo, C0 deve terminare su un limite di byte, il che può essere assicurato aggiungendo un meta-blocco di metadati vuoto ad esso, come nella sezione 11.2.

Quando si comprime la sequenza di byte U1 per produrre C1, possiamo utilizzare qualsiasi compressore che avvia un nuovo meta-blocco all'inizio di U1 nel flusso di input U0+U1, con le seguenti due modifiche. Primo, le distanze all'indietro in C1 non devono fare riferimento a parole del dizionario statico o byte non compressi in U0. Anche se una sequenza di byte in U1 corrisponde a una parola del dizionario statico o a una sequenza di byte che si sovrappone a U0, il compressore deve rappresentare questa sequenza di byte con una combinazione di inserimenti letterali e riferimenti all'indietro a byte in U1 invece. Secondo, il buffer circolare delle ultime quattro distanze deve essere riempito prima con distanze in C1 prima di utilizzarlo per codificare altre distanze in C1. Si noti che entrambi i compressori che producono C0 e C1 devono utilizzare la stessa dimensione della finestra, ma l'intestazione del flusso viene emessa solo dal compressore che produce C0.

Si noti che questo metodo può essere facilmente generalizzato a più di due sequenze di byte non compressi.

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

Ultimo aggiornamento il