1// Copyright 2019+ Klaus Post. All rights reserved.
2// License information can be found in the LICENSE file.
3// Based on work by Yann Collet, released under BSD License.
4
5package zstd
6
7import (
8	"bufio"
9	"bytes"
10	"encoding/binary"
11	"encoding/hex"
12	"fmt"
13	"io"
14	"io/ioutil"
15	"log"
16	"math/rand"
17	"os"
18	"path/filepath"
19	"reflect"
20	"runtime"
21	"strings"
22	"sync"
23	"testing"
24	"time"
25
26	// "github.com/DataDog/zstd"
27	// zstd "github.com/valyala/gozstd"
28
29	"github.com/klauspost/compress/zip"
30	"github.com/klauspost/compress/zstd/internal/xxhash"
31)
32
33func TestNewReaderMismatch(t *testing.T) {
34	// To identify a potential decoding error, do the following steps:
35	// 1) Place the compressed file in testdata, eg 'testdata/backup.bin.zst'
36	// 2) Decompress the file to using zstd, so it will be named 'testdata/backup.bin'
37	// 3) Run the test. A hash file will be generated 'testdata/backup.bin.hash'
38	// 4) The decoder will also run and decode the file. It will stop as soon as a mismatch is found.
39	// The hash file will be reused between runs if present.
40	const baseFile = "testdata/backup.bin"
41	const blockSize = 1024
42	hashes, err := ioutil.ReadFile(baseFile + ".hash")
43	if os.IsNotExist(err) {
44		// Create the hash file.
45		f, err := os.Open(baseFile)
46		if os.IsNotExist(err) {
47			t.Skip("no decompressed file found")
48			return
49		}
50		defer f.Close()
51		br := bufio.NewReader(f)
52		var tmp [8]byte
53		xx := xxhash.New()
54		for {
55			xx.Reset()
56			buf := make([]byte, blockSize)
57			n, err := io.ReadFull(br, buf)
58			if err != nil {
59				if err != io.EOF && err != io.ErrUnexpectedEOF {
60					t.Fatal(err)
61				}
62			}
63			if n > 0 {
64				_, _ = xx.Write(buf[:n])
65				binary.LittleEndian.PutUint64(tmp[:], xx.Sum64())
66				hashes = append(hashes, tmp[4:]...)
67			}
68			if n != blockSize {
69				break
70			}
71		}
72		err = ioutil.WriteFile(baseFile+".hash", hashes, os.ModePerm)
73		if err != nil {
74			// We can continue for now
75			t.Error(err)
76		}
77		t.Log("Saved", len(hashes)/4, "hashes as", baseFile+".hash")
78	}
79
80	f, err := os.Open(baseFile + ".zst")
81	if os.IsNotExist(err) {
82		t.Skip("no compressed file found")
83		return
84	}
85	defer f.Close()
86	dec, err := NewReader(f, WithDecoderConcurrency(1))
87	if err != nil {
88		t.Fatal(err)
89	}
90	defer dec.Close()
91	var tmp [8]byte
92	xx := xxhash.New()
93	var cHash int
94	for {
95		xx.Reset()
96		buf := make([]byte, blockSize)
97		n, err := io.ReadFull(dec, buf)
98		if err != nil {
99			if err != io.EOF && err != io.ErrUnexpectedEOF {
100				t.Fatal("block", cHash, "err:", err)
101			}
102		}
103		if n > 0 {
104			if cHash+4 > len(hashes) {
105				extra, _ := io.Copy(ioutil.Discard, dec)
106				t.Fatal("not enough hashes (length mismatch). Only have", len(hashes)/4, "hashes. Got block of", n, "bytes and", extra, "bytes still on stream.")
107			}
108			_, _ = xx.Write(buf[:n])
109			binary.LittleEndian.PutUint64(tmp[:], xx.Sum64())
110			want, got := hashes[cHash:cHash+4], tmp[4:]
111			if !bytes.Equal(want, got) {
112				org, err := os.Open(baseFile)
113				if err == nil {
114					const sizeBack = 8 << 20
115					defer org.Close()
116					start := int64(cHash)/4*blockSize - sizeBack
117					if start < 0 {
118						start = 0
119					}
120					_, err = org.Seek(start, io.SeekStart)
121					buf2 := make([]byte, sizeBack+1<<20)
122					n, _ := io.ReadFull(org, buf2)
123					if n > 0 {
124						err = ioutil.WriteFile(baseFile+".section", buf2[:n], os.ModePerm)
125						if err == nil {
126							t.Log("Wrote problematic section to", baseFile+".section")
127						}
128					}
129				}
130
131				t.Fatal("block", cHash/4, "offset", cHash/4*blockSize, "hash mismatch, want:", hex.EncodeToString(want), "got:", hex.EncodeToString(got))
132			}
133			cHash += 4
134		}
135		if n != blockSize {
136			break
137		}
138	}
139	t.Log("Output matched")
140}
141
142func TestNewDecoder(t *testing.T) {
143	defer timeout(60 * time.Second)()
144	testDecoderFile(t, "testdata/decoder.zip")
145	dec, err := NewReader(nil)
146	if err != nil {
147		t.Fatal(err)
148	}
149	testDecoderDecodeAll(t, "testdata/decoder.zip", dec)
150}
151
152func TestNewDecoderMemory(t *testing.T) {
153	defer timeout(60 * time.Second)()
154	var testdata bytes.Buffer
155	enc, err := NewWriter(&testdata, WithWindowSize(64<<10), WithSingleSegment(false))
156	if err != nil {
157		t.Fatal(err)
158	}
159	// Write 256KB
160	for i := 0; i < 256; i++ {
161		tmp := strings.Repeat(string([]byte{byte(i)}), 1024)
162		_, err := enc.Write([]byte(tmp))
163		if err != nil {
164			t.Fatal(err)
165		}
166	}
167	err = enc.Close()
168	if err != nil {
169		t.Fatal(err)
170	}
171
172	var n = 5000
173	if testing.Short() {
174		n = 200
175	}
176
177	var before, after runtime.MemStats
178	runtime.GC()
179	runtime.ReadMemStats(&before)
180
181	var decs = make([]*Decoder, n)
182	for i := range decs {
183		// Wrap in NopCloser to avoid shortcut.
184		input := ioutil.NopCloser(bytes.NewBuffer(testdata.Bytes()))
185		decs[i], err = NewReader(input, WithDecoderConcurrency(1), WithDecoderLowmem(true))
186		if err != nil {
187			t.Fatal(err)
188		}
189	}
190
191	// 32K buffer
192	var tmp [128 << 10]byte
193	for i := range decs {
194		_, err := io.ReadFull(decs[i], tmp[:])
195		if err != nil {
196			t.Fatal(err)
197		}
198	}
199
200	runtime.GC()
201	runtime.ReadMemStats(&after)
202	size := (after.HeapInuse - before.HeapInuse) / uint64(n) / 1024
203	t.Log(size, "KiB per decoder")
204	// This is not exact science, but fail if we suddenly get more than 2x what we expect.
205	if size > 221*2 && !testing.Short() {
206		t.Errorf("expected < 221KB per decoder, got %d", size)
207	}
208
209	for _, dec := range decs {
210		dec.Close()
211	}
212}
213
214func TestNewDecoderGood(t *testing.T) {
215	defer timeout(30 * time.Second)()
216	testDecoderFile(t, "testdata/good.zip")
217	dec, err := NewReader(nil)
218	if err != nil {
219		t.Fatal(err)
220	}
221	testDecoderDecodeAll(t, "testdata/good.zip", dec)
222}
223
224func TestNewDecoderBad(t *testing.T) {
225	defer timeout(10 * time.Second)()
226	dec, err := NewReader(nil)
227	if err != nil {
228		t.Fatal(err)
229	}
230	testDecoderDecodeAllError(t, "testdata/bad.zip", dec)
231}
232
233func TestNewDecoderLarge(t *testing.T) {
234	testDecoderFile(t, "testdata/large.zip")
235	dec, err := NewReader(nil)
236	if err != nil {
237		t.Fatal(err)
238	}
239	testDecoderDecodeAll(t, "testdata/large.zip", dec)
240}
241
242func TestNewReaderRead(t *testing.T) {
243	dec, err := NewReader(nil)
244	if err != nil {
245		t.Fatal(err)
246	}
247	defer dec.Close()
248	_, err = dec.Read([]byte{0})
249	if err == nil {
250		t.Fatal("Wanted error on uninitialized read, got nil")
251	}
252	t.Log("correctly got error", err)
253}
254
255func TestNewDecoderBig(t *testing.T) {
256	if testing.Short() {
257		t.SkipNow()
258	}
259	file := "testdata/zstd-10kfiles.zip"
260	if _, err := os.Stat(file); os.IsNotExist(err) {
261		t.Skip("To run extended tests, download https://files.klauspost.com/compress/zstd-10kfiles.zip \n" +
262			"and place it in " + file + "\n" + "Running it requires about 5GB of RAM")
263	}
264	testDecoderFile(t, file)
265	dec, err := NewReader(nil)
266	if err != nil {
267		t.Fatal(err)
268	}
269	testDecoderDecodeAll(t, file, dec)
270}
271
272func TestNewDecoderBigFile(t *testing.T) {
273	if testing.Short() {
274		t.SkipNow()
275	}
276	file := "testdata/enwik9.zst"
277	const wantSize = 1000000000
278	if _, err := os.Stat(file); os.IsNotExist(err) {
279		t.Skip("To run extended tests, download http://mattmahoney.net/dc/enwik9.zip unzip it \n" +
280			"compress it with 'zstd -15 -T0 enwik9' and place it in " + file)
281	}
282	f, err := os.Open(file)
283	if err != nil {
284		t.Fatal(err)
285	}
286	defer f.Close()
287	start := time.Now()
288	dec, err := NewReader(f)
289	if err != nil {
290		t.Fatal(err)
291	}
292	n, err := io.Copy(ioutil.Discard, dec)
293	if err != nil {
294		t.Fatal(err)
295	}
296	if n != wantSize {
297		t.Errorf("want size %d, got size %d", wantSize, n)
298	}
299	elapsed := time.Since(start)
300	mbpersec := (float64(n) / (1024 * 1024)) / (float64(elapsed) / (float64(time.Second)))
301	t.Logf("Decoded %d bytes with %f.2 MB/s", n, mbpersec)
302}
303
304func TestNewDecoderSmallFile(t *testing.T) {
305	if testing.Short() {
306		t.SkipNow()
307	}
308	file := "testdata/z000028.zst"
309	const wantSize = 39807
310	f, err := os.Open(file)
311	if err != nil {
312		t.Fatal(err)
313	}
314	defer f.Close()
315	start := time.Now()
316	dec, err := NewReader(f)
317	if err != nil {
318		t.Fatal(err)
319	}
320	defer dec.Close()
321	n, err := io.Copy(ioutil.Discard, dec)
322	if err != nil {
323		t.Fatal(err)
324	}
325	if n != wantSize {
326		t.Errorf("want size %d, got size %d", wantSize, n)
327	}
328	mbpersec := (float64(n) / (1024 * 1024)) / (float64(time.Since(start)) / (float64(time.Second)))
329	t.Logf("Decoded %d bytes with %f.2 MB/s", n, mbpersec)
330}
331
332type readAndBlock struct {
333	buf     []byte
334	unblock chan struct{}
335}
336
337func (r *readAndBlock) Read(p []byte) (int, error) {
338	n := copy(p, r.buf)
339	if n == 0 {
340		<-r.unblock
341		return 0, io.EOF
342	}
343	r.buf = r.buf[n:]
344	return n, nil
345}
346
347func TestNewDecoderFlushed(t *testing.T) {
348	if testing.Short() {
349		t.SkipNow()
350	}
351	file := "testdata/z000028.zst"
352	payload, err := ioutil.ReadFile(file)
353	if err != nil {
354		t.Fatal(err)
355	}
356	payload = append(payload, payload...) //2x
357	payload = append(payload, payload...) //4x
358	payload = append(payload, payload...) //8x
359	rng := rand.New(rand.NewSource(0x1337))
360	runs := 100
361	if testing.Short() {
362		runs = 5
363	}
364	enc, err := NewWriter(nil, WithWindowSize(128<<10))
365	if err != nil {
366		t.Fatal(err)
367	}
368	defer enc.Close()
369	for i := 0; i < runs; i++ {
370		wantSize := rng.Intn(len(payload)-1) + 1
371		t.Run(fmt.Sprint("size-", wantSize), func(t *testing.T) {
372			var encoded bytes.Buffer
373			enc.Reset(&encoded)
374			_, err := enc.Write(payload[:wantSize])
375			if err != nil {
376				t.Fatal(err)
377			}
378			err = enc.Flush()
379			if err != nil {
380				t.Fatal(err)
381			}
382
383			// We must be able to read back up until the flush...
384			r := readAndBlock{
385				buf:     encoded.Bytes(),
386				unblock: make(chan struct{}),
387			}
388			defer timeout(5 * time.Second)()
389			dec, err := NewReader(&r)
390			if err != nil {
391				t.Fatal(err)
392			}
393			defer dec.Close()
394			defer close(r.unblock)
395			readBack := 0
396			dst := make([]byte, 1024)
397			for readBack < wantSize {
398				// Read until we have enough.
399				n, err := dec.Read(dst)
400				if err != nil {
401					t.Fatal(err)
402				}
403				readBack += n
404			}
405		})
406	}
407}
408
409func TestDecoderRegression(t *testing.T) {
410	defer timeout(160 * time.Second)()
411	data, err := ioutil.ReadFile("testdata/regression.zip")
412	if err != nil {
413		t.Fatal(err)
414	}
415	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
416	if err != nil {
417		t.Fatal(err)
418	}
419	dec, err := NewReader(nil, WithDecoderConcurrency(1), WithDecoderLowmem(true), WithDecoderMaxMemory(1<<20))
420	if err != nil {
421		t.Error(err)
422		return
423	}
424	defer dec.Close()
425	for i, tt := range zr.File {
426		if !strings.HasSuffix(tt.Name, "") || (testing.Short() && i > 10) {
427			continue
428		}
429		t.Run("Reader-"+tt.Name, func(t *testing.T) {
430			r, err := tt.Open()
431			if err != nil {
432				t.Error(err)
433				return
434			}
435			err = dec.Reset(r)
436			if err != nil {
437				t.Error(err)
438				return
439			}
440			got, gotErr := ioutil.ReadAll(dec)
441			t.Log("Received:", len(got), gotErr)
442
443			// Check a fresh instance
444			r, err = tt.Open()
445			if err != nil {
446				t.Error(err)
447				return
448			}
449			decL, err := NewReader(r, WithDecoderConcurrency(1), WithDecoderLowmem(true), WithDecoderMaxMemory(1<<20))
450			if err != nil {
451				t.Error(err)
452				return
453			}
454			defer decL.Close()
455			got2, gotErr2 := ioutil.ReadAll(decL)
456			t.Log("Fresh Reader received:", len(got2), gotErr2)
457			if gotErr != gotErr2 {
458				if gotErr != nil && gotErr2 != nil && gotErr.Error() != gotErr2.Error() {
459					t.Error(gotErr, "!=", gotErr2)
460				}
461				if (gotErr == nil) != (gotErr2 == nil) {
462					t.Error(gotErr, "!=", gotErr2)
463				}
464			}
465			if !bytes.Equal(got2, got) {
466				if gotErr != nil {
467					t.Log("Buffer mismatch without Reset")
468				} else {
469					t.Error("Buffer mismatch without Reset")
470				}
471			}
472		})
473		t.Run("DecodeAll-"+tt.Name, func(t *testing.T) {
474			r, err := tt.Open()
475			if err != nil {
476				t.Error(err)
477				return
478			}
479			in, err := ioutil.ReadAll(r)
480			if err != nil {
481				t.Error(err)
482			}
483			got, gotErr := dec.DecodeAll(in, nil)
484			t.Log("Received:", len(got), gotErr)
485
486			// Check if we got the same:
487			decL, err := NewReader(nil, WithDecoderConcurrency(1), WithDecoderLowmem(true), WithDecoderMaxMemory(1<<20))
488			if err != nil {
489				t.Error(err)
490				return
491			}
492			defer decL.Close()
493			got2, gotErr2 := decL.DecodeAll(in, nil)
494			t.Log("Fresh Reader received:", len(got2), gotErr2)
495			if gotErr != gotErr2 {
496				if gotErr != nil && gotErr2 != nil && gotErr.Error() != gotErr2.Error() {
497					t.Error(gotErr, "!=", gotErr2)
498				}
499				if (gotErr == nil) != (gotErr2 == nil) {
500					t.Error(gotErr, "!=", gotErr2)
501				}
502			}
503			if !bytes.Equal(got2, got) {
504				if gotErr != nil {
505					t.Log("Buffer mismatch without Reset")
506				} else {
507					t.Error("Buffer mismatch without Reset")
508				}
509			}
510		})
511		t.Run("Match-"+tt.Name, func(t *testing.T) {
512			r, err := tt.Open()
513			if err != nil {
514				t.Error(err)
515				return
516			}
517			in, err := ioutil.ReadAll(r)
518			if err != nil {
519				t.Error(err)
520			}
521			got, gotErr := dec.DecodeAll(in, nil)
522			t.Log("Received:", len(got), gotErr)
523
524			// Check a fresh instance
525			decL, err := NewReader(bytes.NewBuffer(in), WithDecoderConcurrency(1), WithDecoderLowmem(true), WithDecoderMaxMemory(1<<20))
526			if err != nil {
527				t.Error(err)
528				return
529			}
530			defer decL.Close()
531			got2, gotErr2 := ioutil.ReadAll(decL)
532			t.Log("Reader Reader received:", len(got2), gotErr2)
533			if gotErr != gotErr2 {
534				if gotErr != nil && gotErr2 != nil && gotErr.Error() != gotErr2.Error() {
535					t.Error(gotErr, "!=", gotErr2)
536				}
537				if (gotErr == nil) != (gotErr2 == nil) {
538					t.Error(gotErr, "!=", gotErr2)
539				}
540			}
541			if !bytes.Equal(got2, got) {
542				if gotErr != nil {
543					t.Log("Buffer mismatch")
544				} else {
545					t.Error("Buffer mismatch")
546				}
547			}
548		})
549	}
550}
551
552func TestDecoder_Reset(t *testing.T) {
553	in, err := ioutil.ReadFile("testdata/z000028")
554	if err != nil {
555		t.Fatal(err)
556	}
557	in = append(in, in...)
558	var e Encoder
559	start := time.Now()
560	dst := e.EncodeAll(in, nil)
561	t.Log("Simple Encoder len", len(in), "-> zstd len", len(dst))
562	mbpersec := (float64(len(in)) / (1024 * 1024)) / (float64(time.Since(start)) / (float64(time.Second)))
563	t.Logf("Encoded %d bytes with %.2f MB/s", len(in), mbpersec)
564
565	dec, err := NewReader(nil)
566	if err != nil {
567		t.Fatal(err)
568	}
569	defer dec.Close()
570	decoded, err := dec.DecodeAll(dst, nil)
571	if err != nil {
572		t.Error(err, len(decoded))
573	}
574	if !bytes.Equal(decoded, in) {
575		t.Fatal("Decoded does not match")
576	}
577	t.Log("Encoded content matched")
578
579	// Decode using reset+copy
580	for i := 0; i < 3; i++ {
581		err = dec.Reset(bytes.NewBuffer(dst))
582		if err != nil {
583			t.Fatal(err)
584		}
585		var dBuf bytes.Buffer
586		n, err := io.Copy(&dBuf, dec)
587		if err != nil {
588			t.Fatal(err)
589		}
590		decoded = dBuf.Bytes()
591		if int(n) != len(decoded) {
592			t.Fatalf("decoded reported length mismatch %d != %d", n, len(decoded))
593		}
594		if !bytes.Equal(decoded, in) {
595			ioutil.WriteFile("testdata/"+t.Name()+"-z000028.got", decoded, os.ModePerm)
596			ioutil.WriteFile("testdata/"+t.Name()+"-z000028.want", in, os.ModePerm)
597			t.Fatal("Decoded does not match")
598		}
599	}
600	// Test without WriterTo interface support.
601	for i := 0; i < 3; i++ {
602		err = dec.Reset(bytes.NewBuffer(dst))
603		if err != nil {
604			t.Fatal(err)
605		}
606		decoded, err := ioutil.ReadAll(ioutil.NopCloser(dec))
607		if err != nil {
608			t.Fatal(err)
609		}
610		if !bytes.Equal(decoded, in) {
611			ioutil.WriteFile("testdata/"+t.Name()+"-z000028.got", decoded, os.ModePerm)
612			ioutil.WriteFile("testdata/"+t.Name()+"-z000028.want", in, os.ModePerm)
613			t.Fatal("Decoded does not match")
614		}
615	}
616}
617
618func TestDecoderMultiFrame(t *testing.T) {
619	fn := "testdata/benchdecoder.zip"
620	data, err := ioutil.ReadFile(fn)
621	if err != nil {
622		t.Fatal(err)
623	}
624	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
625	if err != nil {
626		t.Fatal(err)
627	}
628	dec, err := NewReader(nil)
629	if err != nil {
630		t.Fatal(err)
631		return
632	}
633	defer dec.Close()
634	for _, tt := range zr.File {
635		if !strings.HasSuffix(tt.Name, ".zst") {
636			continue
637		}
638		t.Run(tt.Name, func(t *testing.T) {
639			r, err := tt.Open()
640			if err != nil {
641				t.Fatal(err)
642			}
643			defer r.Close()
644			in, err := ioutil.ReadAll(r)
645			if err != nil {
646				t.Fatal(err)
647			}
648			// 2x
649			in = append(in, in...)
650			if !testing.Short() {
651				// 4x
652				in = append(in, in...)
653				// 8x
654				in = append(in, in...)
655			}
656			err = dec.Reset(bytes.NewBuffer(in))
657			if err != nil {
658				t.Fatal(err)
659			}
660			got, err := ioutil.ReadAll(dec)
661			if err != nil {
662				t.Fatal(err)
663			}
664			err = dec.Reset(bytes.NewBuffer(in))
665			if err != nil {
666				t.Fatal(err)
667			}
668			got2, err := ioutil.ReadAll(dec)
669			if err != nil {
670				t.Fatal(err)
671			}
672			if !bytes.Equal(got, got2) {
673				t.Error("results mismatch")
674			}
675		})
676	}
677}
678
679func TestDecoderMultiFrameReset(t *testing.T) {
680	fn := "testdata/benchdecoder.zip"
681	data, err := ioutil.ReadFile(fn)
682	if err != nil {
683		t.Fatal(err)
684	}
685	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
686	if err != nil {
687		t.Fatal(err)
688	}
689	dec, err := NewReader(nil)
690	if err != nil {
691		t.Fatal(err)
692		return
693	}
694	rng := rand.New(rand.NewSource(1337))
695	defer dec.Close()
696	for _, tt := range zr.File {
697		if !strings.HasSuffix(tt.Name, ".zst") {
698			continue
699		}
700		t.Run(tt.Name, func(t *testing.T) {
701			r, err := tt.Open()
702			if err != nil {
703				t.Fatal(err)
704			}
705			defer r.Close()
706			in, err := ioutil.ReadAll(r)
707			if err != nil {
708				t.Fatal(err)
709			}
710			// 2x
711			in = append(in, in...)
712			if !testing.Short() {
713				// 4x
714				in = append(in, in...)
715				// 8x
716				in = append(in, in...)
717			}
718			err = dec.Reset(bytes.NewBuffer(in))
719			if err != nil {
720				t.Fatal(err)
721			}
722			got, err := ioutil.ReadAll(dec)
723			if err != nil {
724				t.Fatal(err)
725			}
726			err = dec.Reset(bytes.NewBuffer(in))
727			if err != nil {
728				t.Fatal(err)
729			}
730			// Read a random number of bytes
731			tmp := make([]byte, rng.Intn(len(got)))
732			_, err = io.ReadAtLeast(dec, tmp, len(tmp))
733			if err != nil {
734				t.Fatal(err)
735			}
736			err = dec.Reset(bytes.NewBuffer(in))
737			if err != nil {
738				t.Fatal(err)
739			}
740			got2, err := ioutil.ReadAll(dec)
741			if err != nil {
742				t.Fatal(err)
743			}
744			if !bytes.Equal(got, got2) {
745				t.Error("results mismatch")
746			}
747		})
748	}
749}
750
751func testDecoderFile(t *testing.T, fn string) {
752	data, err := ioutil.ReadFile(fn)
753	if err != nil {
754		t.Fatal(err)
755	}
756	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
757	if err != nil {
758		t.Fatal(err)
759	}
760	var want = make(map[string][]byte)
761	for _, tt := range zr.File {
762		if strings.HasSuffix(tt.Name, ".zst") {
763			continue
764		}
765		r, err := tt.Open()
766		if err != nil {
767			t.Fatal(err)
768			return
769		}
770		want[tt.Name+".zst"], _ = ioutil.ReadAll(r)
771	}
772
773	dec, err := NewReader(nil)
774	if err != nil {
775		t.Error(err)
776		return
777	}
778	defer dec.Close()
779	for i, tt := range zr.File {
780		if !strings.HasSuffix(tt.Name, ".zst") || (testing.Short() && i > 20) {
781			continue
782		}
783		t.Run("Reader-"+tt.Name, func(t *testing.T) {
784			r, err := tt.Open()
785			if err != nil {
786				t.Error(err)
787				return
788			}
789			defer r.Close()
790			err = dec.Reset(r)
791			if err != nil {
792				t.Error(err)
793				return
794			}
795			got, err := ioutil.ReadAll(dec)
796			if err != nil {
797				t.Error(err)
798				if err != ErrCRCMismatch {
799					return
800				}
801			}
802			wantB := want[tt.Name]
803			if !bytes.Equal(wantB, got) {
804				if len(wantB)+len(got) < 1000 {
805					t.Logf(" got: %v\nwant: %v", got, wantB)
806				} else {
807					fileName, _ := filepath.Abs(filepath.Join("testdata", t.Name()+"-want.bin"))
808					_ = os.MkdirAll(filepath.Dir(fileName), os.ModePerm)
809					err := ioutil.WriteFile(fileName, wantB, os.ModePerm)
810					t.Log("Wrote file", fileName, err)
811
812					fileName, _ = filepath.Abs(filepath.Join("testdata", t.Name()+"-got.bin"))
813					_ = os.MkdirAll(filepath.Dir(fileName), os.ModePerm)
814					err = ioutil.WriteFile(fileName, got, os.ModePerm)
815					t.Log("Wrote file", fileName, err)
816				}
817				t.Logf("Length, want: %d, got: %d", len(wantB), len(got))
818				t.Error("Output mismatch")
819				return
820			}
821			t.Log(len(got), "bytes returned, matches input, ok!")
822		})
823	}
824}
825
826func BenchmarkDecoder_DecoderSmall(b *testing.B) {
827	fn := "testdata/benchdecoder.zip"
828	data, err := ioutil.ReadFile(fn)
829	if err != nil {
830		b.Fatal(err)
831	}
832	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
833	if err != nil {
834		b.Fatal(err)
835	}
836	dec, err := NewReader(nil)
837	if err != nil {
838		b.Fatal(err)
839		return
840	}
841	defer dec.Close()
842	for _, tt := range zr.File {
843		if !strings.HasSuffix(tt.Name, ".zst") {
844			continue
845		}
846		b.Run(tt.Name, func(b *testing.B) {
847			r, err := tt.Open()
848			if err != nil {
849				b.Fatal(err)
850			}
851			defer r.Close()
852			in, err := ioutil.ReadAll(r)
853			if err != nil {
854				b.Fatal(err)
855			}
856			// 2x
857			in = append(in, in...)
858			// 4x
859			in = append(in, in...)
860			// 8x
861			in = append(in, in...)
862			err = dec.Reset(bytes.NewBuffer(in))
863			if err != nil {
864				b.Fatal(err)
865			}
866			got, err := ioutil.ReadAll(dec)
867			if err != nil {
868				b.Fatal(err)
869			}
870			b.SetBytes(int64(len(got)))
871			b.ReportAllocs()
872			b.ResetTimer()
873			for i := 0; i < b.N; i++ {
874				err = dec.Reset(bytes.NewBuffer(in))
875				if err != nil {
876					b.Fatal(err)
877				}
878				_, err := io.Copy(ioutil.Discard, dec)
879				if err != nil {
880					b.Fatal(err)
881				}
882			}
883		})
884	}
885}
886
887func BenchmarkDecoder_DecodeAll(b *testing.B) {
888	fn := "testdata/benchdecoder.zip"
889	data, err := ioutil.ReadFile(fn)
890	if err != nil {
891		b.Fatal(err)
892	}
893	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
894	if err != nil {
895		b.Fatal(err)
896	}
897	dec, err := NewReader(nil, WithDecoderConcurrency(1))
898	if err != nil {
899		b.Fatal(err)
900		return
901	}
902	defer dec.Close()
903	for _, tt := range zr.File {
904		if !strings.HasSuffix(tt.Name, ".zst") {
905			continue
906		}
907		b.Run(tt.Name, func(b *testing.B) {
908			r, err := tt.Open()
909			if err != nil {
910				b.Fatal(err)
911			}
912			defer r.Close()
913			in, err := ioutil.ReadAll(r)
914			if err != nil {
915				b.Fatal(err)
916			}
917			got, err := dec.DecodeAll(in, nil)
918			if err != nil {
919				b.Fatal(err)
920			}
921			b.SetBytes(int64(len(got)))
922			b.ReportAllocs()
923			b.ResetTimer()
924			for i := 0; i < b.N; i++ {
925				_, err = dec.DecodeAll(in, got[:0])
926				if err != nil {
927					b.Fatal(err)
928				}
929			}
930		})
931	}
932}
933
934func BenchmarkDecoder_DecodeAllParallel(b *testing.B) {
935	fn := "testdata/benchdecoder.zip"
936	data, err := ioutil.ReadFile(fn)
937	if err != nil {
938		b.Fatal(err)
939	}
940	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
941	if err != nil {
942		b.Fatal(err)
943	}
944	dec, err := NewReader(nil)
945	if err != nil {
946		b.Fatal(err)
947		return
948	}
949	defer dec.Close()
950	for _, tt := range zr.File {
951		if !strings.HasSuffix(tt.Name, ".zst") {
952			continue
953		}
954		b.Run(tt.Name, func(b *testing.B) {
955			r, err := tt.Open()
956			if err != nil {
957				b.Fatal(err)
958			}
959			defer r.Close()
960			in, err := ioutil.ReadAll(r)
961			if err != nil {
962				b.Fatal(err)
963			}
964			got, err := dec.DecodeAll(in, nil)
965			if err != nil {
966				b.Fatal(err)
967			}
968			b.SetBytes(int64(len(got)))
969			b.ReportAllocs()
970			b.ResetTimer()
971			b.RunParallel(func(pb *testing.PB) {
972				got := make([]byte, len(got))
973				for pb.Next() {
974					_, err = dec.DecodeAll(in, got[:0])
975					if err != nil {
976						b.Fatal(err)
977					}
978				}
979			})
980		})
981	}
982}
983
984/*
985func BenchmarkDecoder_DecodeAllCgo(b *testing.B) {
986	fn := "testdata/benchdecoder.zip"
987	data, err := ioutil.ReadFile(fn)
988	if err != nil {
989		b.Fatal(err)
990	}
991	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
992	if err != nil {
993		b.Fatal(err)
994	}
995	for _, tt := range zr.File {
996		if !strings.HasSuffix(tt.Name, ".zst") {
997			continue
998		}
999		b.Run(tt.Name, func(b *testing.B) {
1000			tt := tt
1001			r, err := tt.Open()
1002			if err != nil {
1003				b.Fatal(err)
1004			}
1005			defer r.Close()
1006			in, err := ioutil.ReadAll(r)
1007			if err != nil {
1008				b.Fatal(err)
1009			}
1010			got, err := zstd.Decompress(nil, in)
1011			if err != nil {
1012				b.Fatal(err)
1013			}
1014			b.SetBytes(int64(len(got)))
1015			b.ReportAllocs()
1016			b.ResetTimer()
1017			for i := 0; i < b.N; i++ {
1018				got, err = zstd.Decompress(got, in)
1019				if err != nil {
1020					b.Fatal(err)
1021				}
1022			}
1023		})
1024	}
1025}
1026
1027func BenchmarkDecoder_DecodeAllParallelCgo(b *testing.B) {
1028	fn := "testdata/benchdecoder.zip"
1029	data, err := ioutil.ReadFile(fn)
1030	if err != nil {
1031		b.Fatal(err)
1032	}
1033	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
1034	if err != nil {
1035		b.Fatal(err)
1036	}
1037	for _, tt := range zr.File {
1038		if !strings.HasSuffix(tt.Name, ".zst") {
1039			continue
1040		}
1041		b.Run(tt.Name, func(b *testing.B) {
1042			r, err := tt.Open()
1043			if err != nil {
1044				b.Fatal(err)
1045			}
1046			defer r.Close()
1047			in, err := ioutil.ReadAll(r)
1048			if err != nil {
1049				b.Fatal(err)
1050			}
1051			got, err := zstd.Decompress(nil, in)
1052			if err != nil {
1053				b.Fatal(err)
1054			}
1055			b.SetBytes(int64(len(got)))
1056			b.ReportAllocs()
1057			b.ResetTimer()
1058			b.RunParallel(func(pb *testing.PB) {
1059				got := make([]byte, len(got))
1060				for pb.Next() {
1061					got, err = zstd.Decompress(got, in)
1062					if err != nil {
1063						b.Fatal(err)
1064					}
1065				}
1066			})
1067		})
1068	}
1069}
1070
1071func BenchmarkDecoderSilesiaCgo(b *testing.B) {
1072	fn := "testdata/silesia.tar.zst"
1073	data, err := ioutil.ReadFile(fn)
1074	if err != nil {
1075		if os.IsNotExist(err) {
1076			b.Skip("Missing testdata/silesia.tar.zst")
1077			return
1078		}
1079		b.Fatal(err)
1080	}
1081	dec := zstd.NewReader(bytes.NewBuffer(data))
1082	n, err := io.Copy(ioutil.Discard, dec)
1083	if err != nil {
1084		b.Fatal(err)
1085	}
1086
1087	b.SetBytes(n)
1088	b.ReportAllocs()
1089	b.ResetTimer()
1090	for i := 0; i < b.N; i++ {
1091		dec := zstd.NewReader(bytes.NewBuffer(data))
1092		_, err := io.CopyN(ioutil.Discard, dec, n)
1093		if err != nil {
1094			b.Fatal(err)
1095		}
1096	}
1097}
1098func BenchmarkDecoderEnwik9Cgo(b *testing.B) {
1099	fn := "testdata/enwik9-1.zst"
1100	data, err := ioutil.ReadFile(fn)
1101	if err != nil {
1102		if os.IsNotExist(err) {
1103			b.Skip("Missing " + fn)
1104			return
1105		}
1106		b.Fatal(err)
1107	}
1108	dec := zstd.NewReader(bytes.NewBuffer(data))
1109	n, err := io.Copy(ioutil.Discard, dec)
1110	if err != nil {
1111		b.Fatal(err)
1112	}
1113
1114	b.SetBytes(n)
1115	b.ReportAllocs()
1116	b.ResetTimer()
1117	for i := 0; i < b.N; i++ {
1118		dec := zstd.NewReader(bytes.NewBuffer(data))
1119		_, err := io.CopyN(ioutil.Discard, dec, n)
1120		if err != nil {
1121			b.Fatal(err)
1122		}
1123	}
1124}
1125
1126*/
1127
1128func BenchmarkDecoderSilesia(b *testing.B) {
1129	fn := "testdata/silesia.tar.zst"
1130	data, err := ioutil.ReadFile(fn)
1131	if err != nil {
1132		if os.IsNotExist(err) {
1133			b.Skip("Missing testdata/silesia.tar.zst")
1134			return
1135		}
1136		b.Fatal(err)
1137	}
1138	dec, err := NewReader(nil, WithDecoderLowmem(false))
1139	if err != nil {
1140		b.Fatal(err)
1141	}
1142	defer dec.Close()
1143	err = dec.Reset(bytes.NewBuffer(data))
1144	if err != nil {
1145		b.Fatal(err)
1146	}
1147	n, err := io.Copy(ioutil.Discard, dec)
1148	if err != nil {
1149		b.Fatal(err)
1150	}
1151
1152	b.SetBytes(n)
1153	b.ReportAllocs()
1154	b.ResetTimer()
1155	for i := 0; i < b.N; i++ {
1156		err = dec.Reset(bytes.NewBuffer(data))
1157		if err != nil {
1158			b.Fatal(err)
1159		}
1160		_, err := io.CopyN(ioutil.Discard, dec, n)
1161		if err != nil {
1162			b.Fatal(err)
1163		}
1164	}
1165}
1166
1167func BenchmarkDecoderEnwik9(b *testing.B) {
1168	fn := "testdata/enwik9-1.zst"
1169	data, err := ioutil.ReadFile(fn)
1170	if err != nil {
1171		if os.IsNotExist(err) {
1172			b.Skip("Missing " + fn)
1173			return
1174		}
1175		b.Fatal(err)
1176	}
1177	dec, err := NewReader(nil, WithDecoderLowmem(false))
1178	if err != nil {
1179		b.Fatal(err)
1180	}
1181	defer dec.Close()
1182	err = dec.Reset(bytes.NewBuffer(data))
1183	if err != nil {
1184		b.Fatal(err)
1185	}
1186	n, err := io.Copy(ioutil.Discard, dec)
1187	if err != nil {
1188		b.Fatal(err)
1189	}
1190
1191	b.SetBytes(n)
1192	b.ReportAllocs()
1193	b.ResetTimer()
1194	for i := 0; i < b.N; i++ {
1195		err = dec.Reset(bytes.NewBuffer(data))
1196		if err != nil {
1197			b.Fatal(err)
1198		}
1199		_, err := io.CopyN(ioutil.Discard, dec, n)
1200		if err != nil {
1201			b.Fatal(err)
1202		}
1203	}
1204}
1205
1206func testDecoderDecodeAll(t *testing.T, fn string, dec *Decoder) {
1207	data, err := ioutil.ReadFile(fn)
1208	if err != nil {
1209		t.Fatal(err)
1210	}
1211	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
1212	if err != nil {
1213		t.Fatal(err)
1214	}
1215	var want = make(map[string][]byte)
1216	for _, tt := range zr.File {
1217		if strings.HasSuffix(tt.Name, ".zst") {
1218			continue
1219		}
1220		r, err := tt.Open()
1221		if err != nil {
1222			t.Fatal(err)
1223			return
1224		}
1225		want[tt.Name+".zst"], _ = ioutil.ReadAll(r)
1226	}
1227	var wg sync.WaitGroup
1228	for i, tt := range zr.File {
1229		tt := tt
1230		if !strings.HasSuffix(tt.Name, ".zst") || (testing.Short() && i > 20) {
1231			continue
1232		}
1233		wg.Add(1)
1234		t.Run("DecodeAll-"+tt.Name, func(t *testing.T) {
1235			defer wg.Done()
1236			t.Parallel()
1237			r, err := tt.Open()
1238			if err != nil {
1239				t.Fatal(err)
1240			}
1241			in, err := ioutil.ReadAll(r)
1242			if err != nil {
1243				t.Fatal(err)
1244			}
1245			wantB := want[tt.Name]
1246			// make a buffer that is too small.
1247			got, err := dec.DecodeAll(in, make([]byte, 10, 200))
1248			if err != nil {
1249				t.Error(err)
1250			}
1251			if len(got) < 10 {
1252				t.Fatal("didn't get input back")
1253			}
1254			got = got[10:]
1255			if !bytes.Equal(wantB, got) {
1256				if len(wantB)+len(got) < 1000 {
1257					t.Logf(" got: %v\nwant: %v", got, wantB)
1258				} else {
1259					fileName, _ := filepath.Abs(filepath.Join("testdata", t.Name()+"-want.bin"))
1260					_ = os.MkdirAll(filepath.Dir(fileName), os.ModePerm)
1261					err := ioutil.WriteFile(fileName, wantB, os.ModePerm)
1262					t.Log("Wrote file", fileName, err)
1263
1264					fileName, _ = filepath.Abs(filepath.Join("testdata", t.Name()+"-got.bin"))
1265					_ = os.MkdirAll(filepath.Dir(fileName), os.ModePerm)
1266					err = ioutil.WriteFile(fileName, got, os.ModePerm)
1267					t.Log("Wrote file", fileName, err)
1268				}
1269				t.Logf("Length, want: %d, got: %d", len(wantB), len(got))
1270				t.Error("Output mismatch")
1271				return
1272			}
1273			t.Log(len(got), "bytes returned, matches input, ok!")
1274		})
1275	}
1276	go func() {
1277		wg.Wait()
1278		dec.Close()
1279	}()
1280}
1281
1282func testDecoderDecodeAllError(t *testing.T, fn string, dec *Decoder) {
1283	data, err := ioutil.ReadFile(fn)
1284	if err != nil {
1285		t.Fatal(err)
1286	}
1287	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
1288	if err != nil {
1289		t.Fatal(err)
1290	}
1291
1292	var wg sync.WaitGroup
1293	for _, tt := range zr.File {
1294		tt := tt
1295		if !strings.HasSuffix(tt.Name, ".zst") {
1296			continue
1297		}
1298		wg.Add(1)
1299		t.Run("DecodeAll-"+tt.Name, func(t *testing.T) {
1300			defer wg.Done()
1301			t.Parallel()
1302			r, err := tt.Open()
1303			if err != nil {
1304				t.Fatal(err)
1305			}
1306			in, err := ioutil.ReadAll(r)
1307			if err != nil {
1308				t.Fatal(err)
1309			}
1310			// make a buffer that is too small.
1311			_, err = dec.DecodeAll(in, make([]byte, 0, 200))
1312			if err == nil {
1313				t.Error("Did not get expected error")
1314			}
1315		})
1316	}
1317	go func() {
1318		wg.Wait()
1319		dec.Close()
1320	}()
1321}
1322
1323// Test our predefined tables are correct.
1324// We don't predefine them, since this also tests our transformations.
1325// Reference from here: https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L234
1326func TestPredefTables(t *testing.T) {
1327	x := func(nextState uint16, nbAddBits, nbBits uint8, baseVal uint32) decSymbol {
1328		return newDecSymbol(nbBits, nbAddBits, nextState, baseVal)
1329	}
1330	for i := range fsePredef[:] {
1331		var want []decSymbol
1332		switch tableIndex(i) {
1333		case tableLiteralLengths:
1334			want = []decSymbol{
1335				/* nextState, nbAddBits, nbBits, baseVal */
1336				x(0, 0, 4, 0), x(16, 0, 4, 0),
1337				x(32, 0, 5, 1), x(0, 0, 5, 3),
1338				x(0, 0, 5, 4), x(0, 0, 5, 6),
1339				x(0, 0, 5, 7), x(0, 0, 5, 9),
1340				x(0, 0, 5, 10), x(0, 0, 5, 12),
1341				x(0, 0, 6, 14), x(0, 1, 5, 16),
1342				x(0, 1, 5, 20), x(0, 1, 5, 22),
1343				x(0, 2, 5, 28), x(0, 3, 5, 32),
1344				x(0, 4, 5, 48), x(32, 6, 5, 64),
1345				x(0, 7, 5, 128), x(0, 8, 6, 256),
1346				x(0, 10, 6, 1024), x(0, 12, 6, 4096),
1347				x(32, 0, 4, 0), x(0, 0, 4, 1),
1348				x(0, 0, 5, 2), x(32, 0, 5, 4),
1349				x(0, 0, 5, 5), x(32, 0, 5, 7),
1350				x(0, 0, 5, 8), x(32, 0, 5, 10),
1351				x(0, 0, 5, 11), x(0, 0, 6, 13),
1352				x(32, 1, 5, 16), x(0, 1, 5, 18),
1353				x(32, 1, 5, 22), x(0, 2, 5, 24),
1354				x(32, 3, 5, 32), x(0, 3, 5, 40),
1355				x(0, 6, 4, 64), x(16, 6, 4, 64),
1356				x(32, 7, 5, 128), x(0, 9, 6, 512),
1357				x(0, 11, 6, 2048), x(48, 0, 4, 0),
1358				x(16, 0, 4, 1), x(32, 0, 5, 2),
1359				x(32, 0, 5, 3), x(32, 0, 5, 5),
1360				x(32, 0, 5, 6), x(32, 0, 5, 8),
1361				x(32, 0, 5, 9), x(32, 0, 5, 11),
1362				x(32, 0, 5, 12), x(0, 0, 6, 15),
1363				x(32, 1, 5, 18), x(32, 1, 5, 20),
1364				x(32, 2, 5, 24), x(32, 2, 5, 28),
1365				x(32, 3, 5, 40), x(32, 4, 5, 48),
1366				x(0, 16, 6, 65536), x(0, 15, 6, 32768),
1367				x(0, 14, 6, 16384), x(0, 13, 6, 8192),
1368			}
1369		case tableOffsets:
1370			want = []decSymbol{
1371				/* nextState, nbAddBits, nbBits, baseVal */
1372				x(0, 0, 5, 0), x(0, 6, 4, 61),
1373				x(0, 9, 5, 509), x(0, 15, 5, 32765),
1374				x(0, 21, 5, 2097149), x(0, 3, 5, 5),
1375				x(0, 7, 4, 125), x(0, 12, 5, 4093),
1376				x(0, 18, 5, 262141), x(0, 23, 5, 8388605),
1377				x(0, 5, 5, 29), x(0, 8, 4, 253),
1378				x(0, 14, 5, 16381), x(0, 20, 5, 1048573),
1379				x(0, 2, 5, 1), x(16, 7, 4, 125),
1380				x(0, 11, 5, 2045), x(0, 17, 5, 131069),
1381				x(0, 22, 5, 4194301), x(0, 4, 5, 13),
1382				x(16, 8, 4, 253), x(0, 13, 5, 8189),
1383				x(0, 19, 5, 524285), x(0, 1, 5, 1),
1384				x(16, 6, 4, 61), x(0, 10, 5, 1021),
1385				x(0, 16, 5, 65533), x(0, 28, 5, 268435453),
1386				x(0, 27, 5, 134217725), x(0, 26, 5, 67108861),
1387				x(0, 25, 5, 33554429), x(0, 24, 5, 16777213),
1388			}
1389		case tableMatchLengths:
1390			want = []decSymbol{
1391				/* nextState, nbAddBits, nbBits, baseVal */
1392				x(0, 0, 6, 3), x(0, 0, 4, 4),
1393				x(32, 0, 5, 5), x(0, 0, 5, 6),
1394				x(0, 0, 5, 8), x(0, 0, 5, 9),
1395				x(0, 0, 5, 11), x(0, 0, 6, 13),
1396				x(0, 0, 6, 16), x(0, 0, 6, 19),
1397				x(0, 0, 6, 22), x(0, 0, 6, 25),
1398				x(0, 0, 6, 28), x(0, 0, 6, 31),
1399				x(0, 0, 6, 34), x(0, 1, 6, 37),
1400				x(0, 1, 6, 41), x(0, 2, 6, 47),
1401				x(0, 3, 6, 59), x(0, 4, 6, 83),
1402				x(0, 7, 6, 131), x(0, 9, 6, 515),
1403				x(16, 0, 4, 4), x(0, 0, 4, 5),
1404				x(32, 0, 5, 6), x(0, 0, 5, 7),
1405				x(32, 0, 5, 9), x(0, 0, 5, 10),
1406				x(0, 0, 6, 12), x(0, 0, 6, 15),
1407				x(0, 0, 6, 18), x(0, 0, 6, 21),
1408				x(0, 0, 6, 24), x(0, 0, 6, 27),
1409				x(0, 0, 6, 30), x(0, 0, 6, 33),
1410				x(0, 1, 6, 35), x(0, 1, 6, 39),
1411				x(0, 2, 6, 43), x(0, 3, 6, 51),
1412				x(0, 4, 6, 67), x(0, 5, 6, 99),
1413				x(0, 8, 6, 259), x(32, 0, 4, 4),
1414				x(48, 0, 4, 4), x(16, 0, 4, 5),
1415				x(32, 0, 5, 7), x(32, 0, 5, 8),
1416				x(32, 0, 5, 10), x(32, 0, 5, 11),
1417				x(0, 0, 6, 14), x(0, 0, 6, 17),
1418				x(0, 0, 6, 20), x(0, 0, 6, 23),
1419				x(0, 0, 6, 26), x(0, 0, 6, 29),
1420				x(0, 0, 6, 32), x(0, 16, 6, 65539),
1421				x(0, 15, 6, 32771), x(0, 14, 6, 16387),
1422				x(0, 13, 6, 8195), x(0, 12, 6, 4099),
1423				x(0, 11, 6, 2051), x(0, 10, 6, 1027),
1424			}
1425		}
1426		pre := fsePredef[i]
1427		got := pre.dt[:1<<pre.actualTableLog]
1428		if !reflect.DeepEqual(got, want) {
1429			t.Logf("want: %v", want)
1430			t.Logf("got : %v", got)
1431			t.Errorf("Predefined table %d incorrect, len(got) = %d, len(want) = %d", i, len(got), len(want))
1432		}
1433	}
1434}
1435
1436func timeout(after time.Duration) (cancel func()) {
1437	c := time.After(after)
1438	cc := make(chan struct{})
1439	go func() {
1440		select {
1441		case <-cc:
1442			return
1443		case <-c:
1444			buf := make([]byte, 1<<20)
1445			stacklen := runtime.Stack(buf, true)
1446			log.Printf("=== Timeout, assuming deadlock ===\n*** goroutine dump...\n%s\n*** end\n", string(buf[:stacklen]))
1447			os.Exit(2)
1448		}
1449	}()
1450	return func() {
1451		close(cc)
1452	}
1453}
1454