compress/flate: deflatefast does not deliver consistent results after reset

[tbushnell]

in compress/flate/deflatefast.go:

Omitting here the reasons why stableflate does what it does, and focusing just on the one bad effect:

deflatefast.go maintains a counter "cur" in the object. When cur advances past 1<<30, resetAll is called, which discards the current match table. Discarding the match table changes the behavior of further compression at that point, of course.

Normal reset of the object calls reset, which advances cur by 1<<15 (and then is one of the places that checks if it's now past 1<<30, but this is not important here).

If the same object is repeatedly used for compression runs, with a reset in between, then two different objects, with different histories, but both reset, will have different values for cur. This in turn means there is a different run distance before the match table is discarded, and therefore, potentially different compression behavior even with identical input.

O(32K) (1<<30 / 1<<15) resets is sufficient to produce the problem, which is not absurd for a high-volume server.

[dsnet]

\cc @klauspost as this issue probably affects your fork as well.

[tbushnell]

I have a change to the existing tests which will expose the bug, but I'm working on making it flexible instead of based on knowing the exact current implementation. Also getting a fix ready to suggest.

[klauspost]

Thanks for the ping!

I am about to replace it with code that shifts down the table instead of clearing it. That should make it transparent.

Let me see if I can cook up a PR with similar functionality.

[klauspost]

PR added.

[gopherbot]

Change https://golang.org/cl/193605 mentions this issue: compress/flate: fix deflate Reset consistency

[tbushnell]

My concern with shifting down the table is that it makes compression slower. If we had Reset clear the table entirely, then compression remains as fast as it does now. Reset doesn't need to be super fast IMO.

However, I have no objection to this style of fix if it's what you prefer.

[rsc]

Received a report of this problem from a Go 1.15 beta 1 tester.
I wrote a test and tried the pending CL 193605, but it didn't fix my test.
I will see if I can find a simple fix for Go 1.15.

[rsc]

Not completely fixed. There is another.

[gopherbot]

Change https://golang.org/cl/243140 mentions this issue: compress/flate: fix another deflate Reset inconsistency