How do I write an efficient switch() in 8051 assembly?

Question

If I ever want to create a finite state machine in 8051 assembly, I'll need an efficient equivalent of C switch() expression.

[for this question, let us disregard the fall-through behavior, both retaining and dropping it is acceptable].

There are a few ways to achieve that in 8051 assembly, but each of them has their downsides. The ones for short switches of 5-10 cases are simple enough, and clear enough, but if I want a switch of >128, or even >256 cases, things get complicated.

The first one is simple, a chain of CJNE comparing the operand to values and jumping to next case if not equal; equivalent to if(){...}else if(){....} else if(){...}. The upside is simplicity, the downside is obvious: in case of a long switch this will create a very long string of choices. This can be reduced through building a binary tree, using JB for consecutive bits of the control variable. This is still not quite efficient, very hard to maintain and makes sparse keys set difficult to implement (`case 1:...; case 5:...; case 23:...; case 118:...)

Next approach is to multiply, then jump offset. Multiply the control variable by 2, load the result into DPTR, load the accumulator with an offset, then perform a JMP @A+DPTR into a zone preloaded with multitude of AJMP. (or multiply by 3 and jump into zone preloaded with multitude of LJMP. ).

I did that once. Adjusting locations of the jump instruction to the bytes was a puzzle I don't really want to repeat, plus the jump table is unnecessarily large (repeating ajmp each other byte). Maybe I don't know some trick that would make it easy...

And there's the approach to pull an address from a dedicated table, preload the stack and perform RET. It sounds very neat except pulling an address from a dedicated table needs to be done with the horrendous MOVC A, @A+DPTR or MOV A, @A+PC- these addressing modes make me wince so hard I never tried implementing it. If you know a neat way of doing this, please post that as an answer.

In general, I'd like to know if there's a more elegant, efficient way to perform a switch() style jump - one without creating too much overhead, not wasting too much memory and giving freedom of jumping at least AJMP distance, with number of cases going into hundreds.

Strohben

Look at how a compiler does it! If you pick a serious optimizing compiler, you'll find that it's very complex. You can have efficient or elegant, but not both. Why aren't you using C for this part of the code? – Salpingectomy

Answer 1

My second answer is another one you might not like.

Don't write this kind of thing in assembler! What are you hoping to achieve? Old age?

A state machine (perhaps for lexical analysis?) is exactly the sort of thing that generated code is for. Generated code is practically bug free, and much easier to maintain. There are good free tools available. The output of the code generator is usually nice, convenient C. You give the C to a compiler. And guess what, the compiler knows the answer to your question. A good compiler will know how to make the most efficient switch statement, and it'll just go ahead and get on with it without you wasting weeks of your life debugging it.

The other great thing is that, one day, when you decide an 8051 isn't powerful enough for you, you can trivially move to a more powerful architecture without having to totally re-write and debug the whole state machine from scratch! Plus, you won't be stuck working with 8051s for the rest of your life.

Added:

Since this isn't lexical analysis, I suggest you use a State Machine Compiler, like Ragel. You simply feed it a description of your state machine, and it generates your state machine C code.

Alternatively, try a logic grid approach.

Ashleighashlen

Lexical analysis? No. The state machine is essential for any control systems. State: opening valve. Possible transitions: valve open - filling; valve timeout - fault recovery; user abort - bring system back to 'safe' state. Meanwhile other tasks are active, so we can't just freeze awaiting one of the outcomes states. I might write it in a ladder language instead, and these are just as untransferrable as asm. – Strohben

Normally I write that in C or C++ (for "bigger" boards.) But I want to learn how to do it in '51 asm - or at least how it is done by the compiler. I don't think I'll ever write a finite state machine with more than 10 states for '51, but I want that to be because I don't need to, not because I can't. – Strohben

@Strohben - Fair enough. I'm glad that that's the case. But I think you've just answered your own question... – Ashleighashlen

Nope, I'd like to see neat snippets for the 2nd and 3rd option I presented (as opposed to my massacre), or something even more clever if it exists. – Strohben

@Strohben - What I meant was, if you want to learn how how the compiler does it, there's an easy way to find out. – Ashleighashlen

Probably... involves obtaining a compiler :) (haven't written a line of C for '51 in my life. Usually various ARMs). – Strohben

@Strohben Just download the gcc cross compiler for 8051, write your example in c and compile with the -S option and take a look at the resulting .s file. Alternately sdcc produces a .lst file of assembler. – Bonaventure

@SteveBarnes: There's no gcc for '51. :) But yes, SDCC would work. – Strohben

Answer 2

I am not normally a fan of this type of answer, but I feel it's appropriate here.

Don't do it! A very large switch statement is a code smell. It suggests that some poor planning has happened in your code somewhere, or some originally good design has grown out of control as the scope of the project has grown.

You should use a switch statement when you have a choice of several genuinely different options. Like this:

void HandleCommand(unsigned char commadndByte)
{
switch (commandByte)
{
        case COMMAND_RESET:
            Reset();
            break;

        case COMMAND_SET_PARAMETERS:
            SetPID(commandValue[0], commandValue[1], commandValue[2]);
            ResetController();
            SendReply(PID_PARAMETERS_SET);
            break;

        default:
            SendReply(COMMAND_HAD_ERROR);
            break;
    }

Does your switch statement really divert program flow to hundreds of genuinely different options? Or is it more like this?

void HandleCharacter(unsigned char c)
{
switch (c)
    {
        case 'a':    c='A';    break;
        case 'b':    c='B';    break;
        case 'c':    c='C';    break;
        case 'd':    c='D';    break;
        ...
        case 'w':    c='W';    break;
        case 'x':    c='X';    break;
        case 'y':    c='Y';    break;
        case 'z':    c='Z';    break;
    }
}

Whatever it is you're doing, it can probably be done better with an array of some sort. To save writing an answer in assembler, I'll write it in C, but the concept is the same.

If each case of the switch involves calling a different function, then:

const void (*p[256]) (int x, int y) = {myFunction0, myFunction1, ... myFunction255};

void HandleCharacter(unsigned char c)
{
    (*p[c])();
}

You might argue that the array of function pointers takes up lots of memory. If it's const, then it should only take up FLASH, nor RAM, and should take up way less FLASH than the equivalent switch statement;

Or, something like this might be more relevant. If each case of the switch involves assigning a different value, then:

char validResponses[256] = {INVALID, OK, OK, OK, PENDING, OK, INVALID, .... };

void HandleCharacter(unsigned char c)
{
    sendResponse(validResponses[c]);
}

In summary, try to find a pattern in your switch statement; what varies and what stays the same? Put what varies into an array, and what stays the same into code.

Ashleighashlen

The large switch with genuinely different options is the flesh of every finite state machine, and in cooperative multitasking, or an equivalent of RTOS written without actual OS, each task is a finite state machine. I know how to do look-up tables, or parametric executions; it's when you write large code where you need multiple different wait states (or heavyweight loops) and you're forbidden to create any actual wait state, or hog resources for extended period of time, an efficient switch becomes essential. – Strohben

(OTOH, you can create the finite state machine by loading the 'state' variable with address of the actual state procedure instead of just its identifier. That approach has its own range of problems, but at least the address lookup is skipped.) – Strohben

@Strohben - See my second answer. – Ashleighashlen