Optimization - Real-Time Collision Detection - page 550

00401157 je 00401170

00401159 cmp eax,3 ; if (x == 3) goto RETURN_1

0040115C je 00401170

0040115E cmp eax,5 ; if (x == 5) goto RETURN_1

00401161 je 00401170

00401163 cmp eax,7 ; if (x == 7) goto RETURN_1

00401166 je 00401170

00401168 cmp eax,11 ; if (x == 11) goto RETURN_1

0040116B je 00401170

0040116D xor eax,eax ; return 0

0040116F ret

00401170 mov eax,1 ; RETURN_1: return 1

00401175 ret

With almost every other instruction for a branch, this code is not pipeline friendly.
The branches can be removed by replacing the shortcut OR operations ( || ) with
bitwise OR operations ( | ) However, the resulting compiled code becomes quite long,
and thus bitwise ORs do not constitute an ideal solution. A better solution is a small
bitwise lookup table held in a constant. By setting bits 2, 3, 5, 7, and 11 of this
constant, the bit corresponding to x holds the correct return result. When coded in
C/C++, the only complication is that the bit-shift operators are undefined for right-
hand operands larger than the number of bits in the left-hand operand. Taking this
problem into account gives the following branch-optimized code.

uint32 SmallPrime(uint32 x)
{

const uint32 PRIME_BITS = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 11);
uint32 mask = (x < 32);
return (PRIME_BITS >> x) & mask;

}

The new function compiles to the following.

00401180 mov ecx,dword ptr [esp+4] ; fetch x

00401184 mov edx,8Ach ; PRIME_BITS = ...

00401189 cmp ecx,32 ;x<32

0040118C sbb eax,eax

0040118E shr edx,cl ; edx = PRIME_BITS >> “x”

00401190 neg eax ; eax = mask

00401192 and eax,edx

00401194 ret ; return (PRIME_BITS >> x) & mask