How can I minimize memory usage in my table-based statemachine with several hundred states?

arnold_w

I am working with an ARM microcontroller and I have kind of a statemachine with several hundred states. In order to be able to overview it, I have written the code so that it has a 1:1 correspondence with a flowchart specification. I have removed irrelevant code, but basically the code works like this:

Bool_t (*returnTrueOrFalseFunctionPtr) (void);
void (*actionFunctionPtr) (int);

struct myStruct_s {
returnTrueOrFalseFunctionPtr trueOrFalse;
struct myStruct_s* whereToGoIfTrue;
struct myStruct_s* whereToGoIfFalse;
actionFunctionPtr actionsToPerformInThisState[5];
int actionArguments[5];
};

static struct myStruct_s myStateMachine1[];
static struct myStruct_s myStateMachine2[];
static struct myStruct_s myStateMachine3[];
static struct myStruct_s myStateMachine4[];

define myStateMachine1 ms1
define myStateMachine2 ms2
define myStateMachine3 ms3
define myStateMachine4 ms4

static struct myStruct_s myStateMachine1[] = {
{evaluateSomething, &ms1[1], &ms1[3], {startMotor,increaseSpeed, NULL, NULL, NULL, 3,5, 0, 0,0},
{evaluateSomething, &ms1[2], &ms2[0], {stopMotor, openExhaust, decreaseSpeed,NULL, NULL, 1,20,13,0,0},
{evaluateSomething, &ms1[0], &ms1[2], {openRelay, writeStatusToLog,increaseSpeed,NULL, NULL, 4,5, 87,0,0},
{evaluateSomething, &ms1[4], &ms2[1], {blah blah blah... },
{evaluateSomething, &ms2[1], &ms2[2], {blah blah blah... },
};

struct myStruct_s myStateMachine2[] = {
{evaluateSomething, &ms2[1], &ms2[3], { blah blah blah... },
{evaluateSomething, &ms2[2], &ms3[0], { blah blah blah... },
{evaluateSomething, &ms3[1], &ms3[3], { blah blah blah... },
{evaluateSomething, &ms2[4], &ms4[1], { blah blah blah... },
{evaluateSomething, &ms4[0], &ms2[2], { blah blah blah... },
};

I am very happy with this code format, it make it very easy for me to follow where I am in the statemachine/flowchart and decide where to go next. My problem is that I need to port this code to a microcontroller that has little memory, so I would like to memory-optimize the code heavily. I have already replaced my action function pointers with an enum instead:

enum actionsToPerformInThisState_e {
startMotor_,
stopMotor_,
openRelay_,
openExhaust_,
writeStatusToLog_,
decreaseSpeed_,
increase

Lost User

Can the actionArguments have a narrower type? Maybe 5 chars instead of 5 ints? The next-state pointers could be integers that index into the array of states instead of direct pointers, that would probably allow them to be uint16_t. Maybe the pointer to the true/false function can be an enum too?

arnold_w

harold aptroot wrote: Can the actionArguments have a narrower type? Maybe 5 chars instead of 5 ints? No, actionArguments can sometimes use 32 bits. harold aptroot wrote: The next-state pointers could be integers that index into the array of states instead of direct pointers, that would probably allow them to be uint16_t. But how would I index when the pointer is pointing to a different array? harold aptroot wrote: Maybe the pointer to the true/false function can be an enum too? Yes, of course, why didn't I think of that!

Lost User

arnold_w wrote:

actionArguments can sometimes use 32 bits.

OK. How often is that needed? Perhaps you can cheat a bit: allow only a couple of 32bit arguments, and the rest must be small. Then if one "block" of actions does need more 32bit arguments, it can be "split" into two successive states (which costs a lot of space, but if splitting is rare then it can be an overall win) Or maybe: pack arguments in [VLQ](https://en.wikipedia.org/wiki/Variable-length\_quantity), but reserve a fixed amount of space. When it doesn't fit, split the state.

The next-state pointers could be integers that index into the array of states instead of direct pointers, that would probably allow them to be uint16_t. But how would I index when the pointer is pointing to a different array?

OK maybe pack together two parts, some bits that indicate which array to look into, and some bits to indicate the index.

leon de boer

You can tighten the structure at the cost of a carry an action size count. However it does allow you to use the same actions blocks for multiple states. That may often happen in that you just have things like confirm yes/no actions. I also changed your pointer definitions to const as you are clearly going to have static tables and it will save compiler type casting errors. I assume you are going to do this .. see the C11 initializers at code end which uses the standard _countof to autosize the arrays. on GCC it's ARRAY_SIZE() but I hate the name so always define it _countof same as MSVC because it reflects better what it is IMHO.

typedef bool (*returnTrueOrFalseFunctionPtr) (void);
typedef void (*actionFunctionPtr) (int);

struct myAction_s {
const actionFunctionPtr actionToPerformInThisState;
const uint32_t actionArgument;
};

struct myStruct_s {
returnTrueOrFalseFunctionPtr trueOrFalse;
const struct myStruct_s* whereToGoIfTrue;
const struct myStruct_s* whereToGoIfFalse;
const uint8_t maxActionsInThisState; // Count of the actions in this state
const struct myAction_s* actionsListInThisState; // The action block pointer
};

static void SomeYesFunc (int) {

}

static void SomeNoFunc(int) {

}

static void SomePerhapsFunc(int) {

}

static bool truefalseFunc(void) {
return true;
}

/* ACTION BLOCK DEFINITIONS */
const struct myAction_s yesNoBlock[2] = { &SomeYesFunc, 1 , &SomeNoFunc, 2 };
const struct myAction_s yesNoPerhapsBlock[3] = { &SomeYesFunc, 1 , &SomeNoFunc, 2, &SomePerhapsFunc, 3};

/* ACTION STATE DEFINITIONS */
const struct myStruct_s nullState = { 0, 0, 0, 0, 0};
const struct myStruct_s yesNoState = { &truefalseFunc, &nullState , &nullState, _countof(yesNoBlock), &yesNoBlock[0] };
const struct myStruct_s yesNoPerhapsState = { &truefalseFunc, &nullState , &nullState, _countof(yesNoPerhapsBlock), &yesNoPerhapsBlock[0] };

In vino veritas