Retpoline integration

[Jan Stola]

On 7.1.2018 20:27, Jaroslav Tulach wrote:

> I beg the pardon, but...
>
>> array[index + ((length-1-index) & (length-1-index)>>31)]
> What is this
>
> x & (x >> 31)
>
> Operation good for?

The expression follows this pattern:

y + (x-y) & (x-y) >> 31

If x >= y then x-y >= 0 and (x-y) >> 31 is 0 (considering 32-bit type). 
So, we have y + (x-y) & 0 = y.

If x < y then x-y < 0 and (x-y) >> 31 is -1 (represented by all ones). 
So, we have y + (x-y) & (-1) = y + x - y = x.

So, we have min(x,y) = y + (x-y) & (x-y) >> 31.

This explanation ignores the fact that there can be an 
underflow/overflow in (x-y). We have x = array.length - 1 in our case, 
i.e., x >= -1. Hence, x-y >= Integer.MIN_VALUE. On the other hand, we 
can have x-y >= Integer.MAX_VALUE (i.e., overflow, by taking y negative 
with abs(y) large enough). If overflow occurs then x-y is negative 
instead of being positive, i.e., we get maximum instead of minimum. This 
is fine (from the potential attack point of view) because maximum is (x 
== array.length-1) in such case. Hence, we stay in bounds then (unless 
array.length == 0, which is an unimportant corner case).

Honza