12
\$\begingroup\$

The use cases I’m facing require me to have a C++ data type that can store and manipulate the state of somewhere between 400 and 500 bits. In addition it is necessary to be able to store that state within SQL server databases in an efficient manner, i.e. not wasting unnecessary space because there will be a lot of such database records eventually.

I had a look at std::bitset which is capable of storing that amount of bits but lacks the capability to export its internal state in an efficient way. It offers to_ulong and to_ullong which both are too small to store up to 500 bits and to_string which would result in a string of 500 characters, i.e. one character per bit which seems rather inefficient.

I figured I could pack all bits that I require into a byte array that I could store in the SQL database as a blob and hence use eight times less space compared to storing them as a 500 character string.

First I tried to turn the output of std::bitset into a byte array but realized that the logic required to do so might as well be turned into its own class that directly operates with a byte array.

The class that I’m posting here is the result of that approach. Its interface is inspired by std::bitset but deviates in some cases and does not offer all functionality that std::bitset does, simply because I have no use for that functionality.

It does provide read-only access to the array that stores the bits and offers creating an object from such an array so that I can store to and load the state from the database.

The class is designed to be compiled with C++14 but I will migrate my code base to C++17 within a few months.

When reviewing, could you please consider commenting on the following topics?

  • Currently, there is no overloaded = operator, only a copy constructor. For this particular case, is overloading = necessary / does make sense?
  • Given that I switch to C++17: Are there any parts of the code that could be simplified using C++17?
  • I’m unsure how to overload the [] operator so that it can be used to set/get individual bits. I assume I'll need some kind of proxy object but I'm unsure how best to do it. Hints on how to do this would be appreciated.
  • I use #pragma once instead of the more traditional include guards because the compilers (Clang and Microsoft Visual C++) on all platforms that I build for (Android, iOS, Windows) support it. I’m unaware of any downsides of using it. Any comments regarding this?
  • I’m covering the class using the unit tests that I posted. They are built on top of Microsoft’s CppUnitTestFramework that ships together with Visual Studio. Comments regarding those tests are highly appreciated.
  • The method to access individual bits is named get while the corresponding method of std::bitset is named test. I used get as name because “it just makes more sense to me than test”. You might consider this to be a drawback because the class cannot be used as a drop-in replacement for std::bitset that way. However, as mentioned not all functionality is provided anyway (<<, >>, [] operators are missing, etc.). Comments regarding this?

The class:

#pragma once

#include <array>


namespace common
{
  template<std::size_t bit_count>
  class bitpattern
  {
  public:

    static constexpr std::size_t BitCount  = bit_count;
    static constexpr std::size_t ByteCount = (bit_count % CHAR_BIT) ? (bit_count / CHAR_BIT) + 1 : (bit_count / CHAR_BIT);


    bitpattern()
    {
    }


    // The string that is passed to this method is read from right to left, i.e.
    // the last character on the right end of the string is turned into the bit
    // at index 0.
    bitpattern(const std::string bits)
    {
      std::size_t character_count = (bits.length() > bit_count) ? bit_count : bits.length();
      std::size_t first_character = bits.length() - 1;

      for(std::size_t i = 0; i < character_count; i++)
      {
        switch(bits[first_character - i])
        {
          case '0': continue;
          case '1': set(i); break;
          default : throw std::invalid_argument("Argument string contains characters other than '0' and '1'.");
        }
      }
    }


    bitpattern(const std::array<uint8_t, ByteCount> bits)
    {
      _bit_container = bits;
      _bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits are 0
    }


    bitpattern(const bitpattern<bit_count>& pattern)
    {
      _bit_container = pattern._bit_container;
    }


    bitpattern<bit_count>& flip()
    {
      for(uint8_t& byte : _bit_container)
      {
        byte = ~byte;
      }

      _bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
      return *this;
    }


    bitpattern<bit_count>& flip(std::size_t index)
    {
      _throw_if_too_large(index);
      _bit_container[index / CHAR_BIT] ^= (1u << (index % CHAR_BIT));
      return *this;
    }


    bool get(std::size_t index) const
    {
      _throw_if_too_large(index);
      return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
    }


    bitpattern<bit_count>& set(std::size_t index)
    {
      _throw_if_too_large(index);
      _bit_container[index / CHAR_BIT] |= (1u << (index % CHAR_BIT));
      return *this;
    }


    bitpattern<bit_count>& reset(std::size_t index)
    {
      _throw_if_too_large(index);
      _bit_container[index / CHAR_BIT] &= ~(1u << (index % CHAR_BIT));
      return *this;
    }


    bitpattern<bit_count>& reset()
    {
      _bit_container.fill(0);
      return *this;
    }


    bool all() const
    {
      std::size_t i = 0;

      for(; i < (ByteCount - 1); i++)
      {
        if(_bit_container[i] != 0b1111'1111)
        {
          return false;
        }
      }

      // The last byte is treated separately because it could contain
      // padding bits that are 0.
      return _bit_container[i] == _padding_bit_mask;
    }


    bool any() const
    {
      for(uint8_t byte : _bit_container)
      {
        if(byte > 0)
        {
          return true;
        }
      }

      return false;
    }


    bool none() const
    {
      for(uint8_t byte : _bit_container)
      {
        if(byte > 0)
        {
          return false;
        }
      }

      return true;
    }


    std::size_t count() const
    {
      std::size_t count = 0;

      for(uint8_t byte : _bit_container)
      {
        // Implementation of the Hamming Weight algorithm for 8-bit numbers.
        // See https://en.wikipedia.org/wiki/Hamming_weight
        // and https://stackoverflow.com/a/30692782/5548098
        byte = byte - ((byte >> 1) & 0b0101'0101);
        byte = (byte & 0b0011'0011) + ((byte >> 2) & 0b0011'0011);
        count += ((byte + (byte >> 4)) & 0b0000'1111);
      }

      return count;
    }


    bool operator==(const bitpattern<bit_count>& right) const
    {
      for(std::size_t i = 0; i < ByteCount; i++)
      {
        if(_bit_container[i] != right._bit_container[i])
        {
          return false;
        }
      }

      return true;
    }


    bool operator!=(const bitpattern<bit_count>& right) const
    {
      for(std::size_t i = 0; i < ByteCount; i++)
      {
        if(_bit_container[i] == right._bit_container[i])
        {
          return false;
        }
      }

      return true;
    }


    bitpattern<bit_count>& operator&=(const bitpattern<bit_count>& right)
    {
      for(std::size_t i = 0; i < ByteCount; i++)
      {
        _bit_container[i] &= right._bit_container[i];
      }

      return *this;
    }


    bitpattern<bit_count>& operator|=(const bitpattern<bit_count>& right)
    {
      for(std::size_t i = 0; i < ByteCount; i++)
      {
        _bit_container[i] |= right._bit_container[i];
      }

      return *this;
    }


    bitpattern<bit_count>& operator^=(const bitpattern<bit_count>& right)
    {
      for(std::size_t i = 0; i < ByteCount; i++)
      {
        _bit_container[i] ^= right._bit_container[i];
      }

      return *this;
    }


    bitpattern<bit_count> operator&(const bitpattern<bit_count>& right)
    {
      bitpattern<bit_count> resulting_pattern;

      for(std::size_t i = 0; i < ByteCount; i++)
      {
        resulting_pattern._bit_container[i] = _bit_container[i] & right._bit_container[i];
      }

      return resulting_pattern;
    }


    bitpattern<bit_count> operator|(const bitpattern<bit_count>& right)
    {
      bitpattern<bit_count> resulting_pattern;

      for(std::size_t i = 0; i < ByteCount; i++)
      {
        resulting_pattern._bit_container[i] = _bit_container[i] | right._bit_container[i];
      }

      return resulting_pattern;
    }


    bitpattern<bit_count> operator^(const bitpattern<bit_count>& right)
    {
      bitpattern<bit_count> resulting_pattern;

      for(std::size_t i = 0; i < ByteCount; i++)
      {
        resulting_pattern._bit_container[i] = _bit_container[i] ^ right._bit_container[i];
      }

      return resulting_pattern;
    }


    bitpattern<bit_count> operator~()
    {
      bitpattern<bit_count> inverted_pattern;

      for(std::size_t i = 0; i < ByteCount; i++)
      {
        inverted_pattern._bit_container[i] = ~_bit_container[i];
      }

      inverted_pattern._bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
      return inverted_pattern;
    }


    // Note that the string generated by this method must be read from
    // right to left, i.e. the bit with index 0 is to be found at the
    // right end of the string. The approach is taken from numbers where
    // the least significant number is found at the right end.
    std::string to_string() const
    {
      std::string pattern;
      pattern.reserve(bit_count);

      for(int i = (bit_count - 1); i >= 0; i--)
      {
        pattern.append(get(i) ? "1" : "0");
      }

      return pattern;
    }


    const std::array<uint8_t, ByteCount>& array() const
    {
      return _bit_container;
    }


  private:

    void _throw_if_too_large(std::size_t index) const
    {
      if(index >= bit_count)
      {
        throw std::out_of_range("Index is too large.");
      }
    }


    static constexpr uint8_t _create_padding_bit_mask()
    {
      uint8_t count    = bit_count % CHAR_BIT;
      uint8_t bit_mask = 0b1111'1111;

      if(count)
      {
        for(int i = (CHAR_BIT - 1); i >= count; i--)
        {
          bit_mask ^= (1 << i);
        }
      }

      return bit_mask;
    }


    static constexpr uint8_t _padding_bit_mask = _create_padding_bit_mask();
    std::array<uint8_t, ByteCount> _bit_container{};
  };
}

Associated unit tests:

#include "CppUnitTest.h"
#include "../bitpattern/bitpattern.h"

#include <map>

using namespace Microsoft::VisualStudio::CppUnitTestFramework;


namespace common
{
  TEST_CLASS(bitpatterntests)
  {
  public:

    TEST_METHOD(ConstructionZeroInitializesArray)
    {
      bitpattern<69> pattern;
      std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
      std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooLarge)
    {
      std::string bits = "10101110100011010101011100101";
      bitpattern<14> pattern_from_string(bits);
      bitpattern<14> pattern_reference;
      Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(2).set(5).set(6).set(7).set(9).set(11).set(13));
    }


    TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooSmall)
    {
      std::string bits = "101001110101010";
      bitpattern<28> pattern_from_string(bits);
      bitpattern<28> pattern_reference;
      Assert::IsTrue(pattern_from_string == pattern_reference.set(1).set(3).set(5).set(7).set(8).set(9).set(12).set(14));
    }


    TEST_METHOD(ConstructionFromStringWorksWithStringOfSameLength)
    {
      std::string bits = "001000110011010001011";
      bitpattern<21> pattern_from_string(bits);
      bitpattern<21> pattern_reference;
      Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(1).set(3).set(7).set(9).set(10).set(13).set(14).set(18));
    }


    TEST_METHOD(ConstructionFromEmptyStringZeroInitializesArray)
    {
      std::string bits = "";
      bitpattern<13> pattern(bits);
      std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
      std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0 };
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(ConstructionFromStringContainingCharactersOtherThanOneAndZeroThrowsException)
    {
      std::string bits = "01010A0102";
      auto func = [bits] { bitpattern<29> pattern(bits); };
      Assert::ExpectException<std::invalid_argument>(func);
    }


    TEST_METHOD(ConstructionFromArrayZeros1PaddingBits)
    {
      bitpattern<7> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0111'1111);
    }


    TEST_METHOD(ConstructionFromArrayZeros2PaddingBits)
    {
      bitpattern<6> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0011'1111);
    }


    TEST_METHOD(ConstructionFromArrayZeros3PaddingBits)
    {
      bitpattern<5> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0001'1111);
    }


    TEST_METHOD(ConstructionFromArrayZeros4PaddingBits)
    {
      bitpattern<4> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0000'1111);
    }


    TEST_METHOD(ConstructionFromArrayZeros5PaddingBits)
    {
      bitpattern<3> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0000'0111);
    }


    TEST_METHOD(ConstructionFromArrayZeros6PaddingBits)
    {
      bitpattern<2> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0000'0011);
    }


    TEST_METHOD(ConstructionFromArrayZeros7PaddingBits)
    {
      bitpattern<1> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
      Assert::IsTrue(pattern.array()[0] == 0b0000'0001);
    }


    TEST_METHOD(CopyConstructedObjectIsEqualToOriginalObject)
    {
      bitpattern<34> pattern;
      bitpattern<34> pattern_copied(pattern);
      Assert::IsTrue(pattern == pattern_copied);
    }


    TEST_METHOD(FlipInvertsAllBitsExceptPaddingBits)
    {
      std::array<uint8_t, 4> input           = { 0b0011'1010, 0b1111'1011, 0b0001'1011, 0b0110'1010 };
      std::array<uint8_t, 4> expected_output = { 0b1100'0101, 0b0000'0100, 0b1110'0100, 0b0000'0101 };
      bitpattern<27> pattern(input);
      pattern.flip();
      std::array<uint8_t, 4> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(FlipInvertsAllBitsIfThereAreNoPaddingBits)
    {
      std::array<uint8_t, 3> input           = { 0b1010'0110, 0b1111'1111, 0b0110'1001 };
      std::array<uint8_t, 3> expected_output = { 0b0101'1001, 0b0000'0000, 0b1001'0110 };
      bitpattern<24> pattern(input);
      pattern.flip();
      std::array<uint8_t, 3> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(FlipInvertsTheSpecifiedBit)
    {
      std::array<uint8_t, 5> input           = { 0b0010'0010, 0b1010'1001, 0b0110'0101, 0b1101'0000, 0b0011'1110 };
      std::array<uint8_t, 5> expected_output = { 0b0000'1011, 0b0011'1001, 0b0110'1101, 0b0101'1000, 0b0000'0110 };
      bitpattern<36> pattern(input);
      pattern.flip(0).flip(3).flip(5).flip(12).flip(15).flip(19).flip(27).flip(31).flip(35);
      std::array<uint8_t, 5> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(FlipThrowsExceptionForIndexThatIsTooLarge)
    {
      bitpattern<12> pattern;
      auto func = [&pattern] { pattern.flip(pattern.BitCount); };
      Assert::ExpectException<std::out_of_range>(func);
    }


    TEST_METHOD(GetReturnsTheValueOfTheSpecifiedBit)
    {
      std::array<uint8_t, 3> input = { 0b0110'0100, 0b0010'1011 };
      bitpattern<23> pattern(input);
      bool is_set     =  pattern.get(2)  &&
                         pattern.get(5)  &&
                         pattern.get(6)  &&
                         pattern.get(8)  &&
                         pattern.get(9)  &&
                         pattern.get(11) &&
                         pattern.get(13);
      bool is_not_set = !pattern.get(0)  &&
                        !pattern.get(1)  &&
                        !pattern.get(3)  &&
                        !pattern.get(4)  &&
                        !pattern.get(7)  &&
                        !pattern.get(10) &&
                        !pattern.get(12) &&
                        !pattern.get(14) &&
                        !pattern.get(15);
      Assert::IsTrue(is_set && is_not_set);
    }


    TEST_METHOD(GetThrowsExceptionForIndexThatIsTooLarge)
    {
      bitpattern<18> pattern;
      auto func = [&pattern] { pattern.get(pattern.BitCount); };
      Assert::ExpectException<std::out_of_range>(func);
    }


    TEST_METHOD(SetChangesTheSpecifiedBitToOne)
    {
      std::array<uint8_t, 3> expected_output = { 0b0011'1001, 0b0100'0100, 0b0001'0110 };
      bitpattern<21> pattern;
      pattern.set(0).set(3).set(4).set(5).set(10).set(14).set(17).set(18).set(20);
      std::array<uint8_t, 3> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(SetAllowsChangingAllBits)
    {
      std::array<uint8_t, 12> input           = {   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,           0 };
      std::array<uint8_t, 12> expected_output = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0000'0111 };

      bitpattern<91> pattern;

      for(std::size_t i = 0; i < pattern.BitCount; i++)
      {
        pattern.set(i);
      }

      std::array<uint8_t, 12> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(SetThrowsExceptionForIndexThatIsTooLarge)
    {
      bitpattern<44> pattern;
      auto func = [&pattern] { pattern.get(pattern.BitCount); };
      Assert::ExpectException<std::out_of_range>(func);
    }


    TEST_METHOD(ResetChangesTheSpecifiedBitToZero)
    {
      std::array<uint8_t, 4> input           = { 0b0111'1011, 0b0111'0101, 0b1101'0110, 0b0001'0111 };
      std::array<uint8_t, 4> expected_output = { 0b0001'1001, 0b0001'0001, 0b1101'0010, 0b0000'0000 };
      bitpattern<25> pattern(input);
      pattern.reset(1).reset(5).reset(6).reset(10).reset(13).reset(14).reset(16).reset(18).reset(24);
      std::array<uint8_t, 4> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(ResetChangesAllBitsToZero)
    {
      std::array<uint8_t, 12> input           = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
      std::array<uint8_t, 12> expected_output = {   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,           0 };
      bitpattern<94> pattern;
      pattern.reset();
      std::array<uint8_t, 12> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(ResetChangesAllBitsToZeroIndividually)
    {
      std::array<uint8_t, 12> input           = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
      std::array<uint8_t, 12> expected_output = {   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,           0 };

      bitpattern<94> pattern;

      for(std::size_t i = 0; i < pattern.BitCount; i++)
      {
        pattern.reset(i);
      }

      std::array<uint8_t, 12> actual_output = pattern.array();
      Assert::IsTrue(actual_output == expected_output);
    }


    TEST_METHOD(ResetThrowsExceptionForIndexThatIsTooLarge)
    {
      bitpattern<86> pattern;
      auto func = [&pattern] { pattern.get(pattern.BitCount); };
      Assert::ExpectException<std::out_of_range>(func);
    }


    TEST_METHOD(AllReturnsTrueIfAllBitsAreOne)
    {
      std::array<uint8_t, 8> input = { 255, 255, 255, 255, 255, 255, 255, 255 };
      bitpattern<58> pattern(input);
      Assert::IsTrue(pattern.all());
    }


    TEST_METHOD(AllReturnsTrueIfPaddingBitsAreZero)
    {
      std::array<uint8_t, 5> input = { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b0000'0001 };
      bitpattern<33> pattern(input);
      Assert::IsTrue(pattern.all());
    }


    TEST_METHOD(AllReturnsFalseIfNotAllBitsAreOne)
    {
      std::array<uint8_t, 5> input = { 0b0111'0111, 0b1111'1111, 0b1101'0111, 0b1111'1110, 0b0001'0000 };
      bitpattern<37> pattern(input);
      Assert::IsFalse(pattern.all());
    }


    TEST_METHOD(AnyReturnsTrueIfAnyBitIsOne)
    {
      std::array<uint8_t, 3> input = { 0b0000'0000, 0b0010'0000, 0b0000'0000 };
      bitpattern<18> pattern(input);
      Assert::IsTrue(pattern.any());
    }


    TEST_METHOD(AnyReturnsFalseIfAllBitAreZero)
    {
      std::array<uint8_t, 3> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000 };
      bitpattern<18> pattern(input);
      Assert::IsFalse(pattern.any());
    }


    TEST_METHOD(NoneReturnsTrueIfNoBitsAreOne)
    {
      std::array<uint8_t, 4> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 };
      bitpattern<29> pattern(input);
      Assert::IsTrue(pattern.none());
    }


    TEST_METHOD(NoneReturnsFalseIfAnyBitsAreOne)
    {
      std::array<uint8_t, 4> input = { 0b0100'0100, 0b0001'0000, 0b0010'0000, 0b0000'0010 };
      bitpattern<29> pattern(input);
      Assert::IsFalse(pattern.none());
    }


    TEST_METHOD(CountReturnsTheCorrectNumberOfBitsSetToOne)
    {
      const std::map<std::size_t, std::array<uint8_t, 4>> records
      {
        // Bit count (map key) does not include padding bits
        {  0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 } },
        { 15, { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
        { 16, { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
        { 16, { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
        { 15, { 0b0010'0001, 0b1011'0011, 0b0011'0001, 0b0011'1011 } },
        { 11, { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
        {  7, { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
        {  4, { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
        {  2, { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
        {  0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b1100'0000 } },
        {  7, { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
        { 18, { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
        { 30, { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111 } },
      };

      for(auto const& record : records)
      {
        bitpattern<30> pattern(record.second);
        std::size_t count    = pattern.count();
        std::wstring message = L"Expected " + std::to_wstring(record.first) + L" ones (1) in " + wstring_from_string(pattern.to_string()) + L" but counted " + std::to_wstring(count);
        Assert::IsTrue(count == record.first, message.c_str());
      }
    }


    TEST_METHOD(EqualOperatorReturnsTrueWhenComparingAnObjectWithItself)
    {
      bitpattern<60> pattern;
      pattern.set(48).set(12);
      Assert::IsTrue(pattern == pattern);
    }


    TEST_METHOD(EqualOperatorReturnsTrueWhenComparingTwoSimilarObjects)
    {
      std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
      bitpattern<24> pattern1(input);
      bitpattern<24> pattern2(input);
      Assert::IsTrue(pattern1 == pattern2);
    }


    TEST_METHOD(EqualOperatorReturnsFalseWhenComparingTwoDifferentObjects)
    {
      bitpattern<17> pattern1(std::array<uint8_t, 3> { 0b0101'1010, 0b1100'0001, 0b0001'0011 });
      bitpattern<17> pattern2(std::array<uint8_t, 3> { 0b1110'0110, 0b1001'0110, 0b0111'0000 });
      Assert::IsFalse(pattern1 == pattern2);
    }


    TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingAnObjectWithItself)
    {
      bitpattern<129> pattern;
      pattern.set(128).set(0);
      Assert::IsFalse(pattern != pattern);
    }


    TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingTwoSimilarObjects)
    {
      std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
      bitpattern<24> pattern1(input);
      bitpattern<24> pattern2(input);
      Assert::IsFalse(pattern1 != pattern2);
    }


    TEST_METHOD(NotEqualOperatorReturnsTrueWhenComparingTwoDifferentObjects)
    {
      bitpattern<21> pattern1(std::array<uint8_t, 3> { 0b0111'0011, 0b0101'0101, 0b0111'0100 });
      bitpattern<21> pattern2(std::array<uint8_t, 3> { 0b1010'1001, 0b1010'0110, 0b1000'1111 });
      Assert::IsTrue(pattern1 != pattern2);
    }


    TEST_METHOD(BitwiseAndAssignmentOperatorProducesAndResultOfTwoPatterns)
    {
      std::array<uint8_t, 3> left            = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
      std::array<uint8_t, 3> right           = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
      std::array<uint8_t, 3> expected_result = { 0b1010'0010, 0b0000'0110, 0b0110'0100 };
      bitpattern<23> pattern_left (left);
      bitpattern<23> pattern_right(right);
      pattern_left &= pattern_right;
      std::array<uint8_t, 3> actual_result = pattern_left.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(BitwiseOrAssignmentOperatorProducesOrResultOfTwoPatterns)
    {
      std::array<uint8_t, 3> left            = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
      std::array<uint8_t, 3> right           = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
      std::array<uint8_t, 3> expected_result = { 0b1110'1111, 0b1111'0110, 0b0111'1111 };
      bitpattern<23> pattern_left (left);
      bitpattern<23> pattern_right(right);
      pattern_left |= pattern_right;
      std::array<uint8_t, 3> actual_result = pattern_left.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(BitwiseXorAssignmentOperatorProducesXorResultOfTwoPatterns)
    {
      std::array<uint8_t, 3> left            = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
      std::array<uint8_t, 3> right           = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
      std::array<uint8_t, 3> expected_result = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
      bitpattern<23> pattern_left (left);
      bitpattern<23> pattern_right(right);
      pattern_left ^= pattern_right;
      std::array<uint8_t, 3> actual_result = pattern_left.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(BitwiseAndOperatorProducesAndResultOfMultiplePatterns)
    {
      std::array<uint8_t, 3> input1          = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
      std::array<uint8_t, 3> input2          = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
      std::array<uint8_t, 3> input3          = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
      std::array<uint8_t, 3> expected_result = { 0b0010'0100, 0b0010'0010, 0b0010'1000 };
      bitpattern<23> pattern1(input1);
      bitpattern<23> pattern2(input2);
      bitpattern<23> pattern3(input3);
      bitpattern<23> pattern_result = pattern1 & pattern2 & pattern3;
      std::array<uint8_t, 3> actual_result = pattern_result.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(BitwiseOrOperatorProducesOrResultOfMultiplePatterns)
    {
      std::array<uint8_t, 3> input1          = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
      std::array<uint8_t, 3> input2          = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
      std::array<uint8_t, 3> input3          = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
      std::array<uint8_t, 3> expected_result = { 0b1111'1101, 0b1111'1111, 0b0111'1111 };
      bitpattern<23> pattern1(input1);
      bitpattern<23> pattern2(input2);
      bitpattern<23> pattern3(input3);
      bitpattern<23> pattern_result = pattern1 | pattern2 | pattern3;
      std::array<uint8_t, 3> actual_result = pattern_result.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(BitwiseXorOperatorProducesXorResultOfMultiplePatterns)
    {
      std::array<uint8_t, 3> input1          = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
      std::array<uint8_t, 3> input2          = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
      std::array<uint8_t, 3> input3          = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
      std::array<uint8_t, 3> expected_result = { 0b0111'0101, 0b1111'1010, 0b0111'1001 };
      bitpattern<23> pattern1(input1);
      bitpattern<23> pattern2(input2);
      bitpattern<23> pattern3(input3);
      bitpattern<23> pattern_result = pattern1 ^ pattern2 ^ pattern3;
      std::array<uint8_t, 3> actual_result = pattern_result.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(BitwiseNotOperatorInvertsThePattern)
    {
      std::array<uint8_t, 3> input           = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
      std::array<uint8_t, 3> expected_result = { 0b1011'0010, 0b0000'1111, 0b0110'0100 };
      bitpattern<23> pattern(input);
      bitpattern<23> pattern_inverted = ~pattern;
      std::array<uint8_t, 3> actual_result = pattern_inverted.array();
      Assert::IsTrue(actual_result == expected_result);
    }


    TEST_METHOD(InvertingTwiceResultsInTheSameObject)
    {
      bitpattern<24> pattern1(std::array<uint8_t, 3> { 0b0110'0111, 0b1111'0100, 0b0111'1011 });
      bitpattern<24> pattern2 = ~pattern1;
      pattern2 = ~pattern2;
      Assert::IsTrue(pattern1 == pattern2);
    }


    TEST_METHOD(ToStringReturnsCorrectOutput_)
    {
      const std::map<std::string, std::array<uint8_t, 4>> records
      {
        { "10101010101010101010101010101010", { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
        { "00000000111111110000000011111111", { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
        { "11111111000000001111111100000000", { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
        { "00110011001100110011001100110011", { 0b0011'0011, 0b0011'0011, 0b0011'0011, 0b0011'0011 } },
        { "11101110010100100010100010000100", { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
        { "01100000000110000000001000111000", { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
        { "00000001000000010000000100000001", { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
        { "00000001000000000000000100000000", { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
        { "00011111000001110000001100001111", { 0b0000'1111, 0b0000'0011, 0b0000'0111, 0b0001'1111 } },
        { "00000001000000000001100011110000", { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
        { "11111111000000000111111010111110", { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
        { "00101011001111101110000000001111", { 0b0000'1111, 0b1110'0000, 0b0011'1110, 0b0010'1011 } },
      };

      for(auto const& record : records)
      {
        bitpattern<30> pattern(record.second);
        std::size_t substr_index    = record.first.length() - pattern.BitCount;
        std::string expected_output = record.first.substr(substr_index);
        std::string actual_output   = pattern.to_string();
        std::wstring message        = L"Expected " + wstring_from_string(expected_output) + L" but was " + wstring_from_string(actual_output);
        Assert::IsTrue(actual_output == expected_output, message.c_str());
      }
    }


  private:

    std::wstring wstring_from_string(const std::string& string)
    {
      std::wstring wstring;
      wstring.assign(string.begin(), string.end());
      return wstring;
    }
  };
}
\$\endgroup\$
6
\$\begingroup\$

Here are some things that may help you improve your program.

Use all required #includes

The templated class uses CHAR_BIT but is missing this line that provides the definition:

#include <climits>

Eliminate unused variables

The variable input in several tests in your code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.

Be careful with naming

I'm not sure how useful it is to take care to wrap things into a namespace, but then use the name common for it. It isn't necessarily wrong, but it's worth pondering whether there's a better, more apt name for the namespace.

Keep maintaining the tests

The tests are quite good. I was able to translate them all into the standard, non-Microsoft CppUnit in a few minutes. All tests passed on my 64-bit Linux box using gcc.

Let the compiler generate the empty constructor

Instead of explicitly writing the empty constructor, explicitly tell the compiler to construct it instead:

bitpattern() = default;

The intent is a bit more clear in my opinion.

Consider adding some constructors

At the moment this code won't compile:

  std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
  bitpattern<24> pattern1(input);
  bitpattern<22> pattern2(input);
  bitpattern<24> pattern3(pattern2);

It would be nice to have the ability to create longer bit patterns from smaller ones.

It would also be nice to provide constexpr constructors for patterns like this:

  constexpr bitpattern<23> pattern{0x6423};

Here's a way to do that:

constexpr bitpattern(unsigned long long val) 
{
    for (std::size_t i=0; i < ByteCount; ++i) {
        _bit_container[i] = val & 0xff;
        val >>= 8;
    }
}

Note that this uses for loop in a constexpr function and uses the operator[] on the std::array and so requires C++17 or later.

Consider adding operator[]

The std::bitset uses std::bitset::reference to enable operator[]. You could probably do the same. Note that there are two flavors; one is constexpr and returns an actual bool and the other returns a reference object. Here's one way to do that. First, here's the reference class which is in the public section of the bitpattern class:

class reference {
friend class bitpattern<bit_count>;
public:
  reference& operator=(bool x) { 
      if (x) {
          *ptr |= mask;
      } else {
          *ptr &= ~mask;
      }
      return *this;
  }
  reference();  // leave undefined
  reference& operator=(const reference& x) {
      bool bit{x};
      if (bit) {
          *ptr |= mask;
      } else {
          *ptr &= ~mask;
      }
      return *this;
  }
  ~reference() = default;
  operator bool() const {
      return *ptr & mask;
  }
  bool operator~() const {
      return !(*ptr & mask);
  }
  reference& flip() {
      *ptr ^= mask;
      return *this;
  }

private:
  reference(uint8_t *ptr, uint8_t mask) :
    ptr{ptr}, mask{mask} {} 
  uint8_t *ptr;
  uint8_t mask;
};

Here are the two types of operator[]:

constexpr bool operator[](std::size_t index) const
{
  return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}

reference operator[](std::size_t index) 
{
  _throw_if_too_large(index);
  return reference{&_bit_container[index / CHAR_BIT], 
      static_cast<uint8_t>(1 << (index % CHAR_BIT))};
}

Note that the constexpr can't throw, so providing an out-of-range index is simply undefined behavior as with std::bitset.

Add tests for operator[]

Here are the tests I addeed for the new operator[]:

void ConstexprIndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
  constexpr bitpattern<23> pattern{0x2b64};
  constexpr bool is_set     =  
                     pattern[2]  &&
                     pattern[5]  &&
                     pattern[6]  &&
                     pattern[8]  &&
                     pattern[9]  &&
                     pattern[11] &&
                     pattern[13];
  constexpr bool is_not_set = 
                    !pattern[0]  &&
                    !pattern[1]  &&
                    !pattern[3]  &&
                    !pattern[4]  &&
                    !pattern[7]  &&
                    !pattern[10] &&
                    !pattern[12] &&
                    !pattern[14] &&
                    !pattern[15];
  CPPUNIT_ASSERT(is_set && is_not_set);
}

void IndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
  bitpattern<23> pattern{0x2b64};
  bool is_set     =  
                     pattern[2]  &&
                     pattern[5]  &&
                     pattern[6]  &&
                     pattern[8]  &&
                     pattern[9]  &&
                     pattern[11] &&
                     pattern[13];
  bool is_not_set = 
                    !pattern[0]  &&
                    !pattern[1]  &&
                    !pattern[3]  &&
                    !pattern[4]  &&
                    !pattern[7]  &&
                    !pattern[10] &&
                    !pattern[12] &&
                    !pattern[14] &&
                    !pattern[15];
  CPPUNIT_ASSERT(is_set && is_not_set);
}
\$\endgroup\$
8
\$\begingroup\$

not directly answering your question, but just a notice: I would say the more elegant way would be just extending the std::bitset and add the extra methods you need, for ex. to_bytes():

template <size_t N>
class bitpattern : public std::bitset<N>
{
public:
    using byte_t = uint8_t;
    static constexpr size_t num_bytes = N/8 + ((N % 8 == 0) ? 0 : 1);
    using bytes_t = std::array<byte_t, num_bytes>;

    // declare approprite constructors and forward to the base class
    // using base class implementation

    // declare the extra functions you need, for ex.
    // (this is not the efficienst method, but just for demonstration)
    bytes_t to_bytes() const noexcept
    {
        bytes_t bytes;

        for (size_t bix = 0;  bix < num_bytes; bix++)
        {
            byte b = 0;
            for (size_t bitix = 0; (bitix<8) && (bix*8+bitix < N); bitix++)
                if (this->operator[] (bix*8 + bitix))
                    b |= (0x01 << bitix);
            bytes[bix] = b;
        }

        return bytes;
    }
};

Another way would be stay at std::bitset and using the appropriate non-class utility functions, for ex:

template <size_t N>
std::vector<uint8_t> to_bytes(const std::bitset<N>&);

This way (1. or 2.) you can take advantage of the functionalities std::bitset already offers.

\$\endgroup\$
  • \$\begingroup\$ Good answer. I think it would be interesting to compare the two approaches for efficiency. \$\endgroup\$ – Edward Dec 31 '18 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.