Define BitString and BitStringBuffer
BitString is a general purpose class providing the ability to manipulate
individual bits within an allocated section of contiguous memory. A
BitString does not allocate or maintain the memory that it manipulates.
BitStringBuffer is a BitString that allocates and maintains the memory
that it manipulates.
Signed-off-by: Ben Tyner <ben.tyner@ibm.com>
Change-Id: I64e691a169d571dc1fd435a30b666312854346ac
diff --git a/meson.build b/meson.build
index 7a569b6..1fcdd95 100644
--- a/meson.build
+++ b/meson.build
@@ -6,7 +6,7 @@
'cpp_std=c++11'
])
-incdir = [ include_directories('src') ]
+incdir = [include_directories('src')]
build_tests = get_option('tests')
diff --git a/src/util/hei_bit_string.cpp b/src/util/hei_bit_string.cpp
index bdc8694..2cbb3a1 100755
--- a/src/util/hei_bit_string.cpp
+++ b/src/util/hei_bit_string.cpp
@@ -1,7 +1,10 @@
+/** @file hei_bit_string.cpp
+ * @brief BitString and BitStringBuffer class definitions
+ */
-#include <prdfBitString.H>
+#include <util/hei_bit_string.hpp>
-#include <prdfAssert.h>
+#include <hei_user_defines.hpp>
#include <algorithm>
@@ -12,98 +15,126 @@
// BitString class
//##############################################################################
-const uint32_t BitString::CPU_WORD_BIT_LEN = sizeof(CPU_WORD) * 8;
-
-const CPU_WORD BitString::CPU_WORD_MASK = static_cast<CPU_WORD>(-1);
+// number of bits in a uint64_t
+constexpr uint32_t BitString::UINT64_BIT_LEN = sizeof(uint64_t) * 8;
+// number of bits in a uint8_t
+constexpr uint32_t BitString::UINT8_BIT_LEN = sizeof(uint8_t) * 8;
//------------------------------------------------------------------------------
-CPU_WORD BitString::getField( uint32_t i_pos, uint32_t i_len ) const
+uint64_t BitString::getFieldRight( uint32_t i_pos, uint32_t i_len ) const
{
- PRDF_ASSERT( nullptr != getBufAddr() ); // must to have a valid address
- PRDF_ASSERT( 0 < i_len ); // must have at least one bit
- PRDF_ASSERT( i_len <= CPU_WORD_BIT_LEN ); // i_len length must be valid
- PRDF_ASSERT( i_pos + i_len <= getBitLen() ); // field must be within range
+ 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
- // The returned value.
- CPU_WORD o_val = 0;
-
- // Get the relative address and position of the field.
+ // Get the relative address of this byte and the relative starting position
+ // within the byte.
uint32_t relPos = 0;
- CPU_WORD * relAddr = getRelativePosition( relPos, i_pos );
+ uint8_t * relAddr = getRelativePosition( relPos, i_pos );
- // The return value may cross two CPU_WORD addresses. Get length of each
- // chunk, mask to clear the right-handed bits, and the shift value to make
- // each chunk left-justified.
- uint32_t len0 = i_len, len1 = 0;
- if ( CPU_WORD_BIT_LEN < relPos + i_len )
+ // Get the length of the target bit field within this byte and the length of
+ // the bit field for any remaining bits.
+ uint32_t bf_len = i_len;
+ uint32_t remain_len = 0;
+ if ( UINT8_BIT_LEN < relPos + i_len )
{
- len0 = CPU_WORD_BIT_LEN - relPos;
- len1 = i_len - len0;
+ // 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;
}
- CPU_WORD mask0 = CPU_WORD_MASK << (CPU_WORD_BIT_LEN - len0);
- CPU_WORD mask1 = CPU_WORD_MASK << (CPU_WORD_BIT_LEN - len1);
+ // 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.
- uint32_t shift0 = relPos;
- uint32_t shift1 = CPU_WORD_BIT_LEN - relPos;
-
- // Get first half of the value.
- o_val = (*relAddr << shift0) & mask0;
-
- // Get the second half of the value, if needed
- if ( CPU_WORD_BIT_LEN < relPos + i_len )
+ // Check for any remaining bits after this target byte.
+ if ( 0 != remain_len )
{
- ++relAddr;
- o_val |= (*relAddr & mask1) >> shift1;
+ // 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 );
}
- return o_val;
+ // Nothing more to do. Simply return this bit field.
+ return bf;
}
//------------------------------------------------------------------------------
-void BitString::setField( uint32_t i_pos, uint32_t i_len, CPU_WORD i_val )
+void BitString::setFieldLeft( uint32_t i_pos, uint32_t i_len, uint64_t i_val )
{
- PRDF_ASSERT( nullptr != getBufAddr() ); // must to have a valid address
- PRDF_ASSERT( 0 < i_len ); // must have at least one bit
- PRDF_ASSERT( i_len <= CPU_WORD_BIT_LEN ); // i_len length must be valid
- PRDF_ASSERT( i_pos + i_len <= getBitLen() ); // field must be within range
+ 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 and position of the field.
+ // Get the relative address of this byte and the relative starting position
+ // within the byte.
uint32_t relPos = 0;
- CPU_WORD * relAddr = getRelativePosition( relPos, i_pos );
+ uint8_t * relAddr = getRelativePosition( relPos, i_pos );
- // The value is left-justified. Ignore all other bits.
- CPU_WORD mask = CPU_WORD_MASK << (CPU_WORD_BIT_LEN - i_len);
- CPU_WORD val = i_val & mask;
-
- // Set first half of the value.
- *relAddr &= ~(mask >> relPos); // Clear field
- *relAddr |= (val >> relPos); // Set field
-
- // Get the second half of the value, if needed
- if ( CPU_WORD_BIT_LEN < relPos + i_len )
+ // Get the length of the target bit field within this byte and the length of
+ // the bit field for any remaining bits.
+ uint32_t bf_len = i_len;
+ uint32_t remain_len = 0;
+ if ( UINT8_BIT_LEN < relPos + i_len )
{
- relAddr++;
- *relAddr &= ~(mask << (CPU_WORD_BIT_LEN - relPos)); // Clear field
- *relAddr |= (val << (CPU_WORD_BIT_LEN - relPos)); // Set field
+ // 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.
+ uint32_t bf_l_len = relPos;
+ uint32_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.
+ uint32_t bf_l_shift = UINT8_BIT_LEN - bf_l_len;
+ uint32_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( uint32_t i_sPos, uint32_t i_sLen,
- CPU_WORD i_pattern, uint32_t i_pLen )
+ uint64_t i_pattern, uint32_t i_pLen )
{
- PRDF_ASSERT(nullptr != getBufAddr()); // must to have a valid address
- PRDF_ASSERT(0 < i_sLen); // must have at least one bit
- PRDF_ASSERT(i_sPos + i_sLen <= getBitLen()); // field must be within range
- PRDF_ASSERT(0 < i_pLen); // must have at least one bit
- PRDF_ASSERT(i_pLen <= CPU_WORD_BIT_LEN); // i_pLen length must be valid
+
+ 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).
- BitString bso ( i_pLen, &i_pattern, CPU_WORD_BIT_LEN - i_pLen );
+ // 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.
uint32_t endPos = i_sPos + i_sLen;
@@ -112,11 +143,11 @@
// The true chunk size is either i_pLen or the leftovers at the end.
uint32_t len = std::min( i_pLen, endPos - pos );
- // Get this chunk's pattern value, truncate (left justified) if needed.
- CPU_WORD pattern = bso.getField( 0, len );
+ // Get this chunk's pattern value, truncate (right justified) if needed.
+ uint64_t pattern = bs.getFieldRight( 0, len );
// Set the pattern in this string.
- setField( pos, len, pattern );
+ setFieldRight( pos, len, pattern );
}
}
@@ -126,13 +157,13 @@
uint32_t i_sLen, uint32_t i_dPos )
{
// Ensure the source parameters are valid.
- PRDF_ASSERT( nullptr != i_sStr.getBufAddr() );
- PRDF_ASSERT( 0 < i_sLen ); // at least one bit to copy
- PRDF_ASSERT( i_sPos + i_sLen <= i_sStr.getBitLen() );
+ 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.
- PRDF_ASSERT( nullptr != getBufAddr() );
- PRDF_ASSERT( i_dPos < getBitLen() );
+ 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.
@@ -141,8 +172,8 @@
// The bit strings may be in overlapping memory spaces. So we need to copy
// the data in the correct direction to prevent overlapping.
uint32_t sRelOffset = 0, dRelOffset = 0;
- CPU_WORD * sRelAddr = i_sStr.getRelativePosition( sRelOffset, i_sPos );
- CPU_WORD * dRelAddr = getRelativePosition( dRelOffset, i_dPos );
+ uint8_t * sRelAddr = i_sStr.getRelativePosition( sRelOffset, i_sPos );
+ uint8_t * dRelAddr = getRelativePosition( dRelOffset, i_dPos );
// Copy the data.
if ( (dRelAddr == sRelAddr) && (dRelOffset == sRelOffset) )
@@ -153,26 +184,25 @@
((dRelAddr == sRelAddr) && (dRelOffset < sRelOffset)) )
{
// Copy the data forward.
- for ( uint32_t pos = 0; pos < actLen; pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( actLen - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( actLen - pos, UINT64_BIT_LEN );
- CPU_WORD value = i_sStr.getField( i_sPos + pos, len );
- setField( i_dPos + pos, len, value );
+ 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 (CPU_WORD aligned).
- uint32_t lastPos = ((actLen-1) / CPU_WORD_BIT_LEN) * CPU_WORD_BIT_LEN;
+ // Get the first position of the last chunk (byte aligned).
+ uint32_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 -= CPU_WORD_BIT_LEN )
+ for ( int32_t pos = lastPos; 0 <= pos; pos -= UINT64_BIT_LEN )
{
- uint32_t len = std::min( actLen - pos, CPU_WORD_BIT_LEN );
-
- CPU_WORD value = i_sStr.getField( i_sPos + pos, len );
- setField( i_dPos + pos, len, value );
+ uint32_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 );
}
}
}
@@ -184,14 +214,14 @@
// Get the length of the smallest string.
uint32_t actLen = std::min( getBitLen(), i_mask.getBitLen() );
- for ( uint32_t pos = 0; pos < actLen; pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( actLen - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( actLen - pos, UINT64_BIT_LEN );
- CPU_WORD dVal = getField( pos, len );
- CPU_WORD sVal = i_mask.getField( pos, len );
+ uint64_t dVal = getFieldRight( pos, len );
+ uint64_t sVal = i_mask.getFieldRight( pos, len );
- setField( pos, len, dVal & ~sVal );
+ setFieldRight( pos, len, dVal & ~sVal );
}
}
@@ -202,11 +232,11 @@
if ( getBitLen() != i_str.getBitLen() )
return false; // size not equal
- for ( uint32_t pos = 0; pos < getBitLen(); pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( getBitLen() - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( getBitLen() - pos, UINT64_BIT_LEN );
- if ( getField(pos, len) != i_str.getField(pos, len) )
+ if ( getFieldRight(pos, len) != i_str.getFieldRight(pos, len) )
return false; // bit strings do not match
}
@@ -217,11 +247,11 @@
bool BitString::isZero() const
{
- for ( uint32_t pos = 0; pos < getBitLen(); pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( getBitLen() - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( getBitLen() - pos, UINT64_BIT_LEN );
- if ( 0 != getField(pos, len) )
+ if ( 0 != getFieldRight(pos, len) )
return false; // something is non-zero
}
@@ -234,7 +264,7 @@
{
uint32_t endPos = i_pos + i_len;
- PRDF_ASSERT( endPos <= getBitLen() );
+ HEI_ASSERT( endPos <= getBitLen() );
uint32_t count = 0;
@@ -252,13 +282,13 @@
{
BitStringBuffer bsb( getBitLen() );
- for ( uint32_t pos = 0; pos < getBitLen(); pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( getBitLen() - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( getBitLen() - pos, UINT64_BIT_LEN );
- CPU_WORD dVal = getField( pos, len );
+ uint64_t dVal = getFieldRight( pos, len );
- bsb.setField( pos, len, ~dVal );
+ bsb.setFieldRight( pos, len, ~dVal );
}
return bsb;
@@ -273,14 +303,14 @@
BitStringBuffer bsb( actLen );
- for ( uint32_t pos = 0; pos < actLen; pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( actLen - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( actLen - pos, UINT64_BIT_LEN );
- CPU_WORD dVal = getField( pos, len );
- CPU_WORD sVal = i_bs.getField( pos, len );
+ uint64_t dVal = getFieldRight( pos, len );
+ uint64_t sVal = i_bs.getFieldRight( pos, len );
- bsb.setField( pos, len, dVal & sVal );
+ bsb.setFieldRight( pos, len, dVal & sVal );
}
return bsb;
@@ -295,14 +325,14 @@
BitStringBuffer bsb( actLen );
- for ( uint32_t pos = 0; pos < actLen; pos += CPU_WORD_BIT_LEN )
+ for ( uint32_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN )
{
- uint32_t len = std::min( actLen - pos, CPU_WORD_BIT_LEN );
+ uint32_t len = std::min( actLen - pos, UINT64_BIT_LEN );
- CPU_WORD dVal = getField( pos, len );
- CPU_WORD sVal = i_bs.getField( pos, len );
+ uint64_t dVal = getFieldRight( pos, len );
+ uint64_t sVal = i_bs.getFieldRight( pos, len );
- bsb.setField( pos, len, dVal | sVal );
+ bsb.setFieldRight( pos, len, dVal | sVal );
}
return bsb;
@@ -347,15 +377,15 @@
//------------------------------------------------------------------------------
-CPU_WORD * BitString::getRelativePosition( uint32_t & o_relPos,
+uint8_t * BitString::getRelativePosition( uint32_t & o_relPos,
uint32_t i_absPos ) const
{
- PRDF_ASSERT( nullptr != getBufAddr() ); // must to have a valid address
- PRDF_ASSERT( i_absPos < getBitLen() ); // must be a valid position
+ 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) % CPU_WORD_BIT_LEN;
+ o_relPos = (i_absPos + iv_offset) % UINT8_BIT_LEN;
- return iv_bufAddr + ((i_absPos + iv_offset) / CPU_WORD_BIT_LEN);
+ return ((uint8_t *)iv_bufAddr + ((i_absPos + iv_offset) / UINT8_BIT_LEN));
}
//##############################################################################
@@ -372,7 +402,7 @@
BitStringBuffer::~BitStringBuffer()
{
- delete [] getBufAddr();
+ delete [] (uint8_t *)getBufAddr();
}
//------------------------------------------------------------------------------
@@ -399,7 +429,7 @@
{
// 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();
+ delete [] (uint8_t *)getBufAddr();
setBufAddr( nullptr );
setBitLen( i_bs.getBitLen() );
@@ -417,7 +447,7 @@
{
// 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();
+ delete [] (uint8_t *)getBufAddr();
setBufAddr( nullptr );
setBitLen( i_bsb.getBitLen() );
@@ -433,14 +463,10 @@
void BitStringBuffer::initBuffer()
{
// Deallocate the current buffer.
- delete [] getBufAddr();
+ delete [] (uint8_t *)getBufAddr();
- // Allocate the new buffer.
- setBufAddr( new CPU_WORD[ getNumCpuWords(getBitLen()) ] );
-
- // Clear the new buffer.
- if ( !isZero() ) clearAll();
+ // create new buffer, initialized to 0's
+ setBufAddr( new uint8_t[ getMinBytes(getBitLen()) ]() );
}
} // end namespace libhei
-
diff --git a/src/util/hei_bit_string.hpp b/src/util/hei_bit_string.hpp
index cc1c073..889dc41 100755
--- a/src/util/hei_bit_string.hpp
+++ b/src/util/hei_bit_string.hpp
@@ -1,16 +1,12 @@
#pragma once
-#include <prdf_types.h>
+#include <stdint.h>
namespace libhei
{
class BitStringBuffer;
-/** This type is used to take advantage of the most efficient memory reference
- * size for a specific CPU architecture. */
-typedef uint32_t CPU_WORD;
-
//##############################################################################
// BitString class
//##############################################################################
@@ -27,33 +23,45 @@
* The length of a BitString is only limited by the amount of memory that
* contains the data buffer.
*
- * The CPU_WORD type is used internally to reference memory and as the interface
- * type for the field. Ensure that any buffer allocated for a BitString is
- * CPU_WORD aligned so that the BitString does not accidentally access memory
- * beyond availability. For example, say we have a buffer allocated for 6 byte
- * (48 bits) and those 6 bytes are allocated at the very end of accessible
- * memory. When the BitString tries to access the second CPU_WORD, which
- * contains the last 2 bytes of the buffer, an expection will be thrown because
- * the BitString always access an entire CPU_WORD (4 bytes) at a time and the
- * last two bytes are not accessible. Utilize the static function
- * getNumCpuWords() to get the minimum number of CPU_WORDs required to allocate
- * sufficient space in the buffer. For example, getNumCpuWords(48) returns 2.
+ * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
*
- * The bit positions are ordered 0 to n (left to right), where n is the bit
- * length minus one. By default, position 0 will be the first bit of the
- * buffer's start address. The optional constructor allows users to input an
- * offset anywhere within the buffer, which is then used as position 0. This is
- * useful when the data within the buffer is a right-justified.
+ * - The bit positions are ordered 0 to n (left to right), where n is the bit
+ * length minus one.
+ * - The data stored in memory is assumed to be in big-endian byte format.
+ *
+ * So, for example:
+ *
+ * uint8_t a[2]; // 16 bits of memory
+ * BitString bs { 16, a }; // init BitString for a
+ * bs.setFieldRight( 0, 16, 0x1122 ); // set all 16 bits to 0x1122
+ *
+ * Results in:
+ *
+ * a[0] == bs.getFieldRight(0, 8) (i.e. 0x11)
+ * a[1] == bs.getFieldRight(8, 8) (i.e. 0x22)
+ *
+ * It is very important you do NOT do this:
+ *
+ * uint16_t x = 0x1122; // 16 bits of memory
+ * BitString bs { 16, &x }; // init BitString for x
+ *
+ * The results are undefined, or at least not portable. For example:
+ *
+ * Big-endian:
+ * x is stored in memory as |0x11|0x22|.
+ * Therefore, bs.getFieldRight(0, 8) returns 0x11.
+ *
+ * Little-endian:
+ * x is stored in memory as |0x22|0x11|.
+ * Therefore, bs.getFieldRight(0, 8) returns 0x22.
+ *
*/
class BitString
{
- public: // constants
+ private: // constants
- /** Bit length of a CPU_WORD */
- static const uint32_t CPU_WORD_BIT_LEN;
-
- /** A CPU_WORD with all of the bits set to 1 */
- static const CPU_WORD CPU_WORD_MASK;
+ static const uint32_t UINT64_BIT_LEN;
+ static const uint32_t UINT8_BIT_LEN;
public: // functions
@@ -61,16 +69,14 @@
* @brief Constructor
* @param i_bitLen The number of bits in the bit string.
* @param i_bufAddr The starting address of the memory buffer.
- * @param i_offset Optional input to indicate the actual starting position
- * of the bit string within the memory buffer.
- * @post It is possible that i_bitLen + i_offset may not be CPU_WORD
- * aligned, however, the memory space allocated for i_bufAddr must be
- * CPU_WORD aligned to avoid functions in this class accessing memory
- * outside the available memory space. Use getNumCpuWords() to
- * calulate the number of CPU_WORDs needed to allocate sufficient
- * memory space.
+ * @param i_offset By default, position 0 will be the first bit of the
+ * buffer's start address. However, this parameter can be
+ * used to indicate that position 0 actually starts
+ * somewhere in the middle of the buffer.
+ * @pre Use getMinBytes() to calulate the minimum number of bytes needed
+ * to allocate sufficient memory space for this bit string.
*/
- BitString( uint32_t i_bitLen, CPU_WORD * i_bufAddr,
+ BitString( uint32_t i_bitLen, void * i_bufAddr,
uint32_t i_offset = 0 ) :
iv_bitLen(i_bitLen), iv_bufAddr(i_bufAddr), iv_offset(i_offset)
{}
@@ -83,18 +89,18 @@
/** @return The address of the bit string buffer. Note that this may
* return nullptr. */
- CPU_WORD * getBufAddr() const { return iv_bufAddr; }
+ void * getBufAddr() const { return iv_bufAddr; }
/**
* @param i_bitLen The number of bits for a bit string.
* @param i_offset Optional starting position of the bit string within the
* memory buffer.
- * @return The minimum number of CPU_WORDs required to allocate sufficient
+ * @return The minimum number of bytes required to allocate sufficient
* memory space for a bit string.
*/
- static uint32_t getNumCpuWords( uint32_t i_bitLen, uint32_t i_offset = 0 )
+ static uint32_t getMinBytes( uint32_t i_bitLen, uint32_t i_offset = 0 )
{
- return (i_bitLen + i_offset + CPU_WORD_BIT_LEN-1) / CPU_WORD_BIT_LEN;
+ return (i_bitLen + i_offset + UINT8_BIT_LEN-1) / UINT8_BIT_LEN;
}
/**
@@ -105,10 +111,13 @@
* @return The value of the field range specified (left-justified).
* @pre nullptr != getBufAddr()
* @pre 0 < i_len
- * @pre i_len <= CPU_WORD_BIT_LEN
+ * @pre i_len <= UINT64_BIT_LEN
* @pre i_pos + i_len <= getBitLen()
*/
- CPU_WORD getField( uint32_t i_pos, uint32_t i_len ) const;
+ uint64_t getFieldLeft( uint32_t i_pos, uint32_t i_len ) const
+ {
+ return getFieldRight(i_pos, i_len) << (UINT64_BIT_LEN - i_len);
+ }
/**
* @brief Returns a right-justified value of the given length from the bit
@@ -118,13 +127,10 @@
* @return The value of the field range specified (right-justified).
* @pre nullptr != getBufAddr()
* @pre 0 < i_len
- * @pre i_len <= CPU_WORD_BIT_LEN
+ * @pre i_len <= UINT64_BIT_LEN
* @pre i_pos + i_len <= getBitLen()
*/
- CPU_WORD getFieldJustify( uint32_t i_pos, uint32_t i_len ) const
- {
- return getField(i_pos, i_len) >> (CPU_WORD_BIT_LEN - i_len);
- }
+ uint64_t getFieldRight( uint32_t i_pos, uint32_t i_len ) const;
/**
* @brief Sets a left-justified value of the given length into the bit
@@ -134,10 +140,10 @@
* @param i_val The left-justified value to set.
* @pre nullptr != getBufAddr()
* @pre 0 < i_len
- * @pre i_len <= CPU_WORD_BIT_LEN
+ * @pre i_len <= UINT64_BIT_LEN
* @pre i_pos + i_len <= getBitLen()
*/
- void setField( uint32_t i_pos, uint32_t i_len, CPU_WORD i_val );
+ void setFieldLeft( uint32_t i_pos, uint32_t i_len, uint64_t i_val );
/**
* @brief Sets a right-justified value of the given length into the bit
@@ -147,12 +153,12 @@
* @param i_val The right-justified value to set.
* @pre nullptr != getBufAddr()
* @pre 0 < i_len
- * @pre i_len <= CPU_WORD_BIT_LEN
+ * @pre i_len <= UINT64_BIT_LEN
* @pre i_pos + i_len <= getBitLen()
*/
- void setFieldJustify( uint32_t i_pos, uint32_t i_len, CPU_WORD i_val )
+ void setFieldRight( uint32_t i_pos, uint32_t i_len, uint64_t i_val )
{
- setField( i_pos, i_len, i_val << (CPU_WORD_BIT_LEN - i_len) );
+ setFieldLeft( i_pos, i_len, i_val << (UINT64_BIT_LEN - i_len) );
}
/**
@@ -160,24 +166,27 @@
* @return True if the bit at the given position is set(1), false otherwise.
* @pre i_pos < getBitLen().
*/
- bool isBitSet( uint32_t i_pos ) const { return 0 != getField(i_pos, 1); }
+ bool isBitSet( uint32_t i_pos ) const
+ {
+ return 0 != getFieldRight(i_pos, 1);
+ }
/**
* @brief Sets the target position to 1.
* @param i_pos The target position.
* @pre i_pos < getBitLen().
*/
- void setBit( uint32_t i_pos ) { setFieldJustify( i_pos, 1, 1 ); }
+ void setBit( uint32_t i_pos ) { setFieldRight( i_pos, 1, 1 ); }
/** @brief Sets the entire bit string to 1's. */
- void setAll() { setPattern(CPU_WORD_MASK); }
+ void setAll() { setPattern(UINT64_MAX); }
/**
* @brief Sets the target position to 0.
* @param i_pos The target position.
* @pre i_pos < getBitLen().
*/
- void clearBit( uint32_t i_pos ) { setFieldJustify( i_pos, 1, 0 ); }
+ void clearBit( uint32_t i_pos ) { setFieldRight( i_pos, 1, 0 ); }
/** @brief Sets the entire bit string to 0's. */
void clearAll() { setPattern(0); }
@@ -192,7 +201,7 @@
* @pre nullptr != getBufAddr()
* @pre 0 < i_sLen
* @pre i_sPos + i_sLen <= getBitLen()
- * @pre 0 < i_pLen <= CPU_WORD_BIT_LEN
+ * @pre 0 < i_pLen <= UINT64_BIT_LEN
* @post The pattern is repeated/truncated as needed.
*
* Examples: i_sPos(0), i_sLen(10), i_pattern(0xA), i_pLen(4)
@@ -204,7 +213,7 @@
* New String: 0000110000
*/
void setPattern( uint32_t i_sPos, uint32_t i_sLen,
- CPU_WORD i_pattern, uint32_t i_pLen );
+ uint64_t i_pattern, uint32_t i_pLen );
/**
* @brief Sets entire string based on the pattern and length provided.
@@ -214,22 +223,21 @@
* @post The entire string is filled with the pattern.
* @post The pattern is repeated/truncated as needed.
*/
- void setPattern( CPU_WORD i_pattern, uint32_t i_pLen )
+ void setPattern( uint64_t i_pattern, uint32_t i_pLen )
{
setPattern( 0, getBitLen(), i_pattern, i_pLen );
}
/**
- * @brief Sets entire string based on the pattern provided (length of
- * CPU_WORD).
- * @param i_pattern The pattern to set.
+ * @brief Sets entire string based on the pattern provided.
+ * @param i_pattern The pattern to set (right justified).
* @note See definition above for prerequisites.
* @post The entire string is filled with the pattern.
* @post The pattern is repeated/truncated as needed.
*/
- void setPattern( CPU_WORD i_pattern )
+ void setPattern( uint64_t i_pattern )
{
- setPattern( i_pattern, CPU_WORD_BIT_LEN );
+ setPattern( i_pattern, sizeof(i_pattern) * 8 );
}
/**
@@ -269,7 +277,7 @@
/**
* @brief Masks (clears) any bits set in this string that correspond to bits
* set in the given string (this & ~mask).
- * @param i_mask The mask string.
+ * @param i_mask The mask string (right justified).
* @note If the length of the given string is greater than the length of
* this string, then the extra bits are ignored.
* @note If the length of the given string is less than the length of this
@@ -319,6 +327,22 @@
/** @brief Left shift operator. */
BitStringBuffer operator<<( uint32_t i_shift ) const;
+ /**
+ * @brief Explicitly disables assignment from BitStringBuffer.
+ *
+ * Allowing this would be dangerous if the BitStringBuffer goes out of scope
+ * because the BitString would point to memory that is no longer in context.
+ */
+ BitString & operator=( const BitStringBuffer & i_bsb ) = delete;
+
+ /**
+ * @brief Explicitly disables copy from BitStringBuffer.
+ *
+ * Allowing this would be dangerous if the BitStringBuffer goes out of scope
+ * because the BitString would point to memory that is no longer in context.
+ */
+ BitString( const BitStringBuffer & i_bsb ) = delete;
+
protected: // functions
/**
@@ -326,21 +350,13 @@
* @pre Before calling this function, make sure you deallocate the old
* buffer to avoid memory leaks.
*/
- void setBufAddr( CPU_WORD * i_newBufAddr ) { iv_bufAddr = i_newBufAddr; }
+ void setBufAddr( void * i_newBufAddr ) { iv_bufAddr = i_newBufAddr; }
/** @param i_newBitLen The new bit length of this bit string buffer. */
void setBitLen( uint32_t i_newBitLen ) { iv_bitLen = i_newBitLen; }
private: // functions
- // Prevent the assignment operator and copy constructor from a
- // BitStringBuffer. While technically these could be done. We run into
- // serious problems like with the operator functions above that all return
- // a BitStringBuffer. If we allowed these, the BitString would end up
- // pointing to memory that is no longer in context.
- BitString & operator=( const BitStringBuffer & i_bsb );
- BitString( const BitStringBuffer & i_bsb );
-
/**
* @brief Given a bit position within the bit string, this function returns
* the address that contains the bit position and the bit position
@@ -351,13 +367,13 @@
* @pre nullptr != getBufAddr()
* @pre i_absPos < getBitLen()
*/
- CPU_WORD * getRelativePosition( uint32_t & o_relPos,
+ uint8_t * getRelativePosition( uint32_t & o_relPos,
uint32_t i_absPos ) const;
private: // instance variables
uint32_t iv_bitLen; ///< The bit length of this buffer.
- CPU_WORD * iv_bufAddr; ///< The beginning address of this buffer.
+ void * iv_bufAddr; ///< The beginning address of this buffer.
uint32_t iv_offset; ///< Start position offset
};
diff --git a/test/bit_string_test.cpp b/test/bit_string_test.cpp
new file mode 100644
index 0000000..8320d97
--- /dev/null
+++ b/test/bit_string_test.cpp
@@ -0,0 +1,169 @@
+#include <hei_user_defines.hpp>
+#include <util/hei_bit_string.hpp>
+#include "gtest/gtest.h"
+
+using namespace libhei;
+
+static constexpr uint32_t UINT8_BIT_LEN = (sizeof(uint8_t) * 8);
+static constexpr uint32_t UINT64_BIT_LEN = (sizeof(uint64_t) * 8);
+
+// setBit()
+// clearBit()
+// setAll()
+// clearAll()
+// isBitSet()
+// getSetCount()
+// isZero()
+TEST( BitStringTest, TestSet1 )
+{
+ BitStringBuffer bs(UINT64_BIT_LEN);
+ uint32_t i;
+
+ // set all bits in ascending order
+ for(i = 0; i < UINT64_BIT_LEN; i++)
+ {
+ // Make sure bit gets set and set count
+ // is increasing
+ bs.setBit(i);
+ ASSERT_TRUE(bs.isBitSet(i));
+ ASSERT_EQ(bs.getSetCount(), i+1);
+ }
+ // all bits should be set at this point
+ ASSERT_EQ(bs.getFieldRight(0,64), UINT64_MAX);
+ ASSERT_EQ(bs.getFieldLeft(0,64), UINT64_MAX);
+
+ // test clearAll(), setAll()
+ bs.clearAll();
+ ASSERT_TRUE(bs.isZero());
+ bs.setAll();
+ ASSERT_EQ(bs.getSetCount(), UINT64_BIT_LEN);
+
+ // clear all bits in descending order
+ for(i = UINT64_BIT_LEN; 0 != i; i--)
+ {
+ // make sure bit gets cleared and set count
+ // is decreasing
+ ASSERT_EQ(bs.getSetCount(), i);
+ bs.clearBit(i-1);
+ ASSERT_FALSE(bs.isBitSet(i-1));
+ }
+ // all bits should be clear at this point
+ ASSERT_EQ(bs.getSetCount(), 0u);
+ ASSERT_EQ(bs.getFieldRight(0,64), 0u);
+ ASSERT_EQ(bs.getFieldLeft(0,64), 0u);
+ ASSERT_TRUE(bs.isZero());
+}
+
+// setPattern()
+TEST( BitStringTest, TestSet2 )
+{
+ BitStringBuffer bs(UINT64_BIT_LEN);
+ uint64_t field = 0xaaaaaaaaaaaaaaaa;
+
+ bs.setPattern(field);
+ ASSERT_EQ(field, bs.getFieldRight(0, 64));
+ ASSERT_EQ(field, bs.getFieldLeft(0, 64));
+
+ bs.clearAll();
+ ASSERT_TRUE(bs.isZero());
+
+ bs.setPattern(0xaa, 8);
+ ASSERT_EQ(field, bs.getFieldRight(0, 64));
+ ASSERT_EQ(field, bs.getFieldLeft(0, 64));
+
+ bs.clearAll();
+ ASSERT_TRUE(bs.isZero());
+
+ bs.setPattern(0, 64, 0xaaaa, 16);
+ ASSERT_EQ(field, bs.getFieldRight(0, 64));
+ ASSERT_EQ(field, bs.getFieldLeft(0, 64));
+}
+
+// setString()
+TEST( BitStringTest, TestSet3 )
+{
+ BitStringBuffer bsb_dest(64);
+ BitStringBuffer bsb_src(64);
+
+ bsb_dest.clearAll();
+ ASSERT_TRUE(bsb_dest.isZero());
+
+ bsb_src.setAll();
+ ASSERT_EQ(64u, bsb_src.getSetCount());
+
+ bsb_dest.setString(bsb_src);
+ ASSERT_FALSE(bsb_dest.isZero());
+ ASSERT_EQ(bsb_dest.getFieldRight(0, 64), bsb_src.getFieldRight(0,64));
+ ASSERT_EQ(bsb_dest.getFieldLeft(0, 64), bsb_src.getFieldLeft(0,64));
+}
+
+// maskString()
+TEST( BitStringTest, TestSet4 )
+{
+ BitStringBuffer bsb(64);
+ bsb.setAll();
+ ASSERT_EQ(64u, bsb.getSetCount());
+
+ BitStringBuffer bsb_mask(64);
+ bsb_mask.setFieldRight(0, 64, 0xaaaaaaaaaaaaaaaa);
+
+ bsb.maskString(bsb_mask);
+ ASSERT_EQ(bsb.getFieldRight(0, 64), 0x5555555555555555u);
+}
+
+// setFieldRight()
+// setFieldLeft()
+// getFielRight()
+// getFieldLeft()
+TEST( BitStringTest, TestSet5 )
+{
+ uint64_t field = 0x1234567890abcdef;
+ BitStringBuffer bsb(64);
+
+ // set bitstring to low end of field
+ bsb.setFieldRight(0, 32, field);
+ ASSERT_EQ(field << 32, bsb.getFieldLeft(0,32));
+
+ // set bitstring to high end of field
+ bsb.setFieldLeft(0, 32, field);
+ ASSERT_EQ(field >> 32, bsb.getFieldRight(0,32));
+
+ // increasing offset
+ for(uint32_t i = 0; i < UINT64_BIT_LEN; i++)
+ {
+ // increasing length
+ for(uint32_t j = 1; j <= UINT64_BIT_LEN - i; j++)
+ {
+ bsb.clearAll();
+ bsb.setFieldRight(i, j, UINT64_MAX);
+
+ // verify
+ ASSERT_EQ(bsb.getFieldRight(i, j), \
+ UINT64_MAX >> (UINT64_BIT_LEN - j));
+
+ }
+ }
+ for(uint32_t i = 0; i < UINT64_BIT_LEN; i++)
+ {
+ // set 1 bit at offset i
+ bsb.clearAll();
+ bsb.setFieldRight(i, 1, 1);
+
+ // verify bit is set
+ ASSERT_EQ(bsb.getFieldRight(0, 64), (uint64_t)1 << \
+ (UINT64_BIT_LEN - i - 1));
+ }
+}
+
+// operator >>
+// operator <<
+TEST( BitStringTest, TestSet6 )
+{
+ uint64_t field = 0x1234567890abcdef;
+ BitStringBuffer bsb(64);
+
+ bsb.setFieldRight(0, 64, field);
+ ASSERT_EQ(field, bsb.getFieldRight(0, 64));
+ ASSERT_EQ(field >> 32, (bsb >> 32).getFieldRight(0, 64));
+ ASSERT_EQ(field << 32, (bsb << 32).getFieldRight(0, 64));
+}
diff --git a/test/meson.build b/test/meson.build
index 6cc59ae..a4e13ea 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -1,3 +1,18 @@
# build simulator
subdir('simulator')
+# supporting files that need compiled/linked
+test_src = ['../src/util/hei_bit_string.cpp']
+
+# build g-test framework unit tests
+gtests = ['bit_string_test']
+
+gtest = dependency('gtest', main : true, required : false, method : 'system')
+
+if gtest.found()
+ foreach g : gtests
+ test(g, executable(g.underscorify(), g + '.cpp', test_src, \
+ dependencies : gtest, \
+ include_directories : incdir))
+ endforeach
+endif