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 func OnesCount(n uint) int {
114 // amd64:"POPCNTQ",".*x86HasPOPCNT"
115 // arm64:"VCNT","VUADDLV"
120 return bits.OnesCount(n)
123 func OnesCount64(n uint64) int {
124 // amd64:"POPCNTQ",".*x86HasPOPCNT"
125 // arm64:"VCNT","VUADDLV"
130 return bits.OnesCount64(n)
133 func OnesCount32(n uint32) int {
134 // amd64:"POPCNTL",".*x86HasPOPCNT"
135 // arm64:"VCNT","VUADDLV"
140 return bits.OnesCount32(n)
143 func OnesCount16(n uint16) int {
144 // amd64:"POPCNTL",".*x86HasPOPCNT"
145 // arm64:"VCNT","VUADDLV"
150 return bits.OnesCount16(n)
153 func OnesCount8(n uint8) int {
158 return bits.OnesCount8(n)
161 // ----------------------- //
162 // bits.ReverseBytes //
163 // ----------------------- //
165 func ReverseBytes(n uint) uint {
169 return bits.ReverseBytes(n)
172 func ReverseBytes64(n uint64) uint64 {
176 return bits.ReverseBytes64(n)
179 func ReverseBytes32(n uint32) uint32 {
183 return bits.ReverseBytes32(n)
186 func ReverseBytes16(n uint16) uint16 {
188 // arm64:"REV16W",-"UBFX",-"ORR"
189 // arm/5:"SLL","SRL","ORR"
192 return bits.ReverseBytes16(n)
195 // --------------------- //
196 // bits.RotateLeft //
197 // --------------------- //
199 func RotateLeft64(n uint64) uint64 {
206 return bits.RotateLeft64(n, 37)
209 func RotateLeft32(n uint32) uint32 {
210 // amd64:"ROLL" 386:"ROLL"
211 // arm:`MOVW\tR[0-9]+@>23`
217 return bits.RotateLeft32(n, 9)
220 func RotateLeft16(n uint16) uint16 {
221 // amd64:"ROLW" 386:"ROLW"
222 return bits.RotateLeft16(n, 5)
225 func RotateLeft8(n uint8) uint8 {
226 // amd64:"ROLB" 386:"ROLB"
227 return bits.RotateLeft8(n, 5)
230 func RotateLeftVariable(n uint, m int) uint {
237 return bits.RotateLeft(n, m)
240 func RotateLeftVariable64(n uint64, m int) uint64 {
247 return bits.RotateLeft64(n, m)
250 func RotateLeftVariable32(n uint32, m int) uint32 {
251 // arm:`MOVW\tR[0-9]+@>R[0-9]+`
258 return bits.RotateLeft32(n, m)
261 // ------------------------ //
262 // bits.TrailingZeros //
263 // ------------------------ //
265 func TrailingZeros(n uint) int {
266 // amd64:"BSFQ","MOVL\t\\$64","CMOVQEQ"
268 // arm64:"RBIT","CLZ"
270 // ppc64/power8:"ANDN","POPCNTD"
271 // ppc64le/power8:"ANDN","POPCNTD"
272 // ppc64/power9: "CNTTZD"
273 // ppc64le/power9: "CNTTZD"
275 return bits.TrailingZeros(n)
278 func TrailingZeros64(n uint64) int {
279 // amd64:"BSFQ","MOVL\t\\$64","CMOVQEQ"
280 // arm64:"RBIT","CLZ"
282 // ppc64/power8:"ANDN","POPCNTD"
283 // ppc64le/power8:"ANDN","POPCNTD"
284 // ppc64/power9: "CNTTZD"
285 // ppc64le/power9: "CNTTZD"
287 return bits.TrailingZeros64(n)
290 func TrailingZeros32(n uint32) int {
291 // amd64:"BTSQ\\t\\$32","BSFQ"
293 // arm64:"RBITW","CLZW"
294 // s390x:"FLOGR","MOVWZ"
295 // ppc64/power8:"ANDN","POPCNTW"
296 // ppc64le/power8:"ANDN","POPCNTW"
297 // ppc64/power9: "CNTTZW"
298 // ppc64le/power9: "CNTTZW"
300 return bits.TrailingZeros32(n)
303 func TrailingZeros16(n uint16) int {
304 // amd64:"BSFL","BTSL\\t\\$16"
306 // arm:"ORR\t\\$65536","CLZ",-"MOVHU\tR"
307 // arm64:"ORR\t\\$65536","RBITW","CLZW",-"MOVHU\tR",-"RBIT\t",-"CLZ\t"
308 // s390x:"FLOGR","OR\t\\$65536"
309 // ppc64/power8:"POPCNTD","OR\\t\\$65536"
310 // ppc64le/power8:"POPCNTD","OR\\t\\$65536"
311 // ppc64/power9:"CNTTZD","OR\\t\\$65536"
312 // ppc64le/power9:"CNTTZD","OR\\t\\$65536"
314 return bits.TrailingZeros16(n)
317 func TrailingZeros8(n uint8) int {
318 // amd64:"BSFL","BTSL\\t\\$8"
319 // arm:"ORR\t\\$256","CLZ",-"MOVBU\tR"
320 // arm64:"ORR\t\\$256","RBITW","CLZW",-"MOVBU\tR",-"RBIT\t",-"CLZ\t"
321 // s390x:"FLOGR","OR\t\\$256"
323 return bits.TrailingZeros8(n)
326 // IterateBitsNN checks special handling of TrailingZerosNN when the input is known to be non-zero.
328 func IterateBits(n uint) int {
331 // amd64:"BSFQ",-"CMOVEQ"
332 i += bits.TrailingZeros(n)
338 func IterateBits64(n uint64) int {
341 // amd64:"BSFQ",-"CMOVEQ"
342 i += bits.TrailingZeros64(n)
348 func IterateBits32(n uint32) int {
351 // amd64:"BSFL",-"BTSQ"
352 i += bits.TrailingZeros32(n)
358 func IterateBits16(n uint16) int {
361 // amd64:"BSFL",-"BTSL"
362 // arm64:"RBITW","CLZW",-"ORR"
363 i += bits.TrailingZeros16(n)
369 func IterateBits8(n uint8) int {
372 // amd64:"BSFL",-"BTSL"
373 // arm64:"RBITW","CLZW",-"ORR"
374 i += bits.TrailingZeros8(n)
380 // --------------- //
382 // --------------- //
384 func Add(x, y, ci uint) (r, co uint) {
385 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
386 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
387 // s390x:"ADDE","ADDC\t[$]-1,"
388 return bits.Add(x, y, ci)
391 func AddC(x, ci uint) (r, co uint) {
392 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
393 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
394 // s390x:"ADDE","ADDC\t[$]-1,"
395 return bits.Add(x, 7, ci)
398 func AddZ(x, y uint) (r, co uint) {
399 // arm64:"ADDS","ADC",-"ADCS",-"ADD\t",-"CMP"
400 // amd64:"ADDQ","SBBQ","NEGQ",-"NEGL",-"ADCQ"
401 // s390x:"ADDC",-"ADDC\t[$]-1,"
402 return bits.Add(x, y, 0)
405 func AddR(x, y, ci uint) uint {
406 // arm64:"ADDS","ADCS",-"ADD\t",-"CMP"
407 // amd64:"NEGL","ADCQ",-"SBBQ",-"NEGQ"
408 // s390x:"ADDE","ADDC\t[$]-1,"
409 r, _ := bits.Add(x, y, ci)
413 func AddM(p, q, r *[3]uint) {
415 r[0], c = bits.Add(p[0], q[0], c)
416 // arm64:"ADCS",-"ADD\t",-"CMP"
417 // amd64:"ADCQ",-"NEGL",-"SBBQ",-"NEGQ"
418 // s390x:"ADDE",-"ADDC\t[$]-1,"
419 r[1], c = bits.Add(p[1], q[1], c)
420 r[2], c = bits.Add(p[2], q[2], c)
423 func Add64(x, y, ci uint64) (r, co uint64) {
424 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
425 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
426 // ppc64: "ADDC", "ADDE", "ADDZE"
427 // ppc64le: "ADDC", "ADDE", "ADDZE"
428 // s390x:"ADDE","ADDC\t[$]-1,"
429 return bits.Add64(x, y, ci)
432 func Add64C(x, ci uint64) (r, co uint64) {
433 // arm64:"ADDS","ADCS","ADC",-"ADD\t",-"CMP"
434 // amd64:"NEGL","ADCQ","SBBQ","NEGQ"
435 // ppc64: "ADDC", "ADDE", "ADDZE"
436 // ppc64le: "ADDC", "ADDE", "ADDZE"
437 // s390x:"ADDE","ADDC\t[$]-1,"
438 return bits.Add64(x, 7, ci)
441 func Add64Z(x, y uint64) (r, co uint64) {
442 // arm64:"ADDS","ADC",-"ADCS",-"ADD\t",-"CMP"
443 // amd64:"ADDQ","SBBQ","NEGQ",-"NEGL",-"ADCQ"
444 // ppc64: "ADDC", "ADDE", "ADDZE"
445 // ppc64le: "ADDC", "ADDE", "ADDZE"
446 // s390x:"ADDC",-"ADDC\t[$]-1,"
447 return bits.Add64(x, y, 0)
450 func Add64R(x, y, ci uint64) uint64 {
451 // arm64:"ADDS","ADCS",-"ADD\t",-"CMP"
452 // amd64:"NEGL","ADCQ",-"SBBQ",-"NEGQ"
453 // ppc64: "ADDC", "ADDE", "ADDZE"
454 // ppc64le: "ADDC", "ADDE", "ADDZE"
455 // s390x:"ADDE","ADDC\t[$]-1,"
456 r, _ := bits.Add64(x, y, ci)
459 func Add64M(p, q, r *[3]uint64) {
461 r[0], c = bits.Add64(p[0], q[0], c)
462 // arm64:"ADCS",-"ADD\t",-"CMP"
463 // amd64:"ADCQ",-"NEGL",-"SBBQ",-"NEGQ"
464 // ppc64: "ADDC", "ADDE", "ADDZE"
465 // ppc64le: "ADDC", "ADDE", "ADDZE"
466 // s390x:"ADDE",-"ADDC\t[$]-1,"
467 r[1], c = bits.Add64(p[1], q[1], c)
468 r[2], c = bits.Add64(p[2], q[2], c)
471 // --------------- //
473 // --------------- //
475 func Sub(x, y, ci uint) (r, co uint) {
476 // amd64:"NEGL","SBBQ","NEGQ"
477 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
479 return bits.Sub(x, y, ci)
482 func SubC(x, ci uint) (r, co uint) {
483 // amd64:"NEGL","SBBQ","NEGQ"
484 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
486 return bits.Sub(x, 7, ci)
489 func SubZ(x, y uint) (r, co uint) {
490 // amd64:"SUBQ","SBBQ","NEGQ",-"NEGL"
491 // arm64:"SUBS","NGC","NEG",-"SBCS",-"ADD",-"SUB\t",-"CMP"
493 return bits.Sub(x, y, 0)
496 func SubR(x, y, ci uint) uint {
497 // amd64:"NEGL","SBBQ",-"NEGQ"
498 // arm64:"NEGS","SBCS",-"NGC",-"NEG\t",-"ADD",-"SUB",-"CMP"
500 r, _ := bits.Sub(x, y, ci)
503 func SubM(p, q, r *[3]uint) {
505 r[0], c = bits.Sub(p[0], q[0], c)
506 // amd64:"SBBQ",-"NEGL",-"NEGQ"
507 // arm64:"SBCS",-"NEGS",-"NGC",-"NEG",-"ADD",-"SUB",-"CMP"
509 r[1], c = bits.Sub(p[1], q[1], c)
510 r[2], c = bits.Sub(p[2], q[2], c)
513 func Sub64(x, y, ci uint64) (r, co uint64) {
514 // amd64:"NEGL","SBBQ","NEGQ"
515 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
517 return bits.Sub64(x, y, ci)
520 func Sub64C(x, ci uint64) (r, co uint64) {
521 // amd64:"NEGL","SBBQ","NEGQ"
522 // arm64:"NEGS","SBCS","NGC","NEG",-"ADD",-"SUB",-"CMP"
524 return bits.Sub64(x, 7, ci)
527 func Sub64Z(x, y uint64) (r, co uint64) {
528 // amd64:"SUBQ","SBBQ","NEGQ",-"NEGL"
529 // arm64:"SUBS","NGC","NEG",-"SBCS",-"ADD",-"SUB\t",-"CMP"
531 return bits.Sub64(x, y, 0)
534 func Sub64R(x, y, ci uint64) uint64 {
535 // amd64:"NEGL","SBBQ",-"NEGQ"
536 // arm64:"NEGS","SBCS",-"NGC",-"NEG\t",-"ADD",-"SUB",-"CMP"
538 r, _ := bits.Sub64(x, y, ci)
541 func Sub64M(p, q, r *[3]uint64) {
543 r[0], c = bits.Sub64(p[0], q[0], c)
544 // amd64:"SBBQ",-"NEGL",-"NEGQ"
545 // arm64:"SBCS",-"NEGS",-"NGC",-"NEG",-"ADD",-"SUB",-"CMP"
547 r[1], c = bits.Sub64(p[1], q[1], c)
548 r[2], c = bits.Sub64(p[2], q[2], c)
551 // --------------- //
553 // --------------- //
555 func Mul(x, y uint) (hi, lo uint) {
557 // arm64:"UMULH","MUL"
558 // ppc64:"MULHDU","MULLD"
559 // ppc64le:"MULHDU","MULLD"
562 return bits.Mul(x, y)
565 func Mul64(x, y uint64) (hi, lo uint64) {
567 // arm64:"UMULH","MUL"
568 // ppc64:"MULHDU","MULLD"
569 // ppc64le:"MULHDU","MULLD"
572 return bits.Mul64(x, y)
575 // --------------- //
577 // --------------- //
579 func Div(hi, lo, x uint) (q, r uint) {
581 return bits.Div(hi, lo, x)
584 func Div32(hi, lo, x uint32) (q, r uint32) {
585 // arm64:"ORR","UDIV","MSUB",-"UREM"
586 return bits.Div32(hi, lo, x)
589 func Div64(hi, lo, x uint64) (q, r uint64) {
591 return bits.Div64(hi, lo, x)
594 func Div64degenerate(x uint64) (q, r uint64) {
596 return bits.Div64(0, x, 5)