How do you implement a state machine in a micro?

Thread Starter

atferrari

Joined Jan 6, 2004
4,764
I am not C conversant; I do all in Assembly for 18F micros.

I've been thinking of implementing a basic elevator controlled by a micro.

After reading several articles and references, I see that a state machine is frequently (if not always) mentioned what I understand is the way to consider the problem.

I then browsed two pieces of software implementing the basics (I regret losing track of them) and depending if written in (maybe) C or Assembly, what they did was implementing long blocks of "switch case" chains or something similar to this in Assembly:

Code:
  SKIP_IF_DIFFERENT,B'01111000'
  BRA COMB_CASE_C7_R3

  SKIP_IF_DIFFERENT,B'01110010'
  BRA COMB_CASE_C7_R1

  SKIP_IF_DIFFERENT,B'10111000'
  BRA COMB_CASE_C6_R3

  SKIP_IF_DIFFERENT,B'10110010'
  BRA COMB_CASE_C6_R1

  and so on  ------------------------------------------------
Found this quite a crude way to implement it but I cannot see other way of doing it.

My question: is this the actual way you implement a state machine with a micro?
 

Papabravo

Joined Feb 24, 2006
21,159
The basic idea is to keep track of the current state. How you keep track of the current state can be as simple as a short integer with only a couple of values. The set {0, 1, 2, 3} for example. Another way to keep track of the current state is to have a set of pointers to processing routines. Then you pick up the state variable and call the routine located in the memory location it points to. This is easier to do on some processors than others. You can also use a level of indirection, where the state counter is a small integer that indexes a table of pointers to functions.

Each of the functions that you get to is responsible for examining the input variables and computing two functions. One function is the output function and the other function is the next state function. Each function returns to the control loop which examines the current state and dispatches to the appropriate routine. Wash, Rinse, and Repeat.
 

jpanhalt

Joined Jan 18, 2008
11,087
Hi Agustin,

Last year I was doing a stepper using ASM and came across the attached code in AN906B from Microchip. It is a bit hard to link to. If you go to MCC and search on AN906B, then download the zip file, that is it. I have uploaed that file as a text file, as some people refuse to download zip files. I ended up using a slightly different method to drive the stepper, but at least this is an example of a state machine.

What I ended up doing was like JohnP suggested, a computed go to and table.

John
 

Attachments

JohnInTX

Joined Jun 26, 2012
4,787
On the 18F, I use the stack and tables of re-entry addresses instead of computed gotos.

A one byte state indicator is used.

A task is composed of many states. It never waits. If timing is necessary it uses an interrupt driven timer. Each state represents exactly ONE unique condition that the task can be in. Once there, the state examines that condition (inputs, timer etc.) to see if it's in the same state. If something changes and it needs to go to another state, it jumps to the Init point of the new state.

A 'state' has 3 basic parts:
Init: The entry point. Executes once per entry to the state. Does any setup required - sets a timer, turns on IO etc. It also loads the state with its state number so that it will know how to get back.
re-entry: Each time the state machine gets scheduled, the state number is used to compute this address and the processor jumps here. The code here examines the timers, inputs etc. that define the state (i.e. wait here for 3 seconds OR until RA5 is low). If the 'stay' conditions are satisfied, it exits the state machine and returns to the scheduler (maybe there are several tasks going). If the 'stay' condition is NOT satisfied, its time to change state. It figures out what state is next and jumps to the Init point of that state.

The state lookup works like this:
A table in ROM is generated with the addresses of the re-entry points for all of the states in the task.
When its time to renter a state, the state number is read, multiplied by the size of the table entry and added to the base address of the table to locate the entry. This arithmetic is done in TBLPTR.
PUSH the stack and using table reads, copy the table entry (the re-entry address) of the state onto the top of the stack.
Do a RETURN to do the jump.

Computed gotos work OK in the 18F but I like this way because there is no restriction on where the re-entry table is located nor its size (within reason). The lookup code does not have to be co-located with the table. You also don't have to maintain PCLATU/H nor bugger with PCL. Those ops can be a little dicey on the 18F IIRC. No worries on interrupts either.

I'm lazy so once I figured it all out I wrote macros that automate the process. They also inspect the state number to see if its in range.

I use state machines extensively in all my PIC programming. If you take the time to get up to speed on a method that suits you, you'll be happy at how easy coordinating lots of things at once becomes.

Have fun.
 

WBahn

Joined Mar 31, 2012
29,978
I am not C conversant; I do all in Assembly for 18F micros.

I've been thinking of implementing a basic elevator controlled by a micro.

After reading several articles and references, I see that a state machine is frequently (if not always) mentioned what I understand is the way to consider the problem.

I then browsed two pieces of software implementing the basics (I regret losing track of them) and depending if written in (maybe) C or Assembly, what they did was implementing long blocks of "switch case" chains or something similar to this in Assembly:

Found this quite a crude way to implement it but I cannot see other way of doing it.

My question: is this the actual way you implement a state machine with a micro?
It's crude, but pretty easy to implement and maintain. For small state machines that don't need to run particularly fast, this is a common way to do. As the machine gets larger, however, it gets harder to maintain and also gets slower because finding the code that needs to be executed is O(n) time where n is the number of states.

Using the other approaches generally require more time up front to get organized and may, depending on the MCU architecture, require more code. But finding the code to execute for a given state is O(1), hence independent of the number of states. That is a pretty compelling advantage in many implementations.
 

Thread Starter

atferrari

Joined Jan 6, 2004
4,764
Thanks to all that replied

After rereading about FSM, (focused on an elevator case because it is complex enough to show where I am lost), I cannot make my mind about this :

Let us say there is a total of 16 (external) buttons to call the elevator, plus another 14 (internal) ones inside plus 16 sensors of various kinds, all of them with two possible states. Are we talking of a binary value of 46 bits? And a FSM with 92 valid states?

I need to find a way to understand:

How to express all meaningful states of my FSM. Should I expect 92?

The state diagram of a turnpike seems a safe place for those explaining this because it offers no chances of confusion. But what my about FSM?

The one-byte indicator (JohnInTX) or the short integer (PapaBravo) should be in fact that 46-bit value above in my case?

Not making head and tails of the basics, I know. I believed I could do it alone...but no. Bear with me.
 

JohnInTX

Joined Jun 26, 2012
4,787
I would want to break it down into functional blocks. First, consider the elevator car and what states it can be in. A first order description might be
State 0 : stopped, door open at target floor
State 1 : stopped, door closed - examine target floor to see if its above, below or current floor.
State 2: rising towards target floor
State 3: descending towards target floor
There will be more states e.g. door closing, door opening, etc. Note that we just say 'target floor' without looking at buttons yet. We have described a simple elevator with 4 states. The buttons/limit switches/motor controls are deferred. You should be able to sketch a quick state diagram from this.

Things like buttons, limit switches are processed separately from the elevator car FSM - how they work is not important to the car, just that a target floor is commanded to the car and it follows its instructions. The button processor is its own little deal. It scans the buttons and issues direction-sensitive target info to the car which follows the instructions using its 'simple' logic. One implementation might have the button processor maintain a list of floors to visit on the ascent and another on the descent.

Like the car FSM, the lift is a separate FSM that takes commands from the car and operates the motors with the limit switches etc. These commands could be something like 'go to floor 6 and stop' or be broken down to finer detail. The motor FSM would go through all of the things is has to do to move the car - close the door (or ensure that someone else did it), start the motor, watch the floor indicator, stop the motor etc.

As you break things down, you'll be able to determine what function gets done where. In my haste, I've unintentionally blurred the car and lift functions. That would have to be sorted out. Maybe the car IS the motor function.. But the concept is valid. The complex logic gets done multiple FSM's to segregate functions and reduce them to something manageable. When its done, you'll have several FSM's that perform the various functions of the whole system, each operating by itself but taking / giving instructions to other functional blocks.

Don't worry if it seems overwhelming at first. In practice, it becomes kind of easy since you can work on one function while assuming the others will just do their specific jobs without worrying about how they do it.
 

John P

Joined Oct 14, 2008
2,025
It's crude, but pretty easy to implement and maintain. For small state machines that don't need to run particularly fast, this is a common way to do. As the machine gets larger, however, it gets harder to maintain and also gets slower because finding the code that needs to be executed is O(n) time where n is the number of states.

Using the other approaches generally require more time up front to get organized and may, depending on the MCU architecture, require more code. But finding the code to execute for a given state is O(1), hence independent of the number of states. That is a pretty compelling advantage in many implementations.
I suggested a method of implementing a state machine which involved adding to the program counter (PC register, in a PIC). This is a way to create a jump table that has the same execution time for every entry, but it will mess up execution to a serious extent if you make a mistake. My experience is that some compilers won't use it, and put in a long chain of tests instead. You can do it yourself in assembly, or possibly in C if you watch what the compiler does, but you need to be aware of all the states that may exist, and most likely every number will need an entry (i.e. you can't have 0, 1, 2, 4, 5 and miss out 3). And you absolutely must guard against the state ever being a higher number than the highest code you've provided for. You also have to be concerned about where the code you produce will be located in the executable file. That's why I added "If you dare" to the suggestion.
 

NorthGuy

Joined Jun 28, 2014
611
Typically, you would use state machines if you have many of them. If you only have one task, you just run it consecutively - no need for a state machine.

For example, in the elevator, every button would have it's own state machine reflecting button state including debouncing. A button would generate events, which would be used by other state machines to control their behaviour. Say, when the cabin approaches 17-th floor, you would want to know if button for the 17-th floor has been pressed and based on this it can alter the cabin state to stopping-at-the-floor or passing-the-floor-by.

Similarly, doors will have their own states, motor will have states etc.

Then you run your main loop where you process all these state machines in a loop. Working together, the state machines produce the desired behaviour.
 

Thread Starter

atferrari

Joined Jan 6, 2004
4,764
I would want to break it down into functional blocks.

The complex logic gets done multiple FSM's to segregate functions and reduce them to something manageable. When its done, you'll have several FSM's that perform the various functions of the whole system, each operating by itself but taking / giving instructions to other functional blocks.

Don't worry if it seems overwhelming at first. In practice, it becomes kind of easy since you can work on one function while assuming the others will just do their specific jobs without worrying about how they do it.
Instead of a monumental FSM, divide and conquer, so to speak. Definitely I was looking at the problem in a wrong way, John.

Then you run your main loop where you process all these state machines in a loop. Working together, the state machines produce the desired behaviour.
I initially discarded the idea of a main loop, with no reason.

Thanks to you both; things are starting to look that I could handle this.
 
Top