util/yet_another_bit_vector.cc

// Copyright 2019 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "util/yet_another_bit_vector.h"

#include <algorithm>
#include <utility>

#include "util/osp_logging.h"

namespace openscreen {

namespace {

// Returns a bitmask where all the bits whose positions are in the range
// [begin,begin+count) are set, and all other bits are cleared.
constexpr uint64_t MakeBitmask(int begin, int count) {
  // Form a contiguous sequence of bits by subtracting one from the appropriate
  // power of 2. Set all the bits if count >= 64.
  const uint64_t bits_in_wrong_position =
      (count >= std::numeric_limits<uint64_t>::digits)
          ? std::numeric_limits<uint64_t>::max()
          : ((uint64_t{1} << count) - 1);

  // Now shift the contiguous sequence of bits into the correct position.
  return bits_in_wrong_position << begin;
}

}  // namespace

YetAnotherBitVector::YetAnotherBitVector() : size_(0), bits_{.as_integer = 0} {}

YetAnotherBitVector::YetAnotherBitVector(int size,
                                         YetAnotherBitVector::Fill fill) {
  InitializeForNewSize(size, fill);
}

YetAnotherBitVector::~YetAnotherBitVector() {
  if (using_array_storage()) {
    delete[] bits_.as_array;
  }
}

YetAnotherBitVector::YetAnotherBitVector(YetAnotherBitVector&& other)
    : size_(other.size_), bits_(other.bits_) {
  other.size_ = 0;
  other.bits_.as_integer = 0;
}

YetAnotherBitVector& YetAnotherBitVector::operator=(
    YetAnotherBitVector&& other) {
  if (this == &other) {
    return *this;
  }
  if (using_array_storage()) {
    delete[] bits_.as_array;
  }
  size_ = other.size_;
  bits_ = other.bits_;
  other.size_ = 0;
  other.bits_.as_integer = 0;
  return *this;
}

bool YetAnotherBitVector::IsSet(int pos) const {
  OSP_DCHECK_LT(pos, size_);
  const uint64_t* const elem = Select(&pos);
  return (*elem & (uint64_t{1} << pos)) != 0;
}

void YetAnotherBitVector::Set(int pos) {
  OSP_DCHECK_LT(pos, size_);
  uint64_t* const elem = const_cast<uint64_t*>(Select(&pos));
  *elem |= (uint64_t{1} << pos);
}

void YetAnotherBitVector::Clear(int pos) {
  OSP_DCHECK_LT(pos, size_);
  uint64_t* const elem = const_cast<uint64_t*>(Select(&pos));
  *elem &= ~(uint64_t{1} << pos);
}

void YetAnotherBitVector::Resize(int new_size, YetAnotherBitVector::Fill fill) {
  if (using_array_storage()) {
    delete[] bits_.as_array;
  }
  InitializeForNewSize(new_size, fill);
}

void YetAnotherBitVector::SetAll() {
  // Implementation note: Set all bits except those in the last integer that are
  // outside the defined range. This allows the other operations to become
  // simpler and more efficient because they can assume the bits moving into the
  // valid range are not set.

  if (using_array_storage()) {
    const int last_index = array_size() - 1;
    uint64_t* const last = &bits_.as_array[last_index];
    std::fill(&bits_.as_array[0], last, kAllBitsSet);
    *last = MakeBitmask(0, size_ - (last_index * kBitsPerInteger));
  } else {
    bits_.as_integer = MakeBitmask(0, size_);
  }
}

void YetAnotherBitVector::ClearAll() {
  if (using_array_storage()) {
    std::fill(&bits_.as_array[0], &bits_.as_array[array_size()], kNoBitsSet);
  } else {
    bits_.as_integer = kNoBitsSet;
  }
}

void YetAnotherBitVector::ShiftRight(int steps) {
  // Negative |steps| should probably mean "shift left," but this is not
  // implemented.
  OSP_DCHECK_GE(steps, 0);
  OSP_DCHECK_LE(steps, size_);

  if (using_array_storage()) {
    // If |steps| is greater than one integer's worth of bits, first shift the
    // array elements right. This is effectively shifting all the bits right by
    // some multiple of 64.
    const int num_integers = array_size();
    if (steps >= kBitsPerInteger) {
      const int integer_steps = steps / kBitsPerInteger;
      for (int i = integer_steps; i < num_integers; ++i) {
        bits_.as_array[i - integer_steps] = bits_.as_array[i];
      }
      std::fill(&bits_.as_array[num_integers - integer_steps],
                &bits_.as_array[num_integers], kNoBitsSet);
      steps %= kBitsPerInteger;
    }

    // With |steps| now less than 64, shift the bits right within each array
    // element. Start from the back of the array, working towards the front, and
    // propagating any bits that are moving across array elements.
    uint64_t incoming_carry_bits = 0;
    const uint64_t outgoing_mask = MakeBitmask(0, steps);
    for (int i = num_integers; i-- > 0;) {
      const uint64_t outgoing_carry_bits = bits_.as_array[i] & outgoing_mask;
      bits_.as_array[i] >>= steps;
      bits_.as_array[i] |= (incoming_carry_bits << (kBitsPerInteger - steps));
      incoming_carry_bits = outgoing_carry_bits;
    }
  } else {
    if (steps < kBitsPerInteger) {
      bits_.as_integer >>= steps;
    } else {
      bits_.as_integer = 0;
    }
  }
}

int YetAnotherBitVector::FindFirstSet() const {
  // Almost all processors provide a single instruction to "count trailing
  // zeros" in an integer, which is great because this is the same as the
  // 0-based index of the first set bit. So, have the compiler use that
  // whenever it's available. However, note that the intrinsic (and the CPU
  // instruction used) provides undefined results when operating on zero; and
  // so that special case is checked and handled.
#if defined(__clang__) || defined(__GNUC__)
#define CountTrailingZeros(bits) __builtin_ctzll(bits)
#else
  const auto CountTrailingZeros = [](uint64_t bits) -> int {
    // Based on one of the public domain "Bit Twiddling Hacks" heuristics:
    // https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel
    // clang-format off
    bits &= ~bits + 1;
    int count = kBitsPerInteger;
    if (bits) --count;
    if (bits & UINT64_C(0x00000000ffffffff)) count -= 32;
    if (bits & UINT64_C(0x0000ffff0000ffff)) count -= 16;
    if (bits & UINT64_C(0x00ff00ff00ff00ff)) count -= 8;
    if (bits & UINT64_C(0x0f0f0f0f0f0f0f0f)) count -= 4;
    if (bits & UINT64_C(0x3333333333333333)) count -= 2;
    if (bits & UINT64_C(0x5555555555555555)) count -= 1;
    return count;
    // clang-format on
  };
#endif

  if (using_array_storage()) {
    for (int i = 0, end = array_size(); i < end; ++i) {
      if (bits_.as_array[i] != 0) {
        return (i * kBitsPerInteger) + CountTrailingZeros(bits_.as_array[i]);
      }
    }
    return size_;  // All bits are not set.
  }
  return (bits_.as_integer != 0) ? CountTrailingZeros(bits_.as_integer) : size_;
}

int YetAnotherBitVector::CountBitsSet(int begin, int end) const {
  OSP_DCHECK_LE(0, begin);
  OSP_DCHECK_LE(begin, end);
  OSP_DCHECK_LE(end, size_);

  // Almost all processors provide a single instruction to "count the number of
  // bits set" in an integer. So, have the compiler use that whenever it's
  // available.
#if defined(__clang__) || defined(__GNUC__)
#define PopCount(bits) __builtin_popcountll(bits)
#else
  const auto PopCount = [](uint64_t bits) -> int {
    // Based on one of the public domain "Bit Twiddling Hacks" heuristics:
    // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    constexpr int kBitsPerByte = 8;
    bits = bits - ((bits >> 1) & (kAllBitsSet / 3));
    bits = (bits & (kAllBitsSet / 15 * 3)) +
           ((bits >> 2) & (kAllBitsSet / 15 * 3));
    bits = (bits + (bits >> 4)) & (kAllBitsSet / 255 * 15);
    const uint64_t count =
        (bits * (kAllBitsSet / 255)) >> ((sizeof(uint64_t) - 1) * kBitsPerByte);
    return static_cast<int>(count);
  };
#endif

  int count;
  if (using_array_storage()) {
    const int first = begin / kBitsPerInteger;
    const int last = (end - 1) / kBitsPerInteger;
    if (first == last) {
      count = PopCount(bits_.as_array[first] &
                       MakeBitmask(begin % kBitsPerInteger, end - begin));
    } else if (first < last) {
      // Count a subset of the bits in the first and last integers (according to
      // |begin| and |end|), and all of the bits in the integers in-between.
      const uint64_t* p = &bits_.as_array[first];
      count = PopCount((*p) &
                       MakeBitmask(begin % kBitsPerInteger, kBitsPerInteger));
      for (++p; p != &bits_.as_array[last]; ++p) {
        count += PopCount(*p);
      }
      count += PopCount((*p) & MakeBitmask(0, end - (last * kBitsPerInteger)));
    } else {
      count = 0;
    }
  } else {
    count = PopCount(bits_.as_integer & MakeBitmask(begin, end - begin));
  }
  return count;
}

void YetAnotherBitVector::InitializeForNewSize(int new_size, Fill fill) {
  OSP_DCHECK_GE(new_size, 0);
  size_ = new_size;
  if (using_array_storage()) {
    bits_.as_array = new uint64_t[array_size()];
  }
  if (fill == SET) {
    SetAll();
  } else {
    ClearAll();
  }
}

const uint64_t* YetAnotherBitVector::Select(int* pos) const {
  if (using_array_storage()) {
    const int index = *pos / kBitsPerInteger;
    *pos %= kBitsPerInteger;
    return &bits_.as_array[index];
  }
  return &bits_.as_integer;
}

// NOTE: These declarations can be removed when C++17 compliance is mandatory
// for all embedders, as static constexpr members can be declared inline.
constexpr int YetAnotherBitVector::kBitsPerInteger;
constexpr uint64_t YetAnotherBitVector::kAllBitsSet;
constexpr uint64_t YetAnotherBitVector::kNoBitsSet;

}  // namespace openscreen