Passa al contenuto principale

8. Dizionario statico (Static Dictionary)

8. Dizionario statico (Static Dictionary)​

In qualsiasi momento durante la decodifica dei dati compressi, un riferimento a una stringa duplicata nei dati non compressi prodotti finora ha un valore di distanza massima all'indietro (Maximum Backward Distance Value), che è il minimo tra la dimensione della finestra (Window Size) e il numero di byte non compressi prodotti. Tuttavia, la decodifica di una distanza dal flusso compresso, come descritto nella sezione 4, può produrre distanze maggiori di questo valore massimo consentito. In questo caso, la distanza è trattata come un riferimento a una parola nel dizionario statico (Static Dictionary) fornito nell'appendice A. La lunghezza di copia (Copy Length) per un riferimento al dizionario statico deve essere compresa tra 4 e 24.

Il dizionario statico ha tre parti:

  • DICT[0..DICTSIZE]: un array di byte
  • DOFFSET[0..24]: un array di valori di offset di byte per ogni lunghezza
  • NDBITS[0..24]: un array di valori di profondità di bit per ogni lunghezza

Il numero di parole del dizionario statico per una data lunghezza è:

NWORDS[length] = 0                       (if length < 4)
NWORDS[length] = (1 << NDBITS[length])   (if length >= 4)

DOFFSET e DICTSIZE sono definiti dalla seguente ricorsione:

DOFFSET[0] = 0
DOFFSET[length + 1] = DOFFSET[length] + length * NWORDS[length]
DICTSIZE = DOFFSET[24] + 24 * NWORDS[24]

L'offset di una parola all'interno dell'array DICT per una data lunghezza e indice è:

offset(length, index) = DOFFSET[length] + index * length

Ogni parola del dizionario statico ha 121 forme diverse, ottenute applicando una trasformazione di parola (Word Transformation) a una parola base (Base Word) nell'array DICT. L'elenco delle trasformazioni di parole è fornito nell'appendice B. La parola del dizionario statico per una coppia <length, distance> può essere ricostruita come segue:

word_id = distance - (max allowed distance + 1)
index = word_id % NWORDS[length]
base_word = DICT[offset(length, index)..offset(length, index+1)-1]
transform_id = word_id >> NDBITS[length]

La stringa copiata nel flusso non compresso è calcolata applicando la trasformazione alla parola base del dizionario. Se transform_id è maggiore di 120, o la lunghezza è minore di 4 o maggiore di 24, allora il flusso compresso dovrebbe essere rifiutato come non valido.

Ogni trasformazione di parola ha la seguente forma:

transform_i(word) = prefix_i + T_i(word) + suffix_i

dove il pedice _i denota il transform_id sopra. Ogni T_i è una delle seguenti 21 trasformazioni elementari (Elementary Transforms):

Identity, FermentFirst, FermentAll,
OmitFirst1, ..., OmitFirst9, OmitLast1, ..., OmitLast9

La forma di queste trasformazioni elementari è la seguente:

Identity(word) = word

FermentFirst(word) = vedi sotto

FermentAll(word) = vedi sotto

OmitFirstk(word) = gli ultimi (length(word) - k) byte di word, o
                   stringa vuota se length(word) < k

OmitLastk(word) = i primi (length(word) - k) byte di word, o
                  stringa vuota se length(word) < k

Definiamo le trasformazioni FermentFirst e FermentAll utilizzate in questa specifica con le seguenti funzioni in linguaggio C:

int Ferment(uint8_t* word, int word_len, int pos) {
   if (word[pos] < 192) {
      if (word[pos] >= 97 and word[pos] <= 122) {
         word[pos] = word[pos] ^ 32;
      }
      return 1;
   } else if (word[pos] < 224) {
      if (pos + 1 < word_len) {
         word[pos + 1] = word[pos + 1] ^ 32;
      }
      return 2;
   } else {
      if (pos + 2 < word_len) {
         word[pos + 2] = word[pos + 2] ^ 5;
      }
      return 3;
   }
}

void FermentFirst(uint8_t* word, int word_len) {
   if (word_len > 0) {
      Ferment(word, word_len, 0);
   }
}

void FermentAll(uint8_t* word, int word_len) {
   int i = 0;
   while (i < word_len) {
      i += Ferment(word, word_len, i);
   }
}

L'appendice B contiene l'elenco delle trasformazioni specificando i componenti prefisso (Prefix), trasformazione elementare (Elementary Transform) e suffisso (Suffix) di ciascuna di esse. Si noti che la trasformazione elementare OmitFirst8 non è utilizzata nell'elenco delle trasformazioni. Le stringhe nell'appendice B sono in formato stringa C rispetto ai caratteri di escape (barra rovesciata).

Il numero massimo di byte aggiuntivi che una trasformazione può aggiungere a una parola base è 13. Poiché la parola base più grande è lunga 24 byte, un buffer di 38 byte è sufficiente per memorizzare tutte le parole trasformate (contando un byte zero terminale).

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

Ultimo aggiornamento il