1 //  Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 
6 #pragma once
7 
8 #include <assert.h>
9 #ifdef _MSC_VER
10 #include <intrin.h>
11 #endif
12 
13 #include <cstdint>
14 #include <type_traits>
15 
16 namespace ROCKSDB_NAMESPACE {
17 
18 // Fast implementation of floor(log2(v)). Undefined for 0 or negative
19 // numbers (in case of signed type).
20 template <typename T>
FloorLog2(T v)21 inline int FloorLog2(T v) {
22   static_assert(std::is_integral<T>::value, "non-integral type");
23   assert(v > 0);
24 #ifdef _MSC_VER
25   static_assert(sizeof(T) <= sizeof(uint64_t), "type too big");
26   unsigned long idx = 0;
27   if (sizeof(T) <= sizeof(uint32_t)) {
28     _BitScanReverse(&idx, static_cast<uint32_t>(v));
29   } else {
30 #if defined(_M_X64) || defined(_M_ARM64)
31     _BitScanReverse64(&idx, static_cast<uint64_t>(v));
32 #else
33     const auto vh = static_cast<uint32_t>(static_cast<uint64_t>(v) >> 32);
34     if (vh != 0) {
35       _BitScanReverse(&idx, static_cast<uint32_t>(vh));
36       idx += 32;
37     } else {
38       _BitScanReverse(&idx, static_cast<uint32_t>(v));
39     }
40 #endif
41   }
42   return idx;
43 #else
44   static_assert(sizeof(T) <= sizeof(unsigned long long), "type too big");
45   if (sizeof(T) <= sizeof(unsigned int)) {
46     int lz = __builtin_clz(static_cast<unsigned int>(v));
47     return int{sizeof(unsigned int)} * 8 - 1 - lz;
48   } else if (sizeof(T) <= sizeof(unsigned long)) {
49     int lz = __builtin_clzl(static_cast<unsigned long>(v));
50     return int{sizeof(unsigned long)} * 8 - 1 - lz;
51   } else {
52     int lz = __builtin_clzll(static_cast<unsigned long long>(v));
53     return int{sizeof(unsigned long long)} * 8 - 1 - lz;
54   }
55 #endif
56 }
57 
58 // Number of low-order zero bits before the first 1 bit. Undefined for 0.
59 template <typename T>
CountTrailingZeroBits(T v)60 inline int CountTrailingZeroBits(T v) {
61   static_assert(std::is_integral<T>::value, "non-integral type");
62   assert(v != 0);
63 #ifdef _MSC_VER
64   static_assert(sizeof(T) <= sizeof(uint64_t), "type too big");
65   unsigned long tz = 0;
66   if (sizeof(T) <= sizeof(uint32_t)) {
67     _BitScanForward(&tz, static_cast<uint32_t>(v));
68   } else {
69 #if defined(_M_X64) || defined(_M_ARM64)
70     _BitScanForward64(&tz, static_cast<uint64_t>(v));
71 #else
72     _BitScanForward(&tz, static_cast<uint32_t>(v));
73     if (tz == 0) {
74       _BitScanForward(&tz,
75                       static_cast<uint32_t>(static_cast<uint64_t>(v) >> 32));
76       tz += 32;
77     }
78 #endif
79   }
80   return static_cast<int>(tz);
81 #else
82   static_assert(sizeof(T) <= sizeof(unsigned long long), "type too big");
83   if (sizeof(T) <= sizeof(unsigned int)) {
84     return __builtin_ctz(static_cast<unsigned int>(v));
85   } else if (sizeof(T) <= sizeof(unsigned long)) {
86     return __builtin_ctzl(static_cast<unsigned long>(v));
87   } else {
88     return __builtin_ctzll(static_cast<unsigned long long>(v));
89   }
90 #endif
91 }
92 
93 #if defined(_MSC_VER) && !defined(_M_X64)
94 namespace detail {
95 template <typename T>
BitsSetToOneFallback(T v)96 int BitsSetToOneFallback(T v) {
97   const int kBits = static_cast<int>(sizeof(T)) * 8;
98   static_assert((kBits & (kBits - 1)) == 0, "must be power of two bits");
99   // we static_cast these bit patterns in order to truncate them to the correct
100   // size
101   v = static_cast<T>(v - ((v >> 1) & static_cast<T>(0x5555555555555555ull)));
102   v = static_cast<T>((v & static_cast<T>(0x3333333333333333ull)) +
103                      ((v >> 2) & static_cast<T>(0x3333333333333333ull)));
104   v = static_cast<T>((v + (v >> 4)) & static_cast<T>(0x0F0F0F0F0F0F0F0Full));
105   for (int shift_bits = 8; shift_bits < kBits; shift_bits <<= 1) {
106     v += static_cast<T>(v >> shift_bits);
107   }
108   // we want the bottom "slot" that's big enough to represent a value up to
109   // (and including) kBits.
110   return static_cast<int>(v & static_cast<T>(kBits | (kBits - 1)));
111 }
112 
113 }  // namespace detail
114 #endif
115 
116 // Number of bits set to 1. Also known as "population count".
117 template <typename T>
BitsSetToOne(T v)118 inline int BitsSetToOne(T v) {
119   static_assert(std::is_integral<T>::value, "non-integral type");
120 #ifdef _MSC_VER
121   static_assert(sizeof(T) <= sizeof(uint64_t), "type too big");
122   if (sizeof(T) < sizeof(uint32_t)) {
123     // This bit mask is to avoid a compiler warning on unused path
124     constexpr auto mm = 8 * sizeof(uint32_t) - 1;
125     // The bit mask is to neutralize sign extension on small signed types
126     constexpr uint32_t m = (uint32_t{1} << ((8 * sizeof(T)) & mm)) - 1;
127 #if defined(_M_X64) || defined(_M_IX86)
128     return static_cast<int>(__popcnt(static_cast<uint32_t>(v) & m));
129 #else
130     return static_cast<int>(detail::BitsSetToOneFallback(v) & m);
131 #endif
132   } else if (sizeof(T) == sizeof(uint32_t)) {
133 #if defined(_M_X64) || defined(_M_IX86)
134     return static_cast<int>(__popcnt(static_cast<uint32_t>(v)));
135 #else
136     return detail::BitsSetToOneFallback(static_cast<uint32_t>(v));
137 #endif
138   } else {
139 #ifdef _M_X64
140     return static_cast<int>(__popcnt64(static_cast<uint64_t>(v)));
141 #elif defined(_M_IX86)
142     return static_cast<int>(
143         __popcnt(static_cast<uint32_t>(static_cast<uint64_t>(v) >> 32) +
144                  __popcnt(static_cast<uint32_t>(v))));
145 #else
146     return detail::BitsSetToOneFallback(static_cast<uint64_t>(v));
147 #endif
148   }
149 #else
150   static_assert(sizeof(T) <= sizeof(unsigned long long), "type too big");
151   if (sizeof(T) < sizeof(unsigned int)) {
152     // This bit mask is to avoid a compiler warning on unused path
153     constexpr auto mm = 8 * sizeof(unsigned int) - 1;
154     // This bit mask is to neutralize sign extension on small signed types
155     constexpr unsigned int m = (1U << ((8 * sizeof(T)) & mm)) - 1;
156     return __builtin_popcount(static_cast<unsigned int>(v) & m);
157   } else if (sizeof(T) == sizeof(unsigned int)) {
158     return __builtin_popcount(static_cast<unsigned int>(v));
159   } else if (sizeof(T) <= sizeof(unsigned long)) {
160     return __builtin_popcountl(static_cast<unsigned long>(v));
161   } else {
162     return __builtin_popcountll(static_cast<unsigned long long>(v));
163   }
164 #endif
165 }
166 
167 template <typename T>
BitParity(T v)168 inline int BitParity(T v) {
169   static_assert(std::is_integral<T>::value, "non-integral type");
170 #ifdef _MSC_VER
171   // bit parity == oddness of popcount
172   return BitsSetToOne(v) & 1;
173 #else
174   static_assert(sizeof(T) <= sizeof(unsigned long long), "type too big");
175   if (sizeof(T) <= sizeof(unsigned int)) {
176     // On any sane systen, potential sign extension here won't change parity
177     return __builtin_parity(static_cast<unsigned int>(v));
178   } else if (sizeof(T) <= sizeof(unsigned long)) {
179     return __builtin_parityl(static_cast<unsigned long>(v));
180   } else {
181     return __builtin_parityll(static_cast<unsigned long long>(v));
182   }
183 #endif
184 }
185 
186 }  // namespace ROCKSDB_NAMESPACE
187