source: code/trunk/vendor/github.com/klauspost/compress/flate/level6.go@ 824

Last change on this file since 824 was 822, checked in by yakumo.izuru, 22 months ago

Prefer immortal.run over runit and rc.d, use vendored modules
for convenience.

Signed-off-by: Izuru Yakumo <yakumo.izuru@…>
File size: 7.2 KB
Line 
1package flate
2
3import "fmt"
4
5type fastEncL6 struct {
6 fastGen
7 table [tableSize]tableEntry
8 bTable [tableSize]tableEntryPrev
9}
10
11func (e *fastEncL6) 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
20 // Protect against e.cur wraparound.
21 for e.cur >= bufferReset {
22 if len(e.hist) == 0 {
23 for i := range e.table[:] {
24 e.table[i] = tableEntry{}
25 }
26 for i := range e.bTable[:] {
27 e.bTable[i] = tableEntryPrev{}
28 }
29 e.cur = maxMatchOffset
30 break
31 }
32 // Shift down everything in the table that isn't already too far away.
33 minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
34 for i := range e.table[:] {
35 v := e.table[i].offset
36 if v <= minOff {
37 v = 0
38 } else {
39 v = v - e.cur + maxMatchOffset
40 }
41 e.table[i].offset = v
42 }
43 for i := range e.bTable[:] {
44 v := e.bTable[i]
45 if v.Cur.offset <= minOff {
46 v.Cur.offset = 0
47 v.Prev.offset = 0
48 } else {
49 v.Cur.offset = v.Cur.offset - e.cur + maxMatchOffset
50 if v.Prev.offset <= minOff {
51 v.Prev.offset = 0
52 } else {
53 v.Prev.offset = v.Prev.offset - e.cur + maxMatchOffset
54 }
55 }
56 e.bTable[i] = v
57 }
58 e.cur = maxMatchOffset
59 }
60
61 s := e.addBlock(src)
62
63 // This check isn't in the Snappy implementation, but there, the caller
64 // instead of the callee handles this case.
65 if len(src) < minNonLiteralBlockSize {
66 // We do not fill the token table.
67 // This will be picked up by caller.
68 dst.n = uint16(len(src))
69 return
70 }
71
72 // Override src
73 src = e.hist
74 nextEmit := s
75
76 // sLimit is when to stop looking for offset/length copies. The inputMargin
77 // lets us use a fast path for emitLiteral in the main loop, while we are
78 // looking for copies.
79 sLimit := int32(len(src) - inputMargin)
80
81 // nextEmit is where in src the next emitLiteral should start from.
82 cv := load6432(src, s)
83 // Repeat MUST be > 1 and within range
84 repeat := int32(1)
85 for {
86 const skipLog = 7
87 const doEvery = 1
88
89 nextS := s
90 var l int32
91 var t int32
92 for {
93 nextHashS := hash4x64(cv, tableBits)
94 nextHashL := hash7(cv, tableBits)
95 s = nextS
96 nextS = s + doEvery + (s-nextEmit)>>skipLog
97 if nextS > sLimit {
98 goto emitRemainder
99 }
100 // Fetch a short+long candidate
101 sCandidate := e.table[nextHashS]
102 lCandidate := e.bTable[nextHashL]
103 next := load6432(src, nextS)
104 entry := tableEntry{offset: s + e.cur}
105 e.table[nextHashS] = entry
106 eLong := &e.bTable[nextHashL]
107 eLong.Cur, eLong.Prev = entry, eLong.Cur
108
109 // Calculate hashes of 'next'
110 nextHashS = hash4x64(next, tableBits)
111 nextHashL = hash7(next, tableBits)
112
113 t = lCandidate.Cur.offset - e.cur
114 if s-t < maxMatchOffset {
115 if uint32(cv) == load3232(src, lCandidate.Cur.offset-e.cur) {
116 // Long candidate matches at least 4 bytes.
117
118 // Store the next match
119 e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
120 eLong := &e.bTable[nextHashL]
121 eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
122
123 // Check the previous long candidate as well.
124 t2 := lCandidate.Prev.offset - e.cur
125 if s-t2 < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.Prev.offset-e.cur) {
126 l = e.matchlen(s+4, t+4, src) + 4
127 ml1 := e.matchlen(s+4, t2+4, src) + 4
128 if ml1 > l {
129 t = t2
130 l = ml1
131 break
132 }
133 }
134 break
135 }
136 // Current value did not match, but check if previous long value does.
137 t = lCandidate.Prev.offset - e.cur
138 if s-t < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.Prev.offset-e.cur) {
139 // Store the next match
140 e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
141 eLong := &e.bTable[nextHashL]
142 eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
143 break
144 }
145 }
146
147 t = sCandidate.offset - e.cur
148 if s-t < maxMatchOffset && uint32(cv) == load3232(src, sCandidate.offset-e.cur) {
149 // Found a 4 match...
150 l = e.matchlen(s+4, t+4, src) + 4
151
152 // Look up next long candidate (at nextS)
153 lCandidate = e.bTable[nextHashL]
154
155 // Store the next match
156 e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
157 eLong := &e.bTable[nextHashL]
158 eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
159
160 // Check repeat at s + repOff
161 const repOff = 1
162 t2 := s - repeat + repOff
163 if load3232(src, t2) == uint32(cv>>(8*repOff)) {
164 ml := e.matchlen(s+4+repOff, t2+4, src) + 4
165 if ml > l {
166 t = t2
167 l = ml
168 s += repOff
169 // Not worth checking more.
170 break
171 }
172 }
173
174 // If the next long is a candidate, use that...
175 t2 = lCandidate.Cur.offset - e.cur
176 if nextS-t2 < maxMatchOffset {
177 if load3232(src, lCandidate.Cur.offset-e.cur) == uint32(next) {
178 ml := e.matchlen(nextS+4, t2+4, src) + 4
179 if ml > l {
180 t = t2
181 s = nextS
182 l = ml
183 // This is ok, but check previous as well.
184 }
185 }
186 // If the previous long is a candidate, use that...
187 t2 = lCandidate.Prev.offset - e.cur
188 if nextS-t2 < maxMatchOffset && load3232(src, lCandidate.Prev.offset-e.cur) == uint32(next) {
189 ml := e.matchlen(nextS+4, t2+4, src) + 4
190 if ml > l {
191 t = t2
192 s = nextS
193 l = ml
194 break
195 }
196 }
197 }
198 break
199 }
200 cv = next
201 }
202
203 // A 4-byte match has been found. We'll later see if more than 4 bytes
204 // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
205 // them as literal bytes.
206
207 // Extend the 4-byte match as long as possible.
208 if l == 0 {
209 l = e.matchlenLong(s+4, t+4, src) + 4
210 } else if l == maxMatchLength {
211 l += e.matchlenLong(s+l, t+l, src)
212 }
213
214 // Extend backwards
215 for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
216 s--
217 t--
218 l++
219 }
220 if nextEmit < s {
221 emitLiteral(dst, src[nextEmit:s])
222 }
223 if false {
224 if t >= s {
225 panic(fmt.Sprintln("s-t", s, t))
226 }
227 if (s - t) > maxMatchOffset {
228 panic(fmt.Sprintln("mmo", s-t))
229 }
230 if l < baseMatchLength {
231 panic("bml")
232 }
233 }
234
235 dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
236 repeat = s - t
237 s += l
238 nextEmit = s
239 if nextS >= s {
240 s = nextS + 1
241 }
242
243 if s >= sLimit {
244 // Index after match end.
245 for i := nextS + 1; i < int32(len(src))-8; i += 2 {
246 cv := load6432(src, i)
247 e.table[hash4x64(cv, tableBits)] = tableEntry{offset: i + e.cur}
248 eLong := &e.bTable[hash7(cv, tableBits)]
249 eLong.Cur, eLong.Prev = tableEntry{offset: i + e.cur}, eLong.Cur
250 }
251 goto emitRemainder
252 }
253
254 // Store every long hash in-between and every second short.
255 if true {
256 for i := nextS + 1; i < s-1; i += 2 {
257 cv := load6432(src, i)
258 t := tableEntry{offset: i + e.cur}
259 t2 := tableEntry{offset: t.offset + 1}
260 eLong := &e.bTable[hash7(cv, tableBits)]
261 eLong2 := &e.bTable[hash7(cv>>8, tableBits)]
262 e.table[hash4x64(cv, tableBits)] = t
263 eLong.Cur, eLong.Prev = t, eLong.Cur
264 eLong2.Cur, eLong2.Prev = t2, eLong2.Cur
265 }
266 }
267
268 // We could immediately start working at s now, but to improve
269 // compression we first update the hash table at s-1 and at s.
270 cv = load6432(src, s)
271 }
272
273emitRemainder:
274 if int(nextEmit) < len(src) {
275 // If nothing was added, don't encode literals.
276 if dst.n == 0 {
277 return
278 }
279
280 emitLiteral(dst, src[nextEmit:])
281 }
282}
Note: See TracBrowser for help on using the repository browser.