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"
82 func Len32(n uint32) int {
83 // amd64:"BSRQ","LEAQ",-"CMOVQEQ"
85 // arm:"CLZ" arm64:"CLZ"
91 func Len16(n uint16) int {
92 // amd64:"BSRL","LEAL",-"CMOVQEQ"
94 // arm:"CLZ" arm64:"CLZ"
100 func Len8(n uint8) int {
101 // amd64:"BSRL","LEAL",-"CMOVQEQ"
103 // arm:"CLZ" arm64:"CLZ"
109 // -------------------- //
111 // -------------------- //
113 // amd64:".*x86HasPOPCNT"
114 func OnesCount(n uint) int {
116 // arm64:"VCNT","VUADDLV"
121 return bits.OnesCount(n)
124 // amd64:".*x86HasPOPCNT"
125 func OnesCount64(n uint64) int {
127 // arm64:"VCNT","VUADDLV"
132 return bits.OnesCount64(n)
135 // amd64:".*x86HasPOPCNT"
136 func OnesCount32(n uint32) int {
138 // arm64:"VCNT","VUADDLV"
143 return bits.OnesCount32(n)
146 // amd64:".*x86HasPOPCNT"
147 func OnesCount16(n uint16) int {
149 // arm64:"VCNT","VUADDLV"
154 return bits.OnesCount16(n)
157 func OnesCount8(n uint8) int {
162 return bits.OnesCount8(n)
165 // ----------------------- //
166 // bits.ReverseBytes //
167 // ----------------------- //
169 func ReverseBytes(n uint) uint {
173 return bits.ReverseBytes(n)
176 func ReverseBytes64(n uint64) uint64 {
180 return bits.ReverseBytes64(n)
183 func ReverseBytes32(n uint32) uint32 {
187 return bits.ReverseBytes32(n)
190 func ReverseBytes16(n uint16) uint16 {
192 // arm64:"REV16W",-"UBFX",-"ORR"
193 // arm/5:"SLL","SRL","ORR"
196 return bits.ReverseBytes16(n)
199 // --------------------- //
200 // bits.RotateLeft //
201 // --------------------- //
203 func RotateLeft64(n uint64) uint64 {
210 return bits.RotateLeft64(n, 37)
213 func RotateLeft32(n uint32) uint32 {
214 // amd64:"ROLL" 386:"ROLL"
215 // arm:`MOVW\tR[0-9]+@>23`
221 return bits.RotateLeft32(n, 9)
224 func RotateLeft16(n uint16) uint16 {
225 // amd64:"ROLW" 386:"ROLW"
226 return bits.RotateLeft16(n, 5)
229 func RotateLeft8(n uint8) uint8 {
230 // amd64:"ROLB" 386:"ROLB"
231 return bits.RotateLeft8(n, 5)
234 func RotateLeftVariable(n uint, m int) uint {
241 return bits.RotateLeft(n, m)
244 func RotateLeftVariable64(n uint64, m int) uint64 {
251 return bits.RotateLeft64(n, m)
254 func RotateLeftVariable32(n uint32, m int) uint32 {
255 // arm:`MOVW\tR[0-9]+@>R[0-9]+`
262 return bits.RotateLeft32(n, m)
265 // ------------------------ //
266 // bits.TrailingZeros //
267 // ------------------------ //
269 func TrailingZeros(n uint) int {
270 // amd64:"BSFQ","MOVL\t\\$64","CMOVQEQ"
272 // arm64:"RBIT","CLZ"
274 // ppc64/power8:"ANDN","POPCNTD"
275 // ppc64le/power8:"ANDN","POPCNTD"
276 // ppc64/power9: "CNTTZD"
277 // ppc64le/power9: "CNTTZD"
279 return bits.TrailingZeros(n)
282 func TrailingZeros64(n uint64) int {
283 // amd64:"BSFQ","MOVL\t\\$64","CMOVQEQ"
284 // arm64:"RBIT","CLZ"
286 // ppc64/power8:"ANDN","POPCNTD"
287 // ppc64le/power8:"ANDN","POPCNTD"
288 // ppc64/power9: "CNTTZD"
289 // ppc64le/power9: "CNTTZD"
291 return bits.TrailingZeros64(n)
294 func TrailingZeros32(n uint32) int {
295 // amd64:"BTSQ\\t\\$32","BSFQ"
297 // arm64:"RBITW","CLZW"
298 // s390x:"FLOGR","MOVWZ"
299 // ppc64/power8:"ANDN","POPCNTW"
300 // ppc64le/power8:"ANDN","POPCNTW"
301 // ppc64/power9: "CNTTZW"
302 // ppc64le/power9: "CNTTZW"
304 return bits.TrailingZeros32(n)
307 func TrailingZeros16(n uint16) int {
308 // amd64:"BSFL","BTSL\\t\\$16"
310 // arm:"ORR\t\\$65536","CLZ",-"MOVHU\tR"
311 // arm64:"ORR\t\\$65536","RBITW","CLZW",-"MOVHU\tR",-"RBIT\t",-"CLZ\t"
312 // s390x:"FLOGR","OR\t\\$65536"
313 // ppc64/power8:"POPCNTD","OR\\t\\$65536"
314 // ppc64le/power8:"POPCNTD","OR\\t\\$65536"
315 // ppc64/power9:"CNTTZD","OR\\t\\$65536"
316 // ppc64le/power9:"CNTTZD","OR\\t\\$65536"
318 return bits.TrailingZeros16(n)
321 func TrailingZeros8(n uint8) int {
322 // amd64:"BSFL","BTSL\\t\\$8"
323 // arm:"ORR\t\\$256","CLZ",-"MOVBU\tR"
324 // arm64:"ORR\t\\$256","RBITW","CLZW",-"MOVBU\tR",-"RBIT\t",-"CLZ\t"
325 // s390x:"FLOGR","OR\t\\$256"
327 return bits.TrailingZeros8(n)
330 // IterateBitsNN checks special handling of TrailingZerosNN when the input is known to be non-zero.
332 func IterateBits(n uint) int {
335 // amd64:"BSFQ",-"CMOVEQ"
336 i += bits.TrailingZeros(n)
342 func IterateBits64(n uint64) int {
345 // amd64:"BSFQ",-"CMOVEQ"
346 i += bits.TrailingZeros64(n)
352 func IterateBits32(n uint32) int {
355 // amd64:"BSFL",-"BTSQ"
356 i += bits.TrailingZeros32(n)
362 func IterateBits16(n uint16) int {
365 // amd64:"BSFL",-"BTSL"
366 // arm64:"RBITW","CLZW",-"ORR"
367 i += bits.TrailingZeros16(n)
373 func IterateBits8(n uint8) int {
376 // amd64:"BSFL",-"BTSL"
377 // arm64:"RBITW","CLZW",-"ORR"
378 i += bits.TrailingZeros8(n)
384 // --------------- //
386 // --------------- //
388 func Add(x, y, ci uint) (r, co uint) {
389 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
390 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
391 // s390x:"ADDE","ADDC\t[$]-1,"
392 return bits.Add(x, y, ci)
395 func AddC(x, ci uint) (r, co uint) {
396 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
397 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
398 // s390x:"ADDE","ADDC\t[$]-1,"
399 return bits.Add(x, 7, ci)
402 func AddZ(x, y uint) (r, co uint) {
403 // arm64:"ADDS","ADC",-"ADCS",-"ADD\t",-"CMP"
404 // amd64:"ADDQ","SBBQ","NEGQ",-"NEGL",-"ADCQ"
405 // s390x:"ADDC",-"ADDC\t[$]-1,"
406 return bits.Add(x, y, 0)
409 func AddR(x, y, ci uint) uint {
410 // arm64:"ADDS","ADCS",-"ADD\t",-"CMP"
411 // amd64:"NEGL","ADCQ",-"SBBQ",-"NEGQ"
412 // s390x:"ADDE","ADDC\t[$]-1,"
413 r, _ := bits.Add(x, y, ci)
417 func AddM(p, q, r *[3]uint) {
419 r[0], c = bits.Add(p[0], q[0], c)
420 // arm64:"ADCS",-"ADD\t",-"CMP"
421 // amd64:"ADCQ",-"NEGL",-"SBBQ",-"NEGQ"
422 // s390x:"ADDE",-"ADDC\t[$]-1,"
423 r[1], c = bits.Add(p[1], q[1], c)
424 r[2], c = bits.Add(p[2], q[2], c)
427 func Add64(x, y, ci uint64) (r, co uint64) {
428 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
429 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
430 // ppc64: "ADDC", "ADDE", "ADDZE"
431 // ppc64le: "ADDC", "ADDE", "ADDZE"
432 // s390x:"ADDE","ADDC\t[$]-1,"
433 return bits.Add64(x, y, ci)
436 func Add64C(x, ci uint64) (r, co uint64) {
437 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
438 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
439 // ppc64: "ADDC", "ADDE", "ADDZE"
440 // ppc64le: "ADDC", "ADDE", "ADDZE"
441 // s390x:"ADDE","ADDC\t[$]-1,"
442 return bits.Add64(x, 7, ci)
445 func Add64Z(x, y uint64) (r, co uint64) {
446 // arm64:"ADDS","ADC",-"ADCS",-"ADD\t",-"CMP"
447 // amd64:"ADDQ","SBBQ","NEGQ",-"NEGL",-"ADCQ"
448 // ppc64: "ADDC", "ADDE", "ADDZE"
449 // ppc64le: "ADDC", "ADDE", "ADDZE"
450 // s390x:"ADDC",-"ADDC\t[$]-1,"
451 return bits.Add64(x, y, 0)
454 func Add64R(x, y, ci uint64) uint64 {
455 // arm64:"ADDS","ADCS",-"ADD\t",-"CMP"
456 // amd64:"NEGL","ADCQ",-"SBBQ",-"NEGQ"
457 // ppc64: "ADDC", "ADDE", "ADDZE"
458 // ppc64le: "ADDC", "ADDE", "ADDZE"
459 // s390x:"ADDE","ADDC\t[$]-1,"
460 r, _ := bits.Add64(x, y, ci)
463 func Add64M(p, q, r *[3]uint64) {
465 r[0], c = bits.Add64(p[0], q[0], c)
466 // arm64:"ADCS",-"ADD\t",-"CMP"
467 // amd64:"ADCQ",-"NEGL",-"SBBQ",-"NEGQ"
468 // ppc64: "ADDC", "ADDE", "ADDZE"
469 // ppc64le: "ADDC", "ADDE", "ADDZE"
470 // s390x:"ADDE",-"ADDC\t[$]-1,"
471 r[1], c = bits.Add64(p[1], q[1], c)
472 r[2], c = bits.Add64(p[2], q[2], c)
475 func Add64PanicOnOverflowEQ(a, b uint64) uint64 {
476 r, c := bits.Add64(a, b, 0)
477 // s390x:"BRC\t[$]3,",-"ADDE"
484 func Add64PanicOnOverflowNE(a, b uint64) uint64 {
485 r, c := bits.Add64(a, b, 0)
486 // s390x:"BRC\t[$]3,",-"ADDE"
493 func Add64PanicOnOverflowGT(a, b uint64) uint64 {
494 r, c := bits.Add64(a, b, 0)
495 // s390x:"BRC\t[$]3,",-"ADDE"
502 func Add64MPanicOnOverflowEQ(a, b [2]uint64) [2]uint64 {
505 r[0], c = bits.Add64(a[0], b[0], c)
506 r[1], c = bits.Add64(a[1], b[1], c)
507 // s390x:"BRC\t[$]3,"
514 func Add64MPanicOnOverflowNE(a, b [2]uint64) [2]uint64 {
517 r[0], c = bits.Add64(a[0], b[0], c)
518 r[1], c = bits.Add64(a[1], b[1], c)
519 // s390x:"BRC\t[$]3,"
526 func Add64MPanicOnOverflowGT(a, b [2]uint64) [2]uint64 {
529 r[0], c = bits.Add64(a[0], b[0], c)
530 r[1], c = bits.Add64(a[1], b[1], c)
531 // s390x:"BRC\t[$]3,"
538 // --------------- //
540 // --------------- //
542 func Sub(x, y, ci uint) (r, co uint) {
543 // amd64:"NEGL","SBBQ","NEGQ"
544 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
546 return bits.Sub(x, y, ci)
549 func SubC(x, ci uint) (r, co uint) {
550 // amd64:"NEGL","SBBQ","NEGQ"
551 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
553 return bits.Sub(x, 7, ci)
556 func SubZ(x, y uint) (r, co uint) {
557 // amd64:"SUBQ","SBBQ","NEGQ",-"NEGL"
558 // arm64:"SUBS","NGC","NEG",-"SBCS",-"ADD",-"SUB\t",-"CMP"
560 return bits.Sub(x, y, 0)
563 func SubR(x, y, ci uint) uint {
564 // amd64:"NEGL","SBBQ",-"NEGQ"
565 // arm64:"NEGS","SBCS",-"NGC",-"NEG\t",-"ADD",-"SUB",-"CMP"
567 r, _ := bits.Sub(x, y, ci)
570 func SubM(p, q, r *[3]uint) {
572 r[0], c = bits.Sub(p[0], q[0], c)
573 // amd64:"SBBQ",-"NEGL",-"NEGQ"
574 // arm64:"SBCS",-"NEGS",-"NGC",-"NEG",-"ADD",-"SUB",-"CMP"
576 r[1], c = bits.Sub(p[1], q[1], c)
577 r[2], c = bits.Sub(p[2], q[2], c)
580 func Sub64(x, y, ci uint64) (r, co uint64) {
581 // amd64:"NEGL","SBBQ","NEGQ"
582 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
584 return bits.Sub64(x, y, ci)
587 func Sub64C(x, ci uint64) (r, co uint64) {
588 // amd64:"NEGL","SBBQ","NEGQ"
589 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
591 return bits.Sub64(x, 7, ci)
594 func Sub64Z(x, y uint64) (r, co uint64) {
595 // amd64:"SUBQ","SBBQ","NEGQ",-"NEGL"
596 // arm64:"SUBS","NGC","NEG",-"SBCS",-"ADD",-"SUB\t",-"CMP"
598 return bits.Sub64(x, y, 0)
601 func Sub64R(x, y, ci uint64) uint64 {
602 // amd64:"NEGL","SBBQ",-"NEGQ"
603 // arm64:"NEGS","SBCS",-"NGC",-"NEG\t",-"ADD",-"SUB",-"CMP"
605 r, _ := bits.Sub64(x, y, ci)
608 func Sub64M(p, q, r *[3]uint64) {
610 r[0], c = bits.Sub64(p[0], q[0], c)
611 // amd64:"SBBQ",-"NEGL",-"NEGQ"
612 // arm64:"SBCS",-"NEGS",-"NGC",-"NEG",-"ADD",-"SUB",-"CMP"
614 r[1], c = bits.Sub64(p[1], q[1], c)
615 r[2], c = bits.Sub64(p[2], q[2], c)
618 func Sub64PanicOnOverflowEQ(a, b uint64) uint64 {
619 r, b := bits.Sub64(a, b, 0)
620 // s390x:"BRC\t[$]12,",-"ADDE",-"SUBE"
627 func Sub64PanicOnOverflowNE(a, b uint64) uint64 {
628 r, b := bits.Sub64(a, b, 0)
629 // s390x:"BRC\t[$]12,",-"ADDE",-"SUBE"
636 func Sub64PanicOnOverflowGT(a, b uint64) uint64 {
637 r, b := bits.Sub64(a, b, 0)
638 // s390x:"BRC\t[$]12,",-"ADDE",-"SUBE"
645 func Sub64MPanicOnOverflowEQ(a, b [2]uint64) [2]uint64 {
648 r[0], c = bits.Sub64(a[0], b[0], c)
649 r[1], c = bits.Sub64(a[1], b[1], c)
650 // s390x:"BRC\t[$]12,"
657 func Sub64MPanicOnOverflowNE(a, b [2]uint64) [2]uint64 {
660 r[0], c = bits.Sub64(a[0], b[0], c)
661 r[1], c = bits.Sub64(a[1], b[1], c)
662 // s390x:"BRC\t[$]12,"
669 func Sub64MPanicOnOverflowGT(a, b [2]uint64) [2]uint64 {
672 r[0], c = bits.Sub64(a[0], b[0], c)
673 r[1], c = bits.Sub64(a[1], b[1], c)
674 // s390x:"BRC\t[$]12,"
681 // --------------- //
683 // --------------- //
685 func Mul(x, y uint) (hi, lo uint) {
687 // arm64:"UMULH","MUL"
688 // ppc64:"MULHDU","MULLD"
689 // ppc64le:"MULHDU","MULLD"
692 return bits.Mul(x, y)
695 func Mul64(x, y uint64) (hi, lo uint64) {
697 // arm64:"UMULH","MUL"
698 // ppc64:"MULHDU","MULLD"
699 // ppc64le:"MULHDU","MULLD"
702 return bits.Mul64(x, y)
705 // --------------- //
707 // --------------- //
709 func Div(hi, lo, x uint) (q, r uint) {
711 return bits.Div(hi, lo, x)
714 func Div32(hi, lo, x uint32) (q, r uint32) {
715 // arm64:"ORR","UDIV","MSUB",-"UREM"
716 return bits.Div32(hi, lo, x)
719 func Div64(hi, lo, x uint64) (q, r uint64) {
721 return bits.Div64(hi, lo, x)
724 func Div64degenerate(x uint64) (q, r uint64) {
726 return bits.Div64(0, x, 5)