bits.h
Go to the documentation of this file.
00001 // Copyright 2018 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #ifndef ABSL_BASE_INTERNAL_BITS_H_
00016 #define ABSL_BASE_INTERNAL_BITS_H_
00017 
00018 // This file contains bitwise ops which are implementation details of various
00019 // absl libraries.
00020 
00021 #include <cstdint>
00022 
00023 // Clang on Windows has __builtin_clzll; otherwise we need to use the
00024 // windows intrinsic functions.
00025 #if defined(_MSC_VER)
00026 #include <intrin.h>
00027 #if defined(_M_X64)
00028 #pragma intrinsic(_BitScanReverse64)
00029 #pragma intrinsic(_BitScanForward64)
00030 #endif
00031 #pragma intrinsic(_BitScanReverse)
00032 #pragma intrinsic(_BitScanForward)
00033 #endif
00034 
00035 #include "absl/base/attributes.h"
00036 
00037 #if defined(_MSC_VER)
00038 // We can achieve something similar to attribute((always_inline)) with MSVC by
00039 // using the __forceinline keyword, however this is not perfect. MSVC is
00040 // much less aggressive about inlining, and even with the __forceinline keyword.
00041 #define ABSL_BASE_INTERNAL_FORCEINLINE __forceinline
00042 #else
00043 // Use default attribute inline.
00044 #define ABSL_BASE_INTERNAL_FORCEINLINE inline ABSL_ATTRIBUTE_ALWAYS_INLINE
00045 #endif
00046 
00047 
00048 namespace absl {
00049 namespace base_internal {
00050 
00051 ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64Slow(uint64_t n) {
00052   int zeroes = 60;
00053   if (n >> 32) zeroes -= 32, n >>= 32;
00054   if (n >> 16) zeroes -= 16, n >>= 16;
00055   if (n >> 8) zeroes -= 8, n >>= 8;
00056   if (n >> 4) zeroes -= 4, n >>= 4;
00057   return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes;
00058 }
00059 
00060 ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64(uint64_t n) {
00061 #if defined(_MSC_VER) && defined(_M_X64)
00062   // MSVC does not have __buitin_clzll. Use _BitScanReverse64.
00063   unsigned long result = 0;  // NOLINT(runtime/int)
00064   if (_BitScanReverse64(&result, n)) {
00065     return 63 - result;
00066   }
00067   return 64;
00068 #elif defined(_MSC_VER)
00069   // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse
00070   unsigned long result = 0;  // NOLINT(runtime/int)
00071   if ((n >> 32) && _BitScanReverse(&result, n >> 32)) {
00072     return 31 - result;
00073   }
00074   if (_BitScanReverse(&result, n)) {
00075     return 63 - result;
00076   }
00077   return 64;
00078 #elif defined(__GNUC__)
00079   // Use __builtin_clzll, which uses the following instructions:
00080   //  x86: bsr
00081   //  ARM64: clz
00082   //  PPC: cntlzd
00083   static_assert(sizeof(unsigned long long) == sizeof(n),  // NOLINT(runtime/int)
00084                 "__builtin_clzll does not take 64-bit arg");
00085 
00086   // Handle 0 as a special case because __builtin_clzll(0) is undefined.
00087   if (n == 0) {
00088     return 64;
00089   }
00090   return __builtin_clzll(n);
00091 #else
00092   return CountLeadingZeros64Slow(n);
00093 #endif
00094 }
00095 
00096 ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32Slow(uint64_t n) {
00097   int zeroes = 28;
00098   if (n >> 16) zeroes -= 16, n >>= 16;
00099   if (n >> 8) zeroes -= 8, n >>= 8;
00100   if (n >> 4) zeroes -= 4, n >>= 4;
00101   return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes;
00102 }
00103 
00104 ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32(uint32_t n) {
00105 #if defined(_MSC_VER)
00106   unsigned long result = 0;  // NOLINT(runtime/int)
00107   if (_BitScanReverse(&result, n)) {
00108     return 31 - result;
00109   }
00110   return 32;
00111 #elif defined(__GNUC__)
00112   // Use __builtin_clz, which uses the following instructions:
00113   //  x86: bsr
00114   //  ARM64: clz
00115   //  PPC: cntlzd
00116   static_assert(sizeof(int) == sizeof(n),
00117                 "__builtin_clz does not take 32-bit arg");
00118 
00119   // Handle 0 as a special case because __builtin_clz(0) is undefined.
00120   if (n == 0) {
00121     return 32;
00122   }
00123   return __builtin_clz(n);
00124 #else
00125   return CountLeadingZeros32Slow(n);
00126 #endif
00127 }
00128 
00129 ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64Slow(uint64_t n) {
00130   int c = 63;
00131   n &= ~n + 1;
00132   if (n & 0x00000000FFFFFFFF) c -= 32;
00133   if (n & 0x0000FFFF0000FFFF) c -= 16;
00134   if (n & 0x00FF00FF00FF00FF) c -= 8;
00135   if (n & 0x0F0F0F0F0F0F0F0F) c -= 4;
00136   if (n & 0x3333333333333333) c -= 2;
00137   if (n & 0x5555555555555555) c -= 1;
00138   return c;
00139 }
00140 
00141 ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64(uint64_t n) {
00142 #if defined(_MSC_VER) && defined(_M_X64)
00143   unsigned long result = 0;  // NOLINT(runtime/int)
00144   _BitScanForward64(&result, n);
00145   return result;
00146 #elif defined(_MSC_VER)
00147   unsigned long result = 0;  // NOLINT(runtime/int)
00148   if (static_cast<uint32_t>(n) == 0) {
00149     _BitScanForward(&result, n >> 32);
00150     return result + 32;
00151   }
00152   _BitScanForward(&result, n);
00153   return result;
00154 #elif defined(__GNUC__)
00155   static_assert(sizeof(unsigned long long) == sizeof(n),  // NOLINT(runtime/int)
00156                 "__builtin_ctzll does not take 64-bit arg");
00157   return __builtin_ctzll(n);
00158 #else
00159   return CountTrailingZerosNonZero64Slow(n);
00160 #endif
00161 }
00162 
00163 ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32Slow(uint32_t n) {
00164   int c = 31;
00165   n &= ~n + 1;
00166   if (n & 0x0000FFFF) c -= 16;
00167   if (n & 0x00FF00FF) c -= 8;
00168   if (n & 0x0F0F0F0F) c -= 4;
00169   if (n & 0x33333333) c -= 2;
00170   if (n & 0x55555555) c -= 1;
00171   return c;
00172 }
00173 
00174 ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32(uint32_t n) {
00175 #if defined(_MSC_VER)
00176   unsigned long result = 0;  // NOLINT(runtime/int)
00177   _BitScanForward(&result, n);
00178   return result;
00179 #elif defined(__GNUC__)
00180   static_assert(sizeof(int) == sizeof(n),
00181                 "__builtin_ctz does not take 32-bit arg");
00182   return __builtin_ctz(n);
00183 #else
00184   return CountTrailingZerosNonZero32Slow(n);
00185 #endif
00186 }
00187 
00188 #undef ABSL_BASE_INTERNAL_FORCEINLINE
00189 
00190 }  // namespace base_internal
00191 }  // namespace absl
00192 
00193 #endif  // ABSL_BASE_INTERNAL_BITS_H_


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:14