efficient bit array

Projects Programming
1

Hi there

My current project, i.e. decoding RF Signals from a bunch of wireless thermometers, requires the manipulation of long bit sequences.
As C does not offer a native BIT array I am using INT arrays to store these sequences.

However I will need to reduce the memory footprint and was wondering which route to take.
The available options appear to be either of the following:

  1. Using bitRead(X,n)/bitWrite(X,n) with X being as large as 256 bit - is this possible ??

  2. A bitfield structure like this

struct {
unsigned int bit : 1;
} bits[256];

How large will 'bits' be? 32 byte or 512 byte??

  1. my own 'bit field' class with overloaded [] operator.

But what would {myField[0] = 1;} do if [] was overloaded like so:
unsigned int &operator[] (int i) { /* return bit i */}

Thanks for your input
Sebastian

PS:
The bit sequeces do no follow any 8 or 16 bit pattern. In fact the encoded values each have different bit lengths.

2

As C does not offer a native BIT array I am using INT arrays to store these sequences.

Why waste fifteen bits to store one?

  1. Using bitRead(X,n)/bitWrite(X,n) with X being as large as 256 bit - is this possible ??

Do you know any 256 bit data types?

How large will 'bits' be?

You told the compiler that it'll be one bit.
I expect the compiler will do its best to make "bit" one bit wide.

3

AWOL:
Why waste fifteen bits to store one?
]

My mistake - I am using byte[].

AWOL:
Do you know any 256 bit data types?

No but I know several 256 bit data structures. for instance
byte a[32]
I don't need to know a 'type'

AWOL:
You told the compiler that it'll be one bit.
I expect the compiler will do its best to make "bit" one bit wide.

The question is - does the compiler have the means to to that?
I could of course just try out myself:-)

4 
unsigned char BitArray[256/8];

boolean bitArrayRead(const unsigned int index) {
   if (index > 256)
      return false;
   return (boolean) bitRead(BitArray[index/8], index%8);
}

void bitArrayWrite(const unsigned int index, const boolean value) {
   if (index > 256)
      return;
   bitWrite(BitArray[index/8], index%8, value);
}
5 
if (index > 255)
6

struct
{
unsigned int bit :1;
}bits[1024];

requires aproximately 1024 byte of memory.

I can't tell exactly because in order to keep the compiler from removing unused variables I needed some Serial output which yielded 1200 byte of global variables.

7

johnwasser:

unsigned char BitArray[256/8];

boolean bitArrayRead(const unsigned int index) {
  if (index > 256)
     return false;
  return (boolean) bitRead(BitArray[index/8], index%8);
}

void bitArrayWrite(const unsigned int index, const boolean value) {
  if (index > 256)
     return;
  bitWrite(BitArray[index/8], index%8, value);
}

OK - that would do.
I assume your answer implies that bitWrite can only write to 1 byte variables

So that could be wrapped in a class - right ?

8

I assume your answer implies that bitWrite can only write to 1 byte variables

Why do you assume that?

9

AWOL:
Why do you assume that?

Because he creates 256/8=32 unsigned chars and read/writes to them explicitely ([index/8]).

If bitRead could operate on larger memory blocks
there would be no need to split up the required 32 bytes of memory.

10

Have you looked at the source of bitRead?

Why not?

11

AWOL:
Have you looked at the source of bitRead?

Why not?

Sorry, I am not yet very familiar with the arduino environment.
Where are the sources accessible?

12

Where did you install them?

13

AWOL:
Where did you install them?

Is that a serious question?
Nevermind - I will look for the definition of bitRead and bitWrite myself.

I suppose I will need to find an answer for question #3 also myself - as well as for questions #1 and #2.
Thanks guys :slight_smile:

14

WPD64:
Is that a serious question?

You bet.

15

Have a look at my bitArray Class - BitArray, Class to compactly store ints of (almost) any size, - Libraries - Arduino Forum

It uses dynamic memory which makes it slower than what is possible. On the other hand it can work with any element size, but again it is not fast. For raw performance go with the solution of John Wasser in #3

1 Like
16

robtillaart:
Have a look at my bitArray Class - BitArray, Class to compactly store ints of (almost) any size, - Libraries - Arduino Forum

It uses dynamic memory which makes it slower than what is possible. On the other hand it can work with any element size, but again it is not fast. For raw performance go with the solution of John Wasser in #3

Great. I've already taken a look at it.

Could you briefly explain why the public methods get() and set() loop through the entire bit array to get/set a bit value?

I thought this could be implement in one or two assignments (similar to John Wasser's solution)

Thanks!

17

Could you briefly explain why the public methods get() and set() loop through the entire bit array to get/set a bit value?

The bitArray class can be used also to store an array of elements of any size from 1 to 31 bits in the most efficient way. This can be 1000 elements of 1 bit (boolean) or 2000 elements of 3 bits (throw of a dice) or 500 elements of 10 bits (analogRead)

The get() and set() do not go through the entire array, they only go through every bit of the element to be stored / retrieved. Storing and retrieving elements is done bit by bit to be sure it is correct. At a lower level the memory location of the bits are calculated for every bit. This can be made more efficient but I need a good design to keep it generic without increasing the footprint too much.

A class that only can store 1 bit elements (boolArray?) could be based upon the bitArray class in a more efficient way as the location of every bit is easier to calculate. The footprint of the boolArray would probably be slightly smaller too.

I thought this could be implement in one or two assignments (similar to John Wasser's solution)
Yes, it can if you use an array size smaller than 2000 bits (that would fit in one allocation block)

18

From Arduino.h:

#define bitRead(value, bit) (((value) >> (bit)) & 0x01)
#define bitSet(value, bit) ((value) |= (1UL << (bit)))
#define bitClear(value, bit) ((value) &= ~(1UL << (bit)))
#define bitWrite(value, bit, bitvalue) (bitvalue ? bitSet(value, bit) : bitClear(value, bit))

Yes, the macros will work with variables larger than a byte but on an 8-bit processor the generated code is generally more efficient if you use byte variables.

19

OK because it is Sinterklaas a quick implemented boolArray Class (see attachment)

  • similar interface as the bitArray Class - but substantial faster
  • not extensively tested (no guarantees)
  • max 2000 elements.

have fun!

BoolArray.zip (2.01 KB)

20

robtillaart:
A class that only can store 1 bit elements (boolArray?) could be based upon the bitArray class in a more efficient way as the location of every bit is easier to calculate. The footprint of the boolArray would probably be slightly smaller too.
...

I thought this could be implement in one or two assignments (similar to John Wasser's solution)
Yes, it can if you use an array size smaller than 2000 bits (that would fit in one allocation block)

Thanks a lot Rob.
I will probably implement a bit array class tailored to my problem.

Thanks to all and take care
Sebastian