BitField.h

Go to the documentation of this file.

//============================================================================
//  The contents of this file are covered by the Viskores license. See
//  LICENSE.txt for details.
//
//  By contributing to this file, all contributors agree to the Developer
//  Certificate of Origin Version 1.1 (DCO 1.1) as stated in DCO.txt.
//============================================================================
 
//============================================================================
//  Copyright (c) Kitware, Inc.
//  All rights reserved.
//  See LICENSE.txt for details.
//
//  This software is distributed WITHOUT ANY WARRANTY; without even
//  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
//  PURPOSE.  See the above copyright notice for more information.
//============================================================================
 
#ifndef viskores_cont_BitField_h
#define viskores_cont_BitField_h
 
#include <viskores/cont/ArrayHandle.h>
#include <viskores/cont/viskores_cont_export.h>
 
#include <viskores/Atomic.h>
#include <viskores/List.h>
#include <viskores/Types.h>
 
#include <cassert>
#include <climits>
#include <memory>
#include <type_traits>
 
namespace viskores
{
namespace cont
{
 
class BitField;
 
namespace internal
{
 
struct StorageTagBitField;
 
struct VISKORES_ALWAYS_EXPORT BitFieldMetaData
{
  viskores::Id NumberOfBits = 0;
};
 
}
 
namespace detail
{
 
struct BitFieldTraits
{
  // Allocations will occur in blocks of BlockSize bytes. This ensures that
  // power-of-two word sizes up to BlockSize will not access invalid data
  // during word-based access, and that atomic values will be properly aligned.
  // We use the default StorageBasic alignment for this.
  constexpr static viskores::Id BlockSize = VISKORES_ALLOCATION_ALIGNMENT;
 
  // Make sure the blocksize is at least 64. Eventually we may implement SIMD
  // bit operations, and the current largest vector width is 512 bits.
  VISKORES_STATIC_ASSERT(BlockSize >= 64);
 
  template <typename WordType>
  using IsValidWordType =
    std::integral_constant<bool,
                           /* is unsigned */
                           std::is_unsigned<WordType>::value &&
                             /* doesn't exceed blocksize */
                             sizeof(WordType) <= static_cast<size_t>(BlockSize) &&
                             /* BlockSize is a multiple of WordType */
                             static_cast<size_t>(BlockSize) % sizeof(WordType) == 0>;
 
  template <typename WordType>
  using IsValidWordTypeAtomic =
    std::integral_constant<bool,
                           /* is unsigned */
                           std::is_unsigned<WordType>::value &&
                             /* doesn't exceed blocksize */
                             sizeof(WordType) <= static_cast<size_t>(BlockSize) &&
                             /* BlockSize is a multiple of WordType */
                             static_cast<size_t>(BlockSize) % sizeof(WordType) == 0 &&
                             /* Supported by atomic interface */
                             viskores::ListHas<viskores::AtomicTypesSupported, WordType>::value>;
};
 
struct BitCoordinate
{
  viskores::Id WordIndex;
 
  viskores::Int32 BitOffset; // [0, bitsInWord)
};
 
template <bool IsConst>
class BitPortalBase
{
  // Checks if PortalType has a GetIteratorBegin() method that returns a
  // pointer.
  template <typename PortalType,
            typename PointerType = decltype(std::declval<PortalType>().GetIteratorBegin())>
  struct HasPointerAccess : public std::is_pointer<PointerType>
  {
  };
 
  // Determine whether we should store a const vs. mutable pointer:
  template <typename T>
  using MaybeConstPointer = typename std::conditional<IsConst, T const*, T*>::type;
  using BufferType = MaybeConstPointer<void>; // void* or void const*, as appropriate
 
public:
  using WordTypePreferred = viskores::AtomicTypePreferred;
 
  template <typename WordType>
  using IsValidWordType = BitFieldTraits::IsValidWordType<WordType>;
 
  template <typename WordType>
  using IsValidWordTypeAtomic = BitFieldTraits::IsValidWordTypeAtomic<WordType>;
 
  VISKORES_STATIC_ASSERT_MSG(IsValidWordType<WordTypeDefault>::value,
                             "Internal error: Default word type is invalid.");
  VISKORES_STATIC_ASSERT_MSG(IsValidWordType<WordTypePreferred>::value,
                             "Device-specific fast word type is invalid.");
 
  VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordTypeDefault>::value,
                             "Internal error: Default word type is invalid.");
  VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordTypePreferred>::value,
                             "Device-specific fast word type is invalid for atomic operations.");
 
protected:
  friend class viskores::cont::BitField;
  friend class viskores::cont::internal::Storage<bool,
                                                 viskores::cont::internal::StorageTagBitField>;
 
  VISKORES_CONT BitPortalBase(BufferType rawArray, viskores::Id numberOfBits)
    : Data{ rawArray }
    , NumberOfBits{ numberOfBits }
  {
  }
 
public:
  BitPortalBase() noexcept = default;
  BitPortalBase(const BitPortalBase&) noexcept = default;
  BitPortalBase(BitPortalBase&&) noexcept = default;
  BitPortalBase& operator=(const BitPortalBase&) noexcept = default;
  BitPortalBase& operator=(BitPortalBase&&) noexcept = default;
 
  VISKORES_EXEC_CONT
  viskores::Id GetNumberOfBits() const noexcept { return this->NumberOfBits; }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT viskores::Id GetNumberOfWords() const noexcept
  {
    VISKORES_STATIC_ASSERT(IsValidWordType<WordType>::value);
    static constexpr viskores::Id WordSize = static_cast<viskores::Id>(sizeof(WordType));
    static constexpr viskores::Id WordBits = WordSize * CHAR_BIT;
    return (this->NumberOfBits + WordBits - 1) / WordBits;
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType GetFinalWordMask() const noexcept
  {
    if (this->NumberOfBits == 0)
    {
      return WordType{ 0 };
    }
 
    static constexpr viskores::Int32 BitsPerWord =
      static_cast<viskores::Int32>(sizeof(WordType) * CHAR_BIT);
 
    const auto maxBit = this->NumberOfBits - 1;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(maxBit);
    const viskores::Int32 shift = BitsPerWord - coord.BitOffset - 1;
    return (~WordType{ 0 }) >> shift;
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT static BitCoordinate GetBitCoordinateFromIndex(viskores::Id bitIdx) noexcept
  {
    VISKORES_STATIC_ASSERT(IsValidWordType<WordType>::value);
    static constexpr viskores::Id BitsPerWord =
      static_cast<viskores::Id>(sizeof(WordType) * CHAR_BIT);
    return { static_cast<viskores::Id>(bitIdx / BitsPerWord),
             static_cast<viskores::Int32>(bitIdx % BitsPerWord) };
  }
 
  VISKORES_EXEC_CONT
  void SetBit(viskores::Id bitIdx, bool val) const noexcept
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "'Set' method called on const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto mask = WordType(1) << coord.BitOffset;
    WordType* wordAddr = this->GetWordAddress<WordType>(coord.WordIndex);
    if (val)
    {
      *wordAddr |= mask;
    }
    else
    {
      *wordAddr &= ~mask;
    }
  }
 
  VISKORES_EXEC_CONT
  void SetBitAtomic(viskores::Id bitIdx, bool val) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "'Set' method called on const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto mask = WordType(1) << coord.BitOffset;
    if (val)
    {
      this->OrWordAtomic(coord.WordIndex, mask);
    }
    else
    {
      this->AndWordAtomic(coord.WordIndex, ~mask);
    }
  }
 
  VISKORES_EXEC_CONT
  bool GetBit(viskores::Id bitIdx) const noexcept
  {
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto word = this->GetWord<WordType>(coord.WordIndex);
    const auto mask = WordType(1) << coord.BitOffset;
    return (word & mask) != WordType(0);
  }
 
  VISKORES_EXEC_CONT
  bool GetBitAtomic(viskores::Id bitIdx) const
  {
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto word = this->GetWordAtomic<WordType>(coord.WordIndex);
    const auto mask = WordType(1) << coord.BitOffset;
    return (word & mask) != WordType(0);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT void SetWord(viskores::Id wordIdx, WordType word) const noexcept
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "'Set' method called on const BitField portal.");
    *this->GetWordAddress<WordType>(wordIdx) = word;
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT void SetWordAtomic(viskores::Id wordIdx, WordType word) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "'Set' method called on const BitField portal.");
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    viskores::AtomicStore(this->GetWordAddress<WordType>(wordIdx), word);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType GetWord(viskores::Id wordIdx) const noexcept
  {
    return *this->GetWordAddress<WordType>(wordIdx);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType GetWordAtomic(viskores::Id wordIdx) const
  {
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    return viskores::AtomicLoad(this->GetWordAddress<WordType>(wordIdx));
  }
 
  VISKORES_EXEC_CONT
  bool NotBitAtomic(viskores::Id bitIdx) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto mask = WordType(1) << coord.BitOffset;
    const auto oldWord = this->XorWordAtomic(coord.WordIndex, mask);
    return (oldWord & mask) != WordType(0);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType NotWordAtomic(viskores::Id wordIdx) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    WordType* addr = this->GetWordAddress<WordType>(wordIdx);
    return viskores::AtomicNot(addr);
  }
 
  VISKORES_EXEC_CONT
  bool AndBitAtomic(viskores::Id bitIdx, bool val) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto bitmask = WordType(1) << coord.BitOffset;
    // wordmask is all 1's, except for BitOffset which is (val ? 1 : 0)
    const auto wordmask = val ? ~WordType(0) : ~bitmask;
    const auto oldWord = this->AndWordAtomic(coord.WordIndex, wordmask);
    return (oldWord & bitmask) != WordType(0);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType AndWordAtomic(viskores::Id wordIdx, WordType wordmask) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    WordType* addr = this->GetWordAddress<WordType>(wordIdx);
    return viskores::AtomicAnd(addr, wordmask);
  }
 
  VISKORES_EXEC_CONT
  bool OrBitAtomic(viskores::Id bitIdx, bool val) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto bitmask = WordType(1) << coord.BitOffset;
    // wordmask is all 0's, except for BitOffset which is (val ? 1 : 0)
    const auto wordmask = val ? bitmask : WordType(0);
    const auto oldWord = this->OrWordAtomic(coord.WordIndex, wordmask);
    return (oldWord & bitmask) != WordType(0);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType OrWordAtomic(viskores::Id wordIdx, WordType wordmask) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    WordType* addr = this->GetWordAddress<WordType>(wordIdx);
    return viskores::AtomicOr(addr, wordmask);
  }
 
  VISKORES_EXEC_CONT
  bool XorBitAtomic(viskores::Id bitIdx, bool val) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto bitmask = WordType(1) << coord.BitOffset;
    // wordmask is all 0's, except for BitOffset which is (val ? 1 : 0)
    const auto wordmask = val ? bitmask : WordType(0);
    const auto oldWord = this->XorWordAtomic(coord.WordIndex, wordmask);
    return (oldWord & bitmask) != WordType(0);
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT WordType XorWordAtomic(viskores::Id wordIdx, WordType wordmask) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    WordType* addr = this->GetWordAddress<WordType>(wordIdx);
    return viskores::AtomicXor(addr, wordmask);
  }
 
  VISKORES_EXEC_CONT
  bool CompareExchangeBitAtomic(viskores::Id bitIdx, bool* oldBit, bool newBit) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    using WordType = WordTypePreferred;
    const auto coord = this->GetBitCoordinateFromIndex<WordType>(bitIdx);
    const auto bitmask = WordType(1) << coord.BitOffset;
 
    WordType oldWord = this->GetWord<WordType>(coord.WordIndex);
    do
    {
      bool actualBit = (oldWord & bitmask) != WordType(0);
      if (actualBit != *oldBit)
      { // The bit-of-interest does not match what we expected.
        *oldBit = actualBit;
        return false;
      }
      else if (actualBit == newBit)
      { // The bit hasn't changed, but also already matches newVal. We're done.
        return true;
      }
 
      // Attempt to update the word with a compare-exchange in the loop condition.
      // If the old word changed since last queried, oldWord will get updated and
      // the loop will continue until it succeeds.
    } while (!this->CompareExchangeWordAtomic(coord.WordIndex, &oldWord, oldWord ^ bitmask));
 
    return true;
  }
 
  template <typename WordType = WordTypePreferred>
  VISKORES_EXEC_CONT bool CompareExchangeWordAtomic(viskores::Id wordIdx,
                                                    WordType* oldWord,
                                                    WordType newWord) const
  {
    VISKORES_STATIC_ASSERT_MSG(!IsConst, "Attempt to modify const BitField portal.");
    VISKORES_STATIC_ASSERT_MSG(IsValidWordTypeAtomic<WordType>::value,
                               "Requested WordType does not support atomic"
                               " operations on target execution platform.");
    WordType* addr = this->GetWordAddress<WordType>(wordIdx);
    return viskores::AtomicCompareExchange(addr, oldWord, newWord);
  }
 
private:
  template <typename WordType>
  VISKORES_EXEC_CONT MaybeConstPointer<WordType> GetWordAddress(viskores::Id wordId) const noexcept
  {
    VISKORES_STATIC_ASSERT(IsValidWordType<WordType>::value);
    return reinterpret_cast<MaybeConstPointer<WordType>>(this->Data) + wordId;
  }
 
  BufferType Data{ nullptr };
  viskores::Id NumberOfBits{ 0 };
};
 
using BitPortal = BitPortalBase<false>;
 
using BitPortalConst = BitPortalBase<true>;
 
} // end namespace detail
 
class VISKORES_CONT_EXPORT BitField
{
  static constexpr viskores::Id BlockSize = detail::BitFieldTraits::BlockSize;
 
public:
  using WritePortalType = detail::BitPortal;
 
  using ReadPortalType = detail::BitPortalConst;
 
  using WordTypePreferred = viskores::AtomicTypePreferred;
 
  template <typename Device>
  struct ExecutionTypes
  {
    using WordTypePreferred = viskores::AtomicTypePreferred;
 
    using Portal = detail::BitPortal;
 
    using PortalConst = detail::BitPortalConst;
  };
 
  template <typename WordType>
  using IsValidWordType = detail::BitFieldTraits::IsValidWordType<WordType>;
 
  template <typename WordType, typename Device = void>
  using IsValidWordTypeAtomic = detail::BitFieldTraits::IsValidWordTypeAtomic<WordType>;
 
  VISKORES_CONT BitField();
  VISKORES_CONT BitField(const BitField&) = default;
  VISKORES_CONT BitField(BitField&&) noexcept = default;
  VISKORES_CONT ~BitField() = default;
  VISKORES_CONT BitField& operator=(const BitField&) = default;
  VISKORES_CONT BitField& operator=(BitField&&) noexcept = default;
 
  VISKORES_CONT
  bool operator==(const BitField& rhs) const { return this->Buffer == rhs.Buffer; }
 
  VISKORES_CONT
  bool operator!=(const BitField& rhs) const { return this->Buffer != rhs.Buffer; }
 
  VISKORES_CONT viskores::cont::internal::Buffer GetBuffer() const { return this->Buffer; }
 
  VISKORES_CONT viskores::Id GetNumberOfBits() const;
 
  template <typename WordType>
  VISKORES_CONT viskores::Id GetNumberOfWords() const
  {
    VISKORES_STATIC_ASSERT(IsValidWordType<WordType>::value);
    static constexpr viskores::Id WordBits = static_cast<viskores::Id>(sizeof(WordType) * CHAR_BIT);
    return (this->GetNumberOfBits() + WordBits - 1) / WordBits;
  }
 
  VISKORES_CONT void Allocate(viskores::Id numberOfBits,
                              viskores::CopyFlag preserve,
                              viskores::cont::Token& token) const;
 
  VISKORES_CONT void Allocate(viskores::Id numberOfBits,
                              viskores::CopyFlag preserve = viskores::CopyFlag::Off) const
  {
    viskores::cont::Token token;
    this->Allocate(numberOfBits, preserve, token);
  }
 
  template <typename ValueType>
  VISKORES_CONT void AllocateAndFill(viskores::Id numberOfBits,
                                     ValueType value,
                                     viskores::cont::Token& token) const
  {
    this->Allocate(numberOfBits, viskores::CopyFlag::Off, token);
    this->Fill(value, token);
  }
  template <typename ValueType>
  VISKORES_CONT void AllocateAndFill(viskores::Id numberOfBits, ValueType value) const
  {
    viskores::cont::Token token;
    this->AllocateAndFill(numberOfBits, value, token);
  }
 
private:
  VISKORES_CONT void FillImpl(const void* word,
                              viskores::BufferSizeType wordSize,
                              viskores::cont::Token& token) const;
 
public:
  template <typename WordType>
  VISKORES_CONT void Fill(WordType word, viskores::cont::Token& token) const
  {
    this->FillImpl(&word, static_cast<viskores::BufferSizeType>(sizeof(WordType)), token);
  }
  template <typename WordType>
  VISKORES_CONT void Fill(WordType word) const
  {
    viskores::cont::Token token;
    this->Fill(word, token);
  }
 
  VISKORES_CONT void Fill(bool value, viskores::cont::Token& token) const
  {
    using WordType = WordTypePreferred;
    this->Fill(value ? ~WordType{ 0 } : WordType{ 0 }, token);
  }
  VISKORES_CONT void Fill(bool value) const
  {
    viskores::cont::Token token;
    this->Fill(value, token);
  }
 
  VISKORES_CONT void ReleaseResourcesExecution();
 
  VISKORES_CONT void ReleaseResources();
 
  VISKORES_CONT void SyncControlArray() const;
 
  VISKORES_CONT bool IsOnDevice(viskores::cont::DeviceAdapterId device) const;
 
  VISKORES_CONT bool IsOnHost() const
  {
    return this->IsOnDevice(viskores::cont::DeviceAdapterTagUndefined{});
  }
 
  VISKORES_CONT WritePortalType WritePortal() const;
 
  VISKORES_CONT ReadPortalType ReadPortal() const;
 
  VISKORES_CONT ReadPortalType PrepareForInput(viskores::cont::DeviceAdapterId device,
                                               viskores::cont::Token& token) const;
 
  VISKORES_CONT WritePortalType PrepareForOutput(viskores::Id numBits,
                                                 viskores::cont::DeviceAdapterId device,
                                                 viskores::cont::Token& token) const;
 
  VISKORES_CONT WritePortalType PrepareForInPlace(viskores::cont::DeviceAdapterId device,
                                                  viskores::cont::Token& token) const;
 
private:
  mutable viskores::cont::internal::Buffer Buffer;
};
}
} // end namespace viskores::cont
 
#endif // viskores_cont_BitField_h