base/ct.c: Better constant-time algorithms from /Hacker's Delight/.

Improve equality checking and ordering, and add detailed commentary.

diff --git a/base/ct.c b/base/ct.c
index ffb15b0..5393450 100644 (file)
--- a/base/ct.c
+++ b/base/ct.c
@@ -46,14 +46,24 @@
 
 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@ --- *
@@ -71,14 +81,16 @@ int ct_intle(uint32 x, uint32 y)
    *
    * 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@ --- *