packed_value_block.h

#pragma once
 
#include <pixie/permutations/detail/packed_bit_block.h>
 
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <limits>
#include <span>
#include <stdexcept>
#include <type_traits>

namespace pixie::permutations::detail {

template <class T,
          std::size_t StorageBits = 2048,
          std::size_t Width = std::numeric_limits<T>::digits,
          class BitStorage = PackedBitBlock<StorageBits>>
class PackedValueBlock {
  static_assert(std::is_integral_v<T> && std::is_unsigned_v<T> &&
                std::numeric_limits<T>::digits <= 64);
  static_assert(Width > 0 && Width <= std::numeric_limits<T>::digits);
  using Bits = BitStorage;
 
 public:
  using value_type = T;
  static constexpr std::size_t capacity = Bits::capacity / Width;
  static constexpr std::size_t width = Width;
  static constexpr std::size_t payload_offset_bytes =
      Bits::payload_offset_bytes;
  static constexpr std::size_t payload_alignment = Bits::payload_alignment;
  static_assert(capacity > 0);

  PackedValueBlock() noexcept {}
  explicit PackedValueBlock(std::span<const T> values) {
    if (values.size() > capacity) {
      throw std::invalid_argument("PackedValueBlock: input size");
    }
    typename Bits::Payload words;
    if constexpr (Width != 64) {
      words.fill(0);
    }
    for (std::size_t i = 0; i < values.size(); ++i) {
      if (static_cast<std::uint64_t>(values[i]) > field_max) {
        throw std::invalid_argument("PackedValueBlock: value width");
      }
      if constexpr (Width == 64) {
        words[i] = values[i];
      } else {
        encode(words, i, values[i]);
      }
    }
    bits_ = Bits(words, values.size() * Width);
  }
  std::size_t size() const noexcept { return bits_.size() / Width; }
  bool empty() const noexcept { return bits_.empty(); }
  T operator[](std::size_t i) const {
    if (i >= size()) {
      throw std::out_of_range("PackedValueBlock: index");
    }
    return read_unchecked(i);
  }
  T read_unchecked(std::size_t i) const noexcept {
    assert(i < size());
    if constexpr (Width == 1) {
      return static_cast<T>(bits_[i]);
    } else if constexpr (Width == 64) {
      return static_cast<T>(bits_.read_normalized_word(i * 64));
    } else {
      return static_cast<T>(bits_.read_bits(i * Width, Width));
    }
  }
  void set_at(std::size_t i, T value) noexcept {
    assert(i < size() && static_cast<std::uint64_t>(value) <= field_max);
    if constexpr (Width == 64) {
      bits_.write_aligned_word(i * Width, value);
    } else {
      bits_.write_bits(i * Width, Width, value);
    }
  }
  void rotate_left(std::size_t left,
                   std::size_t right,
                   std::size_t distance) noexcept {
    assert(left <= right && right <= size());
    if constexpr (Width == 1) {
      bits_.rotate_left(left, right, distance);
    } else if (left != right) {
      bits_.rotate_left(left * Width, right * Width,
                        (distance % (right - left)) * Width);
      if constexpr (Width == 64) {
        bits_.normalize();
      }
    }
  }
  void insert_at(std::size_t offset, T value) noexcept {
    assert(offset <= size() && size() < capacity);
    typename Bits::Payload words{};
    const auto n = size();
    if constexpr (Width == 64) {
      for (std::size_t i = 0; i < n; ++i) {
        words[i] = bits_.read_aligned_word(i * 64);
      }
      std::memmove(words.data() + offset + 1, words.data() + offset,
                   (n - offset) * sizeof(std::uint64_t));
      words[offset] = static_cast<std::uint64_t>(value);
    } else {
      for (std::size_t i = 0; i < offset; ++i) {
        encode(words, i, bits_.read_bits(i * Width, Width));
      }
      encode(words, offset, value);
      for (std::size_t i = offset; i < n; ++i) {
        encode(words, i + 1, bits_.read_bits(i * Width, Width));
      }
    }
    bits_ = Bits(words, (n + 1) * Width);
  }
  void redistribute(PackedValueBlock& rhs, std::size_t left_size) noexcept {
    assert(this != &rhs && left_size <= capacity &&
           left_size <= size() + rhs.size() &&
           size() + rhs.size() - left_size <= capacity);
    bits_.redistribute(rhs.bits_, left_size * Width);
  }
  void add_bias(std::uint64_t bias) noexcept {
    typename Bits::Payload words{};
    const auto n = size();
    for (std::size_t i = 0; i < n; ++i) {
      const auto value = bits_.read_bits(i * Width, Width);
      assert(bias <= field_max && value <= field_max - bias);
      encode(words, i, value + bias);
    }
    bits_ = Bits(words, n * Width);
  }
  std::size_t payload_capacity_bytes() const noexcept {
    return bits_.payload_capacity_bytes();
  }
  std::size_t metadata_bytes() const noexcept { return bits_.metadata_bytes(); }
 
 private:
  static constexpr std::uint64_t field_max =
      std::numeric_limits<std::uint64_t>::max() >> (64 - Width);
  static void encode(typename Bits::Payload& words,
                     std::size_t i,
                     std::uint64_t value) noexcept {
    const auto bit = i * Width;
    const auto shift = bit % 64;
    words[bit / 64] |= value << shift;
    if (Width > 64 - shift) {
      words[bit / 64 + 1] |= value >> (64 - shift);
    }
  }
  Bits bits_;
};
 
}  // namespace pixie::permutations::detail