1// Copyright 2011 The Snappy-Go Authors. All rights reserved.
2// Modified for deflate by Klaus Post (c) 2015.
3// Use of this source code is governed by a BSD-style
4// license that can be found in the LICENSE file.
5
6package flate
7
8import (
9	"encoding/binary"
10	"fmt"
11	"math/bits"
12)
13
14type fastEnc interface {
15	Encode(dst *tokens, src []byte)
16	Reset()
17}
18
19func newFastEnc(level int) fastEnc {
20	switch level {
21	case 1:
22		return &fastEncL1{fastGen: fastGen{cur: maxStoreBlockSize}}
23	case 2:
24		return &fastEncL2{fastGen: fastGen{cur: maxStoreBlockSize}}
25	case 3:
26		return &fastEncL3{fastGen: fastGen{cur: maxStoreBlockSize}}
27	case 4:
28		return &fastEncL4{fastGen: fastGen{cur: maxStoreBlockSize}}
29	case 5:
30		return &fastEncL5{fastGen: fastGen{cur: maxStoreBlockSize}}
31	case 6:
32		return &fastEncL6{fastGen: fastGen{cur: maxStoreBlockSize}}
33	default:
34		panic("invalid level specified")
35	}
36}
37
38const (
39	tableBits       = 15             // Bits used in the table
40	tableSize       = 1 << tableBits // Size of the table
41	tableShift      = 32 - tableBits // Right-shift to get the tableBits most significant bits of a uint32.
42	baseMatchOffset = 1              // The smallest match offset
43	baseMatchLength = 3              // The smallest match length per the RFC section 3.2.5
44	maxMatchOffset  = 1 << 15        // The largest match offset
45
46	bTableBits   = 17                                               // Bits used in the big tables
47	bTableSize   = 1 << bTableBits                                  // Size of the table
48	allocHistory = maxStoreBlockSize * 5                            // Size to preallocate for history.
49	bufferReset  = (1 << 31) - allocHistory - maxStoreBlockSize - 1 // Reset the buffer offset when reaching this.
50)
51
52const (
53	prime3bytes = 506832829
54	prime4bytes = 2654435761
55	prime5bytes = 889523592379
56	prime6bytes = 227718039650203
57	prime7bytes = 58295818150454627
58	prime8bytes = 0xcf1bbcdcb7a56463
59)
60
61func load32(b []byte, i int) uint32 {
62	// Help the compiler eliminate bounds checks on the read so it can be done in a single read.
63	b = b[i:]
64	b = b[:4]
65	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
66}
67
68func load64(b []byte, i int) uint64 {
69	return binary.LittleEndian.Uint64(b[i:])
70}
71
72func load3232(b []byte, i int32) uint32 {
73	return binary.LittleEndian.Uint32(b[i:])
74}
75
76func load6432(b []byte, i int32) uint64 {
77	return binary.LittleEndian.Uint64(b[i:])
78}
79
80func hash(u uint32) uint32 {
81	return (u * 0x1e35a7bd) >> tableShift
82}
83
84type tableEntry struct {
85	offset int32
86}
87
88// fastGen maintains the table for matches,
89// and the previous byte block for level 2.
90// This is the generic implementation.
91type fastGen struct {
92	hist []byte
93	cur  int32
94}
95
96func (e *fastGen) addBlock(src []byte) int32 {
97	// check if we have space already
98	if len(e.hist)+len(src) > cap(e.hist) {
99		if cap(e.hist) == 0 {
100			e.hist = make([]byte, 0, allocHistory)
101		} else {
102			if cap(e.hist) < maxMatchOffset*2 {
103				panic("unexpected buffer size")
104			}
105			// Move down
106			offset := int32(len(e.hist)) - maxMatchOffset
107			copy(e.hist[0:maxMatchOffset], e.hist[offset:])
108			e.cur += offset
109			e.hist = e.hist[:maxMatchOffset]
110		}
111	}
112	s := int32(len(e.hist))
113	e.hist = append(e.hist, src...)
114	return s
115}
116
117// hash4 returns the hash of u to fit in a hash table with h bits.
118// Preferably h should be a constant and should always be <32.
119func hash4u(u uint32, h uint8) uint32 {
120	return (u * prime4bytes) >> ((32 - h) & reg8SizeMask32)
121}
122
123type tableEntryPrev struct {
124	Cur  tableEntry
125	Prev tableEntry
126}
127
128// hash4x64 returns the hash of the lowest 4 bytes of u to fit in a hash table with h bits.
129// Preferably h should be a constant and should always be <32.
130func hash4x64(u uint64, h uint8) uint32 {
131	return (uint32(u) * prime4bytes) >> ((32 - h) & reg8SizeMask32)
132}
133
134// hash7 returns the hash of the lowest 7 bytes of u to fit in a hash table with h bits.
135// Preferably h should be a constant and should always be <64.
136func hash7(u uint64, h uint8) uint32 {
137	return uint32(((u << (64 - 56)) * prime7bytes) >> ((64 - h) & reg8SizeMask64))
138}
139
140// hash8 returns the hash of u to fit in a hash table with h bits.
141// Preferably h should be a constant and should always be <64.
142func hash8(u uint64, h uint8) uint32 {
143	return uint32((u * prime8bytes) >> ((64 - h) & reg8SizeMask64))
144}
145
146// hash6 returns the hash of the lowest 6 bytes of u to fit in a hash table with h bits.
147// Preferably h should be a constant and should always be <64.
148func hash6(u uint64, h uint8) uint32 {
149	return uint32(((u << (64 - 48)) * prime6bytes) >> ((64 - h) & reg8SizeMask64))
150}
151
152// matchlen will return the match length between offsets and t in src.
153// The maximum length returned is maxMatchLength - 4.
154// It is assumed that s > t, that t >=0 and s < len(src).
155func (e *fastGen) matchlen(s, t int32, src []byte) int32 {
156	if debugDecode {
157		if t >= s {
158			panic(fmt.Sprint("t >=s:", t, s))
159		}
160		if int(s) >= len(src) {
161			panic(fmt.Sprint("s >= len(src):", s, len(src)))
162		}
163		if t < 0 {
164			panic(fmt.Sprint("t < 0:", t))
165		}
166		if s-t > maxMatchOffset {
167			panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
168		}
169	}
170	s1 := int(s) + maxMatchLength - 4
171	if s1 > len(src) {
172		s1 = len(src)
173	}
174
175	// Extend the match to be as long as possible.
176	return int32(matchLen(src[s:s1], src[t:]))
177}
178
179// matchlenLong will return the match length between offsets and t in src.
180// It is assumed that s > t, that t >=0 and s < len(src).
181func (e *fastGen) matchlenLong(s, t int32, src []byte) int32 {
182	if debugDecode {
183		if t >= s {
184			panic(fmt.Sprint("t >=s:", t, s))
185		}
186		if int(s) >= len(src) {
187			panic(fmt.Sprint("s >= len(src):", s, len(src)))
188		}
189		if t < 0 {
190			panic(fmt.Sprint("t < 0:", t))
191		}
192		if s-t > maxMatchOffset {
193			panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
194		}
195	}
196	// Extend the match to be as long as possible.
197	return int32(matchLen(src[s:], src[t:]))
198}
199
200// Reset the encoding table.
201func (e *fastGen) Reset() {
202	if cap(e.hist) < allocHistory {
203		e.hist = make([]byte, 0, allocHistory)
204	}
205	// We offset current position so everything will be out of reach.
206	// If we are above the buffer reset it will be cleared anyway since len(hist) == 0.
207	if e.cur <= bufferReset {
208		e.cur += maxMatchOffset + int32(len(e.hist))
209	}
210	e.hist = e.hist[:0]
211}
212
213// matchLen returns the maximum length.
214// 'a' must be the shortest of the two.
215func matchLen(a, b []byte) int {
216	b = b[:len(a)]
217	var checked int
218
219	for len(a) >= 8 {
220		b = b[:len(a)]
221		if diff := binary.LittleEndian.Uint64(a) ^ binary.LittleEndian.Uint64(b); diff != 0 {
222			return checked + (bits.TrailingZeros64(diff) >> 3)
223		}
224		checked += 8
225		a = a[8:]
226		b = b[8:]
227	}
228	b = b[:len(a)]
229	for i := range a {
230		if a[i] != b[i] {
231			return i + checked
232		}
233	}
234	return len(a) + checked
235}
236