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 3/4] Use pointers for traversing arrays in strstr, strcasestr and memmem.

From: Maxim Kuvyrkov <maxim at codesourcery dot com>
To: Carlos O'Donell <carlos at codesourcery dot com>
Cc: GLIBC Devel <libc-alpha at sourceware dot org>, Eric Blake <eblake at redhat dot com>,Ryan Arnold <rsa at us dot ibm dot com>
Date: Wed, 30 May 2012 21:11:17 +1200
Subject: [PATCH 3/4] Use pointers for traversing arrays in strstr, strcasestr and memmem.
References: <2C516CF2-D083-4C1D-AD27-6A31D381D548@codesourcery.com>

[PATCH 3/4] Use pointers for traversing arrays in strstr, strcasestr and memmem.

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics


	* string/str-two-way.h (two_way_short_needle): Use pointers instead of
	array references.
	* string/strcasestr.c (TOLOWER): Make side-effect safe.
---
 string/str-two-way.h |   65 ++++++++++++++++++++++++++++++++++++-------------
 string/strcasestr.c  |    2 +-
 2 files changed, 49 insertions(+), 18 deletions(-)

diff --git a/string/str-two-way.h b/string/str-two-way.h
index db7f374..b6e17e4 100644
--- a/string/str-two-way.h
+++ b/string/str-two-way.h
@@ -243,17 +243,24 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
       j = 0;
       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 	{
+	  const unsigned char *pneedle;
+	  const unsigned char *phaystack;
+
 	  /* Scan for matches in right half.  */
 	  i = MAX (suffix, memory);
-	  while (i < needle_len && (CANON_ELEMENT (needle[i])
-				    == CANON_ELEMENT (haystack[i + j])))
+	  pneedle = &needle[i];
+	  phaystack = &haystack[i + j];
+	  while (i < needle_len && (CANON_ELEMENT (*pneedle++)
+				    == CANON_ELEMENT (*phaystack++)))
 	    ++i;
 	  if (needle_len <= i)
 	    {
 	      /* Scan for matches in left half.  */
 	      i = suffix - 1;
-	      while (memory < i + 1 && (CANON_ELEMENT (needle[i])
-					== CANON_ELEMENT (haystack[i + j])))
+	      pneedle = &needle[i];
+	      phaystack = &haystack[i + j];
+	      while (memory < i + 1 && (CANON_ELEMENT (*pneedle--)
+					== CANON_ELEMENT (*phaystack--)))
 		--i;
 	      if (i + 1 < memory + 1)
 		return (RETURN_TYPE) (haystack + j);
@@ -271,6 +278,7 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
     }
   else
     {
+      const unsigned char *phaystack = &haystack[suffix];
       /* The comparison always starts from needle[suffix], so cache it
 	 and use an optimized first-character loop.  */
       unsigned char needle_suffix = CANON_ELEMENT (needle[suffix]);
@@ -282,23 +290,28 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
       while (AVAILABLE1 (haystack, haystack_len, j, needle_len))
 	{
 	  unsigned char a;
+	  const unsigned char *pneedle;
 
 	  /* TODO: The first-character loop can be sped up by adapting
 	     longword-at-a-time implementation of memchr/strchr.  */
 	  if (needle_suffix
-	      != (a = CANON_ELEMENT (haystack[suffix + j])))
+	      != (a = CANON_ELEMENT (*phaystack++)))
 	    {
 	      RET0_IF_0 (a);
 	      ++j;
 	      continue;
 	    }
 
+	  /* Calculate J.  */
+	  j = phaystack - &haystack[suffix] - 1;
+
 	  /* Scan for matches in right half.  */
 	  i = suffix + 1;
+	  pneedle = &needle[i];
 	  while (i < needle_len)
 	    {
-	      if (CANON_ELEMENT (needle[i])
-		  != (a = CANON_ELEMENT (haystack[i + j])))
+	      if (CANON_ELEMENT (*pneedle++)
+		  != (a = CANON_ELEMENT (*phaystack++)))
 		{
 		  RET0_IF_0 (a);
 		  break;
@@ -309,10 +322,12 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 	    {
 	      /* Scan for matches in left half.  */
 	      i = suffix - 1;
+	      pneedle = &needle[i];
+	      phaystack = &haystack[i + j];
 	      while (i != SIZE_MAX)
 		{
-		  if (CANON_ELEMENT (needle[i])
-		      != (a = CANON_ELEMENT (haystack[i + j])))
+		  if (CANON_ELEMENT (*pneedle--)
+		      != (a = CANON_ELEMENT (*phaystack--)))
 		    {
 		      RET0_IF_0 (a);
 		      break;
@@ -328,6 +343,8 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 
 	  if (!AVAILABLE2 (haystack, haystack_len, j, needle_len))
 	    break;
+
+	  phaystack = &haystack[suffix + j];
 	}
     }
  ret0: __attribute__ ((unused))
@@ -382,6 +399,9 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
       j = 0;
       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 	{
+	  const unsigned char *pneedle;
+	  const unsigned char *phaystack;
+
 	  /* Check the last byte first; if it does not match, then
 	     shift to the next possible match location.  */
 	  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
@@ -401,15 +421,19 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 	  /* Scan for matches in right half.  The last byte has
 	     already been matched, by virtue of the shift table.  */
 	  i = MAX (suffix, memory);
-	  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
-					== CANON_ELEMENT (haystack[i + j])))
+	  pneedle = &needle[i];
+	  phaystack = &haystack[i + j];
+	  while (i < needle_len - 1 && (CANON_ELEMENT (*pneedle++)
+					== CANON_ELEMENT (*phaystack++)))
 	    ++i;
 	  if (needle_len - 1 <= i)
 	    {
 	      /* Scan for matches in left half.  */
 	      i = suffix - 1;
-	      while (memory < i + 1 && (CANON_ELEMENT (needle[i])
-					== CANON_ELEMENT (haystack[i + j])))
+	      pneedle = &needle[i];
+	      phaystack = &haystack[i + j];
+	      while (memory < i + 1 && (CANON_ELEMENT (*pneedle--)
+					== CANON_ELEMENT (*phaystack--)))
 		--i;
 	      if (i + 1 < memory + 1)
 		return (RETURN_TYPE) (haystack + j);
@@ -434,6 +458,9 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
       j = 0;
       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 	{
+	  const unsigned char *pneedle;
+	  const unsigned char *phaystack;
+
 	  /* Check the last byte first; if it does not match, then
 	     shift to the next possible match location.  */
 	  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
@@ -445,15 +472,19 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 	  /* Scan for matches in right half.  The last byte has
 	     already been matched, by virtue of the shift table.  */
 	  i = suffix;
-	  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
-					== CANON_ELEMENT (haystack[i + j])))
+	  pneedle = &needle[i];
+	  phaystack = &haystack[i + j];
+	  while (i < needle_len - 1 && (CANON_ELEMENT (*pneedle++)
+					== CANON_ELEMENT (*phaystack++)))
 	    ++i;
 	  if (needle_len - 1 <= i)
 	    {
 	      /* Scan for matches in left half.  */
 	      i = suffix - 1;
-	      while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
-				       == CANON_ELEMENT (haystack[i + j])))
+	      pneedle = &needle[i];
+	      phaystack = &haystack[i + j];
+	      while (i != SIZE_MAX && (CANON_ELEMENT (*pneedle--)
+				       == CANON_ELEMENT (*phaystack--)))
 		--i;
 	      if (i == SIZE_MAX)
 		return (RETURN_TYPE) (haystack + j);
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 184ca68..b6458ae 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -36,7 +36,7 @@
 #include <stdbool.h>
 #include <strings.h>
 
-#define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
+#define TOLOWER(Ch) tolower (Ch)
 
 /* Two-Way algorithm.  */
 #define RETURN_TYPE char *
-- 
1.7.4.1

References:
- [PATCH] Optimize strstr, strcasestr and memmem
  - From: Maxim Kuvyrkov

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