Andrew Que Sites list Photos
Projects Contact
Main

September 29, 2019

Poor Man's Semaphore Mistake

On small embedded systems that don’t use an operating system, there is often a mix of a main loop and system interrupts for controlling the system. One problem with interrupts is spelled out in their name: they interrupt normal code. This can change variables being used by other code, while they are being used. This can be useful if you are waiting for an event. For example:

bool volatile hasInterruptOccured = false;

void someInterruptFunction()
{
   hasInterruptOccured = true;
}

while ( ! hasInterruptOccured );

Assume someInterruptFunction is called by an interrupt routine and the while loop is in the program’s main function. One important note here is that hasInterruptOccured is marked volatile. That tells the compiler the value could change at any time. Otherwise, the optimizer will assume that since the while loop never changes hasInterruptOccured then it never needs to check it again. Being volatile means the optimizer will make no such assumptions.

The above is a useful example of variable being changed by interrupts, but it can be problematic.

Consider this code below. A function is called periodically to make calculations from x, but x is changed from an interrupt source.

y = a * x * x + b * x + c;

Now consider what happens if x can change at any time. The equation might actually result in the following:

y = a * x1 * x2 + b * x3 + c;

Where only two of the set of xn are equal. We never know when an interrupt might occur, and should plan that is can occur anywhere. One solution to the above is to use an intermediate to hold the value of x.

xHold = x;
y = a * xHold * xHold + b * xHold + c;

This would seem to solve all our problems, but it might not. Consider this code on an 8-bit processor:

uint16_t xHold = x;
y = a * xHold * xHold + b * xHold + c;

You might think that xHold will capture the value of x, but it may not. That is because on an 8-bit system, storing the value of a 16-bit integer takes 2x 8-bit operations, any one of which might be interrupted. This means xHold could change in horrible ways.

Consider x=256 or 0x0100, and an interrupt will change the value to 255 (0x00FF). Now if the assembly code starts the copy with the most-significant byte, then gets interrupted, the result in xHold will be 511 (0x01FF). That’s because it read the most-significant byte when that was set to 0x01, and after the interrupt read the least-significant byte which was now 0xFF.

The typical solution to avoiding such issues is simply to disable interrupts when reading volatile variables.

DisableInterrupts();
uint16_t xHold = x;
RestoreInterrupts();
y = a * xHold * xHold + b * xHold + c;

Now there is no way for x to change when reading.

There is a second way to accomplish the same thing without disabling interrupts.

uint16_x xHold;
do
{
   xHold = x;
} while ( xHold != x );

What’s going on here is that we check to see if x matches what we just read. If it doesn’t, x changed either during the storing, or the reading check. In either case, we simply try again. This works great for things such as system timers, and doesn’t require disabling every interrupt in the system just to get a value. It is my preferred way to fetch a single volatile value, and I usually call this the poor man’s semaphore as the same type of scenarios happens with threaded tasks. With threads you can simply use a semaphore or mutex to wrap the reading area, but you could use the same do-while trick.

Now for how to mess this up. In many projects I use a micro-controller timer as a system clock that counts in milliseconds or tens or hundreds of milliseconds per tick. The interrupt for the timer is very simple:

static uint32_t volatile systemTime = 0;
void timerInterrupt()
{
   systemTime += 1;
}

Then I make a function to get the system time.

uint32_t getSystemTime()
{
   uint32_t result;
   do
   {
      result = systemTime;
   }
   while ( result != systemTime );
   
   return result;
}

The other day I found I had made a mistake in implementing this function. Here is what I had instead:

uint32_t getSystemTime()
{
   uint32_t result;
   do
   {
      result = systemTime;
   }
   while ( result != systemTime );
   return systemTime;
}

The difference is very subtle, but messed up all the work done to ensure the value didn’t change. If the above code were to run on an 8-bit micro-controller, the function could return bad times. I got lucky. In my case, the system was a 32-bit micro-controller with 1 ms ticks and the system time was a 64-bit value. The timer only modifies the upper 32-bit once every 49 days. So the chances for reading an incorrect timer value is very low. Still, a stupid mistake.

January 07, 2019

64-bit CRC support to A.Q. CRC

This weekend I completed the major changes needed for the CRC site to support 64-bit CRC generation. The reason this could not happen right away has to do with how Javascript handles numbers. In Javascript, all numbers are 64-bit (double-precision) floating-point. You can do bit manipulation, but it is done on floating-point values. An IEEE double-precision float has 1 sign bit, 11-bits of exponent and 52-bits of mantissa. In theory one could store 52-bits in a double without loss of precision. That means Javascript cannot directly hold a 64-bit CRC in a single word, and that makes implementation more difficult.

We cannot use a single word to hold results, but we can use multiple words. So the first step in generating larger CRCs inside Javascript is to create an arbitrary length word. Although we technically can use 52-bits/word, it is easier to work with 32-bit words. I created a unit that can do bit manipulation on words of arbitrary length. In reality I only need 64-bit words, but it was about as easy to use make this size arbitrary. The unit needed to support basic bit operations: AND, OR, XOR, shifts, bit reversal, etc., and converting to/from strings.

After a large word unit was implemented I needed to make the CRC class use it. The large words are significantly slower than small, so I kept the original class and simply duplicated the functionality with a large class.

It took a few passes but I worked out all the bugs and now have a functional CRC class that can generate 64-bit CRCs. The system can do the 82-bit CRC, but the C implementation system only supports up to 64-bit word sizes.

January 04, 2019

Verifying Javascript Output

My CRC website creates C source code using Javascript and I needed a method to verify the generated code. As an engineer I am pretty lazy and I didn’t want anything manual so I went in search of a tool that could help. I found system called PhantomJS which seems to be designed to test Javascript rich websites, and it seems to be exactly what I was looking for. I was able to use it to run a test script that generated C code for every possible CRC output combination, along with test C code. The code is then saved to disk where it can be compiled and verified. The results: all good. CRC code for each combination generates the correct CRC for the test vector.

Temp were above 40°F/4°C this afternoon and made for a very pleasant ride home.  Temperatures are forecast to stay warm through the weekend and I have a feeling the snowman I'm standing with will not be around on my next ride.

January 02, 2019

A.Q. CRC Goes Live

   For several weeks now I have been working on a project for generating CRC calculating source code.  Today I finished enough of the foundation to make it live.  There is still work to be done, especially rigorous testing.  But the basics are online and ready to go.