Go Down

Topic: More efficient data storage method (Read 1 time) previous topic - next topic

dirtshell

Hi, this might get a little mathy, so be warned.

Alright, I have to store a bunch of 12 bit values in an array. Currently, I am storing them as byte values. So I have an array sort of like this (this syntax may be wrong, but you will get the idea)

Code: [Select]

byte myArray[1000][12] =
{
     {                                                 // This is the first of the 1000 indexes
          {1,1,1,1,1,1,1,1,1,1,1,1}     // This takes up 12 bytes, but could be done in 2 bytes
     }
};


So obviously, I am wasting a ton of space (roughly 10 kb for this array alone). Keep in mind that I want to store a minimum of 8 of these arrays, so the wasted space really starts to add up. So I would like to store these numbers as efficiently as possible. This would require converting these 12 bit numbers to base 10, and storing them as ints (which only take up 2 bytes). Is there an easy way to convert these 12 bit numbers to ints, and vice versa?

Brief Overview of My Project:
Currently my project is made to cycle through this array and buffer each of the 1000 indexes. As the program is cycling through the array, it buffers out one of the 1000 indexes, waits 30ms, then buffers out the next one. When the buffer is sent out, it switches 12 digital pins (LOW or HIGH obviously), depending on which of 12 bits is high. Using this binary array makes it easy, but wastes space. If I stored each of the 100 frames as an int, I would have to convert each of these buffers from an int to the 12 bit version for switching the right pins. Also, this has to be done pretty quickly.

TLDR: I need to store  a 12 bit number as an int for maximum storage efficiency. Advice for quickly converting to and from the more efficient int data type.

Cookies

#1
Feb 13, 2013, 03:36 am Last Edit: Feb 13, 2013, 03:49 am by Cookies Reason: 1
You can use bit fields and unions like so -

Code: [Select]

typedef struct {
union {
int all;
bool bit1:1;
bool bit2:1;
bool bit3:1;
bool bit4:1;
bool bit5:1;
bool bit6:1;
bool bit7:1;
bool bit8:1;
bool bit9:1;
bool bit10:1;
bool bit11:1;
bool bit12:1;
};
} myStruct;

myStruct myArray[1000];

void myFunction()
{
myArray[42].bit2 = false;
myArray[3].bit6 = true;
myArray[1].all = 0; // sets all bits to 0
}


the :1 part indicates how many bits to use.


Or instead of bit fields, you could use bit shifts and masks (which is what bit fields already does, but has better compatibility with different systems/compilers etc)

Code: [Select]

int myArray[1000];

void myFunction()
{
bool val = getBit(43, 3); // get bit 3 of array index 43
setBit(56, 10, true); // set bit 10 of array index 56 to true
}

bool getBit(int idx, byte bit)
{
return (myArray[idx] >> bit) & 1;
}

void setBit(int idx, byte bit, bool set)
{
if(set)
myArray[idx] |= (1<<bit);
else
myArray[idx] &= ~(1<<bit);
}

Jack Christensen


Code: [Select]

byte myArray[1000][12] =


So obviously, I am wasting a ton of space (roughly 10 kb for this array alone). Keep in mind that I want to store a minimum of 8 of these arrays, so the wasted space really starts to add up.


You are aware of the SRAM limitations? An Uno has 2K, a Mega 2560 has 8K. Maybe consider a Due?
MCP79411/12 RTC ... "One Million Ohms" ATtiny kit ... available at http://www.tindie.com/stores/JChristensen/

pYro_65

Here is a link to my BitBool class, it manages an array of bit sized booleans.
Your 12000 bits will be a total of 1500 bytes.

http://arduino.cc/forum/index.php/topic,128407.msg965724.html#msg965724

pYro_65


You can use bit fields and unions like so -

Code: [Select]

typedef struct {
union {
int all;
bool bit1:1;
bool bit2:1;
bool bit3:1;
bool bit4:1;
bool bit5:1;
bool bit6:1;
bool bit7:1;
bool bit8:1;
bool bit9:1;
bool bit10:1;
bool bit11:1;
bool bit12:1;
};
} myStruct;



That struct is not standard, nor will it do what you want.

The union members are all physically starting at the same location. ( bit8, bit12, bit1 are all the same bit. ) The only way to modify all the data is using the int 'all'

What you may mean is something like this:

Code: [Select]

typedef struct {
union {
int all;
struct{
bool bit1:1;
bool bit2:1;
bool bit3:1;
bool bit4:1;
bool bit5:1;
bool bit6:1;
bool bit7:1;
bool bit8:1;
bool bit9:1;
bool bit10:1;
bool bit11:1;
bool bit12:1;
} bits;
};
} myStruct;


Also, bool is not suitable for a bit field type, only a variant of 'int' is standard.

liudr

Are you using this array to vary light patterns? Are there any way to calculate these patterns out or ways to indicate that there is some repeating patterns to shorten the array? This is read only?

CrossRoads

So why not just create it as int
Code: [Select]

int myArray[1000] =
{
     {                                                 // This is the first of the 1000 indexes
          B0000111111111111,    // This takes up 12 bytes, but could be done in 2 bytes  0x0FFF
          B0000101010101010,    // 0x0AAA
          B0000010101010101,    // 0x0555     
// etc.
     }
};

If they are fixed patterns, store them in PROGMEM
If they will be updated, consider using Atmega1284P with its 16K of SRAM
Bare boards available for $6 mailed to US locations
Designing & building electrical circuits for over 25 years.  Screw Shield for Mega/Due/Uno,  Bobuino with ATMega1284P, & other '328P & '1284P creations & offerings at  my website.

PeterH


Alright, I have to store a bunch of 12 bit values in an array.


Given the quantity of data you're dealing with, I guess space will be an issue. In that case you can reduce the space requirements significantly by not storing the values in whole bytes. If you store each value in one and a half bytes, the code to read and write these values to a byte array is relatively simple. You will have some non-obvious data to generate, but I assume you're generating it programmatically anyway so you would implement the 'write' part of your algorithm ion the generator.
I only provide help via the forum - please do not contact me for private consultancy.

michinyon

Quote
I have to store a bunch of 12 bit values in an array. Currently, I am storing them as byte values.


12-bit values won't fit into a byte.     12 single-bit values won't fit into a byte either.

billroy

Perhaps instead of:
Code: [Select]
byte myArray[1000][12] =
{
     {                                                 // This is the first of the 1000 indexes
          {1,1,1,1,1,1,1,1,1,1,1,1}     // This takes up 12 bytes, but could be done in 2 bytes
     }
};


…you could represent the table like this:
Code: [Select]
int myArray[1000] =
{
          0b111111111111,     // This takes up 2 bytes
          ...
};


This is a simple (but large) text edit of what you've already done.

Next, go read up on bitRead and bitWrite and use them to access the bits of your shiny new integer bit patterns in the table.  Something like this:
Code: [Select]

          digitalWrite(leds[3], bitRead(myArray[i], 3);  //... to read the fourth bit


-br


dirtshell

Jeeze, this blew up while i was sleeping xD.

First: Thanks a ton for all the good ideas, I will get cracking on em
Second:
Quote
You are aware of the SRAM limitations? An Uno has 2K, a Mega 2560 has 8K. Maybe consider a Due?

Yeah, thats why I am asking xD. The values need to be dynamic, although I suppose I can jimmy in some way for me store it in PROGMEM. I am currently using a 2560, so I am wokring with 8K of SRAM, and 4K of EEPROM. I am going to also save these bit strings, so I need to save them with PROGMEM.

Quote
Here is a link to my BitBool class, it manages an array of bit sized booleans.
Your 12000 bits will be a total of 1500 bytes.

I am going to try this =). May hit you up for some help

liudr

If the numbers need to be dynamic, you can add a QuadRAM on your MEGA with up to 512KB space and load the initial values from PROGMEM.

https://shop.ruggedcircuits.com/index.php?main_page=product_info&cPath=4&products_id=50

Go Up