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