Archive for January, 2009

Common programming errors and presidential inaugurations

Tuesday, January 20th, 2009 Nigel Jones

I don’t normally link politics and embedded systems, but something happened today at the inauguration of Barack Obama that struck me as an obvious error, but which my family and I suspect 99.999% of the rest of the viewers accepted without question. I’m referring to the third paragraph of Rick Warren’s invocation where he stated:

Now, today, we rejoice not only in America’s peaceful transfer of power for the 44th time. We celebrate a …

Well it seems to me that if Barack Obama is the 44th president of the USA, then there can only have ever been 43 transitions of power. I suppose that one could claim that when Washington became president, it was a transition of power. However no one could possibly claim it was peaceful!

What’s my point? Well Rick Warren had just made a classic programming blunder. I’m guessing that his invocation was scrutinized by an army of political hacks, many with advanced degrees from top universities – yet despite this the error was not caught. I guess next time you make this mistake in your code, you can console yourself with this information.

BTW, you will not be surprised to know that my wife and kids just think that this confirms their belief that I’m a complete Nerd who is in desperate need of a life!

Using Espresso to simplify embedded systems

Sunday, January 18th, 2009 Nigel Jones

In this case, Espresso does not refer to the highly caffeinated drink, but rather to the public domain logic minimization tool. What does this have to do with embedded systems? Well, several months back I was faced with an interesting problem. A product I was working on had nine different alarm outputs (some of which are contradictory), which together were dependent upon about thirty different inputs. Furthermore, the interaction between the various inputs leads to situations where the desired alarm outputs are non obvious, and certainly difficult to determine algorithmically. At this point I realized that what was needed was essentially a giant truth table, where the outputs for any given set of inputs was determined by an expert who could look at the various inputs and determine the optimal alarm strategy. Thus the question was, how to tackle this problem? This is what we ultimately ended up doing. First of all the truth table was entered in a database. This was done simply so that we could easily run queries, such as “show me all cases where output 3 is asserted when inputs 6 12 and 13 are negated”. This essentially then was the environment in which the human expert worked. Once the expert was happy with the truth table, it was outputted in CSV format. The CSV file was then pre-processed by a Perl script (thanks Don) and fed to the Espresso logic minimization program. The output of Espresso was then post-processed by the Perl script and converted into compilable C code. To give you a feel for what the output looks like, here’s an excerpt (with the comments removed):

 if(((!(inputs[0] & 0x20)) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10) && (!(inputs[3] & 0xa0))) ||
    ((!(inputs[0] & 0x20)) && (!(inputs[1] & 0x60)) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x20)) && ((inputs[2] & 0x4) == 0x4) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x20)) && ((inputs[1] & 0x1) == 0x1) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x20)) && ((inputs[2] & 0x2) == 0x2) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x24)) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x28)) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x30)) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)) ||
    ((!(inputs[0] & 0x20)) && (!(inputs[1] & 0x4)) && (!(inputs[2] & 0x30)) && ((inputs[3] & 0x10) == 0x10)))
{
 out |= 2048;
}

Evidently, it’s enough to make your head spin! For me, the real benefits of such an approach are as follows:

  • I was able to completely divorce the code from the desired functionality. That is, the functionality of the product was completely driven by the client and was in no way dependent upon me doing anything. Thus, when the client asks me ‘what does it do when the following occurs”, I can honestly answer “it’s whatever you told it to do”.
  • By setting this up using a database and a Perl script we recognized that changes to the truth table would inevitably occur, and thus made the process as painless as possible. Now, when a change in functionality is desired, the client simply makes the changes in the database, presses a button to output a new file and I then run a ‘make’.
  • The approach is rigorous. We have considered every possible combination of inputs – no matter how unlikely they are to occur. In my experience, this is something that firmware is not very good at.

Although I think this is neat in its own right, I think there are several larger points worth making:

  • Just because a tool was designed ostensibly for one environment (in this case Espresso was really designed for logic minimization in electrical circuits), don’t be afraid to use it in other ways.
  • Recognize that certain elements in your design are highly prone to change – and design them with this in mind.
  • Either learn a scripting language or have a scripting expert at your disposal to help build your tool sets. (In my case, I do the latter).
  • If you can divorce your code from the required functionality (i.e. data driven coding), then seriously consider it.

An apology

For all of you that subscribe via RSS, I apologize for the recent blitz of data. I decided to go back through all my postings and add links where appropriate, which seems to have forced the posts to be regenerated.

Home

Using volatile to achieve persistence!

Sunday, January 11th, 2009 Nigel Jones

Once in a while the real world and the arcane world of language standards collide, resulting in surprising results. To see what I mean, read on …

Many of the products I design incorporate a Bootstrap Loader, so that the application firmware may be updated in the field. In most cases, the bootstrap loader is a completely different program to the main application. Despite this, I find it useful for the main application to pass information to the bootstrap loader and vice versa. Thus the question arises, how best to do this? Well in the processor family I am using, although it is technically possible to store information in Flash, EEPROM or RAM, by far the easiest and most secure way of doing it is to place the information into EEPROM. Furthermore, in order to enter the bootstrap loader it is highly desirable to force a reset of the processor by allowing the watchdog timer to time out.

Thus, the code to enter the bootstrap loader looks something like this:

__eeprom uint8_t msg_for_bootloader;

...

msg_for_bootloader = 0x42;

...

for(;;)
{
 /* Wait for watchdog to generate a reset and force entry in to the bootstrap loader */
}

Well, on the face of it, there is not much wrong with this code. However, if one turns on the optimizer, then the compiler examines the code, decides that no code may be executed beyond the infinite loop and thus concludes that the write to msg_for_bootloader is pointless, and promptly optimizes it away. (For a discussion on this topic, see my posting here)

Now you will note that msg_for_bootloader was qualified with __eeprom. This is a compiler extension that allows one to inform the compiler that the variable msg_for_bootloader resides in a special memory space and to be treated accordingly. Now I know that the compiler knows enough about the EEPROM space to generate the correct coding sequences such that reads and writes are performed correctly. However, in my naivete, I also assumed that the compiler knew something about the properties of EEPROM, such that it would realize writing to EEPROM without ostensibly reading it again is intrinsically useful in many applications.

Well it does not. Furthermore, on balance I think the compiler writer’s got it right and the error was completely mine.

So what to do? Well, declaring msg_for_bootloader as volatile fixes the problem. Thus my code now looks like this:

__eeprom volatile uint8_t msg_for_bootloader;

...

msg_for_bootloader = 0x42;

...

for(;;)
{
 /* Wait for watchdog to generate a reset and force entry in to the bootstrap loader */
}

Thus I ended up in the rather bizarre situation of having to declare a variable as volatile in order to make it persistent!

Although I can appreciate the wry irony of this situation, I think it points to a larger problem. The fact is that we are all (ok, most of us) programming in a language (C) that was not designed for use in embedded systems. Indeed, when C was written, I’m not sure EEPROM even existed. As a result, the compiler vendors have added extensions to the C standard in an effort to overcome its shortcomings for embedded systems, while still desperately striving to achieve “full compliance with the standard”. Despite this, I find myself all too frequently falling into traps such as this one. What we really need is a language explicitly designed for embedded systems. It isn’t going to happen, but it doesn’t stop me wishing for it.

Home

Horner's rule and related thoughts

Monday, January 5th, 2009 Nigel Jones

Recently I was examining some statistical data on the performance of a sensor against temperature. The data were from a number of sensors and I was interested in determining a mathematical model that most closely described the sensors’ performance. Using the regression tools built into Excel, I was looking at the various models, from a ‘goodness of fit’ perspective. After playing around for a while, I came to the conclusion that a quadratic polynomial really was the best fit, and should be the model to adopt. At this point, I turned to the issue of computational efficiency.

Now, it turns out that there is a relatively well known algorithm for evaluating polynomials, called Horner’s rule. I say relatively well known, because I’d say about half the time I see a polynomial evaluated, it doesn’t use Horner’s rule, but instead evaluates the polynomial directly. Thus in an effort to increase the use of Horner’s rule, I thought I’d mention it here.

OK, so what is it? Well it’s based on simply refactoring a polynomial expression:

anxn + a(n-1)x(n-1) + … + a0=((anx + a(n-1))x +…)x + a0.

Thus a polynomial of order n, requires exactly n multiplications and n additions.

For example:

23.1x2 – 45.6x + 12.3 = (23.1x -45.6)x + 12.3

In this case a quadratic equation or order 2, using Horner’s rule requires 2 multiplications and two additions to evaluate the polynomial, versus the direct approach which requires 5 multiplications and 2 additions.

For those of you that are looking for code to just use, then this snippet will work. This is for a cubic polynomial. COEFFN is the coefficient of xN.

y = x * COEFF3;
y += COEFF2;
y *= x
y += COEFF1;
y *= x
y += COEFF0;

The recurrence relationship for higher order polynomials should be obvious. Note that unlike most implementations, I perform the code in line, rather than using a loop.

It should be noted that as well as being more computationally efficient, Horner’s rule is also more accurate. This comes about in two ways:

  • The very act of using less floating point operations leads to less rounding errors
  • Higher order polynomials generate very large numbers in a hurry. Horner’s method significantly reduces the magnitude of the intermediate values, thus minimizing problems associated with adding / subtracting floating point numbers that differ in magnitude

Although Horner’s rule is a nice tool to have at one’s disposal, I think there is a larger point to be made here. Whenever you need to perform any sort of calculation, there is nearly always a superior method than the obvious direct method of evaluation. Sometimes it requires algebraic manipulation such as for Horner’s rule. Other times, it’s an approximation method, and other times it’s just a flat out really neat algorithm (see for example my posting on Crenshaw’s square root code). The bottom line. Next time you write code to perform some sort of numerical calculation, take a step back and investigate possibilities other than direct computation. You’ll probably be glad you did.

Update

There is a highly relevant addendum to this posting here.

Home