1// Package zstd provides decompression of zstandard files.
2//
3// For advanced usage and examples, go to the README: https://github.com/klauspost/compress/tree/master/zstd#zstd
4package zstd
5
6import (
7	"errors"
8	"log"
9	"math"
10	"math/bits"
11)
12
13// enable debug printing
14const debug = false
15
16// Enable extra assertions.
17const debugAsserts = debug || false
18
19// print sequence details
20const debugSequences = false
21
22// print detailed matching information
23const debugMatches = false
24
25// force encoder to use predefined tables.
26const forcePreDef = false
27
28// zstdMinMatch is the minimum zstd match length.
29const zstdMinMatch = 3
30
31// Reset the buffer offset when reaching this.
32const bufferReset = math.MaxInt32 - MaxWindowSize
33
34var (
35	// ErrReservedBlockType is returned when a reserved block type is found.
36	// Typically this indicates wrong or corrupted input.
37	ErrReservedBlockType = errors.New("invalid input: reserved block type encountered")
38
39	// ErrCompressedSizeTooBig is returned when a block is bigger than allowed.
40	// Typically this indicates wrong or corrupted input.
41	ErrCompressedSizeTooBig = errors.New("invalid input: compressed size too big")
42
43	// ErrBlockTooSmall is returned when a block is too small to be decoded.
44	// Typically returned on invalid input.
45	ErrBlockTooSmall = errors.New("block too small")
46
47	// ErrMagicMismatch is returned when a "magic" number isn't what is expected.
48	// Typically this indicates wrong or corrupted input.
49	ErrMagicMismatch = errors.New("invalid input: magic number mismatch")
50
51	// ErrWindowSizeExceeded is returned when a reference exceeds the valid window size.
52	// Typically this indicates wrong or corrupted input.
53	ErrWindowSizeExceeded = errors.New("window size exceeded")
54
55	// ErrWindowSizeTooSmall is returned when no window size is specified.
56	// Typically this indicates wrong or corrupted input.
57	ErrWindowSizeTooSmall = errors.New("invalid input: window size was too small")
58
59	// ErrDecoderSizeExceeded is returned if decompressed size exceeds the configured limit.
60	ErrDecoderSizeExceeded = errors.New("decompressed size exceeds configured limit")
61
62	// ErrUnknownDictionary is returned if the dictionary ID is unknown.
63	// For the time being dictionaries are not supported.
64	ErrUnknownDictionary = errors.New("unknown dictionary")
65
66	// ErrFrameSizeExceeded is returned if the stated frame size is exceeded.
67	// This is only returned if SingleSegment is specified on the frame.
68	ErrFrameSizeExceeded = errors.New("frame size exceeded")
69
70	// ErrCRCMismatch is returned if CRC mismatches.
71	ErrCRCMismatch = errors.New("CRC check failed")
72
73	// ErrDecoderClosed will be returned if the Decoder was used after
74	// Close has been called.
75	ErrDecoderClosed = errors.New("decoder used after Close")
76
77	// ErrDecoderNilInput is returned when a nil Reader was provided
78	// and an operation other than Reset/DecodeAll/Close was attempted.
79	ErrDecoderNilInput = errors.New("nil input provided as reader")
80)
81
82func println(a ...interface{}) {
83	if debug {
84		log.Println(a...)
85	}
86}
87
88func printf(format string, a ...interface{}) {
89	if debug {
90		log.Printf(format, a...)
91	}
92}
93
94// matchLenFast does matching, but will not match the last up to 7 bytes.
95func matchLenFast(a, b []byte) int {
96	endI := len(a) & (math.MaxInt32 - 7)
97	for i := 0; i < endI; i += 8 {
98		if diff := load64(a, i) ^ load64(b, i); diff != 0 {
99			return i + bits.TrailingZeros64(diff)>>3
100		}
101	}
102	return endI
103}
104
105// matchLen returns the maximum length.
106// a must be the shortest of the two.
107// The function also returns whether all bytes matched.
108func matchLen(a, b []byte) int {
109	b = b[:len(a)]
110	for i := 0; i < len(a)-7; i += 8 {
111		if diff := load64(a, i) ^ load64(b, i); diff != 0 {
112			return i + (bits.TrailingZeros64(diff) >> 3)
113		}
114	}
115
116	checked := (len(a) >> 3) << 3
117	a = a[checked:]
118	b = b[checked:]
119	for i := range a {
120		if a[i] != b[i] {
121			return i + checked
122		}
123	}
124	return len(a) + checked
125}
126
127func load3232(b []byte, i int32) uint32 {
128	// Help the compiler eliminate bounds checks on the read so it can be done in a single read.
129	b = b[i:]
130	b = b[:4]
131	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
132}
133
134func load6432(b []byte, i int32) uint64 {
135	// Help the compiler eliminate bounds checks on the read so it can be done in a single read.
136	b = b[i:]
137	b = b[:8]
138	return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
139		uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
140}
141
142func load64(b []byte, i int) uint64 {
143	// Help the compiler eliminate bounds checks on the read so it can be done in a single read.
144	b = b[i:]
145	b = b[:8]
146	return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
147		uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
148}
149