Optimize function to write bits to file

Here is a function that writes n bits to a binary file.

Parameters:

• Data : Bit sequence to be written to file (lsb on the right)
• Length: Number of bits to write
• OutFile: Destination file.

First version of the funcion:

void WriteBitsToFile(unsigned long long Data, unsigned Length, std::ofstream & OutFile) {
    static unsigned long long BitBuffer = 0;
    static unsigned BitCounter = 0;

    for (unsigned i = Length; i --; ) {
        (BitBuffer <<= 1) |= ((Data >> i) & 0x1);
        BitCounter ++;

        if (BitCounter == 64) {
            OutFile.write((char *) & BitBuffer, sizeof(BitBuffer));
            BitCounter = 0;
        }
    }
}

Second version:

void WriteBitsToFile(unsigned long long Data, unsigned Length, std::ofstream & OutFile) {
    static unsigned long long BitBuffer = 0;
    static unsigned FreeBitCounter = sizeof(BitBuffer) << 3;

    Data &= (1 << Length) - 1;

    if (FreeB开发者_开发问答itCounter > Length) {
        BitBuffer |= (Data << (FreeBitCounter -= Length));
    } else if (FreeBitCounter < Length) {
        BitBuffer |= (Data >> (Length -= FreeBitCounter));
        OutFile.write((char *) & BitBuffer, sizeof(BitBuffer));
        BitBuffer = Data << ((sizeof(BitBuffer) << 3) - Length);
        FreeBitCounter = (sizeof(BitBuffer) << 3) - Length;
    } else {
        BitBuffer |= Data;
        OutFile.write((char *) & BitBuffer, sizeof(BitBuffer));
        BitBuffer = 0; FreeBitCounter = (sizeof(BitBuffer) << 3);
    }
}

Both of them do the job, but second one is faster then first. Any idea to make it even faster?

Thank you all for help!

1. I would start with removing static variables from your function body. They are a bit slower as should test their state (already initialized or not) on every function call. Just move them out of function scope.

2. Why do you use such short buffer? Are you sure you need to write every unsigned long long into the file? I would suggest using something like unsigned char buffer[1024].

3. Then you should think how to get rid of other "if statements".

Instead of the write() call, try the following:

OutFile.rdbuf()->sputn((char *) & BitBuffer, sizeof(BitBuffer));

Opening the file is likely to be far slower that writing to it. In your design are you minimizing the file open calls?

if I understand you correctly, you want to write length lower bits of the unsigned long long integer you receive. You can save looping through the input bits by masking the required bits:

unsigned long long mask = (1ull << length) - 1; // creates a mask of 'length' 1's
BitBuffer = Data & mask;

as a remark, I don't see why your test and writing is inside the loop, in the first version.

First of all, you need to write the code so it's understandable. I can't easily understand either of your code fragments. Here's an attempt to reformat and refactor the first one to be simpler, and add some comments:

/**
 * @brief Write some bits to a file.
 *
 * The bits are written MSB-first to a temporary 64-bit integer, which is
 * then written to the file in host byte-order.
 *
 * @param Data The data to write to the file.  Only the least-significant
 *             Length bits are written.  Of the bits that are written, the
 *             most significant bit is written first.
 * @param Length The length of the data to write, in bits.  Must be <= 64.
 * @param OutFile The file to write to
 *
 * @note This function is not thread-safe
 * @note This function stores some state in a static variable.  You must
 *       ensure that the total data written is a multiple of 64 bits, or
 *       some data will be lost.  You can only switch from one OutFile to
 *       another on a 64-bit boundry.
 */
void WriteBitsToFile(unsigned long long Data,
                     unsigned Length,
                     std::ofstream & OutFile)
{
   static unsigned long long BitBuffer = 0;
   static unsigned BitCounter = 0; 

   // Loop through input bits, one bit at a time
   for (int i = (int)Length; i >= 0; --i)
   {
      // Get the input bit
      unsigned long long NextBit = ((Data >> i) & 1);

      // Add it to the temporary buffer
      BitBuffer = ((BitBuffer << 1) | NextBit);
      BitCounter++;

      // If the temporary buffer is full, write it out
      if (BitCounter == 64)
      {
         OutFile.write((char *) & BitBuffer, sizeof(BitBuffer));
         BitCounter = 0;
      }
   }
}

Now that I understand what you're trying to do...

Your second version looks much better, because you're avoiding the per-bit loop. Since you're asking about optimizing this, I assume you have profiling results that show that this is slow? And I assume you're putting a lot of data through this?

One possible optimization is to write into a much bigger buffer (I'd suggest at least 4kB). That means you don't need to call write() as often. Calling write() can be relatively slow.

Here's one way to do it with a bigger buffer. (in Pseudo-C#)

const int wordSz= sizeof(unsigned long long)*8;

void WriteBitsToFile(unsigned long long Data, unsigned Length, std::ofstream & OutFile) { 
   static unsigned long long BitBuffer[BUFSZ+1] ={0};  
   static unsigned bitsSoFar = 0;

   Data &= (1 << Length) - 1; 
   int index = bitsSoFar/wordSz;
   int offset = bitsSoFar - (index*wordSz);
   BitBuffer[index]|=Data<<offset;
   int remainder = offset+length-wordSz;
   if (remainder > 0)
   {
      index++;
      BitBuffer[index]=Data>>(length-remainder);
   }
   bitsSoFar+=length;
   if (bitsPacked > BUFSZ*wordSz)
   {
      OutFile.write((char*)BitBuffer, BUFSZ*sizeof(unsigned long long));
      bitsSoFar-=BUFSZ*wordSz;
      BitBuffer[0]=BitBuffer[BUFSZ];
   }
}