[PATCH v3 1/3] string: add find_ne_all to string-fza.h

[Matt Turner]

find_zero_ne_all () searches for a zero byte in X1 or a byte that differs
between X1 and X2.  A caller that knows X2 contains no NUL byte does not
need the zero test, since a NUL byte in X1 already differs from every
byte of X2.

Add find_ne_all (), which searches for inequality alone, to the generic
implementation and to each target that provides its own string-fza.h.
Dropping the zero test makes it cheaper than find_zero_ne_all () on every
target.

Return the difference unreduced wherever index_first () and index_last ()
come from the generic string-fzi.h, which uses stdc_trailing_zeros () and
stdc_leading_zeros () and so only needs to know which byte holds the first
or the last set bit.  That covers armv6t2, powerpc and riscv with the
bitmap extensions, as well as the generic implementation.  Only the
generic one tests HAVE_BITOPTS_WORKING, since its fallback ctzb () and
clzb () isolate a single bit and expect it at 0x80; the target masks are
already incompatible with that fallback and cannot use it either way.

riscv without the bitmap extensions takes its string-fza.h from the
generic implementation while defining its own index_first () and
index_last (), which tested bit 7 of each byte.  Test the whole byte
instead, so that they accept the unreduced difference.

alpha keeps a reduced form, its find_t being a cmpbge mask of one bit per
byte throughout.
---
 sysdeps/alpha/string-fza.h       |  7 +++++++
 sysdeps/arm/armv6t2/string-fza.h |  8 ++++++++
 sysdeps/generic/string-fza.h     | 19 +++++++++++++++++++
 sysdeps/powerpc/string-fza.h     |  9 +++++++++
 sysdeps/riscv/string-fza.h       |  8 ++++++++
 sysdeps/riscv/string-fzi.h       | 28 ++++++++++++++--------------
 6 files changed, 65 insertions(+), 14 deletions(-)

diff --git ./sysdeps/alpha/string-fza.h ./sysdeps/alpha/string-fza.h
index ae5d890a7e..8178e75178 100644
--- ./sysdeps/alpha/string-fza.h
+++ ./sysdeps/alpha/string-fza.h
@@ -52,6 +52,13 @@ find_zero_ne_all (op_t x1, op_t x2)
   return find_zero_all (x1) | (find_zero_all (x1 ^ x2) ^ 0xff);
 }
 
+/* Identify bytes that are not equal between X1 and X2.  */
+static __always_inline find_t
+find_ne_all (op_t x1, op_t x2)
+{
+  return find_zero_all (x1 ^ x2) ^ 0xff;
+}
+
 /* Define the "inexact" versions in terms of the exact versions.  */
 #define find_zero_low		find_zero_all
 #define find_eq_low		find_eq_all
diff --git ./sysdeps/arm/armv6t2/string-fza.h ./sysdeps/arm/armv6t2/string-fza.h
index 1eab43fdc3..a7ab4c9056 100644
--- ./sysdeps/arm/armv6t2/string-fza.h
+++ ./sysdeps/arm/armv6t2/string-fza.h
@@ -61,6 +61,14 @@ find_zero_ne_all (op_t x1, op_t x2)
   return find_zero_all (x1) | (find_zero_all (x1 ^ x2) ^ ones);
 }
 
+/* Identify bytes that are not equal between X1 and X2.  */
+static __always_inline find_t
+find_ne_all (op_t x1, op_t x2)
+{
+  /* The difference need not be reduced; see the generic string-fza.h.  */
+  return x1 ^ x2;
+}
+
 /* Define the "inexact" versions in terms of the exact versions.  */
 #define find_zero_low		find_zero_all
 #define find_eq_low		find_eq_all
diff --git ./sysdeps/generic/string-fza.h ./sysdeps/generic/string-fza.h
index 362c7a8fe6..e569d0aa41 100644
--- ./sysdeps/generic/string-fza.h
+++ ./sysdeps/generic/string-fza.h
@@ -19,6 +19,7 @@
 #ifndef _STRING_FZA_H
 #define _STRING_FZA_H 1
 
+#include <string-bitops.h>
 #include <string-misc.h>
 #include <string-optype.h>
 
@@ -95,4 +96,22 @@ find_zero_ne_all (op_t x1, op_t x2)
   return (ne2 | ~nz1) & ~m;
 }
 
+/* With similar caveats, identify bytes that are not equal between X1
+   and X2.  */
+static __always_inline find_t
+find_ne_all (op_t x1, op_t x2)
+{
+#if HAVE_BITOPTS_WORKING
+  /* index_first and index_last only need to know which byte holds the first
+     or the last set bit, so the difference does not have to be reduced to
+     one bit per byte.  The fallback ctzb and clzb do require the reduced
+     form, since they isolate a single bit and expect it at 0x80.  */
+  return x1 ^ x2;
+#else
+  op_t m = repeat_bytes (0x7f);
+  op_t ne = x1 ^ x2;
+  return (((ne & m) + m) | ne) & ~m;
+#endif
+}
+
 #endif /* _STRING_FZA_H */
diff --git ./sysdeps/powerpc/string-fza.h ./sysdeps/powerpc/string-fza.h
index 43aa0db952..9b6ab905ac 100644
--- ./sysdeps/powerpc/string-fza.h
+++ ./sysdeps/powerpc/string-fza.h
@@ -60,6 +60,15 @@ find_zero_ne_all (op_t x1, op_t x2)
   return find_zero_all (x1) | ~find_eq_all (x1, x2);
 }
 
+/* Identify bytes that are not equal between X1 and X2.  */
+
+static __always_inline find_t
+find_ne_all (op_t x1, op_t x2)
+{
+  /* The difference need not be reduced; see the generic string-fza.h.  */
+  return x1 ^ x2;
+}
+
 /* Define the "inexact" versions in terms of the exact versions.  */
 # define find_zero_low		find_zero_all
 # define find_eq_low		find_eq_all
diff --git ./sysdeps/riscv/string-fza.h ./sysdeps/riscv/string-fza.h
index 7df4dfe415..add1861437 100644
--- ./sysdeps/riscv/string-fza.h
+++ ./sysdeps/riscv/string-fza.h
@@ -63,6 +63,14 @@ find_zero_ne_all (op_t x1, op_t x2)
   return find_zero_all (x1) | ~find_eq_all (x1, x2);
 }
 
+/* Identify bytes that are not equal between X1 and X2.  */
+static __always_inline find_t
+find_ne_all (op_t x1, op_t x2)
+{
+  /* The difference need not be reduced; see the generic string-fza.h.  */
+  return x1 ^ x2;
+}
+
 /* Define the "inexact" versions in terms of the exact versions.  */
 # define find_zero_low		find_zero_all
 # define find_eq_low		find_eq_all
diff --git ./sysdeps/riscv/string-fzi.h ./sysdeps/riscv/string-fzi.h
index 613e5789e4..1e398681fd 100644
--- ./sysdeps/riscv/string-fzi.h
+++ ./sysdeps/riscv/string-fzi.h
@@ -29,23 +29,23 @@
 static __always_inline unsigned int
 index_first (find_t c)
 {
-  if (c & 0x80U)
+  if (c & 0xffU)
     return 0;
-  if (c & 0x8000U)
+  if (c & 0xff00U)
     return 1;
-  if (c & 0x800000U)
+  if (c & 0xff0000U)
     return 2;
 
   if (sizeof (op_t) == 4)
     return 3;
 
-  if (c & 0x80000000U)
+  if (c & 0xff000000U)
     return 3;
-  if (c & 0x8000000000UL)
+  if (c & 0xff00000000UL)
     return 4;
-  if (c & 0x800000000000UL)
+  if (c & 0xff0000000000UL)
     return 5;
-  if (c & 0x80000000000000UL)
+  if (c & 0xff000000000000UL)
     return 6;
   return 7;
 }
@@ -55,20 +55,20 @@ index_last (find_t c)
 {
   if (sizeof (op_t) == 8)
     {
-      if (c & 0x8000000000000000UL)
+      if (c & 0xff00000000000000UL)
 	return 7;
-      if (c & 0x80000000000000UL)
+      if (c & 0xff000000000000UL)
 	return 6;
-      if (c & 0x800000000000UL)
+      if (c & 0xff0000000000UL)
 	return 5;
-      if (c & 0x8000000000UL)
+      if (c & 0xff00000000UL)
 	return 4;
     }
-  if (c & 0x80000000U)
+  if (c & 0xff000000U)
     return 3;
-  if (c & 0x800000U)
+  if (c & 0xff0000U)
     return 2;
-  if (c & 0x8000U)
+  if (c & 0xff00U)
     return 1;
   return 0;
 }
-- 
2.54.0