有限状态机的C语言实现

有限状态机FSM（Finite State Machine）思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。

它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，依据判断进入下一个状态，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。

有限状态机的思想为我们编写状态较为复杂的程序提供了很方便的解决方案。例如通过代码来反应小车的运动，首先小车启动是一个加速的状态，然后小车匀速运动一段距离是一个匀速的状态，最后小车停下来又是一个减速的状态。这就可以将这三个状态反应到代码上:

    enum
    {
        WATING,                //等待启动        
        STRAT,                //启动
        CONSTANT,            //匀速
        BRAKE，                //刹车        
    }CarState = WATING;        //初始状态为启动

    STATE_UPDATE()
    {
        switch(CarState)
        {
            case WATING:
                if(收到启动指令)
                {
                    CarState = START;
                }
                break;
            case START:
                velocity += delt_vel;
                if(velocity == 匀速行驶的速度)
                {
                    CarState = CONSTANT；   
                }
                break；
            case CONSTANT:
                distance += delt_distance;
                if(distance == 设定的匀速前进距离)
                {
                    CarState = BRAKE；
                }
                break；
            case BRAKE:
                velocity -= delt_vel;
                if(velocity == 0)
                {
                    CarState = WAITING;   
                }
        }   
    }

上面的代码就是通过switch——break结构实现了简单的状态机。这种方式简单小巧，也较为原始，在实际工程的运用中，状态复杂难以维护。

因此维护一个二维状态表，横坐标表示当前状态，纵坐标表示输入，表中一个元素存储下一个状态和对应的操作。这样通过状态表来引导状态切换，维护时状态间的转换更为清晰。下面的例程就是通过建立了2*2的状态表来实现不同状态的切换。

    char str[128] = "   ./a.out 100   200   ";
    int argc;
    char * argv[16];

    int i = 0;
    void act_save(void)
    {
        argv[argc++] = str + i;
    }

    void act_end(void)
    {
        str[ i] = '\0';
    }

    void act_null(void)
    {

    }

    int state_trans_table[2][2] =
    {
        { 0, 1 },
        { 0, 1 }
    };


    void (*act_table[2][2])(void) =
    {
        { act_null, act_save },
        { act_end, act_null }
    };

    int get_input_type(char c)
    {
        if (str[ i] == ' ')
            return 0;
        if (str[ i] != ' ')
            return 1;
        return 0;
    }

    void fsm(void)
    {
        int state = 0;
        int input = 0;

        while (str[ i])
        {
            /* get input char type 获取目前所在状态*/
            input = get_input_type(str[ i]);

            /* call action 执行该状态下的动作*/
            act_table[state][input]();
            
            /* transfer to next state 判断下个状态*/
            state = state_trans_table[state][input];

            /* get next input */
            i++;
        }
     
        return;
    }

    int main(void)
    {
        int i = 0;

        fsm();

        printf("argc = %d \n", argc);
        for (i = 0; i < argc; i++)
            printf("argv[%d] = %s \n", i, argv[ i]);

        return 0;
    }

在这个例程中还涉及到了基础地函数指针的使用，这个函数指针时很灵活有趣的，调用它可以非常方便地实现不同功能地触发。

这两个例程介绍了有限状态机的两种简单的实现方法，随着代码复杂度的提高，状态机思想一定会应用到更多方面。

公 号：知物电子

期待您的关注，更多技术分享等你来！