Close

C labels as values for state machines

ken-yapKen Yap wrote 03/02/2021 at 22:18 • 1 min read • Like

My page on bitbanging a protocol made me think of how this might be implemented in C. Coroutines are not part of the C language (yet) so I thought about the approach of implementing the protocol state machine in a interrupt handler.

Normally you would do this with a combination of static variables (statics or globals) and a switch statement. However gcc has an extension for labels as values. Here's an example of the syntax:

#include <stdio.h>

int main(int argc, char **argv)
{
        void *ptr;

        ptr = &&here;
        goto *ptr;
here:
        printf("Labels here is at %p\n", ptr);
        return 0;
}

I would have to think a bit about what advantage, if any, this offers over a switch statement. One might be the ability to jump back into the middle of a loop to resume, which you cannot do with a switch statement, provided the loop variable(s) are in static storage.

Since the Arduino C compiler is avr-gcc, labels as values also work with it.

Like

Discussions

Paul McClay wrote 03/03/2021 at 17:09 point

Please pardon if this is a misfire - I haven't really read much of what you've got here.

Does https://github.com/bxparks/AceRoutine look relevant?

"This library is an implementation of the ProtoThreads library for the Arduino platform." ... "uses the computed goto feature of the GCC compiler (also supported by Clang) to avoid the Duff's Device hack"

The repo has recent activity.

No affiliation.

  Are you sure? yes | no

Ken Yap wrote 03/03/2021 at 20:47 point

Yes it certainly looks like I rediscovered an idea that has occurred to the author and been implemented. Thanks, that library could be useful.

  Are you sure? yes | no

Krzysztof wrote 03/03/2021 at 13:33 point

Switch statement is typically implemented as a list of if equals+jump, sometimes (eg for continuous enums) it's optimized with jump to offset in table + jump to code, which is much faster, but still two jumps. Your solution with labels is just one jump, but is it that much faster? Overall - nice solution.

  Are you sure? yes | no

Ken Yap wrote 03/03/2021 at 13:54 point

It's not the number of jumps as the fact that a goto can jump into the middle of a loop doing the bitbanging, provided the loop variables are static variables. (Possibly also block variables cannot be used.) With switch you have to re-establish where you were up to in the loop so it would have to be a deconstructed loop, not a standard loop because a switch cannot be interleave with a standard loop. The same issue happens with Protothreads; only deconstructed loops can be used.

  Are you sure? yes | no

Krzysztof wrote 03/03/2021 at 14:04 point

If you jump between blocks, you may have a bad time. If you jump between loops, you WILL have a bad time. If you don't keep structure provided by program, you have to keep that structure yourself, which is much harder. THAT's why "goto is considered harmful". If you can limit yourself to keep structure simple enough (keep it as simple as possible), you can typically use switch without much setup. Only then should you consider using gotos. Of course it's only if you want to write code where you can remember in half a year what it exactly does and how to modify it. If you need to do it very fast, you may try goto's or even raw asm.

Generally: mixing structure (loops) and gotos is recipe for errors. If you use gotos, don't use too much structure or loops. I say it after working with all of asm,goto'ish,structural,objective,functional code in my career. I've been there and seen things.

  Are you sure? yes | no

Ken Yap wrote 03/03/2021 at 14:38 point

Yes a friend of mine had the same knee-jerk response. Slogans are not helpful. analysis is. What you have to do is tame the construct. If the construct is too low level, then introduce macros or a preprocessor, similar to how compiler tools are used.

Nobody but you mentioned jumping between blocks. Jumping into loops is fine provided the state of the loop is retained and the compiler doesn't have different frame composition inside and outside the block.

I'll illustrate how you can transform a coroutine version of the state machine to one using this type of goto. Read to my previous page on bitbanging protocols, and remember this is not an idea to use in general programming but specifically for writing protocol state engines. And again, it's not about speed. Everywhere you see a coroutine yield, substitute with an assignment to the state variable with the next state, followed by a return, and then the label of the next state. Thus on the next time the handler is entered it will progress to the next state in the engine. So in fact this transformation is intended to retain the structure of the protocol in the code rather than in variables, contrary to what you thought. It is in fact intended to take pseudo code like this:

sendbyte:

send start

foreach bit in byte do

  send bit

end

send stop

And by inserting context switches after each state, ensure that the protocol is followed. And remember that each send of the start, stop, or bit usually means one data line set, and one clock line change.

  Are you sure? yes | no

Krzysztof wrote 03/04/2021 at 08:49 point

Sorry if it sounded knee-jerk. It WILL work and probably faster than other methods, it's just harder. Plus, it's a hack :)

  Are you sure? yes | no

Ken Yap wrote 03/04/2021 at 08:53 point

Writing state machines on top of interrupt handlers is never easy, but there is a long tradition of using tricky coding, as you can see from the links provided, both by me and others.

  Are you sure? yes | no