The will come a time when you will want to make a device which you can kind of program or configure during runtime. This configuration or program will than be telling the microcontroller what to do, how to behave enabling you to change that behavior without reprogramming your PIC or even turn it off, all during runtime. We can kind of think about this as a basic interpreter of simple programs.
My goal was to have a state machine where each state has a set of conditions and depending on a those condition, actions can be executed.
The full implementation of the state machine can be found in the MCLIB: https://github.com/kubovy/mclib/blob/master/modules/state_machine.h, https://github.com/kubovy/mclib/blob/master/modules/state_machine.c.
Definition
Let’s define your state machine as a non-empty list (ordered set) of at states. A state is than defined as a non-empty list of evaluations. An evaluation is defined as a possibly empty list of conditions followed by a non-empty list of actions.
The state machine starts always with state 0. An evaluation process can be fired due to two possible events. First, state machine enters a new state. Second, an input value change happened.
Entering a state results into evaluation all evaluations in that state. An evaluation is considered true if all conditions in such evaluation are true. If an evaluation is true all actions marked to always execute will fire.
Changing an input value will result into evaluation of all evaluations in the current state. An evaluation is considered true if all conditions in such evaluation are true. If an evaluation is true all actions, both, marked to always execute and execute only on change, will fire.
Let’s start bottom-up, implementing the smaller building blocks and moving up to the larger ones. The first building block we need is a condition.
Condition
First we need to consider our inputs for a conditions. We only consider boolean values and we need to define how many of those we will need. To make it byte-friendly it should be a multiplication of 8. Worst case we don’t use all bits in the condition byte. Not all input values may be considered in a condition therefore we will also need some kind of a mask for each input.
This means that a single condition is represented by one value bit and one mask bit. If the mask bit is 0 than that input is not considered, if the mask bit is 1 than the value bit represents the expectation of the condition.
An example of 8 conditions in 2 byte (value and mask) where value 0, 2, 3 and 5 are expected to be true, value 4 is expected to be false, and values 1, 6, 7 are not considered:
0x2D 0x3D
0b00101101 0b00111101
40 value condition definition:
Cijk - condition k in evaluation j for state i
Mijk - mask k in evaluation j for state i
|BYTE0|BYTE1|BYTE2|BYTE3|BYTE4|BYTE5|BYTE6|BYTE7|BYTE8|BYTE9|
|C000 |M000 |C001 |M001 |C002 |M002 |C003 |M003 |C004 |M004 |
Action
We want actions to be able to fire anything. Therefore we define the action to hold dynamic amount of data. An action definition consist of device (1 byte), data length (2 byte), data (X bytes). In our example we define following devices (those can be changed based on your implementation):
- INPUT: 0x00 – 0x1F (32 inputs, R/O – not actionable)
- OUTPUT: 0x20 – 0x27 (8 output)
- WS281x: 0x28 – 0x47 (32 LEDs)
- LCD_MESSAGE: 0x50 (display message)
- LCD_BACKLIGHT: 0x51 (turn backlight on/off)
- LCD_RESET: 0x52 (reset display)
- LCD_CLEAR: 0x53 (clear display)
- …
- GOTO: 0x70 (transit to another state)
For example an action setting output 2 to 1:
0x21 0x01 0x01
or setting LED 5 to red color:
0x2D 0x04 0x01 0xFF 0x00 0x00
or showing “Hello World” message:
0x50 0x0B 0x48 0x65 0x6C 0x6C 0x6F 0x20 0x57 0x6F 0x72 0x6C 0x64
Action reference definition:
AHijl - action address high in evaluation j
ALijl - action address low in evaluation j
|BYTE0|BYTE1|BYTE2|BYTE3| ... |BYTE |BYTE |
|AAH0 |AAL0 |AAH1 |AAL1 | ... |AAHx |AALx |
Action definition:
ATx - action type
ALx - action data length
ALx - action data length
|BYTE0|BYTE1|BYTE2|BYTE3| ... |BYTEy|
|AT0 |AL0 |AD00 |AD01 | ... |AD0y |
|AT1 |AL1 |AD10 |AD11 | ... |AD1y |
|ATx |ALx |ADx0 |ADx1 | ... |ADxy |
Evaluation
In our example we will consider up to 40 input values which will result into 2 * 5 = 10 bytes (value and mask) conditions. This means that the fixed first 10 bytes of an evaluation are the condition.
Note: an evaluation with no conditions will also have this 10 bytes but all zeroes.
Since we need to enable simple jumping in the memory space and since an action may be called from different evaluations we will not list all actions here but just the 2 byte addresses where the actions reside. This way we keep our memory usage as low as possible (action reuse) and have a fix size per action (2 bytes). Following the 10 condition bytes the evaluation will have 1 byte defining the number of actions and 2 * (action count) bytes of action addresses. Since the number of actions is defined only by 1 byte a result of an evaluation may be up to 255 actions.
Evaluation definition:
Cijk - condition k in evaluation j for state i
Mijk - mask k in evaluation j for state i
ACij - evaluation action count
AHijl - action address high in evaluation j
ALijl - action address low in evaluation j
|BYTE0|BYTE1|BYTE2|BYTE3|BYTE4|BYTE5|BYTE6|BYTE7|BYTE8|BYTE9|
|Ci00 |Mi00 |Ci01 |Mi01 |Ci02 |Mi02 |Ci03 |Mi03 |Ci04 |M004 |
|ACi0 |
|AHi00|ALi00|AHi01|ALi01| ... |AHi0l|ALi0l|
| ... |
|Cij0 |Mij0 |Cij1 |Mij1 |Cij2 |Mij2 |C0ij3 |Mij3 |Cij4 |Mij4 |
|ACij |
|AHij0|ALij0|AHij1|ALij1| ... |AHijl|ALijl|
State
As already said a state is a list of evaluations. Therefore, due to jumping again, the first byte defines the number of evaluations in that state. This puts a limitation that a state may have up to 255 evaluations. Then the evaluation bytes follow as defined above.
State definition:
ECi - evaluation count for state i (j)
Cijk - condition k in evaluation j for state i
Mijk - mask k in evaluation j for state i
ACij - evaluation action count
AHijl - action address high in evaluation j
ALijl - action address low in evaluation j
|BYTE0|BYTE1|BYTE2|BYTE3|BYTE4|BYTE5|BYTE6|BYTE7|BYTE8|BYTE9|
|EC0 |
|C000 |M000 |C001 |M001 |C002 |M002 |C003 |M003 |C004 |M004 |
|AC00 |
|AH000|AL000|AH001|AL001| ... |AH00l|AL00l|
|C010 |M010 |C011 |M011 |C012 |M012 |C013 |M013 |C014 |M014 |
|AC01 |
|AH010|AL010|AH011|AL011| ... |AH01l|AL01l|
| ... |
|C0j0 |M0j0 |C0j1 |M0j1 |C0j2 |M0j2 |C0j3 |M0j3 |C0j4 |M0j4 |
|AC0j |
|AH0j0|AL0j0|AH0j1|AL0j1| ... |AH0jl|AL0jl|
| ... |
|ECi |
|Ci00 |Mi00 |Ci01 |Mi01 |Ci02 |Mi02 |Ci03 |Mi03 |Ci04 |M004 |
|ACi0 |
|AHi00|ALi00|AHi01|ALi01| ... |AHi0l|ALi0l|
| ... |
|Cij0 |Mij0 |Cij1 |Mij1 |Cij2 |Mij2 |C0ij3 |Mij3 |Cij4 |Mij4 |
|ACij |
|AHij0|ALij0|AHij1|ALij1| ... |AHijl|ALijl|
State Machine
Last and upper-most building block is the state machine. The 1st byte defines the state machine’s status. The 2nd byte defines the number of states in the state machine, limit the number of states in a state machine to 255. Next, a list of 2 byte addresses of starting points of each state follows. After which comes the 2 byte starting address of actions. Then come all the states as defined above. Then 2 byte action count followed by the actions themselves.
STA - status
STC - state count low
i - SCH << 8 | SCL - state count
SSH - state start high
SSL - state start low
ASH - action start high
ASL - action start low
ECi - evaluation count for state i (j)
Cijk - condition k in evaluation j for state i
Mijk - mask k in evaluation j for state i
ACij - evaluation action count
AHijl - action address high in evaluation j
ALijl - action address low in evaluation j
ACH - action count high
ACL - action count low
x - ACH << 8 | ACL - action count
AAHx - action address high
AALx - action address low
ATx - action type
ALx - action data length
ALx - action data length
|BYTE0|BYTE1|BYTE2|BYTE3|BYTE4|BYTE5|BYTE6|BYTE7|BYTE8|BYTE9|
|STA |STC |
|SSH0 |SSL0 |SSH1 |SSL1 | ... |SSHi |SSLi |
|ASH |ASL |
|EC0 |
|C000 |M000 |C001 |M001 |C002 |M002 |C003 |M003 |C004 |M004 |
|AC00 |
|AH000|AL000|AH001|AL001| ... |AH00l|AL00l|
|C010 |M010 |C011 |M011 |C012 |M012 |C013 |M013 |C014 |M014 |
|AC01 |
|AH010|AL010|AH011|AL011| ... |AH01l|AL01l|
| ... |
|C0j0 |M0j0 |C0j1 |M0j1 |C0j2 |M0j2 |C0j3 |M0j3 |C0j4 |M0j4 |
|AC0j |
|AH0j0|AL0j0|AH0j1|AL0j1| ... |AH0jl|AL0jl|
| ... |
|ECi |
|Ci00 |Mi00 |Ci01 |Mi01 |Ci02 |Mi02 |Ci03 |Mi03 |Ci04 |M004 |
|ACi0 |
|AHi00|ALi00|AHi01|ALi01| ... |AHi0l|ALi0l|
| ... |
|Cij0 |Mij0 |Cij1 |Mij1 |Cij2 |Mij2 |C0ij3 |Mij3 |Cij4 |Mij4 |
|ACij |
|AHij0|ALij0|AHij1|ALij1| ... |AHijl|ALijl|
|ACH |ACL |
|AAH0 |AAL0 |AAH1 |AAL1 | ... |AAHx |AALx |
|AT0 |AL0 |AD00 |AD01 | ... |AD0y |
|AT1 |AL1 |AD10 |AD11 | ... |AD1y |
| ... |
|ATx |ALx |ADx0 |ADx1 | ... |ADxy |
Implementation
First we define couple constants and structures as our data model/basis (for brevity header files are not included):
struct {
uint8_t count;
} SM_states = {0};
struct {
uint8_t id; // Current state (0xFF state machine did not start yet)
uint16_t start; // Starting address of current state.
uint8_t io[SM_PORT_SIZE]; // Stable state's data.
} SM_currentState = {0xFF, 0x0000};
struct {
uint16_t start; // Action's starting address.
uint16_t count; // Total number of actions.
} SM_actions = {0x0000, 0};
struct {
uint8_t target; // Target state (0xFF no target state)
uint8_t index; // Index on the path.
uint8_t path[0xFF];// Goto path for loop detection.
} SM_goto = {0xFF, 0};Initialization
Next we need to initialize our state machine by reading the memory and read some important information to enable fast navigation in the memory (e.g. current state start, status, states count, actions start address and actions count)
/**
* Initialization, needs to be called before state machine can be used.
*
* This also sets the "SM_status" depending on the memory content. If some data
* are wrong, e.g. no valid state machine was uploaded, the "SM_status" will be
* set to "SM_STATUS_DISABLED".
*/
void SM_init(void) {
SM_currentState.start = 0x0000;
// Reset current state.
for (uint8_t i = 0; i < SM_PORT_SIZE; i++) {
SM_currentState.io[i] = 0;
}
// 1st byte: Status (0x00 - Enabled, 0xFF - Disabled)
SM_status = MEM_read(SM_MEM_ADDRESS, 0x00, 0x00);
if (SM_status != SM_STATUS_ENABLED) {
SM_reset();
return;
}
// 2nd byte: Count of states (0-255)
SM_states.count = MEM_read(SM_MEM_ADDRESS, 0x00, 0x01);
if (((uint16_t) SM_states.count) >= (SM_MAX_SIZE - 2) / 2) {
SM_reset();
return;
}
// Start of actions start address.
uint16_t actionsStartAddr = ((uint16_t) SM_states.count) * 2 + 2;
if (actionsStartAddr >= SM_MAX_SIZE) {
SM_reset();
return;
}
// Actions start address (2 byte).
uint8_t regHigh = MEM_read(SM_MEM_ADDRESS, actionsStartAddr >> 8,
actionsStartAddr & 0xFF);
uint8_t regLow = MEM_read(SM_MEM_ADDRESS, (actionsStartAddr + 1) >> 8,
(actionsStartAddr + 1) & 0xFF);
SM_actions.start = ((regHigh << 8) | regLow);
if (SM_actions.start >= SM_MAX_SIZE) {
SM_reset();
return;
}
// Number of actions (2 byte).
regHigh = MEM_read(SM_MEM_ADDRESS, SM_actions.start >> 8,
SM_actions.start & 0xFF);
regLow = MEM_read(SM_MEM_ADDRESS, (SM_actions.start + 1) >> 8,
(SM_actions.start + 1) & 0xFF);
SM_actions.count = ((regHigh << 8) | regLow);
if (SM_actions.count >= SM_MAX_SIZE) {
SM_reset();
return;
}
}
Consistency check
To check consistency we need to be able to calculate the state machine’s memory usage and checksum:
/**
* Calculates State Machine's data length.
*
* @return Length in bytes.
*/
uint16_t SM_dataLength(void) {
uint8_t regHigh = MEM_read(SM_MEM_ADDRESS, 0x00, 0x00);
uint8_t regLow = MEM_read(SM_MEM_ADDRESS, 0x00, 0x01);
if (regHigh != SM_STATUS_ENABLED) return 0;
if (((uint16_t) regLow) >= (SM_MAX_SIZE - 2) / 2) return 0;
uint16_t actionsStartAddr = ((uint16_t) regLow) * 2 + 2;
if (actionsStartAddr >= SM_MAX_SIZE) return SM_MAX_SIZE;
regHigh = MEM_read(SM_MEM_ADDRESS, actionsStartAddr >> 8,
actionsStartAddr & 0xFF);
regLow = MEM_read(SM_MEM_ADDRESS, (actionsStartAddr + 1) >> 8,
(actionsStartAddr + 1) & 0xFF);
uint16_t actionsAddress = ((regHigh << 8) | regLow);
if (actionsAddress >= SM_MAX_SIZE) return 0;
regHigh = MEM_read(SM_MEM_ADDRESS, actionsAddress >> 8,
actionsAddress & 0xFF);
regLow = MEM_read(SM_MEM_ADDRESS, (actionsAddress + 1) >> 8,
(actionsAddress + 1) & 0xFF);
uint16_t actionCount = ((regHigh << 8) | regLow);
if (actionCount >= SM_MAX_SIZE) return 0;
if (actionsAddress >= SM_MAX_SIZE - (actionCount * 2)) return 0;
uint16_t lastActionAddr = actionsAddress + (actionCount * 2);
if (lastActionAddr >= SM_MAX_SIZE) return 0;
regHigh = MEM_read(SM_MEM_ADDRESS, lastActionAddr >> 8,
lastActionAddr & 0xFF);
regLow = MEM_read(SM_MEM_ADDRESS, (lastActionAddr + 1) >> 8,
(lastActionAddr + 1) & 0xFF);
if (((regHigh << 8) | regLow) >= SM_MAX_SIZE - 1) return 0;
uint16_t lastActionLengthAddr = ((regHigh << 8) | regLow) + 1;
regHigh = MEM_read(SM_MEM_ADDRESS, lastActionLengthAddr >> 8,
lastActionLengthAddr & 0xFF);
if (lastActionLengthAddr >= SM_MAX_SIZE - regHigh - 1) return 0;
return lastActionLengthAddr + regHigh + 1;
}
/**
* Calculates State Machine's checksum.
*
* @return Checksum.
*/
uint8_t SM_checksum(void) {
uint16_t address, length = SM_dataLength();
uint8_t regHigh, regLow, checksum = 0x00;
for (address = 0; address < length; address++) {
regHigh = address >> 8;
regLow = address & 0xFF;
checksum = checksum + MEM_read(SM_MEM_ADDRESS, regHigh, regLow);
}
return checksum;
}Evaluation
We also need the hearth of the state machine, the evaluation function:
void SM_evaluate(bool enteringState, uint8_t *newState) {
if (SM_status != SM_STATUS_ENABLED) return;
uint8_t regHigh = SM_currentState.start >> 8;
uint8_t regLow = SM_currentState.start & 0xFF;
uint8_t evaluationCount = MEM_read(SM_MEM_ADDRESS, regHigh, regLow);
uint16_t evaluationStart = SM_currentState.start + 1;
uint8_t gotoState = 0xFF;
for (uint8_t e = 0; e < evaluationCount; e++) {
bool hasConditions = false;
bool wasChanged = false;
bool result = true;
for (uint8_t c = 0; c < SM_PORT_SIZE; c++) {
uint16_t conditionStart = evaluationStart + c * 2;
regHigh = conditionStart >> 8;
regLow = conditionStart & 0xFF;
uint8_t cond = MEM_read(SM_MEM_ADDRESS, regHigh, regLow);
regHigh = (conditionStart + 1) >> 8;
regLow = (conditionStart + 1) & 0xFF;
uint8_t mask = MEM_read(SM_MEM_ADDRESS, regHigh, regLow);
if (mask > 0) hasConditions = true;
uint8_t changedMask = SM_currentState.io[c] ^ *(newState + c);
if (mask & changedMask) wasChanged = true;
result = result && ((cond & mask) == (*(newState + c) & mask));
}
uint16_t actionListStart = evaluationStart + SM_PORT_SIZE * 2;
regHigh = actionListStart >> 8;
regLow = actionListStart & 0xFF;
uint8_t actionCount = MEM_read(SM_MEM_ADDRESS, regHigh, regLow);
if (((hasConditions && wasChanged) || enteringState) && result) {
for (uint8_t a = 0; a < actionCount; a++) {
regHigh = (actionListStart + a * 2 + 1) >> 8;
regLow = (actionListStart + a * 2 + 1) & 0xFF;
uint16_t actionId = MEM_read(SM_MEM_ADDRESS, regHigh, regLow) << 8;
regHigh = (actionListStart + a * 2 + 2) >> 8;
regLow = (actionListStart + a * 2 + 2) & 0xFF;
actionId = actionId
| (MEM_read(SM_MEM_ADDRESS, regHigh, regLow) & 0xFF);
uint16_t actionAddrStart = SM_actions.start + actionId * 2 + 2;
regHigh = actionAddrStart >> 8;
regLow = actionAddrStart & 0xFF;
uint16_t actionAddr = MEM_read(SM_MEM_ADDRESS, regHigh, regLow) << 8;
regHigh = (actionAddrStart + 1) >> 8;
regLow = (actionAddrStart + 1) & 0xFF;
actionAddr = actionAddr
| (MEM_read(SM_MEM_ADDRESS, regHigh, regLow) & 0xFF);
uint8_t device = MEM_read(SM_MEM_ADDRESS, actionAddr >> 8,
actionAddr & 0xFF);
bool includingEnteringState =
(device & 0b10000000) == 0b10000000; // 0x80
if (!enteringState || !hasConditions || includingEnteringState) {
uint8_t actionDevice = device & 0x7F;
uint8_t actionLength = MEM_read(SM_MEM_ADDRESS,
(actionAddr + 1) >> 8,
(actionAddr + 1) & 0xFF);
uint8_t actionValue[SM_VALUE_MAX_SIZE];
for (uint8_t v = 0; v < actionLength; v++) {
if (v < SM_VALUE_MAX_SIZE) {
actionValue[v] = MEM_read(SM_MEM_ADDRESS,
(actionAddr + v + 2) >> 8,
(actionAddr + v + 2) & 0xFF);
}
}
if (actionDevice == SM_DEVICE_GOTO) {
gotoState = actionValue[0];
} else if (SM_executeAction) {
SM_executeAction(actionDevice, actionLength, actionValue);
}
}
}
}
evaluationStart = actionListStart + actionCount * 2 + 1;
}
// Update new state as stable state
for (uint8_t c = 0; c < SM_PORT_SIZE; c++) {
SM_currentState.io[c] = *(newState + c);
}
if (gotoState < 0xFF) {
bool loopDetected = gotoState == SM_currentState.id;
for (uint8_t i = 0; i < SM_goto.index; i++) {
loopDetected = loopDetected || SM_goto.path[i] == gotoState;
if (loopDetected) break;
}
if (loopDetected) {
MEM_write(SM_MEM_ADDRESS, 0x00, 0x00, 0xFF);
SM_reset();
if (SM_ErrorHandler) {
SM_ErrorHandler(SM_ERROR_LOOP);
}
} else {
SM_goto.path[SM_goto.index++] = gotoState;
SM_goto.target = gotoState;
if (SM_executeAction) {
SM_executeAction(SM_DEVICE_GOTO, 1, &gotoState);
}
}
} else {
if (SM_EvaluatedHandler) {
SM_EvaluatedHandler();
}
}
}Change check
Last, we need to periodically check if the inputs changed. The following function should be called periodically (e.g. by a timer):
/**
* State machine's periodical check should be called in a loop with timer
* using the TIMER_PERIOD period. It checks the current state, evaluates the
* state machine's conditions and executes corresponding actions.
*
* The periodical check uses SM_CHECK_DELAY to delay consecutive checks.
*/
void SM_periodicalCheck(void) {
if (SM_checkCounter > 0) {
SM_checkCounter--;
} else {
SM_checkCounter = SM_CHECK_DELAY;
if (SM_status == SM_STATUS_ENABLED
&& SM_getStateTo
&& (SM_goto.target < 0xFF || SM_currentState.id < 0xFF)) {
uint8_t newState[SM_PORT_SIZE];
SM_getStateTo(newState);
if (SM_goto.target != SM_currentState.id) {
SM_currentState.id = SM_goto.target;
uint8_t regHigh = (((uint16_t) SM_goto.target) * 2 + 2) >> 8;
uint8_t regLow = (((uint16_t) SM_goto.target) * 2 + 2) & 0xFF;
SM_currentState.start = MEM_read(SM_MEM_ADDRESS,
regHigh, regLow) << 8;
regHigh = (((uint16_t) SM_goto.target) * 2 + 3) >> 8;
regLow = (((uint16_t) SM_goto.target) * 2 + 3) & 0xFF;
SM_currentState.start |= MEM_read(SM_MEM_ADDRESS,
regHigh, regLow) & 0xFF;
SM_evaluate(true, newState);
} else if (SM_changed(newState)) {
SM_evaluate(false, newState);
}
}
}
}Conclusion
The full implementation of the state machine can be found in the MCLIB: https://github.com/kubovy/mclib/blob/master/modules/state_machine.h, https://github.com/kubovy/mclib/blob/master/modules/state_machine.c.