ZLIB Spec Correction Proposal

For CM = 8, CINFO is the base-2 logarithm of the LZ77 window size, minus eight (CINFO=7 indicates a 32K window size). Values of CINFO above 7 are not allowed in this version of the specification.  CINFO is not defined in this specification for CM not equal to 8.

For the reasons presented below, this text should be changed to:

For CM = 8, CINFO is an upper bound of the base-2 logarithm of the biggest distance code, minus eight. CINFO = 7 indicates that the distance codes can be at most 32768, and values of CINFO above 7 are not allowed in this version of the specification.  CINFO is not defined in this specification for CM not equal to 8.

Also, in Section 2.3. Compliance, the following text should be added:
A compliant compressor must not output distance codes bigger than 2^(CINFO+8).
...
A compliant decompressor must give an error indication if it detects distance codes bigger than 2^(CINFO+8) in the compressed stream.

The term "the LZ77 window size" is defined by the LZ77 algorithm, but there are some unadressed issues, such as whether to allow matches longer than the window size, or whether to allow matches in the immediate neighborhood of the window margins. These issues are defined by applications, based mainly on the compression ratio vs. execution speed tradeoff. ZLIB is an LZ77 application, but it doesn't specifically define these issues. This may cause unwanted events, such as the events presented here.

- The following encoder optimizations should be correct, but they are not allowed by the current wording of the ZLIB spec:

• Correct Optimization #1:
  If a (non-streamable) encoder with a 32K window detects that its output is identical to the output of any valid encoder with a 2K window (because distance codes bigger than 2K do not occur), CINFO can be optimized from 7 to 3. For this reason, this patch can be applied to the zlib/libz (reference library version 1.1.3) to fix the 256-byte window bug.
• Correct Optimization #2:
  There may be reasons for encoders to employ windows of sizes other than 256, 512, 1K, 2K, 4K, 8K, 16K, 32K. For example, the proposed Z_RLE strategy uses a window of size 1, but encoder implementors may be confused about the value of CINFO: -8 (incorrect because no negative values are allowed?), or 0 (incorrect because 2^(CINFO+8) != 1 ?), or a window of size 1 is merely disallowed? In fact, windows of size 1 should be allowed, and CINFO should be 0 in this case (any other values are also valid, but sub-optimal). This cannot be inferred from the current spec. Interpretation problems also occur when the window size is not a power of two, because CINFO must be an integer in the range 0..7: it can be misinterpreted that such window sizes are disallowed.

• Incorrect Optimization #1:
  Since it is not stated, nor can it be inferred that the window size does not restrict the match lengths, decoder implementors might assume the contrary and optimize the decoders thinking that 257- and 258-byte matches will not appear in 256-byte windows. Such decoders will have unpredicted behavior, which may yield an incorrectly decoded (altered) stream, and/or a system crash.
• Incorrect Optimization #2:
  The term the LZ77 sliding window does not assure that the distance codes can go exactly up to the size of this window. In general, LZ77 applications might decide to have a faster algorithm that keeps the entire match in the window, and this might imply match_length + match_distance <= window_size. In spite that the ZLIB reference library implements the encoder in this fashion, the ZLIB specification does not impose this restriction, so the relation does not hold for ZLIB encoders in general. However, decoder implementors might assume the contrary and optimize the decoders thinking that match_distance <= window_size - 3 (for example, perform double-byte or quad-byte memory copying that is unsafe when window_size - match_distance < 3). This could again yield at least to altered output.