Trust, but Verify!
SHA Newsletter: Vol 2. No. 2

On one project I had occasion to do some fixed-point arithmetic on a digital-signal processing CPU (a “DSP”). Along with other calculations, I had to perform a few square roots along the way. I called a library function to do it, because the library is well-crafted and tuned for performance. Best of all, the function can be called from within a C language program, which is what I needed.

The input argument is a 32-bit unsigned value, and the function returns a 16-bit result. On input, the top 16 bits of the value represent the whole-number portion of the argument; the lower 16 bits are for the fractional part. That means the largest value the function can accept is slightly larger than 65535.

After describing the function in detail, the documentation offered an example program to show the function in action. The input variable, x, was declared as a long variable, and the output, y, was declared as an int. You could compile and run the sample program, and you would obtain the documented result. It sounds pretty straightforward, and it is. But there’s a latent error waiting to cause trouble. Do you see it? If you know about data types in C, you might have noticed the problem from the declaration of the variables. Otherwise, read on.

What’s the Problem?

The function can find square roots for only positive numbers. That’s why the documentation specifies that the input value is UNSIGNED – that is, it cannot be less than zero.

Variables of type long and type int are SIGNED values. They hold values both greater than and less than zero. The most-significant (highest-valued) binary digit (“bit”) in the number is used as a “sign bit” to distinguish positive from negative numbers. When the sign bit is zero, the number is considered positive; a one in the sign bit means the number is negative.

If the input argument is small enough, everything will appear to be OK, because the sign bit in the result will be zero. But if the sample program was used to find the square root of a number close to 65535, it could fail. That’s a valid input, but it can make the sign bit of the answer equal to one. When that happens, the result is interpreted as either zero or a very small negative number.

What’s wrong here? That sample program is suggesting that you can use data types that you might better avoid.

Ouch!

In many cases, you would never see a problem. Things could run properly for days or months, and then go wrong seemingly out of the blue. It might be very hard to track down the cause.

Oftentimes, I’ve seen software developers compare their code to the samples in the documentation. They want to make sure they are doing things in the right way. This can be a good practice, because a good example is often a boon to understanding things. But in this case, just looking at sample code isn’t enough. You need to test your code to verify that it works properly. Or you need to make certain that your program won’t encounter sensitive conditions unless you are prepared for them.

What needs to be checked?

Here are some possible input values for test cases:

Zero: What kind of result will appear if zero is the input? You might find some unusual sign-bit behavior or anomalies in the code that uses the result.

256: This is the square root of 65536, and it might indicate a bit-shift or sign problem if there is one.

4,294,967,295: This is represented as 32 ones in binary numeration and would be largest value that would fit in an unsigned 32-bit variable. You should get a result slightly larger than 256 because of the way the function scales values.

One or more perfect squares: Perfect squares are numbers whose square roots are whole numbers. These test cases could indicate roundoff errors in the function and its surrounding statements.

-1, or some other negative numbers: It would be wrong to use negative numbers for this function. But you might need to know how the function would respond in this case. This might cause a hardware interrupt that your program must handle, or otherwise report an error.

What To Do?

In this case, since the function expects positive numbers, use an unsigned long variable for the input, and an unsigned int for the output. It would keep that extreme case from causing you grief.

In general, if you are using library functions in your program, don’t assume that the documentation is perfect. Don’t assume that a sample program will be invariably correct, that it will demonstrate everything you need to know, or that it will work without side-effects.

For common tasks like square roots, you’re almost always better off using a standard library rather than crafting your own code. But using a library doesn’t mean the end of your worries. You need to test carefully. When you test, you should know beforehand what results you expect and should think about what kinds of errors the test should reveal.

Trust, but verify!

Please note: Any trademarks and trade names of others mentioned in this message are the property of their owners, and not Stoney Hill Associates, LLC. We respect the intellectual property of others. The information provided is believed to be reliable, but we cannot guarantee that the procedures and information given here will work correctly for your specific situation.

If you would like help with a computer or software problem you face, contact us. Send an email to request@stoneyhillassociates.com.

Want to subscribe to this newsletter? Just join our mailing list:

© 2005 Stoney Hill Associates, LLC