From 32b41c8dc75a731e4053b59b19c542a79eb56c1f Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Tue, 28 Feb 2017 14:55:00 -0800 Subject: [PATCH] math/bits: move left-over functionality from bits_impl.go to bits.go Removes an extra function call for TrailingZeroes and thus may increase chances for inlining. Change-Id: Iefd8d4402dc89b64baf4e5c865eb3dadade623af Reviewed-on: https://go-review.googlesource.com/37613 Run-TryBot: Robert Griesemer Reviewed-by: Brad Fitzpatrick --- src/math/bits/bits.go | 64 +++++++++++++++++++++++++++++++++--- src/math/bits/bits_impl.go | 67 -------------------------------------- 2 files changed, 59 insertions(+), 72 deletions(-) delete mode 100644 src/math/bits/bits_impl.go diff --git a/src/math/bits/bits.go b/src/math/bits/bits.go index 33a51c9a42..116d5b7a49 100644 --- a/src/math/bits/bits.go +++ b/src/math/bits/bits.go @@ -8,6 +8,8 @@ // functions for the predeclared unsigned integer types. package bits +const uintSize = 32 << (^uint(0) >> 32 & 1) // 32 or 64 + // UintSize is the size of a uint in bits. const UintSize = uintSize @@ -30,20 +32,72 @@ func LeadingZeros64(x uint64) int { return 64 - Len64(x) } // --- TrailingZeros --- +// See http://supertech.csail.mit.edu/papers/debruijn.pdf +const deBruijn32 = 0x077CB531 + +var deBruijn32tab = [32]byte{ + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, +} + +const deBruijn64 = 0x03f79d71b4ca8b09 + +var deBruijn64tab = [64]byte{ + 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, + 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, + 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, + 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6, +} + // TrailingZeros returns the number of trailing zero bits in x; the result is UintSize for x == 0. -func TrailingZeros(x uint) int { return ntz(x) } +func TrailingZeros(x uint) int { + if UintSize == 32 { + return TrailingZeros32(uint32(x)) + } + return TrailingZeros64(uint64(x)) +} // TrailingZeros8 returns the number of trailing zero bits in x; the result is 8 for x == 0. -func TrailingZeros8(x uint8) int { return int(ntz8tab[x]) } +func TrailingZeros8(x uint8) int { + return int(ntz8tab[x]) +} // TrailingZeros16 returns the number of trailing zero bits in x; the result is 16 for x == 0. -func TrailingZeros16(x uint16) int { return ntz16(x) } +func TrailingZeros16(x uint16) (n int) { + if x == 0 { + return 16 + } + // see comment in TrailingZeros64 + return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)]) +} // TrailingZeros32 returns the number of trailing zero bits in x; the result is 32 for x == 0. -func TrailingZeros32(x uint32) int { return ntz32(x) } +func TrailingZeros32(x uint32) int { + if x == 0 { + return 32 + } + // see comment in TrailingZeros64 + return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)]) +} // TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0. -func TrailingZeros64(x uint64) int { return ntz64(x) } +func TrailingZeros64(x uint64) int { + if x == 0 { + return 64 + } + // If popcount is fast, replace code below with return popcount(^x & (x - 1)). + // + // x & -x leaves only the right-most bit set in the word. Let k be the + // index of that bit. Since only a single bit is set, the value is two + // to the power of k. Multiplying by a power of two is equivalent to + // left shifting, in this case by k bits. The de Bruijn (64 bit) constant + // is such that all six bit, consecutive substrings are distinct. + // Therefore, if we have a left shifted version of this constant we can + // find by how many bits it was shifted by looking at which six bit + // substring ended up at the top of the word. + // (Knuth, volume 4, section 7.3.1) + return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)]) +} // --- OnesCount --- diff --git a/src/math/bits/bits_impl.go b/src/math/bits/bits_impl.go deleted file mode 100644 index 0a1d8d7795..0000000000 --- a/src/math/bits/bits_impl.go +++ /dev/null @@ -1,67 +0,0 @@ -// Copyright 2017 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// This file provides basic implementations of the bits functions. - -package bits - -const uintSize = 32 << (^uint(0) >> 32 & 1) // 32 or 64 - -func ntz(x uint) (n int) { - if UintSize == 32 { - return ntz32(uint32(x)) - } - return ntz64(uint64(x)) -} - -// See http://supertech.csail.mit.edu/papers/debruijn.pdf -const deBruijn32 = 0x077CB531 - -var deBruijn32tab = [32]byte{ - 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, - 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, -} - -func ntz16(x uint16) (n int) { - if x == 0 { - return 16 - } - // see comment in ntz64 - return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)]) -} - -func ntz32(x uint32) int { - if x == 0 { - return 32 - } - // see comment in ntz64 - return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)]) -} - -const deBruijn64 = 0x03f79d71b4ca8b09 - -var deBruijn64tab = [64]byte{ - 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, - 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, - 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, - 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6, -} - -func ntz64(x uint64) int { - if x == 0 { - return 64 - } - // If popcount is fast, replace code below with return popcount(^x & (x - 1)). - // - // x & -x leaves only the right-most bit set in the word. Let k be the - // index of that bit. Since only a single bit is set, the value is two - // to the power of k. Multiplying by a power of two is equivalent to - // left shifting, in this case by k bits. The de Bruijn (64 bit) constant - // is such that all six bit, consecutive substrings are distinct. - // Therefore, if we have a left shifted version of this constant we can - // find by how many bits it was shifted by looking at which six bit - // substring ended up at the top of the word. - // (Knuth, volume 4, section 7.3.1) - return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)]) -} -- 2.48.1