libgo/go/compress/flate/deflate_test.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package flate
   6
   7 import (
   8         "bytes"
   9         "fmt"
  10         "io"
  11         "io/ioutil"
  12         "sync"
  13         "testing"
  14 )
  15
  16 type deflateTest struct {
  17         in    []byte
  18         level int
  19         out   []byte
  20 }
  21
  22 type deflateInflateTest struct {
  23         in []byte
  24 }
  25
  26 type reverseBitsTest struct {
  27         in       uint16
  28         bitCount uint8
  29         out      uint16
  30 }
  31
  32 var deflateTests = []*deflateTest{
  33         {[]byte{}, 0, []byte{1, 0, 0, 255, 255}},
  34         {[]byte{0x11}, -1, []byte{18, 4, 4, 0, 0, 255, 255}},
  35         {[]byte{0x11}, DefaultCompression, []byte{18, 4, 4, 0, 0, 255, 255}},
  36         {[]byte{0x11}, 4, []byte{18, 4, 4, 0, 0, 255, 255}},
  37
  38         {[]byte{0x11}, 0, []byte{0, 1, 0, 254, 255, 17, 1, 0, 0, 255, 255}},
  39         {[]byte{0x11, 0x12}, 0, []byte{0, 2, 0, 253, 255, 17, 18, 1, 0, 0, 255, 255}},
  40         {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 0,
  41                 []byte{0, 8, 0, 247, 255, 17, 17, 17, 17, 17, 17, 17, 17, 1, 0, 0, 255, 255},
  42         },
  43         {[]byte{}, 1, []byte{1, 0, 0, 255, 255}},
  44         {[]byte{0x11}, 1, []byte{18, 4, 4, 0, 0, 255, 255}},
  45         {[]byte{0x11, 0x12}, 1, []byte{18, 20, 2, 4, 0, 0, 255, 255}},
  46         {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 1, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}},
  47         {[]byte{}, 9, []byte{1, 0, 0, 255, 255}},
  48         {[]byte{0x11}, 9, []byte{18, 4, 4, 0, 0, 255, 255}},
  49         {[]byte{0x11, 0x12}, 9, []byte{18, 20, 2, 4, 0, 0, 255, 255}},
  50         {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 9, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}},
  51 }
  52
  53 var deflateInflateTests = []*deflateInflateTest{
  54         {[]byte{}},
  55         {[]byte{0x11}},
  56         {[]byte{0x11, 0x12}},
  57         {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}},
  58         {[]byte{0x11, 0x10, 0x13, 0x41, 0x21, 0x21, 0x41, 0x13, 0x87, 0x78, 0x13}},
  59         {largeDataChunk()},
  60 }
  61
  62 var reverseBitsTests = []*reverseBitsTest{
  63         {1, 1, 1},
  64         {1, 2, 2},
  65         {1, 3, 4},
  66         {1, 4, 8},
  67         {1, 5, 16},
  68         {17, 5, 17},
  69         {257, 9, 257},
  70         {29, 5, 23},
  71 }
  72
  73 func largeDataChunk() []byte {
  74         result := make([]byte, 100000)
  75         for i := range result {
  76                 result[i] = byte(i * i & 0xFF)
  77         }
  78         return result
  79 }
  80
  81 func TestDeflate(t *testing.T) {
  82         for _, h := range deflateTests {
  83                 var buf bytes.Buffer
  84                 w := NewWriter(&buf, h.level)
  85                 w.Write(h.in)
  86                 w.Close()
  87                 if !bytes.Equal(buf.Bytes(), h.out) {
  88                         t.Errorf("Deflate(%d, %x) = %x, want %x", h.level, h.in, buf.Bytes(), h.out)
  89                 }
  90         }
  91 }
  92
  93 type syncBuffer struct {
  94         buf    bytes.Buffer
  95         mu     sync.RWMutex
  96         closed bool
  97         ready  chan bool
  98 }
  99
 100 func newSyncBuffer() *syncBuffer {
 101         return &syncBuffer{ready: make(chan bool, 1)}
 102 }
 103
 104 func (b *syncBuffer) Read(p []byte) (n int, err error) {
 105         for {
 106                 b.mu.RLock()
 107                 n, err = b.buf.Read(p)
 108                 b.mu.RUnlock()
 109                 if n > 0 || b.closed {
 110                         return
 111                 }
 112                 <-b.ready
 113         }
 114         panic("unreachable")
 115 }
 116
 117 func (b *syncBuffer) signal() {
 118         select {
 119         case b.ready <- true:
 120         default:
 121         }
 122 }
 123
 124 func (b *syncBuffer) Write(p []byte) (n int, err error) {
 125         n, err = b.buf.Write(p)
 126         b.signal()
 127         return
 128 }
 129
 130 func (b *syncBuffer) WriteMode() {
 131         b.mu.Lock()
 132 }
 133
 134 func (b *syncBuffer) ReadMode() {
 135         b.mu.Unlock()
 136         b.signal()
 137 }
 138
 139 func (b *syncBuffer) Close() error {
 140         b.closed = true
 141         b.signal()
 142         return nil
 143 }
 144
 145 func testSync(t *testing.T, level int, input []byte, name string) {
 146         if len(input) == 0 {
 147                 return
 148         }
 149
 150         t.Logf("--testSync %d, %d, %s", level, len(input), name)
 151         buf := newSyncBuffer()
 152         buf1 := new(bytes.Buffer)
 153         buf.WriteMode()
 154         w := NewWriter(io.MultiWriter(buf, buf1), level)
 155         r := NewReader(buf)
 156
 157         // Write half the input and read back.
 158         for i := 0; i < 2; i++ {
 159                 var lo, hi int
 160                 if i == 0 {
 161                         lo, hi = 0, (len(input)+1)/2
 162                 } else {
 163                         lo, hi = (len(input)+1)/2, len(input)
 164                 }
 165                 t.Logf("#%d: write %d-%d", i, lo, hi)
 166                 if _, err := w.Write(input[lo:hi]); err != nil {
 167                         t.Errorf("testSync: write: %v", err)
 168                         return
 169                 }
 170                 if i == 0 {
 171                         if err := w.Flush(); err != nil {
 172                                 t.Errorf("testSync: flush: %v", err)
 173                                 return
 174                         }
 175                 } else {
 176                         if err := w.Close(); err != nil {
 177                                 t.Errorf("testSync: close: %v", err)
 178                         }
 179                 }
 180                 buf.ReadMode()
 181                 out := make([]byte, hi-lo+1)
 182                 m, err := io.ReadAtLeast(r, out, hi-lo)
 183                 t.Logf("#%d: read %d", i, m)
 184                 if m != hi-lo || err != nil {
 185                         t.Errorf("testSync/%d (%d, %d, %s): read %d: %d, %v (%d left)", i, level, len(input), name, hi-lo, m, err, buf.buf.Len())
 186                         return
 187                 }
 188                 if !bytes.Equal(input[lo:hi], out[:hi-lo]) {
 189                         t.Errorf("testSync/%d: read wrong bytes: %x vs %x", i, input[lo:hi], out[:hi-lo])
 190                         return
 191                 }
 192                 // This test originally checked that after reading
 193                 // the first half of the input, there was nothing left
 194                 // in the read buffer (buf.buf.Len() != 0) but that is
 195                 // not necessarily the case: the write Flush may emit
 196                 // some extra framing bits that are not necessary
 197                 // to process to obtain the first half of the uncompressed
 198                 // data.  The test ran correctly most of the time, because
 199                 // the background goroutine had usually read even
 200                 // those extra bits by now, but it's not a useful thing to
 201                 // check.
 202                 buf.WriteMode()
 203         }
 204         buf.ReadMode()
 205         out := make([]byte, 10)
 206         if n, err := r.Read(out); n > 0 || err != io.EOF {
 207                 t.Errorf("testSync (%d, %d, %s): final Read: %d, %v (hex: %x)", level, len(input), name, n, err, out[0:n])
 208         }
 209         if buf.buf.Len() != 0 {
 210                 t.Errorf("testSync (%d, %d, %s): extra data at end", level, len(input), name)
 211         }
 212         r.Close()
 213
 214         // stream should work for ordinary reader too
 215         r = NewReader(buf1)
 216         out, err := ioutil.ReadAll(r)
 217         if err != nil {
 218                 t.Errorf("testSync: read: %s", err)
 219                 return
 220         }
 221         r.Close()
 222         if !bytes.Equal(input, out) {
 223                 t.Errorf("testSync: decompress(compress(data)) != data: level=%d input=%s", level, name)
 224         }
 225 }
 226
 227 func testToFromWithLevel(t *testing.T, level int, input []byte, name string) error {
 228         return testToFromWithLevelAndLimit(t, level, input, name, -1)
 229 }
 230
 231 func testToFromWithLevelAndLimit(t *testing.T, level int, input []byte, name string, limit int) error {
 232         buffer := bytes.NewBuffer(nil)
 233         w := NewWriter(buffer, level)
 234         w.Write(input)
 235         w.Close()
 236         if limit > 0 && buffer.Len() > limit {
 237                 t.Errorf("level: %d, len(compress(data)) = %d > limit = %d", level, buffer.Len(), limit)
 238         }
 239         r := NewReader(buffer)
 240         out, err := ioutil.ReadAll(r)
 241         if err != nil {
 242                 t.Errorf("read: %s", err)
 243                 return err
 244         }
 245         r.Close()
 246         if !bytes.Equal(input, out) {
 247                 t.Errorf("decompress(compress(data)) != data: level=%d input=%s", level, name)
 248         }
 249
 250         testSync(t, level, input, name)
 251         return nil
 252 }
 253
 254 func testToFromWithLimit(t *testing.T, input []byte, name string, limit [10]int) {
 255         for i := 0; i < 10; i++ {
 256                 testToFromWithLevelAndLimit(t, i, input, name, limit[i])
 257         }
 258 }
 259
 260 func testToFrom(t *testing.T, input []byte, name string) {
 261         testToFromWithLimit(t, input, name, [10]int{})
 262 }
 263
 264 func TestDeflateInflate(t *testing.T) {
 265         for i, h := range deflateInflateTests {
 266                 testToFrom(t, h.in, fmt.Sprintf("#%d", i))
 267         }
 268 }
 269
 270 func TestReverseBits(t *testing.T) {
 271         for _, h := range reverseBitsTests {
 272                 if v := reverseBits(h.in, h.bitCount); v != h.out {
 273                         t.Errorf("reverseBits(%v,%v) = %v, want %v",
 274                                 h.in, h.bitCount, v, h.out)
 275                 }
 276         }
 277 }
 278
 279 type deflateInflateStringTest struct {
 280         filename string
 281         label    string
 282         limit    [10]int
 283 }
 284
 285 var deflateInflateStringTests = []deflateInflateStringTest{
 286         {
 287                 "../testdata/e.txt",
 288                 "2.718281828...",
 289                 [...]int{10013, 5065, 5096, 5115, 5093, 5079, 5079, 5079, 5079, 5079},
 290         },
 291         {
 292                 "../testdata/Mark.Twain-Tom.Sawyer.txt",
 293                 "Mark.Twain-Tom.Sawyer",
 294                 [...]int{407330, 187598, 180361, 172974, 169160, 163476, 160936, 160506, 160295, 160295},
 295         },
 296 }
 297
 298 func TestDeflateInflateString(t *testing.T) {
 299         for _, test := range deflateInflateStringTests {
 300                 gold, err := ioutil.ReadFile(test.filename)
 301                 if err != nil {
 302                         t.Error(err)
 303                 }
 304                 testToFromWithLimit(t, gold, test.label, test.limit)
 305         }
 306 }
 307
 308 func TestReaderDict(t *testing.T) {
 309         const (
 310                 dict = "hello world"
 311                 text = "hello again world"
 312         )
 313         var b bytes.Buffer
 314         w := NewWriter(&b, 5)
 315         w.Write([]byte(dict))
 316         w.Flush()
 317         b.Reset()
 318         w.Write([]byte(text))
 319         w.Close()
 320
 321         r := NewReaderDict(&b, []byte(dict))
 322         data, err := ioutil.ReadAll(r)
 323         if err != nil {
 324                 t.Fatal(err)
 325         }
 326         if string(data) != "hello again world" {
 327                 t.Fatalf("read returned %q want %q", string(data), text)
 328         }
 329 }
 330
 331 func TestWriterDict(t *testing.T) {
 332         const (
 333                 dict = "hello world"
 334                 text = "hello again world"
 335         )
 336         var b bytes.Buffer
 337         w := NewWriter(&b, 5)
 338         w.Write([]byte(dict))
 339         w.Flush()
 340         b.Reset()
 341         w.Write([]byte(text))
 342         w.Close()
 343
 344         var b1 bytes.Buffer
 345         w = NewWriterDict(&b1, 5, []byte(dict))
 346         w.Write([]byte(text))
 347         w.Close()
 348
 349         if !bytes.Equal(b1.Bytes(), b.Bytes()) {
 350                 t.Fatalf("writer wrote %q want %q", b1.Bytes(), b.Bytes())
 351         }
 352 }
 353
 354 // See http://code.google.com/p/go/issues/detail?id=2508
 355 func TestRegression2508(t *testing.T) {
 356         w := NewWriter(ioutil.Discard, 1)
 357         buf := make([]byte, 1024)
 358         for i := 0; i < 131072; i++ {
 359                 if _, err := w.Write(buf); err != nil {
 360                         t.Fatalf("writer failed: %v", err)
 361                 }
 362         }
 363         w.Close()
 364 }