[PATCH 05/11] Improve generic strrchr

[Richard Henderson <rth at twiddle dot net>]

     * string/strrchr.c: Use haszero.h.
---
 string/strrchr.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 56 insertions(+), 11 deletions(-)

diff --git a/string/strrchr.c b/string/strrchr.c
index a07457e..bea7d76 100644
--- a/string/strrchr.c
+++ b/string/strrchr.c
@@ -16,6 +16,10 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
+#include <stdint.h>
+#include <haszero.h>
+#include <whichzero.h>
+#include <extractbyte.h>
 
 #undef strrchr
 
@@ -25,25 +29,66 @@
 
 /* Find the last occurrence of C in S.  */
 char *
-STRRCHR (const char *s, int c)
+STRRCHR (const char *s, int int_c)
 {
-  const char *found, *p;
+  const unsigned char *found_c = NULL, *ptr_c;
+  const unsigned long int *found_w = NULL, *ptr_w;
+  unsigned long int longword, repeated_c;
+  uintptr_t i, align;
+  unsigned char c;
 
-  c = (unsigned char) c;
+  c = (unsigned char) int_c;
+  ptr_c = (const unsigned char *) s;
 
-  /* Since strchr is fast, we use it rather than the obvious loop.  */
+  /* Handle the first few characters by reading one character at a time.
+     Do this until CHAR_PTR is aligned on a longword boundary.  */
+  align = -(uintptr_t)ptr_c % sizeof(longword);
+  for (i = 0; i < align; ++i, ++ptr_c)
+    {
+      unsigned char this_c = *ptr_c;
+      if (this_c == c)
+        found_c = ptr_c;
+      if (this_c == '\0')
+        goto done;
+    }
+
+  /* Set up a longword, each of whose bytes is C.  */
+  repeated_c = (-1ul / 0xff) * c;
+
+  /* Search words for C.  At this point, merely record the last word
+     that contained the character.  Stop when we find EOS.  */
+  ptr_w = (const unsigned long int *) ptr_c;
+  while (1)
+    {
+      longword = *ptr_w;
+      if (haszero (longword))
+	break;
+      if (haszero (longword ^ repeated_c))
+	found_w = ptr_w;
+      ptr_w++;
+    }
 
-  if (c == '\0')
-    return strchr (s, '\0');
+  /* Check to see if we've got C in the last longword.  */
+  i = whichzero2 (longword, longword ^ repeated_c);
+  if (extractbyte (longword, i) == c)
+    found_w = ptr_w;
 
-  found = NULL;
-  while ((p = strchr (s, c)) != NULL)
+  /* If we found a word containing C, go back and search it byte by byte.  */
+  if (found_w)
     {
-      found = p;
-      s = p + 1;
+      ptr_c = (const unsigned char *) found_w;
+      for (i = 0; i < sizeof(longword); ++i, ++ptr_c)
+	{
+	  unsigned char this_c = *ptr_c;
+	  if (this_c == c)
+	    found_c = ptr_c;
+	  if (this_c == '\0')
+	    break;
+	}
     }
 
-  return (char *) found;
+ done:
+  return (char *) found_c;
 }
 
 #ifdef weak_alias
-- 
2.9.3