3 // Copyright 2018 The Go Authors. All rights reserved.
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file.
11 // ----------------------- //
12 // bits.LeadingZeros //
13 // ----------------------- //
15 func LeadingZeros(n uint) int {
18 // arm:"CLZ" arm64:"CLZ"
21 return bits.LeadingZeros(n)
24 func LeadingZeros64(n uint64) int {
27 // arm:"CLZ" arm64:"CLZ"
30 return bits.LeadingZeros64(n)
33 func LeadingZeros32(n uint32) int {
34 // amd64:"BSRQ","LEAQ",-"CMOVQEQ"
36 // arm:"CLZ" arm64:"CLZW"
39 return bits.LeadingZeros32(n)
42 func LeadingZeros16(n uint16) int {
43 // amd64:"BSRL","LEAL",-"CMOVQEQ"
45 // arm:"CLZ" arm64:"CLZ"
48 return bits.LeadingZeros16(n)
51 func LeadingZeros8(n uint8) int {
52 // amd64:"BSRL","LEAL",-"CMOVQEQ"
54 // arm:"CLZ" arm64:"CLZ"
57 return bits.LeadingZeros8(n)
64 func Len(n uint) int {
67 // arm:"CLZ" arm64:"CLZ"
73 func Len64(n uint64) int {
76 // arm:"CLZ" arm64:"CLZ"
79 // ppc64le:"SUBC","CNTLZD"
80 // ppc64:"SUBC","CNTLZD"
84 func SubFromLen64(n uint64) int {
85 // ppc64le:"CNTLZD",-"SUBC"
86 // ppc64:"CNTLZD",-"SUBC"
87 return 64 - bits.Len64(n)
90 func Len32(n uint32) int {
91 // amd64:"BSRQ","LEAQ",-"CMOVQEQ"
93 // arm:"CLZ" arm64:"CLZ"
99 func Len16(n uint16) int {
100 // amd64:"BSRL","LEAL",-"CMOVQEQ"
102 // arm:"CLZ" arm64:"CLZ"
108 func Len8(n uint8) int {
109 // amd64:"BSRL","LEAL",-"CMOVQEQ"
111 // arm:"CLZ" arm64:"CLZ"
117 // -------------------- //
119 // -------------------- //
121 // TODO(register args) Restore a m d 6 4 :.*x86HasPOPCNT when only one ABI is tested.
122 func OnesCount(n uint) int {
124 // arm64:"VCNT","VUADDLV"
129 return bits.OnesCount(n)
132 func OnesCount64(n uint64) int {
134 // arm64:"VCNT","VUADDLV"
139 return bits.OnesCount64(n)
142 func OnesCount32(n uint32) int {
144 // arm64:"VCNT","VUADDLV"
149 return bits.OnesCount32(n)
152 func OnesCount16(n uint16) int {
154 // arm64:"VCNT","VUADDLV"
159 return bits.OnesCount16(n)
162 func OnesCount8(n uint8) int {
167 return bits.OnesCount8(n)
170 // ----------------------- //
171 // bits.ReverseBytes //
172 // ----------------------- //
174 func ReverseBytes(n uint) uint {
178 return bits.ReverseBytes(n)
181 func ReverseBytes64(n uint64) uint64 {
185 return bits.ReverseBytes64(n)
188 func ReverseBytes32(n uint32) uint32 {
192 return bits.ReverseBytes32(n)
195 func ReverseBytes16(n uint16) uint16 {
197 // arm64:"REV16W",-"UBFX",-"ORR"
198 // arm/5:"SLL","SRL","ORR"
201 return bits.ReverseBytes16(n)
204 // --------------------- //
205 // bits.RotateLeft //
206 // --------------------- //
208 func RotateLeft64(n uint64) uint64 {
213 // s390x:"RISBGZ\t[$]0, [$]63, [$]37, "
215 return bits.RotateLeft64(n, 37)
218 func RotateLeft32(n uint32) uint32 {
219 // amd64:"ROLL" 386:"ROLL"
220 // arm:`MOVW\tR[0-9]+@>23`
226 return bits.RotateLeft32(n, 9)
229 func RotateLeft16(n uint16) uint16 {
230 // amd64:"ROLW" 386:"ROLW"
231 return bits.RotateLeft16(n, 5)
234 func RotateLeft8(n uint8) uint8 {
235 // amd64:"ROLB" 386:"ROLB"
236 return bits.RotateLeft8(n, 5)
239 func RotateLeftVariable(n uint, m int) uint {
246 return bits.RotateLeft(n, m)
249 func RotateLeftVariable64(n uint64, m int) uint64 {
256 return bits.RotateLeft64(n, m)
259 func RotateLeftVariable32(n uint32, m int) uint32 {
260 // arm:`MOVW\tR[0-9]+@>R[0-9]+`
267 return bits.RotateLeft32(n, m)
270 // ------------------------ //
271 // bits.TrailingZeros //
272 // ------------------------ //
274 func TrailingZeros(n uint) int {
275 // amd64/v1,amd64/v2:"BSFQ","MOVL\t\\$64","CMOVQEQ"
278 // arm64:"RBIT","CLZ"
280 // ppc64/power8:"ANDN","POPCNTD"
281 // ppc64le/power8:"ANDN","POPCNTD"
282 // ppc64/power9: "CNTTZD"
283 // ppc64le/power9: "CNTTZD"
285 return bits.TrailingZeros(n)
288 func TrailingZeros64(n uint64) int {
289 // amd64/v1,amd64/v2:"BSFQ","MOVL\t\\$64","CMOVQEQ"
291 // arm64:"RBIT","CLZ"
293 // ppc64/power8:"ANDN","POPCNTD"
294 // ppc64le/power8:"ANDN","POPCNTD"
295 // ppc64/power9: "CNTTZD"
296 // ppc64le/power9: "CNTTZD"
298 return bits.TrailingZeros64(n)
301 func TrailingZeros64Subtract(n uint64) int {
302 // ppc64le/power8:"NEG","SUBC","ANDN","POPCNTD"
303 // ppc64le/power9:"SUBC","CNTTZD"
304 return bits.TrailingZeros64(1 - n)
307 func TrailingZeros32(n uint32) int {
308 // amd64/v1,amd64/v2:"BTSQ\\t\\$32","BSFQ"
311 // arm64:"RBITW","CLZW"
312 // s390x:"FLOGR","MOVWZ"
313 // ppc64/power8:"ANDN","POPCNTW"
314 // ppc64le/power8:"ANDN","POPCNTW"
315 // ppc64/power9: "CNTTZW"
316 // ppc64le/power9: "CNTTZW"
318 return bits.TrailingZeros32(n)
321 func TrailingZeros16(n uint16) int {
322 // amd64:"BSFL","BTSL\\t\\$16"
324 // arm:"ORR\t\\$65536","CLZ",-"MOVHU\tR"
325 // arm64:"ORR\t\\$65536","RBITW","CLZW",-"MOVHU\tR",-"RBIT\t",-"CLZ\t"
326 // s390x:"FLOGR","OR\t\\$65536"
327 // ppc64/power8:"POPCNTD","OR\\t\\$65536"
328 // ppc64le/power8:"POPCNTD","OR\\t\\$65536"
329 // ppc64/power9:"CNTTZD","OR\\t\\$65536"
330 // ppc64le/power9:"CNTTZD","OR\\t\\$65536"
332 return bits.TrailingZeros16(n)
335 func TrailingZeros8(n uint8) int {
336 // amd64:"BSFL","BTSL\\t\\$8"
337 // arm:"ORR\t\\$256","CLZ",-"MOVBU\tR"
338 // arm64:"ORR\t\\$256","RBITW","CLZW",-"MOVBU\tR",-"RBIT\t",-"CLZ\t"
339 // s390x:"FLOGR","OR\t\\$256"
341 return bits.TrailingZeros8(n)
344 // IterateBitsNN checks special handling of TrailingZerosNN when the input is known to be non-zero.
346 func IterateBits(n uint) int {
349 // amd64/v1,amd64/v2:"BSFQ",-"CMOVEQ"
351 i += bits.TrailingZeros(n)
357 func IterateBits64(n uint64) int {
360 // amd64/v1,amd64/v2:"BSFQ",-"CMOVEQ"
362 i += bits.TrailingZeros64(n)
368 func IterateBits32(n uint32) int {
371 // amd64/v1,amd64/v2:"BSFL",-"BTSQ"
373 i += bits.TrailingZeros32(n)
379 func IterateBits16(n uint16) int {
382 // amd64/v1,amd64/v2:"BSFL",-"BTSL"
384 // arm64:"RBITW","CLZW",-"ORR"
385 i += bits.TrailingZeros16(n)
391 func IterateBits8(n uint8) int {
394 // amd64/v1,amd64/v2:"BSFL",-"BTSL"
396 // arm64:"RBITW","CLZW",-"ORR"
397 i += bits.TrailingZeros8(n)
403 // --------------- //
405 // --------------- //
407 func Add(x, y, ci uint) (r, co uint) {
408 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
409 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
410 // s390x:"ADDE","ADDC\t[$]-1,"
411 return bits.Add(x, y, ci)
414 func AddC(x, ci uint) (r, co uint) {
415 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
416 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
417 // s390x:"ADDE","ADDC\t[$]-1,"
418 return bits.Add(x, 7, ci)
421 func AddZ(x, y uint) (r, co uint) {
422 // arm64:"ADDS","ADC",-"ADCS",-"ADD\t",-"CMP"
423 // amd64:"ADDQ","SBBQ","NEGQ",-"NEGL",-"ADCQ"
424 // s390x:"ADDC",-"ADDC\t[$]-1,"
425 return bits.Add(x, y, 0)
428 func AddR(x, y, ci uint) uint {
429 // arm64:"ADDS","ADCS",-"ADD\t",-"CMP"
430 // amd64:"NEGL","ADCQ",-"SBBQ",-"NEGQ"
431 // s390x:"ADDE","ADDC\t[$]-1,"
432 r, _ := bits.Add(x, y, ci)
436 func AddM(p, q, r *[3]uint) {
438 r[0], c = bits.Add(p[0], q[0], c)
439 // arm64:"ADCS",-"ADD\t",-"CMP"
440 // amd64:"ADCQ",-"NEGL",-"SBBQ",-"NEGQ"
441 // s390x:"ADDE",-"ADDC\t[$]-1,"
442 r[1], c = bits.Add(p[1], q[1], c)
443 r[2], c = bits.Add(p[2], q[2], c)
446 func Add64(x, y, ci uint64) (r, co uint64) {
447 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
448 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
449 // ppc64: "ADDC", "ADDE", "ADDZE"
450 // ppc64le: "ADDC", "ADDE", "ADDZE"
451 // s390x:"ADDE","ADDC\t[$]-1,"
452 return bits.Add64(x, y, ci)
455 func Add64C(x, ci uint64) (r, co uint64) {
456 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
457 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
458 // ppc64: "ADDC", "ADDE", "ADDZE"
459 // ppc64le: "ADDC", "ADDE", "ADDZE"
460 // s390x:"ADDE","ADDC\t[$]-1,"
461 return bits.Add64(x, 7, ci)
464 func Add64Z(x, y uint64) (r, co uint64) {
465 // arm64:"ADDS","ADC",-"ADCS",-"ADD\t",-"CMP"
466 // amd64:"ADDQ","SBBQ","NEGQ",-"NEGL",-"ADCQ"
467 // ppc64: "ADDC", "ADDE", "ADDZE"
468 // ppc64le: "ADDC", "ADDE", "ADDZE"
469 // s390x:"ADDC",-"ADDC\t[$]-1,"
470 return bits.Add64(x, y, 0)
473 func Add64R(x, y, ci uint64) uint64 {
474 // arm64:"ADDS","ADCS",-"ADD\t",-"CMP"
475 // amd64:"NEGL","ADCQ",-"SBBQ",-"NEGQ"
476 // ppc64: "ADDC", "ADDE", "ADDZE"
477 // ppc64le: "ADDC", "ADDE", "ADDZE"
478 // s390x:"ADDE","ADDC\t[$]-1,"
479 r, _ := bits.Add64(x, y, ci)
482 func Add64M(p, q, r *[3]uint64) {
484 r[0], c = bits.Add64(p[0], q[0], c)
485 // arm64:"ADCS",-"ADD\t",-"CMP"
486 // amd64:"ADCQ",-"NEGL",-"SBBQ",-"NEGQ"
487 // ppc64: "ADDC", "ADDE", "ADDZE"
488 // ppc64le: "ADDC", "ADDE", "ADDZE"
489 // s390x:"ADDE",-"ADDC\t[$]-1,"
490 r[1], c = bits.Add64(p[1], q[1], c)
491 r[2], c = bits.Add64(p[2], q[2], c)
494 func Add64PanicOnOverflowEQ(a, b uint64) uint64 {
495 r, c := bits.Add64(a, b, 0)
496 // s390x:"BRC\t[$]3,",-"ADDE"
503 func Add64PanicOnOverflowNE(a, b uint64) uint64 {
504 r, c := bits.Add64(a, b, 0)
505 // s390x:"BRC\t[$]3,",-"ADDE"
512 func Add64PanicOnOverflowGT(a, b uint64) uint64 {
513 r, c := bits.Add64(a, b, 0)
514 // s390x:"BRC\t[$]3,",-"ADDE"
521 func Add64MPanicOnOverflowEQ(a, b [2]uint64) [2]uint64 {
524 r[0], c = bits.Add64(a[0], b[0], c)
525 r[1], c = bits.Add64(a[1], b[1], c)
526 // s390x:"BRC\t[$]3,"
533 func Add64MPanicOnOverflowNE(a, b [2]uint64) [2]uint64 {
536 r[0], c = bits.Add64(a[0], b[0], c)
537 r[1], c = bits.Add64(a[1], b[1], c)
538 // s390x:"BRC\t[$]3,"
545 func Add64MPanicOnOverflowGT(a, b [2]uint64) [2]uint64 {
548 r[0], c = bits.Add64(a[0], b[0], c)
549 r[1], c = bits.Add64(a[1], b[1], c)
550 // s390x:"BRC\t[$]3,"
557 // --------------- //
559 // --------------- //
561 func Sub(x, y, ci uint) (r, co uint) {
562 // amd64:"NEGL","SBBQ","NEGQ"
563 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
565 return bits.Sub(x, y, ci)
568 func SubC(x, ci uint) (r, co uint) {
569 // amd64:"NEGL","SBBQ","NEGQ"
570 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
572 return bits.Sub(x, 7, ci)
575 func SubZ(x, y uint) (r, co uint) {
576 // amd64:"SUBQ","SBBQ","NEGQ",-"NEGL"
577 // arm64:"SUBS","NGC","NEG",-"SBCS",-"ADD",-"SUB\t",-"CMP"
579 return bits.Sub(x, y, 0)
582 func SubR(x, y, ci uint) uint {
583 // amd64:"NEGL","SBBQ",-"NEGQ"
584 // arm64:"NEGS","SBCS",-"NGC",-"NEG\t",-"ADD",-"SUB",-"CMP"
586 r, _ := bits.Sub(x, y, ci)
589 func SubM(p, q, r *[3]uint) {
591 r[0], c = bits.Sub(p[0], q[0], c)
592 // amd64:"SBBQ",-"NEGL",-"NEGQ"
593 // arm64:"SBCS",-"NEGS",-"NGC",-"NEG",-"ADD",-"SUB",-"CMP"
595 r[1], c = bits.Sub(p[1], q[1], c)
596 r[2], c = bits.Sub(p[2], q[2], c)
599 func Sub64(x, y, ci uint64) (r, co uint64) {
600 // amd64:"NEGL","SBBQ","NEGQ"
601 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
603 return bits.Sub64(x, y, ci)
606 func Sub64C(x, ci uint64) (r, co uint64) {
607 // amd64:"NEGL","SBBQ","NEGQ"
608 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
610 return bits.Sub64(x, 7, ci)
613 func Sub64Z(x, y uint64) (r, co uint64) {
614 // amd64:"SUBQ","SBBQ","NEGQ",-"NEGL"
615 // arm64:"SUBS","NGC","NEG",-"SBCS",-"ADD",-"SUB\t",-"CMP"
617 return bits.Sub64(x, y, 0)
620 func Sub64R(x, y, ci uint64) uint64 {
621 // amd64:"NEGL","SBBQ",-"NEGQ"
622 // arm64:"NEGS","SBCS",-"NGC",-"NEG\t",-"ADD",-"SUB",-"CMP"
624 r, _ := bits.Sub64(x, y, ci)
627 func Sub64M(p, q, r *[3]uint64) {
629 r[0], c = bits.Sub64(p[0], q[0], c)
630 // amd64:"SBBQ",-"NEGL",-"NEGQ"
631 // arm64:"SBCS",-"NEGS",-"NGC",-"NEG",-"ADD",-"SUB",-"CMP"
633 r[1], c = bits.Sub64(p[1], q[1], c)
634 r[2], c = bits.Sub64(p[2], q[2], c)
637 func Sub64PanicOnOverflowEQ(a, b uint64) uint64 {
638 r, b := bits.Sub64(a, b, 0)
639 // s390x:"BRC\t[$]12,",-"ADDE",-"SUBE"
646 func Sub64PanicOnOverflowNE(a, b uint64) uint64 {
647 r, b := bits.Sub64(a, b, 0)
648 // s390x:"BRC\t[$]12,",-"ADDE",-"SUBE"
655 func Sub64PanicOnOverflowGT(a, b uint64) uint64 {
656 r, b := bits.Sub64(a, b, 0)
657 // s390x:"BRC\t[$]12,",-"ADDE",-"SUBE"
664 func Sub64MPanicOnOverflowEQ(a, b [2]uint64) [2]uint64 {
667 r[0], c = bits.Sub64(a[0], b[0], c)
668 r[1], c = bits.Sub64(a[1], b[1], c)
669 // s390x:"BRC\t[$]12,"
676 func Sub64MPanicOnOverflowNE(a, b [2]uint64) [2]uint64 {
679 r[0], c = bits.Sub64(a[0], b[0], c)
680 r[1], c = bits.Sub64(a[1], b[1], c)
681 // s390x:"BRC\t[$]12,"
688 func Sub64MPanicOnOverflowGT(a, b [2]uint64) [2]uint64 {
691 r[0], c = bits.Sub64(a[0], b[0], c)
692 r[1], c = bits.Sub64(a[1], b[1], c)
693 // s390x:"BRC\t[$]12,"
700 // --------------- //
702 // --------------- //
704 func Mul(x, y uint) (hi, lo uint) {
706 // arm64:"UMULH","MUL"
707 // ppc64:"MULHDU","MULLD"
708 // ppc64le:"MULHDU","MULLD"
711 return bits.Mul(x, y)
714 func Mul64(x, y uint64) (hi, lo uint64) {
716 // arm64:"UMULH","MUL"
717 // ppc64:"MULHDU","MULLD"
718 // ppc64le:"MULHDU","MULLD"
721 // riscv64:"MULHU","MUL"
722 return bits.Mul64(x, y)
725 // --------------- //
727 // --------------- //
729 func Div(hi, lo, x uint) (q, r uint) {
731 return bits.Div(hi, lo, x)
734 func Div32(hi, lo, x uint32) (q, r uint32) {
735 // arm64:"ORR","UDIV","MSUB",-"UREM"
736 return bits.Div32(hi, lo, x)
739 func Div64(hi, lo, x uint64) (q, r uint64) {
741 return bits.Div64(hi, lo, x)
744 func Div64degenerate(x uint64) (q, r uint64) {
746 return bits.Div64(0, x, 5)