bit_block.h

#pragma once
 
#include <pixie/bits.h>
#include <pixie/storage/aligned.h>
 
#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <stdexcept>

namespace pixie::permutations::detail {

template <std::size_t PayloadBits = 2048>
class alignas(CacheLine) BitBlock {
  static_assert(PayloadBits >= 64 && PayloadBits % 64 == 0);
  static_assert(PayloadBits <= std::numeric_limits<std::size_t>::max() / 2);
 
 public:
  using value_type = bool;
  static constexpr std::size_t capacity = PayloadBits;
  using Payload = std::array<std::uint64_t, PayloadBits / 64>;
  static constexpr std::size_t payload_offset_bytes = 2 * sizeof(std::uint64_t);
  static constexpr std::size_t payload_alignment = alignof(std::uint64_t);

  BitBlock() noexcept {}
  BitBlock(const BitBlock& other) noexcept : n_(other.n_), h_(other.h_) {
    std::copy_n(other.bits_.begin(), n_ / 64 + (n_ % 64 != 0), bits_.begin());
  }
  BitBlock& operator=(const BitBlock& other) noexcept {
    if (this != &other) {
      n_ = other.n_;
      h_ = other.h_;
      std::copy_n(other.bits_.begin(), n_ / 64 + (n_ % 64 != 0), bits_.begin());
    }
    return *this;
  }
  BitBlock(std::span<const std::uint64_t> words, std::size_t n) {
    if (n > capacity || n / 64 + (n % 64 != 0) > words.size()) {
      throw std::invalid_argument("BitBlock: input size");
    }
    n_ = n;
    std::copy_n(words.begin(), n / 64 + (n % 64 != 0), bits_.begin());
  }
  std::size_t size() const noexcept { return n_; }
  bool empty() const noexcept { return n_ == 0; }
  bool operator[](std::size_t i) const {
    if (i >= n_) {
      throw std::out_of_range("BitBlock: index");
    }
    const auto sum = h_ + i;
    const auto p = sum >= n_ ? sum - n_ : sum;
    return (bits_[p / 64] >> (p % 64)) & 1;
  }
  std::uint64_t read_bits(std::size_t offset,
                          std::size_t width) const noexcept {
    assert(offset <= n_ && width <= 64 && width <= n_ - offset);
    if (width == 0) {
      return 0;
    }
    // Both operands are below n_, and capacity <= SIZE_MAX / 2. The
    // circular sum cannot overflow and needs at most one subtraction.
    const auto sum = h_ + offset;
    const auto physical = sum >= n_ ? sum - n_ : sum;
    const auto first = std::min(width, n_ - physical);
    auto read = [&](std::size_t p, std::size_t count) {
      const auto shift = p % 64;
      auto value = bits_[p / 64] >> shift;
      if (count > 64 - shift) {
        value |= bits_[p / 64 + 1] << (64 - shift);
      }
      return count == 64 ? value : value & ((std::uint64_t{1} << count) - 1);
    };
    const auto value = read(physical, first);
    return first == width ? value : value | (read(0, width - first) << first);
  }
  std::uint64_t read_aligned_word(std::size_t offset) const noexcept {
    assert(n_ % 64 == 0 && h_ % 64 == 0 && offset % 64 == 0 && offset < n_);
    // The common normalized case has no metadata-dependent value address.
    if (h_ == 0) {
      return bits_[offset / 64];
    }
    const auto sum = h_ + offset;
    const auto physical = sum >= n_ ? sum - n_ : sum;
    return bits_[physical / 64];
  }
  void write_aligned_word(std::size_t offset, std::uint64_t value) noexcept {
    assert(n_ % 64 == 0 && h_ % 64 == 0 && offset % 64 == 0 && offset < n_);
    const auto sum = h_ + offset;
    bits_[(sum >= n_ ? sum - n_ : sum) / 64] = value;
  }
  void write_bits(std::size_t offset,
                  std::size_t width,
                  std::uint64_t value) noexcept {
    assert(offset <= n_ && width <= 64 && width <= n_ - offset);
    if (width == 0) {
      return;
    }
    const auto sum = h_ + offset;
    const auto p = sum >= n_ ? sum - n_ : sum;
    const auto first = std::min(width, n_ - p);
    copy_packed_bits(&value, 0, bits_.data(), p, first);
    copy_packed_bits(&value, first, bits_.data(), 0, width - first);
  }
  Payload flatten() const noexcept {
    Payload out{};
    copy(0, out, 0, n_);
    return out;
  }
  void rotate_left(std::size_t left,
                   std::size_t right,
                   std::size_t distance) noexcept {
    assert(left <= right && right <= n_);
    const auto length = right - left;
    if (length == 0 || (distance %= length) == 0) {
      return;
    }
    if (length == n_) {
      h_ = (h_ + distance) % n_;
      return;
    }
    Payload scratch{};
    copy(left + distance, scratch, 0, length - distance);
    copy(left, scratch, length - distance, distance);
    const auto p = (h_ + left) % n_;
    const auto prefix = std::min(length, n_ - p);
    copy_packed_bits(scratch.data(), 0, bits_.data(), p, prefix);
    copy_packed_bits(scratch.data(), prefix, bits_.data(), 0, length - prefix);
  }
  void redistribute(BitBlock& rhs, std::size_t left_size) noexcept {
    assert(this != &rhs);
    const auto total = n_ + rhs.n_;
    assert(left_size <= capacity && left_size <= total &&
           total - left_size <= capacity);
    if (left_size == total && h_ == 0) {
      // A normalized prefix stays in place when absorbing the whole donor.
      // Copy only the incoming bits, including a possibly circular donor.
      // Partial-word writes preserve destination padding, so initialize newly
      // exposed words before the copy kernel can read those padding bits.
      std::fill(bits_.begin() + n_ / 64 + (n_ % 64 != 0),
                bits_.begin() + total / 64 + (total % 64 != 0), 0);
      rhs.copy(0, bits_, n_, rhs.n_);
      n_ = total;
      rhs.n_ = rhs.h_ = 0;
      return;
    }
    Payload a{}, b{};
    auto gather = [&](std::size_t start, Payload& out, std::size_t count) {
      const auto first = start < n_ ? std::min(count, n_ - start) : 0;
      copy(start, out, 0, first);
      rhs.copy(start + first - std::min(start + first, n_), out, first,
               count - first);
    };
    gather(0, a, left_size);
    gather(left_size, b, total - left_size);
    bits_ = a;
    rhs.bits_ = b;
    n_ = left_size;
    rhs.n_ = total - left_size;
    h_ = rhs.h_ = 0;
  }
  void normalize() noexcept {
    if (h_ == 0) {
      return;
    }
    Payload scratch{};
    copy(0, scratch, 0, n_);
    bits_ = scratch;
    h_ = 0;
  }
  std::uint64_t read_normalized_word(std::size_t offset) const noexcept {
    assert(h_ == 0 && offset % 64 == 0 && offset <= n_ && n_ - offset >= 64);
    return bits_[offset / 64];
  }
  std::size_t payload_capacity_bytes() const noexcept { return sizeof(bits_); }
  std::size_t metadata_bytes() const noexcept {
    return sizeof(*this) - sizeof(bits_);
  }
 
 private:
  void copy(std::size_t offset,
            Payload& out,
            std::size_t destination,
            std::size_t count) const noexcept {
    if (count == 0) {
      return;
    }
    const auto p = (h_ + offset) % n_;
    const auto prefix = std::min(count, n_ - p);
    copy_packed_bits(bits_.data(), p, out.data(), destination, prefix);
    copy_packed_bits(bits_.data(), 0, out.data(), destination + prefix,
                     count - prefix);
  }
  std::uint64_t n_ = 0;
  std::uint64_t h_ = 0;
  Payload bits_;
};
 
}  // namespace pixie::permutations::detail