Efficiently storing a variable length array into static memory

Question

I'm working on an embedded system that requires some pre-determined data to be stored in memory for use at run-time. The data is essentially a large state transition table.

example: {1,2},{1,3},{2,3},{2,4},{2,5},{3,1}

Where: State 1 can go to state 2 or 3. State 2 can go to states 3, 4, or 5. State 3 only goes to state 1.

I'm currently using an "N" x 2 array - Where "N" is the maximum amount of transitions (in this case, 3).

This isn't space efficient, there is a lot of unused memory. From the example above, we'll have 2 unused allocations for State 1, and 4 unused allocations for State 3. The problem gets much more pronounced if one state has a lot more transitions then the rest.

My current implementation stores information as an array of structs, where the struct is of the form:

#define max_transitions 9
...
const struct state_table{
    uint16_t number;
    char len;
    uint16_t stt[max_transitions][2];
};

I then go on to define a pile of data:

#define MAX_STATES 619
const static struct state_table SUPERVISOR[MAX_STATES] = {
{1,6,{{301,2},{410,3},{411,4},{500,5},{501,6},{604,7}}},
...
{619,5,{{301,611},{401,297},{500,619},{501,619},{602,514}}}
};

First element is the current state, second is the length, third is an array for the STT.

Within the 619 states, there's about 10 states that have 9 transitions. The average transition length is 5, so this creates a huge memory waste with my current implementation.

Question: I'm looking for guidance on how I can make this more space efficient.

Thanks in advance,

Asking to make this more space efficient is a question for Code Review. — George Stocker
– George Stocker, Commented Jul 21, 2016 at 14:07
You always have to account for the worst case in embedded system, Even if you come up with some dynamic scheme, what will happen when you hit the worst case? You still need all of this memory. So keep it static. — Eugene Sh.
– Eugene Sh., Commented Jul 21, 2016 at 14:07
If you don't need a dynamic state machine; you'll be far better off including it in code. Here's the method I'm using currently, and it works rather well for my event driven embedded system: barrgroup.com/Embedded-Systems/How-To/… — George Stocker
– George Stocker, Commented Jul 21, 2016 at 14:12
There is no VLA, but a flexible array member. Your question is not clear. See How to Ask. — too honest for this site
– too honest for this site, Commented Jul 21, 2016 at 14:14
What is the largest value expected of N? 10: 100 619 1000 million? — chux
– chux, Commented Jul 21, 2016 at 14:18

Serge Ballesta · Accepted Answer · 2016-07-21 15:03:39Z

1

As said in comment, this does not use VLA. What you need is a struct where the last element is an array of unknown length. A simple way is to use pointers, but it forces you to split the initialization:

const struct state_table{
    uint16_t number;
    char len;
    const uint16_t (*stt)[2]; // pointer to arrays of size 2
};

const uint16_t tst1[][2] = {{301,2},{410,3},{411,4},{500,5},{501,6},{604,7}};
...
const uint16_t tst619[][2] = {{301,611},{401,297},{500,619},{501,619},{602,514}};

const static struct state_table SUPERVISOR[MAX_STATES] = {
{1,6,tst1,
...
{619,5,tst619}
};

In fact, this is like replacing a 2D array with an array of pointers to arrays, because the last element of your struct only points to other arrays.

edited Jul 21, 2016 at 15:03

answered Jul 21, 2016 at 14:48

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

too honest for this site Over a year ago

Ehm, no. That is a 2D array and a pointer to a 1D array which can be accesses as a 2D array. But it is not an array of pointers.

Serge Ballesta Over a year ago

@Olaf Oups... Edited... And thank you for noticing :-)

too honest for this site Over a year ago

Erm, the code is correct, just your explanation still is wrong. In fact, you use a pointer to 1D array, not an array of pointers (that would be const uint16_t *[2]). Do to rules of pointer arithmetic, you can treat it as an "array of array", aka 2D array.

Kevin Searle Over a year ago

This will do the trick. I wasn't sure how to phrase my question, but this is the solution! I'll modify my .py function to generate the code in this manner and suck it into my header files.

Ian Abbott · Accepted Answer · 2016-07-21 16:18:35Z

One possibility is to concatenate the stt members for each state into a shared array, and store a starting offset into this array for each state. The C code for this could be generated by an auxiliary program, or it could be written and maintained manually. If doing it manually, enumerated constants for the lengths and starting offsets would help to keep it maintainable. Here is an example:

struct state_table {
    uint16_t number;
    char len;
    uint16_t offset;
};

#define MAX_STATES 619

enum {
    /* number of transitions for each state */
    st_len_1 = 6,
    /* ... */
    st_len_619 = 5,
    /* starting index of transitions for each state */
    st_offset_1 = 0,
    st_offset_2 = st_offset_1 + st_len_1,
    /* ... */
    st_offset_619 = st_offset_618 + st_len_618
};

static const uint16_t TRANSITIONS[][2] = {
    /*1*/ {301, 2}, {410, 3}, {411, 4}, {500, 5}, {501, 6}, {604, 7},
    /* ... */
    /*619*/ {301, 611}, {401, 297}, {500, 619}, {501, 619}, {602, 514},
};

static const struct state_table SUPERVISOR[MAX_STATES] = {
    {1, st_len_1, st_offset_1},
    /* ... */
    {619, st_len_619, st_offset_619}
};

You can save a bit more space by omitting the len member from struct state_table and determining the number of transitions from the difference between offset members of consecutive elements of the SUPERVISOR array. This would require an extra, dummy element in the SUPERVISOR array to hold the terminating offset, and would require values of consecutive offset members to be strictly increasing.

struct state_table {
    uint16_t number;
    uint16_t offset;
};

#define MAX_STATES 619

enum {
    /* number of transitions for each state */
    st_len_1 = 6,
    /* ... */
    st_len_619 = 5,
    /* starting index of transitions for each state */
    st_offset_1 = 0,
    st_offset_2 = st_offset_1 + st_len_1,
    /* ... */
    st_offset_619 = st_offset_618 + st_len_618,
    st_offset_end = st_offset_619 + st_len_619
};

static const uint16_t TRANSITIONS[][2] = {
    /*1*/ {301, 2}, {410, 3}, {411, 4}, {500, 5}, {501, 6}, {604, 7},
    /* ... */
    /*619*/ {301, 611}, {401, 297}, {500, 619}, {501, 619}, {602, 514},
};

static const struct state_table SUPERVISOR[MAX_STATES + 1] = {
    {1, st_offset_1},
    /* ... */
    {619, st_offset_619},
    {0xffff, st_offset_end}
};

GroovyDotCom · Accepted Answer · 2016-07-21 14:45:34Z

0

How about:

FromState[0] = 0; // To States from 0 begin at index 0
FromState[1] = 3; // To States from 0 end at index 2

ToState[0] = 1
ToState[1] = 3
ToState[2] = 7

We quickly ascertain that state 0 can transition to 3 states 1,3,7.

answered Jul 21, 2016 at 14:45

GroovyDotCom

1,4042 gold badges16 silver badges29 bronze badges

Collectives™ on Stack Overflow

Efficiently storing a variable length array into static memory

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related