Add string vectorized find and detection functions

This patch adds generic string find and detection meant to be used in
generic vectorized string implementation.  The idea is to decompose the
basic string operation so each architecture can reimplement if it
provides any specialized hardware instruction.

The 'string-misc.h' provides miscellaneous functions:

  - extractbyte: extracts the byte from an specific index.
  - repeat_bytes: setup an word by replicate the argument on each byte.

The 'string-fza.h' provides zero byte detection functions:

  - find_zero_low, find_zero_all, find_eq_low, find_eq_all,
    find_zero_eq_low, find_zero_eq_all, and find_zero_ne_all

The 'string-fzb.h' provides boolean zero byte detection functions:

  - has_zero: determine if any byte within a word is zero.
  - has_eq: determine byte equality between two words.
  - has_zero_eq: determine if any byte within a word is zero along with
    byte equality between two words.

The 'string-fzi.h' provides positions for string-fza.h results:

  - index_first: return index of first zero byte within a word.
  - index_last: return index of first byte different between two words.

The 'string-fzc.h' provides a combined version of fza and fzi:

  - index_first_zero_eq: return index of first zero byte within a word or
    first byte different between two words.
  - index_first_zero_ne: return index of first zero byte within a word or
    first byte equal between two words.
  - index_last_zero: return index of last zero byte within a word.
  - index_last_eq: return index of last byte different between two words.

The 'string-shift.h' provides a way to mask off parts of a work based on
some alignmnet (to handle unaligned arguments):

  - shift_find, shift_find_last.

Co-authored-by: Richard Henderson <richard.henderson@linaro.org>
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>

1 files changed, 71 insertions, 0 deletions

diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h
new file mode 100644
index 0000000..2deecef
--- /dev/null
+++ b/sysdeps/generic/string-fzi.h
@@ -0,0 +1,71 @@
+/* Zero byte detection; indexes.  Generic C version.
+   Copyright (C) 2023 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef _STRING_FZI_H
+#define _STRING_FZI_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-fza.h>
+
+static __always_inline int
+clz (find_t c)
+{
+  if (sizeof (find_t) == sizeof (unsigned long))
+    return __builtin_clzl (c);
+  else
+    return __builtin_clzll (c);
+}
+
+static __always_inline int
+ctz (find_t c)
+{
+  if (sizeof (find_t) == sizeof (unsigned long))
+    return __builtin_ctzl (c);
+  else
+    return __builtin_ctzll (c);
+}
+
+/* A subroutine for the index_zero functions.  Given a test word C, return
+   the (memory order) index of the first byte (in memory order) that is
+   non-zero.  */
+static __always_inline unsigned int
+index_first (find_t c)
+{
+  int r;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    r = ctz (c);
+  else
+    r = clz (c);
+  return r / CHAR_BIT;
+}
+
+/* Similarly, but return the (memory order) index of the last byte that is
+   non-zero.  */
+static __always_inline unsigned int
+index_last (find_t c)
+{
+  int r;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    r = clz (c);
+  else
+    r = ctz (c);
+  return sizeof (find_t) - 1 - (r / CHAR_BIT);
+}
+
+#endif /* STRING_FZI_H */