This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
[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