vendor/github.com/golang/snappy/snappy_test.go

   1 // Copyright 2011 The Snappy-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 snappy
   6
   7 import (
   8         "bytes"
   9         "encoding/binary"
  10         "flag"
  11         "fmt"
  12         "io"
  13         "io/ioutil"
  14         "math/rand"
  15         "net/http"
  16         "os"
  17         "os/exec"
  18         "path/filepath"
  19         "runtime"
  20         "strings"
  21         "testing"
  22 )
  23
  24 var (
  25         download     = flag.Bool("download", false, "If true, download any missing files before running benchmarks")
  26         testdataDir  = flag.String("testdataDir", "testdata", "Directory containing the test data")
  27         benchdataDir = flag.String("benchdataDir", "testdata/bench", "Directory containing the benchmark data")
  28 )
  29
  30 // goEncoderShouldMatchCppEncoder is whether to test that the algorithm used by
  31 // Go's encoder matches byte-for-byte what the C++ snappy encoder produces, on
  32 // this GOARCH. There is more than one valid encoding of any given input, and
  33 // there is more than one good algorithm along the frontier of trading off
  34 // throughput for output size. Nonetheless, we presume that the C++ encoder's
  35 // algorithm is a good one and has been tested on a wide range of inputs, so
  36 // matching that exactly should mean that the Go encoder's algorithm is also
  37 // good, without needing to gather our own corpus of test data.
  38 //
  39 // The exact algorithm used by the C++ code is potentially endian dependent, as
  40 // it puns a byte pointer to a uint32 pointer to load, hash and compare 4 bytes
  41 // at a time. The Go implementation is endian agnostic, in that its output is
  42 // the same (as little-endian C++ code), regardless of the CPU's endianness.
  43 //
  44 // Thus, when comparing Go's output to C++ output generated beforehand, such as
  45 // the "testdata/pi.txt.rawsnappy" file generated by C++ code on a little-
  46 // endian system, we can run that test regardless of the runtime.GOARCH value.
  47 //
  48 // When comparing Go's output to dynamically generated C++ output, i.e. the
  49 // result of fork/exec'ing a C++ program, we can run that test only on
  50 // little-endian systems, because the C++ output might be different on
  51 // big-endian systems. The runtime package doesn't export endianness per se,
  52 // but we can restrict this match-C++ test to common little-endian systems.
  53 const goEncoderShouldMatchCppEncoder = runtime.GOARCH == "386" || runtime.GOARCH == "amd64" || runtime.GOARCH == "arm"
  54
  55 func TestMaxEncodedLenOfMaxBlockSize(t *testing.T) {
  56         got := maxEncodedLenOfMaxBlockSize
  57         want := MaxEncodedLen(maxBlockSize)
  58         if got != want {
  59                 t.Fatalf("got %d, want %d", got, want)
  60         }
  61 }
  62
  63 func cmp(a, b []byte) error {
  64         if bytes.Equal(a, b) {
  65                 return nil
  66         }
  67         if len(a) != len(b) {
  68                 return fmt.Errorf("got %d bytes, want %d", len(a), len(b))
  69         }
  70         for i := range a {
  71                 if a[i] != b[i] {
  72                         return fmt.Errorf("byte #%d: got 0x%02x, want 0x%02x", i, a[i], b[i])
  73                 }
  74         }
  75         return nil
  76 }
  77
  78 func roundtrip(b, ebuf, dbuf []byte) error {
  79         d, err := Decode(dbuf, Encode(ebuf, b))
  80         if err != nil {
  81                 return fmt.Errorf("decoding error: %v", err)
  82         }
  83         if err := cmp(d, b); err != nil {
  84                 return fmt.Errorf("roundtrip mismatch: %v", err)
  85         }
  86         return nil
  87 }
  88
  89 func TestEmpty(t *testing.T) {
  90         if err := roundtrip(nil, nil, nil); err != nil {
  91                 t.Fatal(err)
  92         }
  93 }
  94
  95 func TestSmallCopy(t *testing.T) {
  96         for _, ebuf := range [][]byte{nil, make([]byte, 20), make([]byte, 64)} {
  97                 for _, dbuf := range [][]byte{nil, make([]byte, 20), make([]byte, 64)} {
  98                         for i := 0; i < 32; i++ {
  99                                 s := "aaaa" + strings.Repeat("b", i) + "aaaabbbb"
 100                                 if err := roundtrip([]byte(s), ebuf, dbuf); err != nil {
 101                                         t.Errorf("len(ebuf)=%d, len(dbuf)=%d, i=%d: %v", len(ebuf), len(dbuf), i, err)
 102                                 }
 103                         }
 104                 }
 105         }
 106 }
 107
 108 func TestSmallRand(t *testing.T) {
 109         rng := rand.New(rand.NewSource(1))
 110         for n := 1; n < 20000; n += 23 {
 111                 b := make([]byte, n)
 112                 for i := range b {
 113                         b[i] = uint8(rng.Intn(256))
 114                 }
 115                 if err := roundtrip(b, nil, nil); err != nil {
 116                         t.Fatal(err)
 117                 }
 118         }
 119 }
 120
 121 func TestSmallRegular(t *testing.T) {
 122         for n := 1; n < 20000; n += 23 {
 123                 b := make([]byte, n)
 124                 for i := range b {
 125                         b[i] = uint8(i%10 + 'a')
 126                 }
 127                 if err := roundtrip(b, nil, nil); err != nil {
 128                         t.Fatal(err)
 129                 }
 130         }
 131 }
 132
 133 func TestInvalidVarint(t *testing.T) {
 134         testCases := []struct {
 135                 desc  string
 136                 input string
 137         }{{
 138                 "invalid varint, final byte has continuation bit set",
 139                 "\xff",
 140         }, {
 141                 "invalid varint, value overflows uint64",
 142                 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x00",
 143         }, {
 144                 // https://github.com/google/snappy/blob/master/format_description.txt
 145                 // says that "the stream starts with the uncompressed length [as a
 146                 // varint] (up to a maximum of 2^32 - 1)".
 147                 "valid varint (as uint64), but value overflows uint32",
 148                 "\x80\x80\x80\x80\x10",
 149         }}
 150
 151         for _, tc := range testCases {
 152                 input := []byte(tc.input)
 153                 if _, err := DecodedLen(input); err != ErrCorrupt {
 154                         t.Errorf("%s: DecodedLen: got %v, want ErrCorrupt", tc.desc, err)
 155                 }
 156                 if _, err := Decode(nil, input); err != ErrCorrupt {
 157                         t.Errorf("%s: Decode: got %v, want ErrCorrupt", tc.desc, err)
 158                 }
 159         }
 160 }
 161
 162 func TestDecode(t *testing.T) {
 163         lit40Bytes := make([]byte, 40)
 164         for i := range lit40Bytes {
 165                 lit40Bytes[i] = byte(i)
 166         }
 167         lit40 := string(lit40Bytes)
 168
 169         testCases := []struct {
 170                 desc    string
 171                 input   string
 172                 want    string
 173                 wantErr error
 174         }{{
 175                 `decodedLen=0; valid input`,
 176                 "\x00",
 177                 "",
 178                 nil,
 179         }, {
 180                 `decodedLen=3; tagLiteral, 0-byte length; length=3; valid input`,
 181                 "\x03" + "\x08\xff\xff\xff",
 182                 "\xff\xff\xff",
 183                 nil,
 184         }, {
 185                 `decodedLen=2; tagLiteral, 0-byte length; length=3; not enough dst bytes`,
 186                 "\x02" + "\x08\xff\xff\xff",
 187                 "",
 188                 ErrCorrupt,
 189         }, {
 190                 `decodedLen=3; tagLiteral, 0-byte length; length=3; not enough src bytes`,
 191                 "\x03" + "\x08\xff\xff",
 192                 "",
 193                 ErrCorrupt,
 194         }, {
 195                 `decodedLen=40; tagLiteral, 0-byte length; length=40; valid input`,
 196                 "\x28" + "\x9c" + lit40,
 197                 lit40,
 198                 nil,
 199         }, {
 200                 `decodedLen=1; tagLiteral, 1-byte length; not enough length bytes`,
 201                 "\x01" + "\xf0",
 202                 "",
 203                 ErrCorrupt,
 204         }, {
 205                 `decodedLen=3; tagLiteral, 1-byte length; length=3; valid input`,
 206                 "\x03" + "\xf0\x02\xff\xff\xff",
 207                 "\xff\xff\xff",
 208                 nil,
 209         }, {
 210                 `decodedLen=1; tagLiteral, 2-byte length; not enough length bytes`,
 211                 "\x01" + "\xf4\x00",
 212                 "",
 213                 ErrCorrupt,
 214         }, {
 215                 `decodedLen=3; tagLiteral, 2-byte length; length=3; valid input`,
 216                 "\x03" + "\xf4\x02\x00\xff\xff\xff",
 217                 "\xff\xff\xff",
 218                 nil,
 219         }, {
 220                 `decodedLen=1; tagLiteral, 3-byte length; not enough length bytes`,
 221                 "\x01" + "\xf8\x00\x00",
 222                 "",
 223                 ErrCorrupt,
 224         }, {
 225                 `decodedLen=3; tagLiteral, 3-byte length; length=3; valid input`,
 226                 "\x03" + "\xf8\x02\x00\x00\xff\xff\xff",
 227                 "\xff\xff\xff",
 228                 nil,
 229         }, {
 230                 `decodedLen=1; tagLiteral, 4-byte length; not enough length bytes`,
 231                 "\x01" + "\xfc\x00\x00\x00",
 232                 "",
 233                 ErrCorrupt,
 234         }, {
 235                 `decodedLen=1; tagLiteral, 4-byte length; length=3; not enough dst bytes`,
 236                 "\x01" + "\xfc\x02\x00\x00\x00\xff\xff\xff",
 237                 "",
 238                 ErrCorrupt,
 239         }, {
 240                 `decodedLen=4; tagLiteral, 4-byte length; length=3; not enough src bytes`,
 241                 "\x04" + "\xfc\x02\x00\x00\x00\xff",
 242                 "",
 243                 ErrCorrupt,
 244         }, {
 245                 `decodedLen=3; tagLiteral, 4-byte length; length=3; valid input`,
 246                 "\x03" + "\xfc\x02\x00\x00\x00\xff\xff\xff",
 247                 "\xff\xff\xff",
 248                 nil,
 249         }, {
 250                 `decodedLen=4; tagCopy1, 1 extra length|offset byte; not enough extra bytes`,
 251                 "\x04" + "\x01",
 252                 "",
 253                 ErrCorrupt,
 254         }, {
 255                 `decodedLen=4; tagCopy2, 2 extra length|offset bytes; not enough extra bytes`,
 256                 "\x04" + "\x02\x00",
 257                 "",
 258                 ErrCorrupt,
 259         }, {
 260                 `decodedLen=4; tagCopy4, 4 extra length|offset bytes; not enough extra bytes`,
 261                 "\x04" + "\x03\x00\x00\x00",
 262                 "",
 263                 ErrCorrupt,
 264         }, {
 265                 `decodedLen=4; tagLiteral (4 bytes "abcd"); valid input`,
 266                 "\x04" + "\x0cabcd",
 267                 "abcd",
 268                 nil,
 269         }, {
 270                 `decodedLen=13; tagLiteral (4 bytes "abcd"); tagCopy1; length=9 offset=4; valid input`,
 271                 "\x0d" + "\x0cabcd" + "\x15\x04",
 272                 "abcdabcdabcda",
 273                 nil,
 274         }, {
 275                 `decodedLen=8; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=4; valid input`,
 276                 "\x08" + "\x0cabcd" + "\x01\x04",
 277                 "abcdabcd",
 278                 nil,
 279         }, {
 280                 `decodedLen=8; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=2; valid input`,
 281                 "\x08" + "\x0cabcd" + "\x01\x02",
 282                 "abcdcdcd",
 283                 nil,
 284         }, {
 285                 `decodedLen=8; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=1; valid input`,
 286                 "\x08" + "\x0cabcd" + "\x01\x01",
 287                 "abcddddd",
 288                 nil,
 289         }, {
 290                 `decodedLen=8; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=0; zero offset`,
 291                 "\x08" + "\x0cabcd" + "\x01\x00",
 292                 "",
 293                 ErrCorrupt,
 294         }, {
 295                 `decodedLen=9; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=4; inconsistent dLen`,
 296                 "\x09" + "\x0cabcd" + "\x01\x04",
 297                 "",
 298                 ErrCorrupt,
 299         }, {
 300                 `decodedLen=8; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=5; offset too large`,
 301                 "\x08" + "\x0cabcd" + "\x01\x05",
 302                 "",
 303                 ErrCorrupt,
 304         }, {
 305                 `decodedLen=7; tagLiteral (4 bytes "abcd"); tagCopy1; length=4 offset=4; length too large`,
 306                 "\x07" + "\x0cabcd" + "\x01\x04",
 307                 "",
 308                 ErrCorrupt,
 309         }, {
 310                 `decodedLen=6; tagLiteral (4 bytes "abcd"); tagCopy2; length=2 offset=3; valid input`,
 311                 "\x06" + "\x0cabcd" + "\x06\x03\x00",
 312                 "abcdbc",
 313                 nil,
 314         }, {
 315                 `decodedLen=6; tagLiteral (4 bytes "abcd"); tagCopy4; length=2 offset=3; valid input`,
 316                 "\x06" + "\x0cabcd" + "\x07\x03\x00\x00\x00",
 317                 "abcdbc",
 318                 nil,
 319         }}
 320
 321         const (
 322                 // notPresentXxx defines a range of byte values [0xa0, 0xc5) that are
 323                 // not present in either the input or the output. It is written to dBuf
 324                 // to check that Decode does not write bytes past the end of
 325                 // dBuf[:dLen].
 326                 //
 327                 // The magic number 37 was chosen because it is prime. A more 'natural'
 328                 // number like 32 might lead to a false negative if, for example, a
 329                 // byte was incorrectly copied 4*8 bytes later.
 330                 notPresentBase = 0xa0
 331                 notPresentLen  = 37
 332         )
 333
 334         var dBuf [100]byte
 335 loop:
 336         for i, tc := range testCases {
 337                 input := []byte(tc.input)
 338                 for _, x := range input {
 339                         if notPresentBase <= x && x < notPresentBase+notPresentLen {
 340                                 t.Errorf("#%d (%s): input shouldn't contain %#02x\ninput: % x", i, tc.desc, x, input)
 341                                 continue loop
 342                         }
 343                 }
 344
 345                 dLen, n := binary.Uvarint(input)
 346                 if n <= 0 {
 347                         t.Errorf("#%d (%s): invalid varint-encoded dLen", i, tc.desc)
 348                         continue
 349                 }
 350                 if dLen > uint64(len(dBuf)) {
 351                         t.Errorf("#%d (%s): dLen %d is too large", i, tc.desc, dLen)
 352                         continue
 353                 }
 354
 355                 for j := range dBuf {
 356                         dBuf[j] = byte(notPresentBase + j%notPresentLen)
 357                 }
 358                 g, gotErr := Decode(dBuf[:], input)
 359                 if got := string(g); got != tc.want || gotErr != tc.wantErr {
 360                         t.Errorf("#%d (%s):\ngot  %q, %v\nwant %q, %v",
 361                                 i, tc.desc, got, gotErr, tc.want, tc.wantErr)
 362                         continue
 363                 }
 364                 for j, x := range dBuf {
 365                         if uint64(j) < dLen {
 366                                 continue
 367                         }
 368                         if w := byte(notPresentBase + j%notPresentLen); x != w {
 369                                 t.Errorf("#%d (%s): Decode overrun: dBuf[%d] was modified: got %#02x, want %#02x\ndBuf: % x",
 370                                         i, tc.desc, j, x, w, dBuf)
 371                                 continue loop
 372                         }
 373                 }
 374         }
 375 }
 376
 377 func TestDecodeCopy4(t *testing.T) {
 378         dots := strings.Repeat(".", 65536)
 379
 380         input := strings.Join([]string{
 381                 "\x89\x80\x04",         // decodedLen = 65545.
 382                 "\x0cpqrs",             // 4-byte literal "pqrs".
 383                 "\xf4\xff\xff" + dots,  // 65536-byte literal dots.
 384                 "\x13\x04\x00\x01\x00", // tagCopy4; length=5 offset=65540.
 385         }, "")
 386
 387         gotBytes, err := Decode(nil, []byte(input))
 388         if err != nil {
 389                 t.Fatal(err)
 390         }
 391         got := string(gotBytes)
 392         want := "pqrs" + dots + "pqrs."
 393         if len(got) != len(want) {
 394                 t.Fatalf("got %d bytes, want %d", len(got), len(want))
 395         }
 396         if got != want {
 397                 for i := 0; i < len(got); i++ {
 398                         if g, w := got[i], want[i]; g != w {
 399                                 t.Fatalf("byte #%d: got %#02x, want %#02x", i, g, w)
 400                         }
 401                 }
 402         }
 403 }
 404
 405 // TestDecodeLengthOffset tests decoding an encoding of the form literal +
 406 // copy-length-offset + literal. For example: "abcdefghijkl" + "efghij" + "AB".
 407 func TestDecodeLengthOffset(t *testing.T) {
 408         const (
 409                 prefix = "abcdefghijklmnopqr"
 410                 suffix = "ABCDEFGHIJKLMNOPQR"
 411
 412                 // notPresentXxx defines a range of byte values [0xa0, 0xc5) that are
 413                 // not present in either the input or the output. It is written to
 414                 // gotBuf to check that Decode does not write bytes past the end of
 415                 // gotBuf[:totalLen].
 416                 //
 417                 // The magic number 37 was chosen because it is prime. A more 'natural'
 418                 // number like 32 might lead to a false negative if, for example, a
 419                 // byte was incorrectly copied 4*8 bytes later.
 420                 notPresentBase = 0xa0
 421                 notPresentLen  = 37
 422         )
 423         var gotBuf, wantBuf, inputBuf [128]byte
 424         for length := 1; length <= 18; length++ {
 425                 for offset := 1; offset <= 18; offset++ {
 426                 loop:
 427                         for suffixLen := 0; suffixLen <= 18; suffixLen++ {
 428                                 totalLen := len(prefix) + length + suffixLen
 429
 430                                 inputLen := binary.PutUvarint(inputBuf[:], uint64(totalLen))
 431                                 inputBuf[inputLen] = tagLiteral + 4*byte(len(prefix)-1)
 432                                 inputLen++
 433                                 inputLen += copy(inputBuf[inputLen:], prefix)
 434                                 inputBuf[inputLen+0] = tagCopy2 + 4*byte(length-1)
 435                                 inputBuf[inputLen+1] = byte(offset)
 436                                 inputBuf[inputLen+2] = 0x00
 437                                 inputLen += 3
 438                                 if suffixLen > 0 {
 439                                         inputBuf[inputLen] = tagLiteral + 4*byte(suffixLen-1)
 440                                         inputLen++
 441                                         inputLen += copy(inputBuf[inputLen:], suffix[:suffixLen])
 442                                 }
 443                                 input := inputBuf[:inputLen]
 444
 445                                 for i := range gotBuf {
 446                                         gotBuf[i] = byte(notPresentBase + i%notPresentLen)
 447                                 }
 448                                 got, err := Decode(gotBuf[:], input)
 449                                 if err != nil {
 450                                         t.Errorf("length=%d, offset=%d; suffixLen=%d: %v", length, offset, suffixLen, err)
 451                                         continue
 452                                 }
 453
 454                                 wantLen := 0
 455                                 wantLen += copy(wantBuf[wantLen:], prefix)
 456                                 for i := 0; i < length; i++ {
 457                                         wantBuf[wantLen] = wantBuf[wantLen-offset]
 458                                         wantLen++
 459                                 }
 460                                 wantLen += copy(wantBuf[wantLen:], suffix[:suffixLen])
 461                                 want := wantBuf[:wantLen]
 462
 463                                 for _, x := range input {
 464                                         if notPresentBase <= x && x < notPresentBase+notPresentLen {
 465                                                 t.Errorf("length=%d, offset=%d; suffixLen=%d: input shouldn't contain %#02x\ninput: % x",
 466                                                         length, offset, suffixLen, x, input)
 467                                                 continue loop
 468                                         }
 469                                 }
 470                                 for i, x := range gotBuf {
 471                                         if i < totalLen {
 472                                                 continue
 473                                         }
 474                                         if w := byte(notPresentBase + i%notPresentLen); x != w {
 475                                                 t.Errorf("length=%d, offset=%d; suffixLen=%d; totalLen=%d: "+
 476                                                         "Decode overrun: gotBuf[%d] was modified: got %#02x, want %#02x\ngotBuf: % x",
 477                                                         length, offset, suffixLen, totalLen, i, x, w, gotBuf)
 478                                                 continue loop
 479                                         }
 480                                 }
 481                                 for _, x := range want {
 482                                         if notPresentBase <= x && x < notPresentBase+notPresentLen {
 483                                                 t.Errorf("length=%d, offset=%d; suffixLen=%d: want shouldn't contain %#02x\nwant: % x",
 484                                                         length, offset, suffixLen, x, want)
 485                                                 continue loop
 486                                         }
 487                                 }
 488
 489                                 if !bytes.Equal(got, want) {
 490                                         t.Errorf("length=%d, offset=%d; suffixLen=%d:\ninput % x\ngot   % x\nwant  % x",
 491                                                 length, offset, suffixLen, input, got, want)
 492                                         continue
 493                                 }
 494                         }
 495                 }
 496         }
 497 }
 498
 499 const (
 500         goldenText       = "Mark.Twain-Tom.Sawyer.txt"
 501         goldenCompressed = goldenText + ".rawsnappy"
 502 )
 503
 504 func TestDecodeGoldenInput(t *testing.T) {
 505         tDir := filepath.FromSlash(*testdataDir)
 506         src, err := ioutil.ReadFile(filepath.Join(tDir, goldenCompressed))
 507         if err != nil {
 508                 t.Fatalf("ReadFile: %v", err)
 509         }
 510         got, err := Decode(nil, src)
 511         if err != nil {
 512                 t.Fatalf("Decode: %v", err)
 513         }
 514         want, err := ioutil.ReadFile(filepath.Join(tDir, goldenText))
 515         if err != nil {
 516                 t.Fatalf("ReadFile: %v", err)
 517         }
 518         if err := cmp(got, want); err != nil {
 519                 t.Fatal(err)
 520         }
 521 }
 522
 523 func TestEncodeGoldenInput(t *testing.T) {
 524         tDir := filepath.FromSlash(*testdataDir)
 525         src, err := ioutil.ReadFile(filepath.Join(tDir, goldenText))
 526         if err != nil {
 527                 t.Fatalf("ReadFile: %v", err)
 528         }
 529         got := Encode(nil, src)
 530         want, err := ioutil.ReadFile(filepath.Join(tDir, goldenCompressed))
 531         if err != nil {
 532                 t.Fatalf("ReadFile: %v", err)
 533         }
 534         if err := cmp(got, want); err != nil {
 535                 t.Fatal(err)
 536         }
 537 }
 538
 539 func TestExtendMatchGoldenInput(t *testing.T) {
 540         tDir := filepath.FromSlash(*testdataDir)
 541         src, err := ioutil.ReadFile(filepath.Join(tDir, goldenText))
 542         if err != nil {
 543                 t.Fatalf("ReadFile: %v", err)
 544         }
 545         for i, tc := range extendMatchGoldenTestCases {
 546                 got := extendMatch(src, tc.i, tc.j)
 547                 if got != tc.want {
 548                         t.Errorf("test #%d: i, j = %5d, %5d: got %5d (= j + %6d), want %5d (= j + %6d)",
 549                                 i, tc.i, tc.j, got, got-tc.j, tc.want, tc.want-tc.j)
 550                 }
 551         }
 552 }
 553
 554 func TestExtendMatch(t *testing.T) {
 555         // ref is a simple, reference implementation of extendMatch.
 556         ref := func(src []byte, i, j int) int {
 557                 for ; j < len(src) && src[i] == src[j]; i, j = i+1, j+1 {
 558                 }
 559                 return j
 560         }
 561
 562         nums := []int{0, 1, 2, 7, 8, 9, 29, 30, 31, 32, 33, 34, 38, 39, 40}
 563         for yIndex := 40; yIndex > 30; yIndex-- {
 564                 xxx := bytes.Repeat([]byte("x"), 40)
 565                 if yIndex < len(xxx) {
 566                         xxx[yIndex] = 'y'
 567                 }
 568                 for _, i := range nums {
 569                         for _, j := range nums {
 570                                 if i >= j {
 571                                         continue
 572                                 }
 573                                 got := extendMatch(xxx, i, j)
 574                                 want := ref(xxx, i, j)
 575                                 if got != want {
 576                                         t.Errorf("yIndex=%d, i=%d, j=%d: got %d, want %d", yIndex, i, j, got, want)
 577                                 }
 578                         }
 579                 }
 580         }
 581 }
 582
 583 const snappytoolCmdName = "cmd/snappytool/snappytool"
 584
 585 func skipTestSameEncodingAsCpp() (msg string) {
 586         if !goEncoderShouldMatchCppEncoder {
 587                 return fmt.Sprintf("skipping testing that the encoding is byte-for-byte identical to C++: GOARCH=%s", runtime.GOARCH)
 588         }
 589         if _, err := os.Stat(snappytoolCmdName); err != nil {
 590                 return fmt.Sprintf("could not find snappytool: %v", err)
 591         }
 592         return ""
 593 }
 594
 595 func runTestSameEncodingAsCpp(src []byte) error {
 596         got := Encode(nil, src)
 597
 598         cmd := exec.Command(snappytoolCmdName, "-e")
 599         cmd.Stdin = bytes.NewReader(src)
 600         want, err := cmd.Output()
 601         if err != nil {
 602                 return fmt.Errorf("could not run snappytool: %v", err)
 603         }
 604         return cmp(got, want)
 605 }
 606
 607 func TestSameEncodingAsCppShortCopies(t *testing.T) {
 608         if msg := skipTestSameEncodingAsCpp(); msg != "" {
 609                 t.Skip(msg)
 610         }
 611         src := bytes.Repeat([]byte{'a'}, 20)
 612         for i := 0; i <= len(src); i++ {
 613                 if err := runTestSameEncodingAsCpp(src[:i]); err != nil {
 614                         t.Errorf("i=%d: %v", i, err)
 615                 }
 616         }
 617 }
 618
 619 func TestSameEncodingAsCppLongFiles(t *testing.T) {
 620         if msg := skipTestSameEncodingAsCpp(); msg != "" {
 621                 t.Skip(msg)
 622         }
 623         bDir := filepath.FromSlash(*benchdataDir)
 624         failed := false
 625         for i, tf := range testFiles {
 626                 if err := downloadBenchmarkFiles(t, tf.filename); err != nil {
 627                         t.Fatalf("failed to download testdata: %s", err)
 628                 }
 629                 data := readFile(t, filepath.Join(bDir, tf.filename))
 630                 if n := tf.sizeLimit; 0 < n && n < len(data) {
 631                         data = data[:n]
 632                 }
 633                 if err := runTestSameEncodingAsCpp(data); err != nil {
 634                         t.Errorf("i=%d: %v", i, err)
 635                         failed = true
 636                 }
 637         }
 638         if failed {
 639                 t.Errorf("was the snappytool program built against the C++ snappy library version " +
 640                         "d53de187 or later, commited on 2016-04-05? See " +
 641                         "https://github.com/google/snappy/commit/d53de18799418e113e44444252a39b12a0e4e0cc")
 642         }
 643 }
 644
 645 // TestSlowForwardCopyOverrun tests the "expand the pattern" algorithm
 646 // described in decode_amd64.s and its claim of a 10 byte overrun worst case.
 647 func TestSlowForwardCopyOverrun(t *testing.T) {
 648         const base = 100
 649
 650         for length := 1; length < 18; length++ {
 651                 for offset := 1; offset < 18; offset++ {
 652                         highWaterMark := base
 653                         d := base
 654                         l := length
 655                         o := offset
 656
 657                         // makeOffsetAtLeast8
 658                         for o < 8 {
 659                                 if end := d + 8; highWaterMark < end {
 660                                         highWaterMark = end
 661                                 }
 662                                 l -= o
 663                                 d += o
 664                                 o += o
 665                         }
 666
 667                         // fixUpSlowForwardCopy
 668                         a := d
 669                         d += l
 670
 671                         // finishSlowForwardCopy
 672                         for l > 0 {
 673                                 if end := a + 8; highWaterMark < end {
 674                                         highWaterMark = end
 675                                 }
 676                                 a += 8
 677                                 l -= 8
 678                         }
 679
 680                         dWant := base + length
 681                         overrun := highWaterMark - dWant
 682                         if d != dWant || overrun < 0 || 10 < overrun {
 683                                 t.Errorf("length=%d, offset=%d: d and overrun: got (%d, %d), want (%d, something in [0, 10])",
 684                                         length, offset, d, overrun, dWant)
 685                         }
 686                 }
 687         }
 688 }
 689
 690 // TestEncodeNoiseThenRepeats encodes input for which the first half is very
 691 // incompressible and the second half is very compressible. The encoded form's
 692 // length should be closer to 50% of the original length than 100%.
 693 func TestEncodeNoiseThenRepeats(t *testing.T) {
 694         for _, origLen := range []int{256 * 1024, 2048 * 1024} {
 695                 src := make([]byte, origLen)
 696                 rng := rand.New(rand.NewSource(1))
 697                 firstHalf, secondHalf := src[:origLen/2], src[origLen/2:]
 698                 for i := range firstHalf {
 699                         firstHalf[i] = uint8(rng.Intn(256))
 700                 }
 701                 for i := range secondHalf {
 702                         secondHalf[i] = uint8(i >> 8)
 703                 }
 704                 dst := Encode(nil, src)
 705                 if got, want := len(dst), origLen*3/4; got >= want {
 706                         t.Errorf("origLen=%d: got %d encoded bytes, want less than %d", origLen, got, want)
 707                 }
 708         }
 709 }
 710
 711 func TestFramingFormat(t *testing.T) {
 712         // src is comprised of alternating 1e5-sized sequences of random
 713         // (incompressible) bytes and repeated (compressible) bytes. 1e5 was chosen
 714         // because it is larger than maxBlockSize (64k).
 715         src := make([]byte, 1e6)
 716         rng := rand.New(rand.NewSource(1))
 717         for i := 0; i < 10; i++ {
 718                 if i%2 == 0 {
 719                         for j := 0; j < 1e5; j++ {
 720                                 src[1e5*i+j] = uint8(rng.Intn(256))
 721                         }
 722                 } else {
 723                         for j := 0; j < 1e5; j++ {
 724                                 src[1e5*i+j] = uint8(i)
 725                         }
 726                 }
 727         }
 728
 729         buf := new(bytes.Buffer)
 730         if _, err := NewWriter(buf).Write(src); err != nil {
 731                 t.Fatalf("Write: encoding: %v", err)
 732         }
 733         dst, err := ioutil.ReadAll(NewReader(buf))
 734         if err != nil {
 735                 t.Fatalf("ReadAll: decoding: %v", err)
 736         }
 737         if err := cmp(dst, src); err != nil {
 738                 t.Fatal(err)
 739         }
 740 }
 741
 742 func TestWriterGoldenOutput(t *testing.T) {
 743         buf := new(bytes.Buffer)
 744         w := NewBufferedWriter(buf)
 745         defer w.Close()
 746         w.Write([]byte("abcd")) // Not compressible.
 747         w.Flush()
 748         w.Write(bytes.Repeat([]byte{'A'}, 150)) // Compressible.
 749         w.Flush()
 750         // The next chunk is also compressible, but a naive, greedy encoding of the
 751         // overall length 67 copy as a length 64 copy (the longest expressible as a
 752         // tagCopy1 or tagCopy2) plus a length 3 remainder would be two 3-byte
 753         // tagCopy2 tags (6 bytes), since the minimum length for a tagCopy1 is 4
 754         // bytes. Instead, we could do it shorter, in 5 bytes: a 3-byte tagCopy2
 755         // (of length 60) and a 2-byte tagCopy1 (of length 7).
 756         w.Write(bytes.Repeat([]byte{'B'}, 68))
 757         w.Write([]byte("efC"))                 // Not compressible.
 758         w.Write(bytes.Repeat([]byte{'C'}, 20)) // Compressible.
 759         w.Write(bytes.Repeat([]byte{'B'}, 20)) // Compressible.
 760         w.Write([]byte("g"))                   // Not compressible.
 761         w.Flush()
 762
 763         got := buf.String()
 764         want := strings.Join([]string{
 765                 magicChunk,
 766                 "\x01\x08\x00\x00", // Uncompressed chunk, 8 bytes long (including 4 byte checksum).
 767                 "\x68\x10\xe6\xb6", // Checksum.
 768                 "\x61\x62\x63\x64", // Uncompressed payload: "abcd".
 769                 "\x00\x11\x00\x00", // Compressed chunk, 17 bytes long (including 4 byte checksum).
 770                 "\x5f\xeb\xf2\x10", // Checksum.
 771                 "\x96\x01",         // Compressed payload: Uncompressed length (varint encoded): 150.
 772                 "\x00\x41",         // Compressed payload: tagLiteral, length=1,  "A".
 773                 "\xfe\x01\x00",     // Compressed payload: tagCopy2,   length=64, offset=1.
 774                 "\xfe\x01\x00",     // Compressed payload: tagCopy2,   length=64, offset=1.
 775                 "\x52\x01\x00",     // Compressed payload: tagCopy2,   length=21, offset=1.
 776                 "\x00\x18\x00\x00", // Compressed chunk, 24 bytes long (including 4 byte checksum).
 777                 "\x30\x85\x69\xeb", // Checksum.
 778                 "\x70",             // Compressed payload: Uncompressed length (varint encoded): 112.
 779                 "\x00\x42",         // Compressed payload: tagLiteral, length=1,  "B".
 780                 "\xee\x01\x00",     // Compressed payload: tagCopy2,   length=60, offset=1.
 781                 "\x0d\x01",         // Compressed payload: tagCopy1,   length=7,  offset=1.
 782                 "\x08\x65\x66\x43", // Compressed payload: tagLiteral, length=3,  "efC".
 783                 "\x4e\x01\x00",     // Compressed payload: tagCopy2,   length=20, offset=1.
 784                 "\x4e\x5a\x00",     // Compressed payload: tagCopy2,   length=20, offset=90.
 785                 "\x00\x67",         // Compressed payload: tagLiteral, length=1,  "g".
 786         }, "")
 787         if got != want {
 788                 t.Fatalf("\ngot:  % x\nwant: % x", got, want)
 789         }
 790 }
 791
 792 func TestEmitLiteral(t *testing.T) {
 793         testCases := []struct {
 794                 length int
 795                 want   string
 796         }{
 797                 {1, "\x00"},
 798                 {2, "\x04"},
 799                 {59, "\xe8"},
 800                 {60, "\xec"},
 801                 {61, "\xf0\x3c"},
 802                 {62, "\xf0\x3d"},
 803                 {254, "\xf0\xfd"},
 804                 {255, "\xf0\xfe"},
 805                 {256, "\xf0\xff"},
 806                 {257, "\xf4\x00\x01"},
 807                 {65534, "\xf4\xfd\xff"},
 808                 {65535, "\xf4\xfe\xff"},
 809                 {65536, "\xf4\xff\xff"},
 810         }
 811
 812         dst := make([]byte, 70000)
 813         nines := bytes.Repeat([]byte{0x99}, 65536)
 814         for _, tc := range testCases {
 815                 lit := nines[:tc.length]
 816                 n := emitLiteral(dst, lit)
 817                 if !bytes.HasSuffix(dst[:n], lit) {
 818                         t.Errorf("length=%d: did not end with that many literal bytes", tc.length)
 819                         continue
 820                 }
 821                 got := string(dst[:n-tc.length])
 822                 if got != tc.want {
 823                         t.Errorf("length=%d:\ngot  % x\nwant % x", tc.length, got, tc.want)
 824                         continue
 825                 }
 826         }
 827 }
 828
 829 func TestEmitCopy(t *testing.T) {
 830         testCases := []struct {
 831                 offset int
 832                 length int
 833                 want   string
 834         }{
 835                 {8, 04, "\x01\x08"},
 836                 {8, 11, "\x1d\x08"},
 837                 {8, 12, "\x2e\x08\x00"},
 838                 {8, 13, "\x32\x08\x00"},
 839                 {8, 59, "\xea\x08\x00"},
 840                 {8, 60, "\xee\x08\x00"},
 841                 {8, 61, "\xf2\x08\x00"},
 842                 {8, 62, "\xf6\x08\x00"},
 843                 {8, 63, "\xfa\x08\x00"},
 844                 {8, 64, "\xfe\x08\x00"},
 845                 {8, 65, "\xee\x08\x00\x05\x08"},
 846                 {8, 66, "\xee\x08\x00\x09\x08"},
 847                 {8, 67, "\xee\x08\x00\x0d\x08"},
 848                 {8, 68, "\xfe\x08\x00\x01\x08"},
 849                 {8, 69, "\xfe\x08\x00\x05\x08"},
 850                 {8, 80, "\xfe\x08\x00\x3e\x08\x00"},
 851
 852                 {256, 04, "\x21\x00"},
 853                 {256, 11, "\x3d\x00"},
 854                 {256, 12, "\x2e\x00\x01"},
 855                 {256, 13, "\x32\x00\x01"},
 856                 {256, 59, "\xea\x00\x01"},
 857                 {256, 60, "\xee\x00\x01"},
 858                 {256, 61, "\xf2\x00\x01"},
 859                 {256, 62, "\xf6\x00\x01"},
 860                 {256, 63, "\xfa\x00\x01"},
 861                 {256, 64, "\xfe\x00\x01"},
 862                 {256, 65, "\xee\x00\x01\x25\x00"},
 863                 {256, 66, "\xee\x00\x01\x29\x00"},
 864                 {256, 67, "\xee\x00\x01\x2d\x00"},
 865                 {256, 68, "\xfe\x00\x01\x21\x00"},
 866                 {256, 69, "\xfe\x00\x01\x25\x00"},
 867                 {256, 80, "\xfe\x00\x01\x3e\x00\x01"},
 868
 869                 {2048, 04, "\x0e\x00\x08"},
 870                 {2048, 11, "\x2a\x00\x08"},
 871                 {2048, 12, "\x2e\x00\x08"},
 872                 {2048, 13, "\x32\x00\x08"},
 873                 {2048, 59, "\xea\x00\x08"},
 874                 {2048, 60, "\xee\x00\x08"},
 875                 {2048, 61, "\xf2\x00\x08"},
 876                 {2048, 62, "\xf6\x00\x08"},
 877                 {2048, 63, "\xfa\x00\x08"},
 878                 {2048, 64, "\xfe\x00\x08"},
 879                 {2048, 65, "\xee\x00\x08\x12\x00\x08"},
 880                 {2048, 66, "\xee\x00\x08\x16\x00\x08"},
 881                 {2048, 67, "\xee\x00\x08\x1a\x00\x08"},
 882                 {2048, 68, "\xfe\x00\x08\x0e\x00\x08"},
 883                 {2048, 69, "\xfe\x00\x08\x12\x00\x08"},
 884                 {2048, 80, "\xfe\x00\x08\x3e\x00\x08"},
 885         }
 886
 887         dst := make([]byte, 1024)
 888         for _, tc := range testCases {
 889                 n := emitCopy(dst, tc.offset, tc.length)
 890                 got := string(dst[:n])
 891                 if got != tc.want {
 892                         t.Errorf("offset=%d, length=%d:\ngot  % x\nwant % x", tc.offset, tc.length, got, tc.want)
 893                 }
 894         }
 895 }
 896
 897 func TestNewBufferedWriter(t *testing.T) {
 898         // Test all 32 possible sub-sequences of these 5 input slices.
 899         //
 900         // Their lengths sum to 400,000, which is over 6 times the Writer ibuf
 901         // capacity: 6 * maxBlockSize is 393,216.
 902         inputs := [][]byte{
 903                 bytes.Repeat([]byte{'a'}, 40000),
 904                 bytes.Repeat([]byte{'b'}, 150000),
 905                 bytes.Repeat([]byte{'c'}, 60000),
 906                 bytes.Repeat([]byte{'d'}, 120000),
 907                 bytes.Repeat([]byte{'e'}, 30000),
 908         }
 909 loop:
 910         for i := 0; i < 1<<uint(len(inputs)); i++ {
 911                 var want []byte
 912                 buf := new(bytes.Buffer)
 913                 w := NewBufferedWriter(buf)
 914                 for j, input := range inputs {
 915                         if i&(1<<uint(j)) == 0 {
 916                                 continue
 917                         }
 918                         if _, err := w.Write(input); err != nil {
 919                                 t.Errorf("i=%#02x: j=%d: Write: %v", i, j, err)
 920                                 continue loop
 921                         }
 922                         want = append(want, input...)
 923                 }
 924                 if err := w.Close(); err != nil {
 925                         t.Errorf("i=%#02x: Close: %v", i, err)
 926                         continue
 927                 }
 928                 got, err := ioutil.ReadAll(NewReader(buf))
 929                 if err != nil {
 930                         t.Errorf("i=%#02x: ReadAll: %v", i, err)
 931                         continue
 932                 }
 933                 if err := cmp(got, want); err != nil {
 934                         t.Errorf("i=%#02x: %v", i, err)
 935                         continue
 936                 }
 937         }
 938 }
 939
 940 func TestFlush(t *testing.T) {
 941         buf := new(bytes.Buffer)
 942         w := NewBufferedWriter(buf)
 943         defer w.Close()
 944         if _, err := w.Write(bytes.Repeat([]byte{'x'}, 20)); err != nil {
 945                 t.Fatalf("Write: %v", err)
 946         }
 947         if n := buf.Len(); n != 0 {
 948                 t.Fatalf("before Flush: %d bytes were written to the underlying io.Writer, want 0", n)
 949         }
 950         if err := w.Flush(); err != nil {
 951                 t.Fatalf("Flush: %v", err)
 952         }
 953         if n := buf.Len(); n == 0 {
 954                 t.Fatalf("after Flush: %d bytes were written to the underlying io.Writer, want non-0", n)
 955         }
 956 }
 957
 958 func TestReaderUncompressedDataOK(t *testing.T) {
 959         r := NewReader(strings.NewReader(magicChunk +
 960                 "\x01\x08\x00\x00" + // Uncompressed chunk, 8 bytes long (including 4 byte checksum).
 961                 "\x68\x10\xe6\xb6" + // Checksum.
 962                 "\x61\x62\x63\x64", // Uncompressed payload: "abcd".
 963         ))
 964         g, err := ioutil.ReadAll(r)
 965         if err != nil {
 966                 t.Fatal(err)
 967         }
 968         if got, want := string(g), "abcd"; got != want {
 969                 t.Fatalf("got %q, want %q", got, want)
 970         }
 971 }
 972
 973 func TestReaderUncompressedDataNoPayload(t *testing.T) {
 974         r := NewReader(strings.NewReader(magicChunk +
 975                 "\x01\x04\x00\x00" + // Uncompressed chunk, 4 bytes long.
 976                 "", // No payload; corrupt input.
 977         ))
 978         if _, err := ioutil.ReadAll(r); err != ErrCorrupt {
 979                 t.Fatalf("got %v, want %v", err, ErrCorrupt)
 980         }
 981 }
 982
 983 func TestReaderUncompressedDataTooLong(t *testing.T) {
 984         // https://github.com/google/snappy/blob/master/framing_format.txt section
 985         // 4.3 says that "the maximum legal chunk length... is 65540", or 0x10004.
 986         const n = 0x10005
 987
 988         r := NewReader(strings.NewReader(magicChunk +
 989                 "\x01\x05\x00\x01" + // Uncompressed chunk, n bytes long.
 990                 strings.Repeat("\x00", n),
 991         ))
 992         if _, err := ioutil.ReadAll(r); err != ErrCorrupt {
 993                 t.Fatalf("got %v, want %v", err, ErrCorrupt)
 994         }
 995 }
 996
 997 func TestReaderReset(t *testing.T) {
 998         gold := bytes.Repeat([]byte("All that is gold does not glitter,\n"), 10000)
 999         buf := new(bytes.Buffer)
1000         if _, err := NewWriter(buf).Write(gold); err != nil {
1001                 t.Fatalf("Write: %v", err)
1002         }
1003         encoded, invalid, partial := buf.String(), "invalid", "partial"
1004         r := NewReader(nil)
1005         for i, s := range []string{encoded, invalid, partial, encoded, partial, invalid, encoded, encoded} {
1006                 if s == partial {
1007                         r.Reset(strings.NewReader(encoded))
1008                         if _, err := r.Read(make([]byte, 101)); err != nil {
1009                                 t.Errorf("#%d: %v", i, err)
1010                                 continue
1011                         }
1012                         continue
1013                 }
1014                 r.Reset(strings.NewReader(s))
1015                 got, err := ioutil.ReadAll(r)
1016                 switch s {
1017                 case encoded:
1018                         if err != nil {
1019                                 t.Errorf("#%d: %v", i, err)
1020                                 continue
1021                         }
1022                         if err := cmp(got, gold); err != nil {
1023                                 t.Errorf("#%d: %v", i, err)
1024                                 continue
1025                         }
1026                 case invalid:
1027                         if err == nil {
1028                                 t.Errorf("#%d: got nil error, want non-nil", i)
1029                                 continue
1030                         }
1031                 }
1032         }
1033 }
1034
1035 func TestWriterReset(t *testing.T) {
1036         gold := bytes.Repeat([]byte("Not all those who wander are lost;\n"), 10000)
1037         const n = 20
1038         for _, buffered := range []bool{false, true} {
1039                 var w *Writer
1040                 if buffered {
1041                         w = NewBufferedWriter(nil)
1042                         defer w.Close()
1043                 } else {
1044                         w = NewWriter(nil)
1045                 }
1046
1047                 var gots, wants [][]byte
1048                 failed := false
1049                 for i := 0; i <= n; i++ {
1050                         buf := new(bytes.Buffer)
1051                         w.Reset(buf)
1052                         want := gold[:len(gold)*i/n]
1053                         if _, err := w.Write(want); err != nil {
1054                                 t.Errorf("#%d: Write: %v", i, err)
1055                                 failed = true
1056                                 continue
1057                         }
1058                         if buffered {
1059                                 if err := w.Flush(); err != nil {
1060                                         t.Errorf("#%d: Flush: %v", i, err)
1061                                         failed = true
1062                                         continue
1063                                 }
1064                         }
1065                         got, err := ioutil.ReadAll(NewReader(buf))
1066                         if err != nil {
1067                                 t.Errorf("#%d: ReadAll: %v", i, err)
1068                                 failed = true
1069                                 continue
1070                         }
1071                         gots = append(gots, got)
1072                         wants = append(wants, want)
1073                 }
1074                 if failed {
1075                         continue
1076                 }
1077                 for i := range gots {
1078                         if err := cmp(gots[i], wants[i]); err != nil {
1079                                 t.Errorf("#%d: %v", i, err)
1080                         }
1081                 }
1082         }
1083 }
1084
1085 func TestWriterResetWithoutFlush(t *testing.T) {
1086         buf0 := new(bytes.Buffer)
1087         buf1 := new(bytes.Buffer)
1088         w := NewBufferedWriter(buf0)
1089         if _, err := w.Write([]byte("xxx")); err != nil {
1090                 t.Fatalf("Write #0: %v", err)
1091         }
1092         // Note that we don't Flush the Writer before calling Reset.
1093         w.Reset(buf1)
1094         if _, err := w.Write([]byte("yyy")); err != nil {
1095                 t.Fatalf("Write #1: %v", err)
1096         }
1097         if err := w.Flush(); err != nil {
1098                 t.Fatalf("Flush: %v", err)
1099         }
1100         got, err := ioutil.ReadAll(NewReader(buf1))
1101         if err != nil {
1102                 t.Fatalf("ReadAll: %v", err)
1103         }
1104         if err := cmp(got, []byte("yyy")); err != nil {
1105                 t.Fatal(err)
1106         }
1107 }
1108
1109 type writeCounter int
1110
1111 func (c *writeCounter) Write(p []byte) (int, error) {
1112         *c++
1113         return len(p), nil
1114 }
1115
1116 // TestNumUnderlyingWrites tests that each Writer flush only makes one or two
1117 // Write calls on its underlying io.Writer, depending on whether or not the
1118 // flushed buffer was compressible.
1119 func TestNumUnderlyingWrites(t *testing.T) {
1120         testCases := []struct {
1121                 input []byte
1122                 want  int
1123         }{
1124                 {bytes.Repeat([]byte{'x'}, 100), 1},
1125                 {bytes.Repeat([]byte{'y'}, 100), 1},
1126                 {[]byte("ABCDEFGHIJKLMNOPQRST"), 2},
1127         }
1128
1129         var c writeCounter
1130         w := NewBufferedWriter(&c)
1131         defer w.Close()
1132         for i, tc := range testCases {
1133                 c = 0
1134                 if _, err := w.Write(tc.input); err != nil {
1135                         t.Errorf("#%d: Write: %v", i, err)
1136                         continue
1137                 }
1138                 if err := w.Flush(); err != nil {
1139                         t.Errorf("#%d: Flush: %v", i, err)
1140                         continue
1141                 }
1142                 if int(c) != tc.want {
1143                         t.Errorf("#%d: got %d underlying writes, want %d", i, c, tc.want)
1144                         continue
1145                 }
1146         }
1147 }
1148
1149 func benchDecode(b *testing.B, src []byte) {
1150         encoded := Encode(nil, src)
1151         // Bandwidth is in amount of uncompressed data.
1152         b.SetBytes(int64(len(src)))
1153         b.ResetTimer()
1154         for i := 0; i < b.N; i++ {
1155                 Decode(src, encoded)
1156         }
1157 }
1158
1159 func benchEncode(b *testing.B, src []byte) {
1160         // Bandwidth is in amount of uncompressed data.
1161         b.SetBytes(int64(len(src)))
1162         dst := make([]byte, MaxEncodedLen(len(src)))
1163         b.ResetTimer()
1164         for i := 0; i < b.N; i++ {
1165                 Encode(dst, src)
1166         }
1167 }
1168
1169 func testOrBenchmark(b testing.TB) string {
1170         if _, ok := b.(*testing.B); ok {
1171                 return "benchmark"
1172         }
1173         return "test"
1174 }
1175
1176 func readFile(b testing.TB, filename string) []byte {
1177         src, err := ioutil.ReadFile(filename)
1178         if err != nil {
1179                 b.Skipf("skipping %s: %v", testOrBenchmark(b), err)
1180         }
1181         if len(src) == 0 {
1182                 b.Fatalf("%s has zero length", filename)
1183         }
1184         return src
1185 }
1186
1187 // expand returns a slice of length n containing repeated copies of src.
1188 func expand(src []byte, n int) []byte {
1189         dst := make([]byte, n)
1190         for x := dst; len(x) > 0; {
1191                 i := copy(x, src)
1192                 x = x[i:]
1193         }
1194         return dst
1195 }
1196
1197 func benchWords(b *testing.B, n int, decode bool) {
1198         // Note: the file is OS-language dependent so the resulting values are not
1199         // directly comparable for non-US-English OS installations.
1200         data := expand(readFile(b, "/usr/share/dict/words"), n)
1201         if decode {
1202                 benchDecode(b, data)
1203         } else {
1204                 benchEncode(b, data)
1205         }
1206 }
1207
1208 func BenchmarkWordsDecode1e1(b *testing.B) { benchWords(b, 1e1, true) }
1209 func BenchmarkWordsDecode1e2(b *testing.B) { benchWords(b, 1e2, true) }
1210 func BenchmarkWordsDecode1e3(b *testing.B) { benchWords(b, 1e3, true) }
1211 func BenchmarkWordsDecode1e4(b *testing.B) { benchWords(b, 1e4, true) }
1212 func BenchmarkWordsDecode1e5(b *testing.B) { benchWords(b, 1e5, true) }
1213 func BenchmarkWordsDecode1e6(b *testing.B) { benchWords(b, 1e6, true) }
1214 func BenchmarkWordsEncode1e1(b *testing.B) { benchWords(b, 1e1, false) }
1215 func BenchmarkWordsEncode1e2(b *testing.B) { benchWords(b, 1e2, false) }
1216 func BenchmarkWordsEncode1e3(b *testing.B) { benchWords(b, 1e3, false) }
1217 func BenchmarkWordsEncode1e4(b *testing.B) { benchWords(b, 1e4, false) }
1218 func BenchmarkWordsEncode1e5(b *testing.B) { benchWords(b, 1e5, false) }
1219 func BenchmarkWordsEncode1e6(b *testing.B) { benchWords(b, 1e6, false) }
1220
1221 func BenchmarkRandomEncode(b *testing.B) {
1222         rng := rand.New(rand.NewSource(1))
1223         data := make([]byte, 1<<20)
1224         for i := range data {
1225                 data[i] = uint8(rng.Intn(256))
1226         }
1227         benchEncode(b, data)
1228 }
1229
1230 // testFiles' values are copied directly from
1231 // https://raw.githubusercontent.com/google/snappy/master/snappy_unittest.cc
1232 // The label field is unused in snappy-go.
1233 var testFiles = []struct {
1234         label     string
1235         filename  string
1236         sizeLimit int
1237 }{
1238         {"html", "html", 0},
1239         {"urls", "urls.10K", 0},
1240         {"jpg", "fireworks.jpeg", 0},
1241         {"jpg_200", "fireworks.jpeg", 200},
1242         {"pdf", "paper-100k.pdf", 0},
1243         {"html4", "html_x_4", 0},
1244         {"txt1", "alice29.txt", 0},
1245         {"txt2", "asyoulik.txt", 0},
1246         {"txt3", "lcet10.txt", 0},
1247         {"txt4", "plrabn12.txt", 0},
1248         {"pb", "geo.protodata", 0},
1249         {"gaviota", "kppkn.gtb", 0},
1250 }
1251
1252 const (
1253         // The benchmark data files are at this canonical URL.
1254         benchURL = "https://raw.githubusercontent.com/google/snappy/master/testdata/"
1255 )
1256
1257 func downloadBenchmarkFiles(b testing.TB, basename string) (errRet error) {
1258         bDir := filepath.FromSlash(*benchdataDir)
1259         filename := filepath.Join(bDir, basename)
1260         if stat, err := os.Stat(filename); err == nil && stat.Size() != 0 {
1261                 return nil
1262         }
1263
1264         if !*download {
1265                 b.Skipf("test data not found; skipping %s without the -download flag", testOrBenchmark(b))
1266         }
1267         // Download the official snappy C++ implementation reference test data
1268         // files for benchmarking.
1269         if err := os.MkdirAll(bDir, 0777); err != nil && !os.IsExist(err) {
1270                 return fmt.Errorf("failed to create %s: %s", bDir, err)
1271         }
1272
1273         f, err := os.Create(filename)
1274         if err != nil {
1275                 return fmt.Errorf("failed to create %s: %s", filename, err)
1276         }
1277         defer f.Close()
1278         defer func() {
1279                 if errRet != nil {
1280                         os.Remove(filename)
1281                 }
1282         }()
1283         url := benchURL + basename
1284         resp, err := http.Get(url)
1285         if err != nil {
1286                 return fmt.Errorf("failed to download %s: %s", url, err)
1287         }
1288         defer resp.Body.Close()
1289         if s := resp.StatusCode; s != http.StatusOK {
1290                 return fmt.Errorf("downloading %s: HTTP status code %d (%s)", url, s, http.StatusText(s))
1291         }
1292         _, err = io.Copy(f, resp.Body)
1293         if err != nil {
1294                 return fmt.Errorf("failed to download %s to %s: %s", url, filename, err)
1295         }
1296         return nil
1297 }
1298
1299 func benchFile(b *testing.B, i int, decode bool) {
1300         if err := downloadBenchmarkFiles(b, testFiles[i].filename); err != nil {
1301                 b.Fatalf("failed to download testdata: %s", err)
1302         }
1303         bDir := filepath.FromSlash(*benchdataDir)
1304         data := readFile(b, filepath.Join(bDir, testFiles[i].filename))
1305         if n := testFiles[i].sizeLimit; 0 < n && n < len(data) {
1306                 data = data[:n]
1307         }
1308         if decode {
1309                 benchDecode(b, data)
1310         } else {
1311                 benchEncode(b, data)
1312         }
1313 }
1314
1315 // Naming convention is kept similar to what snappy's C++ implementation uses.
1316 func Benchmark_UFlat0(b *testing.B)  { benchFile(b, 0, true) }
1317 func Benchmark_UFlat1(b *testing.B)  { benchFile(b, 1, true) }
1318 func Benchmark_UFlat2(b *testing.B)  { benchFile(b, 2, true) }
1319 func Benchmark_UFlat3(b *testing.B)  { benchFile(b, 3, true) }
1320 func Benchmark_UFlat4(b *testing.B)  { benchFile(b, 4, true) }
1321 func Benchmark_UFlat5(b *testing.B)  { benchFile(b, 5, true) }
1322 func Benchmark_UFlat6(b *testing.B)  { benchFile(b, 6, true) }
1323 func Benchmark_UFlat7(b *testing.B)  { benchFile(b, 7, true) }
1324 func Benchmark_UFlat8(b *testing.B)  { benchFile(b, 8, true) }
1325 func Benchmark_UFlat9(b *testing.B)  { benchFile(b, 9, true) }
1326 func Benchmark_UFlat10(b *testing.B) { benchFile(b, 10, true) }
1327 func Benchmark_UFlat11(b *testing.B) { benchFile(b, 11, true) }
1328 func Benchmark_ZFlat0(b *testing.B)  { benchFile(b, 0, false) }
1329 func Benchmark_ZFlat1(b *testing.B)  { benchFile(b, 1, false) }
1330 func Benchmark_ZFlat2(b *testing.B)  { benchFile(b, 2, false) }
1331 func Benchmark_ZFlat3(b *testing.B)  { benchFile(b, 3, false) }
1332 func Benchmark_ZFlat4(b *testing.B)  { benchFile(b, 4, false) }
1333 func Benchmark_ZFlat5(b *testing.B)  { benchFile(b, 5, false) }
1334 func Benchmark_ZFlat6(b *testing.B)  { benchFile(b, 6, false) }
1335 func Benchmark_ZFlat7(b *testing.B)  { benchFile(b, 7, false) }
1336 func Benchmark_ZFlat8(b *testing.B)  { benchFile(b, 8, false) }
1337 func Benchmark_ZFlat9(b *testing.B)  { benchFile(b, 9, false) }
1338 func Benchmark_ZFlat10(b *testing.B) { benchFile(b, 10, false) }
1339 func Benchmark_ZFlat11(b *testing.B) { benchFile(b, 11, false) }
1340
1341 func BenchmarkExtendMatch(b *testing.B) {
1342         tDir := filepath.FromSlash(*testdataDir)
1343         src, err := ioutil.ReadFile(filepath.Join(tDir, goldenText))
1344         if err != nil {
1345                 b.Fatalf("ReadFile: %v", err)
1346         }
1347         b.ResetTimer()
1348         for i := 0; i < b.N; i++ {
1349                 for _, tc := range extendMatchGoldenTestCases {
1350                         extendMatch(src, tc.i, tc.j)
1351                 }
1352         }
1353 }