bit.h

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <bit>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <rex/platform.h>
#include <rex/types.h>
 
namespace rex {

template <typename T>
constexpr bool is_pow2(T value) {
  return (value & (value - 1)) == 0;
}

template <typename T>
T next_pow2(T value) {
  value--;
  value |= value >> 1;
  value |= value >> 2;
  value |= value >> 4;
  value |= value >> 8;
  value |= value >> 16;
  value++;
  return value;
}

constexpr u32 MakeBitmask(u32 a, u32 b) {
  return (static_cast<u32>(-1) >> (31 - b)) & ~((1u << a) - 1);
}

constexpr u32 select_bits(u32 value, u32 a, u32 b) {
  return (value & MakeBitmask(a, b)) >> a;
}

template <class T>
constexpr u32 BitCount(T v) {
  return static_cast<u32>(std::popcount(v));
}

inline u8 lzcnt(u8 v) {
  return static_cast<u8>(std::countl_zero(v));
}

inline u8 lzcnt(u16 v) {
  return static_cast<u8>(std::countl_zero(v));
}

inline u8 lzcnt(u32 v) {
  return static_cast<u8>(std::countl_zero(v));
}

inline u8 lzcnt(u64 v) {
  return static_cast<u8>(std::countl_zero(v));
}

inline u8 tzcnt(u8 v) {
  return static_cast<u8>(std::countr_zero(v));
}

inline u8 tzcnt(u16 v) {
  return static_cast<u8>(std::countr_zero(v));
}

inline u8 tzcnt(u32 v) {
  return static_cast<u8>(std::countr_zero(v));
}

inline u8 tzcnt(u64 v) {
  return static_cast<u8>(std::countr_zero(v));
}

inline u8 lzcnt(i8 v) {
  return lzcnt(static_cast<u8>(v));
}

inline u8 lzcnt(i16 v) {
  return lzcnt(static_cast<u16>(v));
}

inline u8 lzcnt(i32 v) {
  return lzcnt(static_cast<u32>(v));
}

inline u8 lzcnt(i64 v) {
  return lzcnt(static_cast<u64>(v));
}

inline u8 tzcnt(i8 v) {
  return tzcnt(static_cast<u8>(v));
}

inline u8 tzcnt(i16 v) {
  return tzcnt(static_cast<u16>(v));
}

inline u8 tzcnt(i32 v) {
  return tzcnt(static_cast<u32>(v));
}

inline u8 tzcnt(i64 v) {
  return tzcnt(static_cast<u64>(v));
}

inline bool bit_scan_forward(u32 v, u32* out_first_set_index) {
  if (v == 0) {
    return false;
  }
  *out_first_set_index = static_cast<u32>(std::countr_zero(v));
  return true;
}

inline bool bit_scan_forward(u64 v, u32* out_first_set_index) {
  if (v == 0) {
    return false;
  }
  *out_first_set_index = static_cast<u32>(std::countr_zero(v));
  return true;
}

inline bool bit_scan_forward(i32 v, u32* out_first_set_index) {
  return bit_scan_forward(static_cast<u32>(v), out_first_set_index);
}

inline bool bit_scan_forward(i64 v, u32* out_first_set_index) {
  return bit_scan_forward(static_cast<u64>(v), out_first_set_index);
}

template <typename T>
inline T log2_floor(T v) {
  return sizeof(T) * 8 - 1 - lzcnt(v);
}

template <typename T>
inline T log2_ceil(T v) {
  return sizeof(T) * 8 - lzcnt(v - 1);
}

template <typename T>
inline T RotateLeft(T v, u8 sh) {
  return (v << sh) | (v >> ((sizeof(T) * 8) - sh));
}

class REX_API BitMap {
 public:
  BitMap();

  BitMap(size_t size_bits);

  BitMap(u64* data, size_t size_bits);

  size_t AcquireEntry();

  void ReleaseEntry(size_t index);

  void Resize(size_t new_size_bits);
 
  void Reset();

  const std::vector<u64> GetWords() const { return data_; }
 
  std::vector<u64>& GetWords() { return data_; }
 
 private:
  const static size_t kDataSize = 8;
  const static size_t kDataSizeBits = kDataSize * 8;
  std::vector<u64> data_;
};

template <typename Block>
std::pair<size_t, size_t> GetNextRangeUnset(const Block* bits, size_t first, size_t length) {
  if (!length) {
    return std::make_pair(first, static_cast<size_t>(0));
  }
  size_t last = first + length - 1;
  const size_t block_bits = sizeof(Block) * CHAR_BIT;
  size_t block_first = first / block_bits;
  size_t block_last = last / block_bits;
  size_t range_start = SIZE_MAX;
  for (size_t i = block_first; i <= block_last; ++i) {
    Block block = bits[i];
    if (i == block_first) {
      block |= (Block(1) << (first & (block_bits - 1))) - 1;
    }
    if (i == block_last && (last & (block_bits - 1)) != block_bits - 1) {
      block |= ~((Block(1) << ((last & (block_bits - 1)) + 1)) - 1);
    }
    while (true) {
      u32 block_bit;
      if (range_start == SIZE_MAX) {
        if (!rex::bit_scan_forward(~block, &block_bit)) {
          break;
        }
        range_start = i * block_bits + block_bit;
      } else {
        Block block_bits_set_from_start = block;
        if (i == range_start / block_bits) {
          block_bits_set_from_start &= ~((Block(1) << (range_start & (block_bits - 1))) - 1);
        }
        if (!rex::bit_scan_forward(block_bits_set_from_start, &block_bit)) {
          break;
        }
        return std::make_pair(range_start, (i * block_bits) + block_bit - range_start);
      }
    }
  }
  if (range_start != SIZE_MAX) {
    return std::make_pair(range_start, last + static_cast<size_t>(1) - range_start);
  }
  return std::make_pair(first + length, static_cast<size_t>(0));
}

template <typename Block>
void SetRange(Block* bits, size_t first, size_t length) {
  if (!length) {
    return;
  }
  size_t last = first + length - 1;
  const size_t block_bits = sizeof(Block) * CHAR_BIT;
  size_t block_first = first / block_bits;
  size_t block_last = last / block_bits;
  Block set_first = ~((Block(1) << (first & (block_bits - 1))) - 1);
  Block set_last = ~Block(0);
  if ((last & (block_bits - 1)) != (block_bits - 1)) {
    set_last &= (Block(1) << ((last & (block_bits - 1)) + 1)) - 1;
  }
  if (block_first == block_last) {
    bits[block_first] |= set_first & set_last;
    return;
  }
  bits[block_first] |= set_first;
  if (block_first + 1 < block_last) {
    std::fill_n(bits + block_first + 1, block_last - (block_first + 1), ~Block(0));
  }
  bits[block_last] |= set_last;
}

template <typename E>
inline constexpr bool is_flags_enum = false;

template <typename E>
concept FlagsEnum = std::is_enum_v<E> && is_flags_enum<E>;
 
template <FlagsEnum E>
[[nodiscard]] constexpr E operator|(E lhs, E rhs) {
  return static_cast<E>(std::to_underlying(lhs) | std::to_underlying(rhs));
}
 
template <FlagsEnum E>
[[nodiscard]] constexpr E operator&(E lhs, E rhs) {
  return static_cast<E>(std::to_underlying(lhs) & std::to_underlying(rhs));
}
 
template <FlagsEnum E>
[[nodiscard]] constexpr E operator^(E lhs, E rhs) {
  return static_cast<E>(std::to_underlying(lhs) ^ std::to_underlying(rhs));
}
 
template <FlagsEnum E>
[[nodiscard]] constexpr E operator~(E value) {
  return static_cast<E>(~std::to_underlying(value));
}

template <FlagsEnum E>
constexpr E& operator|=(E& lhs, E rhs) {
  lhs = lhs | rhs;
  return lhs;
}

template <FlagsEnum E>
constexpr E& operator&=(E& lhs, E rhs) {
  lhs = lhs & rhs;
  return lhs;
}

template <FlagsEnum E>
constexpr E& operator^=(E& lhs, E rhs) {
  lhs = lhs ^ rhs;
  return lhs;
}

template <FlagsEnum E>
[[nodiscard]] constexpr bool HasFlags(E value, E flags) {
  return (value & flags) == flags;
}

#define REX_RESTRICT_VAR __restrict

template <typename Dst, typename Src>
void Reinterpret(Dst& REX_RESTRICT_VAR dst, const Src& REX_RESTRICT_VAR src) {
  static_assert(sizeof(Dst) == sizeof(Src));
  static_assert(std::is_trivially_copyable_v<Dst>);
  static_assert(std::is_trivially_copyable_v<Src>);
  dst = std::bit_cast<Dst>(src);
}

template <typename Dst, typename Src>
Dst Reinterpret(const Src& REX_RESTRICT_VAR src) {
  Dst dst;
  Reinterpret(dst, src);
  return dst;
}

inline bool AreBitsEqual(std::span<const f32> a, std::span<const f32> b) {
  return std::ranges::equal(
      a, b, [](f32 x, f32 y) { return std::bit_cast<u32>(x) == std::bit_cast<u32>(y); });
}
 
}  // namespace rex