Copying bit by bit

This is a discussion on Copying bit by bit within the C Programming forums, part of the General Programming Boards category; Hello, I'm trying to write a function in a similar vein to the standard C function memcpy, only this one ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259

    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++;
    
       }
    
    }

  2. #2
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    Well, looks like there is one potential problem. I don't see where ucSrcEndMask is initialized prior to being used.

  3. #3
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259
    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));

  4. #4
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    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?

  5. #5
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259
    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

  6. #6
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    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?

  7. #7
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    >> 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));
    		}
    
    	}
    }

  8. #8
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259
    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...

  9. #9
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. porting application from 32 bit to 64 bit error
    By gandalf_bar in forum Linux Programming
    Replies: 1
    Last Post: 09-14-2005, 09:20 AM
  2. Bit processing in C
    By eliomancini in forum C Programming
    Replies: 8
    Last Post: 06-07-2005, 10:54 AM
  3. Porting from 32 bit machine to 64 bit machine!
    By anoopks in forum C Programming
    Replies: 10
    Last Post: 02-25-2005, 07:02 PM
  4. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM
  5. bit conversions
    By wazilian in forum C Programming
    Replies: 4
    Last Post: 10-25-2001, 08:59 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21