Problem storing random number of bits to a byte.

Hi, Hope you all are fine. I facing problem that I have a sensor whose values I have to store in arduino, so I use data compression technique similar to huffman coding. SO now I am facing problem that for example first value of sensor after data compreesion is 11 in bits after that the other value come like 101 in bits after that 10 in bits. So I have store these three values of sensor in one byte B11101100. I also uses bit manipulation techniques and able to 2 sensor values in one byte 2 nibbles, but I have to store more then that but could not able to find solution :(

Why use compression? Seems like an odd choice of solution.

If you need to store a lot of data, just set up something, like an SD card that can handle lots of data.

-jim lee

Yeah you are right but my project condition is that to store efficiently in Arduino memory.

Basically the data is stored efficiently in the arduino till when the wirless access point is not in the range, as it is in the range it will send all the data to the server.....

Which Arduino, and what memory do you have in mind?

Arduino UNO and storing in heap memory, using ring buffer.

So, your sensor can return one of a number of discrete values, say 0,1,2,3 or 4. You want to (or you have to, because it looks like a school exercise) pack these most efficiently in a buffer. You have developed a encoding scheme, say :
0 is represented by 00
1 is represented by 10
2 is represented by 11
3 is represented by 010
4 is represented by 011

So, let’s say the buffer is empty and is 3 bytes long
xxxxxxxx xxxxxxxx xxxxxxxx

The sensor returns a 4, encoded as 011) so the buffer is now:
011xxxxx xxxxxxxx xxxxxxxx

The sensor returns a 1, (encoded as 01) so the buffer is now:
01101xxx xxxxxxxx xxxxxxxx

You have to maintain an index into the buffer indicating the next free position. Initially it is 0. When it gets to 23 it wraps round back to 0 because you have said it is a circular buffer.
You can use bitWrite() to write individual bits into the bytes of the buffer (bear in mind that the left most, that is the high order bit, is bit 7 and the rightmost bit is 0. If the buffer is short, say 4 bytes you could also use another data type, say uint32_t (an unsigned long), for the whole buffer.
You have to handle crossing byte boundaries, where a value you write spans two bytes.
The exercise becomes even more complex when you have to also read from the buffer.
Normally, a circular buffer is implemented as a queue where you are adding new data at the head and removing it from the tail, checking when you add that the buffer is not full and, conversely, that it is not empty when you read from it. If the exercise goes so far, you’d develop functions such as add(), take(), isFull(), isEmpty() and then you are really getting good.

Thank you for a brief explanation. So there are some problems with my concept or my limited knowlegde with arduino,

  1. As you said as an example…
    0 is represented by 00
    1 is represented by 10
    2 is represented by 11
    3 is represented by 110
    4 is represented by 011
    So arduino will store it as 1 byte so I have to read the high bits of a byte like for example for 1, B00000010, so I am storing this value in a byte variable “P” by shifting B00000010 << 6 , so the resultant is B10000000.
    Now I have to store the next value which is 3 for example which is B00000110 so now I have a problem that how can I know that the variable “P” have to store the value from index 2 so that the resultant will be B10110000, that is my problem…

The code below is that, I simply made a manual Huffman tree with specific frequencies. First I am serching for the highest frequency , then get its index number and if the sensor value is equal to that index it will store a specific compressed value. So after that I have to store it in a byte because arduino minimum data type you can play with is byte so I have to store it in byte efficiently, that is my problem I am facing.

byte Huff(byte K){
int freq[]={5,2,3,4,4,3,2,1};
int first = freq[0];
byte firt=0;
byte K=0;
byte secd=0;
byte thrd=0;
byte frth=0;
byte fift=0;
byte sixt=0;
byte sevt=0;
byte Code=B00000000;
byte chk=0;
int fir {};
 Serial.begin(9600);
 
 for(int i=1;i<8;i++){
   if(first<freq[i]){
     first=freq[i];
      firt=i;
      
      }
      if(first==freq[i+1]){
       chk=(i+1);
      
   }
   }
if(K==firt || K==chk){
 Code=B00000000;
}
   
   Serial.println(firt);
   Serial.print("chk: ");
   Serial.println(chk);
   int secnd=0;
   for(int i=0;i<8;i++){
     if(freq[i]>secnd && freq[i]<first){
       secnd=freq[i];
       secd=i;
     }
   }
     for(int i=0;i<8;i++){
     if(freq[i+1]==secnd){
       chk=(i+1);
       Serial.print("ma yeahn");
      Serial.print("chk: ");
   Serial.println(chk);
   }
   }
   if(K==secd || K==chk){
 Code=B00000011 ;
}
   Serial.println(secd);
   Serial.print("chk: ");
   Serial.println(chk);
    int third=0;
    for(int i=0;i<8;i++){
     if(freq[i]>third && freq[i]<secnd && freq[i]<first){
     third=freq[i];
      thrd=i;
   }
    }
         for(int i=0;i<8;i++){
   if(third==freq[i+1]){
       chk=(i+1);
   }
      
   }
   
     if(K==thrd || K==chk){
 Code=B00000001;
}
   Serial.println(thrd);
   Serial.print("chk: ");
   Serial.println(chk);
   int fourth=0;
   for(int i=0;i<8;i++){
     if(freq[i]>fourth && freq[i]<third && freq[i]<secnd && freq[i]<first){
     fourth=freq[i];
      frth=i;
   }
   }
        for(int i=0;i<8;i++){
   if(fourth==freq[i+1]){
       chk=(i+1);
   }
   }
     if(K==frth || K==chk){
 Code=B00000101;
}
  
   Serial.println(frth);
   Serial.print("chk: ");
   Serial.println(chk);
   int fifth=0;
    for(int i=0;i<8;i++){
     if(freq[i]>fifth && freq[i]<fourth && freq[i]<third && freq[i]<secnd && freq[i]<first){
     fifth=freq[i];
      fift=i;
   }
    }
         for(int i=0;i<8;i++){
   if(fifth==freq[i+1]){
       chk=(i+1);
      
   }
   }
     if(K==fift || K==chk){
 Code=00000111;
}

   Serial.println(fift);
   Serial.print("chk: ");
   Serial.println(chk);
   int sixth=0;
   for(int i=0;i<8;i++){
     if(freq>sixth && freq[i]<fifth && freq[i]<fourth && freq[i]<third && freq[i]<secnd && freq[i]<first){
     sixth=freq[i];
      sixt=i;
   }
   }
        for(int i=0;i<8;i++){
   if(sixth==freq[i+1]){
       chk=(i+1);
      
   }
   }
//      

//}
   Serial.println(sixt);
   Serial.print("chk: ");
   Serial.println(chk);

Serial.print("Code :");
Serial.println(Code);
return(Code);
}
for(byte i=8;i>0;i++){
 TE[i]=bitRead(HUF,i)
}
if(Code==0 || Code==1 || Code==2 || Code==3){
 HUF= Code << 6;
}
if(Code==4 || Code==5 || Code==6 || Code==7){
 HUF= Code << 5;
}
if(Code==8 || Code==9 || Code==10){
 Huf= Code << 4;
}
void loop(){
}

I don’t fully understand your code fully, but that function Huff( K ) simply builds an encoding table and encodes a byte given to it as input and returns the encoded value ?
Incidentally, it appears very early to reset the input parameter K to 0 so effectively ignores it.

So your problem now is to take the encoded values and to pack these into a some storage structure, which you have yet to define.
You are correct that the byte is the smallest addressable unit of storage in C++ so your storage structure will probably be a byte array.

Important when you produce a value to pack into the table is that you also know the number of bits of that value, so any function which returns an encoded byte must also convey (somehow) the number of bits.

In your position, I’d actually start defining the storage structures and functions at a higher level, for storage, retrieval etc. and then work on the implementation of those functions. Your immediate problem, though, appears to be how to pack a value into the storage structure for the encoded data.

Let’s say you have value in a byte Q and in contains 2 encoded bits.
So you need a boolean function storeEncodedValue( value, bitLength ). The return value will be true if OK and false if the store is full. So call storeEncodedValue(Q, 2 )

You’ll also need the storage structure itself:
const uint16_t encDataStoreSize = 32 ; // only an example of the size of the store in bytes.
byte encDataStore[ encDataStoreSize ] = {0} ; Array

and an index to address it. This will be in a number of bits, so you must divide by eight to get the current byte.
int16_t edsBitIndex = 0 ; // initial value

Now start working on the definition of storeEncodedValue( value, bitLength ).

bool storeEncodedValue( value, bitLength ) 
Pseudo code;
check: is there enough room in the store for the new value 
   something like if (  (edsBitIndex + bitLength)  <  encDataStoreSize * 8 ) there is enough room
  if yes, pack the new value into the store and then increment the index in preparation for the next value.
      shift the value left justified in a temporary variable, say P as you have shown.
      now add the highest order bit from P into the byte/bit referenced by edsBitIndex
      Something like: 
         bitWrite( encDataStore[ edsBitIndex/8 ], edsBitIndex%8 , bitRead( P, 7 ) ) ;  // % modulus division - remainder 0..7
         then increment edsBitIndex to prepare for the next bit:  edsBitIndex++
         Now repeat until there are no more bits in value.
           Shift variable P 1 bit left so that the next bit is in the high order position, and do the same again:
           bitWrite( encDataStore[ edsBitIndex/8 ], edsBitIndex%8 , bitRead( P, 7 ) ;  // % gives remainder
           edsBitIndex++
      return ( true ) ; 
  if not enough room in store, return ( false )

I try this psuedo code and have confusion in this line

now add the highest order bit from P into the byte/bit referenced by edsBitIndex
      Something like:
         bitWrite( encDataStore[ edsBitIndex/8 ], edsBitIndex%8 , bitRead( P, 7 ) ) ;  // % modulus division - remainder 0..7

Here bitwrite(encDataStore[edsBitIndex/8], is confusing to me and what do you mean by adding the highest order bit from P into the byte/bit referenced by edsBitIndex?
I also try it below.

int freq[]={5,2,3,4,4,3,2,1};
int first = freq[0];
byte firt=0;
byte K=3;
byte secd=0;                            
byte thrd=0;
byte frth=0;
byte fift=0;
byte W=0;
byte sixt=0;
byte edsBitindex=0;
const byte encdataStoreSize=32;
byte arra[encdataStoreSize]={0};
byte sevt=0;
byte Code=B00000000;
byte chk=0;
int fir {};

bool storeEncodedValue (byte value,byte bitlength){
  byte Store=0;
  if((edsBitindex + bitlength) < encdataStoreSize *8){
    Serial.print("...........");
Store=value << (8-bitlength);
//Serial.println(Store,BIN);
for(byte i=edsBitindex;i<bitlength;i++){
  
  bitWrite(arra[1],edsBitindex%8,bitRead(Store,i));// here arra[1] I used just to simple check if it add or not in                     
                                                                          // first byte also bitRead(Store,i) having problem with it.                                                                                  
  Serial.println(arra[1],BIN);
  edsBitindex++;
  Serial.println(edsBitindex);
     
}
return (true);
  }
  else
  return(false);
}

ABDanyia:
I try this psuedo code and have confusion in this line

now add the highest order bit from P into the byte/bit referenced by edsBitIndex

Something like:
        bitWrite( encDataStore[ edsBitIndex/8 ], edsBitIndex%8 , bitRead( P, 7 ) ) ;  // % modulus division - remainder 0…7




Here bitwrite(encDataStore[edsBitIndex/8], is confusing to me and what do you mean by adding the highest order bit from P into the byte/bit referenced by edsBitIndex?
I also try it below.

OK. Where I have used the variable name ‘P’, you have used Store. Since you have copied ‘value’ into store and shifted store left by N places, the high order bit (that is bit 7) of store now contains the bit which has to be written next into array. The position in the array is indicated by the variable ‘edsBitindex’ which is pointing at next free bit position in the array.

Since the array is an array of bytes, and edsBitindex is a number of bits, it is necessary to divide edsBitindex by 8 to find the byte in the array which has to be written to. Hence encDataStore[edsBitIndex/8] .

bitWrite() needs a byte to be written to, a bit within that byte, and what that bit is (0 or 1).

So instead of this
bitWrite(arra[1], edsBitindex % 8, bitRead(Store, i)) ;

you should use
bitWrite( arra[edsBitIndex/8] , edsBitindex % 8, bitRead(Store, i)) ;

If you want to print out its value, then it will initially be arra[0].

I guess you have understood that arra is a linear buffer. If you want a ring buffer, the logic is a bit more complex, but get something working first as it is.

I’ve made some small changes below.

bool storeEncodedValue (byte value, byte bitlength) {
  byte Store = 0;
  if ((edsBitindex + bitlength) < encdataStoreSize * 8) {
    Serial.print("...........");
    Store = value << (8 - bitlength);
    //Serial.println(Store,BIN);
    for (byte i = 0 ; i < bitlength; i++) {

      bitWrite(arra[edsBitIndex/8] , edsBitindex % 8, bitRead(Store, 7 )); // here arra[1] I used just to simple check if it add or not in
      // you want just bit 7 of store because you should now you shift Store again to get the next bit at position 7
      Store = Store << 1 ;   // moves the next bit into bit 7 of store for the next iteration.
      // first byte also bitRead(Store,i) having problem with it.
      Serial.println(arra[1], BIN);
      edsBitindex++;
      Serial.println(edsBitindex);

    }
    return (true);
  }
  else
    return (false);
}

Incidentally, when you post code, use the auto formatter tool in the IDE to make it easier to read.

you should use
bitWrite( arra[edsBitIndex/8] , edsBitindex % 8, bitRead(Store, i)) ;

If you want to print out its value, then it will initially be arra[0].

So first the edsBitIndex=0 , in second iteration after increment it will be edsBitIndex=1, so what is the meaning of this then ...... bitWrite( arra[1/8] , edsBitindex % 8, bitRead(Store, i)) ;

And also after running the above code I just able to wrote first value....

ABDanyia: ``` you should use bitWrite( arra[edsBitIndex/8] , edsBitindex % 8, bitRead(Store, i)) ;

If you want to print out its value, then it will initially be arra[0].




So first the edsBitIndex=0 , in second iteration after increment it will be edsBitIndex=1, so what is the meaning of this then ......
bitWrite( arra[1/8] , edsBitindex % 8, bitRead(Store, i)) ;

And also after running the above code I just able to wrote first value....

I changed that later in the code sample. It should be

bitWrite( arra[edsBitIndex/8] , edsBitindex % 8, bitRead(Store, 7)) ;

arra[0/8] , arra[1/8] , arra[2/8] . . . arra[7/8] all resolve to arra[ 0 ] which is the first byte of the array. When edsBitindex gets to 8, that is you have filled the first byte, then you get the second byte : arra[edsBitIndex/8] = arra[8/8] = arra[ 1 ] and so it goes on. If the size of the array is 32 bytes, edsBitIndex goes from 0 to 255 to address each individual bit in the array.

Thanks alot for your time and guidence, It work :-)

ABDanyia:
Thanks alot for your time and guidence, It work :slight_smile:

I’m glad you got somewhere. I did a quick test myself and made one bug correction and added a binary print formatter:

byte edsBitindex = 0;
const byte encdataStoreSize = 32;
byte arra[encdataStoreSize] = {0};

void printBin( uint8_t Pbyte ) {
  // prints a byte in bit format. High order bit first.
   Serial.print( "0b" );
   for( byte i = 0; i < 8 ; i++ ) {
     Serial.print( bitRead( Pbyte, 7-i ) ) ; // high order bit (bit(7)) first
   }
}

bool storeEncodedValue (byte value, byte bitlength) {
  byte Store = 0;
  if ((edsBitindex + bitlength) < encdataStoreSize * 8) {
    Serial.print("adding ");
    Serial.print(bitlength );
    Serial.print(" bits from ");
    printBin( value ) ;
    Serial.println( );

    Store = value << (8 - bitlength);
    for (byte i = 0 ; i < bitlength; i++) {
      // copy high order bit from store into arra[] at the next free location
      // order: high order bit first in bytes in arr[] therefore: 7 - (edsBitindex % 8)
      bitWrite(arra[edsBitindex / 8] , 7 - (edsBitindex % 8) , bitRead(Store, 7 ));  // !!!!
      Store = Store << 1 ;   // moves the next bit into bit 7 of store for the next iteration.
      edsBitindex++;
    }
    // just for printing to get the first four bytes of arra[] out
    for ( byte i = 0 ; i < 4 ; i ++ ) {  // just print first 4 bytes
      printBin( arra[ i ] )  ;
      Serial.print("  ") ;
    }
    Serial.print("  edsBitindex= ") ;
    Serial.println(edsBitindex);
    Serial.println() ;
    return (true);
  }
  else
    return (false);
}





void setup() {
  Serial.begin( 115200 ) ;
  /*
    0 is represented by 00
    1 is represented by 10
    2 is represented by 11
    3 is represented by 010
    4 is represented by 011
  */

  // just to test
  storeEncodedValue( 0b00000000, 2 ) ;  // stores '0'
  storeEncodedValue( 0b00000010, 2 ) ;  // stores '1'
  storeEncodedValue( 0b00000011, 2 ) ;  // stores '2'
  storeEncodedValue( 0b00000010, 3 ) ;  // stores '3'
  storeEncodedValue( 0b00000011, 3 ) ;  // stores '4'
  storeEncodedValue( 0b00000000, 2 ) ;  // stores '0'
  storeEncodedValue( 0b00000010, 2 ) ;  // stores '1'
  storeEncodedValue( 0b00000011, 2 ) ;  // stores '2'
  storeEncodedValue( 0b00000010, 3 ) ;  // stores '3'
  storeEncodedValue( 0b00000011, 3 ) ;  // stores '4'

}

void loop() {
}

Yeah i noticed it but I will handle it, thanks alot again....

Hi, Sorry to bother you guys again, what if I have to put this bits in EEPROM memory directly rather then in arra[]??

You can't write bits directly into the EEPROM because it is byte addressable. But you have anyway your data packed into an array so just use EEPROM.put() and EEPROM.get() to store and retrieve the entire array. If you have a (large) external EEPROM and you don't have enough RAM to do the packing, then you have to use a small queue in RAM and load the EEPROM from the queue. Do the reverse for retrieving it. Simply turn arra[] into a queue / circular buffer.

Yeah, I am also doing the same thing to make a circular buffer and when it full the it simply write to EEPROM, but the problem is know that as the bits are random that some time it is 2 bits and some time 3 bits data
so let suppose the encdataStoreSize=2 so after edsBitindex=14 the 3 bits of data come then it didnt enter into the loop. SO I simply put this if statement.

if(edsBitindex==sizeof(arra)*8 || edsBitindex==(sizeof(arra)*8)-1  ||edsBitindex==(sizeof(arra)*8)+1 || edsBitindex==(sizeof(arra)*8)-2) {
  edsBitindex=0;
 }

But it effects the number of bits storing in the memory.

if ((edsBitindex + bitlength) < encdataStoreSize * 8) {
    Serial.print("...........");
    Store = value << (8 - bitlength);
    //Serial.println(Store,BIN);
    for (byte i = 0 ; i < bitlength; i++) {

      bitWrite(arra[edsBitIndex/8] , edsBitindex % 8, bitRead(Store, 7 )); // here arra[1] I used just to simple check if it add or not in
      // you want just bit 7 of store because you should now you shift Store again to get the next bit at position 7
      Store = Store << 1 ;   // moves the next bit into bit 7 of store for the next iteration.
      // first byte also bitRead(Store,i) having problem with it.
      Serial.println(arra[1], BIN);
      edsBitindex++;
      Serial.println(edsBitindex);

    }
    return (true);
  }
  else
    return (false);
}

Every bytes stores perfectly in the EEPROM memory but the last byte of the circular buffer did not store fine having some bit missing and then all the values got misplaced and not stored properly.