[v3,07/18] string: Improve generic memrchr

Message ID 1515588482-15744-8-git-send-email-adhemerval.zanella@linaro.org
State New
Headers show
Series
  • Improve generic string routines
Related show

Commit Message

Adhemerval Zanella Jan. 10, 2018, 12:47 p.m.
From: Richard Henderson <rth@twiddle.net>

New algorithm have the following key differences:

  - Use string-fz{b,i} functions.

It also cleanups the multiple inclusion by leaving the ifunc
implementation to undef the weak_alias.

Checked on x86_64-linux-gnu, i686-linux-gnu, sparc64-linux-gnu,
and sparcv9-linux-gnu by removing the arch-specific assembly
implementation and disabling multi-arch (it covers both LE and BE
for 64 and 32 bits).

	Richard Henderson  <rth@twiddle.net>
	Adhemerval Zanella  <adhemerval.zanella@linaro.org>

	[BZ #5806]
	* string/memrchr.c: Use string-fzb.h, string-fzi.h.
	* sysdeps/i386/i686/multiarch/memrchr-c.c: Redefined weak_alias.
	* sysdeps/s390/multiarch/memrchr-c.c: Likewise.
---
 string/memrchr.c                        | 193 +++++++-------------------------
 sysdeps/i386/i686/multiarch/memrchr-c.c |   2 +
 sysdeps/s390/multiarch/memrchr-c.c      |   2 +
 3 files changed, 44 insertions(+), 153 deletions(-)

Patch

diff --git a/string/memrchr.c b/string/memrchr.c
index 191b89a..5ae9c81 100644
--- a/string/memrchr.c
+++ b/string/memrchr.c
@@ -21,177 +21,64 @@ 
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#include <stdlib.h>
-
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
-
-#if defined _LIBC
-# include <string.h>
-# include <memcopy.h>
-#endif
-
-#if defined HAVE_LIMITS_H || defined _LIBC
-# include <limits.h>
-#endif
-
-#define LONG_MAX_32_BITS 2147483647
-
-#ifndef LONG_MAX
-# define LONG_MAX LONG_MAX_32_BITS
-#endif
-
-#include <sys/types.h>
+#include <string.h>
+#include <stdint.h>
+#include <limits.h>
+#include <string-fzb.h>
+#include <string-fzi.h>
+#include <string-opthr.h>
+#include <string-maskoff.h>
 
 #undef __memrchr
 #undef memrchr
 
-#ifndef weak_alias
-# define __memrchr memrchr
+#ifndef MEMRCHR
+# define MEMRCHR __memrchr
 #endif
 
-/* Search no more than N bytes of S for C.  */
 void *
-#ifndef MEMRCHR
-__memrchr
-#else
-MEMRCHR
-#endif
-     (const void *s, int c_in, size_t n)
+MEMRCHR (const void *s, int c_in, size_t n)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
+  uintptr_t s_int = (uintptr_t) s;
+  uintptr_t lbyte_int = s_int + n;
 
   /* Handle the last few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s + n;
-       n > 0 && ((unsigned long int) char_ptr
-		 & (sizeof (longword) - 1)) != 0;
-       --n)
-    if (*--char_ptr == c)
+     Do this until CHAR_PTR is aligned on a word boundary, or
+     the entirety of small inputs.  */
+  const unsigned char *char_ptr = (const unsigned char *) lbyte_int;
+  size_t align = lbyte_int % sizeof (op_t);
+  if (n < OP_T_THRES || align > n)
+    align = n;
+  for (size_t i = 0; i < align; ++i)
+    if (*--char_ptr == c_in)
       return (void *) char_ptr;
 
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (const unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  magic_bits = -1;
-  magic_bits = magic_bits / 0xff * 0xfe << 1 >> 1 | 1;
+  const op_t *word_ptr = (const op_t *) char_ptr;
+  n -= align;
+  if (__glibc_unlikely (n == 0))
+    return NULL;
 
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-#if LONG_MAX > LONG_MAX_32_BITS
-  charmask |= charmask << 32;
-#endif
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (n >= sizeof (longword))
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C, not zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *--longword_ptr ^ charmask;
+  /* Compute the address of the word containing the initial byte. */
+  const op_t *lword = (const op_t *) (s_int & -sizeof (op_t));
 
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
+  /* Set up a word, each of whose bytes is C.  */
+  op_t repeated_c = repeat_bytes (c_in);
 
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
+  char *ret;
+  op_t word;
 
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) longword_ptr;
-
-#if LONG_MAX > 2147483647
-	  if (cp[7] == c)
-	    return (void *) &cp[7];
-	  if (cp[6] == c)
-	    return (void *) &cp[6];
-	  if (cp[5] == c)
-	    return (void *) &cp[5];
-	  if (cp[4] == c)
-	    return (void *) &cp[4];
-#endif
-	  if (cp[3] == c)
-	    return (void *) &cp[3];
-	  if (cp[2] == c)
-	    return (void *) &cp[2];
-	  if (cp[1] == c)
-	    return (void *) &cp[1];
-	  if (cp[0] == c)
-	    return (void *) cp;
-	}
-
-      n -= sizeof (longword);
-    }
-
-  char_ptr = (const unsigned char *) longword_ptr;
-
-  while (n-- > 0)
+  while (word_ptr != lword)
     {
-      if (*--char_ptr == c)
-	return (void *) char_ptr;
+      word = *--word_ptr;
+      if (has_eq (word, repeated_c))
+	goto found;
     }
+  return NULL;
 
-  return 0;
+found:
+  /* We found a match, but it might be in a byte past the start 
+     of the array.  */
+  ret = (char *) word_ptr + index_last_eq (word, repeated_c);
+  return (ret >= (char*) s) ? ret : NULL;
 }
-#ifndef MEMRCHR
-# ifdef weak_alias
 weak_alias (__memrchr, memrchr)
-# endif
-#endif
diff --git a/sysdeps/i386/i686/multiarch/memrchr-c.c b/sysdeps/i386/i686/multiarch/memrchr-c.c
index ef7bbbe..23c937b 100644
--- a/sysdeps/i386/i686/multiarch/memrchr-c.c
+++ b/sysdeps/i386/i686/multiarch/memrchr-c.c
@@ -1,5 +1,7 @@ 
 #if IS_IN (libc)
 # define MEMRCHR  __memrchr_ia32
+# undef weak_alias
+# define weak_alias(a,b)
 # include <string.h>
 extern void *__memrchr_ia32 (const void *, int, size_t);
 #endif
diff --git a/sysdeps/s390/multiarch/memrchr-c.c b/sysdeps/s390/multiarch/memrchr-c.c
index 1e3c914..d7e59a4 100644
--- a/sysdeps/s390/multiarch/memrchr-c.c
+++ b/sysdeps/s390/multiarch/memrchr-c.c
@@ -18,6 +18,8 @@ 
 
 #if defined HAVE_S390_VX_ASM_SUPPORT && IS_IN (libc)
 # define MEMRCHR  __memrchr_c
+# undef weak_alias
+# define weak_alias(a,b)
 
 # include <string.h>
 extern __typeof (__memrchr) __memrchr_c;