Demo finite state machines in em-forth - a battery charger .etc
January 2008
In the last few months I have been working part time on my first serious sam7 application. It is a motor controller to open our QUT solar observatory. Unfortunately, I am unlikely to publish detail here due to possible IP issues.
In order to demonstrate my implementation of FSM in forth I came up with the idea of making a simple charge controller using an olimex mt-256. This in not indented to be a practical project, very good chargers can be purchased for less than the cost of a mt-256. However there may be some experimenters who may find it useful.
The project or hack only needs a few components - as usual the magic happens in software.
Hardware.
The electronic hardware consists of a simple adjustable voltage divider feeding the DC/battery supply to pin 7 of the ADC (analog to digitial converter). You could make the hardware even simpler by using a fixed divider and calibrating in software.
There are many possible ways to do this. My way was to put a 5K trim-pot between the adc and earth - put a 20K resistor to battery positive and a 1 uF cap across the pot as a filter.
To play safe I also used a diode to feed the power into the board.
The charging current is switched using the on-board relay.
There was a tendency for the micro to crash when the relay switched state.
A 100uF cap across the relay contacts fixed this.
I'm currently using a small 14V plug pack (recycled cordless driver charger) as the power source.
My batteries are 4AH 12V SLA (sealed lead acid).
Software
The software is built around three separate FSMs which are called sequentially by the main program loop.
The main loop also checks for serial data.
The functions of the these FSMs is.
1 - Does the actual charge control. While charging it take a ADC reading every second and turns the relay on (the NC contact is used) when we reach the threshold (eg 13.8V).
Once the threshold has been reached it waits 30 seconds and resumes reading the ADC. If the voltage is below threshold if turns the relay off again and repeats the charging process.
2 - Controls the backlight. The light consumes a significant amount of power so we keep it off most of the time. This FSM just wait for a button press and lights the backlight for around 30 seconds.
3 - Blinks the LED. This FSM also reads the ADC and flashes the LED with a variable duty-cycle based on the battery voltage. As the battery charges the blinks become shorter. This feature doesn't work properly if the charger is running in serial-client mode. This is because of the high overhead in polling the server in the main loop.
There is also a simple data-logger. This is not a FSM. There is no benefit in using FSM for this.
The logger stores the battery voltage in a RAM array - the array is 2K values long and wraps when full.
FSM
Wikipedia have a page on FSM here.
A FSM doesn't let you do anything you couldn't do in standard forth or virtually any other language.
The FSM version could well be bigger and slower.
FSM however tends to be cleaner, easier to understand and debug, and more portable.
Each step of the FSM sequence tends to be short allowing a kind of fine-grained co-operative multitasking.
This example is fairly trivial and could be written just as well without FSMs. We only have a couple of states changing back and forth.
On the other hand my motor controller has 12 states and could have quite a few more when complete.
When using the "C" language a FSM is often implemented as a case statement.
The different states are defined as numerical constants and the programmer has to ensure they haven't doubled up etc.
If there are many states it takes a while just to jump to the correct routine.
Forth doesn't have a "case" structure.
My FSM is based around a jump table.
The state constants are automatically assigned starting with the value of one.
After the constants are defined the complier knows how big to make the table.
The table begins with a pointer to a state variable in RAM (the table may be in flash) then a series of pointers to the code to be executed for each state.
The high bit of the state variable is used to mark that the state has changed.
Entry action or Exit action
Entry action - Performing actions when entering a new state has the advantage that the action only needs to be defined once even if the state can be reached from many other states.
The downside is you may have to test whether the state is new each time you run the FSM state code.
Exit action - Performing actions when leaving a state avoid the "new" test but is more work and harder to maintain if the action needs to be modified. Defining the action as a single word make it easier though.
One way to get around this issue is to add extra states before any states which have multiple entry paths.
FSM forth extensions
To support the easy construction of FSM I've defined the number of forth words in the STATES.FTH (in the includes directory).
Here is a code fragment to illustrate.
DEFINE_STATES STATEDEF LEDON_STATE STATEDEF LEDOFF_STATE DEFINE_STATE_TABLE LED_SMT // Define local variables and code. VARIABLE LED-ALARM : LED-PREP LEDOFF_STATE LED_SMT CHANGESTATE ; etc etc.... LED_SMT LEDON_STATE INSERT_STATE LEDON-CODE LED_SMT LEDOFF_STATE INSERT_STATE LEDOFF-CODE
DEFINE_STATES - this resets the counter used by STATEDEF to one.
STATEDEF creates a constant using the next word in the line as the name with a value starting at one for the first definition after a DEFINE_STATES directive and incrementing by one for each new STATEDEF.
DEFINE_STATE_TABLE creates an empty state table
INSERT_STATE inserts an entry into the table, the state number and table address are on the stack and INSERT_STATE finds the code address of the word which follows.
The code to do the work is usually defined after the state constants are defined and before the table is filled.
Demo1 - not a FSM
// Demo1 - not using state machine. // flash led based on real timer - exit on button down // tested on olimex mt-256 SP! RUNTIME EMPTY HEX 4000 GETMEM DROP INCLUDE ..\include\IO.FTH INCLUDE ..\include\RTT.FTH VARIABLE ALARMTIME : GETBUTTON // mt -- buttons ; read mt-256 buttons PIO_PDSR @ 1B RSHIFT 1F XOR ; : RESETRTT // set up the real time timer RTTRSTBIT 20 + RTTMODE ! BEGIN RTTVAL @ 0= UNTIL ; : FLASHDEMO RESETRTT // set up the real time timer RTTVAL @ ALARMTIME ! // set initial alarm time BEGIN BEGIN ALARMTIME @ RTTVAL @ < // check real time timer UNTIL LEDON // turn led on. 40 ALARMTIME +! // set new alarm time BEGIN ALARMTIME @ RTTVAL @ < // check the real time timer UNTIL LEDOFF // turn led off. 200 ALARMTIME +! // set new alarm time GETBUTTON UNTIL // Repeat until button pushed. ; FLASHDEMO
This demo flashes a led, it uses the real time timer.
It is not a state machine.
This is fine if all you want to do is flash a led - real apps usually do a little more.
Demo 2 - a simple FSM in FORTH
// Demo2 - using a state machine in standard FORTH. // flash led based on real timer - exit on button down // tested on olimex mt-256 SP! RUNTIME EMPTY HEX 4000 GETMEM DROP INCLUDE ..\include\IO.FTH INCLUDE ..\include\RTT.FTH VARIABLE ALARMTIME VARIABLE STATE : GETBUTTON // mt -- buttons ; read mt-256 buttons PIO_PDSR @ 1B RSHIFT 1F XOR ; : RESETRTT // set up the real time timer RTTRSTBIT 20 + RTTMODE ! BEGIN RTTVAL @ 0= UNTIL ; : ONSTATECODE ALARMTIME @ RTTVAL @ < // check the real time timer IF 1 STATE ! // Change the state LEDOFF // turn led off. 200 ALARMTIME +! // set new alarm time THEN ; : OFFSTATECODE ALARMTIME @ RTTVAL @ < // check the real time timer IF 0 STATE ! // Change the state LEDON // turn led on. 40 ALARMTIME +! // set new alarm time THEN ; : RUNFSM STATE @ IF OFFSTATECODE ELSE ONSTATECODE THEN ; : FLASHDEMO RESETRTT // set up the real time timer RTTVAL @ ALARMTIME ! // set initial alarm time BEGIN RUNFSM // run one interation of the state machine GETBUTTON UNTIL // Repeat until button pushed. ; FLASHDEMO
Demo 3 - a simple FSM using my extensions
This demo also flashes a led and uses the real time timer.
It uses a state machine.
If the FSMs are fast and well behaved it is now trivial to run multiple tasks.
This demo uses standard forth with the state remembered in the variable "STATE".
Having only two states we just need to test if the state is zero to know where to branch.
The style is of the "exit actions" flavor.
// Demo3 - using a state machine in standard FORTH. // flash led based on real timer - exit on button down // tested on olimex mt-256 SP! RUNTIME EMPTY HEX 4000 GETMEM DROP INCLUDE ..\include\IO.FTH INCLUDE ..\include\RTT.FTH INCLUDE ..\include\STATE.FTH : GETBUTTON // mt -- buttons ; read mt-256 buttons PIO_PDSR @ 1B RSHIFT 1F XOR ; : RESETRTT // set up the real time timer RTTRSTBIT 20 + RTTMODE ! BEGIN RTTVAL @ 0= UNTIL ; DEFINE_STATES STATEDEF LEDON_STATE STATEDEF LEDOFF_STATE DEFINE_STATE_TABLE LED_SMT // Define local variable and code. VARIABLE ALARMTIME : LEDON-CODE ALARMTIME @ RTTVAL @ < // check the real time timer IF LEDOFF // turn led off. 200 ALARMTIME +! // set new alarm time LEDOFF_STATE LED_SMT CHANGESTATE // set state THEN ; : LEDOFF-CODE ALARMTIME @ RTTVAL @ < // check the real time timer IF LEDON // turn led on. 40 ALARMTIME +! // set new alarm time LEDON_STATE LED_SMT CHANGESTATE // set state THEN ; // Build table LED_SMT LEDON_STATE INSERT_STATE LEDON-CODE LED_SMT LEDOFF_STATE INSERT_STATE LEDOFF-CODE : FLASHDEMO RESETRTT // set up the real time timer RTTVAL @ ALARMTIME ! // set initial alarm time LEDOFF_STATE LED_SMT CHANGESTATE // set initial state BEGIN LED_SMT RUN_SM // run one iteration of the state machine GETBUTTON UNTIL // Repeat until button pushed. ; FLASHDEMO
This demo also flashes a led and uses the real time timer.
It uses a table driven state machine.
It is still an "exit actions" type.
Entry action
: LEDON-CODE LED_SMT ?NEWSTATE IF // Is this state new? LEDON // turn led on. THEN ALARMTIME @ RTTVAL @ < // check the real time timer IF 200 ALARMTIME +! // set new alarm time LEDOFF_STATE LED_SMT CHANGESTATE // set state THEN ; : LEDOFF-CODE LED_SMT ?NEWSTATE IF // Is this state new? LEDOFF // turn led off. THEN ALARMTIME @ RTTVAL @ < // check the real time timer IF 40 ALARMTIME +! // set new alarm time LEDON_STATE LED_SMT CHANGESTATE // set state THEN ;
This is the same as before except the action (turn led on/off) happens one iteration after the state changes. This is silly in this simple example but I think it is easier to understand complex systems in this format. That might just be the way my brain is wired.
In real applications there are likely to be multiple paths from one state to another.
For example you might have an error state which could have "come from" many possible places.
The states where the error was detected will have at least two "exit" paths.
Using ?NEWSTATE has a large cpu cycle overhead - the test happens frequently but only rarely executes the action.
Factorizing the exit action
DEFINE_STATES STATEDEF LEDON_STATE STATEDEF LEDOFF_STATE DEFINE_STATE_TABLE LED_SMT // Define local variable and code. VARIABLE ALARMTIME : LEDON-CHANGE LEDON // turn led on. 40 ALARMTIME +! // set new alarm time LEDON_STATE LED_SMT CHANGESTATE // set state ; : LEDOFF-CHANGE LEDOFF // turn led off. 200 ALARMTIME +! // set new alarm time LEDOFF_STATE LED_SMT CHANGESTATE // set state ; : LEDON-BODY ALARMTIME @ RTTVAL @ < // check the real time timer IF LEDOFF-CHANGE THEN ; : LEDOFF-BODY ALARMTIME @ RTTVAL @ < // check the real time timer IF LEDON-CHANGE THEN ; // Build table LED_SMT LEDON_STATE INSERT_STATE LEDON-BODY LED_SMT LEDOFF_STATE INSERT_STATE LEDOFF-BODY
One advantage of "entry" action is the action is defined in one place.
Using exit actions the action may be defined in many places.
The obvious work around is the define the action as a single word so any change to the action is made by editing that word.
Again the usefulness of this is lost in this trivial demo.
Imagine instead your application controls a machine. There might be twenty different places where as error condition can occur. For each error you may want to shut the thing down. If you've put the shut-down code in multiple places as exit action you've got a lot of editing to do if it needs to be changed.
It may sound obvious but if the shut down sequence is simple it is temping to duplicate it where needed instead of making it a word of its own.
I also use tables pointing to strings. The structure of the table in almost identical to the state table.
They start with an index into the array followed by a list of pointers.
STR_CODE_DEF, DEFINE_CODES, ?NEWCODE and DEFINE_STRING_TABLE are just aliases to STATEDEF, DEFINE_STATES, ?NEWSTATE and DEFINE_STATE_TABLE.
These tables were mainly intended for passing error information from the FSM to the higher level code.
In can be used for other messages.
A string table is defined like this.
DEFINE_CODES STR_CODE_DEF BLON_C STR_CODE_DEF BLOFF_C STRCONSTANT BLONSTR Back light on " STRCONSTANT BLOFFSTR Back light off " DEFINE_STRING_TABLE BL_STRINGS BL_STRINGS BLON_C BLONSTR INSERT_STRING BL_STRINGS BLOFF_C BLOFFSTR INSERT_STRING
To set the code to BLON (back liigth on) do this.
BLON_C BL_STRINGS CHANGECODE
To query if the code has changed and type the message if so - do this.
BL_STRINGS ?NEWCODE IF BL_STRINGS ."CODE CR THEN
Future work..
It could be very useful to have a variation of the FSM which allows instantiation.
That is - to be able to create many instances of a defined FSM.
This just means having separate state and local variables for each instance.
This might be a merging of FSM with OO.
One use for this is the creation of cellular automata.
Improved power usage.
In the above example the CPU runs flat out polling running the FSMs as often as possible. In a real world application the CPU might be sleeping as much as possible to save power. In this case running the main loop or running individual FSMs might be interrupt driven.
For the above example the CPU could sleep and be woken up by a timer interrupt. Most of the time the FSMs are simply waiting for time periods to elapse - there is no point is testing for this unless the timer has ticked.
Binaries and source for this demo are here
F174.bin is the binary for a v1.74 kernel which runs in flash.
charger1.bin is the working binary of the charger.