bit_vector.h

Go to the documentation of this file.

// MIT License
//
// Copyright (c) 2019 Oleksandr Tkachenko
// Cryptography and Privacy Engineering Group (ENCRYPTO)
// TU Darmstadt, Germany
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
 
#pragma once
 
#include <cstddef>
#include <iostream>
#include <memory>
#include <random>
#include <string>
#include <vector>
 
#include <fmt/format.h>
#include <boost/align/aligned_allocator.hpp>
 
#include "config.h"
#include "helpers.h"
 
namespace encrypto::motion {
 
// bitmask to set a specific bit in a byte
constexpr std::byte kSetBitMask[] = {
    std::byte(0b10000000), std::byte(0b01000000), std::byte(0b00100000), std::byte(0b00010000),
    std::byte(0b00001000), std::byte(0b00000100), std::byte(0b00000010), std::byte(0b00000001)};
 
// bitmask to unset a specific bit in a byte
constexpr std::byte kUnsetBitMask[] = {
    std::byte(0b01111111), std::byte(0b10111111), std::byte(0b11011111), std::byte(0b11101111),
    std::byte(0b11110111), std::byte(0b11111011), std::byte(0b11111101), std::byte(0b11111110)};
 
// bitmask to truncate the a byte
constexpr std::byte TruncationBitMask[] = {
    std::byte(0b10000000), std::byte(0b11000000), std::byte(0b11100000), std::byte(0b111110000),
    std::byte(0b11111000), std::byte(0b11111100), std::byte(0b11111110), std::byte(0b11111111)};
 
class BitSpan;
 
using StdAllocator = std::allocator<std::byte>;
using AlignedAllocator = boost::alignment::aligned_allocator<std::byte, kAlignment>;
 
template <typename Allocator = std::allocator<std::byte>>
class BitVector {
  template <typename OtherAllocator>
  friend class BitVector;
  friend class BitSpan;
 
 public:
  // Default constructor, results in an empty vector
  BitVector() noexcept : bit_size_(0){};
 
  // Move constructor
  BitVector(BitVector&& bit_vector) noexcept
      : data_vector_(std::move(bit_vector.data_vector_)), bit_size_(bit_vector.bit_size_) {}
 
  // XXX Copy and Move constructor/assigment can be defaulted
 
  // Copy constructor
  BitVector(const BitVector& bit_vector) noexcept
      : data_vector_(bit_vector.data_vector_), bit_size_(bit_vector.bit_size_) {}
 
  // Copy assignment
  BitVector<Allocator>& operator=(const BitVector<Allocator>& other) noexcept;
 
  // Move assignment
  BitVector<Allocator>& operator=(BitVector<Allocator>&& other) noexcept;
 
  template <typename OtherAllocator>
  BitVector(const BitVector<OtherAllocator>& bit_vector) noexcept
      : data_vector_(bit_vector.data_vector_.cbegin(), bit_vector.data_vector_.cend()),
        bit_size_(bit_vector.bit_size_) {}
 
  template <typename OtherAllocator>
  BitVector<Allocator>& operator=(const BitVector<OtherAllocator>& other) noexcept;
 
  BitVector(const std::vector<bool>& data) : BitVector(data, data.size()) {}
 
  explicit BitVector(const std::vector<bool>& data, std::size_t number_of_bits);
 
  explicit BitVector(std::size_t number_of_bits, bool value = false) noexcept;
 
  BitVector(const unsigned char* buffer, std::size_t bits)
      : BitVector(reinterpret_cast<const std::byte*>(buffer), bits) {}
 
  BitVector(const std::byte* buffer, std::size_t bits);
 
  template <typename OtherAllocator>
  explicit BitVector(const std::vector<std::byte, OtherAllocator>& data,
                     std::size_t number_of_bits);
 
  explicit BitVector(std::vector<std::byte, Allocator>&& data, std::size_t number_of_bits);
 
  bool Empty() const { return bit_size_ == 0; }
 
  auto GetSize() const noexcept { return bit_size_; }
 
  const auto& GetData() const noexcept { return data_vector_; }
 
  auto& GetMutableData() noexcept { return data_vector_; }
 
  void Assign(const BitVector& other) noexcept { *this = other; }
 
  void Assign(BitVector&& other) noexcept { *this = std::move(other); }
 
  void Set(bool value) noexcept;
 
  void Set(bool value, std::size_t position);
 
  bool Get(std::size_t position) const;
 
  void Resize(std::size_t number_of_bits, bool zero_fill = false) noexcept;
 
  void Reserve(std::size_t number_of_bits) { data_vector_.reserve(BitsToBytes(number_of_bits)); }
 
  void Append(bool bit) noexcept;
 
  void Append(const BitVector<Allocator>& other) noexcept;
 
  void Append(BitVector&& other) noexcept;
 
  void Append(const BitSpan& other);
 
  void Append(BitSpan&& other);
 
  void Append(const std::byte* pointer, const std::size_t append_bit_size) noexcept;
 
  void Copy(const std::size_t dest_from, const std::size_t dest_to, const BitVector& other);
 
  void Copy(const std::size_t dest_from, const BitVector& other);
 
  BitVector Subset(std::size_t from, std::size_t to) const;
 
  std::string AsString() const noexcept;
 
  void Clear() noexcept;
 
  void Invert();
 
  bool operator[](std::size_t position) const { return Get(position); }
 
  BitVector operator~() const;
 
  template <typename OtherAllocator>
  BitVector operator&(const BitVector<OtherAllocator>& other) const noexcept;
 
  BitVector operator&(const BitSpan& other) const noexcept;
 
  template <typename OtherAllocator>
  BitVector operator^(const BitVector<OtherAllocator>& other) const noexcept;
 
  BitVector operator^(const BitSpan& other) const noexcept;
 
  template <typename OtherAllocator>
  BitVector operator|(const BitVector<OtherAllocator>& other) const noexcept;
 
  BitVector operator|(const BitSpan& other) const noexcept;
 
  template <typename OtherAllocator>
  bool operator!=(const BitVector<OtherAllocator>& other) const noexcept;
 
  bool operator!=(const BitSpan& other) const noexcept;
 
  template <typename OtherAllocator>
  bool operator==(const BitVector<OtherAllocator>& other) const noexcept;
 
  bool operator==(const BitSpan& other) const noexcept;
 
  template <typename OtherAllocator>
  BitVector& operator&=(const BitVector<OtherAllocator>& other) noexcept;
 
  BitVector& operator&=(const BitSpan& other) noexcept;
 
  template <typename OtherAllocator>
  BitVector& operator^=(const BitVector<OtherAllocator>& other) noexcept;
 
  BitVector& operator^=(const BitSpan& other) noexcept;
 
  template <typename OtherAllocator>
  BitVector& operator|=(const BitVector<OtherAllocator>& other) noexcept;
 
  BitVector& operator|=(const BitSpan& other) noexcept;
 
  static BitVector SecureRandom(const std::size_t size) noexcept;
 
  static BitVector RandomSeeded(const std::size_t size, const std::size_t seed = 0) noexcept;
 
  static bool OrReduceBitVector(const BitVector& bit_vector);
 
  static BitVector OrBitVectors(const std::vector<BitVector>& bit_vectors);
 
  static bool AndReduceBitVector(const BitVector& bit_vector);
 
  static BitVector AndBitVectors(const std::vector<BitVector>& bit_vectors);
 
  static std::vector<BitVector> AndBitVectors(const std::vector<BitVector>& a,
                                              const std::vector<BitVector>& b);
 
  static std::vector<BitVector> AndBitVectors(
      const std::vector<std::vector<BitVector>>& bit_vectors);
 
  static bool XorReduceBitVector(const BitVector& bit_vector);
 
  static BitVector XorBitVectors(const std::vector<BitVector>& bit_vectors);
 
  static std::vector<BitVector> XorBitVectors(const std::vector<BitVector>& a,
                                              const std::vector<BitVector>& b);
 
  static std::vector<BitVector> XorBitVectors(
      const std::vector<std::vector<BitVector>>& bit_vectors);
 
  static bool IsEqualSizeDimensions(const std::vector<BitVector>& bit_vectors);
 
  static constexpr bool IsAligned() noexcept { return std::is_same_v<Allocator, AlignedAllocator>; }
 
 private:
  std::vector<std::byte, Allocator> data_vector_;
 
  std::size_t bit_size_;
 
  void TruncateToFit() noexcept;
 
  void BoundsCheckEquality([[maybe_unused]] const std::size_t bit_size) const;
 
  void BoundsCheckInRange([[maybe_unused]] const std::size_t bit_size) const;
};
 
template <typename Allocator>
std::ostream& operator<<(std::ostream& os, const BitVector<Allocator>& bit_vector) {
  return os << bit_vector.AsString();
}
 
// Input functions that convert inputs of integer and floating point types to vectors of
// BitVectors, which are a suitable input to MOTION.
 
template <typename T,
          typename = std::enable_if_t<std::is_floating_point_v<T> || std::is_unsigned_v<T>>,
          typename Allocator = std::allocator<std::byte>>
std::vector<BitVector<Allocator>> ToInput(T value);
 
template <typename T,
          typename = std::enable_if_t<std::is_floating_point_v<T> || std::is_unsigned_v<T>>,
          typename Allocator = std::allocator<std::byte>>
std::vector<BitVector<Allocator>> ToInput(const std::vector<T>& vector);
 
// Output functions for converting vectors of BitVectors to vectors of floating point or
// integer numbers
 
template <typename UnsignedIntegralType,
          typename = std::enable_if_t<std::is_unsigned_v<UnsignedIntegralType>>,
          typename Allocator = std::allocator<std::byte>>
UnsignedIntegralType ToOutput(std::vector<BitVector<Allocator>> bit_vectors) {
  static_assert(std::is_integral<UnsignedIntegralType>::value);
  static_assert(sizeof(UnsignedIntegralType) <= 8);
  if constexpr (sizeof(UnsignedIntegralType) == 1) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint8_t>);
  } else if constexpr (sizeof(UnsignedIntegralType) == 2) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint16_t>);
  } else if constexpr (sizeof(UnsignedIntegralType) == 4) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint32_t>);
  } else if constexpr (sizeof(UnsignedIntegralType) == 8) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint64_t>);
  }
 
  // kBitLength is always equal to bit_vectors
  constexpr auto kBitLength{sizeof(UnsignedIntegralType) * 8};
 
  assert(!bit_vectors.empty());
  if (kBitLength != bit_vectors.size()) {
    throw std::runtime_error(
        fmt::format("Trying to convert to different bitlength: is {}, expected {}",
                    bit_vectors.size(), kBitLength));
  }
 
  const auto number_of_simd{bit_vectors.at(0).GetSize()};
  assert(number_of_simd > 0u);
  for ([[maybe_unused]] auto i = 0ull; i < bit_vectors.size(); ++i)
    assert(bit_vectors.at(i).GetSize() == number_of_simd);
 
  UnsignedIntegralType output_value{0};
  // Converting values in a BitVector to UnsignedIntegralType
  for (auto i = 0ull; i < kBitLength; ++i) {
    assert(bit_vectors.at(i).GetSize() == 1);
    output_value += static_cast<UnsignedIntegralType>(bit_vectors.at(i)[0]) << i;
  }
 
  return output_value;
}
 
template <typename UnsignedIntegralType,
          typename = std::enable_if_t<std::is_unsigned_v<UnsignedIntegralType>>,
          typename Allocator = std::allocator<std::byte>>
std::vector<UnsignedIntegralType> ToVectorOutput(std::vector<BitVector<Allocator>> bit_vectors) {
  static_assert(std::is_integral<UnsignedIntegralType>::value);
  static_assert(sizeof(UnsignedIntegralType) <= 8);
  if constexpr (sizeof(UnsignedIntegralType) == 1) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint8_t>);
  } else if constexpr (sizeof(UnsignedIntegralType) == 2) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint16_t>);
  } else if constexpr (sizeof(UnsignedIntegralType) == 4) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint32_t>);
  } else if constexpr (sizeof(UnsignedIntegralType) == 8) {
    static_assert(std::is_same_v<UnsignedIntegralType, std::uint64_t>);
  }
 
  constexpr auto kBitLength{sizeof(UnsignedIntegralType) * 8};
 
  assert(!bit_vectors.empty());
  if (kBitLength != bit_vectors.size()) {
    throw std::runtime_error(
        fmt::format("Trying to convert to different bitlength: is {}, expected {}",
                    bit_vectors.size(), kBitLength));
  }
 
  const auto number_of_simd{bit_vectors.at(0).GetSize()};
  assert(number_of_simd > 0u);
  for ([[maybe_unused]] auto i = 0ull; i < bit_vectors.size(); ++i)
    assert(bit_vectors.at(i).GetSize() == number_of_simd);
 
  // Converting values in a BitVector to a value of UnsignedIntegralType
  // Example: If the jth BitVector of size 3 is represented by the tuple: (xj, yj, zj)
  // Then output_vector[0] == x0*2^0 + x1*2^1 + ... + xn*2^n
  //     output_vector[1] == y0*2^0 + y1*2^1 + ... + yn*2^n
  //     output_vector[2] == z0*2^0 + z1*2^1 + ... + zn*2^n
  std::vector<UnsignedIntegralType> output_vector;
  for (auto i = 0ull; i < number_of_simd; ++i) {
    UnsignedIntegralType value{0};
    for (auto j = 0ull; j < kBitLength; ++j) {
      value += static_cast<UnsignedIntegralType>(bit_vectors.at(j)[i]) << j;
    }
    output_vector.emplace_back(value);
  }
  return output_vector;
}
 
using AlignedBitVector = BitVector<AlignedAllocator>;
 
class BitSpan {
 public:
  BitSpan() = default;
 
  ~BitSpan() = default;
 
  // XXX Copy and move constructor/assignment can be declared default.
  // XXX Assignments do not check for self-assignment.
  BitSpan(const BitSpan& other);
 
  BitSpan(BitSpan&& other);
 
  BitSpan& operator=(const BitSpan& other);
 
  BitSpan& operator=(BitSpan&& other);
 
  template <typename BitVectorType>
  BitSpan(BitVectorType& bit_vector)
      : pointer_(bit_vector.GetMutableData().data()),
        bit_size_(bit_vector.GetSize()),
        aligned_(bit_vector.IsAligned()) {}
 
  template <typename BitVectorType>
  BitSpan& operator=(BitVectorType& bit_vector) {
    pointer_ = bit_vector.GetMutableData().data();
    bit_size_ = bit_vector.GetSize();
    aligned_ = bit_vector.IsAligned();
    return *this;
  }
 
  BitSpan(std::byte* buffer, std::size_t bit_size, bool aligned = false);
 
  template <typename T>
  BitSpan(T* buffer, std::size_t bit_size, bool aligned = false)
      : pointer_(reinterpret_cast<std::byte*>(buffer)), bit_size_(bit_size), aligned_(aligned) {}
 
  // TODO make this a user-defined conversion.
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType As() const {
    return BitVectorType(pointer_, bit_size_);
  }
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType Subset(const std::size_t from, const std::size_t to) const;
 
  bool Empty() const noexcept { return bit_size_; }
 
  void Invert();
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator~() const {
    BitVectorType result(pointer_, bit_size_);
    result.Invert();
    return result;
  }
 
  template <typename BitVectorType = AlignedBitVector>
  bool operator==(const BitVectorType& other) const;
 
  bool operator==(const BitSpan& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator&(const BitVectorType& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator&(const BitSpan& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator|(const BitVectorType& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator|(const BitSpan& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator^(const BitVectorType& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitVectorType operator^(const BitSpan& other) const;
 
  template <typename BitVectorType = AlignedBitVector>
  BitSpan& operator&=(const BitVectorType& other);
 
  BitSpan& operator&=(const BitSpan& other);
 
  template <typename BitVectorType = AlignedBitVector>
  BitSpan& operator|=(const BitVectorType& other);
 
  BitSpan& operator|=(const BitSpan& other);
 
  template <typename BitVectorType = AlignedBitVector>
  BitSpan& operator^=(const BitVectorType& other);
 
  BitSpan& operator^=(const BitSpan& other);
 
  bool Get(const std::size_t position) const;
 
  bool operator[](const std::size_t position) const { return Get(position); }
 
  void Set(const bool value);
 
  void Set(const bool value, const std::size_t position);
 
  const std::byte* GetData() const noexcept { return pointer_; }
 
  std::byte* GetMutableData() noexcept { return pointer_; }
 
  std::size_t GetSize() const noexcept { return bit_size_; }
 
  std::string AsString() const noexcept;
 
  bool IsAligned() const noexcept { return aligned_; }
 
  template <typename BitVectorType>
  void Copy(const std::size_t dest_from, const std::size_t dest_to, BitVectorType& other);
 
  template <typename BitVectorType>
  void Copy(const std::size_t dest_from, BitVectorType& other);
 
  void Copy(const std::size_t dest_from, const std::size_t dest_to, BitSpan& other);
 
  void Copy(const std::size_t dest_from, const std::size_t dest_to, BitSpan&& other);
 
  void Copy(const std::size_t dest_from, BitSpan& other);
 
  void Copy(const std::size_t dest_from, BitSpan&& other);
 
 private:
  std::byte* pointer_;
  std::size_t bit_size_;
  bool aligned_;
};
 
std::ostream& operator<<(std::ostream& os, const BitSpan& bit_span);
 
}  // namespace encrypto::motion