Demo finite state machines in em-forth - a battery charger .etc

CRW 9260 Crp

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.