[PATCH 04/17] Add string vectorized find and detection functions

[Wilco Dijkstra <Wilco.Dijkstra@arm.com>]

Hi Adhemerval,

+static inline unsigned int
+__clz (op_t x)
+{
+#if !HAVE_BUILTIN_CLZ
+  unsigned r;
+  op_t i;
+
+  x |= x >> 1;
+  x |= x >> 2;
+  x |= x >> 4;
+  x |= x >> 8;
+  x |= x >> 16;
+# if __WORDSIZE == 64
+  x |= x >> 32;
+  i = x * 0x03F79D71B4CB0A89ull >> 58;
+# else
+  i = x * 0x07C4ACDDU >> 27;
+# endif
+  r = index_access (i);
+  return r ^ (sizeof (op_t) * CHAR_BIT - 1);
+#else
+  if (sizeof (op_t) == sizeof (long int))
+    return __builtin_clzl (x);
+  else
+    return __builtin_clzll (x);
+#endif
+}

This is a really bad idea. Firstly it is incorrect - sizeof (op_t) != __WORDSIZE due to
the odd way it is defined (it can be 64 bits on 32-bit targets). That in itself is
problematic since it isn't clear that using 64 bits operations extensively is efficient
on 32-bit targets (using 64-bit multiplies in GMP is different from using 64-bit
load/store in memcpy/memset which is different from 64-bit logical operations and
shifts, so all of these should be decoupled rather than forced together).

Secondly, there are already several ways to use count leading zeroes in GLIBC.
One is use the builtin unconditionally (done in lots of places, eg. by math code),
another is count_leading_zeros defined in longlong.h. This would add the third way. 
It's not clear how much gain inlining gives over using the libgcc implementation,
but if it is significant then we could provide a generic inline clzl/clzll that can be
used throughout GLIBC (replacing existing builtin_clz and count_leading_zeros).

Finally, emulating a full clz is inefficient. If you have already called find_zero_low
then there are at most 4 bits set on a 32-bit LE target, so you can trivially get the
index of the first zero byte via:

x = x & -x;
x = (x >> 15) + (x >> 22) + 3 * (x >> 31);

This is many times faster. There may be similar sequences for big-endian, but
you could just do a multiply with a magic word that gives the correct result
without needing a lookup table.

Cheers,
Wilco