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 "reflect" 13 "sync" 14 "testing" 15 ) 16 17 type deflateTest struct { 18 in []byte 19 level int 20 out []byte 21 } 22 23 type deflateInflateTest struct { 24 in []byte 25 } 26 27 type reverseBitsTest struct { 28 in uint16 29 bitCount uint8 30 out uint16 31 } 32 33 var deflateTests = []*deflateTest{ 34 {[]byte{}, 0, []byte{1, 0, 0, 255, 255}}, 35 {[]byte{0x11}, -1, []byte{18, 4, 4, 0, 0, 255, 255}}, 36 {[]byte{0x11}, DefaultCompression, []byte{18, 4, 4, 0, 0, 255, 255}}, 37 {[]byte{0x11}, 4, []byte{18, 4, 4, 0, 0, 255, 255}}, 38 39 {[]byte{0x11}, 0, []byte{0, 1, 0, 254, 255, 17, 1, 0, 0, 255, 255}}, 40 {[]byte{0x11, 0x12}, 0, []byte{0, 2, 0, 253, 255, 17, 18, 1, 0, 0, 255, 255}}, 41 {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 0, 42 []byte{0, 8, 0, 247, 255, 17, 17, 17, 17, 17, 17, 17, 17, 1, 0, 0, 255, 255}, 43 }, 44 {[]byte{}, 1, []byte{1, 0, 0, 255, 255}}, 45 {[]byte{0x11}, 1, []byte{18, 4, 4, 0, 0, 255, 255}}, 46 {[]byte{0x11, 0x12}, 1, []byte{18, 20, 2, 4, 0, 0, 255, 255}}, 47 {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 1, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}}, 48 {[]byte{}, 9, []byte{1, 0, 0, 255, 255}}, 49 {[]byte{0x11}, 9, []byte{18, 4, 4, 0, 0, 255, 255}}, 50 {[]byte{0x11, 0x12}, 9, []byte{18, 20, 2, 4, 0, 0, 255, 255}}, 51 {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 9, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}}, 52 } 53 54 var deflateInflateTests = []*deflateInflateTest{ 55 {[]byte{}}, 56 {[]byte{0x11}}, 57 {[]byte{0x11, 0x12}}, 58 {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}}, 59 {[]byte{0x11, 0x10, 0x13, 0x41, 0x21, 0x21, 0x41, 0x13, 0x87, 0x78, 0x13}}, 60 {largeDataChunk()}, 61 } 62 63 var reverseBitsTests = []*reverseBitsTest{ 64 {1, 1, 1}, 65 {1, 2, 2}, 66 {1, 3, 4}, 67 {1, 4, 8}, 68 {1, 5, 16}, 69 {17, 5, 17}, 70 {257, 9, 257}, 71 {29, 5, 23}, 72 } 73 74 func largeDataChunk() []byte { 75 result := make([]byte, 100000) 76 for i := range result { 77 result[i] = byte(i * i & 0xFF) 78 } 79 return result 80 } 81 82 func TestDeflate(t *testing.T) { 83 for _, h := range deflateTests { 84 var buf bytes.Buffer 85 w, err := NewWriter(&buf, h.level) 86 if err != nil { 87 t.Errorf("NewWriter: %v", err) 88 continue 89 } 90 w.Write(h.in) 91 w.Close() 92 if !bytes.Equal(buf.Bytes(), h.out) { 93 t.Errorf("Deflate(%d, %x) = %x, want %x", h.level, h.in, buf.Bytes(), h.out) 94 } 95 } 96 } 97 98 // A sparseReader returns a stream consisting of 0s followed by 1<<16 1s. 99 // This tests missing hash references in a very large input. 100 type sparseReader struct { 101 l int64 102 cur int64 103 } 104 105 func (r *sparseReader) Read(b []byte) (n int, err error) { 106 if r.cur >= r.l { 107 return 0, io.EOF 108 } 109 n = len(b) 110 cur := r.cur + int64(n) 111 if cur > r.l { 112 n -= int(cur - r.l) 113 cur = r.l 114 } 115 for i := range b[0:n] { 116 if r.cur+int64(i) >= r.l-1<<16 { 117 b[i] = 1 118 } else { 119 b[i] = 0 120 } 121 } 122 r.cur = cur 123 return 124 } 125 126 func TestVeryLongSparseChunk(t *testing.T) { 127 if testing.Short() { 128 t.Skip("skipping sparse chunk during short test") 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 } 163 164 func (b *syncBuffer) signal() { 165 select { 166 case b.ready <- true: 167 default: 168 } 169 } 170 171 func (b *syncBuffer) Write(p []byte) (n int, err error) { 172 n, err = b.buf.Write(p) 173 b.signal() 174 return 175 } 176 177 func (b *syncBuffer) WriteMode() { 178 b.mu.Lock() 179 } 180 181 func (b *syncBuffer) ReadMode() { 182 b.mu.Unlock() 183 b.signal() 184 } 185 186 func (b *syncBuffer) Close() error { 187 b.closed = true 188 b.signal() 189 return nil 190 } 191 192 func testSync(t *testing.T, level int, input []byte, name string) { 193 if len(input) == 0 { 194 return 195 } 196 197 t.Logf("--testSync %d, %d, %s", level, len(input), name) 198 buf := newSyncBuffer() 199 buf1 := new(bytes.Buffer) 200 buf.WriteMode() 201 w, err := NewWriter(io.MultiWriter(buf, buf1), level) 202 if err != nil { 203 t.Errorf("NewWriter: %v", err) 204 return 205 } 206 r := NewReader(buf) 207 208 // Write half the input and read back. 209 for i := 0; i < 2; i++ { 210 var lo, hi int 211 if i == 0 { 212 lo, hi = 0, (len(input)+1)/2 213 } else { 214 lo, hi = (len(input)+1)/2, len(input) 215 } 216 t.Logf("#%d: write %d-%d", i, lo, hi) 217 if _, err := w.Write(input[lo:hi]); err != nil { 218 t.Errorf("testSync: write: %v", err) 219 return 220 } 221 if i == 0 { 222 if err := w.Flush(); err != nil { 223 t.Errorf("testSync: flush: %v", err) 224 return 225 } 226 } else { 227 if err := w.Close(); err != nil { 228 t.Errorf("testSync: close: %v", err) 229 } 230 } 231 buf.ReadMode() 232 out := make([]byte, hi-lo+1) 233 m, err := io.ReadAtLeast(r, out, hi-lo) 234 t.Logf("#%d: read %d", i, m) 235 if m != hi-lo || err != nil { 236 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()) 237 return 238 } 239 if !bytes.Equal(input[lo:hi], out[:hi-lo]) { 240 t.Errorf("testSync/%d: read wrong bytes: %x vs %x", i, input[lo:hi], out[:hi-lo]) 241 return 242 } 243 // This test originally checked that after reading 244 // the first half of the input, there was nothing left 245 // in the read buffer (buf.buf.Len() != 0) but that is 246 // not necessarily the case: the write Flush may emit 247 // some extra framing bits that are not necessary 248 // to process to obtain the first half of the uncompressed 249 // data. The test ran correctly most of the time, because 250 // the background goroutine had usually read even 251 // those extra bits by now, but it's not a useful thing to 252 // check. 253 buf.WriteMode() 254 } 255 buf.ReadMode() 256 out := make([]byte, 10) 257 if n, err := r.Read(out); n > 0 || err != io.EOF { 258 t.Errorf("testSync (%d, %d, %s): final Read: %d, %v (hex: %x)", level, len(input), name, n, err, out[0:n]) 259 } 260 if buf.buf.Len() != 0 { 261 t.Errorf("testSync (%d, %d, %s): extra data at end", level, len(input), name) 262 } 263 r.Close() 264 265 // stream should work for ordinary reader too 266 r = NewReader(buf1) 267 out, err = ioutil.ReadAll(r) 268 if err != nil { 269 t.Errorf("testSync: read: %s", err) 270 return 271 } 272 r.Close() 273 if !bytes.Equal(input, out) { 274 t.Errorf("testSync: decompress(compress(data)) != data: level=%d input=%s", level, name) 275 } 276 } 277 278 func testToFromWithLevelAndLimit(t *testing.T, level int, input []byte, name string, limit int) { 279 var buffer bytes.Buffer 280 w, err := NewWriter(&buffer, level) 281 if err != nil { 282 t.Errorf("NewWriter: %v", err) 283 return 284 } 285 w.Write(input) 286 w.Close() 287 if limit > 0 && buffer.Len() > limit { 288 t.Errorf("level: %d, len(compress(data)) = %d > limit = %d", level, buffer.Len(), limit) 289 return 290 } 291 r := NewReader(&buffer) 292 out, err := ioutil.ReadAll(r) 293 if err != nil { 294 t.Errorf("read: %s", err) 295 return 296 } 297 r.Close() 298 if !bytes.Equal(input, out) { 299 t.Errorf("decompress(compress(data)) != data: level=%d input=%s", level, name) 300 return 301 } 302 testSync(t, level, input, name) 303 } 304 305 func testToFromWithLimit(t *testing.T, input []byte, name string, limit [10]int) { 306 for i := 0; i < 10; i++ { 307 testToFromWithLevelAndLimit(t, i, input, name, limit[i]) 308 } 309 } 310 311 func TestDeflateInflate(t *testing.T) { 312 for i, h := range deflateInflateTests { 313 testToFromWithLimit(t, h.in, fmt.Sprintf("#%d", i), [10]int{}) 314 } 315 } 316 317 func TestReverseBits(t *testing.T) { 318 for _, h := range reverseBitsTests { 319 if v := reverseBits(h.in, h.bitCount); v != h.out { 320 t.Errorf("reverseBits(%v,%v) = %v, want %v", 321 h.in, h.bitCount, v, h.out) 322 } 323 } 324 } 325 326 type deflateInflateStringTest struct { 327 filename string 328 label string 329 limit [10]int 330 } 331 332 var deflateInflateStringTests = []deflateInflateStringTest{ 333 { 334 "../testdata/e.txt", 335 "2.718281828...", 336 [...]int{100018, 50650, 50960, 51150, 50930, 50790, 50790, 50790, 50790, 50790}, 337 }, 338 { 339 "../testdata/Mark.Twain-Tom.Sawyer.txt", 340 "Mark.Twain-Tom.Sawyer", 341 [...]int{407330, 187598, 180361, 172974, 169160, 163476, 160936, 160506, 160295, 160295}, 342 }, 343 } 344 345 func TestDeflateInflateString(t *testing.T) { 346 for _, test := range deflateInflateStringTests { 347 gold, err := ioutil.ReadFile(test.filename) 348 if err != nil { 349 t.Error(err) 350 } 351 testToFromWithLimit(t, gold, test.label, test.limit) 352 if testing.Short() { 353 break 354 } 355 } 356 } 357 358 func TestReaderDict(t *testing.T) { 359 const ( 360 dict = "hello world" 361 text = "hello again world" 362 ) 363 var b bytes.Buffer 364 w, err := NewWriter(&b, 5) 365 if err != nil { 366 t.Fatalf("NewWriter: %v", err) 367 } 368 w.Write([]byte(dict)) 369 w.Flush() 370 b.Reset() 371 w.Write([]byte(text)) 372 w.Close() 373 374 r := NewReaderDict(&b, []byte(dict)) 375 data, err := ioutil.ReadAll(r) 376 if err != nil { 377 t.Fatal(err) 378 } 379 if string(data) != "hello again world" { 380 t.Fatalf("read returned %q want %q", string(data), text) 381 } 382 } 383 384 func TestWriterDict(t *testing.T) { 385 const ( 386 dict = "hello world" 387 text = "hello again world" 388 ) 389 var b bytes.Buffer 390 w, err := NewWriter(&b, 5) 391 if err != nil { 392 t.Fatalf("NewWriter: %v", err) 393 } 394 w.Write([]byte(dict)) 395 w.Flush() 396 b.Reset() 397 w.Write([]byte(text)) 398 w.Close() 399 400 var b1 bytes.Buffer 401 w, _ = NewWriterDict(&b1, 5, []byte(dict)) 402 w.Write([]byte(text)) 403 w.Close() 404 405 if !bytes.Equal(b1.Bytes(), b.Bytes()) { 406 t.Fatalf("writer wrote %q want %q", b1.Bytes(), b.Bytes()) 407 } 408 } 409 410 // See https://golang.org/issue/2508 411 func TestRegression2508(t *testing.T) { 412 if testing.Short() { 413 t.Logf("test disabled with -short") 414 return 415 } 416 w, err := NewWriter(ioutil.Discard, 1) 417 if err != nil { 418 t.Fatalf("NewWriter: %v", err) 419 } 420 buf := make([]byte, 1024) 421 for i := 0; i < 131072; i++ { 422 if _, err := w.Write(buf); err != nil { 423 t.Fatalf("writer failed: %v", err) 424 } 425 } 426 w.Close() 427 } 428 429 func TestWriterReset(t *testing.T) { 430 for level := 0; level <= 9; level++ { 431 if testing.Short() && level > 1 { 432 break 433 } 434 w, err := NewWriter(ioutil.Discard, level) 435 if err != nil { 436 t.Fatalf("NewWriter: %v", err) 437 } 438 buf := []byte("hello world") 439 for i := 0; i < 1024; i++ { 440 w.Write(buf) 441 } 442 w.Reset(ioutil.Discard) 443 444 wref, err := NewWriter(ioutil.Discard, level) 445 if err != nil { 446 t.Fatalf("NewWriter: %v", err) 447 } 448 449 // DeepEqual doesn't compare functions. 450 w.d.fill, wref.d.fill = nil, nil 451 w.d.step, wref.d.step = nil, nil 452 if !reflect.DeepEqual(w, wref) { 453 t.Errorf("level %d Writer not reset after Reset", level) 454 } 455 } 456 testResetOutput(t, func(w io.Writer) (*Writer, error) { return NewWriter(w, NoCompression) }) 457 testResetOutput(t, func(w io.Writer) (*Writer, error) { return NewWriter(w, DefaultCompression) }) 458 testResetOutput(t, func(w io.Writer) (*Writer, error) { return NewWriter(w, BestCompression) }) 459 dict := []byte("we are the world") 460 testResetOutput(t, func(w io.Writer) (*Writer, error) { return NewWriterDict(w, NoCompression, dict) }) 461 testResetOutput(t, func(w io.Writer) (*Writer, error) { return NewWriterDict(w, DefaultCompression, dict) }) 462 testResetOutput(t, func(w io.Writer) (*Writer, error) { return NewWriterDict(w, BestCompression, dict) }) 463 } 464 465 func testResetOutput(t *testing.T, newWriter func(w io.Writer) (*Writer, error)) { 466 buf := new(bytes.Buffer) 467 w, err := newWriter(buf) 468 if err != nil { 469 t.Fatalf("NewWriter: %v", err) 470 } 471 b := []byte("hello world") 472 for i := 0; i < 1024; i++ { 473 w.Write(b) 474 } 475 w.Close() 476 out1 := buf.String() 477 478 buf2 := new(bytes.Buffer) 479 w.Reset(buf2) 480 for i := 0; i < 1024; i++ { 481 w.Write(b) 482 } 483 w.Close() 484 out2 := buf2.String() 485 486 if out1 != out2 { 487 t.Errorf("got %q, expected %q", out2, out1) 488 } 489 t.Logf("got %d bytes", len(out1)) 490 } 491
