This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH v2 07/16] Improve generic strrchr


	* string/strrchr.c: Use string-fzb.h and string-fzi.h.
---
 string/strrchr.c | 76 +++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 61 insertions(+), 15 deletions(-)

diff --git a/string/strrchr.c b/string/strrchr.c
index a07457e..09c1043 100644
--- a/string/strrchr.c
+++ b/string/strrchr.c
@@ -16,38 +16,84 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
+#include <stdint.h>
+#include <string-fzb.h>
+#include <string-fzi.h>
+#include <string-extbyte.h>
 
 #undef strrchr
+#undef rindex
 
-#ifndef STRRCHR
-# define STRRCHR strrchr
+#ifdef STRRCHR
+#define strrchr STRRCHR
 #endif
 
 /* 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 op_t *found_w = NULL, *ptr_w;
+  op_t word, 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 word boundary.  */
+  align = -(uintptr_t)ptr_c % sizeof(word);
+  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')
+        return (char *) found_c;
+    }
 
-  if (c == '\0')
-    return strchr (s, '\0');
+  /* Set up a word, each of whose bytes is C.  */
+  repeated_c = ((op_t)-1 / 0xff) * c;
 
-  found = NULL;
-  while ((p = strchr (s, c)) != NULL)
+  /* Search words for C.  At this point, merely record the last word
+     that contained the character.  Stop when we find EOS.  */
+  ptr_w = (const op_t *) ptr_c;
+  while (1)
     {
-      found = p;
-      s = p + 1;
+      word = *ptr_w;
+      if (has_zero (word))
+	break;
+      if (has_eq (word, repeated_c))
+	found_w = ptr_w;
+      ptr_w++;
     }
 
-  return (char *) found;
+  /* Check to see if we've got C in the last word.  */
+  i = index_first_zero_eq (word, repeated_c);
+  if (extractbyte (word, i) == c)
+    found_w = ptr_w;
+
+  /* If we found a word containing C, go back and search it byte by byte.
+     This is probably cheaper than indexing for the zero within WORD,
+     using that to mask out following bytes that might be C, and then
+     indexing to find the last C.  */
+  if (found_w)
+    {
+      ptr_c = (const unsigned char *) found_w;
+      for (i = 0; i < sizeof (word); ++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_c;
 }
 
-#ifdef weak_alias
-#undef rindex
+#ifndef STRRCHR
 weak_alias (strrchr, rindex)
 #endif
 libc_hidden_builtin_def (strrchr)
-- 
2.9.3


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]