Fast bitwise algorithm

[in_tyrannos]

First, the file is read to the buffer. Now, I want to access this
buffer in the following way. Start index is defined as i =
j*size(byte) +k*size(bit) = j*8+k*1. The length of the sequence to be
read from buffer is defined similarly. So basically, I want to read
sequence of bits from buffer at specified bit-location. Further, I
want to do this efficiently.

For example, start index is 13. The length of sequence of bits to be
read is 17. This means that (when reading bytes in c), we first read
two bytes to reach position 13 from positon 0. Sequence is now
obtained by reading 3 bits from second byte, then 16 bits (=two
bytes). From the last byte we read only 6 bits. Since c has only
limited number of primitive types, the question becomes: "How to do
this efficiently?" Of course, next the solution should be expandable
to such scheme, where the original is read continuosly to the buffer,
and bit-sequnces are also read continuosly (size of the buffer and
sequnce should be variables)...

Any ideas? Maybe something like this is done when writing file headers
or compressing files?

BR, J

 

[user923005]

First, the file is read to the buffer. Now, I want to access this
buffer in the following way. Start index is defined as i =
j*size(byte) +k*size(bit) = j*8+k*1. The length of the sequence to be
read from buffer is defined similarly. So basically, I want to read
sequence of bits from buffer at specified bit-location. Further, I
want to do this efficiently.

For example, start index is 13. The length of sequence of bits to be
read is 17. This means that (when reading bytes in c), we first read
two bytes to reach position 13 from positon 0. Sequence is now
obtained by reading 3 bits from second byte, then 16 bits (=two
bytes). From the last byte we read only 6 bits. Since c has only
limited number of primitive types, the question becomes: "How to do
this efficiently?" Of course, next the solution should be expandable
to such scheme, where the original is read continuosly to the buffer,
and bit-sequnces are also read continuosly (size of the buffer and
sequnce should be variables)...

Any ideas? Maybe something like this is done when writing file headers
or compressing files?

It's a FAQ:

20.8: How can I implement sets or arrays of bits?

A: Use arrays of char or int, with a few macros to access the
desired bit at the proper index. Here are some simple macros to
use with arrays of char:

#include <limits.h> /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

(If you don't have <limits.h>, try using 8 for CHAR_BIT.)

References: H&S Sec. 7.6.7 pp. 211-216.

The C-FAQ book has a lot more detail.

 

[Thad Smith]

First, the file is read to the buffer. Now, I want to access this
buffer in the following way. Start index is defined as i =
j*size(byte) +k*size(bit) = j*8+k*1. The length of the sequence to be
read from buffer is defined similarly. So basically, I want to read
sequence of bits from buffer at specified bit-location. Further, I
want to do this efficiently.

For example, start index is 13. The length of sequence of bits to be
read is 17. This means that (when reading bytes in c), we first read
two bytes to reach position 13 from positon 0. Sequence is now
obtained by reading 3 bits from second byte, then 16 bits (=two
bytes). From the last byte we read only 6 bits. Since c has only
limited number of primitive types, the question becomes: "How to do
this efficiently?" Of course, next the solution should be expandable
to such scheme, where the original is read continuosly to the buffer,
and bit-sequnces are also read continuosly (size of the buffer and
sequnce should be variables)...

Any ideas? Maybe something like this is done when writing file headers
or compressing files?

It's a FAQ:

20.8: How can I implement sets or arrays of bits?

A: Use arrays of char or int, with a few macros to access the
desired bit at the proper index. Here are some simple macros to
use with arrays of char:

#include <limits.h> /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

(If you don't have <limits.h>, try using 8 for CHAR_BIT.)

This works well for accessing single bits. For grabbing fields of bits
limited to a length of a built-in integer type, I would locate the first
byte, concatenate them into a large enough unsigned integer using shift
and bitwise-or,then shift and mask to align properly.