— Yul Brynner
In part III and IV I discussed solutions for a circular problem where two indices performed a race within a circular buffer; that is, either index could be ahead of the other.
Sometimes, however, life is simpler and it is always known which index is the leader, and thus the winner — from the outset:
|
1 2 3 4 5 |
0 1 2 3 4 5 6 7 8 9 ^ ^ b a |
In this example, provided we know that b must always be ahead of a, we can deduce that b has wrapped around and the distance between a and b is 4.
Either implementation (the one given in part III and the one given in part IV) of circular_distance will return the same result:
|
1 2 3 |
circular_distance(8, 2, 10) == 4 |
However, both will fail for this case:
|
1 2 3 4 5 6 7 |
0 1 2 3 4 5 6 7 8 9 ^ ^ b a circular_distance(8, 4, 10) == -4 |
Why? Under the premise that b is always ahead of a, the distance is +6 not -4. circular_distance computes the wrong result because it assumes that the leading index is less than half the circular buffer size ahead of the other index. This assumption was made (I called it ‘invariant’ at the time) to be able to compute the circular distance even if it is not known which index is ahead of which.
Based on the prerequisite that b is always ahead of a we can give a simplified version of the circular_distance function from part III:
|
1 2 3 4 |
circular_lead(a, b, N): return (b - a) mod N |
I call this function circular_lead instead of circular_distance to emphasize that it returns how much b is ahead of a, which is always a positive number. As usual, all the restrictions (and optimizations) regarding the mod operator apply. In C, which lacks a true mod operator, a generic, portable implementation looks like this:
|
1 2 3 4 5 6 |
size_t circular_lead(size_t a, size_t b, size_t N) { if (b >= a) return b - a; return N - (a - b); } |
In situations where one index is known to be ahead of the other, circular_lead has an edge over circular_distance because it supports distances in the range 0 to N-1, whereas circular_distance only supports ranges from 0 to (N-1)/2. This is always the case in “monotonically increasing” scenarios, like run-time measurement, at least until the flux capacitor is invented. Hence, the last example of part IV can be rewritten like this:
|
1 2 3 4 5 6 7 8 9 10 |
volatile uint32_t g_systemTime; // Wraps around. ... uint32_t start = g_systemTime; // Do some lengthy operation. After that, we know // that 'g_systemTime' will be ahead of 'start'. unt32_t delta = circular_lead_32bit(start, g_systemTime); |
If we replace the mod operator with a cast to uint32_t, circular_lead_32bit boils down to this:
|
1 2 3 4 5 |
inline uint32_t circular_lead_32bit(uint32_t a, uint32_t b) { return (uint32_t) (b - a); } |
[For the mathematically inclined: What we are really talking about here is residue class rings, a concept used by all contemporary computers. I might explore the number theory behind this and other circular topics in a future post.]