bitshift a large amount of data

[Eric.Medlin]

I am reading in 1bit data to a buffer that contains over 30000 bits and
I would like to beable to bitshift the entire buffer and AND and OR it
with other buffers of the same size. I though I could use the stl
bitset class, but I cannot find a way to load the buffer into the
bitset. I have been trying with this test program (with the size
scaled down to 1024 bits) to load a buffer into the bitset, but prints
out all zeros.

#include <iostream>
#include <bitset>

int main(){
int const size = 1024;
unsigned char* data = new unsigned char[size];
*(data+1000) = 0xEA;
std::bitset<size> bits(*data);
std::cout<<bits.count()<<std::endl;
std::cout<<bits<<std::endl;
delete[] data;
return 0;
}

 

[roberts.noah]

I am reading in 1bit data to a buffer that contains over 30000 bits and
I would like to beable to bitshift the entire buffer and AND and OR it
with other buffers of the same size. I though I could use the stl
bitset class, but I cannot find a way to load the buffer into the
bitset. I have been trying with this test program (with the size
scaled down to 1024 bits) to load a buffer into the bitset, but prints
out all zeros.

#include <iostream>
#include <bitset>

int main(){
int const size = 1024;
unsigned char* data = new unsigned char[size];
*(data+1000) = 0xEA;
std::bitset<size> bits(*data);

Who knows what will be in this data. All 0 is just one possibility.
You never assign that area of memory any value. The compiler is being
nice to you.

Try bits(0xEA);

You're using the unsigned long constructor. I'm not positive how the
conversion is done but my bet is you are actually only passing the
first byte of "data" into the constructor. The data you set is of
course 1000 bytes away.

 

[Eric.Medlin]

I don't care what is in the data right now because this is just a test.
My compiler is giving me zeros and I assigne data+1000 0xEA just to
puts some ones in the buffer. I believe you are right about the
unsigned long constructor being used. Is there away to make bitset use
a buffer I give it?

 

[roberts.noah]

I don't care what is in the data right now because this is just a test.
My compiler is giving me zeros and I assigne data+1000 0xEA just to
puts some ones in the buffer. I believe you are right about the
unsigned long constructor being used. Is there away to make bitset use
a buffer I give it?

No, there are a few shortcommings of bitset and the inability to define
one in terms of actual bits is one of those things. You can only do so
up to the size of an unsigned long.

Your other option is to define a string of 1's and 0's and pass it in.
You could also do something like:

unsigned long array[size/sizeof(unsigned long)] = {####L, etc};
bitset<size> bits;

for (int i = 0; i < size/sizeof(unsigned long); ++i)
bits |= (bitset<size>(array) << i * sizeof(unsigned long));

That is untested btw...

 

[Eric.Medlin]

That is what I was afraid of. No way to define a bitset based on a
random memory buffer. I saw how you could define it as string, but
that will not help me. Strangly, I just wrote a test program similar
to yours before I read your response. I used unsigned char instead of
unsigned longs though because my data is byte aligned not 4 byte
aligned. I may change that though so I can load 4 bytes at a time
instead of 1 byte at a time.

1 #include <iostream>
2 #include <bitset>
3
4 int main(){
5 int const size = 256;
6 unsigned char* data = new unsigned char[size/8];
7 unsigned char* dataBegin = data;
8 *(data) = 0xEA;
9 *(data+1) = 0x1;
10 *(data+8) = 0xFF;
11 std::bitset<size> bits;
12 for(int i=0; i<size/8; ++i){
13 bits <<= 8;
14 bits |= std::bitset<size>(*data);
15 ++data;
16 }
17 std::cout<<bits.count()<<std::endl;
18 std::cout<<bits<<std::endl;
19 delete[] dataBegin;
20 return 0;
21 }

 

[Alf P. Steinbach]

* Eric Medlin:

I am reading in 1bit data to a buffer that contains over 30000 bits and
I would like to beable to bitshift the entire buffer and AND and OR it
with other buffers of the same size. I though I could use the stl
bitset class, but I cannot find a way to load the buffer into the
bitset. I have been trying with this test program (with the size
scaled down to 1024 bits) to load a buffer into the bitset, but prints
out all zeros.

#include <iostream>
#include <bitset>

int main(){
int const size = 1024;
unsigned char* data = new unsigned char[size];
*(data+1000) = 0xEA;
std::bitset<size> bits(*data);
std::cout<<bits.count()<<std::endl;
std::cout<<bits<<std::endl;
delete[] data;
return 0;
}

No standard library container can use external storage for its elements;
it makes a copy of the data (that's why container elements must be
copyable).

You can use a std::bitset directly, or you can copy the data to and from
a std::bitset, or you can roll your own.

For the latter, if measurements tell you that you have to optimize, it
might be a good idea to look up your system's available bitblt
functions; typically they employ graphics hardware to do the operations.

 

[Eric.Medlin]

Well even loading the data 4 bytes at a time it is just to slow for me
to load the data that way. Using a size 30000 it takes 0.015 secs when
a memcpy only takes 0.00005 secs. I have to load 30000 rows of data at
a size of 30000. That makes this way of loading bitset to slow for me.
So unless its bitshift and AND and OR operators are way faster than
what I can write for a big chunk of memory then I won't be able to use
it. And it looks like such an easy solution to my problem to if you
could only loaded it up faster.

 

[Jim Langston]

I am reading in 1bit data to a buffer that contains over 30000 bits and
I would like to beable to bitshift the entire buffer and AND and OR it
with other buffers of the same size. I though I could use the stl
bitset class, but I cannot find a way to load the buffer into the
bitset. I have been trying with this test program (with the size
scaled down to 1024 bits) to load a buffer into the bitset, but prints
out all zeros.

#include <iostream>
#include <bitset>

int main(){
int const size = 1024;
unsigned char* data = new unsigned char[size];
*(data+1000) = 0xEA;
std::bitset<size> bits(*data);
std::cout<<bits.count()<<std::endl;
std::cout<<bits<<std::endl;
delete[] data;
return 0;
}

If I had to do this, I don't think I'd actually shift the bits until a
bit/byte value was requested.

I would create a vector of unsigned char and allocate enought memory for
3000 bytes and load the data into the vector. Shifting right or left by any
multiple of 8 is trivial. Shift right by 8, delete the last char, push 0
onto the front. Shift left by 8, delete the first element, push 0 onto the
back.

Your only concern comes in then when you actually want to read the bits
(perhaps to AND or OR them). Encapsulate the vector with a class, over ride
the >> and << to do your custom shifting (only shift by mulitples of 8, any
remainder keep in a variable). Override []. When [] is used build the byte
to return. The override of [] would be a little more difficult, but not
much.

Say, for instance, they had shifted right 12. You would delete the last
element, push a 0 onto the front. That leaves a remainder of 4 to shift
right. So if the [] method requests byte 100, you would know to build the
byte by shifting the 100 element right 4, and making the high 4 bits the low
bits of element 99.

return (( BitVector[100] >> 4 ) & 0x0F ) | (( BitVector[99] << 4 ) & 0xF0)

That is untested, but I'm fairly sure it's right. Of course the constant 4
would be in a variable, and you would do something similar if it was shifted
left, and look out for your first and last elements.

The ANDing and ORing is trivial, just do it a byte at a time (with the
returned shifted value of course) and build a new vector to return.

 

[Larry I Smith]

I am reading in 1bit data to a buffer that contains over 30000 bits and
I would like to beable to bitshift the entire buffer and AND and OR it
with other buffers of the same size. I though I could use the stl
bitset class, but I cannot find a way to load the buffer into the
bitset. I have been trying with this test program (with the size
scaled down to 1024 bits) to load a buffer into the bitset, but prints
out all zeros.

#include <iostream>
#include <bitset>

int main(){
int const size = 1024;
unsigned char* data = new unsigned char[size];
*(data+1000) = 0xEA;
std::bitset<size> bits(*data);
std::cout<<bits.count()<<std::endl;
std::cout<<bits<<std::endl;
delete[] data;
return 0;
}

See page 122 ('Sets' chapter) in "Applying C++" by
Scott Robert Ladd.

That chapter contains a complete implemenation of
a ShortBitSet class that handles up to 65k bits and
a LongBitSet class that handles up to 4 billion bits.
'or', 'and', etc operators are included, but shift
operators are not - you'll have to add your own.

Regards,
Larry