10. Algoritmo di decodifica (Decoding Algorithm)
10. Algoritmo di decodifica (Decoding Algorithm)
L'algoritmo di decodifica (Decoding Algorithm) che produce i dati non compressi è il seguente:
leggere la dimensione della finestra
do
leggere il bit ISLAST
if ISLAST
leggere il bit ISLASTEMPTY
if ISLASTEMPTY
uscire dal ciclo
leggere MNIBBLES
if MNIBBLES è zero
verificare che il bit riservato sia zero
leggere MSKIPLEN
saltare tutti i bit fino al prossimo limite di byte
saltare MSKIPLEN byte
continuare al prossimo meta-blocco
else
leggere MLEN
if not ISLAST
leggere il bit ISUNCOMPRESSED
if ISUNCOMPRESSED
saltare tutti i bit fino al prossimo limite di byte
copiare MLEN byte di dati compressi come letterali
continuare al prossimo meta-blocco
ciclo per ogni tre categorie di blocchi (i = L, I, D)
leggere NBLTYPESi
if NBLTYPESi >= 2
leggere il codice prefisso per i tipi di blocchi, HTREE_BTYPE_i
leggere il codice prefisso per i conteggi di blocchi, HTREE_BLEN_i
leggere il conteggio di blocchi, BLEN_i
impostare il tipo di blocco, BTYPE_i a 0
inizializzare il penultimo e l'ultimo tipo di blocco a 0 e 1
else
impostare il tipo di blocco, BTYPE_i a 0
impostare il conteggio di blocchi, BLEN_i a 16777216
leggere NPOSTFIX e NDIRECT
leggere l'array dei modi di contesto letterali, CMODE[]
leggere NTREESL
if NTREESL >= 2
leggere la mappa di contesto letterale, CMAPL[]
else
riempire CMAPL[] con zeri
leggere NTREESD
if NTREESD >= 2
leggere la mappa di contesto di distanza, CMAPD[]
else
riempire CMAPD[] con zeri
leggere l'array dei codici prefissi letterali, HTREEL[]
leggere l'array dei codici prefissi di lunghezze inserimento-copia, HTREEI[]
leggere l'array dei codici prefissi di distanze, HTREED[]
do
if BLEN_I è zero
leggere il tipo di blocco usando HTREE_BTYPE_I e impostare BTYPE_I
salvare il tipo di blocco precedente
leggere il conteggio di blocchi usando HTREE_BLEN_I e impostare BLEN_I
decrementare BLEN_I
leggere il simbolo di lunghezza inserimento-copia usando HTREEI[BTYPE_I]
calcolare la lunghezza di inserimento, ILEN, e la lunghezza di copia, CLEN
ciclo per ILEN
if BLEN_L è zero
leggere il tipo di blocco usando HTREE_BTYPE_L e impostare BTYPE_L
salvare il tipo di blocco precedente
leggere il conteggio di blocchi usando HTREE_BLEN_L e impostare BLEN_L
decrementare BLEN_L
cercare il modo di contesto CMODE[BTYPE_L]
calcolare l'ID di contesto, CIDL dagli ultimi due byte non compressi
leggere il letterale usando HTREEL[CMAPL[64*BTYPE_L + CIDL]]
scrivere il letterale nel flusso non compresso
if il numero di byte non compressi prodotti nel ciclo per questo
meta-blocco è MLEN, allora uscire dal ciclo (in questo caso la
lunghezza di copia è ignorata e può avere qualsiasi valore)
if il codice di distanza è uno zero implicito dal codice inserimento-copia
impostare la distanza all'indietro all'ultima distanza
else
if BLEN_D è zero
leggere il tipo di blocco usando HTREE_BTYPE_D e impostare BTYPE_D
salvare il tipo di blocco precedente
leggere il conteggio di blocchi usando HTREE_BLEN_D e impostare BLEN_D
decrementare BLEN_D
calcolare l'ID di contesto, CIDD da CLEN
leggere il codice di distanza usando HTREED[CMAPD[4*BTYPE_D + CIDD]]
calcolare la distanza per sostituzione di codice corto di distanza
if il codice di distanza non è zero,
e la distanza non è un riferimento al dizionario statico,
spingere la distanza nel buffer circolare delle ultime distanze
if la distanza è inferiore alla distanza massima consentita più uno
spostarsi all'indietro di distanza byte nei dati non compressi,
e copiare CLEN byte da questa posizione nel
flusso non compresso
else
cercare la parola del dizionario statico, trasformare la parola come
indicato e copiare il risultato nel flusso non compresso
while numero di byte non compressi per questo meta-blocco < MLEN
while not ISLAST
Se il flusso termina prima del completamento dell'ultimo meta-blocco, allora il flusso dovrebbe essere rifiutato come non valido.
Si noti che un riferimento di stringa duplicata può fare riferimento a una stringa in un meta-blocco precedente, cioè la distanza all'indietro può attraversare uno o più confini di meta-blocchi. Tuttavia, una distanza di copia all'indietro non farà riferimento oltre l'inizio del flusso non compresso o la dimensione della finestra; qualsiasi distanza di questo tipo è interpretata come un riferimento a una parola del dizionario statico. Si noti inoltre che la stringa referenziata può sovrapporsi alla posizione corrente, ad esempio, se gli ultimi 2 byte decodificati hanno valori X e Y, un riferimento di stringa con <length = 5, distance = 2> aggiunge X,Y,X,Y,X al flusso non compresso.
Fonte (Source): RFC 7932, Section 10
Testo ufficiale (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt