Thread: bit shifting

  1. #1
    Registered User
    Join Date
    Nov 2003
    Posts
    5

    bit shifting

    I need directions on how to shift right/left a string of bytes by n bits, 0 < n < 64, starting at any bit of any byte.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    It depends on how you plan to represent the bits. Are we talking about an array of bool values or an actual 64 bit data type variable? If it's the latter then you can use the built in operators, otherwise memmove is your friend.

    On a side note, you should have very precise rules for how you intend to fill the vacated positions or how to handle such cases as this:
    Code:
    /* Shift left by 20 bits from the far left bit? */
    shift_left ( bit_array, 0, 20 );
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Nov 2003
    Posts
    5
    In fact, itīs a bitmap of an ascii character that i have to shift, to the right or to the left, depending on the values received. The bits shifted are replaced by zeroes to keep the bmp unchanged.

    Memmove only copies bytes. I didnīt find any references to bits.

    Tia

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Ok, so what exactly are you shifting? You mention a string, a byte, a 64 bit value, so which one is it?

    You could always union an array to a long long int, assuming your compiler supports it, and shift it as Prelude said, with standard operators.

    Otherwise, you could mask off the fragmented bits, and mmove the bytes.

    You'll also want to pay this link a visit.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Nov 2003
    Posts
    5
    Thank you for your answer.

    Depending a parameterized value received , i have to shift a bitmapped character, so what i have is a sequence of bytes that have to shifted, n bits, starting from any point of the byte.

  6. #6
    .
    Join Date
    Nov 2003
    Posts
    307
    I've written a bunch of stuff for work - this is extracted and simplified - also slower.
    It takes a loooong bitstream and shifts all the bits in it.

    To show you what's going on I copied in some other routines which is why the globals and mangled names. you can modify it as you see fit.
    Code:
    /* xbit.c bitshift an arbitrary number of bytes by an arbitrary number of bits */
    /* byte limit in this example 8191 */
    // note: c99 comments are used
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #define BITS 8
    
    static char *_Workstr=NULL;
    void leftshift(unsigned char *, int ,int);
    void rightshift(unsigned char *, int, int);
    void setup(int *, int, int);
    void putbits(unsigned char *, unsigned char *, int,int,int );
    void help(void);
    
    /* these are routines to look or display bit patterns ----  */
    int isbitsetset(unsigned char, int);
    char setbit(unsigned char, int);
    void clear_workstr(void);
    void bld_workstr(size_t);
    char *bitpattern(unsigned char);
    void dumpit(unsigned char *,int);
    /* end -------------------------------------------  */
    
    int main(int argc, char *argv[]){ /* usage xbit filename <left/right> <nbits eg.,123 > */
             char tmp[8192]={'\0'};
             int count=0;         
             int bytecount;         
             unsigned char *ptr;
             if(argc<3) help();
             bytecount=10; /* arbitrary end of buffer assigned */
             count=atoi(argv[2]);
             ptr=(unsigned char *)tmp;
             /* dummy up starting data */
             for(i=0;i<bytecount;i+=2) {*(ptr+i)=255;*(ptr+i+1)=0;}
             /* display input */
             printf("Action shift %s %d bits:%d bytes data before shifting:\n",argv[2],count,bytecount);
             dumpit(ptr,bytecount);
             if(!strcmp(argv[1],"left"))
                       leftshift(ptr,count,bytecount);
             else
                       rightshift(ptr,count,bytecount);
             /* display output */
             printf("Action shift %s %d bits:%d bytes data after shifting:\n",argv[2],count,bytecount);
             dumpit(ptr,bytecount);
             return 0;
    }
    /* shift left count bits, total number of bytes to shift = bytecount */
    void leftshift(unsigned char *src, int count,int bytecount){
    	 unsigned char dest[8192];
    	 unsigned char *start;
    	 int bitcount=0;
    	 memset(dest,0x00,sizeof(dest));
    	 setup(&bitcount,bytecount,count);	
    	 start=dest;
    	 putbits(src,start,bitcount,count,0);
    	 memset(src,0x00,bytecount);
    	 memmove(src, dest, bytecount);
    }
    /* shift right count bits, total number of bytes to shift = bytecount */
    void rightshift(unsigned char *src, int count, int bytecount) {
    	 unsigned char dest[8192];
    	 unsigned char *start;	 
     	 memset(dest,0x00,sizeof(dest));	
    	 start=dest;
    	 putbits(src,start,bytecount*BITS,0,count);
    	 memset(src,0x00,bytecount);
    	 memmove(src, dest, bytecount);
    
    }
    /* emulates a "bit pointer" moving over a giant bit buffer
       and setting bits in a second buffer
    */
    void putbits(unsigned char *source, unsigned char *dest,int bitcount, int offsrc, int offdest  ){
    	 unsigned char values[8]={1,2,4,8,16,32,64,128};
    	 unsigned char *src; /* need local src pointer */
    	 register int destcount;
    	 register int bits;
    	 src=source;
    	 src+= offsrc/BITS;      /* set integral offset from start of source */
    	 offsrc=offsrc%BITS;     /* set bit offset */
    	 dest+= offdest/BITS;
    	 offdest=offdest%BITS;
    	 
    	 /* stomp thru all the bits in the source, setting bits in destination */
    	 for(bits=offsrc,destcount=offdest;bits<=bitcount;bits++,destcount++){
    	 	if((bits) && !(bits%BITS)) src++;
    	 	if((destcount) && !(destcount%BITS)) dest++;
    	        if( isbitset(*src, bits%BITS ))
    	               *dest=setbit(*dest,bits%BITS);
             }
    
    
    
    }
    void setup(int *bits, int bytes, int count){
    	 if( count > BITS * bytes) {          /* this test has to be -- to prevent core dump */
    	 	fprintf(stderr,"%s\n","Invalid shift argument: too large");
    	 	exit(EXIT_FAILURE);
    	 }
             *bits = bytes * BITS;
    	 *bits-=count;
    }
    char *bitpattern(unsigned char ch){             // create a bit pattern string: 0's & 1's
            const char one='1',
                       zero = '0';
    
            struct bitmap{                         // bitfields for a byte
                    unsigned b7:1;
                    unsigned b6:1;
                    unsigned b5:1;
                    unsigned b4:1;
                    unsigned b3:1;
                    unsigned b2:1;
                    unsigned b1:1;
                    unsigned b0:1;
            };
    
            union bits{                            // allow moving a byte into the bitfields
                    unsigned char ch;
                    struct bitmap x;
            } b;
            int i;
            bld_workstr(8);
            for(i=0;i<8;i++)*(_Workstr+i)=zero; // set all the bits to zero for starters
            b.ch = ch;                          // move the char into the union
            if(b.x.b7) *_Workstr=one;           // for each bit set, put a '1' in the string
            if(b.x.b6) *(_Workstr+1)=one;
            if(b.x.b5) *(_Workstr+2)=one;
            if(b.x.b4) *(_Workstr+3)=one;
            if(b.x.b3) *(_Workstr+4)=one;
            if(b.x.b2) *(_Workstr+5)=one;
            if(b.x.b1) *(_Workstr+6)=one;
            if(b.x.b0) *(_Workstr+7)=one;
            return _Workstr;
    }
    
    void bld_workstr(size_t size){         // create working-storage string
    	size++;                        // one bigger than requested
            if(_Workstr==NULL){            // first time into this routine
                    _Workstr=malloc(size);
                    atexit(clear_workstr); // setup memory free when program exits
            }else{
                    realloc(_Workstr,size);// we have been here before, resize string
            }
            memset(_Workstr,0x00,size);    // set all chars to '\0'
            return;
    }
    void clear_workstr(void){              // free any memory used by _Workstr
            if(_Workstr!=NULL) free(_Workstr);
            return;
    }
    void dumpit(unsigned char *ptr, int bytes){
    	int i=1;
    	for(;i<=bytes;i++,ptr++){
    	     printf("%s ",bitpattern(*ptr) );
    	     if((i) && !(i%5))printf("\n");
    	}
    	printf("\n");
    }
    void help(void){
    	fprintf(stderr,"Usage: xbit <filename>  <direction{left/right}>  <bitcount>\n");
    	exit(EXIT_FAILURE);
    }
    int isbitset(unsigned char ch, int check){  // is bit #check set 1=yes
             unsigned char values[8]={1,2,4,8,16,32,64,128};
             check = ch & (~values[check]);
             return !((int)ch==check);
    }
    char setbit(unsigned char ch,int bitnum){ // set bit bitnum on
            unsigned char values[9]={1,2,4,8,16,32,64,128};
            return (ch | values[bitnum]);
    }

  7. #7
    Registered User
    Join Date
    Nov 2003
    Posts
    5
    Jim thank you for your help. I will make a test and will return it to you.


    Regards

  8. #8
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    This, by the very nature of it's redundancy, is a performance-intensive application. Therefore, the proper steps must be taken to analyse what you 1) want to get done, and 2) how to best accomplish that goal with an eye towards performance.

    Here are the givens:

    1) It is not necessary to shift more than 7 bits, period
    2) Since this is a shift, and not a roll, it is not necessary to save bits being overwritten
    3) mmove() is used, but does not mitigate the need for shifting every byte in order to reallign the bits appropriately.
    4) No additional buffering is necessary.

    Here's the solution.

    d = distance to be shifted

    1) Determine modulo, the bits being shifted (d%8).
    2) If zero, means the distance to be shifted is byte-aligned, then just mmove() it and go to step #6
    3) Otherwise, shift everything left or right according to the modulo result.
    4) Get number of bytes to shift (d/8)
    5) mmove() the entire datablock within the buffer by result in step 4.
    6) exit

    Takes approx 12 to 20 lines of code to do it.
    It is not the spoon that bends, it is you who bends around the spoon.

  9. #9
    Registered User
    Join Date
    Nov 2003
    Posts
    5
    Sayeh, sorry for the delay. I was out of town.

    Thak you for your answer.

    I will take a deep look at it.

    Regards

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. bit value check efficiency
    By George2 in forum C Programming
    Replies: 5
    Last Post: 11-05-2007, 07:59 AM
  3. Quick question regardin bit shifting
    By shoobsie in forum C Programming
    Replies: 10
    Last Post: 11-04-2005, 10:46 AM
  4. bit patterns of negtive numbers?
    By chunlee in forum C Programming
    Replies: 4
    Last Post: 11-08-2004, 08:20 AM
  5. bit shifting
    By Nor in forum C++ Programming
    Replies: 9
    Last Post: 08-08-2003, 11:55 AM