This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH 3/4] Use pointers for traversing arrays in strstr, strcasestrand memmem.
- From: Carlos O'Donell <carlos_odonell at mentor dot com>
- To: Maxim Kuvyrkov <maxim at codesourcery dot com>
- Cc: Carlos O'Donell <carlos at codesourcery dot com>, 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: Thu, 16 Aug 2012 22:51:13 -0400
- Subject: Re: [PATCH 3/4] Use pointers for traversing arrays in strstr, strcasestrand memmem.
- References: <2C516CF2-D083-4C1D-AD27-6A31D381D548@codesourcery.com> <D2F81944-1466-4374-93E4-C347F5475ACF@codesourcery.com>
On 5/30/2012 5:11 AM, Maxim Kuvyrkov wrote:
> [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;
(1) Use a meaningful variable name please.
>
> /* 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 *
>
OK with change (1).
Cheers,
Carlos.
--
Carlos O'Donell
Mentor Graphics / CodeSourcery
carlos_odonell@mentor.com
carlos@codesourcery.com
+1 (613) 963 1026