Source file src/runtime/internal/sys/intrinsics.go

     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	// +build !386
     6	
     7	package sys
     8	
     9	// Using techniques from http://supertech.csail.mit.edu/papers/debruijn.pdf
    10	
    11	const deBruijn64 = 0x0218a392cd3d5dbf
    12	
    13	var deBruijnIdx64 = [64]byte{
    14		0, 1, 2, 7, 3, 13, 8, 19,
    15		4, 25, 14, 28, 9, 34, 20, 40,
    16		5, 17, 26, 38, 15, 46, 29, 48,
    17		10, 31, 35, 54, 21, 50, 41, 57,
    18		63, 6, 12, 18, 24, 27, 33, 39,
    19		16, 37, 45, 47, 30, 53, 49, 56,
    20		62, 11, 23, 32, 36, 44, 52, 55,
    21		61, 22, 43, 51, 60, 42, 59, 58,
    22	}
    23	
    24	const deBruijn32 = 0x04653adf
    25	
    26	var deBruijnIdx32 = [32]byte{
    27		0, 1, 2, 6, 3, 11, 7, 16,
    28		4, 14, 12, 21, 8, 23, 17, 26,
    29		31, 5, 10, 15, 13, 20, 22, 25,
    30		30, 9, 19, 24, 29, 18, 28, 27,
    31	}
    32	
    33	// Ctz64 counts trailing (low-order) zeroes,
    34	// and if all are zero, then 64.
    35	func Ctz64(x uint64) int {
    36		x &= -x                      // isolate low-order bit
    37		y := x * deBruijn64 >> 58    // extract part of deBruijn sequence
    38		i := int(deBruijnIdx64[y])   // convert to bit index
    39		z := int((x - 1) >> 57 & 64) // adjustment if zero
    40		return i + z
    41	}
    42	
    43	// Ctz32 counts trailing (low-order) zeroes,
    44	// and if all are zero, then 32.
    45	func Ctz32(x uint32) int {
    46		x &= -x                      // isolate low-order bit
    47		y := x * deBruijn32 >> 27    // extract part of deBruijn sequence
    48		i := int(deBruijnIdx32[y])   // convert to bit index
    49		z := int((x - 1) >> 26 & 32) // adjustment if zero
    50		return i + z
    51	}
    52	
    53	// Ctz8 returns the number of trailing zero bits in x; the result is 8 for x == 0.
    54	func Ctz8(x uint8) int {
    55		return int(ntz8tab[x])
    56	}
    57	
    58	var ntz8tab = [256]uint8{
    59		0x08, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    60		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    61		0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    62		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    63		0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    64		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    65		0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    66		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    67		0x07, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    68		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    69		0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    70		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    71		0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    72		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    73		0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    74		0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
    75	}
    76	
    77	// Bswap64 returns its input with byte order reversed
    78	// 0x0102030405060708 -> 0x0807060504030201
    79	func Bswap64(x uint64) uint64 {
    80		c8 := uint64(0x00ff00ff00ff00ff)
    81		a := x >> 8 & c8
    82		b := (x & c8) << 8
    83		x = a | b
    84		c16 := uint64(0x0000ffff0000ffff)
    85		a = x >> 16 & c16
    86		b = (x & c16) << 16
    87		x = a | b
    88		c32 := uint64(0x00000000ffffffff)
    89		a = x >> 32 & c32
    90		b = (x & c32) << 32
    91		x = a | b
    92		return x
    93	}
    94	
    95	// Bswap32 returns its input with byte order reversed
    96	// 0x01020304 -> 0x04030201
    97	func Bswap32(x uint32) uint32 {
    98		c8 := uint32(0x00ff00ff)
    99		a := x >> 8 & c8
   100		b := (x & c8) << 8
   101		x = a | b
   102		c16 := uint32(0x0000ffff)
   103		a = x >> 16 & c16
   104		b = (x & c16) << 16
   105		x = a | b
   106		return x
   107	}
   108	

View as plain text