Pages: [1]   Go Down
Author Topic: More efficient data storage method  (Read 1004 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 38
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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.
Logged

UK
Offline Offline
Newbie
*
Karma: 0
Posts: 17
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

You can use bit fields and unions like so -

Code:
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:
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);
}
« Last Edit: February 12, 2013, 09:49:11 pm by Cookies » Logged

Grand Blanc, MI, USA
Offline Offline
Faraday Member
**
Karma: 95
Posts: 4095
CODE is a mass noun and should not be used in the plural or with an indefinite article.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Code:
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?
Logged

MCP79411/12 RTC ... "One Million Ohms" ATtiny kit ... available at http://www.tindie.com/stores/JChristensen/

North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 76
Posts: 2247
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged


North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 76
Posts: 2247
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

You can use bit fields and unions like so -

Code:
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:
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.
Logged


Central MN, USA
Offline Offline
Tesla Member
***
Karma: 76
Posts: 7305
Phi_prompt, phi_interfaces, phi-2 shields, phi-panels
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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?
Logged


Global Moderator
Boston area, metrowest
Offline Offline
Brattain Member
*****
Karma: 549
Posts: 27427
Author of "Arduino for Teens". Available for Design & Build services. Now with Unlimited Eagle board sizes!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

So why not just create it as int
Code:
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
Logged

Designing & building electrical circuits for over 25 years. Check out the ATMega1284P based Bobuino and other '328P & '1284P creations & offerings at  www.crossroadsfencing.com/BobuinoRev17.
Arduino for Teens available at Amazon.com.

UK
Offline Offline
Shannon Member
****
Karma: 223
Posts: 12630
-
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

I only provide help via the forum - please do not contact me for private consultancy.

Offline Offline
Faraday Member
**
Karma: 62
Posts: 3080
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

0
Offline Offline
God Member
*****
Karma: 39
Posts: 988
Get Bitlash: http://bitlash.net
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Perhaps instead of:
Code:
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:
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:
          digitalWrite(leds[3], bitRead(myArray[i], 3);  //... to read the fourth bit

-br

Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 38
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Central MN, USA
Offline Offline
Tesla Member
***
Karma: 76
Posts: 7305
Phi_prompt, phi_interfaces, phi-2 shields, phi-panels
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged


Pages: [1]   Go Up
Jump to: