Debian Codegraph @

s2/_generate/gen.go

raw
1 package main
2
3 //go:generate go run gen.go -out ../encodeblock_amd64.s -stubs ../encodeblock_amd64.go -pkg=s2
4 //go:generate gofmt -w ../encodeblock_amd64.go
5 //go:generate go run cleanup.go ../encodeblock_amd64.s
6
7 import (
8 "flag"
9 "fmt"
10 "math"
11 "math/rand"
12 "runtime"
13 "strings"
14
15 . "github.com/mmcloughlin/avo/build"
16 "github.com/mmcloughlin/avo/buildtags"
17 . "github.com/mmcloughlin/avo/operand"
18 "github.com/mmcloughlin/avo/reg"
19 )
20
21 // insert extra checks here and there.
22 const debug = false
23
24 const (
25 limit14B = math.MaxUint32
26 // Use 12 bit table when no more than...
27 limit12B = 16<<10 - 1
28 // Use 10 bit table when no more than...
29 limit10B = 4<<10 - 1
30 // Use 8 bit table when no more than...
31 limit8B = 512 - 1
32 )
33
34 func main() {
35 flag.Parse()
36 Constraint(buildtags.Not("appengine").ToConstraint())
37 Constraint(buildtags.Not("noasm").ToConstraint())
38 Constraint(buildtags.Term("gc").ToConstraint())
39 Constraint(buildtags.Not("noasm").ToConstraint())
40
41 // We need a function to add comments.
42 TEXT("_dummy_", 0, "func()")
43 Comment("#ifdef GOAMD64_v4")
44 Comment("#ifndef GOAMD64_v3")
45 Comment("#define GOAMD64_v3")
46 Comment("#endif")
47 Comment("#endif")
48 RET()
49
50 o := options{
51 bmi1: false,
52 bmi2: false,
53 snappy: false,
54 avx2: false,
55 outputMargin: 9,
56 }
57 o.genEncodeBlockAsm("encodeBlockAsm", 14, 6, 6, limit14B)
58 o.genEncodeBlockAsm("encodeBlockAsm4MB", 14, 6, 6, 4<<20)
59 o.genEncodeBlockAsm("encodeBlockAsm12B", 12, 5, 5, limit12B)
60 o.genEncodeBlockAsm("encodeBlockAsm10B", 10, 5, 4, limit10B)
61 o.genEncodeBlockAsm("encodeBlockAsm8B", 8, 4, 4, limit8B)
62
63 o.outputMargin = 6
64 o.maxSkip = 100 // Blocks can be long, limit max skipping.
65 o.genEncodeBetterBlockAsm("encodeBetterBlockAsm", 17, 14, 7, 7, limit14B)
66 o.genEncodeBetterBlockAsm("encodeBetterBlockAsm4MB", 17, 14, 7, 7, 4<<20)
67 o.maxSkip = 0
68 o.genEncodeBetterBlockAsm("encodeBetterBlockAsm12B", 14, 12, 6, 6, limit12B)
69 o.genEncodeBetterBlockAsm("encodeBetterBlockAsm10B", 12, 10, 5, 6, limit10B)
70 o.genEncodeBetterBlockAsm("encodeBetterBlockAsm8B", 10, 8, 4, 6, limit8B)
71
72 // Snappy compatible
73 o.snappy = true
74 o.outputMargin = 9
75 o.genEncodeBlockAsm("encodeSnappyBlockAsm", 14, 6, 6, limit14B)
76 o.genEncodeBlockAsm("encodeSnappyBlockAsm64K", 14, 6, 6, 64<<10-1)
77 o.genEncodeBlockAsm("encodeSnappyBlockAsm12B", 12, 5, 5, limit12B)
78 o.genEncodeBlockAsm("encodeSnappyBlockAsm10B", 10, 5, 4, limit10B)
79 o.genEncodeBlockAsm("encodeSnappyBlockAsm8B", 8, 4, 4, limit8B)
80
81 o.maxSkip = 100
82 o.genEncodeBetterBlockAsm("encodeSnappyBetterBlockAsm", 17, 14, 7, 7, limit14B)
83 o.maxSkip = 0
84 o.genEncodeBetterBlockAsm("encodeSnappyBetterBlockAsm64K", 16, 13, 7, 7, 64<<10-1)
85 o.genEncodeBetterBlockAsm("encodeSnappyBetterBlockAsm12B", 14, 12, 6, 6, limit12B)
86 o.genEncodeBetterBlockAsm("encodeSnappyBetterBlockAsm10B", 12, 10, 5, 6, limit10B)
87 o.genEncodeBetterBlockAsm("encodeSnappyBetterBlockAsm8B", 10, 8, 4, 6, limit8B)
88
89 o.maxSkip = 0
90 o.skipOutput = true
91 o.snappy = true
92 o.genEncodeBlockAsm("calcBlockSize", 13, 5, 6, limit14B)
93 o.genEncodeBlockAsm("calcBlockSizeSmall", 9, 4, 4, 1024)
94 o.skipOutput = false
95 o.snappy = false
96
97 o.snappy = false
98 o.outputMargin = 0
99 o.maxLen = math.MaxUint32
100 o.maxOffset = math.MaxUint32 - 1
101 o.genEmitLiteral()
102 o.genEmitRepeat()
103 o.genEmitCopy()
104 o.snappy = true
105 o.genEmitCopyNoRepeat()
106 o.snappy = false
107 o.genMatchLen()
108 o.cvtLZ4BlockAsm(false)
109 o.cvtLZ4BlockAsm(true)
110 o.snappy = true
111 o.cvtLZ4BlockAsm(false)
112 o.cvtLZ4BlockAsm(true)
113
114 Generate()
115 }
116
117 func debugval(v Op) {
118 value := reg.R15
119 MOVQ(v, value)
120 INT(Imm(3))
121 }
122
123 func debugval32(v Op) {
124 value := reg.R15L
125 MOVL(v, value)
126 INT(Imm(3))
127 }
128
129 var assertCounter int
130
131 // assert will insert code if debug is enabled.
132 // The code should jump to 'ok' is assertion is success.
133 func assert(fn func(ok LabelRef)) {
134 if debug {
135 caller := [100]uintptr{0}
136 runtime.Callers(2, caller[:])
137 frame, _ := runtime.CallersFrames(caller[:]).Next()
138
139 ok := fmt.Sprintf("assert_check_%d_ok_srcline_%d", assertCounter, frame.Line)
140 fn(LabelRef(ok))
141 // Emit several since delve is imprecise.
142 INT(Imm(3))
143 INT(Imm(3))
144 Label(ok)
145 assertCounter++
146 }
147 }
148
149 type regTable struct {
150 r reg.Register
151 disp int
152 }
153
154 func (r regTable) Idx(idx reg.GPVirtual, scale uint8) Mem {
155 return Mem{Base: r.r, Index: idx, Scale: scale, Disp: r.disp}
156 }
157
158 type options struct {
159 snappy bool
160 bmi1 bool
161 bmi2 bool
162 skipOutput bool
163 avx2 bool
164 maxLen int
165 maxOffset int
166 outputMargin int // Should be at least 5.
167 maxSkip int
168 }
169
170 func (o options) genEncodeBlockAsm(name string, tableBits, skipLog, hashBytes, maxLen int) {
171 dstTxt := "dst, "
172 if o.skipOutput {
173 dstTxt = ""
174 }
175
176 var tableSize = 4 * (1 << tableBits)
177 // Memzero needs at least 128 bytes.
178 if tableSize < 128 {
179 panic("tableSize must be at least 128 bytes")
180 }
181
182 arrPtr := fmt.Sprintf(",tmp *[%d]byte", tableSize)
183 TEXT(name, 0, "func("+dstTxt+"src []byte"+arrPtr+") int")
184 Doc(name+" encodes a non-empty src to a guaranteed-large-enough dst.",
185 fmt.Sprintf("Maximum input %d bytes.", maxLen),
186 "It assumes that the varint-encoded length of the decompressed bytes has already been written.", "")
187 Pragma("noescape")
188
189 o.maxLen = maxLen
190 o.maxOffset = maxLen - 1
191 var literalMaxOverhead = maxLitOverheadFor(maxLen)
192
193 // Memzero needs at least 128 bytes.
194 if tableSize < 128 {
195 panic("tableSize must be at least 128 bytes")
196 }
197
198 lenSrcBasic, err := Param("src").Len().Resolve()
199 if err != nil {
200 panic(err)
201 }
202 lenSrcQ := lenSrcBasic.Addr
203
204 var lenDstQ Mem
205 if debug && !o.skipOutput {
206 lenDstBasic, err := Param("dst").Len().Resolve()
207 if err != nil {
208 panic(err)
209 }
210 lenDstQ = lenDstBasic.Addr
211 }
212
213 // Bail if we can't compress to at least this.
214 dstLimitPtrQ := AllocLocal(8)
215
216 // sLimitL is when to stop looking for offset/length copies.
217 sLimitL := AllocLocal(4)
218
219 // nextEmitL keeps track of the point we have emitted to.
220 nextEmitL := AllocLocal(4)
221
222 // Repeat stores the last match offset.
223 repeatL := AllocLocal(4)
224
225 // nextSTempL keeps nextS while other functions are being called.
226 nextSTempL := AllocLocal(4)
227
228 // Load pointer to temp table
229 table := regTable{r: Load(Param("tmp"), GP64())}
230
231 dst := GP64()
232 if !o.skipOutput {
233 dstBaseBasic, err := Param("dst").Base().Resolve()
234 if err != nil {
235 panic(err)
236 }
237 dstBaseQ := dstBaseBasic.Addr
238 MOVQ(dstBaseQ, dst)
239 } else {
240 // Zero dst address
241 XORQ(dst, dst)
242 }
243
244 srcBaseBasic, err := Param("src").Base().Resolve()
245 if err != nil {
246 panic(err)
247 }
248 srcBaseQ := srcBaseBasic.Addr
249
250 // Zero table
251 {
252 iReg := GP64()
253 MOVQ(U32(tableSize/8/16), iReg)
254 tablePtr := GP64()
255 MOVQ(table.r, tablePtr)
256 zeroXmm := XMM()
257 PXOR(zeroXmm, zeroXmm)
258
259 Label("zero_loop_" + name)
260 for i := 0; i < 8; i++ {
261 MOVOU(zeroXmm, Mem{Base: tablePtr, Disp: i * 16})
262 }
263 ADDQ(U8(16*8), tablePtr)
264 DECQ(iReg)
265 JNZ(LabelRef("zero_loop_" + name))
266 }
267
268 {
269 // nextEmit is offset n src where the next emitLiteral should start from.
270 MOVL(U32(0), nextEmitL)
271
272 const inputMargin = 8
273 tmp, tmp2, tmp3 := GP64(), GP64(), GP64()
274 MOVQ(lenSrcQ, tmp)
275 LEAQ(Mem{Base: tmp, Disp: -o.outputMargin}, tmp2)
276 // sLimitL := len(src) - inputMargin
277 LEAQ(Mem{Base: tmp, Disp: -inputMargin}, tmp3)
278
279 assert(func(ok LabelRef) {
280 CMPQ(tmp3, lenSrcQ)
281 JB(ok)
282 })
283
284 MOVL(tmp3.As32(), sLimitL)
285
286 // dstLimit := (len(src) - outputMargin ) - len(src)>>5
287 SHRQ(U8(5), tmp)
288 SUBL(tmp.As32(), tmp2.As32()) // tmp2 = tmp2 - tmp
289
290 assert(func(ok LabelRef) {
291 // if len(src) > len(src) - len(src)>>5 - outputMargin: ok
292 CMPQ(lenSrcQ, tmp2)
293 JAE(ok)
294 })
295
296 LEAQ(Mem{Base: dst, Index: tmp2, Scale: 1}, tmp2)
297 MOVQ(tmp2, dstLimitPtrQ)
298 }
299
300 // s = 1
301 s := GP32()
302 MOVL(U32(1), s)
303 // repeatL = 1
304 MOVL(s, repeatL)
305
306 src := GP64()
307 Load(Param("src").Base(), src)
308
309 // Load cv
310 Label("search_loop_" + name)
311 candidate := GP32()
312 {
313 assert(func(ok LabelRef) {
314 // Check if somebody changed src
315 tmp := GP64()
316 MOVQ(srcBaseQ, tmp)
317 CMPQ(tmp, src)
318 JEQ(ok)
319 })
320
321 cv := GP64()
322 nextS := GP32()
323 // nextS := s + (s-nextEmit)>>6 + 4
324 if o.maxSkip == 0 {
325 tmp := GP64()
326 MOVL(s, tmp.As32()) // tmp = s
327 SUBL(nextEmitL, tmp.As32()) // tmp = s - nextEmit
328 SHRL(U8(skipLog), tmp.As32()) // tmp = (s - nextEmit) >> skipLog
329 LEAL(Mem{Base: s, Disp: 4, Index: tmp, Scale: 1}, nextS)
330 }
331 // if nextS > sLimit {goto emitRemainder}
332 {
333 CMPL(nextS.As32(), sLimitL)
334 JAE(LabelRef("emit_remainder_" + name))
335 }
336 MOVQ(Mem{Base: src, Index: s, Scale: 1}, cv)
337 assert(func(ok LabelRef) {
338 // Check if s is valid (we should have jumped above if not)
339 tmp := GP64()
340 MOVQ(lenSrcQ, tmp)
341 CMPQ(tmp, s.As64())
342 JA(ok)
343 })
344 // move nextS to stack.
345 MOVL(nextS.As32(), nextSTempL)
346
347 candidate2 := GP32()
348 hasher := hashN(hashBytes, tableBits)
349 {
350 hash0, hash1 := GP64(), GP64()
351 MOVQ(cv, hash0)
352 MOVQ(cv, hash1)
353 SHRQ(U8(8), hash1)
354 hasher.hash(hash0)
355 hasher.hash(hash1)
356 MOVL(table.Idx(hash0, 4), candidate)
357 MOVL(table.Idx(hash1, 4), candidate2)
358 assert(func(ok LabelRef) {
359 CMPQ(hash0, U32(tableSize))
360 JB(ok)
361 })
362 assert(func(ok LabelRef) {
363 CMPQ(hash1, U32(tableSize))
364 JB(ok)
365 })
366
367 MOVL(s, table.Idx(hash0, 4))
368 tmp := GP32()
369 LEAL(Mem{Base: s, Disp: 1}, tmp)
370 MOVL(tmp, table.Idx(hash1, 4))
371 }
372
373 // Can be moved up if registers are available.
374 hash2 := GP64()
375 {
376 // hash2 := hash6(cv>>16, tableBits)
377 // hasher = hash6(tableBits)
378 MOVQ(cv, hash2)
379 SHRQ(U8(16), hash2)
380 hasher.hash(hash2)
381 assert(func(ok LabelRef) {
382 CMPQ(hash2, U32(tableSize))
383 JB(ok)
384 })
385 }
386
387 // En/disable repeat matching.
388 if true {
389 // Check repeat at offset checkRep
390 const checkRep = 1
391 {
392 // rep = s - repeat
393 rep := GP32()
394 MOVL(s, rep)
395 SUBL(repeatL, rep) // rep = s - repeat
396
397 // if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) {
398 left, right := GP64(), GP64()
399 MOVL(Mem{Base: src, Index: rep, Disp: checkRep, Scale: 1}, right.As32())
400 MOVQ(cv, left)
401 SHRQ(U8(checkRep*8), left)
402 CMPL(left.As32(), right.As32())
403 // BAIL, no repeat.
404 JNE(LabelRef("no_repeat_found_" + name))
405 }
406 // base = s + checkRep
407 base := GP32()
408 LEAL(Mem{Base: s, Disp: checkRep}, base)
409
410 // nextEmit before repeat.
411 nextEmit := GP32()
412 MOVL(nextEmitL, nextEmit)
413
414 // Extend back
415 if true {
416 i := GP32()
417 MOVL(base, i)
418 SUBL(repeatL, i)
419 JZ(LabelRef("repeat_extend_back_end_" + name))
420
421 Label("repeat_extend_back_loop_" + name)
422 // if base <= nextemit {exit}
423 CMPL(base.As32(), nextEmit)
424 JBE(LabelRef("repeat_extend_back_end_" + name))
425 // if src[i-1] == src[base-1]
426 tmp, tmp2 := GP64(), GP64()
427 MOVB(Mem{Base: src, Index: i, Scale: 1, Disp: -1}, tmp.As8())
428 MOVB(Mem{Base: src, Index: base, Scale: 1, Disp: -1}, tmp2.As8())
429 CMPB(tmp.As8(), tmp2.As8())
430 JNE(LabelRef("repeat_extend_back_end_" + name))
431 LEAL(Mem{Base: base, Disp: -1}, base)
432 DECL(i)
433 JNZ(LabelRef("repeat_extend_back_loop_" + name))
434 }
435 Label("repeat_extend_back_end_" + name)
436
437 {
438 // tmp = s-nextEmit
439 tmp := GP64()
440 MOVL(base.As32(), tmp.As32())
441 SUBL(nextEmitL, tmp.As32())
442 // tmp = &dst + s-nextEmit
443 LEAQ(Mem{Base: dst, Index: tmp, Scale: 1, Disp: literalMaxOverhead}, tmp)
444 CMPQ(tmp, dstLimitPtrQ)
445 JB(LabelRef("repeat_dst_size_check_" + name))
446 ri, err := ReturnIndex(0).Resolve()
447 if err != nil {
448 panic(err)
449 }
450 MOVQ(U32(0), ri.Addr)
451 if o.avx2 {
452 VZEROUPPER()
453 }
454 RET()
455 }
456 Label("repeat_dst_size_check_" + name)
457
458 // Base is now at start. Emit until base.
459 // d += emitLiteral(dst[d:], src[nextEmit:base])
460 o.emitLiteralsDstP(nextEmitL, base, src, dst, "repeat_emit_"+name)
461
462 // Extend forward
463 {
464 // s += 4 + checkRep
465 ADDL(U8(4+checkRep), s)
466
467 {
468 // candidate := s - repeat + 4 + checkRep
469 MOVL(s, candidate)
470 SUBL(repeatL, candidate) // candidate = s - repeat
471
472 // srcLeft = len(src) - s
473 srcLeft := GP64()
474 MOVQ(lenSrcQ, srcLeft)
475 SUBL(s, srcLeft.As32())
476 assert(func(ok LabelRef) {
477 // if srcleft < maxint32: ok
478 CMPQ(srcLeft, U32(0x7fffffff))
479 JB(ok)
480 })
481 // Forward address
482 forwardStart := GP64()
483 LEAQ(Mem{Base: src, Index: s, Scale: 1}, forwardStart)
484 // End address
485 backStart := GP64()
486 LEAQ(Mem{Base: src, Index: candidate, Scale: 1}, backStart)
487
488 length := o.matchLen("repeat_extend_"+name, forwardStart, backStart, srcLeft, LabelRef("repeat_extend_forward_end_"+name))
489 forwardStart, backStart, srcLeft = nil, nil, nil
490 Label("repeat_extend_forward_end_" + name)
491 // s+= length
492 ADDL(length.As32(), s)
493 }
494 }
495 // Emit
496 {
497 // length = s-base
498 length := GP32()
499 MOVL(s, length)
500 SUBL(base.As32(), length) // length = s - base
501
502 offsetVal := GP32()
503 MOVL(repeatL, offsetVal)
504
505 if !o.snappy {
506 // if nextEmit == 0 {do copy instead...}
507 TESTL(nextEmit, nextEmit)
508 JZ(LabelRef("repeat_as_copy_" + name))
509
510 // Emit as repeat...
511 o.emitRepeat("match_repeat_"+name, length, offsetVal, nil, dst, LabelRef("repeat_end_emit_"+name), false)
512
513 // Emit as copy instead...
514 Label("repeat_as_copy_" + name)
515 }
516 o.emitCopy("repeat_as_copy_"+name, length, offsetVal, nil, dst, nil, LabelRef("repeat_end_emit_"+name))
517
518 Label("repeat_end_emit_" + name)
519 // Store new dst and nextEmit
520 MOVL(s, nextEmitL)
521 }
522 // if s >= sLimit is picked up on next loop.
523 if false {
524 CMPL(s.As32(), sLimitL)
525 JAE(LabelRef("emit_remainder_" + name))
526 }
527 JMP(LabelRef("search_loop_" + name))
528 }
529 Label("no_repeat_found_" + name)
530 {
531 // Check candidates are ok. All must be < s and < len(src)
532 assert(func(ok LabelRef) {
533 tmp := GP64()
534 MOVQ(lenSrcQ, tmp)
535 CMPL(tmp.As32(), candidate)
536 JA(ok)
537 })
538 assert(func(ok LabelRef) {
539 CMPL(s, candidate)
540 JA(ok)
541 })
542 assert(func(ok LabelRef) {
543 tmp := GP64()
544 MOVQ(lenSrcQ, tmp)
545 CMPL(tmp.As32(), candidate2)
546 JA(ok)
547 })
548 assert(func(ok LabelRef) {
549 CMPL(s, candidate2)
550 JA(ok)
551 })
552
553 CMPL(Mem{Base: src, Index: candidate, Scale: 1}, cv.As32())
554 JEQ(LabelRef("candidate_match_" + name))
555
556 tmp := GP32()
557 // cv >>= 8
558 SHRQ(U8(8), cv)
559
560 // candidate = int(table[hash2]) - load early.
561 MOVL(table.Idx(hash2, 4), candidate)
562 assert(func(ok LabelRef) {
563 tmp := GP64()
564 MOVQ(lenSrcQ, tmp)
565 CMPL(tmp.As32(), candidate)
566 JA(ok)
567 })
568 assert(func(ok LabelRef) {
569 // We may get s and s+1
570 tmp := GP32()
571 LEAL(Mem{Base: s, Disp: 2}, tmp)
572 CMPL(tmp, candidate)
573 JA(ok)
574 })
575
576 LEAL(Mem{Base: s, Disp: 2}, tmp)
577
578 //if uint32(cv>>8) == load32(src, candidate2)
579 CMPL(Mem{Base: src, Index: candidate2, Scale: 1}, cv.As32())
580 JEQ(LabelRef("candidate2_match_" + name))
581
582 // table[hash2] = uint32(s + 2)
583 MOVL(tmp, table.Idx(hash2, 4))
584
585 // cv >>= 8 (>> 16 total)
586 SHRQ(U8(8), cv)
587
588 // if uint32(cv>>16) == load32(src, candidate)
589 CMPL(Mem{Base: src, Index: candidate, Scale: 1}, cv.As32())
590 JEQ(LabelRef("candidate3_match_" + name))
591
592 // No match found, next loop
593 // s = nextS
594 MOVL(nextSTempL, s)
595 JMP(LabelRef("search_loop_" + name))
596
597 // Matches candidate at s + 2 (3rd check)
598 Label("candidate3_match_" + name)
599 ADDL(U8(2), s)
600 JMP(LabelRef("candidate_match_" + name))
601
602 // Match at s + 1 (we calculated the hash, lets store it)
603 Label("candidate2_match_" + name)
604 // table[hash2] = uint32(s + 2)
605 MOVL(tmp, table.Idx(hash2, 4))
606 // s++
607 INCL(s)
608 MOVL(candidate2, candidate)
609 }
610 }
611
612 Label("candidate_match_" + name)
613 // We have a match at 's' with src offset in "candidate" that matches at least 4 bytes.
614 // Extend backwards
615 if true {
616 ne := GP32()
617 MOVL(nextEmitL, ne)
618 TESTL(candidate, candidate)
619 JZ(LabelRef("match_extend_back_end_" + name))
620
621 // candidate is tested when decremented, so we loop back here.
622 Label("match_extend_back_loop_" + name)
623 // if s <= nextEmit {exit}
624 CMPL(s, ne)
625 JBE(LabelRef("match_extend_back_end_" + name))
626 // if src[candidate-1] == src[s-1]
627 tmp, tmp2 := GP64(), GP64()
628 MOVB(Mem{Base: src, Index: candidate, Scale: 1, Disp: -1}, tmp.As8())
629 MOVB(Mem{Base: src, Index: s, Scale: 1, Disp: -1}, tmp2.As8())
630 CMPB(tmp.As8(), tmp2.As8())
631 JNE(LabelRef("match_extend_back_end_" + name))
632 LEAL(Mem{Base: s, Disp: -1}, s)
633 DECL(candidate)
634 JZ(LabelRef("match_extend_back_end_" + name))
635 JMP(LabelRef("match_extend_back_loop_" + name))
636 }
637 Label("match_extend_back_end_" + name)
638
639 // Bail if we exceed the maximum size.
640 {
641 // tmp = s-nextEmit
642 tmp := GP64()
643 MOVL(s, tmp.As32())
644 SUBL(nextEmitL, tmp.As32())
645 // tmp = &dst + s-nextEmit
646 LEAQ(Mem{Base: dst, Index: tmp, Scale: 1, Disp: literalMaxOverhead}, tmp)
647 CMPQ(tmp, dstLimitPtrQ)
648 JB(LabelRef("match_dst_size_check_" + name))
649 ri, err := ReturnIndex(0).Resolve()
650 if err != nil {
651 panic(err)
652 }
653 MOVQ(U32(0), ri.Addr)
654 if o.avx2 {
655 VZEROUPPER()
656 }
657 RET()
658 }
659 Label("match_dst_size_check_" + name)
660 {
661 base := GP32()
662 MOVL(s, base.As32())
663 o.emitLiteralsDstP(nextEmitL, base, src, dst, "match_emit_"+name)
664 }
665 cv := GP64()
666 Label("match_nolit_loop_" + name)
667 {
668 // Update repeat
669 {
670 // repeat = base - candidate
671 repeatVal := GP64().As32()
672 MOVL(s, repeatVal)
673 SUBL(candidate, repeatVal)
674 MOVL(repeatVal, repeatL)
675 }
676 // s+=4, candidate+=4
677 ADDL(U8(4), s)
678 ADDL(U8(4), candidate)
679 // Extend the 4-byte match as long as possible and emit copy.
680 {
681 assert(func(ok LabelRef) {
682 // s must be > candidate cannot be equal.
683 CMPL(s, candidate)
684 JA(ok)
685 })
686 // srcLeft = len(src) - s
687 srcLeft := GP64()
688 MOVQ(lenSrcQ, srcLeft)
689 SUBL(s, srcLeft.As32())
690 assert(func(ok LabelRef) {
691 // if srcleft < maxint32: ok
692 CMPQ(srcLeft, U32(0x7fffffff))
693 JB(ok)
694 })
695
696 a, b := GP64(), GP64()
697 LEAQ(Mem{Base: src, Index: s, Scale: 1}, a)
698 LEAQ(Mem{Base: src, Index: candidate, Scale: 1}, b)
699 length := o.matchLen("match_nolit_"+name,
700 a, b,
701 srcLeft,
702 LabelRef("match_nolit_end_"+name),
703 )
704 Label("match_nolit_end_" + name)
705 assert(func(ok LabelRef) {
706 CMPL(length.As32(), U32(math.MaxInt32))
707 JB(ok)
708 })
709 a, b, srcLeft = nil, nil, nil
710
711 // s += length (length is destroyed, use it now)
712 ADDL(length.As32(), s)
713
714 // Load offset from repeat value.
715 offset := GP64()
716 MOVL(repeatL, offset.As32())
717
718 // length += 4
719 ADDL(U8(4), length.As32())
720 MOVL(s, nextEmitL) // nextEmit = s
721 o.emitCopy("match_nolit_"+name, length, offset, nil, dst, nil, LabelRef("match_nolit_emitcopy_end_"+name))
722 Label("match_nolit_emitcopy_end_" + name)
723
724 // if s >= sLimit { end }
725 {
726 CMPL(s.As32(), sLimitL)
727 JAE(LabelRef("emit_remainder_" + name))
728 }
729 // Start load s-2 as early as possible...
730 MOVQ(Mem{Base: src, Index: s, Scale: 1, Disp: -2}, cv)
731 // Bail if we exceed the maximum size.
732 {
733 CMPQ(dst, dstLimitPtrQ)
734 JB(LabelRef("match_nolit_dst_ok_" + name))
735 ri, err := ReturnIndex(0).Resolve()
736 if err != nil {
737 panic(err)
738 }
739 MOVQ(U32(0), ri.Addr)
740 if o.avx2 {
741 VZEROUPPER()
742 }
743 RET()
744 Label("match_nolit_dst_ok_" + name)
745 }
746 }
747 // cv must be set to value at s-2 before arriving here
748 {
749 // Check for an immediate match, otherwise start search at s+1
750 // Index s-2
751 hasher := hashN(hashBytes, tableBits)
752 hash0, hash1 := GP64(), GP64()
753 MOVQ(cv, hash0) // src[s-2]
754 SHRQ(U8(16), cv)
755 MOVQ(cv, hash1) // src[s]
756 hasher.hash(hash0)
757 hasher.hash(hash1)
758 sm2 := GP32() // s - 2
759 LEAL(Mem{Base: s, Disp: -2}, sm2)
760 assert(func(ok LabelRef) {
761 CMPQ(hash0, U32(tableSize))
762 JB(ok)
763 })
764 assert(func(ok LabelRef) {
765 CMPQ(hash1, U32(tableSize))
766 JB(ok)
767 })
768 addr := GP64()
769 LEAQ(table.Idx(hash1, 4), addr)
770 MOVL(Mem{Base: addr}, candidate)
771 MOVL(sm2, table.Idx(hash0, 4))
772 MOVL(s, Mem{Base: addr})
773 CMPL(Mem{Base: src, Index: candidate, Scale: 1}, cv.As32())
774 JEQ(LabelRef("match_nolit_loop_" + name))
775 INCL(s)
776 }
777 JMP(LabelRef("search_loop_" + name))
778 }
779
780 Label("emit_remainder_" + name)
781 // Bail if we exceed the maximum size.
782 // if d+len(src)-nextEmitL > dstLimitPtrQ { return 0
783 {
784 // remain = len(src) - nextEmit
785 remain := GP64()
786 MOVQ(lenSrcQ, remain)
787 SUBL(nextEmitL, remain.As32())
788
789 dstExpect := GP64()
790 // dst := dst + (len(src)-nextEmitL)
791
792 LEAQ(Mem{Base: dst, Index: remain, Scale: 1, Disp: literalMaxOverhead}, dstExpect)
793 CMPQ(dstExpect, dstLimitPtrQ)
794 JB(LabelRef("emit_remainder_ok_" + name))
795 ri, err := ReturnIndex(0).Resolve()
796 if err != nil {
797 panic(err)
798 }
799 if o.avx2 {
800 VZEROUPPER()
801 }
802 MOVQ(U32(0), ri.Addr)
803 RET()
804 Label("emit_remainder_ok_" + name)
805 }
806 {
807 // emitLiteral(dst[d:], src[nextEmitL:])
808 emitEnd := GP64()
809 MOVQ(lenSrcQ, emitEnd)
810
811 // Emit final literals.
812 // Since we may be at the end of source,
813 // we cannot have output margin.
814 x := o.outputMargin
815 o.outputMargin = 0
816 o.emitLiteralsDstP(nextEmitL, emitEnd, src, dst, "emit_remainder_"+name)
817 o.outputMargin = x
818 // Assert size is < limit
819 assert(func(ok LabelRef) {
820 // if dstBaseQ < dstLimitPtrQ: ok
821 CMPQ(dst, dstLimitPtrQ)
822 JB(ok)
823 })
824 }
825
826 // length := start - base (ptr arithmetic)
827 length := GP64()
828 if !o.skipOutput {
829 base := Load(Param("dst").Base(), GP64())
830 MOVQ(dst, length)
831 SUBQ(base, length)
832 } else {
833 length = dst
834 }
835
836 // Assert size is < len(src)
837 assert(func(ok LabelRef) {
838 // if len(src) >= length: ok
839 CMPQ(lenSrcQ, length)
840 JAE(ok)
841 })
842 // Assert size is < len(dst)
843 if !o.skipOutput {
844 assert(func(ok LabelRef) {
845 // if len(dst) >= length: ok
846 CMPQ(lenDstQ, length)
847 JAE(ok)
848 })
849 }
850 if o.avx2 {
851 VZEROUPPER()
852 }
853 Store(length, ReturnIndex(0))
854 RET()
855 }
856
857 func maxLitOverheadFor(n int) int {
858 switch {
859 case n == 0:
860 return 0
861 case n < 60:
862 return 1
863 case n < 1<<8:
864 return 2
865 case n < 1<<16:
866 return 3
867 case n < 1<<24:
868 return 4
869 }
870 return 5
871 }
872
873 func (o options) genEncodeBetterBlockAsm(name string, lTableBits, sTableBits, skipLog, lHashBytes, maxLen int) {
874 var lTableSize = 4 * (1 << lTableBits)
875 var sTableSize = 4 * (1 << sTableBits)
876 tableSize := lTableSize + sTableSize
877
878 // Memzero needs at least 128 bytes.
879 if tableSize < 128 {
880 panic("tableSize must be at least 128 bytes")
881 }
882 arrPtr := fmt.Sprintf(", tmp *[%d]byte", tableSize)
883
884 TEXT(name, 0, "func(dst, src []byte"+arrPtr+") int")
885 Doc(name+" encodes a non-empty src to a guaranteed-large-enough dst.",
886 fmt.Sprintf("Maximum input %d bytes.", maxLen),
887 "It assumes that the varint-encoded length of the decompressed bytes has already been written.", "")
888 Pragma("noescape")
889
890 if lHashBytes > 7 || lHashBytes <= 4 {
891 panic("lHashBytes must be <= 7 and >4")
892 }
893 var literalMaxOverhead = maxLitOverheadFor(maxLen)
894
895 const sHashBytes = 4
896 o.maxLen = maxLen
897 o.maxOffset = maxLen - 1
898
899 // Memzero needs at least 128 bytes.
900 if (lTableSize + sTableSize) < 128 {
901 panic("tableSize must be at least 128 bytes")
902 }
903
904 lenSrcBasic, err := Param("src").Len().Resolve()
905 if err != nil {
906 panic(err)
907 }
908 lenSrcQ := lenSrcBasic.Addr
909
910 lenDstBasic, err := Param("dst").Len().Resolve()
911 if err != nil {
912 panic(err)
913 }
914 lenDstQ := lenDstBasic.Addr
915
916 // Bail if we can't compress to at least this.
917 dstLimitPtrQ := AllocLocal(8)
918
919 // sLimitL is when to stop looking for offset/length copies.
920 sLimitL := AllocLocal(4)
921
922 // nextEmitL keeps track of the point we have emitted to.
923 nextEmitL := AllocLocal(4)
924
925 // Repeat stores the last match offset.
926 repeatL := AllocLocal(4)
927
928 // nextSTempL keeps nextS while other functions are being called.
929 nextSTempL := AllocLocal(4)
930
931 table := Load(Param("tmp"), GP64())
932 lTab := regTable{r: table}
933 sTab := regTable{r: table, disp: lTableSize}
934
935 dst := GP64()
936 {
937 dstBaseBasic, err := Param("dst").Base().Resolve()
938 if err != nil {
939 panic(err)
940 }
941 dstBaseQ := dstBaseBasic.Addr
942 MOVQ(dstBaseQ, dst)
943 }
944
945 srcBaseBasic, err := Param("src").Base().Resolve()
946 if err != nil {
947 panic(err)
948 }
949 srcBaseQ := srcBaseBasic.Addr
950
951 // Zero table
952 {
953 iReg := GP64()
954 MOVQ(U32((sTableSize+lTableSize)/8/16), iReg)
955 tablePtr := GP64()
956 MOVQ(table, tablePtr)
957 zeroXmm := XMM()
958 PXOR(zeroXmm, zeroXmm)
959
960 Label("zero_loop_" + name)
961 for i := 0; i < 8; i++ {
962 MOVOU(zeroXmm, Mem{Base: tablePtr, Disp: i * 16})
963 }
964 ADDQ(U8(16*8), tablePtr)
965 DECQ(iReg)
966 JNZ(LabelRef("zero_loop_" + name))
967 }
968
969 {
970 // nextEmit is offset n src where the next emitLiteral should start from.
971 MOVL(U32(0), nextEmitL)
972
973 const inputMargin = 8
974 tmp, tmp2, tmp3 := GP64(), GP64(), GP64()
975 MOVQ(lenSrcQ, tmp)
976 LEAQ(Mem{Base: tmp, Disp: -o.outputMargin}, tmp2)
977 // sLimitL := len(src) - inputMargin
978 LEAQ(Mem{Base: tmp, Disp: -inputMargin}, tmp3)
979
980 assert(func(ok LabelRef) {
981 CMPQ(tmp3, lenSrcQ)
982 JB(ok)
983 })
984
985 MOVL(tmp3.As32(), sLimitL)
986
987 // dstLimit := (len(src) - 5 ) - len(src)>>5
988 SHRQ(U8(5), tmp)
989 SUBL(tmp.As32(), tmp2.As32()) // tmp2 = tmp2 - tmp
990
991 assert(func(ok LabelRef) {
992 // if len(src) > len(src) - len(src)>>5 - 5: ok
993 CMPQ(lenSrcQ, tmp2)
994 JAE(ok)
995 })
996
997 LEAQ(Mem{Base: dst, Index: tmp2, Scale: 1}, tmp2)
998 MOVQ(tmp2, dstLimitPtrQ)
999 }
1000
1001 // s = 1
1002 s := GP32()
1003 MOVL(U32(1), s)
1004 // repeatL = 0
1005 MOVL(U32(0), repeatL)
1006
1007 src := GP64()
1008 Load(Param("src").Base(), src)
1009
1010 // Load cv
1011 Label("search_loop_" + name)
1012 candidate := GP32()
1013 {
1014 assert(func(ok LabelRef) {
1015 // Check if somebody changed src
1016 tmp := GP64()
1017 MOVQ(srcBaseQ, tmp)
1018 CMPQ(tmp, src)
1019 JEQ(ok)
1020 })
1021
1022 cv := GP64()
1023 nextS := GP32()
1024 // nextS := s + (s-nextEmit)>>skipLog + 1
1025 if o.maxSkip == 0 {
1026 tmp := GP64()
1027 MOVL(s, tmp.As32()) // tmp = s
1028 SUBL(nextEmitL, tmp.As32()) // tmp = s - nextEmit
1029 SHRL(U8(skipLog), tmp.As32()) // tmp = (s - nextEmit) >> skipLog
1030 LEAL(Mem{Base: s, Disp: 1, Index: tmp, Scale: 1}, nextS)
1031 } else {
1032 /*
1033 nextS = (s-nextEmit)>>7 + 1
1034 if nextS > maxSkip {
1035 nextS = s + maxSkip
1036 } else {
1037 nextS += s
1038 }
1039 */
1040 tmp := GP64()
1041 MOVL(s, tmp.As32()) // tmp = s
1042 SUBL(nextEmitL, tmp.As32()) // tmp = s - nextEmit
1043 SHRL(U8(skipLog), tmp.As32()) // tmp = (s - nextEmit) >> skipLog
1044 CMPL(tmp.As32(), U8(o.maxSkip-1))
1045 JBE(LabelRef("check_maxskip_ok_" + name))
1046 LEAL(Mem{Base: s, Disp: o.maxSkip, Scale: 1}, nextS)
1047 JMP(LabelRef("check_maxskip_cont_" + name))
1048
1049 Label("check_maxskip_ok_" + name)
1050 LEAL(Mem{Base: s, Disp: 1, Index: tmp, Scale: 1}, nextS)
1051 Label("check_maxskip_cont_" + name)
1052 }
1053 // if nextS > sLimit {goto emitRemainder}
1054 {
1055 CMPL(nextS.As32(), sLimitL)
1056 JAE(LabelRef("emit_remainder_" + name))
1057 }
1058 MOVQ(Mem{Base: src, Index: s, Scale: 1}, cv)
1059 assert(func(ok LabelRef) {
1060 // Check if s is valid (we should have jumped above if not)
1061 tmp := GP64()
1062 MOVQ(lenSrcQ, tmp)
1063 CMPQ(tmp, s.As64())
1064 JA(ok)
1065 })
1066 // move nextS to stack.
1067 MOVL(nextS.As32(), nextSTempL)
1068
1069 candidateS := GP32()
1070 lHasher := hashN(lHashBytes, lTableBits)
1071 {
1072 sHasher := hashN(sHashBytes, sTableBits)
1073 hash0, hash1 := GP64(), GP64()
1074 MOVQ(cv, hash0)
1075 MOVQ(cv, hash1)
1076 lHasher.hash(hash0)
1077 sHasher.hash(hash1)
1078 MOVL(lTab.Idx(hash0, 4), candidate)
1079 MOVL(sTab.Idx(hash1, 4), candidateS)
1080 assert(func(ok LabelRef) {
1081 CMPQ(hash0, U32(lTableSize))
1082 JB(ok)
1083 })
1084 assert(func(ok LabelRef) {
1085 CMPQ(hash1, U32(sTableSize))
1086 JB(ok)
1087 })
1088
1089 MOVL(s, lTab.Idx(hash0, 4))
1090 MOVL(s, sTab.Idx(hash1, 4))
1091 }
1092
1093 longVal := GP64()
1094 shortVal := GP64()
1095 MOVQ(Mem{Base: src, Index: candidate, Scale: 1}, longVal)
1096 MOVQ(Mem{Base: src, Index: candidateS, Scale: 1}, shortVal)
1097
1098 // If we have at least 8 bytes match, choose that first.
1099 CMPQ(longVal, cv.As64())
1100 JEQ(LabelRef("candidate_match_" + name))
1101
1102 CMPQ(shortVal, cv.As64())
1103 JNE(LabelRef("no_short_found_" + name))
1104 MOVL(candidateS.As32(), candidate.As32())
1105 JMP(LabelRef("candidate_match_" + name))
1106
1107 Label("no_short_found_" + name)
1108 MOVL(longVal.As32(), longVal.As32())
1109
1110 // En/disable repeat matching.
1111 // Too small improvement
1112 if false {
1113 {
1114 CMPL(repeatL, U8(0))
1115 JEQ(LabelRef("no_repeat_found_" + name))
1116 }
1117 // Check repeat at offset checkRep
1118 const checkRep = 1
1119 const wantRepeatBytes = 6
1120 const repeatMask = ((1 << (wantRepeatBytes * 8)) - 1) << (8 * checkRep)
1121 {
1122 // rep = s - repeat
1123 rep := GP32()
1124 MOVL(s, rep)
1125 SUBL(repeatL, rep) // rep = s - repeat
1126
1127 // if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) {
1128 tmp := GP64()
1129 mask := GP64()
1130 MOVQ(Mem{Base: src, Index: rep, Disp: 0, Scale: 1}, tmp.As64())
1131 MOVQ(U64(repeatMask), mask)
1132 XORQ(cv.As64(), tmp.As64())
1133 TESTQ(mask.As64(), tmp.As64())
1134 // BAIL, no repeat.
1135 JNE(LabelRef("no_repeat_found_" + name))
1136 }
1137 // base = s + checkRep
1138 base := GP32()
1139 LEAL(Mem{Base: s, Disp: checkRep}, base)
1140
1141 // nextEmit before repeat.
1142 nextEmit := GP32()
1143 MOVL(nextEmitL, nextEmit)
1144
1145 // Extend back
1146 if true {
1147 i := GP32()
1148 MOVL(base, i)
1149 SUBL(repeatL, i)
1150 JZ(LabelRef("repeat_extend_back_end_" + name))
1151
1152 Label("repeat_extend_back_loop_" + name)
1153 // if base <= nextemit {exit}
1154 CMPL(base.As32(), nextEmit)
1155 JBE(LabelRef("repeat_extend_back_end_" + name))
1156 // if src[i-1] == src[base-1]
1157 tmp, tmp2 := GP64(), GP64()
1158 MOVB(Mem{Base: src, Index: i, Scale: 1, Disp: -1}, tmp.As8())
1159 MOVB(Mem{Base: src, Index: base, Scale: 1, Disp: -1}, tmp2.As8())
1160 CMPB(tmp.As8(), tmp2.As8())
1161 JNE(LabelRef("repeat_extend_back_end_" + name))
1162 LEAL(Mem{Base: base, Disp: -1}, base)
1163 DECL(i)
1164 JNZ(LabelRef("repeat_extend_back_loop_" + name))
1165 }
1166 Label("repeat_extend_back_end_" + name)
1167
1168 // Base is now at start. Emit until base.
1169 // d += emitLiteral(dst[d:], src[nextEmit:base])
1170 if true {
1171 o.emitLiteralsDstP(nextEmitL, base, src, dst, "repeat_emit_"+name)
1172 }
1173
1174 // Extend forward
1175 {
1176 // s += 4 + checkRep
1177 ADDL(U8(wantRepeatBytes+checkRep), s)
1178
1179 if true {
1180 // candidate := s - repeat + 4 + checkRep
1181 MOVL(s, candidate)
1182 SUBL(repeatL, candidate) // candidate = s - repeat
1183
1184 // srcLeft = len(src) - s
1185 srcLeft := GP64()
1186 MOVQ(lenSrcQ, srcLeft)
1187 SUBL(s, srcLeft.As32())
1188 assert(func(ok LabelRef) {
1189 // if srcleft < maxint32: ok
1190 CMPQ(srcLeft, U32(0x7fffffff))
1191 JB(ok)
1192 })
1193 // Forward address
1194 forwardStart := GP64()
1195 LEAQ(Mem{Base: src, Index: s, Scale: 1}, forwardStart)
1196 // End address
1197 backStart := GP64()
1198 LEAQ(Mem{Base: src, Index: candidate, Scale: 1}, backStart)
1199
1200 length := o.matchLen("repeat_extend_"+name, forwardStart, backStart, srcLeft, LabelRef("repeat_extend_forward_end_"+name))
1201 forwardStart, backStart, srcLeft = nil, nil, nil
1202 Label("repeat_extend_forward_end_" + name)
1203 // s+= length
1204 ADDL(length.As32(), s)
1205 }
1206 }
1207 // Emit
1208 if true {
1209 // length = s-base
1210 length := GP32()
1211 MOVL(s, length)
1212 SUBL(base.As32(), length) // length = s - base
1213
1214 offsetVal := GP32()
1215 MOVL(repeatL, offsetVal)
1216
1217 // Emit as repeat...
1218 o.emitRepeat("match_repeat_"+name, length, offsetVal, nil, dst, LabelRef("repeat_end_emit_"+name), false)
1219
1220 Label("repeat_end_emit_" + name)
1221 // Store new dst and nextEmit
1222 MOVL(s, nextEmitL)
1223 }
1224 // if s >= sLimit is picked up on next loop.
1225 if false {
1226 CMPL(s.As32(), sLimitL)
1227 JAE(LabelRef("emit_remainder_" + name))
1228 }
1229 JMP(LabelRef("search_loop_" + name))
1230 }
1231 Label("no_repeat_found_" + name)
1232 {
1233 // Check candidates are ok. All must be < s and < len(src)
1234 assert(func(ok LabelRef) {
1235 tmp := GP64()
1236 MOVQ(lenSrcQ, tmp)
1237 CMPL(tmp.As32(), candidate)
1238 JA(ok)
1239 })
1240 assert(func(ok LabelRef) {
1241 CMPL(s, candidate)
1242 JA(ok)
1243 })
1244 assert(func(ok LabelRef) {
1245 tmp := GP64()
1246 MOVQ(lenSrcQ, tmp)
1247 CMPL(tmp.As32(), candidateS)
1248 JA(ok)
1249 })
1250 assert(func(ok LabelRef) {
1251 CMPL(s, candidateS)
1252 JA(ok)
1253 })
1254
1255 CMPL(longVal.As32(), cv.As32())
1256 JEQ(LabelRef("candidate_match_" + name))
1257
1258 //if uint32(cv) == load32(src, candidateS)
1259 CMPL(shortVal.As32(), cv.As32())
1260 JEQ(LabelRef("candidateS_match_" + name))
1261
1262 // No match found, next loop
1263 // s = nextS
1264 MOVL(nextSTempL, s)
1265 JMP(LabelRef("search_loop_" + name))
1266
1267 // Short match at s, try a long candidate at s+1
1268 Label("candidateS_match_" + name)
1269 if true {
1270 hash0 := GP64()
1271 SHRQ(U8(8), cv)
1272 MOVQ(cv, hash0)
1273 lHasher.hash(hash0)
1274 MOVL(lTab.Idx(hash0, 4), candidate)
1275 INCL(s)
1276 assert(func(ok LabelRef) {
1277 CMPQ(hash0, U32(lTableSize))
1278 JB(ok)
1279 })
1280 MOVL(s, lTab.Idx(hash0, 4))
1281 CMPL(Mem{Base: src, Index: candidate, Scale: 1}, cv.As32())
1282 JEQ(LabelRef("candidate_match_" + name))
1283 // No match, decrement s again and use short match at s...
1284 DECL(s)
1285 }
1286 MOVL(candidateS, candidate)
1287 }
1288 }
1289
1290 Label("candidate_match_" + name)
1291 // We have a match at 's' with src offset in "candidate" that matches at least 4 bytes.
1292 // Extend backwards
1293 if true {
1294 ne := GP32()
1295 MOVL(nextEmitL, ne)
1296 TESTL(candidate, candidate)
1297 JZ(LabelRef("match_extend_back_end_" + name))
1298
1299 // candidate is tested when decremented, so we loop back here.
1300 Label("match_extend_back_loop_" + name)
1301 // if s <= nextEmit {exit}
1302 CMPL(s, ne)
1303 JBE(LabelRef("match_extend_back_end_" + name))
1304 // if src[candidate-1] == src[s-1]
1305 tmp, tmp2 := GP64(), GP64()
1306 MOVB(Mem{Base: src, Index: candidate, Scale: 1, Disp: -1}, tmp.As8())
1307 MOVB(Mem{Base: src, Index: s, Scale: 1, Disp: -1}, tmp2.As8())
1308 CMPB(tmp.As8(), tmp2.As8())
1309 JNE(LabelRef("match_extend_back_end_" + name))
1310 LEAL(Mem{Base: s, Disp: -1}, s)
1311 DECL(candidate)
1312 JZ(LabelRef("match_extend_back_end_" + name))
1313 JMP(LabelRef("match_extend_back_loop_" + name))
1314 }
1315 Label("match_extend_back_end_" + name)
1316
1317 // Bail if we exceed the maximum size.
1318 if true {
1319 // tmp = s-nextEmit
1320 tmp := GP64()
1321 MOVL(s, tmp.As32())
1322 SUBL(nextEmitL, tmp.As32())
1323 // tmp = &dst + s-nextEmit
1324 LEAQ(Mem{Base: dst, Index: tmp, Scale: 1, Disp: literalMaxOverhead}, tmp)
1325 CMPQ(tmp, dstLimitPtrQ)
1326 JB(LabelRef("match_dst_size_check_" + name))
1327 ri, err := ReturnIndex(0).Resolve()
1328 if err != nil {
1329 panic(err)
1330 }
1331 MOVQ(U32(0), ri.Addr)
1332 if o.avx2 {
1333 VZEROUPPER()
1334 }
1335 RET()
1336 }
1337 Label("match_dst_size_check_" + name)
1338
1339 base := GP32()
1340 MOVL(s, base.As32())
1341
1342 // s+=4, candidate+=4
1343 ADDL(U8(4), s)
1344 ADDL(U8(4), candidate)
1345 // Extend the 4-byte match as long as possible and emit copy.
1346 {
1347 assert(func(ok LabelRef) {
1348 // s must be > candidate cannot be equal.
1349 CMPL(s, candidate)
1350 JA(ok)
1351 })
1352 // srcLeft = len(src) - s
1353 srcLeft := GP64()
1354 MOVQ(lenSrcQ, srcLeft)
1355 SUBL(s, srcLeft.As32())
1356 assert(func(ok LabelRef) {
1357 // if srcleft < maxint32: ok
1358 CMPQ(srcLeft, U32(0x7fffffff))
1359 JB(ok)
1360 })
1361
1362 a, b := GP64(), GP64()
1363 LEAQ(Mem{Base: src, Index: s, Scale: 1}, a)
1364 LEAQ(Mem{Base: src, Index: candidate, Scale: 1}, b)
1365 length := o.matchLen("match_nolit_"+name,
1366 a, b,
1367 srcLeft,
1368 LabelRef("match_nolit_end_"+name),
1369 )
1370 Label("match_nolit_end_" + name)
1371 assert(func(ok LabelRef) {
1372 CMPL(length.As32(), U32(math.MaxInt32))
1373 JB(ok)
1374 })
1375 a, b, srcLeft = nil, nil, nil
1376
1377 offset := GP64()
1378 offset32 := offset.As32()
1379 {
1380 // offset = base - candidate
1381 MOVL(s, offset32)
1382 SUBL(candidate, offset32)
1383 Comment("Check if repeat")
1384 if !o.snappy {
1385 CMPL(repeatL, offset32)
1386 JEQ(LabelRef("match_is_repeat_" + name))
1387 }
1388
1389 // NOT REPEAT
1390 {
1391 // Check if match is better..
1392 if o.maxOffset > 65535 {
1393 CMPL(length.As32(), U8(1))
1394 JA(LabelRef("match_length_ok_" + name))
1395 CMPL(offset32, U32(65535))
1396 JBE(LabelRef("match_length_ok_" + name))
1397 // Match is equal or worse to the encoding.
1398 MOVL(nextSTempL, s)
1399 INCL(s)
1400 JMP(LabelRef("search_loop_" + name))
1401 Label("match_length_ok_" + name)
1402 }
1403 // Store updated repeat
1404 MOVL(offset32, repeatL)
1405 // Emit....
1406 o.emitLiteralsDstP(nextEmitL, base, src, dst, "match_emit_"+name)
1407 // s += length (length is destroyed, use it now)
1408 ADDL(length.As32(), s)
1409
1410 // length += 4
1411 ADDL(U8(4), length.As32())
1412 MOVL(s, nextEmitL) // nextEmit = s
1413 o.emitCopy("match_nolit_"+name, length, offset, nil, dst, nil, LabelRef("match_nolit_emitcopy_end_"+name))
1414 // Jumps at end
1415 }
1416 // REPEAT
1417 if !o.snappy {
1418 Label("match_is_repeat_" + name)
1419 // Emit....
1420 o.emitLiteralsDstP(nextEmitL, base, src, dst, "match_emit_repeat_"+name)
1421 // s += length (length is destroyed, use it now)
1422 ADDL(length.As32(), s)
1423
1424 // length += 4
1425 ADDL(U8(4), length.As32())
1426 MOVL(s, nextEmitL) // nextEmit = s
1427 o.emitRepeat("match_nolit_repeat_"+name, length, offset, nil, dst, LabelRef("match_nolit_emitcopy_end_"+name), false)
1428 }
1429 }
1430 Label("match_nolit_emitcopy_end_" + name)
1431
1432 // if s >= sLimit { end }
1433 {
1434 CMPL(s.As32(), sLimitL)
1435 JAE(LabelRef("emit_remainder_" + name))
1436 }
1437
1438 // Bail if we exceed the maximum size.
1439 {
1440 CMPQ(dst, dstLimitPtrQ)
1441 JB(LabelRef("match_nolit_dst_ok_" + name))
1442 ri, err := ReturnIndex(0).Resolve()
1443 if err != nil {
1444 panic(err)
1445 }
1446 MOVQ(U32(0), ri.Addr)
1447 if o.avx2 {
1448 VZEROUPPER()
1449 }
1450 RET()
1451 }
1452 }
1453 Label("match_nolit_dst_ok_" + name)
1454 if true {
1455 lHasher := hashN(lHashBytes, lTableBits)
1456 sHasher := hashN(sHashBytes, sTableBits)
1457
1458 index0, index1 := GP64(), GP64()
1459 // index0 := base + 1
1460 LEAQ(Mem{Base: base, Disp: 1}, index0)
1461 // index1 := s - 2
1462 LEAQ(Mem{Base: s, Disp: -2}, index1)
1463 hash0l, hash0s, hash1l, hash1s := GP64(), GP64(), GP64(), GP64()
1464 MOVQ(Mem{Base: src, Index: index0, Scale: 1, Disp: 0}, hash0l)
1465 MOVQ(Mem{Base: src, Index: index0, Scale: 1, Disp: 1}, hash0s)
1466 MOVQ(Mem{Base: src, Index: index1, Scale: 1, Disp: 0}, hash1l)
1467 MOVQ(Mem{Base: src, Index: index1, Scale: 1, Disp: 1}, hash1s)
1468
1469 lHasher.hash(hash0l)
1470 sHasher.hash(hash0s)
1471 lHasher.hash(hash1l)
1472 sHasher.hash(hash1s)
1473
1474 plusone0, plusone1 := GP64(), GP64()
1475 LEAQ(Mem{Base: index0, Disp: 1}, plusone0)
1476 LEAQ(Mem{Base: index1, Disp: 1}, plusone1)
1477 MOVL(index0.As32(), lTab.Idx(hash0l, 4))
1478 MOVL(index1.As32(), lTab.Idx(hash1l, 4))
1479 MOVL(plusone0.As32(), sTab.Idx(hash0s, 4))
1480 MOVL(plusone1.As32(), sTab.Idx(hash1s, 4))
1481
1482 // index2 := (index0 + index1 + 1) >> 1
1483 index2 := GP64()
1484 LEAQ(Mem{Base: index1, Disp: 1, Index: index0, Scale: 1}, index2)
1485 SHRQ(U8(1), index2)
1486
1487 ADDQ(U8(1), index0)
1488 SUBQ(U8(1), index1)
1489
1490 Label("index_loop_" + name)
1491 // for index2 < index1
1492 CMPQ(index2, index1)
1493 JAE(LabelRef("search_loop_" + name))
1494 hash0l, hash1l = GP64(), GP64()
1495 MOVQ(Mem{Base: src, Index: index0, Scale: 1, Disp: 0}, hash0l)
1496 MOVQ(Mem{Base: src, Index: index2, Scale: 1, Disp: 0}, hash1l)
1497
1498 lHasher.hash(hash0l)
1499 lHasher.hash(hash1l)
1500
1501 MOVL(index0.As32(), lTab.Idx(hash0l, 4))
1502 MOVL(index2.As32(), lTab.Idx(hash1l, 4))
1503
1504 ADDQ(U8(2), index0)
1505 ADDQ(U8(2), index2)
1506 JMP(LabelRef("index_loop_" + name))
1507 } else {
1508 lHasher := hashN(lHashBytes, lTableBits)
1509 sHasher := hashN(sHashBytes, sTableBits)
1510
1511 // Index base+1 long, base+2 short...
1512 cv := GP64()
1513 INCL(base)
1514 MOVQ(Mem{Base: src, Index: base, Scale: 1, Disp: 0}, cv)
1515 hash0, hash1, hash2, hash3 := GP64(), GP64(), GP64(), GP64()
1516 MOVQ(cv, hash0) // src[base+1]
1517 MOVQ(cv, hash1)
1518 MOVQ(cv, hash2)
1519 SHRQ(U8(8), hash1) // src[base+2]
1520 MOVQ(hash1, hash3)
1521 SHRQ(U8(16), hash2) // src[base+3]
1522 bp1, bp2 := GP32(), GP32() // base+1
1523 LEAL(Mem{Base: base, Disp: 1}, bp1)
1524 LEAL(Mem{Base: base, Disp: 2}, bp2)
1525
1526 // Load s-2 early
1527 MOVQ(Mem{Base: src, Index: s, Scale: 1, Disp: -2}, cv)
1528
1529 lHasher.hash(hash0)
1530 lHasher.hash(hash3)
1531 sHasher.hash(hash1)
1532 sHasher.hash(hash2)
1533 assert(func(ok LabelRef) {
1534 CMPQ(hash0, U32(lTableSize))
1535 JB(ok)
1536 })
1537 assert(func(ok LabelRef) {
1538 CMPQ(hash3, U32(lTableSize))
1539 JB(ok)
1540 })
1541 assert(func(ok LabelRef) {
1542 CMPQ(hash1, U32(sTableSize))
1543 JB(ok)
1544 })
1545 assert(func(ok LabelRef) {
1546 CMPQ(hash2, U32(sTableSize))
1547 JB(ok)
1548 })
1549 MOVL(base, lTab.Idx(hash0, 4))
1550 MOVL(bp1, lTab.Idx(hash3, 4))
1551 MOVL(bp1, sTab.Idx(hash1, 4))
1552 MOVL(bp2, sTab.Idx(hash2, 4))
1553
1554 // Index s-2 long, s-1 long+short...
1555 MOVQ(cv, hash0) // src[s-2]
1556 MOVQ(cv, hash1) // src[s-1]
1557 SHRQ(U8(8), hash1)
1558 MOVQ(hash1, hash3)
1559 sm1, sm2 := GP32(), GP32() // s -1, s - 2
1560 LEAL(Mem{Base: s, Disp: -2}, sm2)
1561 LEAL(Mem{Base: s, Disp: -1}, sm1)
1562 lHasher.hash(hash0)
1563 sHasher.hash(hash1)
1564 lHasher.hash(hash3)
1565 assert(func(ok LabelRef) {
1566 CMPQ(hash0, U32(lTableSize))
1567 JB(ok)
1568 })
1569 assert(func(ok LabelRef) {
1570 CMPQ(hash3, U32(lTableSize))
1571 JB(ok)
1572 })
1573 assert(func(ok LabelRef) {
1574 CMPQ(hash1, U32(sTableSize))
1575 JB(ok)
1576 })
1577 MOVL(sm2, lTab.Idx(hash0, 4))
1578 MOVL(sm1, sTab.Idx(hash1, 4))
1579 MOVL(sm1, lTab.Idx(hash3, 4))
1580 JMP(LabelRef("search_loop_" + name))
1581 }
1582
1583 Label("emit_remainder_" + name)
1584 // Bail if we exceed the maximum size.
1585 // if d+len(src)-nextEmitL > dstLimitPtrQ { return 0
1586 {
1587 // remain = len(src) - nextEmit
1588 remain := GP64()
1589 MOVQ(lenSrcQ, remain)
1590 SUBL(nextEmitL, remain.As32())
1591
1592 dstExpect := GP64()
1593 // dst := dst + (len(src)-nextEmitL)
1594
1595 LEAQ(Mem{Base: dst, Index: remain, Scale: 1, Disp: literalMaxOverhead}, dstExpect)
1596 CMPQ(dstExpect, dstLimitPtrQ)
1597 JB(LabelRef("emit_remainder_ok_" + name))
1598 ri, err := ReturnIndex(0).Resolve()
1599 if err != nil {
1600 panic(err)
1601 }
1602 MOVQ(U32(0), ri.Addr)
1603 if o.avx2 {
1604 VZEROUPPER()
1605 }
1606 RET()
1607 Label("emit_remainder_ok_" + name)
1608 }
1609 // emitLiteral(dst[d:], src[nextEmitL:])
1610 emitEnd := GP64()
1611 MOVQ(lenSrcQ, emitEnd)
1612
1613 // Emit final literals.
1614 // Since we may be at the end of source,
1615 // we cannot have output margin.
1616 x := o.outputMargin
1617 o.outputMargin = 0
1618 o.emitLiteralsDstP(nextEmitL, emitEnd, src, dst, "emit_remainder_"+name)
1619 o.outputMargin = x
1620
1621 // Assert size is < limit
1622 assert(func(ok LabelRef) {
1623 // if dstBaseQ < dstLimitPtrQ: ok
1624 CMPQ(dst, dstLimitPtrQ)
1625 JB(ok)
1626 })
1627
1628 // length := start - base (ptr arithmetic)
1629 length := GP64()
1630 dstBase := Load(Param("dst").Base(), GP64())
1631 MOVQ(dst, length)
1632 SUBQ(dstBase, length)
1633
1634 // Assert size is < len(src)
1635 assert(func(ok LabelRef) {
1636 // if len(src) >= length: ok
1637 CMPQ(lenSrcQ, length)
1638 JAE(ok)
1639 })
1640 // Assert size is < len(dst)
1641 assert(func(ok LabelRef) {
1642 // if len(dst) >= length: ok
1643 CMPQ(lenDstQ, length)
1644 JAE(ok)
1645 })
1646 Store(length, ReturnIndex(0))
1647 if o.avx2 {
1648 VZEROUPPER()
1649 }
1650 RET()
1651 }
1652
1653 // emitLiterals emits literals from nextEmit to base, updates nextEmit, dstBase.
1654 // Checks if base == nextemit.
1655 // src & base are untouched.
1656 func (o options) emitLiterals(nextEmitL Mem, base reg.GPVirtual, src reg.GPVirtual, dstBase Mem, name string) {
1657 nextEmit, litLen, dstBaseTmp, litBase := GP32(), GP32(), GP64(), GP64()
1658 MOVL(nextEmitL, nextEmit)
1659 CMPL(nextEmit, base.As32())
1660 JEQ(LabelRef("emit_literal_skip_" + name))
1661 MOVL(base.As32(), litLen.As32())
1662
1663 // Base is now next emit.
1664 MOVL(base.As32(), nextEmitL)
1665
1666 // litBase = src[nextEmitL:]
1667 LEAQ(Mem{Base: src, Index: nextEmit, Scale: 1}, litBase)
1668 SUBL(nextEmit, litLen.As32()) // litlen = base - nextEmit
1669
1670 // Load (and store when we return)
1671 MOVQ(dstBase, dstBaseTmp)
1672 o.emitLiteral(name, litLen, nil, dstBaseTmp, litBase, LabelRef("emit_literal_done_"+name), true)
1673 Label("emit_literal_done_" + name)
1674
1675 // Emitted length must be > litlen.
1676 // We have already checked for len(0) above.
1677 assert(func(ok LabelRef) {
1678 tmp := GP64()
1679 MOVQ(dstBaseTmp, tmp)
1680 SUBQ(dstBase, tmp) // tmp = dstBaseTmp - dstBase
1681 // if tmp > litLen: ok
1682 CMPQ(tmp, litLen.As64())
1683 JA(ok)
1684 })
1685 // Store updated dstBase
1686 MOVQ(dstBaseTmp, dstBase)
1687 Label("emit_literal_skip_" + name)
1688 }
1689
1690 // emitLiterals emits literals from nextEmit to base, updates nextEmit, dstBase.
1691 // Checks if base == nextemit.
1692 // src & base are untouched.
1693 func (o options) emitLiteralsDstP(nextEmitL Mem, base reg.GPVirtual, src, dst reg.GPVirtual, name string) {
1694 nextEmit, litLen, litBase := GP32(), GP32(), GP64()
1695 MOVL(nextEmitL, nextEmit)
1696 CMPL(nextEmit, base.As32())
1697 JEQ(LabelRef("emit_literal_done_" + name))
1698 MOVL(base.As32(), litLen.As32())
1699
1700 // Base is now next emit.
1701 MOVL(base.As32(), nextEmitL)
1702
1703 // litBase = src[nextEmitL:]
1704 LEAQ(Mem{Base: src, Index: nextEmit, Scale: 1}, litBase)
1705 SUBL(nextEmit, litLen.As32()) // litlen = base - nextEmit
1706
1707 // Load (and store when we return)
1708 o.emitLiteral(name, litLen, nil, dst, litBase, LabelRef("emit_literal_done_"+name), true)
1709 Label("emit_literal_done_" + name)
1710 }
1711
1712 type hashGen struct {
1713 bytes int
1714 tablebits int
1715 mulreg reg.GPVirtual
1716 }
1717
1718 // hashN uses multiply to get a 'output' hash on the hash of the lowest 'bytes' bytes in value.
1719 func hashN(hashBytes, tablebits int) hashGen {
1720 h := hashGen{
1721 bytes: hashBytes,
1722 tablebits: tablebits,
1723 mulreg: GP64(),
1724 }
1725 primebytes := uint64(0)
1726 switch hashBytes {
1727 case 3:
1728 primebytes = 506832829
1729 case 4:
1730 primebytes = 2654435761
1731 case 5:
1732 primebytes = 889523592379
1733 case 6:
1734 primebytes = 227718039650203
1735 case 7:
1736 primebytes = 58295818150454627
1737 case 8:
1738 primebytes = 0xcf1bbcdcb7a56463
1739 default:
1740 panic("invalid hash length")
1741 }
1742 MOVQ(Imm(primebytes), h.mulreg)
1743 return h
1744 }
1745
1746 // hash uses multiply to get hash of the value.
1747 func (h hashGen) hash(val reg.GPVirtual) {
1748 // Move value to top of register.
1749 if h.bytes < 8 {
1750 SHLQ(U8(64-8*h.bytes), val)
1751 }
1752 // 329 AMD64 :IMUL r64, r64 L: 0.86ns= 3.0c T: 0.29ns= 1.00c
1753 // 2020 BMI2 :MULX r64, r64, r64 L: 1.14ns= 4.0c T: 0.29ns= 1.00c
1754 IMULQ(h.mulreg, val)
1755 // Move value to bottom
1756 // 2032 BMI2 :SHRX r64, r64, r64 L: 0.29ns= 1.0c T: 0.12ns= 0.42c
1757 // 236 AMD64 :SHR r64, imm8 L: 0.29ns= 1.0c T: 0.13ns= 0.46c
1758 SHRQ(U8(64-h.tablebits), val)
1759 }
1760
1761 func (o options) genEmitLiteral() {
1762 TEXT("emitLiteral", NOSPLIT, "func(dst, lit []byte) int")
1763 Doc("emitLiteral writes a literal chunk and returns the number of bytes written.", "",
1764 "It assumes that:",
1765 fmt.Sprintf(" dst is long enough to hold the encoded bytes with margin of %d bytes", o.outputMargin),
1766 " 0 <= len(lit) && len(lit) <= math.MaxUint32", "")
1767 Pragma("noescape")
1768
1769 dstBase, litBase, litLen, retval := GP64(), GP64(), GP64(), GP64()
1770 Load(Param("lit").Len(), litLen)
1771 Load(Param("dst").Base(), dstBase)
1772 Load(Param("lit").Base(), litBase)
1773 TESTQ(litLen, litLen)
1774 JZ(LabelRef("emit_literal_end_standalone_skip"))
1775 o.emitLiteral("standalone", litLen, retval, dstBase, litBase, "emit_literal_end_standalone", false)
1776
1777 Label("emit_literal_end_standalone_skip")
1778 XORQ(retval, retval)
1779
1780 Label("emit_literal_end_standalone")
1781 Store(retval, ReturnIndex(0))
1782 RET()
1783
1784 }
1785
1786 // emitLiteral can be used for inlining an emitLiteral call.
1787 // litLen must be > 0.
1788 // stack must have at least 32 bytes.
1789 // retval will contain emitted bytes, but can be nil if this is not interesting.
1790 // dstBase and litBase are updated.
1791 // Uses 2 GP registers.
1792 // If updateDst is true dstBase will have the updated end pointer and an additional register will be used.
1793 func (o options) emitLiteral(name string, litLen, retval, dstBase, litBase reg.GPVirtual, end LabelRef, updateDst bool) {
1794 n := GP32()
1795 n16 := GP32()
1796
1797 // litLen must be > 0
1798 assert(func(ok LabelRef) {
1799 TESTL(litLen.As32(), litLen.As32())
1800 JNZ(ok)
1801 })
1802
1803 // We always add litLen bytes
1804 if retval != nil {
1805 MOVL(litLen.As32(), retval.As32())
1806 }
1807 // n = litlen - 1
1808 LEAL(Mem{Base: litLen.As32(), Disp: -1}, n)
1809
1810 // Find number of bytes to emit for tag.
1811 CMPL(n.As32(), U8(60))
1812 JB(LabelRef("one_byte_" + name))
1813 CMPL(n.As32(), U32(1<<8))
1814 JB(LabelRef("two_bytes_" + name))
1815 if o.maxLen >= 1<<16 {
1816 CMPL(n.As32(), U32(1<<16))
1817 JB(LabelRef("three_bytes_" + name))
1818 } else {
1819 JB(LabelRef("three_bytes_" + name))
1820 }
1821 if o.maxLen >= 1<<16 {
1822 if o.maxLen >= 1<<24 {
1823 CMPL(n.As32(), U32(1<<24))
1824 JB(LabelRef("four_bytes_" + name))
1825 } else {
1826 JMP(LabelRef("four_bytes_" + name))
1827 }
1828 }
1829 if o.maxLen >= 1<<24 {
1830 Label("five_bytes_" + name)
1831 if !o.skipOutput {
1832 MOVB(U8(252), Mem{Base: dstBase})
1833 MOVL(n.As32(), Mem{Base: dstBase, Disp: 1})
1834 }
1835 if retval != nil {
1836 ADDQ(U8(5), retval)
1837 }
1838 ADDQ(U8(5), dstBase)
1839 JMP(LabelRef("memmove_long_" + name))
1840 }
1841 if o.maxLen >= 1<<16 {
1842 Label("four_bytes_" + name)
1843 if !o.skipOutput {
1844 MOVL(n, n16)
1845 SHRL(U8(16), n16.As32())
1846 MOVB(U8(248), Mem{Base: dstBase})
1847 MOVW(n.As16(), Mem{Base: dstBase, Disp: 1})
1848 MOVB(n16.As8(), Mem{Base: dstBase, Disp: 3})
1849 }
1850 if retval != nil {
1851 ADDQ(U8(4), retval)
1852 }
1853 ADDQ(U8(4), dstBase)
1854 JMP(LabelRef("memmove_long_" + name))
1855 }
1856 Label("three_bytes_" + name)
1857 if !o.skipOutput {
1858 MOVB(U8(0xf4), Mem{Base: dstBase})
1859 MOVW(n.As16(), Mem{Base: dstBase, Disp: 1})
1860 }
1861 if retval != nil {
1862 ADDQ(U8(3), retval)
1863 }
1864 ADDQ(U8(3), dstBase)
1865 JMP(LabelRef("memmove_long_" + name))
1866
1867 Label("two_bytes_" + name)
1868 if !o.skipOutput {
1869 MOVB(U8(0xf0), Mem{Base: dstBase})
1870 MOVB(n.As8(), Mem{Base: dstBase, Disp: 1})
1871 }
1872 if retval != nil {
1873 ADDQ(U8(2), retval)
1874 }
1875 ADDQ(U8(2), dstBase)
1876 CMPL(n.As32(), U8(64))
1877 JB(LabelRef("memmove_" + name))
1878 JMP(LabelRef("memmove_long_" + name))
1879
1880 Label("one_byte_" + name)
1881 if !o.skipOutput {
1882 SHLB(U8(2), n.As8())
1883 MOVB(n.As8(), Mem{Base: dstBase})
1884 }
1885 if retval != nil {
1886 ADDQ(U8(1), retval)
1887 }
1888 ADDQ(U8(1), dstBase)
1889 // Fallthrough
1890
1891 Label("memmove_" + name)
1892
1893 // copy(dst[i:], lit)
1894 dstEnd := GP64()
1895 copyEnd := end
1896 if updateDst {
1897 copyEnd = LabelRef("memmove_end_copy_" + name)
1898 LEAQ(Mem{Base: dstBase, Index: litLen, Scale: 1}, dstEnd)
1899 }
1900 if !o.skipOutput {
1901
1902 length := GP64()
1903 MOVL(litLen.As32(), length.As32())
1904
1905 // We wrote one byte, we have that less in output margin.
1906 o.outputMargin--
1907 // updates litBase.
1908 o.genMemMoveShort("emit_lit_memmove_"+name, dstBase, litBase, length, copyEnd)
1909 o.outputMargin++
1910 }
1911 if updateDst {
1912 Label("memmove_end_copy_" + name)
1913 MOVQ(dstEnd, dstBase)
1914 }
1915 JMP(end)
1916
1917 // > 64 bytes
1918 Label("memmove_long_" + name)
1919
1920 // copy(dst[i:], lit)
1921 dstEnd = GP64()
1922 copyEnd = end
1923 if updateDst {
1924 copyEnd = LabelRef("memmove_end_copy_long_" + name)
1925 LEAQ(Mem{Base: dstBase, Index: litLen, Scale: 1}, dstEnd)
1926 }
1927 if !o.skipOutput {
1928 length := GP64()
1929 MOVL(litLen.As32(), length.As32())
1930
1931 // updates litBase.
1932 o.genMemMoveLong("emit_lit_memmove_long_"+name, dstBase, litBase, length, copyEnd)
1933 }
1934 if updateDst {
1935 Label("memmove_end_copy_long_" + name)
1936 MOVQ(dstEnd, dstBase)
1937 }
1938 JMP(end)
1939 // Should be unreachable
1940 if debug {
1941 INT(Imm(3))
1942 }
1943 return
1944 }
1945
1946 // genEmitRepeat generates a standalone emitRepeat.
1947 func (o options) genEmitRepeat() {
1948 TEXT("emitRepeat", NOSPLIT, "func(dst []byte, offset, length int) int")
1949 Doc("emitRepeat writes a repeat chunk and returns the number of bytes written.",
1950 "Length must be at least 4 and < 1<<32", "")
1951 Pragma("noescape")
1952
1953 dstBase, offset, length, retval := GP64(), GP64(), GP64(), GP64()
1954
1955 // retval = 0
1956 XORQ(retval, retval)
1957
1958 Load(Param("dst").Base(), dstBase)
1959 Load(Param("offset"), offset)
1960 Load(Param("length"), length)
1961 o.emitRepeat("standalone", length, offset, retval, dstBase, LabelRef("gen_emit_repeat_end"), false)
1962 Label("gen_emit_repeat_end")
1963 Store(retval, ReturnIndex(0))
1964 RET()
1965 }
1966
1967 // emitRepeat can be used for inlining an emitRepeat call.
1968 // length >= 4 and < 1<<32
1969 // length is modified. dstBase is updated. retval is added to input.
1970 // retval can be nil.
1971 // Will jump to end label when finished.
1972 // Uses 1 GP register.
1973 // longer indicates we know match will be > 12
1974 func (o options) emitRepeat(name string, length reg.GPVirtual, offset reg.GPVirtual, retval reg.GPVirtual, dstBase reg.GPVirtual, end LabelRef, longer bool) {
1975 Comment("emitRepeat")
1976 if longer {
1977 // Skip initial length tests
1978 LEAL(Mem{Base: length, Disp: -4}, length.As32()) // length -= 4
1979 JMP(LabelRef("cant_repeat_two_offset_" + name))
1980 }
1981 Label("emit_repeat_again_" + name)
1982 tmp := GP32()
1983 MOVL(length.As32(), tmp) // Copy length
1984 LEAL(Mem{Base: length, Disp: -4}, length.As32()) // length -= 4
1985
1986 // if length <= 4 (use copied value)
1987 CMPL(tmp.As32(), U8(8))
1988 JBE(LabelRef("repeat_two_" + name))
1989
1990 // length < 8 && offset < 2048
1991 CMPL(tmp.As32(), U8(12))
1992 JAE(LabelRef("cant_repeat_two_offset_" + name))
1993 if o.maxLen >= 2048 {
1994 CMPL(offset.As32(), U32(2048))
1995 JB(LabelRef("repeat_two_offset_" + name))
1996 }
1997
1998 const maxRepeat = ((1 << 24) - 1) + 65536
1999 Label("cant_repeat_two_offset_" + name)
2000 CMPL(length.As32(), U32((1<<8)+4))
2001 JB(LabelRef("repeat_three_" + name)) // if length < (1<<8)+4
2002 if o.maxLen >= (1<<16)+(1<<8) {
2003 CMPL(length.As32(), U32((1<<16)+(1<<8)))
2004 JB(LabelRef("repeat_four_" + name)) // if length < (1 << 16) + (1 << 8)
2005 } else {
2006 // Not needed, we should skip to it when generating.
2007 // JMP(LabelRef("repeat_four_" + name)) // if length < (1 << 16) + (1 << 8)
2008 }
2009 if o.maxLen >= maxRepeat {
2010 CMPL(length.As32(), U32(maxRepeat))
2011 JB(LabelRef("repeat_five_" + name)) // If less than 24 bits to represent.
2012
2013 if !o.skipOutput {
2014 // We have have more than 24 bits
2015 // Emit so we have at least 4 bytes left.
2016 LEAL(Mem{Base: length, Disp: -(maxRepeat - 4)}, length.As32()) // length -= (maxRepeat - 4)
2017 MOVL(U32(7<<2|tagCopy1|(65531<<16)), Mem{Base: dstBase}) // dst[0] = 7<<2 | tagCopy1, dst[1] = 0 dst[2+3] = 65531
2018 MOVB(U8(255), Mem{Base: dstBase, Disp: 4})
2019 ADDQ(U8(5), dstBase)
2020 }
2021 if retval != nil {
2022 ADDQ(U8(5), retval)
2023 }
2024 JMP(LabelRef("emit_repeat_again_" + name))
2025 } else {
2026 // Not needed.
2027 // JMP(LabelRef("repeat_five_" + name)) // If less than 24 bits to represent.
2028 }
2029
2030 // Must be able to be within 5 bytes.
2031 if o.maxLen >= (1<<16)+(1<<8) {
2032 Label("repeat_five_" + name)
2033 LEAL(Mem{Base: length, Disp: -65536}, length.As32()) // length -= 65536
2034 if !o.skipOutput {
2035 MOVL(length.As32(), offset.As32())
2036 MOVW(U16(7<<2|tagCopy1), Mem{Base: dstBase}) // dst[0] = 7<<2 | tagCopy1, dst[1] = 0
2037 MOVW(length.As16(), Mem{Base: dstBase, Disp: 2}) // dst[2] = uint8(length), dst[3] = uint8(length >> 8)
2038 SARL(U8(16), offset.As32()) // offset = length >> 16
2039 MOVB(offset.As8(), Mem{Base: dstBase, Disp: 4}) // dst[4] = length >> 16
2040 }
2041 if retval != nil {
2042 ADDQ(U8(5), retval) // i += 5
2043 }
2044 ADDQ(U8(5), dstBase) // dst += 5
2045 JMP(end)
2046 }
2047 Label("repeat_four_" + name)
2048 if !o.skipOutput {
2049 LEAL(Mem{Base: length, Disp: -256}, length.As32()) // length -= 256
2050 MOVW(U16(6<<2|tagCopy1), Mem{Base: dstBase}) // dst[0] = 6<<2 | tagCopy1, dst[1] = 0
2051 MOVW(length.As16(), Mem{Base: dstBase, Disp: 2}) // dst[2] = uint8(length), dst[3] = uint8(length >> 8)
2052 }
2053 if retval != nil {
2054 ADDQ(U8(4), retval) // i += 4
2055 }
2056 ADDQ(U8(4), dstBase) // dst += 4
2057 JMP(end)
2058
2059 Label("repeat_three_" + name)
2060 if !o.skipOutput {
2061 LEAL(Mem{Base: length, Disp: -4}, length.As32()) // length -= 4
2062 MOVW(U16(5<<2|tagCopy1), Mem{Base: dstBase}) // dst[0] = 5<<2 | tagCopy1, dst[1] = 0
2063 MOVB(length.As8(), Mem{Base: dstBase, Disp: 2}) // dst[2] = uint8(length)
2064 }
2065 if retval != nil {
2066 ADDQ(U8(3), retval) // i += 3
2067 }
2068 ADDQ(U8(3), dstBase) // dst += 3
2069 JMP(end)
2070
2071 Label("repeat_two_" + name)
2072 // dst[0] = uint8(length)<<2 | tagCopy1, dst[1] = 0
2073 if !o.skipOutput {
2074 SHLL(U8(2), length.As32())
2075 ORL(U8(tagCopy1), length.As32())
2076 MOVW(length.As16(), Mem{Base: dstBase}) // dst[0] = 7<<2 | tagCopy1, dst[1] = 0
2077 }
2078 if retval != nil {
2079 ADDQ(U8(2), retval) // i += 2
2080 }
2081 ADDQ(U8(2), dstBase) // dst += 2
2082 JMP(end)
2083
2084 Label("repeat_two_offset_" + name)
2085 // Emit the remaining copy, encoded as 2 bytes.
2086 // dst[1] = uint8(offset)
2087 // dst[0] = uint8(offset>>8)<<5 | uint8(length)<<2 | tagCopy1
2088 tmp = GP64()
2089 XORQ(tmp, tmp)
2090 // Use scale and displacement to shift and subtract values from length.
2091 if !o.skipOutput {
2092 LEAL(Mem{Base: tmp, Index: length, Scale: 4, Disp: tagCopy1}, length.As32())
2093 MOVB(offset.As8(), Mem{Base: dstBase, Disp: 1}) // Store offset lower byte
2094 SARL(U8(8), offset.As32()) // Remove lower
2095 SHLL(U8(5), offset.As32()) // Shift back up
2096 ORL(offset.As32(), length.As32()) // OR result
2097 MOVB(length.As8(), Mem{Base: dstBase, Disp: 0})
2098 }
2099 if retval != nil {
2100 ADDQ(U8(2), retval) // i += 2
2101 }
2102 ADDQ(U8(2), dstBase) // dst += 2
2103
2104 JMP(end)
2105 }
2106
2107 // emitCopy writes a copy chunk and returns the number of bytes written.
2108 //
2109 // It assumes that:
2110 // dst is long enough to hold the encoded bytes
2111 // 1 <= offset && offset <= math.MaxUint32
2112 // 4 <= length && length <= 1 << 24
2113
2114 // genEmitCopy generates a standalone emitCopy
2115 func (o options) genEmitCopy() {
2116 TEXT("emitCopy", NOSPLIT, "func(dst []byte, offset, length int) int")
2117 Doc("emitCopy writes a copy chunk and returns the number of bytes written.", "",
2118 "It assumes that:",
2119 " dst is long enough to hold the encoded bytes",
2120 " 1 <= offset && offset <= math.MaxUint32",
2121 " 4 <= length && length <= 1 << 24", "")
2122 Pragma("noescape")
2123
2124 dstBase, offset, length, retval := GP64(), GP64(), GP64(), GP64()
2125
2126 // i := 0
2127 XORQ(retval, retval)
2128 Load(Param("dst").Base(), dstBase)
2129 Load(Param("offset"), offset)
2130 Load(Param("length"), length)
2131 o.emitCopy("standalone", length, offset, retval, dstBase, nil, LabelRef("gen_emit_copy_end"))
2132 Label("gen_emit_copy_end")
2133 Store(retval, ReturnIndex(0))
2134 RET()
2135 }
2136
2137 // emitCopy writes a copy chunk and returns the number of bytes written.
2138 //
2139 // It assumes that:
2140 // dst is long enough to hold the encoded bytes
2141 // 1 <= offset && offset <= math.MaxUint32
2142 // 4 <= length && length <= 1 << 24
2143
2144 // genEmitCopy generates a standalone emitCopy
2145 func (o options) genEmitCopyNoRepeat() {
2146 TEXT("emitCopyNoRepeat", NOSPLIT, "func(dst []byte, offset, length int) int")
2147 Doc("emitCopyNoRepeat writes a copy chunk and returns the number of bytes written.", "",
2148 "It assumes that:",
2149 " dst is long enough to hold the encoded bytes",
2150 " 1 <= offset && offset <= math.MaxUint32",
2151 " 4 <= length && length <= 1 << 24", "")
2152 Pragma("noescape")
2153
2154 dstBase, offset, length, retval := GP64(), GP64(), GP64(), GP64()
2155
2156 // i := 0
2157 XORQ(retval, retval)
2158
2159 Load(Param("dst").Base(), dstBase)
2160 Load(Param("offset"), offset)
2161 Load(Param("length"), length)
2162 o.emitCopy("standalone_snappy", length, offset, retval, dstBase, nil, "gen_emit_copy_end_snappy")
2163 Label("gen_emit_copy_end_snappy")
2164 Store(retval, ReturnIndex(0))
2165 RET()
2166 }
2167
2168 const (
2169 tagLiteral = 0x00
2170 tagCopy1 = 0x01
2171 tagCopy2 = 0x02
2172 tagCopy4 = 0x03
2173 )
2174
2175 // emitCopy can be used for inlining an emitCopy call.
2176 // length is modified (and junk). dstBase is updated. retval is added to input.
2177 // retval can be nil.
2178 // Will jump to end label when finished.
2179 // Uses 2 GP registers.
2180 // dstLimit is optional. If set each iteration will check if dstLimit is reached.
2181 // If so, it will jump to "end" without emitting everything.
2182 func (o options) emitCopy(name string, length, offset, retval, dstBase, dstLimit reg.GPVirtual, end LabelRef) {
2183 Comment("emitCopy")
2184
2185 checkDst := func(reg reg.GPVirtual) {
2186 if dstLimit != nil {
2187 CMPQ(reg, dstLimit)
2188 JAE(end)
2189 }
2190 }
2191
2192 if o.maxOffset >= 65536 {
2193 //if offset >= 65536 {
2194 CMPL(offset.As32(), U32(65536))
2195 JB(LabelRef("two_byte_offset_" + name))
2196
2197 // offset is >= 65536
2198 // if length <= 64 goto four_bytes_remain_
2199 Label("four_bytes_loop_back_" + name)
2200 CMPL(length.As32(), U8(64))
2201 JBE(LabelRef("four_bytes_remain_" + name))
2202
2203 if !o.skipOutput {
2204 // Emit a length 64 copy, encoded as 5 bytes.
2205 // dst[0] = 63<<2 | tagCopy4
2206 MOVB(U8(63<<2|tagCopy4), Mem{Base: dstBase})
2207 // dst[4] = uint8(offset >> 24)
2208 // dst[3] = uint8(offset >> 16)
2209 // dst[2] = uint8(offset >> 8)
2210 // dst[1] = uint8(offset)
2211 MOVL(offset.As32(), Mem{Base: dstBase, Disp: 1})
2212 }
2213 // length -= 64
2214 LEAL(Mem{Base: length, Disp: -64}, length.As32())
2215 if retval != nil {
2216 ADDQ(U8(5), retval) // i+=5
2217 }
2218 ADDQ(U8(5), dstBase) // dst+=5
2219
2220 // if length >= 4 {
2221 CMPL(length.As32(), U8(4))
2222 JB(LabelRef("four_bytes_remain_" + name))
2223
2224 // Emit remaining as repeats
2225 // return 5 + emitRepeat(dst[5:], offset, length)
2226 // Inline call to emitRepeat. Will jump to end
2227 if !o.snappy {
2228 o.emitRepeat(name+"_emit_copy", length, offset, retval, dstBase, end, false)
2229 } else {
2230 checkDst(dstBase)
2231 JMP(LabelRef("four_bytes_loop_back_" + name))
2232 }
2233
2234 Label("four_bytes_remain_" + name)
2235 // if length == 0 {
2236 // return i
2237 // }
2238 TESTL(length.As32(), length.As32())
2239 JZ(end)
2240
2241 // Emit a copy, offset encoded as 4 bytes.
2242 // dst[i+0] = uint8(length-1)<<2 | tagCopy4
2243 // dst[i+1] = uint8(offset)
2244 // dst[i+2] = uint8(offset >> 8)
2245 // dst[i+3] = uint8(offset >> 16)
2246 // dst[i+4] = uint8(offset >> 24)
2247 tmp := GP64()
2248 XORL(tmp.As32(), tmp.As32())
2249 // Use displacement to subtract 1 from upshifted length.
2250 if !o.skipOutput {
2251 LEAL(Mem{Base: tmp, Disp: -(1 << 2) | tagCopy4, Index: length, Scale: 4}, length.As32())
2252 MOVB(length.As8(), Mem{Base: dstBase})
2253 MOVL(offset.As32(), Mem{Base: dstBase, Disp: 1})
2254 }
2255 // return i + 5
2256 if retval != nil {
2257 ADDQ(U8(5), retval)
2258 }
2259 ADDQ(U8(5), dstBase)
2260 JMP(end)
2261 }
2262 Label("two_byte_offset_" + name)
2263 // Offset no more than 2 bytes.
2264
2265 //if length > 64 {
2266 CMPL(length.As32(), U8(64))
2267 JBE(LabelRef("two_byte_offset_short_" + name))
2268
2269 // if offset < 2048 {
2270 if !o.snappy {
2271 CMPL(offset.As32(), U32(2048))
2272 JAE(LabelRef("long_offset_short_" + name))
2273 // Emit a length 8 copy, encoded as 2 bytes.
2274 // Emit remaining as repeat value (minimum 4 bytes).
2275 // dst[1] = uint8(offset)
2276 // dst[0] = uint8(offset>>8)<<5 | uint8(8-4)<<2 | tagCopy1
2277 if !o.skipOutput {
2278 tmp := GP64()
2279 MOVL(U32(tagCopy1), tmp.As32())
2280 // Use scale and displacement to shift and subtract values from length.
2281 LEAL(Mem{Base: tmp, Disp: (8 - 4) << 2}, tmp.As32())
2282 MOVB(offset.As8(), Mem{Base: dstBase, Disp: 1}) // Store offset lower byte
2283 tmp2 := GP64()
2284 MOVL(offset.As32(), tmp2.As32())
2285 SHRL(U8(8), tmp2.As32()) // Remove lower
2286 SHLL(U8(5), tmp2.As32()) // Shift back up
2287 ORL(tmp2.As32(), tmp.As32()) // OR result
2288 MOVB(tmp.As8(), Mem{Base: dstBase, Disp: 0})
2289 }
2290 if retval != nil {
2291 ADDQ(U8(2), retval) // i += 2
2292 }
2293 ADDQ(U8(2), dstBase) // dst += 2
2294 SUBL(U8(8), length.As32()) // length -= 8
2295 // emitRepeat(dst[2:], offset, length)
2296 o.emitRepeat(name+"_emit_copy_short_2b", length, offset, retval, dstBase, end, true)
2297
2298 Label("long_offset_short_" + name)
2299 }
2300
2301 // Emit a length 60 copy, encoded as 3 bytes.
2302 // Emit remaining as repeat value (minimum 4 bytes).
2303 // dst[2] = uint8(offset >> 8)
2304 // dst[1] = uint8(offset)
2305 // dst[0] = 59<<2 | tagCopy2
2306 if !o.skipOutput {
2307 MOVB(U8(59<<2|tagCopy2), Mem{Base: dstBase})
2308 MOVW(offset.As16(), Mem{Base: dstBase, Disp: 1})
2309 }
2310 // length -= 60
2311 LEAL(Mem{Base: length, Disp: -60}, length.As32())
2312
2313 // Emit remaining as repeats, at least 4 bytes remain.
2314 // return 3 + emitRepeat(dst[3:], offset, length)
2315 //}
2316 ADDQ(U8(3), dstBase)
2317 if retval != nil {
2318 ADDQ(U8(3), retval)
2319 }
2320 // Inline call to emitRepeat. Will jump to end
2321 if !o.snappy {
2322 o.emitRepeat(name+"_emit_copy_short", length, offset, retval, dstBase, end, false)
2323 } else {
2324 checkDst(dstBase)
2325 JMP(LabelRef("two_byte_offset_" + name))
2326 }
2327
2328 Label("two_byte_offset_short_" + name)
2329
2330 // Create a length * 4 as early as possible.
2331 length4 := GP32()
2332 MOVL(length.As32(), length4)
2333 SHLL(U8(2), length4)
2334
2335 //if length >= 12 || offset >= 2048 {
2336 CMPL(length.As32(), U8(12))
2337 JAE(LabelRef("emit_copy_three_" + name))
2338 if o.maxOffset >= 2048 {
2339 CMPL(offset.As32(), U32(2048))
2340 JAE(LabelRef("emit_copy_three_" + name))
2341 }
2342 // Emit the remaining copy, encoded as 2 bytes.
2343 // dst[1] = uint8(offset)
2344 // dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1
2345 // Use scale and displacement to shift and subtract values from length.
2346 if !o.skipOutput {
2347 LEAL(Mem{Base: length4, Disp: -(4 << 2) | tagCopy1}, length4.As32())
2348 MOVB(offset.As8(), Mem{Base: dstBase, Disp: 1}) // Store offset lower byte
2349 SHRL(U8(8), offset.As32()) // Remove lower
2350 SHLL(U8(5), offset.As32()) // Shift back up
2351 ORL(offset.As32(), length4.As32()) // OR result
2352 MOVB(length4.As8(), Mem{Base: dstBase, Disp: 0})
2353 }
2354 if retval != nil {
2355 ADDQ(U8(2), retval) // i += 2
2356 }
2357 ADDQ(U8(2), dstBase) // dst += 2
2358 // return 2
2359 JMP(end)
2360
2361 Label("emit_copy_three_" + name)
2362 // // Emit the remaining copy, encoded as 3 bytes.
2363 // dst[2] = uint8(offset >> 8)
2364 // dst[1] = uint8(offset)
2365 // dst[0] = uint8(length-1)<<2 | tagCopy2
2366
2367 if !o.skipOutput {
2368 LEAL(Mem{Base: length4, Disp: -(1 << 2) | tagCopy2}, length4.As32())
2369 MOVB(length4.As8(), Mem{Base: dstBase})
2370 MOVW(offset.As16(), Mem{Base: dstBase, Disp: 1})
2371 }
2372 // return 3
2373 if retval != nil {
2374 ADDQ(U8(3), retval) // i += 3
2375 }
2376 ADDQ(U8(3), dstBase) // dst += 3
2377 JMP(end)
2378 }
2379
2380 // func memmove(to, from unsafe.Pointer, n uintptr)
2381 // src and dst may not overlap.
2382 // Non AVX uses 2 GP register, 16 SSE2 registers.
2383 // AVX uses 4 GP registers 16 AVX/SSE registers.
2384 // All passed registers may be updated.
2385 // Length must be 1 -> 64 bytes
2386 func (o options) genMemMoveShort(name string, dst, src, length reg.GPVirtual, end LabelRef) {
2387 if o.skipOutput {
2388 JMP(end)
2389 return
2390 }
2391 Comment("genMemMoveShort")
2392 AX, CX := GP64(), GP64()
2393 name += "_memmove_"
2394
2395 // Only enable if length can be 0.
2396 if false {
2397 TESTQ(length, length)
2398 JEQ(end)
2399 }
2400 assert(func(ok LabelRef) {
2401 CMPQ(length, U8(64))
2402 JBE(ok)
2403 })
2404 assert(func(ok LabelRef) {
2405 TESTQ(length, length)
2406 JNZ(ok)
2407 })
2408
2409 if o.outputMargin <= 3 {
2410 CMPQ(length, U8(3))
2411 JB(LabelRef(name + "move_1or2"))
2412 JE(LabelRef(name + "move_3"))
2413 } else if o.outputMargin >= 4 && o.outputMargin < 8 {
2414 CMPQ(length, U8(4))
2415 JBE(LabelRef(name + "move_4"))
2416 }
2417 if o.outputMargin <= 7 {
2418 CMPQ(length, U8(8))
2419 JB(LabelRef(name + "move_4through7"))
2420 } else if o.outputMargin >= 8 {
2421 CMPQ(length, U8(8))
2422 JBE(LabelRef(name + "move_8"))
2423 }
2424 CMPQ(length, U8(16))
2425 JBE(LabelRef(name + "move_8through16"))
2426 CMPQ(length, U8(32))
2427 JBE(LabelRef(name + "move_17through32"))
2428 if debug {
2429 CMPQ(length, U8(64))
2430 JBE(LabelRef(name + "move_33through64"))
2431 INT(U8(3))
2432 }
2433 JMP(LabelRef(name + "move_33through64"))
2434
2435 //genMemMoveLong(name, dst, src, length, end)
2436
2437 if o.outputMargin <= 3 {
2438 Label(name + "move_1or2")
2439 MOVB(Mem{Base: src}, AX.As8())
2440 MOVB(Mem{Base: src, Disp: -1, Index: length, Scale: 1}, CX.As8())
2441 MOVB(AX.As8(), Mem{Base: dst})
2442 MOVB(CX.As8(), Mem{Base: dst, Disp: -1, Index: length, Scale: 1})
2443 JMP(end)
2444
2445 Label(name + "move_3")
2446 MOVW(Mem{Base: src}, AX.As16())
2447 MOVB(Mem{Base: src, Disp: 2}, CX.As8())
2448 MOVW(AX.As16(), Mem{Base: dst})
2449 MOVB(CX.As8(), Mem{Base: dst, Disp: 2})
2450 JMP(end)
2451 }
2452
2453 if o.outputMargin >= 4 && o.outputMargin < 8 {
2454 // Use single move.
2455 Label(name + "move_4")
2456 MOVL(Mem{Base: src}, AX.As32())
2457 MOVL(AX.As32(), Mem{Base: dst})
2458 JMP(end)
2459 }
2460 if o.outputMargin < 8 {
2461 Label(name + "move_4through7")
2462 MOVL(Mem{Base: src}, AX.As32())
2463 MOVL(Mem{Base: src, Disp: -4, Index: length, Scale: 1}, CX.As32())
2464 MOVL(AX.As32(), Mem{Base: dst})
2465 MOVL(CX.As32(), Mem{Base: dst, Disp: -4, Index: length, Scale: 1})
2466 JMP(end)
2467 } else {
2468 // Use single move.
2469 Label(name + "move_8")
2470 MOVQ(Mem{Base: src}, AX)
2471 MOVQ(AX, Mem{Base: dst})
2472 JMP(end)
2473 }
2474
2475 Label(name + "move_8through16")
2476 MOVQ(Mem{Base: src}, AX)
2477 MOVQ(Mem{Base: src, Disp: -8, Index: length, Scale: 1}, CX)
2478 MOVQ(AX, Mem{Base: dst})
2479 MOVQ(CX, Mem{Base: dst, Disp: -8, Index: length, Scale: 1})
2480 JMP(end)
2481
2482 Label(name + "move_17through32")
2483 X0, X1, X2, X3 := XMM(), XMM(), XMM(), XMM()
2484
2485 MOVOU(Mem{Base: src}, X0)
2486 MOVOU(Mem{Base: src, Disp: -16, Index: length, Scale: 1}, X1)
2487 MOVOU(X0, Mem{Base: dst})
2488 MOVOU(X1, Mem{Base: dst, Disp: -16, Index: length, Scale: 1})
2489 JMP(end)
2490
2491 Label(name + "move_33through64")
2492 MOVOU(Mem{Base: src}, X0)
2493 MOVOU(Mem{Base: src, Disp: 16}, X1)
2494 MOVOU(Mem{Base: src, Disp: -32, Index: length, Scale: 1}, X2)
2495 MOVOU(Mem{Base: src, Disp: -16, Index: length, Scale: 1}, X3)
2496 MOVOU(X0, Mem{Base: dst})
2497 MOVOU(X1, Mem{Base: dst, Disp: 16})
2498 MOVOU(X2, Mem{Base: dst, Disp: -32, Index: length, Scale: 1})
2499 MOVOU(X3, Mem{Base: dst, Disp: -16, Index: length, Scale: 1})
2500 JMP(end)
2501 }
2502
2503 // func genMemMoveLong(to, from unsafe.Pointer, n uintptr)
2504 // src and dst may not overlap.
2505 // length must be >= 64 bytes.
2506 // Non AVX uses 2 GP register, 16 SSE2 registers.
2507 // AVX uses 4 GP registers 16 AVX/SSE registers.
2508 // All passed registers may be updated.
2509 func (o options) genMemMoveLong(name string, dst, src, length reg.GPVirtual, end LabelRef) {
2510 if o.skipOutput {
2511 JMP(end)
2512 return
2513 }
2514 Comment("genMemMoveLong")
2515 name += "large_"
2516
2517 assert(func(ok LabelRef) {
2518 CMPQ(length, U8(64))
2519 JAE(ok)
2520 })
2521
2522 // These are disabled.
2523 // AVX is ever so slightly faster, but it is disabled for simplicity.
2524 const branchLoops = false
2525 const avx = false && branchLoops
2526 if branchLoops {
2527 CMPQ(length, U8(128))
2528 JBE(LabelRef(name + "move_65through128"))
2529 CMPQ(length, U32(256))
2530 JBE(LabelRef(name + "move_129through256"))
2531 if avx {
2532 JMP(LabelRef(name + "avxUnaligned"))
2533 } else {
2534 JMP(LabelRef(name + "forward_sse"))
2535 }
2536
2537 X0, X1, X2, X3, X4, X5, X6, X7 := XMM(), XMM(), XMM(), XMM(), XMM(), XMM(), XMM(), XMM()
2538 X8, X9, X10, X11, X12, X13, X14, X15 := XMM(), XMM(), XMM(), XMM(), XMM(), XMM(), XMM(), XMM()
2539 Label(name + "move_65through128")
2540 MOVOU(Mem{Base: src}, X0)
2541 MOVOU(Mem{Base: src, Disp: 16}, X1)
2542 MOVOU(Mem{Base: src, Disp: 32}, X2)
2543 MOVOU(Mem{Base: src, Disp: 48}, X3)
2544 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -64}, X12)
2545 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -48}, X13)
2546 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -32}, X14)
2547 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -16}, X15)
2548 MOVOU(X0, Mem{Base: dst})
2549 MOVOU(X1, Mem{Base: dst, Disp: 16})
2550 MOVOU(X2, Mem{Base: dst, Disp: 32})
2551 MOVOU(X3, Mem{Base: dst, Disp: 48})
2552 MOVOU(X12, Mem{Base: dst, Index: length, Scale: 1, Disp: -64})
2553 MOVOU(X13, Mem{Base: dst, Index: length, Scale: 1, Disp: -48})
2554 MOVOU(X14, Mem{Base: dst, Index: length, Scale: 1, Disp: -32})
2555 MOVOU(X15, Mem{Base: dst, Index: length, Scale: 1, Disp: -16})
2556 JMP(end)
2557
2558 Label(name + "move_129through256")
2559 MOVOU(Mem{Base: src}, X0)
2560 MOVOU(Mem{Base: src, Disp: 16}, X1)
2561 MOVOU(Mem{Base: src, Disp: 32}, X2)
2562 MOVOU(Mem{Base: src, Disp: 48}, X3)
2563 MOVOU(Mem{Base: src, Disp: 64}, X4)
2564 MOVOU(Mem{Base: src, Disp: 80}, X5)
2565 MOVOU(Mem{Base: src, Disp: 96}, X6)
2566 MOVOU(Mem{Base: src, Disp: 112}, X7)
2567 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -128}, X8)
2568 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -112}, X9)
2569 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -96}, X10)
2570 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -80}, X11)
2571 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -64}, X12)
2572 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -48}, X13)
2573 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -32}, X14)
2574 MOVOU(Mem{Base: src, Index: length, Scale: 1, Disp: -16}, X15)
2575 MOVOU(X0, Mem{Base: dst})
2576 MOVOU(X1, Mem{Base: dst, Disp: 16})
2577 MOVOU(X2, Mem{Base: dst, Disp: 32})
2578 MOVOU(X3, Mem{Base: dst, Disp: 48})
2579 MOVOU(X4, Mem{Base: dst, Disp: 64})
2580 MOVOU(X5, Mem{Base: dst, Disp: 80})
2581 MOVOU(X6, Mem{Base: dst, Disp: 96})
2582 MOVOU(X7, Mem{Base: dst, Disp: 112})
2583 MOVOU(X8, Mem{Base: dst, Index: length, Scale: 1, Disp: -128})
2584 MOVOU(X9, Mem{Base: dst, Index: length, Scale: 1, Disp: -112})
2585 MOVOU(X10, Mem{Base: dst, Index: length, Scale: 1, Disp: -96})
2586 MOVOU(X11, Mem{Base: dst, Index: length, Scale: 1, Disp: -80})
2587 MOVOU(X12, Mem{Base: dst, Index: length, Scale: 1, Disp: -64})
2588 MOVOU(X13, Mem{Base: dst, Index: length, Scale: 1, Disp: -48})
2589 MOVOU(X14, Mem{Base: dst, Index: length, Scale: 1, Disp: -32})
2590 MOVOU(X15, Mem{Base: dst, Index: length, Scale: 1, Disp: -16})
2591 JMP(end)
2592 if avx {
2593 Label(name + "avxUnaligned")
2594 AX, CX, R8, R10 := GP64(), GP64(), GP64(), GP64()
2595 // Memory layout on the source side
2596 // src CX
2597 // |<---------length before correction--------->|
2598 // | |<--length corrected-->| |
2599 // | | |<--- AX --->|
2600 // |<-R11->| |<-128 bytes->|
2601 // +----------------------------------------+
2602 // | Head | Body | Tail |
2603 // +-------+------------------+-------------+
2604 // ^ ^ ^
2605 // | | |
2606 // Save head into Y4 Save tail into X5..X12
2607 // |
2608 // src+R11, where R11 = ((dst & -32) + 32) - dst
2609 // Algorithm:
2610 // 1. Unaligned save of the tail's 128 bytes
2611 // 2. Unaligned save of the head's 32 bytes
2612 // 3. Destination-aligned copying of body (128 bytes per iteration)
2613 // 4. Put head on the new place
2614 // 5. Put the tail on the new place
2615 // It can be important to satisfy processor's pipeline requirements for
2616 // small sizes as the cost of unaligned memory region copying is
2617 // comparable with the cost of main loop. So code is slightly messed there.
2618 // There is more clean implementation of that algorithm for bigger sizes
2619 // where the cost of unaligned part copying is negligible.
2620 // You can see it after gobble_big_data_fwd label.
2621 Y0, Y1, Y2, Y3, Y4 := YMM(), YMM(), YMM(), YMM(), YMM()
2622
2623 LEAQ(Mem{Base: src, Index: length, Scale: 1}, CX)
2624 MOVQ(dst, R10)
2625 // CX points to the end of buffer so we need go back slightly. We will use negative offsets there.
2626 MOVOU(Mem{Base: CX, Disp: -0x80}, X5)
2627 MOVOU(Mem{Base: CX, Disp: -0x70}, X6)
2628 MOVQ(U32(0x80), AX)
2629
2630 // Align destination address
2631 ANDQ(U32(0xffffffe0), dst)
2632 ADDQ(U8(32), dst)
2633 // Continue tail saving.
2634 MOVOU(Mem{Base: CX, Disp: -0x60}, X7)
2635 MOVOU(Mem{Base: CX, Disp: -0x50}, X8)
2636 // Make R8 delta between aligned and unaligned destination addresses.
2637 MOVQ(dst, R8)
2638 SUBQ(R10, R8)
2639 // Continue tail saving.
2640 MOVOU(Mem{Base: CX, Disp: -0x40}, X9)
2641 MOVOU(Mem{Base: CX, Disp: -0x30}, X10)
2642 // Let's make bytes-to-copy value adjusted as we've prepared unaligned part for copying.
2643 SUBQ(R8, length)
2644 // Continue tail saving.
2645 MOVOU(Mem{Base: CX, Disp: -0x20}, X11)
2646 MOVOU(Mem{Base: CX, Disp: -0x10}, X12)
2647 // The tail will be put on its place after main body copying.
2648 // It's time for the unaligned heading part.
2649 VMOVDQU(Mem{Base: src}, Y4)
2650 // Adjust source address to point past head.
2651 ADDQ(R8, src)
2652 SUBQ(AX, length)
2653
2654 // Aligned memory copying there
2655 Label(name + "gobble_128_loop")
2656 VMOVDQU(Mem{Base: src}, Y0)
2657 VMOVDQU(Mem{Base: src, Disp: 0x20}, Y1)
2658 VMOVDQU(Mem{Base: src, Disp: 0x40}, Y2)
2659 VMOVDQU(Mem{Base: src, Disp: 0x60}, Y3)
2660 ADDQ(AX, src)
2661 VMOVDQA(Y0, Mem{Base: dst})
2662 VMOVDQA(Y1, Mem{Base: dst, Disp: 0x20})
2663 VMOVDQA(Y2, Mem{Base: dst, Disp: 0x40})
2664 VMOVDQA(Y3, Mem{Base: dst, Disp: 0x60})
2665 ADDQ(AX, dst)
2666 SUBQ(AX, length)
2667 JA(LabelRef(name + "gobble_128_loop"))
2668 // Now we can store unaligned parts.
2669 ADDQ(AX, length)
2670 ADDQ(dst, length)
2671 VMOVDQU(Y4, Mem{Base: R10})
2672 VZEROUPPER()
2673 MOVOU(X5, Mem{Base: length, Disp: -0x80})
2674 MOVOU(X6, Mem{Base: length, Disp: -0x70})
2675 MOVOU(X7, Mem{Base: length, Disp: -0x60})
2676 MOVOU(X8, Mem{Base: length, Disp: -0x50})
2677 MOVOU(X9, Mem{Base: length, Disp: -0x40})
2678 MOVOU(X10, Mem{Base: length, Disp: -0x30})
2679 MOVOU(X11, Mem{Base: length, Disp: -0x20})
2680 MOVOU(X12, Mem{Base: length, Disp: -0x10})
2681 JMP(end)
2682
2683 return
2684 }
2685 }
2686
2687 // Store start and end for sse_tail
2688 Label(name + "forward_sse")
2689 X0, X1, X2, X3, X4, X5 := XMM(), XMM(), XMM(), XMM(), XMM(), XMM()
2690 // X6, X7 := XMM(), XMM()
2691 //X8, X9, X10, X11 := XMM(), XMM(), XMM(), XMM()
2692
2693 MOVOU(Mem{Base: src}, X0)
2694 MOVOU(Mem{Base: src, Disp: 16}, X1)
2695 MOVOU(Mem{Base: src, Disp: -32, Index: length, Scale: 1}, X2)
2696 MOVOU(Mem{Base: src, Disp: -16, Index: length, Scale: 1}, X3)
2697
2698 // forward (only)
2699 dstAlign := GP64()
2700 bigLoops := GP64()
2701 MOVQ(length, bigLoops)
2702 SHRQ(U8(5), bigLoops) // bigLoops = length / 32
2703
2704 MOVQ(dst, dstAlign)
2705 ANDL(U32(31), dstAlign.As32())
2706 srcOff := GP64()
2707 MOVQ(U32(64), srcOff)
2708 SUBQ(dstAlign, srcOff)
2709
2710 // Move 32 bytes/loop
2711 DECQ(bigLoops)
2712 JA(LabelRef(name + "forward_sse_loop_32"))
2713
2714 // Can be moved inside loop for less regs.
2715 srcPos := GP64()
2716 LEAQ(Mem{Disp: -32, Base: src, Scale: 1, Index: srcOff}, srcPos)
2717 dstPos := GP64()
2718 LEAQ(Mem{Disp: -32, Base: dst, Scale: 1, Index: srcOff}, dstPos)
2719
2720 Label(name + "big_loop_back")
2721
2722 MOVOU(Mem{Disp: 0, Base: srcPos}, X4)
2723 MOVOU(Mem{Disp: 16, Base: srcPos}, X5)
2724
2725 MOVOA(X4, Mem{Disp: 0, Base: dstPos})
2726 MOVOA(X5, Mem{Disp: 16, Base: dstPos})
2727 ADDQ(U8(32), dstPos)
2728 ADDQ(U8(32), srcPos)
2729 ADDQ(U8(32), srcOff) // This could be outside the loop, but we lose a reg if we do.
2730 DECQ(bigLoops)
2731 JNA(LabelRef(name + "big_loop_back"))
2732
2733 Label(name + "forward_sse_loop_32")
2734 MOVOU(Mem{Disp: -32, Base: src, Scale: 1, Index: srcOff}, X4)
2735 MOVOU(Mem{Disp: -16, Base: src, Scale: 1, Index: srcOff}, X5)
2736 MOVOA(X4, Mem{Disp: -32, Base: dst, Scale: 1, Index: srcOff})
2737 MOVOA(X5, Mem{Disp: -16, Base: dst, Scale: 1, Index: srcOff})
2738 ADDQ(U8(32), srcOff)
2739 CMPQ(length, srcOff)
2740 JAE(LabelRef(name + "forward_sse_loop_32"))
2741
2742 // sse_tail patches up the beginning and end of the transfer.
2743 MOVOU(X0, Mem{Base: dst, Disp: 0})
2744 MOVOU(X1, Mem{Base: dst, Disp: 16})
2745 MOVOU(X2, Mem{Base: dst, Disp: -32, Index: length, Scale: 1})
2746 MOVOU(X3, Mem{Base: dst, Disp: -16, Index: length, Scale: 1})
2747
2748 JMP(end)
2749 return
2750 }
2751
2752 // genMatchLen generates standalone matchLen.
2753 func (o options) genMatchLen() {
2754 TEXT("matchLen", NOSPLIT, "func(a, b []byte) int")
2755 Doc("matchLen returns how many bytes match in a and b", "",
2756 "It assumes that:",
2757 " len(a) <= len(b)", "")
2758 Pragma("noescape")
2759
2760 aBase, bBase, length := GP64(), GP64(), GP64()
2761
2762 Load(Param("a").Base(), aBase)
2763 Load(Param("b").Base(), bBase)
2764 Load(Param("a").Len(), length)
2765 l := o.matchLen("standalone", aBase, bBase, length, LabelRef("gen_match_len_end"))
2766 Label("gen_match_len_end")
2767 if o.avx2 {
2768 VZEROUPPER()
2769 }
2770 Store(l.As64(), ReturnIndex(0))
2771 RET()
2772 }
2773
2774 // matchLen returns the number of matching bytes of a and b.
2775 // len is the maximum number of bytes to match.
2776 // Will jump to end when done and returns the length.
2777 // Uses 2 GP registers.
2778 func (o options) matchLen(name string, a, b, len reg.GPVirtual, end LabelRef) reg.GPVirtual {
2779 Comment("matchLen")
2780 tmp, matched := GP64(), GP32()
2781 XORL(matched, matched)
2782 if o.avx2 {
2783 // Not faster...
2784 o.matchLenAVX2(name+"Avx2", a, b, len, LabelRef("avx2_continue_"+name), end, matched)
2785 }
2786 Label("avx2_continue_" + name)
2787
2788 Label("matchlen_loopback_16_" + name)
2789 tmp2 := GP64()
2790 CMPL(len.As32(), U8(16))
2791 JB(LabelRef("matchlen_match8_" + name))
2792 MOVQ(Mem{Base: a, Index: matched, Scale: 1}, tmp)
2793 MOVQ(Mem{Base: a, Index: matched, Scale: 1, Disp: 8}, tmp2)
2794 XORQ(Mem{Base: b, Index: matched, Scale: 1}, tmp)
2795 JNZ(LabelRef("matchlen_bsf_8_" + name))
2796 XORQ(Mem{Base: b, Index: matched, Scale: 1, Disp: 8}, tmp2)
2797 JNZ(LabelRef("matchlen_bsf_16" + name))
2798 // All 8 byte matched, update and loop.
2799 LEAL(Mem{Base: len, Disp: -16}, len.As32())
2800 LEAL(Mem{Base: matched, Disp: 16}, matched)
2801 JMP(LabelRef("matchlen_loopback_16_" + name))
2802
2803 Label("matchlen_bsf_16" + name)
2804 // Not all match.
2805 Comment("#ifdef GOAMD64_v3")
2806 // 2016 BMI :TZCNT r64, r64 L: 0.57ns= 2.0c T: 0.29ns= 1.00c
2807 // 315 AMD64 :BSF r64, r64 L: 0.88ns= 3.1c T: 0.86ns= 3.00c
2808 TZCNTQ(tmp2, tmp2)
2809 Comment("#else")
2810 BSFQ(tmp2, tmp2)
2811 Comment("#endif")
2812
2813 SARQ(U8(3), tmp2)
2814 LEAL(Mem{Base: matched, Index: tmp2, Scale: 1, Disp: 8}, matched)
2815 JMP(end)
2816
2817 Label("matchlen_match8_" + name)
2818 CMPL(len.As32(), U8(8))
2819 JB(LabelRef("matchlen_match4_" + name))
2820 MOVQ(Mem{Base: a, Index: matched, Scale: 1}, tmp)
2821 XORQ(Mem{Base: b, Index: matched, Scale: 1}, tmp)
2822 JNZ(LabelRef("matchlen_bsf_8_" + name))
2823 // All 8 byte matched, update and loop.
2824 LEAL(Mem{Base: len, Disp: -8}, len.As32())
2825 LEAL(Mem{Base: matched, Disp: 8}, matched)
2826 JMP(LabelRef("matchlen_match4_" + name))
2827 Label("matchlen_bsf_8_" + name)
2828
2829 // Not all match.
2830 Comment("#ifdef GOAMD64_v3")
2831 // 2016 BMI :TZCNT r64, r64 L: 0.57ns= 2.0c T: 0.29ns= 1.00c
2832 // 315 AMD64 :BSF r64, r64 L: 0.88ns= 3.1c T: 0.86ns= 3.00c
2833 TZCNTQ(tmp, tmp)
2834 Comment("#else")
2835 BSFQ(tmp, tmp)
2836 Comment("#endif")
2837
2838 SARQ(U8(3), tmp)
2839 LEAL(Mem{Base: matched, Index: tmp, Scale: 1}, matched)
2840 JMP(end)
2841
2842 // Less than 8 bytes left.
2843 // Test 4 bytes...
2844 Label("matchlen_match4_" + name)
2845 CMPL(len.As32(), U8(4))
2846 JB(LabelRef("matchlen_match2_" + name))
2847 MOVL(Mem{Base: a, Index: matched, Scale: 1}, tmp.As32())
2848 CMPL(Mem{Base: b, Index: matched, Scale: 1}, tmp.As32())
2849 JNE(LabelRef("matchlen_match2_" + name))
2850 LEAL(Mem{Base: len.As32(), Disp: -4}, len.As32())
2851 LEAL(Mem{Base: matched, Disp: 4}, matched)
2852
2853 // Test 2 bytes...
2854 Label("matchlen_match2_" + name)
2855 CMPL(len.As32(), U8(1))
2856 // If we don't have 1, branch appropriately
2857 JE(LabelRef("matchlen_match1_" + name))
2858 JB(end)
2859 // 2 or 3
2860 MOVW(Mem{Base: a, Index: matched, Scale: 1}, tmp.As16())
2861 CMPW(Mem{Base: b, Index: matched, Scale: 1}, tmp.As16())
2862 JNE(LabelRef("matchlen_match1_" + name))
2863 LEAL(Mem{Base: matched, Disp: 2}, matched)
2864 SUBL(U8(2), len.As32())
2865 JZ(end)
2866
2867 // Test 1 byte...
2868 Label("matchlen_match1_" + name)
2869 MOVB(Mem{Base: a, Index: matched, Scale: 1}, tmp.As8())
2870 CMPB(Mem{Base: b, Index: matched, Scale: 1}, tmp.As8())
2871 JNE(end)
2872 LEAL(Mem{Base: matched, Disp: 1}, matched)
2873 JMP(end)
2874 return matched
2875 }
2876
2877 // matchLen returns the number of matching bytes of a and b.
2878 // len is the maximum number of bytes to match.
2879 // Will jump to end when done and returns the length.
2880 // Uses 3 GP registers.
2881 // It is better on longer matches.
2882 func (o options) matchLenAVX2(name string, a, b, len reg.GPVirtual, cont, end LabelRef, dst reg.GPVirtual) {
2883 Comment("matchLenAVX2")
2884
2885 equalMaskBits := GP64()
2886 Label(name + "loop")
2887 {
2888 CMPQ(len, U8(32))
2889 JB(cont)
2890 Comment("load 32 bytes into YMM registers")
2891 adata := YMM()
2892 bdata := YMM()
2893 equalMaskBytes := YMM()
2894 VMOVDQU(Mem{Base: a}, adata)
2895 VMOVDQU(Mem{Base: b}, bdata)
2896 Comment("compare bytes in adata and bdata, like 'bytewise XNOR'",
2897 "if the byte is the same in adata and bdata, VPCMPEQB will store 0xFF in the same position in equalMaskBytes")
2898 VPCMPEQB(adata, bdata, equalMaskBytes)
2899 Comment("like convert byte to bit, store equalMaskBytes into general reg")
2900 VPMOVMSKB(equalMaskBytes, equalMaskBits.As32())
2901 CMPL(equalMaskBits.As32(), U32(0xffffffff))
2902 JNE(LabelRef(name + "cal_prefix"))
2903 ADDQ(U8(32), a)
2904 ADDQ(U8(32), b)
2905 ADDL(U8(32), dst)
2906 SUBQ(U8(32), len)
2907 JZ(end)
2908 JMP(LabelRef(name + "loop"))
2909 }
2910
2911 Label(name + "cal_prefix")
2912 {
2913 NOTQ(equalMaskBits)
2914 if o.bmi1 {
2915 TZCNTQ(equalMaskBits, equalMaskBits)
2916 } else {
2917 BSFQ(equalMaskBits, equalMaskBits)
2918 }
2919 ADDL(equalMaskBits.As32(), dst)
2920 }
2921 JMP(end)
2922 return
2923 }
2924
2925 func (o options) cvtLZ4BlockAsm(lz4s bool) {
2926 snap := "Asm"
2927 name := "lz4_s2_"
2928 srcAlgo := "LZ4"
2929 dstAlgo := "S2"
2930 if o.snappy {
2931 snap = "SnappyAsm"
2932 name = "lz4_snappy_"
2933 dstAlgo = "Snappy"
2934 }
2935 if lz4s {
2936 name = strings.ReplaceAll(name, "lz4", "lz4s")
2937 srcAlgo = "LZ4s"
2938 }
2939 TEXT("cvt"+srcAlgo+"Block"+snap, NOSPLIT, "func(dst, src []byte) (uncompressed int, dstUsed int)")
2940 Doc("cvt"+srcAlgo+"Block converts an "+srcAlgo+" block to "+dstAlgo, "")
2941 Pragma("noescape")
2942 o.outputMargin = 8
2943 o.maxOffset = math.MaxUint16
2944
2945 const (
2946 errCorrupt = -1
2947 errDstTooSmall = -2
2948 )
2949 dst, dstLen, src, srcLen, retval := GP64(), GP64(), GP64(), GP64(), GP64()
2950
2951 // retval = 0
2952 XORQ(retval, retval)
2953
2954 Load(Param("dst").Base(), dst)
2955 Load(Param("dst").Len(), dstLen)
2956 Load(Param("src").Base(), src)
2957 Load(Param("src").Len(), srcLen)
2958 srcEnd, dstEnd := GP64(), GP64()
2959 LEAQ(Mem{Base: src, Index: srcLen, Scale: 1, Disp: 0}, srcEnd)
2960 LEAQ(Mem{Base: dst, Index: dstLen, Scale: 1, Disp: -o.outputMargin}, dstEnd)
2961 lastOffset := GP64()
2962 if !o.snappy {
2963 XORQ(lastOffset, lastOffset)
2964 }
2965
2966 checkSrc := func(reg reg.GPVirtual) {
2967 if debug {
2968 name := fmt.Sprintf(name+"ok_%d", rand.Int31())
2969
2970 CMPQ(reg, srcEnd)
2971 JB(LabelRef(name))
2972 JMP(LabelRef(name + "corrupt"))
2973 Label(name)
2974 } else {
2975 CMPQ(reg, srcEnd)
2976 JAE(LabelRef(name + "corrupt"))
2977 }
2978 }
2979 checkDst := func(reg reg.GPVirtual) {
2980 CMPQ(reg, dstEnd)
2981 JAE(LabelRef(name + "dstfull"))
2982 }
2983
2984 var lz4MinMatch = 4
2985 if lz4s {
2986 lz4MinMatch = 3
2987 }
2988
2989 Label(name + "loop")
2990 checkSrc(src)
2991 checkDst(dst)
2992 token := GP64()
2993 MOVBQZX(Mem{Base: src}, token)
2994 ll, ml := GP64(), GP64()
2995 MOVQ(token, ll)
2996 MOVQ(token, ml)
2997 SHRQ(U8(4), ll)
2998 ANDQ(U8(0xf), ml)
2999
3000 // If upper nibble is 15, literal length is extended
3001 {
3002 CMPQ(token, U8(0xf0))
3003 JB(LabelRef(name + "ll_end"))
3004 Label(name + "ll_loop")
3005 INCQ(src) // s++
3006 checkSrc(src)
3007 val := GP64()
3008 MOVBQZX(Mem{Base: src}, val)
3009 ADDQ(val, ll)
3010 CMPQ(val, U8(255))
3011 JEQ(LabelRef(name + "ll_loop"))
3012 Label(name + "ll_end")
3013 }
3014
3015 // if s+ll >= len(src)
3016 endLits := GP64()
3017 LEAQ(Mem{Base: src, Index: ll, Scale: 1}, endLits)
3018 ADDQ(U8(lz4MinMatch), ml)
3019 checkSrc(endLits)
3020 INCQ(src) // s++
3021 INCQ(endLits)
3022 TESTQ(ll, ll)
3023 JZ(LabelRef(name + "lits_done"))
3024 {
3025 dstEnd := GP64()
3026 LEAQ(Mem{Base: dst, Index: ll, Scale: 1}, dstEnd)
3027 checkDst(dstEnd)
3028 o.outputMargin++
3029 ADDQ(ll, retval)
3030 o.emitLiteral(strings.TrimRight(name, "_"), ll, nil, dst, src, LabelRef(name+"lits_emit_done"), true)
3031 o.outputMargin--
3032 Label(name + "lits_emit_done")
3033 MOVQ(endLits, src)
3034 }
3035 Label(name + "lits_done")
3036 // if s == len(src) && ml == lz4MinMatch
3037 CMPQ(src, srcEnd)
3038 JNE(LabelRef(name + "match"))
3039 CMPQ(ml, U8(lz4MinMatch))
3040 JEQ(LabelRef(name + "done"))
3041 JMP(LabelRef(name + "corrupt"))
3042
3043 Label(name + "match")
3044 if lz4s {
3045 CMPQ(ml, U8(lz4MinMatch))
3046 JEQ(LabelRef(name + "loop"))
3047 }
3048 // if s >= len(src)-2 {
3049 end := GP64()
3050 LEAQ(Mem{Base: src, Disp: 2}, end)
3051 checkSrc(end)
3052 offset := GP64()
3053 MOVWQZX(Mem{Base: src}, offset)
3054 MOVQ(end, src) // s = s + 2
3055
3056 if debug {
3057 // if offset == 0 {
3058 TESTQ(offset, offset)
3059 JNZ(LabelRef(name + "c1"))
3060 JMP(LabelRef(name + "corrupt"))
3061
3062 Label(name + "c1")
3063
3064 // if int(offset) > uncompressed {
3065 CMPQ(offset, retval)
3066 JB(LabelRef(name + "c2"))
3067 JMP(LabelRef(name + "corrupt"))
3068
3069 Label(name + "c2")
3070
3071 } else {
3072 // if offset == 0 {
3073 TESTQ(offset, offset)
3074 JZ(LabelRef(name + "corrupt"))
3075
3076 // if int(offset) > uncompressed {
3077 CMPQ(offset, retval)
3078 JA(LabelRef(name + "corrupt"))
3079 }
3080
3081 // if ml == lz4MinMatch+15 {
3082 {
3083 CMPQ(ml, U8(lz4MinMatch+15))
3084 JNE(LabelRef(name + "ml_done"))
3085
3086 Label(name + "ml_loop")
3087 val := GP64()
3088 MOVBQZX(Mem{Base: src}, val)
3089 INCQ(src) // s++
3090 ADDQ(val, ml) // ml += val
3091 checkSrc(src)
3092 CMPQ(val, U8(255))
3093 JEQ(LabelRef(name + "ml_loop"))
3094 }
3095 Label(name + "ml_done")
3096
3097 // uncompressed += ml
3098 ADDQ(ml, retval)
3099 if !o.snappy {
3100 CMPQ(offset, lastOffset)
3101 JNE(LabelRef(name + "docopy"))
3102 // Offsets can only be 16 bits
3103 {
3104 // emitRepeat16(dst[d:], offset, ml)
3105 o.emitRepeat("lz4_s2", ml, offset, nil, dst, LabelRef(name+"loop"), false)
3106 }
3107 }
3108 Label(name + "docopy")
3109 {
3110 // emitCopy16(dst[d:], offset, ml)
3111 if !o.snappy {
3112 MOVQ(offset, lastOffset)
3113 }
3114 o.emitCopy("lz4_s2", ml, offset, nil, dst, dstEnd, LabelRef(name+"loop"))
3115 }
3116
3117 Label(name + "done")
3118 {
3119 tmp := GP64()
3120 Load(Param("dst").Base(), tmp)
3121 SUBQ(tmp, dst)
3122 Store(retval, ReturnIndex(0))
3123 Store(dst, ReturnIndex(1))
3124 RET()
3125 }
3126 Label(name + "corrupt")
3127 {
3128 tmp := GP64()
3129 if debug {
3130 tmp := GP64()
3131 Load(Param("dst").Base(), tmp)
3132 SUBQ(tmp, dst)
3133 Store(dst, ReturnIndex(1))
3134 }
3135 XORQ(tmp, tmp)
3136 LEAQ(Mem{Base: tmp, Disp: errCorrupt}, retval)
3137 Store(retval, ReturnIndex(0))
3138 RET()
3139 }
3140
3141 Label(name + "dstfull")
3142 {
3143 tmp := GP64()
3144 XORQ(tmp, tmp)
3145 LEAQ(Mem{Base: tmp, Disp: errDstTooSmall}, retval)
3146 Store(retval, ReturnIndex(0))
3147 RET()
3148 }
3149 }