intrinsics.go

Documentation: runtime/internal/sys

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:build !386
     6  // +build !386
     7  
     8  // TODO finish intrinsifying 386, deadcode the assembly, remove build tags, merge w/ intrinsics_common
     9  // TODO replace all uses of CtzXX with TrailingZerosXX; they are the same.
    10  
    11  package sys
    12  
    13  // Using techniques from http://supertech.csail.mit.edu/papers/debruijn.pdf
    14  
    15  const deBruijn64ctz = 0x0218a392cd3d5dbf
    16  
    17  var deBruijnIdx64ctz = [64]byte{
    18  	0, 1, 2, 7, 3, 13, 8, 19,
    19  	4, 25, 14, 28, 9, 34, 20, 40,
    20  	5, 17, 26, 38, 15, 46, 29, 48,
    21  	10, 31, 35, 54, 21, 50, 41, 57,
    22  	63, 6, 12, 18, 24, 27, 33, 39,
    23  	16, 37, 45, 47, 30, 53, 49, 56,
    24  	62, 11, 23, 32, 36, 44, 52, 55,
    25  	61, 22, 43, 51, 60, 42, 59, 58,
    26  }
    27  
    28  const deBruijn32ctz = 0x04653adf
    29  
    30  var deBruijnIdx32ctz = [32]byte{
    31  	0, 1, 2, 6, 3, 11, 7, 16,
    32  	4, 14, 12, 21, 8, 23, 17, 26,
    33  	31, 5, 10, 15, 13, 20, 22, 25,
    34  	30, 9, 19, 24, 29, 18, 28, 27,
    35  }
    36  
    37  // Ctz64 counts trailing (low-order) zeroes,
    38  // and if all are zero, then 64.
    39  func Ctz64(x uint64) int {
    40  	x &= -x                       // isolate low-order bit
    41  	y := x * deBruijn64ctz >> 58  // extract part of deBruijn sequence
    42  	i := int(deBruijnIdx64ctz[y]) // convert to bit index
    43  	z := int((x - 1) >> 57 & 64)  // adjustment if zero
    44  	return i + z
    45  }
    46  
    47  // Ctz32 counts trailing (low-order) zeroes,
    48  // and if all are zero, then 32.
    49  func Ctz32(x uint32) int {
    50  	x &= -x                       // isolate low-order bit
    51  	y := x * deBruijn32ctz >> 27  // extract part of deBruijn sequence
    52  	i := int(deBruijnIdx32ctz[y]) // convert to bit index
    53  	z := int((x - 1) >> 26 & 32)  // adjustment if zero
    54  	return i + z
    55  }
    56  
    57  // Ctz8 returns the number of trailing zero bits in x; the result is 8 for x == 0.
    58  func Ctz8(x uint8) int {
    59  	return int(ntz8tab[x])
    60  }
    61  
    62  // Bswap64 returns its input with byte order reversed
    63  // 0x0102030405060708 -> 0x0807060504030201
    64  func Bswap64(x uint64) uint64 {
    65  	c8 := uint64(0x00ff00ff00ff00ff)
    66  	a := x >> 8 & c8
    67  	b := (x & c8) << 8
    68  	x = a | b
    69  	c16 := uint64(0x0000ffff0000ffff)
    70  	a = x >> 16 & c16
    71  	b = (x & c16) << 16
    72  	x = a | b
    73  	c32 := uint64(0x00000000ffffffff)
    74  	a = x >> 32 & c32
    75  	b = (x & c32) << 32
    76  	x = a | b
    77  	return x
    78  }
    79  
    80  // Bswap32 returns its input with byte order reversed
    81  // 0x01020304 -> 0x04030201
    82  func Bswap32(x uint32) uint32 {
    83  	c8 := uint32(0x00ff00ff)
    84  	a := x >> 8 & c8
    85  	b := (x & c8) << 8
    86  	x = a | b
    87  	c16 := uint32(0x0000ffff)
    88  	a = x >> 16 & c16
    89  	b = (x & c16) << 16
    90  	x = a | b
    91  	return x
    92  }
    93
View as plain text