compress/flate: fix Huffman tree bug

compress/flate: fix Huffman tree bug
Incorporate refactoring and a regression test from http://codereview.appspot.com/4538090/

[Ivan Krasin, 2011-05-25 23:06:49]

This fix has been tested with zlib:

krasin@li139-230:~$ cat t.go
package main

import (
       "compress/zlib"
       "os"
)

func main() {
     content := []byte("test a reasonable sized string that can be compressed")
     w, _ := zlib.NewWriter(os.Stdout)
     w.Write(content)
     w.Close()
}

krasin@li139-230:~$ 6g t.go && 6l -o t t.6
krasin@li139-230:~$ ./t > out3
krasin@li139-230:~$ python
Python 2.6.6 (r266:84292, Sep 15 2010, 16:22:56) 
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import zlib
>>> f = open('out3')
>>> zlib.decompress(f.read())
'test a reasonable sized string that can be compressed'
>>> 
krasin@li139-230:~$ 

The funny thing is that we have a bug inside inflate.go that does not access an
empty offset code table. I will try to produce the example in a minute. After
that I will need to fix the bug in the inflater too.

Ivan

[aam, 2011-05-25 23:11:37]

> The funny thing is that we have a bug inside inflate.go that does not
> access an empty offset code table.

is this the same thing we were commenting out earlier to get inflate
to work (before the whole deflate bug appeared)? see line 98 in
inflate.go.

[rsc, 2011-05-25 23:17:18]

> The funny thing is that we have a bug inside inflate.go that does not
> access an empty offset code table. I will try to produce the example in
> a minute. After that I will need to fix the bug in the inflater too.

While I believe it could be, I will want to see a binary input
that zlib handles and the inflater does not.

[Ivan Krasin, 2011-05-25 23:26:13]

On 2011/05/25 23:17:18, rsc wrote:
> > The funny thing is that we have a bug inside inflate.go that does not
> > access an empty offset code table. I will try to produce the example in
> > a minute. After that I will need to fix the bug in the inflater too.
> 
> While I believe it could be, I will want to see a binary input
> that zlib handles and the inflater does not.

I have uploaded a fix and I will provide a binary input in a minute.

[Ivan Krasin, 2011-05-26 00:04:41]

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

The input file is:

78 9C 04 40  D1 0D 84 20  14 5B A5 AB  15 68 EE 48  F4 61 5E FB  E5 F4 26 72  40
B4 E8 53  1C 97 E0 FD  6A C1 E9 5D  3F E4 CF 60  B2 30 84 79  EE A7 65 6B  7D 01
00 00  FF FF 15 7F  13 D3

I have given a hex just for the inline reference, but it's supposed that you'll
use the attach from http://code.google.com/p/go/issues/detail?id=1833

[Ivan Krasin, 2011-05-26 00:11:19]

I've used this Go program to check:

package main

import (
       "compress/zlib"
       "log"
       "fmt"
       "os"
)

func main() {
     r, _ := zlib.NewReader(os.Stdin)
     content := make([]byte, 100)
     n, err := r.Read(content)
     if err != nil {
     	log.Fatal(err)
     }
     fmt.Printf("%s\n", string(content[0:n]))
}

krasin@li139-230:~$ 6g v.go && 6l -o v v.6
krasin@li139-230:~$ ./v < out3
2011/05/26 00:10:39 flate: corrupt input before offset 21

[Ivan Krasin, 2011-05-26 00:12:41]

If the fix is applied,

krasin@li139-230:~$ ./v < out3
test a reasonable sized string that can be compressed

[Ivan Krasin, 2011-05-26 00:14:32]

On 2011/05/25 23:11:37, aam wrote:
> > The funny thing is that we have a bug inside inflate.go that does not
> > access an empty offset code table.
> 
> is this the same thing we were commenting out earlier to get inflate
> to work (before the whole deflate bug appeared)? see line 98 in
> inflate.go.
No (sorry, missed this reply)

[rsc, 2011-05-26 02:24:06]

please change CL description to

compress/flate: fix Huffman tree bug

http://codereview.appspot.com/4524070/diff/7001/src/pkg/compress/flate/inflat...
File src/pkg/compress/flate/inflate.go (right):

http://codereview.appspot.com/4524070/diff/7001/src/pkg/compress/flate/inflat...
src/pkg/compress/flate/inflate.go:80: // TODO(rsc): Return false sometimes.
please delete

http://codereview.appspot.com/4524070/diff/7001/src/pkg/compress/flate/inflat...
src/pkg/compress/flate/inflate.go:81: if len(bits) == 1 && bits[0] == 0 {
please insert a comment above this line saying
where in the RFC it says to do this.
i skimmed it last night and came up empty

[peterGo, 2011-05-26 02:56:43]

I ran a test with this CL and it seemed to solve this bug too.

weird problem: flate: corrupt input before offset 14, when loading very specific
images
http://groups.google.com/group/golang-nuts/browse_thread/thread/ea07ee6e7c33f181

Peter

[imkrasin, 2011-05-26 04:41:23]

http://codereview.appspot.com/4524070/diff/7001/src/pkg/compress/flate/inflat...
File src/pkg/compress/flate/inflate.go (right):

http://codereview.appspot.com/4524070/diff/7001/src/pkg/compress/flate/inflat...
src/pkg/compress/flate/inflate.go:80: // TODO(rsc): Return false sometimes.
On 2011/05/26 02:24:06, rsc wrote:
> please delete

Done.

http://codereview.appspot.com/4524070/diff/7001/src/pkg/compress/flate/inflat...
src/pkg/compress/flate/inflate.go:81: if len(bits) == 1 && bits[0] == 0 {
On 2011/05/26 02:24:06, rsc wrote:
> please insert a comment above this line saying
> where in the RFC it says to do this.
> i skimmed it last night and came up empty
I have spent some time trying to find the definition of "null" empty tree for
offsets and haven't found anything.

I believe that zlib is "defensive" against not fully-compliant encoders (like
I've written). I have removed this defensive code and now I encode a fake
huffman tree for offsets if there's no matches found (see the changes in
huffman_bit_writer.go)

[rsc, 2011-05-26 13:18:25]

LGTM

Thanks for working through this.

[aam, 2011-05-26 14:17:01]

my randomized tests completed without errors (2 000 000
compress/decompress cycles)

thanks!

On Thu, May 26, 2011 at 7:18 AM,  <rsc@golang.org> wrote:
> LGTM
>
> Thanks for working through this.
>
>
> http://codereview.appspot.com/4524070/
>

[imkrasin, 2011-05-26 20:59:13]

On 2011/05/26 13:18:25, rsc wrote:
> LGTM
> 
> Thanks for working through this.

Russ,

I'm not a committer. Could you please submit this patch?

Thanks,
Ivan

[rsc, 2011-05-26 21:01:58]

Will do, sorry for the delay.

[rsc, 2011-05-26 21:02:16]

*** Submitted as http://code.google.com/p/go/source/detail?r=0f0d1ba9a292 ***

compress/flate: fix Huffman tree bug
Incorporate refactoring and a regression test from
http://codereview.appspot.com/4538090/

R=rsc, go.peter.90, imkrasin
CC=golang-dev, mirtchovski
http://codereview.appspot.com/4524070

Committer: Russ Cox <rsc@golang.org>