Skip to main content

10. Decoding Algorithm

  1. Decoding Algorithm

The decoding algorithm that produces the uncompressed data is as follows:

read window size do read ISLAST bit if ISLAST read ISLASTEMPTY bit if ISLASTEMPTY break from loop read MNIBBLES if MNIBBLES is zero verify reserved bit is zero read MSKIPLEN skip any bits up to the next byte boundary skip MSKIPLEN bytes continue to the next meta-block else read MLEN if not ISLAST read ISUNCOMPRESSED bit if ISUNCOMPRESSED skip any bits up to the next byte boundary copy MLEN bytes of compressed data as literals continue to the next meta-block

loop for each three block categories (i = L, I, D) read NBLTYPESi if NBLTYPESi >= 2 read prefix code for block types, HTREE_BTYPE_i read prefix code for block counts, HTREE_BLEN_i read block count, BLEN_i set block type, BTYPE_i to 0 initialize second-to-last and last block types to 0 and 1 else set block type, BTYPE_i to 0 set block count, BLEN_i to 16777216 read NPOSTFIX and NDIRECT read array of literal context modes, CMODE[] read NTREESL if NTREESL >= 2 read literal context map, CMAPL[] else fill CMAPL[] with zeros read NTREESD if NTREESD >= 2 read distance context map, CMAPD[] else fill CMAPD[] with zeros read array of literal prefix codes, HTREEL[] read array of insert-and-copy length prefix codes, HTREEI[] read array of distance prefix codes, HTREED[] do if BLEN_I is zero read block type using HTREE_BTYPE_I and set BTYPE_I save previous block type read block count using HTREE_BLEN_I and set BLEN_I decrement BLEN_I read insert-and-copy length symbol using HTREEI[BTYPE_I] compute insert length, ILEN, and copy length, CLEN loop for ILEN if BLEN_L is zero read block type using HTREE_BTYPE_L and set BTYPE_L save previous block type read block count using HTREE_BLEN_L and set BLEN_L decrement BLEN_L look up context mode CMODE[BTYPE_L] compute context ID, CIDL from last two uncompressed bytes read literal using HTREEL[CMAPL[64*BTYPE_L + CIDL]] write literal to uncompressed stream if number of uncompressed bytes produced in the loop for this meta-block is MLEN, then break from loop (in this case the copy length is ignored and can have any value)

if distance code is implicit zero from insert-and-copy code set backward distance to the last distance else if BLEN_D is zero read block type using HTREE_BTYPE_D and set BTYPE_D save previous block type read block count using HTREE_BLEN_D and set BLEN_D decrement BLEN_D compute context ID, CIDD from CLEN read distance code using HTREED[CMAPD[4*BTYPE_D + CIDD]] compute distance by distance short code substitution if distance code is not zero, and distance is not a static dictionary reference, push distance to the ring buffer of last distances if distance is less than the max allowed distance plus one move backwards distance bytes in the uncompressed data, and copy CLEN bytes from this position to the uncompressed stream else look up the static dictionary word, transform the word as directed, and copy the result to the uncompressed stream while number of uncompressed bytes for this meta-block < MLEN while not ISLAST

If the stream ends before the completion of the last meta-block, then the stream should be rejected as invalid.

Note that a duplicated string reference may refer to a string in a previous meta-block, i.e., the backward distance may cross one or more meta-block boundaries. However, a backward copy distance will not refer past the beginning of the uncompressed stream or the window size; any such distance is interpreted as a reference to a static dictionary word. Also, note that the referenced string may overlap the current position, for example, if the last 2 bytes decoded have values X and Y, a string reference with <length = 5, distance = 2> adds X,Y,X,Y,X to the uncompressed stream.

Source: RFC 7932 Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt

Last updated on