2.7 Decoding Matches and Literals (Aligned and Verbatim Blocks)

Decoding is performed by first decoding an element from the main tree and then, if the item is a match, determining which additional components are required to decode to reconstruct the match. The following is a pseudocode example of decoding a match or an uncompressed character.

     main_element = main_tree.decode_element()
    
     /* Check if it is a literal character. */
     if (main_element < 256 ) 
    
        /* It is a literal, so copy the literal to output. */
        window[ curpos ] ← (byte) main_element 
        curpos ← curpos + 1
    
     /* Decode the match. For a match, there are two components, offset and length. */
     else 
    
        length_header ← (main_element – 256) & 7
    
        /* Length of the footer. */
        if (length_header == 7) 
           match_length ← length_tree.decode_element() + 7 + 2
        else
           /* no length footer */
           match_length ← length_header + 2 
        endif
        
        /* Decoding a match length (if a match length < 257). */
        position_slot ← (main_element – 256) >> 3
    
        /* Check for repeated offsets (positions 0,1,2). */
        if (position_slot == 0)
           match_offset ← R0
        else if (position_slot == 1)
           match_offset ← R1
           swap(R0 ↔ R1)
        else if (position_slot == 2)
           match_offset ← R2
           swap(R0 ↔ R2)
        /* Not a repeated offset. */
        else 
           offset_bits ← footer_bits[ position_slot ]
    
           if (block_type == aligned_offset_block)
              /* This means there are some aligned bits. */
              if (offset_bits > 3) 
                 verbatim_bits ← (readbits(offset_bits-3)) << 3
                 aligned_bits  ← aligned_offset_tree.decode_element();
              else 
                 /* 0, 1, or 2 verbatim bits */ 
                 verbatim_bits ← readbits(offset_bits)
                 aligned_bits  ← 0
              endif
              
              formatted_offset ← base_position[ position_slot ]
                               + verbatim_bits + aligned_bits
          
          else 
             /* Block_type is a verbatim_block. */
              verbatim_bits ← readbits(offset_bits)
              formatted_offset ← base_position[ position_slot ] + verbatim_bits
           endif
    
           /* Decoding a match offset. */
           match_offset ← formatted_offset – 2
    
           /* Update repeated offset least recently used queue. */
           R2 ← R1
           R1 ← R0
           R0 ← match_offset
    
       endif
    
       /* Check for extra length. */
    
       if (match_length == 257)
          if (readbits( 1 ) != 0)
             if (readbits( 1 ) != 0)
                if (readbits( 1 ) != 0)
                   extra_len = readbits( 15 )
                else
                   extra_len = readbits( 12 ) + 1024 + 256
                endif
             else
                extra_len = readbits( 10 ) + 256
             endif
          else
             extra_len = readbits( 8 )
          endif
    
          /* Get the match length (if match length >= 257). */
          match_length ← 257 + extra_len
    
       endif
    
       /* Get match length and offset. Perform copy and paste work. */
       for (i = 0; i < match_length; i++)
          window[curpos + i] ← window[curpos + i – match_offset]
       endfor
    
       curpos ← curpos + match_length
  
     endif