numeric/internal/bits.h

0001 // Copyright 2020 The Abseil Authors
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //     https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_NUMERIC_INTERNAL_BITS_H_
0016 #define ABSL_NUMERIC_INTERNAL_BITS_H_
0017
0018 #include <cstdint>
0019 #include <limits>
0020 #include <type_traits>
0021
0022 // Clang on Windows has __builtin_clzll; otherwise we need to use the
0023 // windows intrinsic functions.
0024 #if defined(_MSC_VER) && !defined(__clang__)
0025 #include <intrin.h>
0026 #endif
0027
0028 #include "absl/base/attributes.h"
0029 #include "absl/base/config.h"
0030
0031 #if defined(__GNUC__) && !defined(__clang__)
0032 // GCC
0033 #define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) 1
0034 #else
0035 #define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) ABSL_HAVE_BUILTIN(x)
0036 #endif
0037
0038 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountl) && \
0039     ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll)
0040 #define ABSL_INTERNAL_CONSTEXPR_POPCOUNT constexpr
0041 #define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 1
0042 #else
0043 #define ABSL_INTERNAL_CONSTEXPR_POPCOUNT
0044 #define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 0
0045 #endif
0046
0047 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz) && \
0048     ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll)
0049 #define ABSL_INTERNAL_CONSTEXPR_CLZ constexpr
0050 #define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 1
0051 #else
0052 #define ABSL_INTERNAL_CONSTEXPR_CLZ
0053 #define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 0
0054 #endif
0055
0056 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz) && \
0057     ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll)
0058 #define ABSL_INTERNAL_CONSTEXPR_CTZ constexpr
0059 #define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 1
0060 #else
0061 #define ABSL_INTERNAL_CONSTEXPR_CTZ
0062 #define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 0
0063 #endif
0064
0065 namespace absl {
0066 ABSL_NAMESPACE_BEGIN
0067 namespace numeric_internal {
0068
0069 constexpr bool IsPowerOf2(unsigned int x) noexcept {
0070   return x != 0 && (x & (x - 1)) == 0;
0071 }
0072
0073 template <class T>
0074 ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateRight(
0075     T x, int s) noexcept {
0076   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
0077   static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
0078                 "T must have a power-of-2 size");
0079
0080   return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) |
0081          static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1)));
0082 }
0083
0084 template <class T>
0085 ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft(
0086     T x, int s) noexcept {
0087   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
0088   static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
0089                 "T must have a power-of-2 size");
0090
0091   return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) |
0092          static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1)));
0093 }
0094
0095 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
0096 Popcount32(uint32_t x) noexcept {
0097 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcount)
0098   static_assert(sizeof(unsigned int) == sizeof(x),
0099                 "__builtin_popcount does not take 32-bit arg");
0100   return __builtin_popcount(x);
0101 #else
0102   x -= ((x >> 1) & 0x55555555);
0103   x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
0104   return static_cast<int>((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24);
0105 #endif
0106 }
0107
0108 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
0109 Popcount64(uint64_t x) noexcept {
0110 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll)
0111   static_assert(sizeof(unsigned long long) == sizeof(x),  // NOLINT(runtime/int)
0112                 "__builtin_popcount does not take 64-bit arg");
0113   return __builtin_popcountll(x);
0114 #else
0115   x -= (x >> 1) & 0x5555555555555555ULL;
0116   x = ((x >> 2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL);
0117   return static_cast<int>(
0118       (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56);
0119 #endif
0120 }
0121
0122 template <class T>
0123 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
0124 Popcount(T x) noexcept {
0125   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
0126   static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
0127                 "T must have a power-of-2 size");
0128   static_assert(sizeof(x) <= sizeof(uint64_t), "T is too large");
0129   return sizeof(x) <= sizeof(uint32_t) ? Popcount32(x) : Popcount64(x);
0130 }
0131
0132 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
0133 CountLeadingZeroes32(uint32_t x) {
0134 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz)
0135   // Use __builtin_clz, which uses the following instructions:
0136   //  x86: bsr, lzcnt
0137   //  ARM64: clz
0138   //  PPC: cntlzd
0139
0140   static_assert(sizeof(unsigned int) == sizeof(x),
0141                 "__builtin_clz does not take 32-bit arg");
0142   // Handle 0 as a special case because __builtin_clz(0) is undefined.
0143   return x == 0 ? 32 : __builtin_clz(x);
0144 #elif defined(_MSC_VER) && !defined(__clang__)
0145   unsigned long result = 0;  // NOLINT(runtime/int)
0146   if (_BitScanReverse(&result, x)) {
0147     return 31 - result;
0148   }
0149   return 32;
0150 #else
0151   int zeroes = 28;
0152   if (x >> 16) {
0153     zeroes -= 16;
0154     x >>= 16;
0155   }
0156   if (x >> 8) {
0157     zeroes -= 8;
0158     x >>= 8;
0159   }
0160   if (x >> 4) {
0161     zeroes -= 4;
0162     x >>= 4;
0163   }
0164   return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
0165 #endif
0166 }
0167
0168 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
0169 CountLeadingZeroes16(uint16_t x) {
0170 #if ABSL_HAVE_BUILTIN(__builtin_clzg)
0171   return x == 0 ? 16 : __builtin_clzg(x);
0172 #elif ABSL_HAVE_BUILTIN(__builtin_clzs)
0173   static_assert(sizeof(unsigned short) == sizeof(x),  // NOLINT(runtime/int)
0174                 "__builtin_clzs does not take 16-bit arg");
0175   return x == 0 ? 16 : __builtin_clzs(x);
0176 #else
0177   return CountLeadingZeroes32(x) - 16;
0178 #endif
0179 }
0180
0181 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
0182 CountLeadingZeroes64(uint64_t x) {
0183 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll)
0184   // Use __builtin_clzll, which uses the following instructions:
0185   //  x86: bsr, lzcnt
0186   //  ARM64: clz
0187   //  PPC: cntlzd
0188   static_assert(sizeof(unsigned long long) == sizeof(x),  // NOLINT(runtime/int)
0189                 "__builtin_clzll does not take 64-bit arg");
0190
0191   // Handle 0 as a special case because __builtin_clzll(0) is undefined.
0192   return x == 0 ? 64 : __builtin_clzll(x);
0193 #elif defined(_MSC_VER) && !defined(__clang__) && \
0194     (defined(_M_X64) || defined(_M_ARM64))
0195   // MSVC does not have __buitin_clzll. Use _BitScanReverse64.
0196   unsigned long result = 0;  // NOLINT(runtime/int)
0197   if (_BitScanReverse64(&result, x)) {
0198     return 63 - result;
0199   }
0200   return 64;
0201 #elif defined(_MSC_VER) && !defined(__clang__)
0202   // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse
0203   unsigned long result = 0;  // NOLINT(runtime/int)
0204   if ((x >> 32) &&
0205       _BitScanReverse(&result, static_cast<unsigned long>(x >> 32))) {
0206     return 31 - result;
0207   }
0208   if (_BitScanReverse(&result, static_cast<unsigned long>(x))) {
0209     return 63 - result;
0210   }
0211   return 64;
0212 #else
0213   int zeroes = 60;
0214   if (x >> 32) {
0215     zeroes -= 32;
0216     x >>= 32;
0217   }
0218   if (x >> 16) {
0219     zeroes -= 16;
0220     x >>= 16;
0221   }
0222   if (x >> 8) {
0223     zeroes -= 8;
0224     x >>= 8;
0225   }
0226   if (x >> 4) {
0227     zeroes -= 4;
0228     x >>= 4;
0229   }
0230   return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
0231 #endif
0232 }
0233
0234 template <typename T>
0235 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
0236 CountLeadingZeroes(T x) {
0237   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
0238   static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
0239                 "T must have a power-of-2 size");
0240   static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
0241   return sizeof(T) <= sizeof(uint16_t)
0242              ? CountLeadingZeroes16(static_cast<uint16_t>(x)) -
0243                    (std::numeric_limits<uint16_t>::digits -
0244                     std::numeric_limits<T>::digits)
0245              : (sizeof(T) <= sizeof(uint32_t)
0246                     ? CountLeadingZeroes32(static_cast<uint32_t>(x)) -
0247                           (std::numeric_limits<uint32_t>::digits -
0248                            std::numeric_limits<T>::digits)
0249                     : CountLeadingZeroes64(x));
0250 }
0251
0252 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
0253 CountTrailingZeroesNonzero32(uint32_t x) {
0254 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz)
0255   static_assert(sizeof(unsigned int) == sizeof(x),
0256                 "__builtin_ctz does not take 32-bit arg");
0257   return __builtin_ctz(x);
0258 #elif defined(_MSC_VER) && !defined(__clang__)
0259   unsigned long result = 0;  // NOLINT(runtime/int)
0260   _BitScanForward(&result, x);
0261   return result;
0262 #else
0263   int c = 31;
0264   x &= ~x + 1;
0265   if (x & 0x0000FFFF) c -= 16;
0266   if (x & 0x00FF00FF) c -= 8;
0267   if (x & 0x0F0F0F0F) c -= 4;
0268   if (x & 0x33333333) c -= 2;
0269   if (x & 0x55555555) c -= 1;
0270   return c;
0271 #endif
0272 }
0273
0274 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
0275 CountTrailingZeroesNonzero64(uint64_t x) {
0276 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll)
0277   static_assert(sizeof(unsigned long long) == sizeof(x),  // NOLINT(runtime/int)
0278                 "__builtin_ctzll does not take 64-bit arg");
0279   return __builtin_ctzll(x);
0280 #elif defined(_MSC_VER) && !defined(__clang__) && \
0281     (defined(_M_X64) || defined(_M_ARM64))
0282   unsigned long result = 0;  // NOLINT(runtime/int)
0283   _BitScanForward64(&result, x);
0284   return result;
0285 #elif defined(_MSC_VER) && !defined(__clang__)
0286   unsigned long result = 0;  // NOLINT(runtime/int)
0287   if (static_cast<uint32_t>(x) == 0) {
0288     _BitScanForward(&result, static_cast<unsigned long>(x >> 32));
0289     return result + 32;
0290   }
0291   _BitScanForward(&result, static_cast<unsigned long>(x));
0292   return result;
0293 #else
0294   int c = 63;
0295   x &= ~x + 1;
0296   if (x & 0x00000000FFFFFFFF) c -= 32;
0297   if (x & 0x0000FFFF0000FFFF) c -= 16;
0298   if (x & 0x00FF00FF00FF00FF) c -= 8;
0299   if (x & 0x0F0F0F0F0F0F0F0F) c -= 4;
0300   if (x & 0x3333333333333333) c -= 2;
0301   if (x & 0x5555555555555555) c -= 1;
0302   return c;
0303 #endif
0304 }
0305
0306 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
0307 CountTrailingZeroesNonzero16(uint16_t x) {
0308 #if ABSL_HAVE_BUILTIN(__builtin_ctzg)
0309   return __builtin_ctzg(x);
0310 #elif ABSL_HAVE_BUILTIN(__builtin_ctzs)
0311   static_assert(sizeof(unsigned short) == sizeof(x),  // NOLINT(runtime/int)
0312                 "__builtin_ctzs does not take 16-bit arg");
0313   return __builtin_ctzs(x);
0314 #else
0315   return CountTrailingZeroesNonzero32(x);
0316 #endif
0317 }
0318
0319 template <class T>
0320 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
0321 CountTrailingZeroes(T x) noexcept {
0322   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
0323   static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
0324                 "T must have a power-of-2 size");
0325   static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
0326   return x == 0 ? std::numeric_limits<T>::digits
0327                 : (sizeof(T) <= sizeof(uint16_t)
0328                        ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x))
0329                        : (sizeof(T) <= sizeof(uint32_t)
0330                               ? CountTrailingZeroesNonzero32(
0331                                     static_cast<uint32_t>(x))
0332                               : CountTrailingZeroesNonzero64(x)));
0333 }
0334
0335 // If T is narrower than unsigned, T{1} << bit_width will be promoted.  We
0336 // want to force it to wraparound so that bit_ceil of an invalid value are not
0337 // core constant expressions.
0338 template <class T>
0339 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline
0340     typename std::enable_if<std::is_unsigned<T>::value, T>::type
0341     BitCeilPromotionHelper(T x, T promotion) {
0342   return (T{1} << (x + promotion)) >> promotion;
0343 }
0344
0345 template <class T>
0346 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline
0347     typename std::enable_if<std::is_unsigned<T>::value, T>::type
0348     BitCeilNonPowerOf2(T x) {
0349   // If T is narrower than unsigned, it undergoes promotion to unsigned when we
0350   // shift.  We calculate the number of bits added by the wider type.
0351   return BitCeilPromotionHelper(
0352       static_cast<T>(std::numeric_limits<T>::digits - CountLeadingZeroes(x)),
0353       T{sizeof(T) >= sizeof(unsigned) ? 0
0354                                       : std::numeric_limits<unsigned>::digits -
0355                                             std::numeric_limits<T>::digits});
0356 }
0357
0358 }  // namespace numeric_internal
0359 ABSL_NAMESPACE_END
0360 }  // namespace absl
0361
0362 #endif  // ABSL_NUMERIC_INTERNAL_BITS_H_