src/util/hei_bit_string.cpp - openbmc/openpower-libhei - Gitiles

 /** @file hei_bit_string.cpp
  *  @brief BitString and BitStringBuffer class definitions
  */

 #include <util/hei_bit_string.hpp>
 #include <util/hei_includes.hpp>

 #include <algorithm>

 namespace libhei
 {

 // ##############################################################################
 //                              BitString class
 // ##############################################################################

 // number of bits in a uint64_t
 const uint64_t BitString::UINT64_BIT_LEN = sizeof(uint64_t) * 8;
 // number of bits in a uint8_t
 const uint64_t BitString::UINT8_BIT_LEN = sizeof(uint8_t) * 8;

 //------------------------------------------------------------------------------

 uint64_t BitString::getFieldRight(uint64_t i_pos, uint64_t i_len) const
 {
     HEI_ASSERT(nullptr != getBufAddr());      // must to have a valid address
     HEI_ASSERT(0 < i_len);                    // must have at least one bit
     HEI_ASSERT(i_len <= UINT64_BIT_LEN);      // i_len length must be valid
     HEI_ASSERT(i_pos + i_len <= getBitLen()); // field must be within range

     // Get the relative address of this byte and the relative starting position
     // within the byte.
     uint64_t relPos = 0;
     uint8_t* relAddr = getRelativePosition(relPos, i_pos);

     // Get the length of the target bit field within this byte and the length of
     // the bit field for any remaining bits.
     uint64_t bf_len = i_len;
     uint64_t remain_len = 0;
     if (UINT8_BIT_LEN < relPos + i_len)
     {
         // The target bit field crosses a byte boundary. So truncate the bit
         // length for this byte and update the remaining length.
         bf_len = UINT8_BIT_LEN - relPos;
         remain_len = i_len - bf_len;
     }

     // Get the target bit field within this byte (right justified).
     uint8_t bf = *relAddr;
     bf <<= relPos;                 // Mask off uneeded bits on the left side.
     bf >>= UINT8_BIT_LEN - bf_len; // Right justify the value.

     // Check for any remaining bits after this target byte.
     if (0 != remain_len)
     {
         // Recursively call this function on the remaining bits and push them
         // into the right side of the return value.
         uint64_t val = static_cast<uint64_t>(bf) << remain_len;
         return val | getFieldRight(i_pos + bf_len, remain_len);
     }

     // Nothing more to do. Simply return this bit field.
     return bf;
 }

 //------------------------------------------------------------------------------

 void BitString::setFieldLeft(uint64_t i_pos, uint64_t i_len, uint64_t i_val)
 {
     HEI_ASSERT(nullptr != getBufAddr());      // must to have a valid address
     HEI_ASSERT(0 < i_len);                    // must have at least one bit
     HEI_ASSERT(i_len <= UINT64_BIT_LEN);      // i_len length must be valid
     HEI_ASSERT(i_pos + i_len <= getBitLen()); // field must be within range

     // Get the relative address of this byte and the relative starting position
     // within the byte.
     uint64_t relPos = 0;
     uint8_t* relAddr = getRelativePosition(relPos, i_pos);

     // Get the length of the target bit field within this byte and the length of
     // the bit field for any remaining bits.
     uint64_t bf_len = i_len;
     uint64_t remain_len = 0;
     if (UINT8_BIT_LEN < relPos + i_len)
     {
         // The target bit field crosses a byte boundary. So truncate the bit
         // length for this byte and update the remaining length.
         bf_len = UINT8_BIT_LEN - relPos;
         remain_len = i_len - bf_len;
     }

     // It is possible there are bits in this byte on either side of the target
     // bit field that must be preserved. Get the length of each of those bit
     // fields.
     uint64_t bf_l_len = relPos;
     uint64_t bf_r_len = UINT8_BIT_LEN - (bf_l_len + bf_len);

     // Get the target bit field from the left justified inputed value.
     uint8_t bf = (i_val >> (UINT64_BIT_LEN - bf_len)) << bf_r_len;

     // Get the bit fields on either side of the target bit field.
     uint64_t bf_l_shift = UINT8_BIT_LEN - bf_l_len;
     uint64_t bf_r_shift = UINT8_BIT_LEN - bf_r_len;

     uint8_t bf_l = *relAddr;
     bf_l >>= bf_l_shift;
     bf_l <<= bf_l_shift;

     uint8_t bf_r = *relAddr;
     bf_r <<= bf_r_shift;
     bf_r >>= bf_r_shift;

     // Combine all three parts of the byte and write it out to memory.
     *relAddr = bf_l | bf | bf_r;

     // Check for any remaining bits after this target byte.
     if (0 != remain_len)
     {
         // Recursively call this function on the remaining bits.
         setFieldLeft(i_pos + bf_len, remain_len, i_val << bf_len);
     }
 }

 //------------------------------------------------------------------------------

 void BitString::setPattern(uint64_t i_sPos, uint64_t i_sLen, uint64_t i_pattern,
                            uint64_t i_pLen)
 {
     HEI_ASSERT(nullptr != getBufAddr());        // must to have a valid address
     HEI_ASSERT(0 < i_sLen);                     // must have at least one bit
     HEI_ASSERT(i_sPos + i_sLen <= getBitLen()); // field must be within range
     HEI_ASSERT(0 < i_pLen);                     // must have at least one bit
     HEI_ASSERT(i_pLen <= UINT64_BIT_LEN);       // i_pLen length must be valid

     // Get a bit string for the pattern subset (right justified).
     // Note that we cannot use a BitStringBuffer here because this function
     // could be used in the constructor of BitStringBuffer, which could causes
     // an infinite loop.
     uint8_t a[sizeof(i_pattern)] = {};
     BitString bs{sizeof(i_pattern) * 8, a};
     bs.setFieldRight(0, i_pLen, i_pattern);

     // Iterate the range in chunks the size of i_pLen.
     uint64_t endPos = i_sPos + i_sLen;
     for (uint64_t pos = i_sPos; pos < endPos; pos += i_pLen)
     {
         // The true chunk size is either i_pLen or the leftovers at the end.
         uint64_t len = std::min(i_pLen, endPos - pos);

         // Get this chunk's pattern value, truncate (right justified) if needed.
         uint64_t pattern = bs.getFieldRight(0, len);

         // Set the pattern in this string.
         setFieldRight(pos, len, pattern);
     }
 }

 //------------------------------------------------------------------------------

 void BitString::setString(const BitString& i_sStr, uint64_t i_sPos,
                           uint64_t i_sLen, uint64_t i_dPos)
 {
     // Ensure the source parameters are valid.
     HEI_ASSERT(nullptr != i_sStr.getBufAddr());
     HEI_ASSERT(0 < i_sLen); // at least one bit to copy
     HEI_ASSERT(i_sPos + i_sLen <= i_sStr.getBitLen());

     // Ensure the destination has at least one bit available to copy.
     HEI_ASSERT(nullptr != getBufAddr());
     HEI_ASSERT(i_dPos < getBitLen());

     // If the source length is greater than the destination length than the
     // extra source bits are ignored.
     uint64_t actLen = std::min(i_sLen, getBitLen() - i_dPos);

     // The bit strings may be in overlapping memory spaces. So we need to copy
     // the data in the correct direction to prevent overlapping.
     uint64_t sRelOffset = 0, dRelOffset = 0;
     uint8_t* sRelAddr = i_sStr.getRelativePosition(sRelOffset, i_sPos);
     uint8_t* dRelAddr = getRelativePosition(dRelOffset, i_dPos);

     // Copy the data.
     if ((dRelAddr == sRelAddr) && (dRelOffset == sRelOffset))
     {
         // Do nothing. The source and destination are the same.
     }
     else if ((dRelAddr < sRelAddr) ||
              ((dRelAddr == sRelAddr) && (dRelOffset < sRelOffset)))
     {
         // Copy the data forward.
         for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
         {
             uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

             uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len);
             setFieldRight(i_dPos + pos, len, value);
         }
     }
     else // Copy the data backwards.
     {
         // Get the first position of the last chunk (byte aligned).
         uint64_t lastPos = ((actLen - 1) / UINT64_BIT_LEN) * UINT64_BIT_LEN;

         // Start with the last chunk and work backwards.
         for (int32_t pos = lastPos; 0 <= pos; pos -= UINT64_BIT_LEN)
         {
             uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);
             uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len);
             setFieldRight(i_dPos + pos, len, value);
         }
     }
 }

 //------------------------------------------------------------------------------

 void BitString::maskString(const BitString& i_mask)
 {
     // Get the length of the smallest string.
     uint64_t actLen = std::min(getBitLen(), i_mask.getBitLen());

     for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
     {
         uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

         uint64_t dVal = getFieldRight(pos, len);
         uint64_t sVal = i_mask.getFieldRight(pos, len);

         setFieldRight(pos, len, dVal & ~sVal);
     }
 }

 //------------------------------------------------------------------------------

 bool BitString::isEqual(const BitString& i_str) const
 {
     if (getBitLen() != i_str.getBitLen())
         return false; // size not equal

     for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
     {
         uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

         if (getFieldRight(pos, len) != i_str.getFieldRight(pos, len))
             return false; // bit strings do not match
     }

     return true; // bit strings match
 }

 //------------------------------------------------------------------------------

 bool BitString::isZero() const
 {
     for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
     {
         uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

         if (0 != getFieldRight(pos, len))
             return false; // something is non-zero
     }

     return true; // everything was zero
 }

 //------------------------------------------------------------------------------

 uint64_t BitString::getSetCount(uint64_t i_pos, uint64_t i_len) const
 {
     uint64_t endPos = i_pos + i_len;

     HEI_ASSERT(endPos <= getBitLen());

     uint64_t count = 0;

     for (uint64_t i = i_pos; i < endPos; i++)
     {
         if (isBitSet(i))
             count++;
     }

     return count;
 }

 //------------------------------------------------------------------------------

 bool BitString::operator<(const BitString& i_str) const
 {
     if (getBitLen() < i_str.getBitLen())
     {
         return true;
     }
     else if (getBitLen() == i_str.getBitLen())
     {
         // Can only compare the bit strings if the length is the same.
         for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
         {
             uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

             auto l_str = getFieldRight(pos, len);
             auto r_str = i_str.getFieldRight(pos, len);

             if (l_str < r_str)
             {
                 return true;
             }
             // The loop can only continue if the values are equal.
             else if (l_str > r_str)
             {
                 return false;
             }
         }
     }

     return false;
 }

 //------------------------------------------------------------------------------

 BitStringBuffer BitString::operator~() const
 {
     BitStringBuffer bsb(getBitLen());

     for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
     {
         uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

         uint64_t dVal = getFieldRight(pos, len);

         bsb.setFieldRight(pos, len, ~dVal);
     }

     return bsb;
 }

 //------------------------------------------------------------------------------

 BitStringBuffer BitString::operator&(const BitString& i_bs) const
 {
     // Get the length of the smallest string.
     uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen());

     BitStringBuffer bsb(actLen);

     for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
     {
         uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

         uint64_t dVal = getFieldRight(pos, len);
         uint64_t sVal = i_bs.getFieldRight(pos, len);

         bsb.setFieldRight(pos, len, dVal & sVal);
     }

     return bsb;
 }

 //------------------------------------------------------------------------------

 BitStringBuffer BitString::operator|(const BitString& i_bs) const
 {
     // Get the length of the smallest string.
     uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen());

     BitStringBuffer bsb(actLen);

     for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
     {
         uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

         uint64_t dVal = getFieldRight(pos, len);
         uint64_t sVal = i_bs.getFieldRight(pos, len);

         bsb.setFieldRight(pos, len, dVal | sVal);
     }

     return bsb;
 }

 //------------------------------------------------------------------------------

 BitStringBuffer BitString::operator>>(uint64_t i_shift) const
 {
     BitStringBuffer bsb(getBitLen()); // default all zeros

     if (i_shift < getBitLen())
     {
         // bso overlays bsb, containing the shifted offset.
         BitString bso(bsb.getBitLen() - i_shift, bsb.getBufAddr(), i_shift);

         // Copy this into bso.
         bso.setString(*this);
     }

     return bsb;
 }

 //------------------------------------------------------------------------------

 BitStringBuffer BitString::operator<<(uint64_t i_shift) const
 {
     BitStringBuffer bsb(getBitLen()); // default all zeros

     if (i_shift < getBitLen())
     {
         // bso overlays *this, containing the shifted offset.
         BitString bso(this->getBitLen() - i_shift, this->getBufAddr(), i_shift);

         // Copy bso into bsb.
         bsb.setString(bso);
     }

     return bsb;
 }

 //------------------------------------------------------------------------------

 uint8_t* BitString::getRelativePosition(uint64_t& o_relPos,
                                         uint64_t i_absPos) const
 {
     HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address
     HEI_ASSERT(i_absPos < getBitLen());  // must be a valid position

     o_relPos = (i_absPos + iv_offset) % UINT8_BIT_LEN;

     return (iv_bufAddr + ((i_absPos + iv_offset) / UINT8_BIT_LEN));
 }

 // ##############################################################################
 //                           BitStringBuffer class
 // ##############################################################################

 BitStringBuffer::BitStringBuffer(uint64_t i_bitLen) :
     BitString(i_bitLen, nullptr)
 {
     initBuffer();
 }

 //------------------------------------------------------------------------------

 BitStringBuffer::~BitStringBuffer()
 {
     delete[] getBufAddr();
 }

 //------------------------------------------------------------------------------

 BitStringBuffer::BitStringBuffer(const BitString& i_bs) :
     BitString(i_bs.getBitLen(), nullptr)
 {
     initBuffer();
     if (!i_bs.isZero())
     {
         setString(i_bs);
     }
 }

 //------------------------------------------------------------------------------

 BitStringBuffer::BitStringBuffer(const BitStringBuffer& i_bsb) :
     BitString(i_bsb.getBitLen(), nullptr)
 {
     initBuffer();
     if (!i_bsb.isZero())
     {
         setString(i_bsb);
     }
 }

 //------------------------------------------------------------------------------

 BitStringBuffer& BitStringBuffer::operator=(const BitString& i_bs)
 {
     // The initBuffer() function will deallocate the buffer as well, however we
     // also need to deallocate the buffer here before we set the length.
     delete[] getBufAddr();
     setBufAddr(nullptr);

     setBitLen(i_bs.getBitLen());
     initBuffer();
     if (!i_bs.isZero())
     {
         setString(i_bs);
     }

     return *this;
 }

 //------------------------------------------------------------------------------

 BitStringBuffer& BitStringBuffer::operator=(const BitStringBuffer& i_bsb)
 {
     if (this != &i_bsb) // Check for assignment to self
     {
         // The initBuffer() function will deallocate the buffer as well, however
         // we also need to deallocate the buffer here before we set the length.
         delete[] getBufAddr();
         setBufAddr(nullptr);

         setBitLen(i_bsb.getBitLen());
         initBuffer();
         if (!i_bsb.isZero())
         {
             setString(i_bsb);
         }
     }

     return *this;
 }

 //------------------------------------------------------------------------------

 void BitStringBuffer::initBuffer()
 {
     // Deallocate the current buffer.
     delete[] getBufAddr();

     // create new buffer, initialized to 0's
     setBufAddr(new uint8_t[getMinBytes(getBitLen())]());
 }

 } // end namespace libhei
	/** @file hei_bit_string.cpp
	* @brief BitString and BitStringBuffer class definitions
	*/

	#include <util/hei_bit_string.hpp>
	#include <util/hei_includes.hpp>

	#include <algorithm>

	namespace libhei
	{

	// ##############################################################################
	// BitString class
	// ##############################################################################

	// number of bits in a uint64_t
	const uint64_t BitString::UINT64_BIT_LEN = sizeof(uint64_t) * 8;
	// number of bits in a uint8_t
	const uint64_t BitString::UINT8_BIT_LEN = sizeof(uint8_t) * 8;

	//------------------------------------------------------------------------------

	uint64_t BitString::getFieldRight(uint64_t i_pos, uint64_t i_len) const
	{
	HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address
	HEI_ASSERT(0 < i_len); // must have at least one bit
	HEI_ASSERT(i_len <= UINT64_BIT_LEN); // i_len length must be valid
	HEI_ASSERT(i_pos + i_len <= getBitLen()); // field must be within range

	// Get the relative address of this byte and the relative starting position
	// within the byte.
	uint64_t relPos = 0;
	uint8_t* relAddr = getRelativePosition(relPos, i_pos);

	// Get the length of the target bit field within this byte and the length of
	// the bit field for any remaining bits.
	uint64_t bf_len = i_len;
	uint64_t remain_len = 0;
	if (UINT8_BIT_LEN < relPos + i_len)
	{
	// The target bit field crosses a byte boundary. So truncate the bit
	// length for this byte and update the remaining length.
	bf_len = UINT8_BIT_LEN - relPos;
	remain_len = i_len - bf_len;
	}

	// Get the target bit field within this byte (right justified).
	uint8_t bf = *relAddr;
	bf <<= relPos; // Mask off uneeded bits on the left side.
	bf >>= UINT8_BIT_LEN - bf_len; // Right justify the value.

	// Check for any remaining bits after this target byte.
	if (0 != remain_len)
	{
	// Recursively call this function on the remaining bits and push them
	// into the right side of the return value.
	uint64_t val = static_cast<uint64_t>(bf) << remain_len;
	return val \| getFieldRight(i_pos + bf_len, remain_len);
	}

	// Nothing more to do. Simply return this bit field.
	return bf;
	}

	//------------------------------------------------------------------------------

	void BitString::setFieldLeft(uint64_t i_pos, uint64_t i_len, uint64_t i_val)
	{
	HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address
	HEI_ASSERT(0 < i_len); // must have at least one bit
	HEI_ASSERT(i_len <= UINT64_BIT_LEN); // i_len length must be valid
	HEI_ASSERT(i_pos + i_len <= getBitLen()); // field must be within range

	// Get the relative address of this byte and the relative starting position
	// within the byte.
	uint64_t relPos = 0;
	uint8_t* relAddr = getRelativePosition(relPos, i_pos);

	// Get the length of the target bit field within this byte and the length of
	// the bit field for any remaining bits.
	uint64_t bf_len = i_len;
	uint64_t remain_len = 0;
	if (UINT8_BIT_LEN < relPos + i_len)
	{
	// The target bit field crosses a byte boundary. So truncate the bit
	// length for this byte and update the remaining length.
	bf_len = UINT8_BIT_LEN - relPos;
	remain_len = i_len - bf_len;
	}

	// It is possible there are bits in this byte on either side of the target
	// bit field that must be preserved. Get the length of each of those bit
	// fields.
	uint64_t bf_l_len = relPos;
	uint64_t bf_r_len = UINT8_BIT_LEN - (bf_l_len + bf_len);

	// Get the target bit field from the left justified inputed value.
	uint8_t bf = (i_val >> (UINT64_BIT_LEN - bf_len)) << bf_r_len;

	// Get the bit fields on either side of the target bit field.
	uint64_t bf_l_shift = UINT8_BIT_LEN - bf_l_len;
	uint64_t bf_r_shift = UINT8_BIT_LEN - bf_r_len;

	uint8_t bf_l = *relAddr;
	bf_l >>= bf_l_shift;
	bf_l <<= bf_l_shift;

	uint8_t bf_r = *relAddr;
	bf_r <<= bf_r_shift;
	bf_r >>= bf_r_shift;

	// Combine all three parts of the byte and write it out to memory.
	*relAddr = bf_l \| bf \| bf_r;

	// Check for any remaining bits after this target byte.
	if (0 != remain_len)
	{
	// Recursively call this function on the remaining bits.
	setFieldLeft(i_pos + bf_len, remain_len, i_val << bf_len);
	}
	}

	//------------------------------------------------------------------------------

	void BitString::setPattern(uint64_t i_sPos, uint64_t i_sLen, uint64_t i_pattern,
	uint64_t i_pLen)
	{
	HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address
	HEI_ASSERT(0 < i_sLen); // must have at least one bit
	HEI_ASSERT(i_sPos + i_sLen <= getBitLen()); // field must be within range
	HEI_ASSERT(0 < i_pLen); // must have at least one bit
	HEI_ASSERT(i_pLen <= UINT64_BIT_LEN); // i_pLen length must be valid

	// Get a bit string for the pattern subset (right justified).
	// Note that we cannot use a BitStringBuffer here because this function
	// could be used in the constructor of BitStringBuffer, which could causes
	// an infinite loop.
	uint8_t a[sizeof(i_pattern)] = {};
	BitString bs{sizeof(i_pattern) * 8, a};
	bs.setFieldRight(0, i_pLen, i_pattern);

	// Iterate the range in chunks the size of i_pLen.
	uint64_t endPos = i_sPos + i_sLen;
	for (uint64_t pos = i_sPos; pos < endPos; pos += i_pLen)
	{
	// The true chunk size is either i_pLen or the leftovers at the end.
	uint64_t len = std::min(i_pLen, endPos - pos);

	// Get this chunk's pattern value, truncate (right justified) if needed.
	uint64_t pattern = bs.getFieldRight(0, len);

	// Set the pattern in this string.
	setFieldRight(pos, len, pattern);
	}
	}

	//------------------------------------------------------------------------------

	void BitString::setString(const BitString& i_sStr, uint64_t i_sPos,
	uint64_t i_sLen, uint64_t i_dPos)
	{
	// Ensure the source parameters are valid.
	HEI_ASSERT(nullptr != i_sStr.getBufAddr());
	HEI_ASSERT(0 < i_sLen); // at least one bit to copy
	HEI_ASSERT(i_sPos + i_sLen <= i_sStr.getBitLen());

	// Ensure the destination has at least one bit available to copy.
	HEI_ASSERT(nullptr != getBufAddr());
	HEI_ASSERT(i_dPos < getBitLen());

	// If the source length is greater than the destination length than the
	// extra source bits are ignored.
	uint64_t actLen = std::min(i_sLen, getBitLen() - i_dPos);

	// The bit strings may be in overlapping memory spaces. So we need to copy
	// the data in the correct direction to prevent overlapping.
	uint64_t sRelOffset = 0, dRelOffset = 0;
	uint8_t* sRelAddr = i_sStr.getRelativePosition(sRelOffset, i_sPos);
	uint8_t* dRelAddr = getRelativePosition(dRelOffset, i_dPos);

	// Copy the data.
	if ((dRelAddr == sRelAddr) && (dRelOffset == sRelOffset))
	{
	// Do nothing. The source and destination are the same.
	}
	else if ((dRelAddr < sRelAddr) \|\|
	((dRelAddr == sRelAddr) && (dRelOffset < sRelOffset)))
	{
	// Copy the data forward.
	for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

	uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len);
	setFieldRight(i_dPos + pos, len, value);
	}
	}
	else // Copy the data backwards.
	{
	// Get the first position of the last chunk (byte aligned).
	uint64_t lastPos = ((actLen - 1) / UINT64_BIT_LEN) * UINT64_BIT_LEN;

	// Start with the last chunk and work backwards.
	for (int32_t pos = lastPos; 0 <= pos; pos -= UINT64_BIT_LEN)
	{
	uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);
	uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len);
	setFieldRight(i_dPos + pos, len, value);
	}
	}
	}

	//------------------------------------------------------------------------------

	void BitString::maskString(const BitString& i_mask)
	{
	// Get the length of the smallest string.
	uint64_t actLen = std::min(getBitLen(), i_mask.getBitLen());

	for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

	uint64_t dVal = getFieldRight(pos, len);
	uint64_t sVal = i_mask.getFieldRight(pos, len);

	setFieldRight(pos, len, dVal & ~sVal);
	}
	}

	//------------------------------------------------------------------------------

	bool BitString::isEqual(const BitString& i_str) const
	{
	if (getBitLen() != i_str.getBitLen())
	return false; // size not equal

	for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

	if (getFieldRight(pos, len) != i_str.getFieldRight(pos, len))
	return false; // bit strings do not match
	}

	return true; // bit strings match
	}

	//------------------------------------------------------------------------------

	bool BitString::isZero() const
	{
	for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

	if (0 != getFieldRight(pos, len))
	return false; // something is non-zero
	}

	return true; // everything was zero
	}

	//------------------------------------------------------------------------------

	uint64_t BitString::getSetCount(uint64_t i_pos, uint64_t i_len) const
	{
	uint64_t endPos = i_pos + i_len;

	HEI_ASSERT(endPos <= getBitLen());

	uint64_t count = 0;

	for (uint64_t i = i_pos; i < endPos; i++)
	{
	if (isBitSet(i))
	count++;
	}

	return count;
	}

	//------------------------------------------------------------------------------

	bool BitString::operator<(const BitString& i_str) const
	{
	if (getBitLen() < i_str.getBitLen())
	{
	return true;
	}
	else if (getBitLen() == i_str.getBitLen())
	{
	// Can only compare the bit strings if the length is the same.
	for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

	auto l_str = getFieldRight(pos, len);
	auto r_str = i_str.getFieldRight(pos, len);

	if (l_str < r_str)
	{
	return true;
	}
	// The loop can only continue if the values are equal.
	else if (l_str > r_str)
	{
	return false;
	}
	}
	}

	return false;
	}

	//------------------------------------------------------------------------------

	BitStringBuffer BitString::operator~() const
	{
	BitStringBuffer bsb(getBitLen());

	for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN);

	uint64_t dVal = getFieldRight(pos, len);

	bsb.setFieldRight(pos, len, ~dVal);
	}

	return bsb;
	}

	//------------------------------------------------------------------------------

	BitStringBuffer BitString::operator&(const BitString& i_bs) const
	{
	// Get the length of the smallest string.
	uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen());

	BitStringBuffer bsb(actLen);

	for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

	uint64_t dVal = getFieldRight(pos, len);
	uint64_t sVal = i_bs.getFieldRight(pos, len);

	bsb.setFieldRight(pos, len, dVal & sVal);
	}

	return bsb;
	}

	//------------------------------------------------------------------------------

	BitStringBuffer BitString::operator\|(const BitString& i_bs) const
	{
	// Get the length of the smallest string.
	uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen());

	BitStringBuffer bsb(actLen);

	for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN)
	{
	uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN);

	uint64_t dVal = getFieldRight(pos, len);
	uint64_t sVal = i_bs.getFieldRight(pos, len);

	bsb.setFieldRight(pos, len, dVal \| sVal);
	}

	return bsb;
	}

	//------------------------------------------------------------------------------

	BitStringBuffer BitString::operator>>(uint64_t i_shift) const
	{
	BitStringBuffer bsb(getBitLen()); // default all zeros

	if (i_shift < getBitLen())
	{
	// bso overlays bsb, containing the shifted offset.
	BitString bso(bsb.getBitLen() - i_shift, bsb.getBufAddr(), i_shift);

	// Copy this into bso.
	bso.setString(*this);
	}

	return bsb;
	}

	//------------------------------------------------------------------------------

	BitStringBuffer BitString::operator<<(uint64_t i_shift) const
	{
	BitStringBuffer bsb(getBitLen()); // default all zeros

	if (i_shift < getBitLen())
	{
	// bso overlays *this, containing the shifted offset.
	BitString bso(this->getBitLen() - i_shift, this->getBufAddr(), i_shift);

	// Copy bso into bsb.
	bsb.setString(bso);
	}

	return bsb;
	}

	//------------------------------------------------------------------------------

	uint8_t* BitString::getRelativePosition(uint64_t& o_relPos,
	uint64_t i_absPos) const
	{
	HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address
	HEI_ASSERT(i_absPos < getBitLen()); // must be a valid position

	o_relPos = (i_absPos + iv_offset) % UINT8_BIT_LEN;

	return (iv_bufAddr + ((i_absPos + iv_offset) / UINT8_BIT_LEN));
	}

	// ##############################################################################
	// BitStringBuffer class
	// ##############################################################################

	BitStringBuffer::BitStringBuffer(uint64_t i_bitLen) :
	BitString(i_bitLen, nullptr)
	{
	initBuffer();
	}

	//------------------------------------------------------------------------------

	BitStringBuffer::~BitStringBuffer()
	{
	delete[] getBufAddr();
	}

	//------------------------------------------------------------------------------

	BitStringBuffer::BitStringBuffer(const BitString& i_bs) :
	BitString(i_bs.getBitLen(), nullptr)
	{
	initBuffer();
	if (!i_bs.isZero())
	{
	setString(i_bs);
	}
	}

	//------------------------------------------------------------------------------

	BitStringBuffer::BitStringBuffer(const BitStringBuffer& i_bsb) :
	BitString(i_bsb.getBitLen(), nullptr)
	{
	initBuffer();
	if (!i_bsb.isZero())
	{
	setString(i_bsb);
	}
	}

	//------------------------------------------------------------------------------

	BitStringBuffer& BitStringBuffer::operator=(const BitString& i_bs)
	{
	// The initBuffer() function will deallocate the buffer as well, however we
	// also need to deallocate the buffer here before we set the length.
	delete[] getBufAddr();
	setBufAddr(nullptr);

	setBitLen(i_bs.getBitLen());
	initBuffer();
	if (!i_bs.isZero())
	{
	setString(i_bs);
	}

	return *this;
	}

	//------------------------------------------------------------------------------

	BitStringBuffer& BitStringBuffer::operator=(const BitStringBuffer& i_bsb)
	{
	if (this != &i_bsb) // Check for assignment to self
	{
	// The initBuffer() function will deallocate the buffer as well, however
	// we also need to deallocate the buffer here before we set the length.
	delete[] getBufAddr();
	setBufAddr(nullptr);

	setBitLen(i_bsb.getBitLen());
	initBuffer();
	if (!i_bsb.isZero())
	{
	setString(i_bsb);
	}
	}

	return *this;
	}

	//------------------------------------------------------------------------------

	void BitStringBuffer::initBuffer()
	{
	// Deallocate the current buffer.
	delete[] getBufAddr();

	// create new buffer, initialized to 0's
	setBufAddr(new uint8_t[getMinBytes(getBitLen())]());
	}

	} // end namespace libhei