bitmath_func.hpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef BITMATH_FUNC_HPP
#define BITMATH_FUNC_HPP
 
template <typename T>
debug_inline constexpr static uint GB(const T x, const uint8_t s, const uint8_t n)
{
  return (x >> s) & (((T)1U << n) - 1);
}
 
template <typename T, typename U>
constexpr T SB(T &x, const uint8_t s, const uint8_t n, const U d)
{
  x &= (T)(~((((T)1U << n) - 1) << s));
  x |= (T)(d << s);
  return x;
}
 
template <typename T, typename U>
constexpr T AB(T &x, const uint8_t s, const uint8_t n, const U i)
{
  const T mask = ((((T)1U << n) - 1) << s);
  x = (T)((x & ~mask) | ((x + (i << s)) & mask));
  return x;
}
 
template <typename T>
debug_inline constexpr bool HasBit(const T x, const uint8_t y)
{
  return (x & ((T)1U << y)) != 0;
}
 
template <typename T>
constexpr T SetBit(T &x, const uint8_t y)
{
  return x = (T)(x | ((T)1U << y));
}
 
#define SETBITS(x, y) ((x) |= (y))
 
template <typename T>
constexpr T ClrBit(T &x, const uint8_t y)
{
  return x = (T)(x & ~((T)1U << y));
}
 
#define CLRBITS(x, y) ((x) &= ~(y))
 
template <typename T>
constexpr T ToggleBit(T &x, const uint8_t y)
{
  return x = (T)(x ^ ((T)1U << y));
}
 
template <typename T>
constexpr T AssignBit(T &x, const uint8_t y, bool value)
{
  return SB<T>(x, y, 1, value ? 1 : 0);
}
 
template <typename T>
constexpr uint8_t FindFirstBit(T x)
{
  if (x == 0) return 0;
 
  if constexpr (std::is_enum_v<T>) {
    return std::countr_zero<std::underlying_type_t<T>>(x);
  } else {
    return std::countr_zero(x);
  }
}
 
template <typename T>
constexpr uint8_t FindLastBit(T x)
{
  if (x == 0) return 0;
 
  return std::numeric_limits<T>::digits - std::countl_zero(x) - 1;
}
 
template <typename T>
constexpr T KillFirstBit(T value)
{
  return value &= (T)(value - 1);
}
 
template <typename T>
constexpr uint CountBits(T value)
{
  if constexpr (std::is_enum_v<T>) {
    return std::popcount<std::underlying_type_t<T>>(value);
  } else {
    return std::popcount(value);
  }
}
 
template <typename T>
constexpr bool HasExactlyOneBit(T value)
{
  return value != 0 && (value & (value - 1)) == 0;
}
 
template <typename T>
constexpr bool HasAtMostOneBit(T value)
{
  return (value & (value - 1)) == 0;
}
 
template <typename Tbitpos = uint, typename Tbitset = uint>
struct SetBitIterator {
  struct Iterator {
    typedef Tbitpos value_type;
    typedef value_type *pointer;
    typedef value_type &reference;
    typedef size_t difference_type;
    typedef std::forward_iterator_tag iterator_category;
 
    explicit Iterator(Tbitset bitset) : bitset(bitset), bitpos(static_cast<Tbitpos>(0))
    {
      this->Validate();
    }
 
    bool operator==(const Iterator &other) const
    {
      return this->bitset == other.bitset;
    }
    bool operator!=(const Iterator &other) const { return !(*this == other); }
    Tbitpos operator*() const { return this->bitpos; }
    Iterator & operator++() { this->Next(); this->Validate(); return *this; }
 
  private:
    Tbitset bitset;
    Tbitpos bitpos;
    void Validate()
    {
      if (this->bitset != 0) {
        typename std::make_unsigned<Tbitset>::type unsigned_value = this->bitset;
        this->bitpos = static_cast<Tbitpos>(FindFirstBit(unsigned_value));
      }
    }
    void Next()
    {
      this->bitset = KillFirstBit(this->bitset);
    }
  };
 
  SetBitIterator(Tbitset bitset) : bitset(bitset) {}
  Iterator begin() { return Iterator(this->bitset); }
  Iterator end() { return Iterator(static_cast<Tbitset>(0)); }
  bool empty() { return this->begin() == this->end(); }
 
private:
  Tbitset bitset;
};
 
#if defined(__APPLE__)
  /* Make endian swapping use Apple's macros to increase speed
   * (since it will use hardware swapping if available).
   * Even though they should return uint16_t and uint32_t, we get
   * warnings if we don't cast those (why?) */
# define BSWAP32(x) (static_cast<uint32_t>(CFSwapInt32(x)))
# define BSWAP16(x) (static_cast<uint16_t>(CFSwapInt16(x)))
#elif defined(_MSC_VER)
  /* MSVC has intrinsics for swapping, resulting in faster code */
# define BSWAP32(x) (_byteswap_ulong(x))
# define BSWAP16(x) (_byteswap_ushort(x))
#else
  static inline uint32_t BSWAP32(uint32_t x)
  {
#if !defined(__ICC) && defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4)  && __GNUC_MINOR__ >= 3))
    /* GCC >= 4.3 provides a builtin, resulting in faster code */
    return static_cast<uint32_t>(__builtin_bswap32(static_cast<int32_t>(x)));
#else
    return ((x >> 24) & 0xFF) | ((x >> 8) & 0xFF00) | ((x << 8) & 0xFF0000) | ((x << 24) & 0xFF000000);
#endif /* defined(__GNUC__) */
  }
 
  static inline uint16_t BSWAP16(uint16_t x)
  {
    return (x >> 8) | (x << 8);
  }
#endif /* __APPLE__ */
 
#endif /* BITMATH_FUNC_HPP */