Add functions to count trailing zero bits in a word.

* cipher/bithelp.h (_gcry_ctz, _gcry_ctz64): New.
* configure.ac (HAVE_BUILTIN_CTZ): Add new test.
--

Note that these functions return the number of bits in the word when
passing 0.

Signed-off-by: Werner Koch <wk@gnupg.org>

2 files changed, 60 insertions, 0 deletions

diff --git a/cipher/bithelp.h b/cipher/bithelp.h
index 6e59c53f..2220bc87 100644
--- a/cipher/bithelp.h
+++ b/cipher/bithelp.h
@@ -77,4 +77,49 @@ _gcry_bswap64(u64 x)
 # endif
 #endif
 
+
+/* Count trailing zero bits in an unsigend int.  We return an int
+   because that is what gcc's builtin does.  Returns the number of
+   bits in X if X is 0. */
+static inline int
+_gcry_ctz (unsigned int x)
+{
+#if defined (HAVE_BUILTIN_CTZ)
+  return x? __builtin_ctz (x) : 8 * sizeof (x);
+#else
+  /* See
+   * http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup
+   */
+  static const unsigned char mod37[] =
+    {
+      sizeof (unsigned int)*8,
+          0,  1, 26,  2, 23, 27,  0,  3, 16, 24, 30, 28, 11,  0, 13,
+      4,  7, 17,  0, 25, 22, 31, 15, 29, 10, 12,  6,  0, 21, 14,  9,
+      5, 20,  8, 19, 18
+    };
+  return (int)mod37[(-x & x) % 37];
+#endif
+}
+
+
+/* Count trailing zero bits in an u64.  We return an int because that
+   is what gcc's builtin does.  Returns the number of bits in X if X
+   is 0.  */
+#ifdef HAVE_U64_TYPEDEF
+static inline int
+_gcry_ctz64(u64 x)
+{
+#if defined (HAVE_BUILTIN_CTZ) && SIZEOF_UNSIGNED_INT >= 8
+#warning hello
+  return x? __builtin_ctz (x) : 8 * sizeof (x);
+#else
+  if ((x & 0xffffffff))
+    return _gcry_ctz (x);
+  else
+    return 32 + _gcry_ctz (x >> 32);
+#endif
+}
+#endif /*HAVE_U64_TYPEDEF*/
+
+
 #endif /*G10_BITHELP_H*/
diff --git a/configure.ac b/configure.ac
index 4cfebe7b..4bbd686c 100644
--- a/configure.ac
+++ b/configure.ac
@@ -827,6 +827,21 @@ fi
 
 
 #
+# Check for __builtin_ctz intrinsic.
+#
+AC_CACHE_CHECK(for __builtin_ctz,
+       [gcry_cv_have_builtin_ctz],
+       [gcry_cv_have_builtin_ctz=no
+        AC_LINK_IFELSE([AC_LANG_PROGRAM([],
+          [unsigned int x = 0; int y = __builtin_ctz(x); return y;])],
+          [gcry_cv_have_builtin_ctz=yes])])
+if test "$gcry_cv_have_builtin_ctz" = "yes" ; then
+   AC_DEFINE(HAVE_BUILTIN_CTZ, 1,
+             [Defined if compiler has '__builtin_ctz' intrinsic])
+fi
+
+
+#
 # Check for VLA support (variable length arrays).
 #
 AC_CACHE_CHECK(whether the variable length arrays are supported,