X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FBits.h;h=b818655e2a347c6d301a7723fa0bf823c0ed1970;hb=49399f7cf36dfdda58e1bc01f2c9a1bc7a4ed400;hp=a88e6349254dd30269447b34ec587d7136124007;hpb=9284f39b8b851dfbe8d8dd514def166fd454982e;p=folly.git diff --git a/folly/Bits.h b/folly/Bits.h index a88e6349..b818655e 100644 --- a/folly/Bits.h +++ b/folly/Bits.h @@ -1,5 +1,5 @@ /* - * Copyright 2012 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -52,27 +52,27 @@ * @author Tudor Bosman (tudorb@fb.com) */ -#ifndef FOLLY_BITS_H_ -#define FOLLY_BITS_H_ +#pragma once -#include "folly/Portability.h" - -#ifndef _GNU_SOURCE -#define _GNU_SOURCE 1 +#if !defined(__clang__) && !(defined(_MSC_VER) && (_MSC_VER < 1900)) +#define FOLLY_INTRINSIC_CONSTEXPR constexpr +#else +// GCC and MSVC 2015+ are the only compilers with +// intrinsics constexpr. +#define FOLLY_INTRINSIC_CONSTEXPR const #endif -#ifndef __GNUC__ -#error GCC required -#endif +#include +#include -#include "folly/detail/BitsDetail.h" -#include "folly/detail/BitIteratorDetail.h" -#include "folly/Likely.h" +#include +#include +#include +#include -#include #include +#include #include -#include #include #include #include @@ -84,18 +84,18 @@ namespace folly { // Generate overloads for findFirstSet as wrappers around // appropriate ffs, ffsl, ffsll gcc builtins template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_unsigned::value && sizeof(T) <= sizeof(unsigned int)), unsigned int>::type findFirstSet(T x) { - return __builtin_ffs(x); + return static_cast(__builtin_ffs(static_cast(x))); } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_unsigned::value && @@ -103,11 +103,11 @@ typename std::enable_if< sizeof(T) <= sizeof(unsigned long)), unsigned int>::type findFirstSet(T x) { - return __builtin_ffsl(x); + return static_cast(__builtin_ffsl(static_cast(x))); } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_unsigned::value && @@ -115,11 +115,11 @@ typename std::enable_if< sizeof(T) <= sizeof(unsigned long long)), unsigned int>::type findFirstSet(T x) { - return __builtin_ffsll(x); + return static_cast(__builtin_ffsll(static_cast(x))); } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_signed::value), unsigned int>::type @@ -133,18 +133,20 @@ typename std::enable_if< // findLastSet: return the 1-based index of the highest bit set // for x > 0, findLastSet(x) == 1 + floor(log2(x)) template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_unsigned::value && sizeof(T) <= sizeof(unsigned int)), unsigned int>::type findLastSet(T x) { - return x ? 8 * sizeof(unsigned int) - __builtin_clz(x) : 0; + // If X is a power of two X - Y = ((X - 1) ^ Y) + 1. Doing this transformation + // allows GCC to remove its own xor that it adds to implement clz using bsr + return x ? ((8 * sizeof(unsigned int) - 1) ^ __builtin_clz(x)) + 1 : 0; } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_unsigned::value && @@ -152,11 +154,11 @@ typename std::enable_if< sizeof(T) <= sizeof(unsigned long)), unsigned int>::type findLastSet(T x) { - return x ? 8 * sizeof(unsigned long) - __builtin_clzl(x) : 0; + return x ? ((8 * sizeof(unsigned long) - 1) ^ __builtin_clzl(x)) + 1 : 0; } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_unsigned::value && @@ -164,11 +166,12 @@ typename std::enable_if< sizeof(T) <= sizeof(unsigned long long)), unsigned int>::type findLastSet(T x) { - return x ? 8 * sizeof(unsigned long long) - __builtin_clzll(x) : 0; + return x ? ((8 * sizeof(unsigned long long) - 1) ^ __builtin_clzll(x)) + 1 + : 0; } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< (std::is_integral::value && std::is_signed::value), @@ -178,19 +181,25 @@ typename std::enable_if< } template -inline constexpr +inline FOLLY_INTRINSIC_CONSTEXPR typename std::enable_if< std::is_integral::value && std::is_unsigned::value, T>::type nextPowTwo(T v) { - return v ? (1ul << findLastSet(v - 1)) : 1; + return v ? (T(1) << findLastSet(v - 1)) : 1; } template -inline constexpr -typename std::enable_if< - std::is_integral::value && std::is_unsigned::value, - bool>::type +inline FOLLY_INTRINSIC_CONSTEXPR typename std:: + enable_if::value && std::is_unsigned::value, T>::type + prevPowTwo(T v) { + return v ? (T(1) << (findLastSet(v) - 1)) : 0; +} + +template +inline constexpr typename std::enable_if< + std::is_integral::value && std::is_unsigned::value, + bool>::type isPowTwo(T v) { return (v != 0) && !(v & (v - 1)); } @@ -205,7 +214,7 @@ inline typename std::enable_if< sizeof(T) <= sizeof(unsigned int)), size_t>::type popcount(T x) { - return detail::popcount(x); + return size_t(detail::popcount(x)); } template @@ -216,7 +225,7 @@ inline typename std::enable_if< sizeof(T) <= sizeof(unsigned long long)), size_t>::type popcount(T x) { - return detail::popcountll(x); + return size_t(detail::popcountll(x)); } /** @@ -224,50 +233,56 @@ inline typename std::enable_if< */ namespace detail { -template -struct EndianIntBase { - public: - static T swap(T x); -}; +template +struct uint_types_by_size; -#define FB_GEN(t, fn) \ -template<> inline t EndianIntBase::swap(t x) { return fn(x); } +#define FB_GEN(sz, fn) \ + static inline uint##sz##_t byteswap_gen(uint##sz##_t v) { \ + return fn(v); \ + } \ + template <> \ + struct uint_types_by_size { \ + using type = uint##sz##_t; \ + }; -// fn(x) expands to (x) if the second argument is empty, which is exactly -// what we want for [u]int8_t -FB_GEN( int8_t,) -FB_GEN(uint8_t,) -FB_GEN( int64_t, bswap_64) -FB_GEN(uint64_t, bswap_64) -FB_GEN( int32_t, bswap_32) -FB_GEN(uint32_t, bswap_32) -FB_GEN( int16_t, bswap_16) -FB_GEN(uint16_t, bswap_16) +FB_GEN(8, uint8_t) +#ifdef _MSC_VER +FB_GEN(64, _byteswap_uint64) +FB_GEN(32, _byteswap_ulong) +FB_GEN(16, _byteswap_ushort) +#else +FB_GEN(64, __builtin_bswap64) +FB_GEN(32, __builtin_bswap32) +FB_GEN(16, __builtin_bswap16) +#endif #undef FB_GEN -#if __BYTE_ORDER == __LITTLE_ENDIAN - -template -struct EndianInt : public detail::EndianIntBase { - public: - static T big(T x) { return EndianInt::swap(x); } - static T little(T x) { return x; } -}; - -#elif __BYTE_ORDER == __BIG_ENDIAN - template -struct EndianInt : public detail::EndianIntBase { - public: - static T big(T x) { return x; } - static T little(T x) { return EndianInt::swap(x); } +struct EndianInt { + static_assert( + (std::is_integral::value && !std::is_same::value) || + std::is_floating_point::value, + "template type parameter must be non-bool integral or floating point"); + static T swap(T x) { + // we implement this with memcpy because that is defined behavior in C++ + // we rely on compilers to optimize away the memcpy calls + constexpr auto s = sizeof(T); + using B = typename uint_types_by_size::type; + B b; + std::memcpy(&b, &x, s); + b = byteswap_gen(b); + std::memcpy(&x, &b, s); + return x; + } + static T big(T x) { + return kIsLittleEndian ? EndianInt::swap(x) : x; + } + static T little(T x) { + return kIsBigEndian ? EndianInt::swap(x) : x; + } }; -#else -# error Your machine uses a weird endianness! -#endif /* __BYTE_ORDER */ - } // namespace detail // big* convert between native and big-endian representations @@ -295,29 +310,24 @@ class Endian { BIG }; - static constexpr Order order = -#if __BYTE_ORDER == __LITTLE_ENDIAN - Order::LITTLE; -#elif __BYTE_ORDER == __BIG_ENDIAN - Order::BIG; -#else -# error Your machine uses a weird endianness! -#endif /* __BYTE_ORDER */ + static constexpr Order order = kIsLittleEndian ? Order::LITTLE : Order::BIG; template static T swap(T x) { - return detail::EndianInt::swap(x); + return folly::detail::EndianInt::swap(x); } template static T big(T x) { - return detail::EndianInt::big(x); + return folly::detail::EndianInt::big(x); } template static T little(T x) { - return detail::EndianInt::little(x); + return folly::detail::EndianInt::little(x); } +#if !defined(__ANDROID__) FB_GEN(64) FB_GEN(32) FB_GEN(16) FB_GEN(8) +#endif }; #undef FB_GEN @@ -346,7 +356,7 @@ class BitIterator /** * Return the number of bits in an element of the underlying iterator. */ - static size_t bitsPerBlock() { + static unsigned int bitsPerBlock() { return std::numeric_limits< typename std::make_unsigned< typename std::iterator_traits::value_type @@ -358,9 +368,9 @@ class BitIterator * Construct a BitIterator that points at a given bit offset (default 0) * in iter. */ - explicit BitIterator(const BaseIter& iter, size_t bitOffset=0) + explicit BitIterator(const BaseIter& iter, size_t bitOff=0) : bititerator_detail::BitIteratorBase::type(iter), - bitOffset_(bitOffset) { + bitOffset_(bitOff) { assert(bitOffset_ < bitsPerBlock()); } @@ -399,7 +409,7 @@ class BitIterator void advance(ssize_t n) { size_t bpb = bitsPerBlock(); - ssize_t blocks = n / bpb; + ssize_t blocks = n / ssize_t(bpb); bitOffset_ += n % bpb; if (bitOffset_ >= bpb) { bitOffset_ -= bpb; @@ -427,12 +437,12 @@ class BitIterator } ssize_t distance_to(const BitIterator& other) const { - return - (other.base_reference() - this->base_reference()) * bitsPerBlock() + - (other.bitOffset_ - bitOffset_); + return ssize_t( + (other.base_reference() - this->base_reference()) * bitsPerBlock() + + other.bitOffset_ - bitOffset_); } - ssize_t bitOffset_; + size_t bitOffset_; }; /** @@ -494,6 +504,7 @@ template struct Unaligned; /** * Representation of an unaligned value of a POD type. */ +FOLLY_PACK_PUSH template struct Unaligned< T, @@ -501,7 +512,8 @@ struct Unaligned< Unaligned() = default; // uninitialized /* implicit */ Unaligned(T v) : value(v) { } T value; -} __attribute__((packed)); +} FOLLY_PACK_ATTR; +FOLLY_PACK_POP /** * Read an unaligned value of type T and return it. @@ -510,7 +522,13 @@ template inline T loadUnaligned(const void* p) { static_assert(sizeof(Unaligned) == sizeof(T), "Invalid unaligned size"); static_assert(alignof(Unaligned) == 1, "Invalid alignment"); - return static_cast*>(p)->value; + if (kHasUnalignedAccess) { + return static_cast*>(p)->value; + } else { + T value; + memcpy(&value, p, sizeof(T)); + return value; + } } /** @@ -520,10 +538,17 @@ template inline void storeUnaligned(void* p, T value) { static_assert(sizeof(Unaligned) == sizeof(T), "Invalid unaligned size"); static_assert(alignof(Unaligned) == 1, "Invalid alignment"); - new (p) Unaligned(value); + if (kHasUnalignedAccess) { + // Prior to C++14, the spec says that a placement new like this + // is required to check that p is not nullptr, and to do nothing + // if p is a nullptr. By assuming it's not a nullptr, we get a + // nice loud segfault in optimized builds if p is nullptr, rather + // than just silently doing nothing. + folly::assume(p != nullptr); + new (p) Unaligned(value); + } else { + memcpy(p, &value, sizeof(T)); + } } } // namespace folly - -#endif /* FOLLY_BITS_H_ */ -