# Poisoned Numbers, Poisoned Branching.

© Copyright 2004 by Paul Hsieh

In this little essay we are going to discuss poisoned numbers (numbers we
want to avoid) by looking at two simple problems. We complicate the problems
by asking how to write code to solve with without branches (which modern
processors don't like.)

### 1. The Pigeonhole Choice

Suppose we start with 3 predefined constant numbers (which may or may not be
different -- but you don't necessarily know.) You are passed two of the
numbers, and required to return the third. This actually comes up as an
interesting practical problem when using the "triple buffer algorithm" to
smooth a stream of multimedia data when the producer is asynchronous to the
consumer. One buffer was just written to, the other consumed, which is the
remaining buffer from which we can start a new write sequence? Well we can
pose a trivial solution:

But of course, this code has a lot of conditional operations (the if(), the
&&, and 8 == operations). This does not bode well for our modern deeply
pipelined processor. The question is, can we solve this without any
branches (no if()'s, loops, ?: or conditional operators)?

### 2. Any Other Number

Suppose we have been handed an array of 32 unsigned integers (2s complement)
that are 32 bits in length each. We wish to choose any number which is
different from all these numbers (not necessarily from any given set of
numbers as in the problem described above.) How might we do this?

Well the loops ought to be well predicted right? Yeah, but the two if()
statements in there are going be bad news for the our deeply pipelined
processor. So same as before, the question is, can we solve this without any
branches (no if()'s, loops, ?: or conditional operators)?