int ct_inteq(uint32 x, uint32 y)
{
- uint32 a = U32(~(x ^ y));
-
- a &= a >> 16;
- a &= a >> 8;
- a &= a >> 4;
- a &= a >> 2;
- a &= a >> 1;
- return (a & 1);
+ uint32 a = x ^ y;
+
+ /* --- How it works --- *
+ *
+ * Obviously, %$a$% is nonzero if and only if %$x \ne y$%. Let %$N > 0$%.
+ * Suppose that %$0 < a < N$%. Then:
+ *
+ * %$N/2 = N - N/2 \le N - (a + 1)/2 = N - a/2 - 1/2$%
+ * %${} = N - a + a/2 - 1/2 = N - a + (a - 1)/2$%
+ * %${} \le N - a + \lfloor a/2 \rfloor < N$%
+ *
+ * Consequently, if %$N = 2^{32}$% and %$a$% is nonzero, then
+ * %$a - \lfloor a/2 \rfloor$% has its top bit set. Of course, if
+ * %$a = 0$% then %$a - \lfloor a/2 \rfloor = 0$%.
+ */
+
+ a = (a >> 1) - a;
+ return (U32(~a) >> 31);
}
/* --- @ct_intle@ --- *
*
* Arguments: @uint32 x, y@ = two 32-bit unsigned integers
*
- * Returns: One if %$x \le y$% are equal, zero if @x@ is greater.
+ * Returns: One if %$x \le y$%, zero if @x@ is greater.
*
* Use: Answers whether two integers are ordered, in constant time.
*/
*
* If the top bits of @x@ and @y@ are the same then %$x \le y$% if and only
* if %$y - x$% has its top bit clear; otherwise, %$x \le y$% if and only
- * if the top bit of @x@ is clear and the top bit of @y@ is set.
+ * if (the top bit of @x@ is clear and) the top bit of @y@ is set.
*
* This assumes we can do subtraction in constant time, which seems like a
* safe enough bet.
*/
- uint32 xx = x >> 31, yy = y >> 31, zz = (y - x) >> 31;
- return ((~xx&yy) | (~(xx^yy)&~zz)) & 1;
+ uint32 diff = x^y;
+ uint32 low = y - x;
+ uint32 a = (y&diff) | (~low&~diff);
+ return (U32(a) >> 31);
}
/* --- @ct_pick@ --- *