From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 29 Dec 2016 11:50:50 +0000 (+0000)
Subject: base/ct.c: Better constant-time algorithms from /Hacker's Delight/.
X-Git-Tag: 2.3.0~23
X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/commitdiff_plain/8f7fd6c08d5bbf5cb451852c01db05f4a6dd598d

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 ffb15b09..5393450b 100644
--- 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@ --- *