with a hole in the middle.”

— Mark Twain

In circular situations, we often wish to employ the mod operator to achieve “wrap-around” at both ends of a linear system to mimic a circular system:

1 2 3 |
0 1 2 3 4 5 6 7 (n = 8) ^ i |

Achieving clockwise wrap-around (from n to 0) usually poses no problem:

1 2 3 |
size_t circular_increment(size_t index, size_t n) { return (index + 1) % n; } |

The % operator is the compiler vendor’s approximation of the mod operator. It ensures that values which exceed n wrap-around nicely:

1 2 3 4 5 |
assert(circular_increment(5, 8) == 6); assert(circular_increment(6, 8) == 7); assert(circular_increment(7, 8) == 0); assert(circular_increment(0, 8) == 1); : |

Alas, most operator % implementations are not so useful when it comes to counter-clockwise wrap-around (from 0 to n):

1 2 3 |
size_t circular_decrement(size_t index, size_t n) { return (index - 1) % n; } |

If index – 1 becomes negative, we likely get negative results — which is far from what we desire:

1 2 3 |
assert(circular_decrement(2, 8) == 1); assert(circular_decrement(1, 8) == 0); assert(circular_decrement(0, 8) == 7); // Fail! -1 returned instead of 7. |

To readers of this column (part I in particular) this is of course old hat. They know that you can’t trust the % operator when negative operands are involved. Circular coders often work around this shortcoming like so:

1 2 3 4 5 6 |
size_t circular_decrement(size_t index, size_t n) { if (index == 0) return n - 1; else return index - 1; } |

Not nice, but no big deal either, you probably think. But what if you need a function that advances an index in either direction, depending on the sign of the offset:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
size_t circular_advance(size_t index, int offset, size_t n) { size_t new_index; if (offset >= 0) { new_index = (index + offset) % n; } else { offset = -offset; if (index >= offset) { new_index = index - offset; } else { new_index = n - offset + index; } } return new_index; } |

Now this looks disgusting, this *is* a big deal! And all just because our wretched % operator doesn’t behave like it should. Remember, if it did, we could simply write:

1 2 3 |
size_t circular_advance(size_t index, int offset, size_t n) { return (index + offset) % n; // if only '%' was 'mod'... sigh! } |

Did you notice that our convoluted circular_advance function actually contains a bug? No? Here’s a hint. The bug is in this line:

1 |
new_index = n - offset + index; |

What happens if the offset is larger than n? Answer: the expression n – offset will underflow producing a wrong result. That’s why we would have to write this, at least if we wanted to be 100% correct:

1 |
new_index = n - (offset % n) + index; |

which makes the code even uglier. But do we really need to support such large offsets? If we don’t (which is almost always the case in circular scenarios) and can live with offsets whose value is less than or equal to n, we can simplify circular_advance significantly. Here’s how.

We know that adding a multiple of n to the dividend x doesn’t change the result of the modulo operation:

1 |
x mod n ≡ (x + i*n) mod n |

If we include an arbitrary offset, we get this:

1 |
(x + offset) mod n ≡ (x + offset + i*n) mod n |

This allows us to turn negative arguments to operator % into positive arguments by adding i*n, without changing the result. Further, if we ignore cases where the offset value is greater than n, we only have to add 1*n to enforce a positive argument to operator %. Here’s an example:

1 2 3 |
(1 - 3) mod 8 ≡ (1 - 3 + 8) mod 8 -2 mod 8 ≡ 6 mod 8 6 ≡ 6 |

Since all operands are positive, we can use 6 % 8 to compute -2 mod 8. Equipped with this knowledge, we can eradicate the ugliness and circular_advance boils down to this:

1 2 3 |
size_t circular_advance(size_t index, int offset, size_t n) { return (index + offset + n) % n; } |

If we apply the same technique to the ring buffer’s original ring_buffer::size method from the last installment:

1 2 3 4 5 |
size_t size() const { return head_ >= tail_ ? head_ - tail_ : BUFSIZE - (tail_ - head_); } |

we get a simple branch-free solution:

1 2 3 |
size_t size() const { return (head_ - tail_ + BUFSIZE) % BUFSIZE; } |

which can be optimized easily by the compiler, especially if BUFSIZE is a base-2 number.

So here’s the takeaway. To get efficient, branch-free mod-like behavior for positive divisors n:

If n is a base-2 number, use bitwise-AND instead of the % operator:

1 |
a mod n ≡ a & (n - 1) |

If there’s only clockwise wrap-around (ie. a >= 0), % works just fine

1 |
a mod n ≡ a % n |

If a is either positive or negative, but |a| is <= n, add n to the operand before applying the % operator:

1 |
a mod n ≡ (a + n) % n |

## Comments (0)