Fast constant time evaluation of "x==7" to 1 (true) or 0 (false) in Java

Question

I want to port a crypto function from C to Java. The function has to run in constant time, so no conditional branchings (and no table lookups based on x) are allowed.

The original C code is:

int x,result;
...
result = (x==7);
...

So that 'result' is set to 1 if 'x==7' and to 0 otherwise. The 'result' variable is then used in further computations.

I am now looking for the best way to transpose this to Java. As in Java expressions evaluate to booleans and not to integers, one has to simulate the above using operators.

I currently use

int x,result;
...
result = (1<<(x-7))&1;
...

which works fine for me, as my x is in the range {0,...,15}. (Note that the shift function uses only the lower 5 bits, so that you will get false positives when x is too large.)

The expression will be evaluated millions of times, so if it there is for instance a clever solution that uses only 2 operators instead of 3, this would make the overall computation faster.

Answer 1

The best option as noted by @Hosch250 is ternary operator. Let's take a look at the assembler generated by JIT compiler for this method:

public static int ternary(int x) {
    return x == 7 ? 1 : 0;
}

It actually depends on branch profiling. When your x has value 7 quite often, it's compiled like this:

xor %r11d,%r11d
mov $0x1,%eax
cmp $0x7,%edx
cmovne %r11d,%eax  ;*ireturn
                   ; - Test::ternary@11 (line 12)

See that ternary was replaced with cmovne which is not the branch instruction.

On the other hand if you pass 7 in very rare cases (e.g. once in 5000 calls), then branch is here:

cmp $0x7,%edx
je <slowpath>  ;*if_icmpne
                       ; - Test::ternary@3 (line 12)
xor %eax,%eax

Now branch is almost never taken, so the faster is to keep the condition as CPU branch predictor will be almost always correct. Note that <slowpath> is not just return 1;, it also updates the branch profile, so if it happens that the pattern changed during the program execution (7 become to appear more often), then the method will be recompiled to the first version.

In general, don't try to be smarter than JIT-compiler in such simple cases.