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