[PATCH 1/5] string: Add fallback implementation for ctz/clz

[Adhemerval Zanella]

The algorithm is based on De Bruijn sequence, and it might be used
if the ABI does not want to use libgcc fallback implementation (for
instance on statup code where libgcc might be compiled with some
options not support at the time, like stack protector).

It is disable by default, so no target is affected.
---
 sysdeps/generic/math-use-builtins-bitops.h |  2 +
 sysdeps/generic/string-fzi.h               | 73 ++++++++++++++++++++--
 2 files changed, 69 insertions(+), 6 deletions(-)
 create mode 100644 sysdeps/generic/math-use-builtins-bitops.h

diff --git a/sysdeps/generic/math-use-builtins-bitops.h b/sysdeps/generic/math-use-builtins-bitops.h
new file mode 100644
index 0000000000..203f1bb70b
--- /dev/null
+++ b/sysdeps/generic/math-use-builtins-bitops.h
@@ -0,0 +1,2 @@
+#define USE_CLZ_BUILTIN 1
+#define USE_CTZ_BUILTIN 1
diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h
index 3c1028d1ec..beb7204fb9 100644
--- a/sysdeps/generic/string-fzi.h
+++ b/sysdeps/generic/string-fzi.h
@@ -22,23 +22,84 @@
 #include <limits.h>
 #include <endian.h>
 #include <string-fza.h>
+#include <math-use-builtins-bitops.h>
 
 static __always_inline int
-clz (find_t c)
+ctz (find_t c)
 {
+#if USE_CTZ_BUILTIN
   if (sizeof (find_t) == sizeof (unsigned long))
-    return __builtin_clzl (c);
+    return __builtin_ctzl (c);
   else
-    return __builtin_clzll (c);
+    return __builtin_ctzll (c);
+#else
+  if (sizeof (find_t) < 8)
+    {
+      static const char debruijn32[]
+	  = { 0,  1,  23, 2,  29, 24, 19, 3,  30, 27, 25, 11, 20, 8, 4,	 13,
+	      31, 22, 28, 18, 26, 10, 7,  12, 21, 17, 9,  6,  16, 5, 15, 14 };
+      return debruijn32[(c & -c) * 0x076be629 >> 27];
+    }
+  else
+    {
+      static const char debruijn64[]
+	  = { 0,  1,  2,  53, 3,  7,  54, 27, 4,  38, 41, 8,  34, 55, 48, 28,
+	      62, 5,  39, 46, 44, 42, 22, 9,  24, 35, 59, 56, 49, 18, 29, 11,
+	      63, 52, 6,  26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
+	      51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12 };
+      return debruijn64[(c & -c) * 0x022fdd63cc95386dull >> 58];
+    }
+#endif
 }
 
 static __always_inline int
-ctz (find_t c)
+clz (find_t c)
 {
+#if USE_CTZ_BUILTIN
   if (sizeof (find_t) == sizeof (unsigned long))
-    return __builtin_ctzl (c);
+    return __builtin_clzl (c);
   else
-    return __builtin_ctzll (c);
+    return __builtin_clzll (c);
+#else
+  if (sizeof (find_t) < 8)
+    {
+      c >>= 1;
+      c |= c >> 1;
+      c |= c >> 2;
+      c |= c >> 4;
+      c |= c >> 8;
+      c |= c >> 16;
+      c++;
+      return 31 - ctz (c);
+    }
+  else
+    {
+      unsigned long long int c0 = c;
+      find_t y;
+      find_t r;
+      if (c0 >> 32)
+	y = c0 >> 32, r = 0;
+      else
+	y = c0, r = 32;
+      if (y >> 16)
+	y >>= 16;
+      else
+	r |= 16;
+      if (y >> 8)
+	y >>= 8;
+      else
+	r |= 8;
+      if (y >> 4)
+	y >>= 4;
+      else
+	r |= 4;
+      if (y >> 2)
+	y >>= 2;
+      else
+	r |= 2;
+      return r | !(y >> 1);
+    }
+#endif
 }
 
 /* A subroutine for the index_zero functions.  Given a test word C, return
-- 
2.43.0