#include <cstdint>
#include <type_traits>
+#include "rocksdb/rocksdb_namespace.h"
+
namespace ROCKSDB_NAMESPACE {
// Fast implementation of floor(log2(v)). Undefined for 0 or negative
#endif
}
+// Constexpr version of FloorLog2
+template <typename T>
+constexpr int ConstexprFloorLog2(T v) {
+ int rv = 0;
+ while (v > T{1}) {
+ ++rv;
+ v >>= 1;
+ }
+ return rv;
+}
+
// Number of low-order zero bits before the first 1 bit. Undefined for 0.
template <typename T>
inline int CountTrailingZeroBits(T v) {
#endif
}
-#if defined(_MSC_VER) && !defined(_M_X64)
+// Not all MSVC compile settings will use `BitsSetToOneFallback()`. We include
+// the following code at coarse granularity for simpler macros. It's important
+// to exclude at least so our non-MSVC unit test coverage tool doesn't see it.
+#ifdef _MSC_VER
+
namespace detail {
+
template <typename T>
int BitsSetToOneFallback(T v) {
const int kBits = static_cast<int>(sizeof(T)) * 8;
static_assert((kBits & (kBits - 1)) == 0, "must be power of two bits");
// we static_cast these bit patterns in order to truncate them to the correct
- // size
+ // size. Warning C4309 dislikes this technique, so disable it here.
+#pragma warning(disable : 4309)
v = static_cast<T>(v - ((v >> 1) & static_cast<T>(0x5555555555555555ull)));
v = static_cast<T>((v & static_cast<T>(0x3333333333333333ull)) +
((v >> 2) & static_cast<T>(0x3333333333333333ull)));
v = static_cast<T>((v + (v >> 4)) & static_cast<T>(0x0F0F0F0F0F0F0F0Full));
+#pragma warning(default : 4309)
for (int shift_bits = 8; shift_bits < kBits; shift_bits <<= 1) {
v += static_cast<T>(v >> shift_bits);
}
}
} // namespace detail
-#endif
+
+#endif // _MSC_VER
// Number of bits set to 1. Also known as "population count".
template <typename T>
constexpr auto mm = 8 * sizeof(uint32_t) - 1;
// The bit mask is to neutralize sign extension on small signed types
constexpr uint32_t m = (uint32_t{1} << ((8 * sizeof(T)) & mm)) - 1;
-#if defined(_M_X64) || defined(_M_IX86)
+#if defined(HAVE_SSE42) && (defined(_M_X64) || defined(_M_IX86))
return static_cast<int>(__popcnt(static_cast<uint32_t>(v) & m));
#else
return static_cast<int>(detail::BitsSetToOneFallback(v) & m);
#endif
} else if (sizeof(T) == sizeof(uint32_t)) {
-#if defined(_M_X64) || defined(_M_IX86)
+#if defined(HAVE_SSE42) && (defined(_M_X64) || defined(_M_IX86))
return static_cast<int>(__popcnt(static_cast<uint32_t>(v)));
#else
return detail::BitsSetToOneFallback(static_cast<uint32_t>(v));
#endif
} else {
-#ifdef _M_X64
+#if defined(HAVE_SSE42) && defined(_M_X64)
return static_cast<int>(__popcnt64(static_cast<uint64_t>(v)));
-#elif defined(_M_IX86)
+#elif defined(HAVE_SSE42) && defined(_M_IX86)
return static_cast<int>(
__popcnt(static_cast<uint32_t>(static_cast<uint64_t>(v) >> 32) +
__popcnt(static_cast<uint32_t>(v))));
#endif
}
+// Swaps between big and little endian. Can be used in combination with the
+// little-endian encoding/decoding functions in coding_lean.h and coding.h to
+// encode/decode big endian.
+template <typename T>
+inline T EndianSwapValue(T v) {
+ static_assert(std::is_integral<T>::value, "non-integral type");
+
+#ifdef _MSC_VER
+ if (sizeof(T) == 2) {
+ return static_cast<T>(_byteswap_ushort(static_cast<uint16_t>(v)));
+ } else if (sizeof(T) == 4) {
+ return static_cast<T>(_byteswap_ulong(static_cast<uint32_t>(v)));
+ } else if (sizeof(T) == 8) {
+ return static_cast<T>(_byteswap_uint64(static_cast<uint64_t>(v)));
+ }
+#else
+ if (sizeof(T) == 2) {
+ return static_cast<T>(__builtin_bswap16(static_cast<uint16_t>(v)));
+ } else if (sizeof(T) == 4) {
+ return static_cast<T>(__builtin_bswap32(static_cast<uint32_t>(v)));
+ } else if (sizeof(T) == 8) {
+ return static_cast<T>(__builtin_bswap64(static_cast<uint64_t>(v)));
+ }
+#endif
+ // Recognized by clang as bswap, but not by gcc :(
+ T ret_val = 0;
+ for (std::size_t i = 0; i < sizeof(T); ++i) {
+ ret_val |= ((v >> (8 * i)) & 0xff) << (8 * (sizeof(T) - 1 - i));
+ }
+ return ret_val;
+}
+
+// Reverses the order of bits in an integral value
+template <typename T>
+inline T ReverseBits(T v) {
+ T r = EndianSwapValue(v);
+ const T kHighestByte = T{1} << ((sizeof(T) - 1) * 8);
+ const T kEveryByte = kHighestByte | (kHighestByte / 255);
+
+ r = ((r & (kEveryByte * 0x0f)) << 4) | ((r >> 4) & (kEveryByte * 0x0f));
+ r = ((r & (kEveryByte * 0x33)) << 2) | ((r >> 2) & (kEveryByte * 0x33));
+ r = ((r & (kEveryByte * 0x55)) << 1) | ((r >> 1) & (kEveryByte * 0x55));
+
+ return r;
+}
+
+// Every output bit depends on many input bits in the same and higher
+// positions, but not lower positions. Specifically, this function
+// * Output highest bit set to 1 is same as input (same FloorLog2, or
+// equivalently, same number of leading zeros)
+// * Is its own inverse (an involution)
+// * Guarantees that b bottom bits of v and c bottom bits of
+// DownwardInvolution(v) uniquely identify b + c bottom bits of v
+// (which is all of v if v < 2**(b + c)).
+// ** A notable special case is that modifying c adjacent bits at
+// some chosen position in the input is bijective with the bottom c
+// output bits.
+// * Distributes over xor, as in DI(a ^ b) == DI(a) ^ DI(b)
+//
+// This transformation is equivalent to a matrix*vector multiplication in
+// GF(2) where the matrix is recursively defined by the pattern matrix
+// P = | 1 1 |
+// | 0 1 |
+// and replacing 1's with P and 0's with 2x2 zero matices to some depth,
+// e.g. depth of 6 for 64-bit T. An essential feature of this matrix
+// is that all square sub-matrices that include the top row are invertible.
+template <typename T>
+inline T DownwardInvolution(T v) {
+ static_assert(std::is_integral<T>::value, "non-integral type");
+ static_assert(sizeof(T) <= 8, "only supported up to 64 bits");
+
+ uint64_t r = static_cast<uint64_t>(v);
+ if constexpr (sizeof(T) > 4) {
+ r ^= r >> 32;
+ }
+ if constexpr (sizeof(T) > 2) {
+ r ^= (r & 0xffff0000ffff0000U) >> 16;
+ }
+ if constexpr (sizeof(T) > 1) {
+ r ^= (r & 0xff00ff00ff00ff00U) >> 8;
+ }
+ r ^= (r & 0xf0f0f0f0f0f0f0f0U) >> 4;
+ r ^= (r & 0xccccccccccccccccU) >> 2;
+ r ^= (r & 0xaaaaaaaaaaaaaaaaU) >> 1;
+ return static_cast<T>(r);
+}
+
} // namespace ROCKSDB_NAMESPACE
projects / ceph.git / blobdiff