1package flate
2
3import "fmt"
4
5type fastEncL4 struct {
6	fastGen
7	table  [tableSize]tableEntry
8	bTable [tableSize]tableEntry
9}
10
11func (e *fastEncL4) Encode(dst *tokens, src []byte) {
12	const (
13		inputMargin            = 12 - 1
14		minNonLiteralBlockSize = 1 + 1 + inputMargin
15	)
16	if debugDeflate && e.cur < 0 {
17		panic(fmt.Sprint("e.cur < 0: ", e.cur))
18	}
19	// Protect against e.cur wraparound.
20	for e.cur >= bufferReset {
21		if len(e.hist) == 0 {
22			for i := range e.table[:] {
23				e.table[i] = tableEntry{}
24			}
25			for i := range e.bTable[:] {
26				e.bTable[i] = tableEntry{}
27			}
28			e.cur = maxMatchOffset
29			break
30		}
31		// Shift down everything in the table that isn't already too far away.
32		minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
33		for i := range e.table[:] {
34			v := e.table[i].offset
35			if v <= minOff {
36				v = 0
37			} else {
38				v = v - e.cur + maxMatchOffset
39			}
40			e.table[i].offset = v
41		}
42		for i := range e.bTable[:] {
43			v := e.bTable[i].offset
44			if v <= minOff {
45				v = 0
46			} else {
47				v = v - e.cur + maxMatchOffset
48			}
49			e.bTable[i].offset = v
50		}
51		e.cur = maxMatchOffset
52	}
53
54	s := e.addBlock(src)
55
56	// This check isn't in the Snappy implementation, but there, the caller
57	// instead of the callee handles this case.
58	if len(src) < minNonLiteralBlockSize {
59		// We do not fill the token table.
60		// This will be picked up by caller.
61		dst.n = uint16(len(src))
62		return
63	}
64
65	// Override src
66	src = e.hist
67	nextEmit := s
68
69	// sLimit is when to stop looking for offset/length copies. The inputMargin
70	// lets us use a fast path for emitLiteral in the main loop, while we are
71	// looking for copies.
72	sLimit := int32(len(src) - inputMargin)
73
74	// nextEmit is where in src the next emitLiteral should start from.
75	cv := load6432(src, s)
76	for {
77		const skipLog = 6
78		const doEvery = 1
79
80		nextS := s
81		var t int32
82		for {
83			nextHashS := hash4x64(cv, tableBits)
84			nextHashL := hash7(cv, tableBits)
85
86			s = nextS
87			nextS = s + doEvery + (s-nextEmit)>>skipLog
88			if nextS > sLimit {
89				goto emitRemainder
90			}
91			// Fetch a short+long candidate
92			sCandidate := e.table[nextHashS]
93			lCandidate := e.bTable[nextHashL]
94			next := load6432(src, nextS)
95			entry := tableEntry{offset: s + e.cur}
96			e.table[nextHashS] = entry
97			e.bTable[nextHashL] = entry
98
99			t = lCandidate.offset - e.cur
100			if s-t < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.offset-e.cur) {
101				// We got a long match. Use that.
102				break
103			}
104
105			t = sCandidate.offset - e.cur
106			if s-t < maxMatchOffset && uint32(cv) == load3232(src, sCandidate.offset-e.cur) {
107				// Found a 4 match...
108				lCandidate = e.bTable[hash7(next, tableBits)]
109
110				// If the next long is a candidate, check if we should use that instead...
111				lOff := nextS - (lCandidate.offset - e.cur)
112				if lOff < maxMatchOffset && load3232(src, lCandidate.offset-e.cur) == uint32(next) {
113					l1, l2 := matchLen(src[s+4:], src[t+4:]), matchLen(src[nextS+4:], src[nextS-lOff+4:])
114					if l2 > l1 {
115						s = nextS
116						t = lCandidate.offset - e.cur
117					}
118				}
119				break
120			}
121			cv = next
122		}
123
124		// A 4-byte match has been found. We'll later see if more than 4 bytes
125		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
126		// them as literal bytes.
127
128		// Extend the 4-byte match as long as possible.
129		l := e.matchlenLong(s+4, t+4, src) + 4
130
131		// Extend backwards
132		for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
133			s--
134			t--
135			l++
136		}
137		if nextEmit < s {
138			emitLiteral(dst, src[nextEmit:s])
139		}
140		if debugDeflate {
141			if t >= s {
142				panic("s-t")
143			}
144			if (s - t) > maxMatchOffset {
145				panic(fmt.Sprintln("mmo", t))
146			}
147			if l < baseMatchLength {
148				panic("bml")
149			}
150		}
151
152		dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
153		s += l
154		nextEmit = s
155		if nextS >= s {
156			s = nextS + 1
157		}
158
159		if s >= sLimit {
160			// Index first pair after match end.
161			if int(s+8) < len(src) {
162				cv := load6432(src, s)
163				e.table[hash4x64(cv, tableBits)] = tableEntry{offset: s + e.cur}
164				e.bTable[hash7(cv, tableBits)] = tableEntry{offset: s + e.cur}
165			}
166			goto emitRemainder
167		}
168
169		// Store every 3rd hash in-between
170		if true {
171			i := nextS
172			if i < s-1 {
173				cv := load6432(src, i)
174				t := tableEntry{offset: i + e.cur}
175				t2 := tableEntry{offset: t.offset + 1}
176				e.bTable[hash7(cv, tableBits)] = t
177				e.bTable[hash7(cv>>8, tableBits)] = t2
178				e.table[hash4u(uint32(cv>>8), tableBits)] = t2
179
180				i += 3
181				for ; i < s-1; i += 3 {
182					cv := load6432(src, i)
183					t := tableEntry{offset: i + e.cur}
184					t2 := tableEntry{offset: t.offset + 1}
185					e.bTable[hash7(cv, tableBits)] = t
186					e.bTable[hash7(cv>>8, tableBits)] = t2
187					e.table[hash4u(uint32(cv>>8), tableBits)] = t2
188				}
189			}
190		}
191
192		// We could immediately start working at s now, but to improve
193		// compression we first update the hash table at s-1 and at s.
194		x := load6432(src, s-1)
195		o := e.cur + s - 1
196		prevHashS := hash4x64(x, tableBits)
197		prevHashL := hash7(x, tableBits)
198		e.table[prevHashS] = tableEntry{offset: o}
199		e.bTable[prevHashL] = tableEntry{offset: o}
200		cv = x >> 8
201	}
202
203emitRemainder:
204	if int(nextEmit) < len(src) {
205		// If nothing was added, don't encode literals.
206		if dst.n == 0 {
207			return
208		}
209
210		emitLiteral(dst, src[nextEmit:])
211	}
212}
213