[Zlib-devel] stored-block size limit?

[Mark Adler]

On Sunday, March 31, 2002, at 05:50  PM, Greg Roelofs wrote:
> Any chance 1.1.5 will lift the artificial 32 KB limit on stored-block 
> size?

Actually, I will take this opportunity to report, on our nifty new 
mailing list, a bug/feature of deflate with respect to stored blocks and 
the maximum expansion factor.

The zlib technical details page claims that deflation adds at most five 
bytes per 32K.  zlib.h claims that you can deflate in a single step if 
you provide 0.1% more output space than the input, plus 12 bytes.  Both 
are wrong.  This is the reality:

1.  If windowBits is greater than or equal to memLevel + 6, then the 
stored block size is approximately 2^(memLevel + 6).  Therefore if 
memLevel is 9 and windowBits is 15 (the maximum settings), the 32K claim 
is correct.  However for the default settings with a memLevel of 8 and 
windowBits of 15, zlib will add five bytes for every 16K or so.  
Furthermore, once you get down to a memLevel of 6, the 0.1% is incorrect 
as well.  In that case, you need 0.13% more output space.  And it gets 
worse as memLevel continues from 5 down to 1.  At a memLevel of 1, you 
need 4% more output space.

So zlib.h is wrong for memLevel <= 6.  Furthermore, 32K stored blocks 
are not created even for the default deflate settings.

2. If windowBits is less than memLevel + 6, then deflate appears to 
refuse to use stored blocks at all!  In this case, the expansion can be 
much more significant.  Empirically, the expansion factor for these 
cases is approximately equal to 2^(13 - memLevel) / 100 in %.  I.e for a 
memLevel of 9, the expansion is approximately 0.16%.  For a memLevel of 
4 (the lowest memLevel of this case for windowBits >= 9), the expansion 
is 5.12%.  For all of these cases, the expansion factor is greater than 
0.1%.  Also I do not know if these observed expansion factors are upper 
bounds.  Someone would have to analyze the maximum expansion factor of 
properly constructed dynamic blocks with each specified number of 
literal/length codes to figure that out.

So in addition, zlib.h is wrong for windowBits < memLevel + 6.

At a minimum, these behaviors of deflate need to be documented.  In my 
opinion, at least case #2 above could be considered a bug, since deflate 
should be using stored blocks for incompressible data.

New feature request: as a courtesy to users of compress() and 
single-step deflate(), as well as to avoid confusion on this topic, zlib 
should provide a function that returns the maximum compressed size given 
the uncompressed size.  It appears empirically that 6.25% plus 11 bytes 
(i.e. size + (size >> 4) + 11) is safe in all cases.  However that would 
need to be verified somehow for case #2.

mark