“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:
|
1 2 3 4 5 |
0 1 2 3 4 5 6 7 8 9 ^ ^ a b |
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:
|
1 2 3 4 5 |
-5 -4 -3 -2 -1 0 1 2 3 4 ^ ^ a b |
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:
|
1 2 3 |
1 - -2 = 1 + 2 = 3 |
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
|
1 2 3 4 5 |
-5 -4 -3 -2 -1 0 1 2 3 4 ^ ^ a b |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
b-a leader a < b cd(a, b) ------------------------------- 0 - false 0 1 b true 1 2 b true 2 3 b true 3 4 b true 4 5 - - - 6 a false -4 7 a false -3 8 a false -2 9 a false -1 -1 a false -1 -2 a false -2 -3 a false -3 -4 a false -4 -5 - - - -6 b true 4 -7 b true 3 -8 b true 2 -9 b true 1 ------------------------------- |
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.
This “unusual” range of index values from -N/2 – 1 to +N/2 is what’s called a 2’s complement system in computer science. It’s a means of supporting signed types in programming languages. The unsigned value range 0 to N is split in two halves, one for the negative values and one for the positive values. Even though it’s not stipulated by the C language standard, 2’s complement systems are the de facto standard for signed type implementations in all contemporary compilers (including Java and C#; contrary to C, both actually do stipulate 2’s complement).
In order to compute the circular distance in a 2’s complement system, it looks as if we need to take three steps: 1) convert our real-world unsigned indices into signed indices, 2) calculate their signed difference, and 3) wrap-around the signed difference if it lays outside the -N/2 – 1 to +N/2 value range, similarly to what the mod operator does for unsigned values.
Step 1 we can skip altogether, because to a CPU, there really is no difference between signed and unsigned numbers, it’s just a matter of how we (or the compiler) interpret the bit patterns of the operation’s result. Hence, we can proceed to step 2 and compute the unsigned difference and interpret it as a signed number in step 3:
|
1 2 3 4 5 6 7 8 9 |
circular_distance(a, b, N): cd = (b - a) mod N # Unsigned difference. if cd > N/2: # Wrap-around positive to negativ. cd -= N elif cd < -N/2 - 1: # Wrap-around negative to positiv. cd += N return cd |
Now, if N is a base-2 number that coincides with our signed integer types
|
1 2 3 4 5 6 7 8 9 |
Type N From To ------------------------------------------ signed char 2^8 -128 +127 signed short 2^16 -32768 +32767 signed int 2^32 -2^31 - 1 +2^31 signed long 2^32 -2^31 - 1 +2^31 ------------------------------------------ |
Step 3 is as simple as a type-cast:
|
1 2 3 4 5 6 |
int32_t circular_distance_32_bit(uint32_t a, uint32_t b) { uint32_t cd = b - a; // mod 2^32 is implicit. return (int32_t)cd; } |
or even simpler:
|
1 2 3 4 5 |
int32_t circular_distance_32_bit(uint32_t a, uint32_t b) { return (int32_t)(b - a); } |
Strictly speaking, casting an unsigned integer to a signed integer is “implementation defined”. Implementation defined is not to be confused with “undefined” and means for all practical purposes: interpret the unsigned value as a 2’s complement signed integer value. This achieves the intended 2’s complement wrap-around, just as we desire.
As a case in point, 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:
|
1 2 3 4 5 6 7 8 9 |
volatile uint32_t g_systemTime; ... uint32 start = g_systemTime; // Do some lengthy operation. int32_t delta = circular_distance_32_bit(start, g_systemTime); |
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.