Expert: Ralph McArdell - 3/27/2006

Question
consider a frame of 720 words
each word is of 10 bits

how can i fill up my frame of 720 words with numbers starting from 0 to 720.

if we store this frame in a file then size taken by this frame should not be more than 900 bytes.

note:-each number should be represented in 10 bit form
will BitArray or BitFields will be helpful if yes then how please explain ur answers with some sample code


Answer
In this case, no I do not think std::bitarray will be of much use as it cannot output the data in the format you require.

In fact at first look I think the best thing to do is to write a class that wraps a collection of 900 byte values (unsigned char) and provides functions to set and get 10 bit values (passed as 16 bit integer types if your implementation supports them - e.g. as unsigned short values) using the 10 bit index (0 .. 719).

Note that if you have 720 10 bit numbers and they are indexed from 0 then the highest index is 719 not 720, so if you set each value to the number of its index you can fill them with values 0 to 719, not 0 to 720, as your question claims. If you require 0 to 720 (i.e. 721 10 bit values) then you will need 902 bytes to store them.

Assuming you require 720 10 bit values stored as 900 bytes then you wish to be able to do something like the following:
      
       int main()
       {
       // create a frame object
              Frame frame;

       // Set 10 bit values from 10-bit value index values
               for ( int i = 0; i < Frame::FrameSize; ++i )
               {
                       frame.SetAt( i, i );
               }

       // Get 10-bit values from 10 bit value index values
               for ( int i = 0; i < Frame::FrameSize; ++i )
               {
                       std::cout << "frame[" << i << "] = "
                                 << frame.GetAt( i ) << '\n';
               }

       // Write and read a frame to and from files:
               std::ofstream outFile("newFrameFile");
               std::ifstream inFile("existingFrameFile");

               frame.Write( outFile );
               frame.Read( inFile );
       }

All code shown is for example usage only, so omits error checking etc., is formatted to pass through AllExperts and is best viewed using a mono-spaced font such as Courier.

The above shows the usage required. For the moment I have steered clear of using C++ operators and the like. This initially gives us a class that looks like this:

       class Frame
       {
       public:
                 Frame();

                 ValueType GetAt( SizeType idx );

                 void SetAt( SizeType idx, ValueType value );

                 void Write( std::ostream & out );

                 void Read( std::istream & in );

       };

SizeType and ValueType are integer types that represent the types used for the size of arrays and indexes and the like and the type used for transferring 10-bit types. These we can add to the class as type aliases (typedefs). In addition we require a collection of bytes, let's say a std::vector of byte type integers. These types can also be added as type aliases, and the Frame byte collection as a private member:

       #include <vector>

       class Frame
       {
       public:
                 typedef unsigned char             ByteType;
                 typedef std::vector<ByteType>
                                                   ByteCollectionType;
                 typedef ByteCollectionType::size_type
                                                   SizeType;
                 typedef unsigned short            ValueType;

                 Frame();

                 ValueType GetAt( SizeType idx );

                 void SetAt( SizeType idx, ValueType value );

                 void Write( std::ostream & out );

                 void Read( std::istream & in );
       private:
                 ByteCollectionType    iBytes;
       };

The implementation of the constructor is trivial we just set the size of the vector to be the number of bytes required to hold the number of 10 bit values in a frame:

       class Frame
       {
       public:

       // ...

                 static SizeType const      ValueBitSize = 10;
                 static SizeType const      ByteBitSize = 8;
                 static SizeType const      FrameSize = 720;
                 static SizeType const      FrameByteSize =
                                 (FrameSize*ValueBitSize)/ByteBitSize;

                 Frame()
                 : iBytes( FrameByteSize )
                 {
                 }
       // ...

       };

Note the above calculation is not perfect as it does not round up if FrameSize does not equate to a whole number of bytes.

The read and write operations are trivial to implement, but note that we will be storing the values as pure binary and not bytes that are text, so we need to open the files in binary mode. All this does is suppress translation to and from C/C++ end of lines ('\n') and operating system text file end of lines (e.g. "\r\n" on Microsoft operating systems such as MS-DOS and Windows). On UN*X and Linux systems this is not so important and the operating system text file end of line is the same as the C/C++ end of line. Doing this forces the file size to be the 900 characters as expected on MS operating systems, and the byte values to be as expected on all systems. Otherwise each byte that happens to represent the '\n' character (byte value of 10 or 0xA) will be translated and appear as (for example on Windows) 13 10 - increasing the file size.

Here are example implementation for Read and Write:

     void Frame::Write( std::ostream & out )
     {
             char const *
               bytesPtr( reinterpret_cast<char const *>(&iBytes[0]) );
             out.write( bytesPtr, FrameByteSize );
     }

     void Frame::Read( std::istream & in )
     {
             char * bytesPtr( reinterpret_cast<char *>(&iBytes[0]) );
             in.read( bytesPtr, FrameByteSize );
     }

We have to cast the address of the ByteType unsigned char at the first (0) vector element to char pointers (pointers to const char for write). Using char as the ByteType may remove the need for the casts but complicates the setting and getting of frame values (if char is signed by default as shifting can sign extend to maintain the sign of a value which we are not interested in).

Once we have a pointer to the byte data we just pass the request along to the stream write or read member functions.

We need to look at the frame data in several different ways:

- as a collection of 8 bit bytes as used by the computer
- as a collection of 10 bit values as required by the application
- as a collection of bits, useful as an intermediate result when converting from 10 bit to 8 bit values.

Each 10 bit value will be split across 2 bytes. The first value (index 0) will occupy all 8 bits in the first byte and the 2 lowest bits in the second. The next (second) value (at index 1) will occupy the remaining 6 highest bits in the second byte and the 4 lowest bits in the third and so on.

The way to handle packing and unpacking the 10 bit values involves a lot of bit calculations and manipulation and is not something that you can understand without thinking about. The explanation is not going to be clear unless you are following carefully. I suggest you get a pen or pencil and paper and start by drawing a sequence of 5 bytes and then pack 4 10 bit values in them noting which positions in which bytes each value occupies. You can also note the absolute bit number each value starts at, viewing the 5 bytes as a 40 bit word with bits numbered 0 to 39. You should draw additional diagrams or add notations and try some examples of values as the explanation proceeds. I suggest you use a value index in the range 0 to 3 for your examples.

Now to get and set 10-bit values we need to locate the two bytes in the byte vector in which the value resides. This is based on the value's index. So first translate the 10-bit index into a bit number where it starts:

       SizeType bit0( idx * ValueBitSize );

Where idx is 0 to 719.

We can then locate the byte by dividing by the number of bits in a byte:

       SizeType byteIdx( bit0 / ByteBitSize );

The value will spill over into the next byte and we can obtain that easily enough by incrementing (i.e. ++byteIdx).

Next we need to obtain information about which parts of the two bytes used to store the value that value occupies. The least significant bit of the value in the first byte is given by the remainder of the start bit number (bit0) and the number of bits in a byte:

       SizeType byte0LSBit( bit0 % ByteBitSize );

The most significant bit of the value in the second byte can be similarly calculated, but is more complex as it is based on the number of remaining bits to be placed in the second byte, which is dependent on the number of bits of the value in the first byte and the number of bits in the values:

       SizeType byte1MSBit(ValueBitSize-(ByteBitSize-byte0LSBit)-1);

This tells us where the value goes but does not help us extract it (for getting) or placing it (for setting). For such operations we need mask values which are values that contain one values for each bit in each of the bytes the value occupies. These can be produced by using shifting:

       ByteType maskByte0( AllByteBits << byte0LSBit );
       ByteType maskByte1(AllByteBits >> (ByteBitSize-byte1MSBit-1));

AllByteBits is a constant having the value of a ByteType when all bits are 1, so has the value 0xff. Shifting is performed by the << and >> operators and is the original use for these operators.

v << n shifts v n bits to the left. For each bit shifted the hightest bit is lost and the zeroth bit becomes 0.

v >> n shifts v n bits to the right. For each bit shifted the hightest bit becomes 0 (or the value of the sign bit if v is signed) and the zeroth bit is lost.

So 11111111 << 2 becomes 11111100 and 11111111 >> 2 becomes 00111111.

We can now form the 10 bit value at an index by extracting the bytes from each of the two byte value locations, removing the parts which are not part of the value in question using the mask values with bitwise AND operations, and combining them using shifting and adding (or ORing):

       ValueType value( (iBytes[byteIdx] & maskByte0) >> byte0LSBit );

gets the value part in the first byte, and:

       ValueType valueUpper(iBytes[ ++byteIdx ] & maskByte1);

the value part in the second byte. They can then be combined:

       value += valueUpper << (ByteBitSize - byte0LSBit);

Note that the upper part is shifted to the correct starting bit in the 10-bit value before being added to the (lower part) value.

Setting a value is a little trickier as we need to split the value into two parts at the appropriate bit position and then place these values into the calculated byte positions in the frame byte vector. Again, this can be done with a combination of masking and shifting:

       ByteType maskValueLower( maskByte0 >> byte0LSBit );
       ByteType byte0( value & maskValueLower );
       ByteType byte1( value >> (ByteBitSize - byte0LSBit) );

Next we have to place the two parts of the value into the byte vector, but as it is likely that there are bits in these bytes that are used for parts of other values we cannot just assign the value's part bytes them. We have to keep the bits in each of the value's bytes that form part of other values an merge in the bits that are for the value we are setting. We can use the ones complement of the value byte masks to extract the bits used for other values as this gives us the bits that are NOT the bits of our values, for example to obtain just the bits used for another value in byte 0 we use:

       iBytes[ byteIdx ] &= ~maskByte0;

We can then add or OR in the bits of the value we are interested in for each byte, shifting into the relevant position. The whole sequence for setting the value byte values into their correct byte vector position is as follows:

       iBytes[ byteIdx ] &= ~maskByte0;
       iBytes[ byteIdx ] |= (byte0 << byte0LSBit);
       ++byteIdx;
       iBytes[ byteIdx ] &= ~maskByte1;
       iBytes[ byteIdx ] |= byte1;

I shall leave it to you to form the above into an implementation of the GetAt and SetAt member functions.

The following can be used as a test program:

       int main()
       {
               Frame frame;
               for ( Frame::ValueType i = 0; i<Frame::FrameSize; ++i )
               {
                       frame.SetAt( i, i );
               }


               {
                       std::ofstream outFile( "newFrameFile"
                                            , std::ios::out
                                            | std::ios::binary
                                            );
                       frame.Write( outFile );
               }

               {
                       std::ifstream inFile( "newFrameFile"
                                           , std::ios::in
                                           | std::ios::binary
                                           );
                       frame.Read( inFile );
               }

               for ( Frame::ValueType i = 0; i<Frame::FrameSize; ++i )
               {
                       std::cout << "frame[" << i << "] = "
                                 << frame.GetAt( i )
                                 << "\n";
               }

       }

You should include:

       #include <vector>
       #include <istream>
       #include <ostream>
       #include <fstream>
       #include <iostream>

Note that this is most likely not the only way to solve this problem and my solution may not be quite how you wish, especially the interface used: maybe you would like to pass in the files as pathnames to Read and Write. Maybe you would like to use operator[] or operator* to set and get values. I'll leave such details up to you. However you may find the latter tricky as such operators usually return their values by reference (as a pointer or reference) and this is not possible here without some additional complexity. You should of course add error and range checking and the like.

I should note that my bit-manipulation operations are not at all optimised for simplicity or speed, as they came straight out of my head. You might like to consider using lookup tables (fixed arrays) to get some of the currently on-the-fly calculated values. This is where the observation that 4 10 bit values fits into 5 8 bit bytes would be useful as the bit positions and mask values for values at an index in the byte array repeats every 4 values / 5 bytes.

I appologise for any errors or typos.

Finally, this has taken a long time to put together. I will reject any further questions of this complexity as I simply cannot spend this amount of time putting together a reply. You will have start using your own brain, sorry.