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, err := NewWriter(&buf, h.level)
  85                 if err != nil {
  86                         t.Errorf("NewWriter: %v", err)
  87                         continue
  88                 }
  89                 w.Write(h.in)
  90                 w.Close()
  91                 if !bytes.Equal(buf.Bytes(), h.out) {
  92                         t.Errorf("Deflate(%d, %x) = %x, want %x", h.level, h.in, buf.Bytes(), h.out)
  93                 }
  94         }
  95 }
  96
  97 // A sparseReader returns a stream consisting of 0s followed by 1<<16 1s.
  98 // This tests missing hash references in a very large input.
  99 type sparseReader struct {
 100         l   int64
 101         cur int64
 102 }
 103
 104 func (r *sparseReader) Read(b []byte) (n int, err error) {
 105         if r.cur >= r.l {
 106                 return 0, io.EOF
 107         }
 108         n = len(b)
 109         cur := r.cur + int64(n)
 110         if cur > r.l {
 111                 n -= int(cur - r.l)
 112                 cur = r.l
 113         }
 114         for i := range b[0:n] {
 115                 if r.cur+int64(i) >= r.l-1<<16 {
 116                         b[i] = 1
 117                 } else {
 118                         b[i] = 0
 119                 }
 120         }
 121         r.cur = cur
 122         return
 123 }
 124
 125 func TestVeryLongSparseChunk(t *testing.T) {
 126         if testing.Short() {
 127                 t.Logf("skipping sparse chunk during short test")
 128                 return
 129         }
 130         w, err := NewWriter(ioutil.Discard, 1)
 131         if err != nil {
 132                 t.Errorf("NewWriter: %v", err)
 133                 return
 134         }
 135         if _, err = io.Copy(w, &sparseReader{l: 23E8}); err != nil {
 136                 t.Errorf("Compress failed: %v", err)
 137                 return
 138         }
 139 }
 140
 141 type syncBuffer struct {
 142         buf    bytes.Buffer
 143         mu     sync.RWMutex
 144         closed bool
 145         ready  chan bool
 146 }
 147
 148 func newSyncBuffer() *syncBuffer {
 149         return &syncBuffer{ready: make(chan bool, 1)}
 150 }
 151
 152 func (b *syncBuffer) Read(p []byte) (n int, err error) {
 153         for {
 154                 b.mu.RLock()
 155                 n, err = b.buf.Read(p)
 156                 b.mu.RUnlock()
 157                 if n > 0 || b.closed {
 158                         return
 159                 }
 160                 <-b.ready
 161         }
 162         panic("unreachable")
 163 }
 164
 165 func (b *syncBuffer) signal() {
 166         select {
 167         case b.ready <- true:
 168         default:
 169         }
 170 }
 171
 172 func (b *syncBuffer) Write(p []byte) (n int, err error) {
 173         n, err = b.buf.Write(p)
 174         b.signal()
 175         return
 176 }
 177
 178 func (b *syncBuffer) WriteMode() {
 179         b.mu.Lock()
 180 }
 181
 182 func (b *syncBuffer) ReadMode() {
 183         b.mu.Unlock()
 184         b.signal()
 185 }
 186
 187 func (b *syncBuffer) Close() error {
 188         b.closed = true
 189         b.signal()
 190         return nil
 191 }
 192
 193 func testSync(t *testing.T, level int, input []byte, name string) {
 194         if len(input) == 0 {
 195                 return
 196         }
 197
 198         t.Logf("--testSync %d, %d, %s", level, len(input), name)
 199         buf := newSyncBuffer()
 200         buf1 := new(bytes.Buffer)
 201         buf.WriteMode()
 202         w, err := NewWriter(io.MultiWriter(buf, buf1), level)
 203         if err != nil {
 204                 t.Errorf("NewWriter: %v", err)
 205                 return
 206         }
 207         r := NewReader(buf)
 208
 209         // Write half the input and read back.
 210         for i := 0; i < 2; i++ {
 211                 var lo, hi int
 212                 if i == 0 {
 213                         lo, hi = 0, (len(input)+1)/2
 214                 } else {
 215                         lo, hi = (len(input)+1)/2, len(input)
 216                 }
 217                 t.Logf("#%d: write %d-%d", i, lo, hi)
 218                 if _, err := w.Write(input[lo:hi]); err != nil {
 219                         t.Errorf("testSync: write: %v", err)
 220                         return
 221                 }
 222                 if i == 0 {
 223                         if err := w.Flush(); err != nil {
 224                                 t.Errorf("testSync: flush: %v", err)
 225                                 return
 226                         }
 227                 } else {
 228                         if err := w.Close(); err != nil {
 229                                 t.Errorf("testSync: close: %v", err)
 230                         }
 231                 }
 232                 buf.ReadMode()
 233                 out := make([]byte, hi-lo+1)
 234                 m, err := io.ReadAtLeast(r, out, hi-lo)
 235                 t.Logf("#%d: read %d", i, m)
 236                 if m != hi-lo || err != nil {
 237                         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())
 238                         return
 239                 }
 240                 if !bytes.Equal(input[lo:hi], out[:hi-lo]) {
 241                         t.Errorf("testSync/%d: read wrong bytes: %x vs %x", i, input[lo:hi], out[:hi-lo])
 242                         return
 243                 }
 244                 // This test originally checked that after reading
 245                 // the first half of the input, there was nothing left
 246                 // in the read buffer (buf.buf.Len() != 0) but that is
 247                 // not necessarily the case: the write Flush may emit
 248                 // some extra framing bits that are not necessary
 249                 // to process to obtain the first half of the uncompressed
 250                 // data.  The test ran correctly most of the time, because
 251                 // the background goroutine had usually read even
 252                 // those extra bits by now, but it's not a useful thing to
 253                 // check.
 254                 buf.WriteMode()
 255         }
 256         buf.ReadMode()
 257         out := make([]byte, 10)
 258         if n, err := r.Read(out); n > 0 || err != io.EOF {
 259                 t.Errorf("testSync (%d, %d, %s): final Read: %d, %v (hex: %x)", level, len(input), name, n, err, out[0:n])
 260         }
 261         if buf.buf.Len() != 0 {
 262                 t.Errorf("testSync (%d, %d, %s): extra data at end", level, len(input), name)
 263         }
 264         r.Close()
 265
 266         // stream should work for ordinary reader too
 267         r = NewReader(buf1)
 268         out, err = ioutil.ReadAll(r)
 269         if err != nil {
 270                 t.Errorf("testSync: read: %s", err)
 271                 return
 272         }
 273         r.Close()
 274         if !bytes.Equal(input, out) {
 275                 t.Errorf("testSync: decompress(compress(data)) != data: level=%d input=%s", level, name)
 276         }
 277 }
 278
 279 func testToFromWithLevelAndLimit(t *testing.T, level int, input []byte, name string, limit int) {
 280         var buffer bytes.Buffer
 281         w, err := NewWriter(&buffer, level)
 282         if err != nil {
 283                 t.Errorf("NewWriter: %v", err)
 284                 return
 285         }
 286         w.Write(input)
 287         w.Close()
 288         if limit > 0 && buffer.Len() > limit {
 289                 t.Errorf("level: %d, len(compress(data)) = %d > limit = %d", level, buffer.Len(), limit)
 290                 return
 291         }
 292         r := NewReader(&buffer)
 293         out, err := ioutil.ReadAll(r)
 294         if err != nil {
 295                 t.Errorf("read: %s", err)
 296                 return
 297         }
 298         r.Close()
 299         if !bytes.Equal(input, out) {
 300                 t.Errorf("decompress(compress(data)) != data: level=%d input=%s", level, name)
 301                 return
 302         }
 303         testSync(t, level, input, name)
 304 }
 305
 306 func testToFromWithLimit(t *testing.T, input []byte, name string, limit [10]int) {
 307         for i := 0; i < 10; i++ {
 308                 testToFromWithLevelAndLimit(t, i, input, name, limit[i])
 309         }
 310 }
 311
 312 func TestDeflateInflate(t *testing.T) {
 313         for i, h := range deflateInflateTests {
 314                 testToFromWithLimit(t, h.in, fmt.Sprintf("#%d", i), [10]int{})
 315         }
 316 }
 317
 318 func TestReverseBits(t *testing.T) {
 319         for _, h := range reverseBitsTests {
 320                 if v := reverseBits(h.in, h.bitCount); v != h.out {
 321                         t.Errorf("reverseBits(%v,%v) = %v, want %v",
 322                                 h.in, h.bitCount, v, h.out)
 323                 }
 324         }
 325 }
 326
 327 type deflateInflateStringTest struct {
 328         filename string
 329         label    string
 330         limit    [10]int
 331 }
 332
 333 var deflateInflateStringTests = []deflateInflateStringTest{
 334         {
 335                 "../testdata/e.txt",
 336                 "2.718281828...",
 337                 [...]int{100018, 50650, 50960, 51150, 50930, 50790, 50790, 50790, 50790, 50790},
 338         },
 339         {
 340                 "../testdata/Mark.Twain-Tom.Sawyer.txt",
 341                 "Mark.Twain-Tom.Sawyer",
 342                 [...]int{407330, 187598, 180361, 172974, 169160, 163476, 160936, 160506, 160295, 160295},
 343         },
 344 }
 345
 346 func TestDeflateInflateString(t *testing.T) {
 347         for _, test := range deflateInflateStringTests {
 348                 gold, err := ioutil.ReadFile(test.filename)
 349                 if err != nil {
 350                         t.Error(err)
 351                 }
 352                 testToFromWithLimit(t, gold, test.label, test.limit)
 353                 if testing.Short() {
 354                         break
 355                 }
 356         }
 357 }
 358
 359 func TestReaderDict(t *testing.T) {
 360         const (
 361                 dict = "hello world"
 362                 text = "hello again world"
 363         )
 364         var b bytes.Buffer
 365         w, err := NewWriter(&b, 5)
 366         if err != nil {
 367                 t.Fatalf("NewWriter: %v", err)
 368         }
 369         w.Write([]byte(dict))
 370         w.Flush()
 371         b.Reset()
 372         w.Write([]byte(text))
 373         w.Close()
 374
 375         r := NewReaderDict(&b, []byte(dict))
 376         data, err := ioutil.ReadAll(r)
 377         if err != nil {
 378                 t.Fatal(err)
 379         }
 380         if string(data) != "hello again world" {
 381                 t.Fatalf("read returned %q want %q", string(data), text)
 382         }
 383 }
 384
 385 func TestWriterDict(t *testing.T) {
 386         const (
 387                 dict = "hello world"
 388                 text = "hello again world"
 389         )
 390         var b bytes.Buffer
 391         w, err := NewWriter(&b, 5)
 392         if err != nil {
 393                 t.Fatalf("NewWriter: %v", err)
 394         }
 395         w.Write([]byte(dict))
 396         w.Flush()
 397         b.Reset()
 398         w.Write([]byte(text))
 399         w.Close()
 400
 401         var b1 bytes.Buffer
 402         w, _ = NewWriterDict(&b1, 5, []byte(dict))
 403         w.Write([]byte(text))
 404         w.Close()
 405
 406         if !bytes.Equal(b1.Bytes(), b.Bytes()) {
 407                 t.Fatalf("writer wrote %q want %q", b1.Bytes(), b.Bytes())
 408         }
 409 }
 410
 411 // See http://code.google.com/p/go/issues/detail?id=2508
 412 func TestRegression2508(t *testing.T) {
 413         if testing.Short() {
 414                 t.Logf("test disabled with -short")
 415                 return
 416         }
 417         w, err := NewWriter(ioutil.Discard, 1)
 418         if err != nil {
 419                 t.Fatalf("NewWriter: %v", err)
 420         }
 421         buf := make([]byte, 1024)
 422         for i := 0; i < 131072; i++ {
 423                 if _, err := w.Write(buf); err != nil {
 424                         t.Fatalf("writer failed: %v", err)
 425                 }
 426         }
 427         w.Close()
 428 }