Automatically generated state machines

Automatically generated state machine code

Although it may not seem obvious for a simple example, sometimes it gets very complicated to write the if-then-else state machine code by hand. Furthermore, it becomes difficult to optimize the source code (for speed and space) by minimizing the number of if-then-else statements performed. For these reasons, WhatOS includes tasks which can automatically generate the if-then-else statements from a given set of state transitions. Note that you do not need this functionality for the vast majority of simple tasks.

In this section we reimplement the SLIP receiver from the WhatOS Introduction using automatically generated state machine code. Let's draw the state transition diagram of a SLIP receiver. The nodes are the states and the edges are the conditions, as binary variable expressions which must evaluate to true for the transition to take place. Each binary variable can only be true or false and the allowable operators are the following: negation (~), or (|), and (&).

variable meaning

esc received byte ESC

end received byte END

esc_esc received byte ESC_ESC

esc_end received byte ESC_END

variable	meaning
esc	received byte ESC
end	received byte END
esc_esc	received byte ESC_ESC
esc_end	received byte ESC_END

How do you specify this state machine in WhatOS? The following file rewrites csliprx using whatos.core.cautotask:

slip2.py - pysliptx and automatically generated csliprx

Show code

Hide code

from slip1 import *
# we'll rewrite csliprx so let's delete the old one
del csliprx

# clone cautotask and customize
class csliprx(cautotask):
    packet = packet()
    wuint8 = wuint8()
    inbyte = input('inbyte', type = 'wuint8')
    outpacket = output('outpacket', type = 'packet')
    defines = {'OVERFLOW' : 10,
               'END' : END,
               'ESC' : ESC,
               'ESC_END' : ESC_END,
               'ESC_ESC' : ESC_ESC,
               # define condition variables
               'esc' : '(byte == ESC)',
               'end' : '(byte == END)',
               'esc_esc' : '(byte == ESC_ESC)',
               'esc_end' : '(byte == ESC_END)',
               # define state variables
               'state_0' : '(newstate & 1)',
               'state_1' : '(newstate & 2)'}
    process = """\
    static wuint8 state = idle;
    static packet * p;
    wuint8 byte;
    wuint8 newstate = state;

    byte = (wuint8) (unsigned int) inputval;
    await(-1);
    /* execute generated transition if-then-else statement */
    transition_code();
    reject();
    """
    # write transitions
    def idle_TO_idle(self):
        'end & ~esc'
        return """\
        goto accept_it;
        """
    def idle_TO_receiving(self):
        '~end & ~esc'
        return """\
        idle_to_receiving_esc:
        p = acquire(t_packet);
        if (!p) {
            TRACE1("rejecting byte -- no room for packet");
            await(0);
            require(t_packet);
            reject();
        }
        p->len = 0;
        if (byte == ESC) {
            newstate = receiving_esc;
            goto accept_it;
        }
        else {
            newstate = receiving;
            goto append;
        }
        """
    def idle_TO_receiving_esc(self):
        'esc'
        return """\
        goto idle_to_receiving_esc;
        """
    def receiving_TO_idle(self):
        'end & ~esc'
        return """\
        emit(outpacket, p);
        newstate = idle;
        goto accept_it;
        """
    def receiving_TO_receiving(self):
        '~end & ~esc'
        return """\
        goto append;
        """
    def receiving_TO_receiving_esc(self):
        'esc'
        return """\
        newstate = receiving_esc;
        goto accept_it;
        """
    def receiving_esc_TO_receiving__esc(self):
        'esc_esc & ~esc_end'
        return """\
        byte = ESC;
        receiving_esc_to_receiving:
        newstate = receiving;
        append:
        if (p->len == sizeof(p->data)) {
            MTRACEE(OVERFLOW);
            release(p);
            newstate = idle;
            goto accept_it;
        }
        p->data[p->len] = byte;
        p->len++;
        accept_it:
        state = newstate;
        accept();
        """
    def receiving_esc_TO_receiving__end(self):
        'esc_end'
        return """\
        byte = END;
        goto receiving_esc_to_receiving;
        """
    def receiving_esc_TO_idle(self):
        '~esc_end & ~esc_esc'
        return """\
        release(p);
        newstate = idle;
        goto accept_it;
        """

Hide code

Transitions are defined as methods named <from_state>_TO_<to_state>. Condition expressions are written as documentation strings of those methods. The action performed during the transition is returned by those methods. The resulting if-then-else statement containing the tests, transitions, and actions becomes a macro called transition_code(); you execute this macro in the task's process. Writing a python task using whatos.core.pyautotask is very similar.

Feature: Generate state machine code from state transition diagram.

Let's put these two tasks in a system:

system2.py - System made using slip2.py

Show code

Hide code

from slip2 import *

# clone system and customize
class system(system):
    # code to go in the header file (wossystem.h)
    header = """
    #define WOS_DBG_SIM          /* enable whatos simulation */
    #define WOS_ASSERT_INTERNALS /* enable catching internal errors */
    """
    # tasks
    pysliptx = pysliptx()
    # clone and customize csliprx, renaming inbyte to outbyte
    csliprx = csliprx(inbyte = csliprx.inbyte('outbyte'))
    # turn on printing of state transitions
    csliprx.transitions_viewer = transitions_printer(task = csliprx)

# specify number of units of packet and wos_Signal to allocate
system.wos_Signal.allocate = 10         # signal queue length = 10
system.packet.allocate = 2

Hide code

The two csliprx tasks - the original created using ctask and the new one created using cautotask - behave identically. However, there is a little more debugging information available in the cautotask version; as the following interactive session shows, you can trace state transitions inside an autotask:

$ wospython
>>> from system1 import *
>>> system.dllbuild()
>>> system.dllload()
>>> system.inpacket.emit([1, 2, 3])
inpacket([1, 2, 3]) -> pysliptx
outbyte(192) -> csliprx
Transition(csliprx): idle -> idle
outbyte(1) -> csliprx
Transition(csliprx): idle -> receiving
outbyte(2) -> csliprx
Transition(csliprx): receiving -> receiving
outbyte(3) -> csliprx
Transition(csliprx): receiving -> receiving
outbyte(192) -> csliprx
Transition(csliprx): receiving -> idle
outpacket([1, 2, 3]) -> environment


DOWNLOAD	CHANGES	SCREENSHOTS	DOCUMENTATION