diff options
author | Rutger Broekhoff | 2024-01-02 18:56:31 +0100 |
---|---|---|
committer | Rutger Broekhoff | 2024-01-02 18:56:31 +0100 |
commit | 8db41da676ac8368ef7c2549d56239a5ff5eedde (patch) | |
tree | 09c427fd66de2ec1ebffc8342f5fdbb84b0701b5 /vendor/github.com/klauspost/compress/s2/encode_go.go | |
parent | d4f75fb6db22e57577867445a022227e70958931 (diff) | |
download | gitolfs3-8db41da676ac8368ef7c2549d56239a5ff5eedde.tar.gz gitolfs3-8db41da676ac8368ef7c2549d56239a5ff5eedde.zip |
Delete vendor directory
Diffstat (limited to 'vendor/github.com/klauspost/compress/s2/encode_go.go')
-rw-r--r-- | vendor/github.com/klauspost/compress/s2/encode_go.go | 729 |
1 files changed, 0 insertions, 729 deletions
diff --git a/vendor/github.com/klauspost/compress/s2/encode_go.go b/vendor/github.com/klauspost/compress/s2/encode_go.go deleted file mode 100644 index 6b393c3..0000000 --- a/vendor/github.com/klauspost/compress/s2/encode_go.go +++ /dev/null | |||
@@ -1,729 +0,0 @@ | |||
1 | //go:build !amd64 || appengine || !gc || noasm | ||
2 | // +build !amd64 appengine !gc noasm | ||
3 | |||
4 | package s2 | ||
5 | |||
6 | import ( | ||
7 | "bytes" | ||
8 | "math/bits" | ||
9 | ) | ||
10 | |||
11 | const hasAmd64Asm = false | ||
12 | |||
13 | // encodeBlock encodes a non-empty src to a guaranteed-large-enough dst. It | ||
14 | // assumes that the varint-encoded length of the decompressed bytes has already | ||
15 | // been written. | ||
16 | // | ||
17 | // It also assumes that: | ||
18 | // | ||
19 | // len(dst) >= MaxEncodedLen(len(src)) | ||
20 | func encodeBlock(dst, src []byte) (d int) { | ||
21 | if len(src) < minNonLiteralBlockSize { | ||
22 | return 0 | ||
23 | } | ||
24 | return encodeBlockGo(dst, src) | ||
25 | } | ||
26 | |||
27 | // encodeBlockBetter encodes a non-empty src to a guaranteed-large-enough dst. It | ||
28 | // assumes that the varint-encoded length of the decompressed bytes has already | ||
29 | // been written. | ||
30 | // | ||
31 | // It also assumes that: | ||
32 | // | ||
33 | // len(dst) >= MaxEncodedLen(len(src)) | ||
34 | func encodeBlockBetter(dst, src []byte) (d int) { | ||
35 | return encodeBlockBetterGo(dst, src) | ||
36 | } | ||
37 | |||
38 | // encodeBlockBetter encodes a non-empty src to a guaranteed-large-enough dst. It | ||
39 | // assumes that the varint-encoded length of the decompressed bytes has already | ||
40 | // been written. | ||
41 | // | ||
42 | // It also assumes that: | ||
43 | // | ||
44 | // len(dst) >= MaxEncodedLen(len(src)) | ||
45 | func encodeBlockBetterSnappy(dst, src []byte) (d int) { | ||
46 | return encodeBlockBetterSnappyGo(dst, src) | ||
47 | } | ||
48 | |||
49 | // encodeBlock encodes a non-empty src to a guaranteed-large-enough dst. It | ||
50 | // assumes that the varint-encoded length of the decompressed bytes has already | ||
51 | // been written. | ||
52 | // | ||
53 | // It also assumes that: | ||
54 | // | ||
55 | // len(dst) >= MaxEncodedLen(len(src)) | ||
56 | func encodeBlockSnappy(dst, src []byte) (d int) { | ||
57 | if len(src) < minNonLiteralBlockSize { | ||
58 | return 0 | ||
59 | } | ||
60 | return encodeBlockSnappyGo(dst, src) | ||
61 | } | ||
62 | |||
63 | // emitLiteral writes a literal chunk and returns the number of bytes written. | ||
64 | // | ||
65 | // It assumes that: | ||
66 | // | ||
67 | // dst is long enough to hold the encoded bytes | ||
68 | // 0 <= len(lit) && len(lit) <= math.MaxUint32 | ||
69 | func emitLiteral(dst, lit []byte) int { | ||
70 | if len(lit) == 0 { | ||
71 | return 0 | ||
72 | } | ||
73 | const num = 63<<2 | tagLiteral | ||
74 | i, n := 0, uint(len(lit)-1) | ||
75 | switch { | ||
76 | case n < 60: | ||
77 | dst[0] = uint8(n)<<2 | tagLiteral | ||
78 | i = 1 | ||
79 | case n < 1<<8: | ||
80 | dst[1] = uint8(n) | ||
81 | dst[0] = 60<<2 | tagLiteral | ||
82 | i = 2 | ||
83 | case n < 1<<16: | ||
84 | dst[2] = uint8(n >> 8) | ||
85 | dst[1] = uint8(n) | ||
86 | dst[0] = 61<<2 | tagLiteral | ||
87 | i = 3 | ||
88 | case n < 1<<24: | ||
89 | dst[3] = uint8(n >> 16) | ||
90 | dst[2] = uint8(n >> 8) | ||
91 | dst[1] = uint8(n) | ||
92 | dst[0] = 62<<2 | tagLiteral | ||
93 | i = 4 | ||
94 | default: | ||
95 | dst[4] = uint8(n >> 24) | ||
96 | dst[3] = uint8(n >> 16) | ||
97 | dst[2] = uint8(n >> 8) | ||
98 | dst[1] = uint8(n) | ||
99 | dst[0] = 63<<2 | tagLiteral | ||
100 | i = 5 | ||
101 | } | ||
102 | return i + copy(dst[i:], lit) | ||
103 | } | ||
104 | |||
105 | // emitRepeat writes a repeat chunk and returns the number of bytes written. | ||
106 | // Length must be at least 4 and < 1<<24 | ||
107 | func emitRepeat(dst []byte, offset, length int) int { | ||
108 | // Repeat offset, make length cheaper | ||
109 | length -= 4 | ||
110 | if length <= 4 { | ||
111 | dst[0] = uint8(length)<<2 | tagCopy1 | ||
112 | dst[1] = 0 | ||
113 | return 2 | ||
114 | } | ||
115 | if length < 8 && offset < 2048 { | ||
116 | // Encode WITH offset | ||
117 | dst[1] = uint8(offset) | ||
118 | dst[0] = uint8(offset>>8)<<5 | uint8(length)<<2 | tagCopy1 | ||
119 | return 2 | ||
120 | } | ||
121 | if length < (1<<8)+4 { | ||
122 | length -= 4 | ||
123 | dst[2] = uint8(length) | ||
124 | dst[1] = 0 | ||
125 | dst[0] = 5<<2 | tagCopy1 | ||
126 | return 3 | ||
127 | } | ||
128 | if length < (1<<16)+(1<<8) { | ||
129 | length -= 1 << 8 | ||
130 | dst[3] = uint8(length >> 8) | ||
131 | dst[2] = uint8(length >> 0) | ||
132 | dst[1] = 0 | ||
133 | dst[0] = 6<<2 | tagCopy1 | ||
134 | return 4 | ||
135 | } | ||
136 | const maxRepeat = (1 << 24) - 1 | ||
137 | length -= 1 << 16 | ||
138 | left := 0 | ||
139 | if length > maxRepeat { | ||
140 | left = length - maxRepeat + 4 | ||
141 | length = maxRepeat - 4 | ||
142 | } | ||
143 | dst[4] = uint8(length >> 16) | ||
144 | dst[3] = uint8(length >> 8) | ||
145 | dst[2] = uint8(length >> 0) | ||
146 | dst[1] = 0 | ||
147 | dst[0] = 7<<2 | tagCopy1 | ||
148 | if left > 0 { | ||
149 | return 5 + emitRepeat(dst[5:], offset, left) | ||
150 | } | ||
151 | return 5 | ||
152 | } | ||
153 | |||
154 | // emitCopy writes a copy chunk and returns the number of bytes written. | ||
155 | // | ||
156 | // It assumes that: | ||
157 | // | ||
158 | // dst is long enough to hold the encoded bytes | ||
159 | // 1 <= offset && offset <= math.MaxUint32 | ||
160 | // 4 <= length && length <= 1 << 24 | ||
161 | func emitCopy(dst []byte, offset, length int) int { | ||
162 | if offset >= 65536 { | ||
163 | i := 0 | ||
164 | if length > 64 { | ||
165 | // Emit a length 64 copy, encoded as 5 bytes. | ||
166 | dst[4] = uint8(offset >> 24) | ||
167 | dst[3] = uint8(offset >> 16) | ||
168 | dst[2] = uint8(offset >> 8) | ||
169 | dst[1] = uint8(offset) | ||
170 | dst[0] = 63<<2 | tagCopy4 | ||
171 | length -= 64 | ||
172 | if length >= 4 { | ||
173 | // Emit remaining as repeats | ||
174 | return 5 + emitRepeat(dst[5:], offset, length) | ||
175 | } | ||
176 | i = 5 | ||
177 | } | ||
178 | if length == 0 { | ||
179 | return i | ||
180 | } | ||
181 | // Emit a copy, offset encoded as 4 bytes. | ||
182 | dst[i+0] = uint8(length-1)<<2 | tagCopy4 | ||
183 | dst[i+1] = uint8(offset) | ||
184 | dst[i+2] = uint8(offset >> 8) | ||
185 | dst[i+3] = uint8(offset >> 16) | ||
186 | dst[i+4] = uint8(offset >> 24) | ||
187 | return i + 5 | ||
188 | } | ||
189 | |||
190 | // Offset no more than 2 bytes. | ||
191 | if length > 64 { | ||
192 | off := 3 | ||
193 | if offset < 2048 { | ||
194 | // emit 8 bytes as tagCopy1, rest as repeats. | ||
195 | dst[1] = uint8(offset) | ||
196 | dst[0] = uint8(offset>>8)<<5 | uint8(8-4)<<2 | tagCopy1 | ||
197 | length -= 8 | ||
198 | off = 2 | ||
199 | } else { | ||
200 | // Emit a length 60 copy, encoded as 3 bytes. | ||
201 | // Emit remaining as repeat value (minimum 4 bytes). | ||
202 | dst[2] = uint8(offset >> 8) | ||
203 | dst[1] = uint8(offset) | ||
204 | dst[0] = 59<<2 | tagCopy2 | ||
205 | length -= 60 | ||
206 | } | ||
207 | // Emit remaining as repeats, at least 4 bytes remain. | ||
208 | return off + emitRepeat(dst[off:], offset, length) | ||
209 | } | ||
210 | if length >= 12 || offset >= 2048 { | ||
211 | // Emit the remaining copy, encoded as 3 bytes. | ||
212 | dst[2] = uint8(offset >> 8) | ||
213 | dst[1] = uint8(offset) | ||
214 | dst[0] = uint8(length-1)<<2 | tagCopy2 | ||
215 | return 3 | ||
216 | } | ||
217 | // Emit the remaining copy, encoded as 2 bytes. | ||
218 | dst[1] = uint8(offset) | ||
219 | dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1 | ||
220 | return 2 | ||
221 | } | ||
222 | |||
223 | // emitCopyNoRepeat writes a copy chunk and returns the number of bytes written. | ||
224 | // | ||
225 | // It assumes that: | ||
226 | // | ||
227 | // dst is long enough to hold the encoded bytes | ||
228 | // 1 <= offset && offset <= math.MaxUint32 | ||
229 | // 4 <= length && length <= 1 << 24 | ||
230 | func emitCopyNoRepeat(dst []byte, offset, length int) int { | ||
231 | if offset >= 65536 { | ||
232 | i := 0 | ||
233 | if length > 64 { | ||
234 | // Emit a length 64 copy, encoded as 5 bytes. | ||
235 | dst[4] = uint8(offset >> 24) | ||
236 | dst[3] = uint8(offset >> 16) | ||
237 | dst[2] = uint8(offset >> 8) | ||
238 | dst[1] = uint8(offset) | ||
239 | dst[0] = 63<<2 | tagCopy4 | ||
240 | length -= 64 | ||
241 | if length >= 4 { | ||
242 | // Emit remaining as repeats | ||
243 | return 5 + emitCopyNoRepeat(dst[5:], offset, length) | ||
244 | } | ||
245 | i = 5 | ||
246 | } | ||
247 | if length == 0 { | ||
248 | return i | ||
249 | } | ||
250 | // Emit a copy, offset encoded as 4 bytes. | ||
251 | dst[i+0] = uint8(length-1)<<2 | tagCopy4 | ||
252 | dst[i+1] = uint8(offset) | ||
253 | dst[i+2] = uint8(offset >> 8) | ||
254 | dst[i+3] = uint8(offset >> 16) | ||
255 | dst[i+4] = uint8(offset >> 24) | ||
256 | return i + 5 | ||
257 | } | ||
258 | |||
259 | // Offset no more than 2 bytes. | ||
260 | if length > 64 { | ||
261 | // Emit a length 60 copy, encoded as 3 bytes. | ||
262 | // Emit remaining as repeat value (minimum 4 bytes). | ||
263 | dst[2] = uint8(offset >> 8) | ||
264 | dst[1] = uint8(offset) | ||
265 | dst[0] = 59<<2 | tagCopy2 | ||
266 | length -= 60 | ||
267 | // Emit remaining as repeats, at least 4 bytes remain. | ||
268 | return 3 + emitCopyNoRepeat(dst[3:], offset, length) | ||
269 | } | ||
270 | if length >= 12 || offset >= 2048 { | ||
271 | // Emit the remaining copy, encoded as 3 bytes. | ||
272 | dst[2] = uint8(offset >> 8) | ||
273 | dst[1] = uint8(offset) | ||
274 | dst[0] = uint8(length-1)<<2 | tagCopy2 | ||
275 | return 3 | ||
276 | } | ||
277 | // Emit the remaining copy, encoded as 2 bytes. | ||
278 | dst[1] = uint8(offset) | ||
279 | dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1 | ||
280 | return 2 | ||
281 | } | ||
282 | |||
283 | // matchLen returns how many bytes match in a and b | ||
284 | // | ||
285 | // It assumes that: | ||
286 | // | ||
287 | // len(a) <= len(b) | ||
288 | func matchLen(a []byte, b []byte) int { | ||
289 | b = b[:len(a)] | ||
290 | var checked int | ||
291 | if len(a) > 4 { | ||
292 | // Try 4 bytes first | ||
293 | if diff := load32(a, 0) ^ load32(b, 0); diff != 0 { | ||
294 | return bits.TrailingZeros32(diff) >> 3 | ||
295 | } | ||
296 | // Switch to 8 byte matching. | ||
297 | checked = 4 | ||
298 | a = a[4:] | ||
299 | b = b[4:] | ||
300 | for len(a) >= 8 { | ||
301 | b = b[:len(a)] | ||
302 | if diff := load64(a, 0) ^ load64(b, 0); diff != 0 { | ||
303 | return checked + (bits.TrailingZeros64(diff) >> 3) | ||
304 | } | ||
305 | checked += 8 | ||
306 | a = a[8:] | ||
307 | b = b[8:] | ||
308 | } | ||
309 | } | ||
310 | b = b[:len(a)] | ||
311 | for i := range a { | ||
312 | if a[i] != b[i] { | ||
313 | return int(i) + checked | ||
314 | } | ||
315 | } | ||
316 | return len(a) + checked | ||
317 | } | ||
318 | |||
319 | // input must be > inputMargin | ||
320 | func calcBlockSize(src []byte) (d int) { | ||
321 | // Initialize the hash table. | ||
322 | const ( | ||
323 | tableBits = 13 | ||
324 | maxTableSize = 1 << tableBits | ||
325 | ) | ||
326 | |||
327 | var table [maxTableSize]uint32 | ||
328 | |||
329 | // sLimit is when to stop looking for offset/length copies. The inputMargin | ||
330 | // lets us use a fast path for emitLiteral in the main loop, while we are | ||
331 | // looking for copies. | ||
332 | sLimit := len(src) - inputMargin | ||
333 | |||
334 | // Bail if we can't compress to at least this. | ||
335 | dstLimit := len(src) - len(src)>>5 - 5 | ||
336 | |||
337 | // nextEmit is where in src the next emitLiteral should start from. | ||
338 | nextEmit := 0 | ||
339 | |||
340 | // The encoded form must start with a literal, as there are no previous | ||
341 | // bytes to copy, so we start looking for hash matches at s == 1. | ||
342 | s := 1 | ||
343 | cv := load64(src, s) | ||
344 | |||
345 | // We search for a repeat at -1, but don't output repeats when nextEmit == 0 | ||
346 | repeat := 1 | ||
347 | |||
348 | for { | ||
349 | candidate := 0 | ||
350 | for { | ||
351 | // Next src position to check | ||
352 | nextS := s + (s-nextEmit)>>6 + 4 | ||
353 | if nextS > sLimit { | ||
354 | goto emitRemainder | ||
355 | } | ||
356 | hash0 := hash6(cv, tableBits) | ||
357 | hash1 := hash6(cv>>8, tableBits) | ||
358 | candidate = int(table[hash0]) | ||
359 | candidate2 := int(table[hash1]) | ||
360 | table[hash0] = uint32(s) | ||
361 | table[hash1] = uint32(s + 1) | ||
362 | hash2 := hash6(cv>>16, tableBits) | ||
363 | |||
364 | // Check repeat at offset checkRep. | ||
365 | const checkRep = 1 | ||
366 | if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) { | ||
367 | base := s + checkRep | ||
368 | // Extend back | ||
369 | for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; { | ||
370 | i-- | ||
371 | base-- | ||
372 | } | ||
373 | d += emitLiteralSize(src[nextEmit:base]) | ||
374 | |||
375 | // Extend forward | ||
376 | candidate := s - repeat + 4 + checkRep | ||
377 | s += 4 + checkRep | ||
378 | for s <= sLimit { | ||
379 | if diff := load64(src, s) ^ load64(src, candidate); diff != 0 { | ||
380 | s += bits.TrailingZeros64(diff) >> 3 | ||
381 | break | ||
382 | } | ||
383 | s += 8 | ||
384 | candidate += 8 | ||
385 | } | ||
386 | |||
387 | d += emitCopyNoRepeatSize(repeat, s-base) | ||
388 | nextEmit = s | ||
389 | if s >= sLimit { | ||
390 | goto emitRemainder | ||
391 | } | ||
392 | |||
393 | cv = load64(src, s) | ||
394 | continue | ||
395 | } | ||
396 | |||
397 | if uint32(cv) == load32(src, candidate) { | ||
398 | break | ||
399 | } | ||
400 | candidate = int(table[hash2]) | ||
401 | if uint32(cv>>8) == load32(src, candidate2) { | ||
402 | table[hash2] = uint32(s + 2) | ||
403 | candidate = candidate2 | ||
404 | s++ | ||
405 | break | ||
406 | } | ||
407 | table[hash2] = uint32(s + 2) | ||
408 | if uint32(cv>>16) == load32(src, candidate) { | ||
409 | s += 2 | ||
410 | break | ||
411 | } | ||
412 | |||
413 | cv = load64(src, nextS) | ||
414 | s = nextS | ||
415 | } | ||
416 | |||
417 | // Extend backwards | ||
418 | for candidate > 0 && s > nextEmit && src[candidate-1] == src[s-1] { | ||
419 | candidate-- | ||
420 | s-- | ||
421 | } | ||
422 | |||
423 | // Bail if we exceed the maximum size. | ||
424 | if d+(s-nextEmit) > dstLimit { | ||
425 | return 0 | ||
426 | } | ||
427 | |||
428 | // A 4-byte match has been found. We'll later see if more than 4 bytes | ||
429 | // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit | ||
430 | // them as literal bytes. | ||
431 | |||
432 | d += emitLiteralSize(src[nextEmit:s]) | ||
433 | |||
434 | // Call emitCopy, and then see if another emitCopy could be our next | ||
435 | // move. Repeat until we find no match for the input immediately after | ||
436 | // what was consumed by the last emitCopy call. | ||
437 | // | ||
438 | // If we exit this loop normally then we need to call emitLiteral next, | ||
439 | // though we don't yet know how big the literal will be. We handle that | ||
440 | // by proceeding to the next iteration of the main loop. We also can | ||
441 | // exit this loop via goto if we get close to exhausting the input. | ||
442 | for { | ||
443 | // Invariant: we have a 4-byte match at s, and no need to emit any | ||
444 | // literal bytes prior to s. | ||
445 | base := s | ||
446 | repeat = base - candidate | ||
447 | |||
448 | // Extend the 4-byte match as long as possible. | ||
449 | s += 4 | ||
450 | candidate += 4 | ||
451 | for s <= len(src)-8 { | ||
452 | if diff := load64(src, s) ^ load64(src, candidate); diff != 0 { | ||
453 | s += bits.TrailingZeros64(diff) >> 3 | ||
454 | break | ||
455 | } | ||
456 | s += 8 | ||
457 | candidate += 8 | ||
458 | } | ||
459 | |||
460 | d += emitCopyNoRepeatSize(repeat, s-base) | ||
461 | if false { | ||
462 | // Validate match. | ||
463 | a := src[base:s] | ||
464 | b := src[base-repeat : base-repeat+(s-base)] | ||
465 | if !bytes.Equal(a, b) { | ||
466 | panic("mismatch") | ||
467 | } | ||
468 | } | ||
469 | |||
470 | nextEmit = s | ||
471 | if s >= sLimit { | ||
472 | goto emitRemainder | ||
473 | } | ||
474 | |||
475 | if d > dstLimit { | ||
476 | // Do we have space for more, if not bail. | ||
477 | return 0 | ||
478 | } | ||
479 | // Check for an immediate match, otherwise start search at s+1 | ||
480 | x := load64(src, s-2) | ||
481 | m2Hash := hash6(x, tableBits) | ||
482 | currHash := hash6(x>>16, tableBits) | ||
483 | candidate = int(table[currHash]) | ||
484 | table[m2Hash] = uint32(s - 2) | ||
485 | table[currHash] = uint32(s) | ||
486 | if uint32(x>>16) != load32(src, candidate) { | ||
487 | cv = load64(src, s+1) | ||
488 | s++ | ||
489 | break | ||
490 | } | ||
491 | } | ||
492 | } | ||
493 | |||
494 | emitRemainder: | ||
495 | if nextEmit < len(src) { | ||
496 | // Bail if we exceed the maximum size. | ||
497 | if d+len(src)-nextEmit > dstLimit { | ||
498 | return 0 | ||
499 | } | ||
500 | d += emitLiteralSize(src[nextEmit:]) | ||
501 | } | ||
502 | return d | ||
503 | } | ||
504 | |||
505 | // length must be > inputMargin. | ||
506 | func calcBlockSizeSmall(src []byte) (d int) { | ||
507 | // Initialize the hash table. | ||
508 | const ( | ||
509 | tableBits = 9 | ||
510 | maxTableSize = 1 << tableBits | ||
511 | ) | ||
512 | |||
513 | var table [maxTableSize]uint32 | ||
514 | |||
515 | // sLimit is when to stop looking for offset/length copies. The inputMargin | ||
516 | // lets us use a fast path for emitLiteral in the main loop, while we are | ||
517 | // looking for copies. | ||
518 | sLimit := len(src) - inputMargin | ||
519 | |||
520 | // Bail if we can't compress to at least this. | ||
521 | dstLimit := len(src) - len(src)>>5 - 5 | ||
522 | |||
523 | // nextEmit is where in src the next emitLiteral should start from. | ||
524 | nextEmit := 0 | ||
525 | |||
526 | // The encoded form must start with a literal, as there are no previous | ||
527 | // bytes to copy, so we start looking for hash matches at s == 1. | ||
528 | s := 1 | ||
529 | cv := load64(src, s) | ||
530 | |||
531 | // We search for a repeat at -1, but don't output repeats when nextEmit == 0 | ||
532 | repeat := 1 | ||
533 | |||
534 | for { | ||
535 | candidate := 0 | ||
536 | for { | ||
537 | // Next src position to check | ||
538 | nextS := s + (s-nextEmit)>>6 + 4 | ||
539 | if nextS > sLimit { | ||
540 | goto emitRemainder | ||
541 | } | ||
542 | hash0 := hash6(cv, tableBits) | ||
543 | hash1 := hash6(cv>>8, tableBits) | ||
544 | candidate = int(table[hash0]) | ||
545 | candidate2 := int(table[hash1]) | ||
546 | table[hash0] = uint32(s) | ||
547 | table[hash1] = uint32(s + 1) | ||
548 | hash2 := hash6(cv>>16, tableBits) | ||
549 | |||
550 | // Check repeat at offset checkRep. | ||
551 | const checkRep = 1 | ||
552 | if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) { | ||
553 | base := s + checkRep | ||
554 | // Extend back | ||
555 | for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; { | ||
556 | i-- | ||
557 | base-- | ||
558 | } | ||
559 | d += emitLiteralSize(src[nextEmit:base]) | ||
560 | |||
561 | // Extend forward | ||
562 | candidate := s - repeat + 4 + checkRep | ||
563 | s += 4 + checkRep | ||
564 | for s <= sLimit { | ||
565 | if diff := load64(src, s) ^ load64(src, candidate); diff != 0 { | ||
566 | s += bits.TrailingZeros64(diff) >> 3 | ||
567 | break | ||
568 | } | ||
569 | s += 8 | ||
570 | candidate += 8 | ||
571 | } | ||
572 | |||
573 | d += emitCopyNoRepeatSize(repeat, s-base) | ||
574 | nextEmit = s | ||
575 | if s >= sLimit { | ||
576 | goto emitRemainder | ||
577 | } | ||
578 | |||
579 | cv = load64(src, s) | ||
580 | continue | ||
581 | } | ||
582 | |||
583 | if uint32(cv) == load32(src, candidate) { | ||
584 | break | ||
585 | } | ||
586 | candidate = int(table[hash2]) | ||
587 | if uint32(cv>>8) == load32(src, candidate2) { | ||
588 | table[hash2] = uint32(s + 2) | ||
589 | candidate = candidate2 | ||
590 | s++ | ||
591 | break | ||
592 | } | ||
593 | table[hash2] = uint32(s + 2) | ||
594 | if uint32(cv>>16) == load32(src, candidate) { | ||
595 | s += 2 | ||
596 | break | ||
597 | } | ||
598 | |||
599 | cv = load64(src, nextS) | ||
600 | s = nextS | ||
601 | } | ||
602 | |||
603 | // Extend backwards | ||
604 | for candidate > 0 && s > nextEmit && src[candidate-1] == src[s-1] { | ||
605 | candidate-- | ||
606 | s-- | ||
607 | } | ||
608 | |||
609 | // Bail if we exceed the maximum size. | ||
610 | if d+(s-nextEmit) > dstLimit { | ||
611 | return 0 | ||
612 | } | ||
613 | |||
614 | // A 4-byte match has been found. We'll later see if more than 4 bytes | ||
615 | // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit | ||
616 | // them as literal bytes. | ||
617 | |||
618 | d += emitLiteralSize(src[nextEmit:s]) | ||
619 | |||
620 | // Call emitCopy, and then see if another emitCopy could be our next | ||
621 | // move. Repeat until we find no match for the input immediately after | ||
622 | // what was consumed by the last emitCopy call. | ||
623 | // | ||
624 | // If we exit this loop normally then we need to call emitLiteral next, | ||
625 | // though we don't yet know how big the literal will be. We handle that | ||
626 | // by proceeding to the next iteration of the main loop. We also can | ||
627 | // exit this loop via goto if we get close to exhausting the input. | ||
628 | for { | ||
629 | // Invariant: we have a 4-byte match at s, and no need to emit any | ||
630 | // literal bytes prior to s. | ||
631 | base := s | ||
632 | repeat = base - candidate | ||
633 | |||
634 | // Extend the 4-byte match as long as possible. | ||
635 | s += 4 | ||
636 | candidate += 4 | ||
637 | for s <= len(src)-8 { | ||
638 | if diff := load64(src, s) ^ load64(src, candidate); diff != 0 { | ||
639 | s += bits.TrailingZeros64(diff) >> 3 | ||
640 | break | ||
641 | } | ||
642 | s += 8 | ||
643 | candidate += 8 | ||
644 | } | ||
645 | |||
646 | d += emitCopyNoRepeatSize(repeat, s-base) | ||
647 | if false { | ||
648 | // Validate match. | ||
649 | a := src[base:s] | ||
650 | b := src[base-repeat : base-repeat+(s-base)] | ||
651 | if !bytes.Equal(a, b) { | ||
652 | panic("mismatch") | ||
653 | } | ||
654 | } | ||
655 | |||
656 | nextEmit = s | ||
657 | if s >= sLimit { | ||
658 | goto emitRemainder | ||
659 | } | ||
660 | |||
661 | if d > dstLimit { | ||
662 | // Do we have space for more, if not bail. | ||
663 | return 0 | ||
664 | } | ||
665 | // Check for an immediate match, otherwise start search at s+1 | ||
666 | x := load64(src, s-2) | ||
667 | m2Hash := hash6(x, tableBits) | ||
668 | currHash := hash6(x>>16, tableBits) | ||
669 | candidate = int(table[currHash]) | ||
670 | table[m2Hash] = uint32(s - 2) | ||
671 | table[currHash] = uint32(s) | ||
672 | if uint32(x>>16) != load32(src, candidate) { | ||
673 | cv = load64(src, s+1) | ||
674 | s++ | ||
675 | break | ||
676 | } | ||
677 | } | ||
678 | } | ||
679 | |||
680 | emitRemainder: | ||
681 | if nextEmit < len(src) { | ||
682 | // Bail if we exceed the maximum size. | ||
683 | if d+len(src)-nextEmit > dstLimit { | ||
684 | return 0 | ||
685 | } | ||
686 | d += emitLiteralSize(src[nextEmit:]) | ||
687 | } | ||
688 | return d | ||
689 | } | ||
690 | |||
691 | // emitLiteral writes a literal chunk and returns the number of bytes written. | ||
692 | // | ||
693 | // It assumes that: | ||
694 | // | ||
695 | // dst is long enough to hold the encoded bytes | ||
696 | // 0 <= len(lit) && len(lit) <= math.MaxUint32 | ||
697 | func emitLiteralSize(lit []byte) int { | ||
698 | if len(lit) == 0 { | ||
699 | return 0 | ||
700 | } | ||
701 | switch { | ||
702 | case len(lit) <= 60: | ||
703 | return len(lit) + 1 | ||
704 | case len(lit) <= 1<<8: | ||
705 | return len(lit) + 2 | ||
706 | case len(lit) <= 1<<16: | ||
707 | return len(lit) + 3 | ||
708 | case len(lit) <= 1<<24: | ||
709 | return len(lit) + 4 | ||
710 | default: | ||
711 | return len(lit) + 5 | ||
712 | } | ||
713 | } | ||
714 | |||
715 | func cvtLZ4BlockAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) { | ||
716 | panic("cvtLZ4BlockAsm should be unreachable") | ||
717 | } | ||
718 | |||
719 | func cvtLZ4BlockSnappyAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) { | ||
720 | panic("cvtLZ4BlockSnappyAsm should be unreachable") | ||
721 | } | ||
722 | |||
723 | func cvtLZ4sBlockAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) { | ||
724 | panic("cvtLZ4sBlockAsm should be unreachable") | ||
725 | } | ||
726 | |||
727 | func cvtLZ4sBlockSnappyAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) { | ||
728 | panic("cvtLZ4sBlockSnappyAsm should be unreachable") | ||
729 | } | ||