2.4.4 Processing

This section provides the decompression method corresponding to the compression method that is described in section 2.3. The basic structure is to decode each flag, which indicates whether the next item is a literal or a match. Literals are copied directly from the input buffer to the output buffer. Matches are decoded into a (length, offset) pair that is used to copy data from earlier in the output buffer. If the code that follows reads or writes outside the provided buffers at any time, an implementation MUST return an error indicating that the compressed buffer is invalid. Note that the match-copying loop copies 1 byte at a time and cannot use the standard library functions memcpy or memmove. A sequence of bytes such as aaaaaa can be encoded as follows:

 [literal: "a"][match: offset=1, length=5]

The match length can be greater than the match offset, and this necessitates the 1-byte-at-a-time copying strategy shown in the following pseudocode.

 BufferedFlags = 0
 BufferedFlagCount = 0
 InputPosition = 0
 OutputPosition = 0
 LastLengthHalfByte = 0
 Loop until break instruction or error
     If BufferedFlagCount == 0
         BufferedFlags = read 4 bytes at InputPosition
         InputPosition += 4
         BufferedFlagCount = 32
     BufferedFlagCount = BufferedFlagCount – 1
     If (BufferedFlags & (1 << BufferedFlagCount)) == 0
         Copy 1 byte from InputPosition to OutputPosition.  Advance both.
     Else
         If InputPosition == InputBufferSize
             Decompression is complete.  Return with success.
         MatchBytes = read 2 bytes from InputPosition
         InputPosition += 2
         MatchLength = MatchBytes mod 8
         MatchOffset = (MatchBytes / 8) + 1
         If MatchLength == 7
             If LastLengthHalfByte == 0
                 MatchLength = read 1 byte from InputPosition
                 MatchLength = MatchLength mod 16
                 LastLengthHalfByte = InputPosition
                 InputPosition += 1
             Else
                 MatchLength = read 1 byte from LastLengthHalfByte position
                 MatchLength = MatchLength / 16
                 LastLengthHalfByte = 0
             If MatchLength == 15
                 MatchLength = read 1 byte from InputPosition
                 InputPosition += 1
                 If MatchLength == 255
                     MatchLength = read 2 bytes from InputPosition
                     InputPosition += 2
                     If MatchLength == 0
                         MatchLength = read 4 bytes from InputPosition
                         InputPosition += 4 bytes
                     If MatchLength < 15 + 7
                        Return error.
                     MatchLength -= (15 + 7)
                 MatchLength += 15
             MatchLength += 7
         MatchLength += 3
         For i = 0 to MatchLength – 1
             Copy 1 byte from OutputBuffer[OutputPosition – MatchOffset]
             OutputPosition += 1