Tuesday, March 9, 2010

New Unoriginal Idea

I don't think that I learn much at my job, but I was surprised the other day to learn something new about microcontrollers. Well, coding in general anyhow. You see, when working with microcontrollers I use a finite state machine to control program execution. No, wait, what does that mean? That's technical gobbledy gook. It means that I have a variable and I define a bunch of different values it can take. When my program starts it goes into INITIALIZE mode and it initializes stuff. Then when its done I usually put it into IDLE where it doesn't do much of anything and usually waits for user input like a button press or something. Then depending on what happens I put it into other modes like DO_STUFF_1 or DO_STUFF_2. Different events can change the mode it's in and that produces different behaviors. The idea is that it will be a nice and orderly flow from one mode to the next and that depending on what mode you're in you won't handle certain inputs, or you'll handle them differently. The goal is predictable behavior.

But microcontrollers are anything but predictable. You see, there's these awful things called interrupts. They are what they sound like - they interrupt your program and do something else. They happen usually when hardware has done something - say a button has been pressed. When that happens, whatever you were doing previously stops and this new code executes. That's not usually so bad, but you almost always want to change the mode you're in based on what happens in that interrupt. Okay, so change the mode. Fine, whatever. I don't care.

Except I obviously do. This might happen:

CODE ALERT! CODE ALERT!

do_special_stuff_for_different(modes)
{
mode1:
easy_command();
easy_command();
---OOOOPS INTERRUPT HAPPENED HERE!----
change_mode_to(mode2)
---INTERRUPT OVER BYE BYE NOW!--------
command_that_checks_mode(); //Oops, doesn't run, wrong mode!
command_that_depends_on_the_above(); //fails, above didnt' run!
...
} //Always close your braces!

You see what happens there. Ideally, you want all the commands for a mode to run regardless of whether the mode changes halfway through.

This can be done. Just use a queue data structure to change the mode. A queue is a list of things. I can put things into the back end and take things out of the front. So when I want the mode to change, I can just put the new value for mode into the queue and then handle it in one and only one place in the program:

is(empty(mode_queue))
{
no:
mode =new_mode_from_the(mode_queue);
yes:
//Do nothing!
}
do_special_stuff_for_different(modes)
{
mode1:
easy_command();
...
}

So you only change the mode before you handle events for that mode, and never while you're handling them. This eliminates confusion for the poor code.

But, my unoriginal idea improves this - I think. Say that you're in MODE1 and you have an interrupt that wants to change the mode to MODE2. Ok, it puts the new mode into the queue and we'll handle it when the time comes. But now, before it can be handled you get another interrupt that tries to change the mode to MODE3. Well, put it in the queue and we'll handle it. When everything is said and done, you have the mode change from MODE1 to MODE2 to MODE3 right after one another. It seems OK, but wait! When we designed the system, we never intended to move from MODE2 to MODE3 because in MODE2, we set things up to get ready for MODE4 which we intend to follow MODE2 directly. But that doesn't happen. When you're in MODE2 you try to put MODE4 on the queue, but it gets in line behind MODE3. And meanwhile, if MODE3 attempts to put MODE5 next, it also fails. So you've got two different things trying to happen in sequence at the same time.

It might work, but it might not. We intended in our design to move right from MODE2 to MODE4 but we didn't do anything to ensure that it actually would. That's where my unoriginal idea comes in. These modes are stored on a microcontroller. That means they're stored with bytes, and bytes are made of bits - eight of them to be precise. Eight bits can store 256 different modes if you encode it that way, or it can store eight if you use something called one-hot encoding. One-hot encoding means that only one bit is ever a '1' at a time - the rest are zeros. Wherever the '1' is determines what the value is.

So, when we want to change modes we don't put the next mode we want to move to into the queue, we XOR the current mode with the next mode and put that into the queue. The XOR operation works on bits and it says if two bits are the same, the outcome is zero. If they're different, the outcome is 1. Since all of our modes are encoded with one-hot encoding, there shouldn't be any same bits. Wherever there was a one in either of the modes' bytes, there will be a one in the resulted XOR'd byte. Using this method we don't only record the next mode we want to go to, but we record the mode the program was in when it wanted to go there. It says 'I want to go from MODE2 to MODE4' instead of 'I want to go to MODE4'. Then, when it comes time to look at the queue and change the mode, we can make a better decision. If the request is 'I want to go from MODE2 to MODE4' but we're in MODE3 right now, it doesn't happen. It goes on to the next request which was 'I want to go from MODE3 to MODE5' and that one happens.

Now, there's an obvious flaw in this: the request to go to MODE4 is lost totally. The upshot is that if I press two buttons at the same time only one thing happens. For buttons that's good enough, but for other inputs it's not. For some inputs what you really mean to say is 'No matter what mode I'm in now, I want to go to MODE8'. How do you do that? Simple, it's.. No, wait, how DO you do that?

Oh, wait, I know how. Assuming you followed all of the above steps, then when you XOR the information in the queue with the current mode you get out a valid new mode and just switch to that. If you don't, then you can assume that you want to perform one of these unequivocal mode changes. You just have to figure out what mode you want to change to. So, in order to handle that, you can do this: instead of putting the XOR'd mode into the queue, just put the next mode you want to go to. When the program attempts to XOR it again with the current mode it WON'T get a valid mode out of it. So, it will XOR the data again with the current mode and if you meant to do one of those unequivocal jumps, it will produce a valid mode from THAT XOR operation. If you didn't mean to do an unequivocal jump, then it will produce an invalid mode. Tada!

No comments: