« Archives in December, 2012

Circular Adventures IV: A “Complementary” Gift

“Th’ hast spoken right, ’tis true.
The wheel is come full circle, I am here.”

— Shakespear, King Lear Act 5, scene 3, 171–175

In the previous part of this series, I’ve shown how to calculate the distance between two indices into a circular buffer using the mathematical mod operator. Today, I will give you a solution that doesn’t need the mod operator and is even more efficient.

We have always viewed our N element ring buffer like this:

There are N = 10 elements, indices start at 0 and end at N – 1. But let’s pretend for a moment that we had signed indices instead; indices that can become negative:

Like in the unsigned system, we assume that the borders are joined, that is, the successor of 4 is -5 and the predecessor of -5 is 4.

The arithmetic distance between a and b is, like before, b – a:

What is special about this new system is that if the distance gets larger than 4, it suddenly becomes negative. Remember that the successor of 4 is -5. So in this case

b – a is +6 which is, taken our special wrap-around mechanism into account, -4. This means that not b is ahead of a, but a is ahead of b by 4!

In fact, the wrap-around value of the arithmetic distance is exactly the circular distance that we calculated in part III using a different approach:

Note that our invariant which we established in the previous installment still applies: the true circular distance between two indices must be half the size of the ring buffer (N) or less. That’s why the circular distance for cases where b – a equals +/-5 is marked as undefined in the table.

In order to calculate the circular distance, we need to take the following steps:

1. Convert the positive indices a and b from an unsigned number system (0 .. N) into indices of a signed number system (-N/2 – 1 .. +N/2) via a ‘magic’ wrap-around function.

2. Calculate the arithmetic difference: d = magic(b) – magic(a)

3. Calculate the circular distance by applying the magic function to the arithmetic distance: cd = magic(d)

Or, in pseudo code:

You probably wonder how magic() could be implemented, but by now, you should know that the mod operator is the answer to almost all circular problems. So one way to implement magic() is this:

Viewed from a different angle, our new signed system is really just the old unsigned system translated by -N/2.

But what have we gained compared to our implementation of circular_distance from part III? We now have to invoke the mod operator three times (due to three calls to magic()) compared to one time. And we still have the problem that the mathematical mod operator is not available on all platforms/languages. Unless we find an efficient alternative implementation of magic(), we are off worse.

If you take a closer look at the new signed system (values that go from -N/2 – 1 to +N/2) you might notice that it bears a strong resemblance to C’s integer types. Consider the following value ranges on a typical 32-bit system:

Apparently, in the C programming language, the type ranges also go from -N/2 – 1 to +N/2! But what’s even better is that if you exceed the upper/lower boundaries of a signed C integer type, wrapping will be done just like we want it:

Strictly speaking, according to the C/C++ standards, what happens on signed integer over-/underflow is not defined. But if your system uses two’s complement to represent negative numbers (and I’ve never come across a system that does not) you are fine.

Leaving this academic portability issue for C/C++ aside, in C/C++/C# and Java, magic() corresponds to a simple cast to a signed type, provided our ring buffer has a size that is supported by the value range of an integer type. If, for example, N is 256, circular_distance can be implemented like this:

We can leave out the explicit casts if we use a function, since the parameters and return value will be ‘cast’ implicitly:

As an example, consider a 32-bit timer that keeps track of the system time. A timer interrupt service routine will update the timer value regularly behind the scenes. Based on what we have learned, you can easily measure the time between two events, even if the timer should overflow in between:

Most systems software (including embedded systems) is implemented in C, mainly because efficiency is at a premium. Due to the fact that C doesn’t come with a mathematical mod operator, it is sometimes sensible to “force” the size of timers/counters/ring buffers to the upper bound of an unsigned integer type. With this being the case, the aforementioned ‘cast-to-signed’ trick can be applied and calculating circular distances becomes both, easy and computationally cheap.

More circular adventures…