Expert: Zlatko - 12/16/2011

Question
QUESTION: Hi,
I was wondering if there is such thing as a dynamic bit-field or any other way to implement it?
To illuminate the question how can i create a bit-field where the size of the members is provided at run-time and added to the developing struct or any other data type? Any method possible? THANKS IN ADVANCE!!

ANSWER: Hello Heni

Yes of course it is possible to implement it. It would be built upon the tools I described in this answer:
http://en.allexperts.com/q/C-1587/2011/11/c-storage-minimal-space-1.htm

I did not get any follow up questions from you about it. If you understood my answer, then try to implement a function to get the N'th bit from a section of memory. If you show me some effort in that, then I'll know you're serious and we can we can get to work on your bit field question.

If you didn't understand my last answer, then please do ask questions about it. We have to build the foundation, before we can go on to the higher level functions.

Best regards
Zlatko


---------- FOLLOW-UP ----------

QUESTION: Hi,
I do understand your answer. The point is that what could happen in the following problem.
-The elements which i previously said were 7bits each, were infact, let's say, 5, 6, 7, 9 bits long(they were different). With your method i could encode it, but how could i possibly decode it if i don't know which element is what long? THANK IN ADVANCE AGAIN!!

Answer
Hello Heni

Well thanks for being patient, I have had a busy week.

To answer your question, you would need some method of storing the starting and ending position of each field. For example, if a field starts at bit 10 and ends at bit 15 (6 bits), then you would need to store that somewhere. In my scheme below, I'm using a vector of pairs of integers. The C++ standard template library provides both.

I initialize the bit field object with starting and ending positions for each field, but then I access the field by its field number. Have a look at the program below, and ask questions about anything you don't understand. I've tested it only a little.


#include <vector>
#include <utility>
#include <string>
#include <iostream>

class BitFields
{
public:
   
   /*
   The FieldDefns hold the starting and ending bit number
   of each field.
   */
   typedef std::pair<int, int> FieldDefn;
   typedef std::vector< FieldDefn > FieldDefnList;

   BitFields(FieldDefnList& fieldDefinitions);
   ~BitFields();

   /*
   We will assume that each bit field fits into an
   integer.
   */
   int getField(int fieldNum) const;
   void setField(int fieldNum, int value);

   bool getNthBit(int N) const;
   void setNthBit(int N, bool value);

private:
   /*
   We will forbid copying of the bit field unless you want to implement it
   If you attempt to copy, the compiler will give you an error
   */
   BitFields(const BitFields&);
   BitFields& operator=(const BitFields&);

private:
   // This is the private data.
   FieldDefnList mFields;
   char* mMemory;
};

BitFields::BitFields(FieldDefnList& fieldDefinitions)
{
   // copy the field definitions
   mFields = fieldDefinitions;

   /* go through each field definition, checking that
   the end is past the start, and finding the farthest bit
   swap field definitions where the starting bit is after the ending bit
   */
   int farthestBit = 0;
   for(unsigned int ix = 0; ix < mFields.size(); ++ix)
   {
       FieldDefn& p = mFields[ix];

       // We will be tolerant of some sloppy input from the user
       if (p.first > p.second)
       {
         int tmp = p.first;
         p.first = p.second;
         p.second = tmp;
       }

       /*
       Because we are assuming that each bit field fits into an integer, we
       must validate the user's input against that assumption.
       */
       if (p.second - p.first + 1 > sizeof(int)*8)
       {
         throw std::string("bad input, bit field too large");
       }
       farthestBit = std::max(p.second, farthestBit);
   }

   // allocate memory
   ++farthestBit;
   int byteCount = farthestBit / 8;
   if (farthestBit % 8 != 0) ++byteCount;
   mMemory = new char[byteCount];
}

BitFields::~BitFields()
{
   delete mMemory;
}

/* This method will obtain the bits of bit field numbered by bf
and return the bits of the bit field in the result
*/
int BitFields::getField(int bf) const
{
   int result = 0;

   // first get the bounds of the bit field
   FieldDefn fd = mFields[bf];
   int start = fd.first;
   int end = fd.second;

   // then get the individual bits and pack them into the result
   while(start <= end)
   {
       int bit = getNthBit(start);
       // shift to the left by 1 to make room in the result for the new bit
       result <<= 1;
       // put the bit in
       result |= bit;

       // advance to the next bit
       ++start;
   }

   return result;
}

/* This method will set the bits of bit field numbered by bf
to the bits int value
*/
void BitFields::setField(int bf, int value)
{
   // first get the bounds of the bit field
   FieldDefn fd = mFields[bf];
   int start = fd.first;
   int end = fd.second;

   while (end >= start)
   {
       /*
       We define the last bit in the bit field to be the least significant bit
       in the value
       */
       setNthBit(end, value & 1);
       // shift value to the right by one to get access to the next bit
       value >>= 1;
       --end;
   }
}

bool BitFields::getNthBit(int N) const
{
   /*
   from my answer at
   http://en.allexperts.com/q/C-1587/2011/11/c-storage-minimal-space-1.htm

   N/8 gives you the byte number in your memory
   N%8 gives you the bit number
   We take the binary value 10000000 and shift it to the right by the bit number,
   so if we are interested in the second bit, then 10000000 becomes 01000000
   and if we are interested in the third bit, it becomes 00100000
   That is the mask.

   Then we bitwise-AND the shifted value against the byte
   For example
   Byte: 10101111
   Mask: 00100000
   AND : 00100000

   If the result is 0, the the N'th bit was 0,
   if the result was not 0, then the N'th bit was 1
   */
   return (mMemory[ N/8 ] &  (0x80 >> (N % 8)) ) != 0;
}

void BitFields::setNthBit(int N, bool value)
{
   char mask = 0x80 >> ( N % 8);

   char& byte = mMemory [ N/8 ];
   if (value)
   {
       // set the bit
       byte |= mask;
   }
   else
   {
       // clear the bit
       byte &= ~mask;
   }
}

int main(void)
{
   /* Lets define the bit fields.
   As you say in your question
   "infact, let's say, 5, 6, 7, 9 bits long(they were different)"
   */
   BitFields::FieldDefnList fieldsDefns;
   fieldsDefns.push_back( BitFields::FieldDefn(0, 4)); // 5 bits
   fieldsDefns.push_back( BitFields::FieldDefn(5, 10)); // 6 bits
   fieldsDefns.push_back( BitFields::FieldDefn(11, 17)); // 7 bits
   fieldsDefns.push_back( BitFields::FieldDefn(18, 26)); // 9 bits
   fieldsDefns.push_back( BitFields::FieldDefn(27, 27)); // 1 bit
   fieldsDefns.push_back( BitFields::FieldDefn(28, 28)); // 1 bit

   // set fields
   BitFields bf(fieldsDefns);
   bf.setField(0, 22); // set field 0 to     10110
   bf.setField(1, 33); // set field 1 to    100001
   bf.setField(2, 87); // set field 2 to   1010111
   bf.setField(3, 341);// set field 3 to 101010101
   bf.setField(4, 1);
   bf.setField(5, 0);
   
   // test by reading them back
   for(unsigned int ix = 0; ix < fieldsDefns.size(); ++ix)
   {
       int value = bf.getField(ix);
       std::cout << "Field " << ix << " has " << value << std::endl;
   }
}