CODEWITHSUNDEEP
carrays
Kevin Searle
Kevin Searle

Reputation: 113

Efficiently storing a variable length array into static memory

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,

Upvotes: 3

Views: 142

Answers (3)

Ian Abbott
Ian Abbott

Reputation: 17413

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}
};

Upvotes: 1

Serge Ballesta
Serge Ballesta

Reputation: 148975

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.

Upvotes: 1

GroovyDotCom
GroovyDotCom

Reputation: 1374

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.

Upvotes: 0

Related Questions