kc3-lang/angle/src/common/bitset_utils.h

Branch : - branch - main - tag -

• Show log

  Commit

• Author : Charlie Lao
  Date : 2023-05-04 10:19:35
  Hash : 76fa3806
  Message : Vulkan: Expand BufferOnly path for VertexArray binding change VertexArrayVk has a fast code path for attribute change where the only change is buffer (i.e, no format or relativeOffset change). It will pass in bufferOnly to syncDirtyAttrib() call and will avoid invalidate graphics pipeline. This CL expands DIRTY_BIT_BINDING_n change and will also try to detect the bufferOnly case. This CL and crrev.com/c/4507978 together seeing Gfxbench driver overhead score improves 1.48% (from average 6804 before CLs to 6905 after CLs) on pixel 7 pro. Bug: b/277644512 Change-Id: I71da1b886bb26ba2629b83af3aeaba4d45c3d3c2 Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/4504919 Reviewed-by: Shahbaz Youssefi <syoussefi@chromium.org> Reviewed-by: Amirali Abdolrashidi <abdolrashidi@google.com> Commit-Queue: Charlie Lao <cclao@google.com> Auto-Submit: Charlie Lao <cclao@google.com>

• src/common/bitset_utils.h

• //
  // Copyright 2015 The ANGLE Project Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  //
  // bitset_utils:
  //   Bitset-related helper classes, such as a fast iterator to scan for set bits.
  //
  
  #ifndef COMMON_BITSETITERATOR_H_
  #define COMMON_BITSETITERATOR_H_
  
  #include <stdint.h>
  
  #include <array>
  
  #include "common/angleutils.h"
  #include "common/debug.h"
  #include "common/mathutil.h"
  #include "common/platform.h"
  
  namespace angle
  {
  // Given x, create 1 << x.
  template <typename BitsT, typename ParamT>
  constexpr BitsT Bit(ParamT x)
  {
      // It's undefined behavior if the shift size is equal to or larger than the width of the type.
      ASSERT(static_cast<size_t>(x) < sizeof(BitsT) * 8);
  
      return (static_cast<BitsT>(1) << static_cast<size_t>(x));
  }
  
  // Given x, create (1 << x) - 1, i.e. a mask with x bits set.
  template <typename BitsT, typename ParamT>
  constexpr BitsT BitMask(ParamT x)
  {
      if (static_cast<size_t>(x) == 0)
      {
          return 0;
      }
      return ((Bit<BitsT>(static_cast<ParamT>(static_cast<size_t>(x) - 1)) - 1) << 1) | 1;
  }
  
  template <size_t N, typename BitsT, typename ParamT = std::size_t>
  class BitSetT final
  {
    public:
      class Reference final
      {
        public:
          ~Reference() {}
          Reference &operator=(bool x)
          {
              mParent->set(mBit, x);
              return *this;
          }
          explicit operator bool() const { return mParent->test(mBit); }
  
        private:
          friend class BitSetT;
  
          Reference(BitSetT *parent, ParamT bit) : mParent(parent), mBit(bit) {}
  
          BitSetT *mParent;
          ParamT mBit;
      };
  
      class Iterator final
      {
        public:
          Iterator(const BitSetT &bits);
          Iterator &operator++();
  
          bool operator==(const Iterator &other) const;
          bool operator!=(const Iterator &other) const;
          ParamT operator*() const;
  
          // These helper functions allow mutating an iterator in-flight.
          // They only operate on later bits to ensure we don't iterate the same bit twice.
          void resetLaterBit(std::size_t index)
          {
              ASSERT(index > mCurrentBit);
              mBitsCopy.reset(index);
          }
  
          // bits could contain bit that earlier than mCurrentBit. Since mBitCopy can't have bits
          // earlier than mCurrentBit, the & operation will mask out earlier bits anyway.
          void resetLaterBits(const BitSetT &bits)
          {
              BitSetT maskedBits = ~Mask(mCurrentBit + 1);
              maskedBits &= bits;
              mBitsCopy &= ~maskedBits;
          }
  
          void setLaterBit(std::size_t index)
          {
              ASSERT(index > mCurrentBit);
              mBitsCopy.set(index);
          }
  
          void setLaterBits(const BitSetT &bits)
          {
              ASSERT((BitSetT(bits) &= Mask(mCurrentBit + 1)).none());
              mBitsCopy |= bits;
          }
  
        private:
          std::size_t getNextBit();
  
          BitSetT mBitsCopy;
          std::size_t mCurrentBit;
      };
  
      using value_type = BitsT;
      using param_type = ParamT;
  
      constexpr BitSetT();
      constexpr explicit BitSetT(BitsT value);
      constexpr explicit BitSetT(std::initializer_list<ParamT> init);
  
      constexpr BitSetT(const BitSetT &other);
      constexpr BitSetT &operator=(const BitSetT &other);
  
      constexpr bool operator==(const BitSetT &other) const;
      constexpr bool operator!=(const BitSetT &other) const;
  
      constexpr bool operator[](ParamT pos) const;
      Reference operator[](ParamT pos) { return Reference(this, pos); }
  
      constexpr bool test(ParamT pos) const;
  
      constexpr bool all() const;
      constexpr bool any() const;
      constexpr bool none() const;
      constexpr std::size_t count() const;
  
      constexpr static std::size_t size() { return N; }
  
      constexpr BitSetT &operator&=(const BitSetT &other);
      constexpr BitSetT &operator|=(const BitSetT &other);
      constexpr BitSetT &operator^=(const BitSetT &other);
      constexpr BitSetT operator~() const;
  
      constexpr BitSetT &operator&=(BitsT value);
      constexpr BitSetT &operator|=(BitsT value);
      constexpr BitSetT &operator^=(BitsT value);
  
      constexpr BitSetT operator<<(std::size_t pos) const;
      constexpr BitSetT &operator<<=(std::size_t pos);
      constexpr BitSetT operator>>(std::size_t pos) const;
      constexpr BitSetT &operator>>=(std::size_t pos);
  
      constexpr BitSetT &set();
      constexpr BitSetT &set(ParamT pos, bool value = true);
  
      constexpr BitSetT &reset();
      constexpr BitSetT &reset(ParamT pos);
  
      constexpr BitSetT &flip();
      constexpr BitSetT &flip(ParamT pos);
  
      constexpr unsigned long to_ulong() const { return static_cast<unsigned long>(mBits); }
      constexpr BitsT bits() const { return mBits; }
  
      Iterator begin() const { return Iterator(*this); }
      Iterator end() const { return Iterator(BitSetT()); }
  
      constexpr static BitSetT Zero() { return BitSetT(); }
  
      constexpr ParamT first() const;
      constexpr ParamT last() const;
  
      // Produces a mask of ones up to the "x"th bit.
      constexpr static BitSetT Mask(std::size_t x)
      {
          BitSetT result;
          result.mBits = BitMask<BitsT>(static_cast<ParamT>(x));
          return result;
      }
  
    private:
      BitsT mBits;
  };
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT>::BitSetT() : mBits(0)
  {
      static_assert(N > 0, "Bitset type cannot support zero bits.");
      static_assert(N <= sizeof(BitsT) * 8, "Bitset type cannot support a size this large.");
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT>::BitSetT(BitsT value) : mBits(value & Mask(N).bits())
  {}
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT>::BitSetT(std::initializer_list<ParamT> init) : mBits(0)
  {
      for (ParamT element : init)
      {
          mBits |= Bit<BitsT>(element);
      }
      ASSERT(mBits == (mBits & Mask(N).bits()));
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT>::BitSetT(const BitSetT &other) : mBits(other.mBits)
  {}
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator=(const BitSetT &other)
  {
      mBits = other.mBits;
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::operator==(const BitSetT &other) const
  {
      return mBits == other.mBits;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::operator!=(const BitSetT &other) const
  {
      return mBits != other.mBits;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::operator[](ParamT pos) const
  {
      return test(pos);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::test(ParamT pos) const
  {
      return (mBits & Bit<BitsT>(pos)) != 0;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::all() const
  {
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return mBits == Mask(N).bits();
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::any() const
  {
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return (mBits != 0);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr bool BitSetT<N, BitsT, ParamT>::none() const
  {
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return (mBits == 0);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr std::size_t BitSetT<N, BitsT, ParamT>::count() const
  {
      return gl::BitCount(mBits);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(const BitSetT &other)
  {
      mBits &= other.mBits;
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(const BitSetT &other)
  {
      mBits |= other.mBits;
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(const BitSetT &other)
  {
      mBits = mBits ^ other.mBits;
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator~() const
  {
      return BitSetT<N, BitsT, ParamT>(~mBits & Mask(N).bits());
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(BitsT value)
  {
      mBits &= value;
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(BitsT value)
  {
      mBits |= value;
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(BitsT value)
  {
      mBits ^= value;
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator<<(std::size_t pos) const
  {
      return BitSetT<N, BitsT, ParamT>((mBits << pos) & Mask(N).bits());
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator<<=(std::size_t pos)
  {
      mBits = mBits << pos & Mask(N).bits();
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator>>(std::size_t pos) const
  {
      return BitSetT<N, BitsT, ParamT>(mBits >> pos);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator>>=(std::size_t pos)
  {
      mBits = (mBits >> pos) & Mask(N).bits();
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set()
  {
      ASSERT(mBits == (mBits & Mask(N).bits()));
      mBits = Mask(N).bits();
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set(ParamT pos, bool value)
  {
      ASSERT(static_cast<size_t>(pos) < N);
      if (value)
      {
          mBits |= Bit<BitsT>(pos);
      }
      else
      {
          reset(pos);
      }
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset()
  {
      ASSERT(mBits == (mBits & Mask(N).bits()));
      mBits = 0;
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset(ParamT pos)
  {
      ASSERT(static_cast<size_t>(pos) < N);
      ASSERT(mBits == (mBits & Mask(N).bits()));
      mBits &= ~Bit<BitsT>(pos);
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip()
  {
      ASSERT(mBits == (mBits & Mask(N).bits()));
      mBits ^= Mask(N).bits();
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip(ParamT pos)
  {
      ASSERT(static_cast<size_t>(pos) < N);
      mBits ^= Bit<BitsT>(pos);
      ASSERT(mBits == (mBits & Mask(N).bits()));
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr ParamT BitSetT<N, BitsT, ParamT>::first() const
  {
      ASSERT(!none());
      return static_cast<ParamT>(gl::ScanForward(mBits));
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  constexpr ParamT BitSetT<N, BitsT, ParamT>::last() const
  {
      ASSERT(!none());
      return static_cast<ParamT>(gl::ScanReverse(mBits));
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  BitSetT<N, BitsT, ParamT>::Iterator::Iterator(const BitSetT &bits) : mBitsCopy(bits), mCurrentBit(0)
  {
      if (bits.any())
      {
          mCurrentBit = getNextBit();
      }
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  ANGLE_INLINE typename BitSetT<N, BitsT, ParamT>::Iterator &
  BitSetT<N, BitsT, ParamT>::Iterator::operator++()
  {
      ASSERT(mBitsCopy.any());
      mBitsCopy.reset(static_cast<ParamT>(mCurrentBit));
      mCurrentBit = getNextBit();
      return *this;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  bool BitSetT<N, BitsT, ParamT>::Iterator::operator==(const Iterator &other) const
  {
      return mBitsCopy == other.mBitsCopy;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  bool BitSetT<N, BitsT, ParamT>::Iterator::operator!=(const Iterator &other) const
  {
      return !(*this == other);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  ParamT BitSetT<N, BitsT, ParamT>::Iterator::operator*() const
  {
      return static_cast<ParamT>(mCurrentBit);
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  std::size_t BitSetT<N, BitsT, ParamT>::Iterator::getNextBit()
  {
      if (mBitsCopy.none())
      {
          return 0;
      }
  
      return gl::ScanForward(mBitsCopy.mBits);
  }
  
  template <size_t N>
  using BitSet8 = BitSetT<N, uint8_t>;
  
  template <size_t N>
  using BitSet16 = BitSetT<N, uint16_t>;
  
  template <size_t N>
  using BitSet32 = BitSetT<N, uint32_t>;
  
  template <size_t N>
  using BitSet64 = BitSetT<N, uint64_t>;
  
  template <std::size_t N>
  class BitSetArray;
  
  namespace priv
  {
  
  template <size_t N, typename T>
  using EnableIfBitsFit = typename std::enable_if<N <= sizeof(T) * 8>::type;
  
  template <size_t N, typename Enable = void>
  struct GetBitSet
  {
      using Type = BitSetArray<N>;
  };
  
  // Prefer 64-bit bitsets on 64-bit CPUs. They seem faster than 32-bit.
  #if defined(ANGLE_IS_64_BIT_CPU)
  template <size_t N>
  struct GetBitSet<N, EnableIfBitsFit<N, uint64_t>>
  {
      using Type = BitSet64<N>;
  };
  constexpr std::size_t kDefaultBitSetSize = 64;
  using BaseBitSetType                     = BitSet64<kDefaultBitSetSize>;
  #else
  template <size_t N>
  struct GetBitSet<N, EnableIfBitsFit<N, uint32_t>>
  {
      using Type = BitSet32<N>;
  };
  constexpr std::size_t kDefaultBitSetSize = 32;
  using BaseBitSetType                     = BitSet32<kDefaultBitSetSize>;
  #endif  // defined(ANGLE_IS_64_BIT_CPU)
  
  }  // namespace priv
  
  template <size_t N>
  using BitSet = typename priv::GetBitSet<N>::Type;
  
  template <std::size_t N>
  class BitSetArray final
  {
    public:
      using BaseBitSet = priv::BaseBitSetType;
      using value_type = BaseBitSet::value_type;
      using param_type = BaseBitSet::param_type;
  
      constexpr BitSetArray();
      constexpr explicit BitSetArray(uint64_t value);
      constexpr explicit BitSetArray(std::initializer_list<param_type> init);
  
      constexpr BitSetArray(const BitSetArray<N> &other);
  
      class Reference final
      {
        public:
          ~Reference() {}
          Reference &operator=(bool x)
          {
              mParent.set(mPosition, x);
              return *this;
          }
          explicit operator bool() const { return mParent.test(mPosition); }
  
        private:
          friend class BitSetArray;
  
          Reference(BitSetArray &parent, std::size_t pos) : mParent(parent), mPosition(pos) {}
  
          BitSetArray &mParent;
          std::size_t mPosition;
      };
      class Iterator final
      {
        public:
          Iterator(const BitSetArray<N> &bitSetArray, std::size_t index);
          Iterator &operator++();
          bool operator==(const Iterator &other) const;
          bool operator!=(const Iterator &other) const;
          size_t operator*() const;
  
          // These helper functions allow mutating an iterator in-flight.
          // They only operate on later bits to ensure we don't iterate the same bit twice.
          void resetLaterBit(std::size_t pos)
          {
              ASSERT(pos > (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator);
              prepareCopy();
              mParentCopy.reset(pos);
              updateIteratorBit(pos, false);
          }
  
          void setLaterBit(std::size_t pos)
          {
              ASSERT(pos > (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator);
              prepareCopy();
              mParentCopy.set(pos);
              updateIteratorBit(pos, true);
          }
  
          void setLaterBits(const BitSetArray &bits)
          {
              prepareCopy();
              mParentCopy |= bits;
              updateIteratorBits(bits);
          }
  
        private:
          ANGLE_INLINE void prepareCopy()
          {
              ASSERT(mParent.mBaseBitSetArray[mIndex].end() ==
                     mParentCopy.mBaseBitSetArray[mIndex].end());
              if (mParentCopy.none())
              {
                  mParentCopy    = mParent;
                  mCurrentParent = &mParentCopy;
              }
          }
  
          ANGLE_INLINE void updateIteratorBit(std::size_t pos, bool setBit)
          {
              // Get the index and offset, update current interator if within range
              size_t index  = pos >> kShiftForDivision;
              size_t offset = pos & kDefaultBitSetSizeMinusOne;
              if (index == mIndex)
              {
                  if (setBit)
                  {
                      mCurrentIterator.setLaterBit(offset);
                  }
                  else
                  {
                      mCurrentIterator.resetLaterBit(offset);
                  }
              }
          }
  
          ANGLE_INLINE void updateIteratorBits(const BitSetArray &bits)
          {
              mCurrentIterator.setLaterBits(bits.mBaseBitSetArray[mIndex]);
          }
  
          // Problem -
          // We want to provide the fastest path possible for usecases that iterate though the bitset.
          //
          // Options -
          // 1) For non-mutating iterations the const ref <mParent> is set as mCurrentParent and only
          //    for usecases that need to mutate the bitset while iterating we perform a copy of
          //    <mParent> into <mParentCopy> and modify its bits accordingly.
          // 2) The alternate approach was to perform a copy all the time in the constructor
          //    irrespective of whether it was a mutating usecase or not.
          //
          // Experiment -
          // BitSetIteratorPerfTest was run on a Windows machine with Intel CPU and these were the
          // results -
          // 1) Copy only when necessary -
          //      RESULT BitSetIteratorPerf.wall_time:    run = 116.1067374961 ns
          //      RESULT BitSetIteratorPerf.trial_steps : run = 8416124 count
          //      RESULT BitSetIteratorPerf.total_steps : run = 16832251 count
          // 2) Copy always -
          //      RESULT BitSetIteratorPerf.wall_time:    run = 242.7446459439 ns
          //      RESULT BitSetIteratorPerf.trial_steps : run = 4171416 count
          //      RESULT BitSetIteratorPerf.total_steps : run = 8342834 count
          //
          // Resolution -
          // We settled on the copy only when necessary path.
          size_t mIndex;
          const BitSetArray &mParent;
          BitSetArray mParentCopy;
          const BitSetArray *mCurrentParent;
          typename BaseBitSet::Iterator mCurrentIterator;
      };
  
      constexpr static std::size_t size() { return N; }
      Iterator begin() const { return Iterator(*this, 0); }
      Iterator end() const { return Iterator(*this, kArraySize); }
      constexpr unsigned long to_ulong() const
      {
          // TODO(anglebug.com/5628): Handle serializing more than kDefaultBitSetSize
          for (std::size_t index = 1; index < kArraySize; index++)
          {
              ASSERT(mBaseBitSetArray[index].none());
          }
          return static_cast<unsigned long>(mBaseBitSetArray[0].to_ulong());
      }
  
      // Assignment operators
      constexpr BitSetArray &operator=(const BitSetArray &other);
      constexpr BitSetArray &operator&=(const BitSetArray &other);
      constexpr BitSetArray &operator|=(const BitSetArray &other);
      constexpr BitSetArray &operator^=(const BitSetArray &other);
  
      // Bitwise operators
      constexpr BitSetArray<N> operator&(const angle::BitSetArray<N> &other) const;
      constexpr BitSetArray<N> operator|(const angle::BitSetArray<N> &other) const;
      constexpr BitSetArray<N> operator^(const angle::BitSetArray<N> &other) const;
  
      // Relational Operators
      constexpr bool operator==(const angle::BitSetArray<N> &other) const;
      constexpr bool operator!=(const angle::BitSetArray<N> &other) const;
  
      // Unary operators
      constexpr BitSetArray operator~() const;
      constexpr bool operator[](std::size_t pos) const;
      constexpr Reference operator[](std::size_t pos)
      {
          ASSERT(pos < size());
          return Reference(*this, pos);
      }
  
      // Setter, getters and other helper methods
      constexpr BitSetArray &set();
      constexpr BitSetArray &set(std::size_t pos, bool value = true);
      constexpr BitSetArray &reset();
      constexpr BitSetArray &reset(std::size_t pos);
      constexpr bool test(std::size_t pos) const;
      constexpr bool all() const;
      constexpr bool any() const;
      constexpr bool none() const;
      constexpr std::size_t count() const;
      constexpr bool intersects(const BitSetArray &other) const;
      constexpr BitSetArray<N> &flip();
      constexpr param_type first() const;
      constexpr param_type last() const;
  
      constexpr value_type bits(size_t index) const;
  
      // Produces a mask of ones up to the "x"th bit.
      constexpr static BitSetArray Mask(std::size_t x);
  
    private:
      static constexpr std::size_t kDefaultBitSetSizeMinusOne = priv::kDefaultBitSetSize - 1;
      static constexpr std::size_t kShiftForDivision =
          static_cast<std::size_t>(rx::Log2(static_cast<unsigned int>(priv::kDefaultBitSetSize)));
      static constexpr std::size_t kArraySize =
          ((N + kDefaultBitSetSizeMinusOne) >> kShiftForDivision);
      constexpr static std::size_t kLastElementCount = (N & kDefaultBitSetSizeMinusOne);
      constexpr static std::size_t kLastElementMask =
          priv::BaseBitSetType::Mask(kLastElementCount == 0 ? priv::kDefaultBitSetSize
                                                            : kLastElementCount)
              .bits();
  
      std::array<BaseBitSet, kArraySize> mBaseBitSetArray;
  };
  
  template <std::size_t N>
  constexpr BitSetArray<N>::BitSetArray()
  {
      static_assert(N > priv::kDefaultBitSetSize, "BitSetArray type can't support requested size.");
      reset();
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N>::BitSetArray(uint64_t value)
  {
      reset();
  
      if (priv::kDefaultBitSetSize < 64)
      {
          size_t i = 0;
          for (; i < kArraySize - 1; ++i)
          {
              value_type elemValue =
                  value & priv::BaseBitSetType::Mask(priv::kDefaultBitSetSize).bits();
              mBaseBitSetArray[i] = priv::BaseBitSetType(elemValue);
              value >>= priv::kDefaultBitSetSize;
          }
          value_type elemValue = value & kLastElementMask;
          mBaseBitSetArray[i]  = priv::BaseBitSetType(elemValue);
      }
      else
      {
          value_type elemValue = value & priv::BaseBitSetType::Mask(priv::kDefaultBitSetSize).bits();
          mBaseBitSetArray[0]  = priv::BaseBitSetType(elemValue);
      }
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N>::BitSetArray(std::initializer_list<param_type> init)
  {
      reset();
  
      for (param_type element : init)
      {
          size_t index  = element >> kShiftForDivision;
          size_t offset = element & kDefaultBitSetSizeMinusOne;
          mBaseBitSetArray[index].set(offset, true);
      }
  }
  
  template <size_t N>
  constexpr BitSetArray<N>::BitSetArray(const BitSetArray<N> &other)
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          mBaseBitSetArray[index] = other.mBaseBitSetArray[index];
      }
  }
  
  template <size_t N>
  BitSetArray<N>::Iterator::Iterator(const BitSetArray<N> &bitSetArray, std::size_t index)
      : mIndex(index),
        mParent(bitSetArray),
        mCurrentParent(&mParent),
        mCurrentIterator(mParent.mBaseBitSetArray[0].begin())
  {
      while (mIndex < mCurrentParent->kArraySize)
      {
          if (mCurrentParent->mBaseBitSetArray[mIndex].any())
          {
              break;
          }
          mIndex++;
      }
  
      if (mIndex < mCurrentParent->kArraySize)
      {
          mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin();
      }
      else
      {
          mCurrentIterator = mCurrentParent->mBaseBitSetArray[mCurrentParent->kArraySize - 1].end();
      }
  }
  
  template <std::size_t N>
  typename BitSetArray<N>::Iterator &BitSetArray<N>::Iterator::operator++()
  {
      ++mCurrentIterator;
      while (mCurrentIterator == mCurrentParent->mBaseBitSetArray[mIndex].end())
      {
          mIndex++;
          if (mIndex >= mCurrentParent->kArraySize)
          {
              break;
          }
          mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin();
      }
      return *this;
  }
  
  template <std::size_t N>
  bool BitSetArray<N>::Iterator::operator==(const BitSetArray<N>::Iterator &other) const
  {
      return mCurrentIterator == other.mCurrentIterator;
  }
  
  template <std::size_t N>
  bool BitSetArray<N>::Iterator::operator!=(const BitSetArray<N>::Iterator &other) const
  {
      return mCurrentIterator != other.mCurrentIterator;
  }
  
  template <std::size_t N>
  std::size_t BitSetArray<N>::Iterator::operator*() const
  {
      return (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::operator=(const BitSetArray<N> &other)
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          mBaseBitSetArray[index] = other.mBaseBitSetArray[index];
      }
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::operator&=(const BitSetArray<N> &other)
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          mBaseBitSetArray[index] &= other.mBaseBitSetArray[index];
      }
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::operator|=(const BitSetArray<N> &other)
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          mBaseBitSetArray[index] |= other.mBaseBitSetArray[index];
      }
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::operator^=(const BitSetArray<N> &other)
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          mBaseBitSetArray[index] ^= other.mBaseBitSetArray[index];
      }
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> BitSetArray<N>::operator&(const angle::BitSetArray<N> &other) const
  {
      angle::BitSetArray<N> result(other);
      result &= *this;
      return result;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> BitSetArray<N>::operator|(const angle::BitSetArray<N> &other) const
  {
      angle::BitSetArray<N> result(other);
      result |= *this;
      return result;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> BitSetArray<N>::operator^(const angle::BitSetArray<N> &other) const
  {
      angle::BitSetArray<N> result(other);
      result ^= *this;
      return result;
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::operator==(const angle::BitSetArray<N> &other) const
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          if (mBaseBitSetArray[index] != other.mBaseBitSetArray[index])
          {
              return false;
          }
      }
      return true;
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::operator!=(const angle::BitSetArray<N> &other) const
  {
      return !(*this == other);
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> BitSetArray<N>::operator~() const
  {
      angle::BitSetArray<N> result;
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          result.mBaseBitSetArray[index] |= ~mBaseBitSetArray[index];
      }
      // The last element in result may need special handling
      result.mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
  
      return result;
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::operator[](std::size_t pos) const
  {
      ASSERT(pos < size());
      return test(pos);
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::set()
  {
      for (BaseBitSet &baseBitSet : mBaseBitSetArray)
      {
          baseBitSet.set();
      }
      // The last element in mBaseBitSetArray may need special handling
      mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
  
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::set(std::size_t pos, bool value)
  {
      ASSERT(pos < size());
      // Get the index and offset, then set the bit
      size_t index  = pos >> kShiftForDivision;
      size_t offset = pos & kDefaultBitSetSizeMinusOne;
      mBaseBitSetArray[index].set(offset, value);
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::reset()
  {
      for (BaseBitSet &baseBitSet : mBaseBitSetArray)
      {
          baseBitSet.reset();
      }
      return *this;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::reset(std::size_t pos)
  {
      ASSERT(pos < size());
      return set(pos, false);
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::test(std::size_t pos) const
  {
      ASSERT(pos < size());
      // Get the index and offset, then test the bit
      size_t index  = pos >> kShiftForDivision;
      size_t offset = pos & kDefaultBitSetSizeMinusOne;
      return mBaseBitSetArray[index].test(offset);
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::all() const
  {
      constexpr priv::BaseBitSetType kLastElementBitSet = priv::BaseBitSetType(kLastElementMask);
  
      for (std::size_t index = 0; index < kArraySize - 1; index++)
      {
          if (!mBaseBitSetArray[index].all())
          {
              return false;
          }
      }
  
      // The last element in mBaseBitSetArray may need special handling
      return mBaseBitSetArray[kArraySize - 1] == kLastElementBitSet;
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::any() const
  {
      for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
      {
          if (baseBitSet.any())
          {
              return true;
          }
      }
      return false;
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::none() const
  {
      for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
      {
          if (!baseBitSet.none())
          {
              return false;
          }
      }
      return true;
  }
  
  template <std::size_t N>
  constexpr std::size_t BitSetArray<N>::count() const
  {
      size_t count = 0;
      for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
      {
          count += baseBitSet.count();
      }
      return count;
  }
  
  template <std::size_t N>
  constexpr bool BitSetArray<N>::intersects(const BitSetArray<N> &other) const
  {
      for (std::size_t index = 0; index < kArraySize; index++)
      {
          if ((mBaseBitSetArray[index].bits() & other.mBaseBitSetArray[index].bits()) != 0)
          {
              return true;
          }
      }
      return false;
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> &BitSetArray<N>::flip()
  {
      for (BaseBitSet &baseBitSet : mBaseBitSetArray)
      {
          baseBitSet.flip();
      }
  
      // The last element in mBaseBitSetArray may need special handling
      mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
      return *this;
  }
  
  template <std::size_t N>
  constexpr typename BitSetArray<N>::param_type BitSetArray<N>::first() const
  {
      ASSERT(any());
      for (size_t arrayIndex = 0; arrayIndex < kArraySize; ++arrayIndex)
      {
          const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex];
          if (baseBitSet.any())
          {
              return baseBitSet.first() + arrayIndex * priv::kDefaultBitSetSize;
          }
      }
      UNREACHABLE();
      return 0;
  }
  
  template <std::size_t N>
  constexpr typename BitSetArray<N>::param_type BitSetArray<N>::last() const
  {
      ASSERT(any());
      for (size_t arrayIndex = kArraySize; arrayIndex > 0; --arrayIndex)
      {
          const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex - 1];
          if (baseBitSet.any())
          {
              return baseBitSet.last() + (arrayIndex - 1) * priv::kDefaultBitSetSize;
          }
      }
      UNREACHABLE();
      return 0;
  }
  
  template <std::size_t N>
  constexpr typename BitSetArray<N>::value_type BitSetArray<N>::bits(size_t index) const
  {
      return mBaseBitSetArray[index].bits();
  }
  
  template <std::size_t N>
  constexpr BitSetArray<N> BitSetArray<N>::Mask(std::size_t x)
  {
      BitSetArray result;
  
      for (size_t arrayIndex = 0; arrayIndex < kArraySize; ++arrayIndex)
      {
          const size_t bitOffset = arrayIndex * priv::kDefaultBitSetSize;
          if (x <= bitOffset)
          {
              break;
          }
          const size_t bitsInThisIndex        = std::min(x - bitOffset, priv::kDefaultBitSetSize);
          result.mBaseBitSetArray[arrayIndex] = BaseBitSet::Mask(bitsInThisIndex);
      }
  
      return result;
  }
  }  // namespace angle
  
  template <size_t N, typename BitsT, typename ParamT>
  inline constexpr angle::BitSetT<N, BitsT, ParamT> operator&(
      const angle::BitSetT<N, BitsT, ParamT> &lhs,
      const angle::BitSetT<N, BitsT, ParamT> &rhs)
  {
      angle::BitSetT<N, BitsT, ParamT> result(lhs);
      result &= rhs.bits();
      return result;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  inline constexpr angle::BitSetT<N, BitsT, ParamT> operator|(
      const angle::BitSetT<N, BitsT, ParamT> &lhs,
      const angle::BitSetT<N, BitsT, ParamT> &rhs)
  {
      angle::BitSetT<N, BitsT, ParamT> result(lhs);
      result |= rhs.bits();
      return result;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  inline constexpr angle::BitSetT<N, BitsT, ParamT> operator^(
      const angle::BitSetT<N, BitsT, ParamT> &lhs,
      const angle::BitSetT<N, BitsT, ParamT> &rhs)
  {
      angle::BitSetT<N, BitsT, ParamT> result(lhs);
      result ^= rhs.bits();
      return result;
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  inline bool operator==(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
  {
      return lhs.bits() == rhs.bits();
  }
  
  template <size_t N, typename BitsT, typename ParamT>
  inline bool operator!=(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
  {
      return !(lhs == rhs);
  }
  
  #endif  // COMMON_BITSETITERATOR_H_