code review 4538090: compress/flate: fix + test encoder error

compress/flate: fix + test encoder error

Fixes issue 1833.  Discussion there.
The new behavior is consistent with zlib.

[rsc, 2011-05-24 17:04:59]

Hello mirtchovski@gmail.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg

[aam, 2011-05-24 17:15:49]

http://codereview.appspot.com/4538090/diff/4002/src/pkg/compress/flate/huffma...
File src/pkg/compress/flate/huffman_bit_writer.go (right):

http://codereview.appspot.com/4538090/diff/4002/src/pkg/compress/flate/huffma...
src/pkg/compress/flate/huffman_bit_writer.go:397: for numOffsets > 1 &&
w.offsetFreq[numOffsets-1] == 0 {
this code assumes that at least the first offset is provided, which isn't always
true. wouldn't it be better if the check here was for numOffsets >= 1? in which
case line 465 can be changed to numOffsets == 0, reflecting the true state of
affairs?

the fix works in both cases.

[rsc, 2011-05-25 04:30:19]

Hello mirtchovski@gmail.com (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-05-25 04:32:48]

I cleaned up the code a little.
It is unclear to me why you don't have to check that
not all the codegenFreq are zero either, but this is at
least a concrete step in the right direction.
I also pulled out some code marked as an
extension to RFC 1951 that the inflater knew
nothing about.

[aam, 2011-05-25 04:46:09]

LGTM. this is fairly specific code though, so you may want to get a second
opinion if there's anyone who can offer it. I still don't feel comfortable
inside that function.

I will re-run my test of 2,000,000 random 16-byte inputs tomorrow. that
generated 40k of broken encodes last time.

[rsc, 2011-05-25 05:00:03]

+krasin

[imkrasin, 2011-05-25 05:54:09]

On 2011/05/25 05:00:03, rsc wrote:
> +krasin

Thanks, I've started looking into this.

[imkrasin, 2011-05-25 06:19:08]

http://codereview.appspot.com/4538090/diff/6002/src/pkg/compress/flate/huffma...
File src/pkg/compress/flate/huffman_bit_writer.go (right):

http://codereview.appspot.com/4538090/diff/6002/src/pkg/compress/flate/huffma...
src/pkg/compress/flate/huffman_bit_writer.go:388: for numOffsets > 0 &&
w.offsetFreq[numOffsets-1] == 0 {
This is the actual fix, not the other stuff, right?
I have not yet recall the whole code (so, I don't currently understand why we
need to compare with zero here, not with one), but all other changes don't
affect "small" chunks. Basically, it's a nice refactoring (thanks, Russ) and
getting rid of the "extended" version of deflate which applies to "large"
chunks. Please, correct me, if I'm wrong.

Regarding to the CL: I would like to take a look at it morning and understand
this change. If you have an explanation why it's right, feel free to put it
here.

Ivan

[aam, 2011-05-25 06:28:33]

> This is the actual fix, not the other stuff, right?

yes,

the issue discussing the bug is
http://code.google.com/p/go/issues/detail?id=1833

It appears that for some small inputs an encoding will be generated
that has no matchType tokens but was attempted to be written out using
a dynamic table.

hope that helps.

[rsc, 2011-05-25 11:25:47]

> This is the actual fix, not the other stuff, right?
> I have not yet recall the whole code (so, I don't currently understand
> why we need to compare with zero here, not with one), but all other
> changes don't affect "small" chunks. Basically, it's a nice refactoring
> (thanks, Russ) and getting rid of the "extended" version of deflate
> which applies to "large" chunks. Please, correct me, if I'm wrong.

Sounds right to me.
As Andrey says, the issue tracker has more.

[imkrasin, 2011-05-25 18:53:50]

I'm still looking into this. I hope to finish my investigations before
the end of the day. Sorry for being a slowpoke.

On Wed, May 25, 2011 at 4:25 AM, Russ Cox <rsc@golang.org> wrote:
>> This is the actual fix, not the other stuff, right?
>> I have not yet recall the whole code (so, I don't currently understand
>> why we need to compare with zero here, not with one), but all other
>> changes don't affect "small" chunks. Basically, it's a nice refactoring
>> (thanks, Russ) and getting rid of the "extended" version of deflate
>> which applies to "large" chunks. Please, correct me, if I'm wrong.
>
> Sounds right to me.
> As Andrey says, the issue tracker has more.
>

[imkrasin, 2011-05-25 22:41:30]

Ok. The actual bug was inside sortByFreq. I've just checked that my
fix works with zlib:

>>> zlib.decompress(f.read())
'test a reasonable sized string that can be compressed'

I will send the CL soon. It will incorporate all the improvements made
in this CL, but will not include disabling dynamic encoding in case if
we have literal tokens only (i.e. the string does not have
repetitions)

Ivan

On Wed, May 25, 2011 at 11:53 AM, Ivan Krasin <imkrasin@gmail.com> wrote:
> I'm still looking into this. I hope to finish my investigations before
> the end of the day. Sorry for being a slowpoke.
>
> On Wed, May 25, 2011 at 4:25 AM, Russ Cox <rsc@golang.org> wrote:
>>> This is the actual fix, not the other stuff, right?
>>> I have not yet recall the whole code (so, I don't currently understand
>>> why we need to compare with zero here, not with one), but all other
>>> changes don't affect "small" chunks. Basically, it's a nice refactoring
>>> (thanks, Russ) and getting rid of the "extended" version of deflate
>>> which applies to "large" chunks. Please, correct me, if I'm wrong.
>>
>> Sounds right to me.
>> As Andrey says, the issue tracker has more.
>>
>

[rsc, 2011-05-27 04:25:27]

*** Abandoned ***