Pages: [1]   Go Down
 Author Topic: More efficient data storage method  (Read 851 times) 0 Members and 1 Guest are viewing this topic.
Offline
Newbie
Karma: 0
Posts: 38
 « on: February 12, 2013, 09:10:47 pm » Bigger Smaller 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
Newbie
Karma: 0
Posts: 17
 « Reply #1 on: February 12, 2013, 09:36:52 pm » Bigger Smaller 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
Karma: 92
Posts: 3942
CODE is a mass noun and should not be used in the plural or with an indefinite article.
 « Reply #2 on: February 12, 2013, 10:19:36 pm » Bigger Smaller 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
Edison Member
Karma: 64
Posts: 2101
 « Reply #3 on: February 12, 2013, 11:54:21 pm » Bigger Smaller 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
Edison Member
Karma: 64
Posts: 2101
 « Reply #4 on: February 13, 2013, 12:06:35 am » Bigger Smaller 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
Tesla Member
Karma: 72
Posts: 7171
Phi_prompt, phi_interfaces, phi-2 shields, phi-panels
 « Reply #5 on: February 13, 2013, 12:08:28 am » Bigger Smaller 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
Brattain Member
Karma: 518
Posts: 26341
Author of "Arduino for Teens". Available for Design & Build services. Now with Unlimited Eagle board sizes!
 « Reply #6 on: February 13, 2013, 12:49:03 am » Bigger Smaller 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
Shannon Member
Karma: 222
Posts: 12534
-
 « Reply #7 on: February 13, 2013, 08:05:52 am » Bigger Smaller 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
Karma: 57
Posts: 2778
 « Reply #8 on: February 13, 2013, 08:08:31 am » Bigger Smaller 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
God Member
Karma: 39
Posts: 988
Get Bitlash: http://bitlash.net
 « Reply #9 on: February 13, 2013, 08:16:34 am » Bigger Smaller Reset

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:

-br

 Logged

Offline
Newbie
Karma: 0
Posts: 38
 « Reply #10 on: February 13, 2013, 12:32:59 pm » Bigger Smaller 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
Tesla Member
Karma: 72
Posts: 7171
Phi_prompt, phi_interfaces, phi-2 shields, phi-panels
 « Reply #11 on: February 13, 2013, 01:21:20 pm » Bigger Smaller 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