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