Thread: Copying bit by bit

Hello,

I'm trying to write a function in a similar vein to the standard C function memcpy, only this one copies individual bits from one place to another. The source and the destination could be aligned/unaligned, so I'm doing the old heave-ho (shifting and masking).

It's appears to be so close to being correct that I've spent hours today trying to figure out what the problem is with it. As I don't fancy going blind, I'm posting it so some fresh minds can take a look and probably find the issue straight away.

My logic in this function is thus:-

1. Use a particular ......../mask combination for the first destination byte
2. Use a particular ......../mask combination for successive destination bytes
3. Use a particular ......../mask combination for the last destination byte

This should ensure that however the source and destination bits are aligned, one will copy to the other.

You may scratch your head at one or two little things in this, to be honest I don't know why they're there, they just appear to make the output correct with certain inputs. Just not all inputs, it would seem.

So, without further ado:-

Code:

void bitcpy(unsigned char *lpDest, int iDestBit, unsigned char *lpSrc, int iSrcBit, int iLength)
{
   int iCopied = 0, iDestShift, iSrcShift;
   unsigned char ucDestEndMask, ucDestStartMask, ucSrcEndMask;

   // Please don't feed me rubbish
   if (!lpDest || !lpSrc)
      return;

   // Set up shifts and masks for initial copy
   iDestShift = iDestBit & 7;
   iSrcShift = iSrcBit & 7;
   ucDestEndMask = 0xFF >> ((iDestBit + iLength) & 7);
   ucDestStartMask = ~(0xFF >> iDestShift);
   if (!((iDestBit + iLength) & 7))
      ucDestEndMask = ~ucDestEndMask;
			
   while (iCopied < iLength)
   {
      // Recalculate mask if first dest byte needed more than one copy
      if (iCopied > 0 && (iDestBit + iCopied) <= 8)
      {
         if (iDestShift)
            ucDestStartMask = ~(0xFF >> iDestShift);
         else
            ucDestStartMask = ~(0xFF << iSrcShift);

      }

      // Final dest byte?
      if ((iDestBit + iCopied) >= (iLength & ~7))
      {
         // Modify mask and keep trailing bits safe
         if (iDestShift)
            ucDestStartMask = 0xFF >> iDestShift;
         else
            ucDestStartMask = 0xFF << iSrcShift;

         ucDestEndMask |= ucDestStartMask;
         *lpDest &= ucDestEndMask;
         if (!(iCopied & 7) && iDestShift)
            *lpDest |= ((*lpSrc & ucSrcEndMask) >> iSrcShift) << iDestShift;
         else
            *lpDest |= ((*lpSrc & ucSrcEndMask) << iSrcShift) >> iDestShift;

      }
      else
      {
         *lpDest &= ucDestStartMask;
         if (iCopied && !(iCopied & 7) && iDestShift)
            *lpDest |= (*lpSrc >> iSrcShift) << iDestShift;
         else
            *lpDest |= ((*lpSrc << iSrcShift) & 0xFF) >> iDestShift;

      }

      // How many bits did we copy?
      if (iDestShift)
         iCopied += 8 - iDestShift;
      else
         iCopied += 8 - iSrcShift;

      // Clamp for calculations
      if (iCopied > iLength)
         iCopied = iLength;

      // Recalculate shifts
      iDestShift = (iDestBit + iCopied) & 7;
      iSrcShift = (iSrcBit + iCopied) & 7;

      // Flip mask
      if (ucDestStartMask)
         ucDestStartMask = ~ucDestStartMask;

      if (!iDestShift)
         lpDest++;

      if (!iSrcShift)
         lpSrc++;

   }

}

Well, looks like there is one potential problem. I don't see where ucSrcEndMask is initialized prior to being used.

Point. It is there on my copy, but it looks like it disappeared along with the tabs on this version. I need sleep.

Code:

(before the while)
ucSrcEndMask = ~(0xFF >> ((iSrcBit + sLength) & 7));

Well, looks like there is one potential problem. I don't see where ucSrcEndMask is initialized prior to being used.

If you understood that code enough to suggest a problem in less than twenty minutes, you are a genius!

For the rest of us, SMurf, could you tell us exactly what your function is meant to achieve (and the meaning of its arguments) and we may be able to make some suggestions. Is it trying to copy a single bit in each byte or a range of bits?

Fine, fine. Spoil the fun of personal discovery...

bitcpy copies iLength bits from lpDest to lpSrc. iDestBit and iSrcBit specify the bit offsets into the initial destination and source bytes respectively.

0 <= iDestBit < 8
0 <= iSrcBit < 8

If you understood that code enough to suggest a problem in less than twenty minutes, you are a genius!

Well, first of all I do NOT fully understand the code even though it is somewhat commented. I just pointed out a fairly common programming mistake that most people including myself often make. Anybody doing a cursory review of the code would have noticed this problem. I just happened to notice it first.

SMurf, sLength is not defined in your snippet?

>> Fine, fine. Spoil the fun of personal discovery... <<

I tried, but then my mind exploded and now I've got to clean it up!

This seems to work. You may have to tweak to suit your requirements.

Code:

/*
 * bitcpy copies BitCount bits from pSrc to pDest. DestOffset and SrcOffset
 * specify the bit offsets (0 based, from left to right) into the initial destination
 * and source bytes respectively.
 * Note: Doesn't touch destination bits outside the range of DstOffset + BitCount.
 */
void bitcpy(unsigned char* pDst, size_t DstOffset, 
            unsigned char* pSrc, size_t SrcOffset,
            size_t BitCount)
{
	size_t i, DstByte, SrcByte, DstBit, SrcBit, SrcState;

	if (!pDst || !pSrc)
		return;

	for (i = 0; i < BitCount; i++)
	{
		/* Calculate the source and destination bytes we are working on. */
		SrcByte = (SrcOffset + i) / 8;
		DstByte = (DstOffset + i) / 8;

		/* Calculate the bit offsets. */
		SrcBit = (SrcOffset + i) % 8;
		DstBit = (DstOffset + i) % 8;

		/* Calculate the state of the specified source bit. */
		SrcState = pSrc[SrcByte] & (1 << (7 - SrcBit));

		if (SrcState)
		{
			/* The src bit was set, set the corresponding destination bit. */
			pDst[DstByte] |= (1 << (7 - DstBit));
		}
		else
		{
			/* The src bit was off, turn off the corresponding destination bit. */
			pDst[DstByte] &= ~(1 << (7 - DstBit));
		}

	}
}

On the money.

This does actually look similar to the code I started from, before I went down the "But what if I could set more than one bit at a time?" route. The code I posted, coupled with the few input variables that produce correct output, does copy 1-8 bits per iteration.

But as you can see, it gets complicated then, aligning everything...

One more thing related to this:- supposing I want to do some other things with the end of the copied data. Given source arguments that don't change and varying DstOffset, DstByte also changes when the loop finishes depending on whether a full byte was written or not.

How can I ensure that DstByte always refers to the next "clean" destination byte?