source: code/trunk/vendor/github.com/klauspost/compress/flate/level5.go@ 822

Last change on this file since 822 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.0 KB
Line 
1package flate
2
3import "fmt"
4
5type fastEncL5 struct {
6 fastGen
7 table [tableSize]tableEntry
8 bTable [tableSize]tableEntryPrev
9}
10
11func (e *fastEncL5) 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 for {
84 const skipLog = 6
85 const doEvery = 1
86
87 nextS := s
88 var l int32
89 var t int32
90 for {
91 nextHashS := hash4x64(cv, tableBits)
92 nextHashL := hash7(cv, tableBits)
93
94 s = nextS
95 nextS = s + doEvery + (s-nextEmit)>>skipLog
96 if nextS > sLimit {
97 goto emitRemainder
98 }
99 // Fetch a short+long candidate
100 sCandidate := e.table[nextHashS]
101 lCandidate := e.bTable[nextHashL]
102 next := load6432(src, nextS)
103 entry := tableEntry{offset: s + e.cur}
104 e.table[nextHashS] = entry
105 eLong := &e.bTable[nextHashL]
106 eLong.Cur, eLong.Prev = entry, eLong.Cur
107
108 nextHashS = hash4x64(next, tableBits)
109 nextHashL = hash7(next, tableBits)
110
111 t = lCandidate.Cur.offset - e.cur
112 if s-t < maxMatchOffset {
113 if uint32(cv) == load3232(src, lCandidate.Cur.offset-e.cur) {
114 // Store the next match
115 e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
116 eLong := &e.bTable[nextHashL]
117 eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
118
119 t2 := lCandidate.Prev.offset - e.cur
120 if s-t2 < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.Prev.offset-e.cur) {
121 l = e.matchlen(s+4, t+4, src) + 4
122 ml1 := e.matchlen(s+4, t2+4, src) + 4
123 if ml1 > l {
124 t = t2
125 l = ml1
126 break
127 }
128 }
129 break
130 }
131 t = lCandidate.Prev.offset - e.cur
132 if s-t < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.Prev.offset-e.cur) {
133 // Store the next match
134 e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
135 eLong := &e.bTable[nextHashL]
136 eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
137 break
138 }
139 }
140
141 t = sCandidate.offset - e.cur
142 if s-t < maxMatchOffset && uint32(cv) == load3232(src, sCandidate.offset-e.cur) {
143 // Found a 4 match...
144 l = e.matchlen(s+4, t+4, src) + 4
145 lCandidate = e.bTable[nextHashL]
146 // Store the next match
147
148 e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
149 eLong := &e.bTable[nextHashL]
150 eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
151
152 // If the next long is a candidate, use that...
153 t2 := lCandidate.Cur.offset - e.cur
154 if nextS-t2 < maxMatchOffset {
155 if load3232(src, lCandidate.Cur.offset-e.cur) == uint32(next) {
156 ml := e.matchlen(nextS+4, t2+4, src) + 4
157 if ml > l {
158 t = t2
159 s = nextS
160 l = ml
161 break
162 }
163 }
164 // If the previous long is a candidate, use that...
165 t2 = lCandidate.Prev.offset - e.cur
166 if nextS-t2 < maxMatchOffset && load3232(src, lCandidate.Prev.offset-e.cur) == uint32(next) {
167 ml := e.matchlen(nextS+4, t2+4, src) + 4
168 if ml > l {
169 t = t2
170 s = nextS
171 l = ml
172 break
173 }
174 }
175 }
176 break
177 }
178 cv = next
179 }
180
181 // A 4-byte match has been found. We'll later see if more than 4 bytes
182 // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
183 // them as literal bytes.
184
185 // Extend the 4-byte match as long as possible.
186 if l == 0 {
187 l = e.matchlenLong(s+4, t+4, src) + 4
188 } else if l == maxMatchLength {
189 l += e.matchlenLong(s+l, t+l, src)
190 }
191 // Extend backwards
192 for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
193 s--
194 t--
195 l++
196 }
197 if nextEmit < s {
198 emitLiteral(dst, src[nextEmit:s])
199 }
200 if debugDeflate {
201 if t >= s {
202 panic(fmt.Sprintln("s-t", s, t))
203 }
204 if (s - t) > maxMatchOffset {
205 panic(fmt.Sprintln("mmo", s-t))
206 }
207 if l < baseMatchLength {
208 panic("bml")
209 }
210 }
211
212 dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
213 s += l
214 nextEmit = s
215 if nextS >= s {
216 s = nextS + 1
217 }
218
219 if s >= sLimit {
220 goto emitRemainder
221 }
222
223 // Store every 3rd hash in-between.
224 if true {
225 const hashEvery = 3
226 i := s - l + 1
227 if i < s-1 {
228 cv := load6432(src, i)
229 t := tableEntry{offset: i + e.cur}
230 e.table[hash4x64(cv, tableBits)] = t
231 eLong := &e.bTable[hash7(cv, tableBits)]
232 eLong.Cur, eLong.Prev = t, eLong.Cur
233
234 // Do an long at i+1
235 cv >>= 8
236 t = tableEntry{offset: t.offset + 1}
237 eLong = &e.bTable[hash7(cv, tableBits)]
238 eLong.Cur, eLong.Prev = t, eLong.Cur
239
240 // We only have enough bits for a short entry at i+2
241 cv >>= 8
242 t = tableEntry{offset: t.offset + 1}
243 e.table[hash4x64(cv, tableBits)] = t
244
245 // Skip one - otherwise we risk hitting 's'
246 i += 4
247 for ; i < s-1; i += hashEvery {
248 cv := load6432(src, i)
249 t := tableEntry{offset: i + e.cur}
250 t2 := tableEntry{offset: t.offset + 1}
251 eLong := &e.bTable[hash7(cv, tableBits)]
252 eLong.Cur, eLong.Prev = t, eLong.Cur
253 e.table[hash4u(uint32(cv>>8), tableBits)] = t2
254 }
255 }
256 }
257
258 // We could immediately start working at s now, but to improve
259 // compression we first update the hash table at s-1 and at s.
260 x := load6432(src, s-1)
261 o := e.cur + s - 1
262 prevHashS := hash4x64(x, tableBits)
263 prevHashL := hash7(x, tableBits)
264 e.table[prevHashS] = tableEntry{offset: o}
265 eLong := &e.bTable[prevHashL]
266 eLong.Cur, eLong.Prev = tableEntry{offset: o}, eLong.Cur
267 cv = x >> 8
268 }
269
270emitRemainder:
271 if int(nextEmit) < len(src) {
272 // If nothing was added, don't encode literals.
273 if dst.n == 0 {
274 return
275 }
276
277 emitLiteral(dst, src[nextEmit:])
278 }
279}
Note: See TracBrowser for help on using the repository browser.