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