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.
Printable View
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.
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 );
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
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.
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.
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]);
}
Jim thank you for your help. I will make a test and will return it to you.
Regards
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.
Sayeh, sorry for the delay. I was out of town.
Thak you for your answer.
I will take a deep look at it.
Regards