[prev in list] [next in list] [prev in thread] [next in thread]
List: glibc-cvs
Subject: GNU C Library master sources branch azanella/str-two-way-optimization created. glibc-2.27.9000-529-g
From: azanella () sourceware ! org
Date: 2018-06-29 19:22:02
Message-ID: 20180629192202.99384.qmail () sourceware ! org
[Download RAW message or body]
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".
The branch, azanella/str-two-way-optimization has been created
at 6cc58a9708ff256323c34d200fd9362f25bf66f7 (commit)
- Log -----------------------------------------------------------------
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=6cc58a9708ff256323c34d200fd9362f25bf66f7
commit 6cc58a9708ff256323c34d200fd9362f25bf66f7
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date: Thu Jun 28 20:57:20 2018 +0000
Improve strstr/strcasestr/memmem performance
Strstr tends to be slow because it uses many calls to memchr and a slow
byte loop to scan for the next match. Performance is significantly
improved by using strnlen on larger blocks and using strchr to search
for the next matching character. strcasestr can also use strnlen to
scan ahead, and memmem can use memchr to check for the next match.
On the GLIBC bench tests the overall performance gains on Cortex-A72 are:
strstr: +25%
strcasestr: +4.3%
memmem: +18%
On a 256KB dataset strstr performance improves by 67%, strcasestr by 47%.
Checked on aarch64-linux-gnu.
* string/memmem.c (FASTSEARCH): Define.
* string/strcasestr.c (AVAILABLE): Use read-ahead strnlen.
* string/strstr.c (AVAILABLE): Use read-ahead strnlen.
* benchtests/bench-strcasestr.c (__strnlen): Define to strnlen.
* benchtests/bench-strstr.c (__strnlen): Likewise.
* string/test-strcasestr.c (__strnlen): Likewise.
* string/test-strstr.c (__strnlen): Likewise.
diff --git a/ChangeLog b/ChangeLog
index dcbb0dd..6688a37 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2018-06-29 Wilco Dijkstra <wdijkstr@arm.com>
+
+ * string/memmem.c (FASTSEARCH): Define.
+ * string/strcasestr.c (AVAILABLE): Use read-ahead strnlen.
+ * string/strstr.c (AVAILABLE): Use read-ahead strnlen.
+ * benchtests/bench-strcasestr.c (__strnlen): Define to strnlen.
+ * benchtests/bench-strstr.c (__strnlen): Likewise.
+ * string/test-strcasestr.c (__strnlen): Likewise.
+ * string/test-strstr.c (__strnlen): Likewise.
+
2018-06-29 Adhemerval Zanella <adhemerval.zanella@linaro.org>
* string/memmem.c: Sync with gnulib.
diff --git a/benchtests/bench-strcasestr.c b/benchtests/bench-strcasestr.c
index e6659ea..dc2d5e8 100644
--- a/benchtests/bench-strcasestr.c
+++ b/benchtests/bench-strcasestr.c
@@ -22,6 +22,7 @@
#define STRCASESTR simple_strcasestr
+#define __strnlen strnlen
#define NO_ALIAS
#define __strncasecmp strncasecmp
#include "../string/strcasestr.c"
diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index c30cd10..6b96acd 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -22,6 +22,7 @@
#define STRSTR simple_strstr
+#define __strnlen strnlen
#define libc_hidden_builtin_def(X)
#include "../string/strstr.c"
diff --git a/string/memmem.c b/string/memmem.c
index c8e0fb3..1e0b562 100644
--- a/string/memmem.c
+++ b/string/memmem.c
@@ -26,6 +26,7 @@
#define RETURN_TYPE void *
#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
+#define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N))
#include "str-two-way.h"
/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 1a2c713..87881d2 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -28,8 +28,9 @@
/* Two-Way algorithm. */
#define RETURN_TYPE char *
#define AVAILABLE(h, h_l, j, n_l) \
- (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
- && ((h_l) = (j) + (n_l)))
+ (((j) + (n_l) <= (h_l)) \
+ || ((h_l) += __strnlen ((void*)((h) + (h_l)), 512), \
+ (j) + (n_l) <= (h_l)))
#define CANON_ELEMENT(c) TOLOWER (c)
#define CMP_FUNC(p1, p2, l) \
__strncasecmp ((const char *) (p1), (const char *) (p2), l)
diff --git a/string/strstr.c b/string/strstr.c
index eb30fe7..27a4634 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -29,8 +29,9 @@
#define RETURN_TYPE char *
#define AVAILABLE(h, h_l, j, n_l) \
- (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
- && ((h_l) = (j) + (n_l)))
+ (((j) + (n_l) <= (h_l)) \
+ || ((h_l) += __strnlen ((void*)((h) + (h_l)), 512), \
+ (j) + (n_l) <= (h_l)))
#include "str-two-way.h"
#ifndef STRSTR
diff --git a/string/test-strcasestr.c b/string/test-strcasestr.c
index 2b0a38e..eaa36c4 100644
--- a/string/test-strcasestr.c
+++ b/string/test-strcasestr.c
@@ -23,6 +23,7 @@
#define STRCASESTR simple_strcasestr
+#define __strnlen strnlen
#define NO_ALIAS
#define __strncasecmp strncasecmp
#include "strcasestr.c"
diff --git a/string/test-strstr.c b/string/test-strstr.c
index acf6ff8..4bdfff7 100644
--- a/string/test-strstr.c
+++ b/string/test-strstr.c
@@ -23,6 +23,7 @@
#define STRSTR simple_strstr
+#define __strnlen strnlen
#define libc_hidden_builtin_def(arg) /* nothing */
#include "strstr.c"
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=482241fb1da0ea615a2b9ea9aad795f1247f188a
commit 482241fb1da0ea615a2b9ea9aad795f1247f188a
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Thu Jun 28 20:07:54 2018 +0000
Sync memmem/strcasestr/strstr generic implementation with gnulib
This patch syncs with gnulib implementation (commit id 7729b92621).
* string/memmem.c: Sync with gnulib.
* string/strcasestr.c: Likewise.
* string/strstr.c: Likewise.
* string/str-two-way.h: Likewise.
diff --git a/ChangeLog b/ChangeLog
index 1f35f29..dcbb0dd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2018-06-29 Adhemerval Zanella <adhemerval.zanella@linaro.org>
+
+ * string/memmem.c: Sync with gnulib.
+ * string/strcasestr.c: Likewise.
+ * string/strstr.c: Likewise.
+ * string/str-two-way.h: Likewise.
+
2018-06-28 Szabolcs Nagy <szabolcs.nagy@arm.com>
* manual/llio.texi: Remove spurious space.
diff --git a/string/memmem.c b/string/memmem.c
index c17e1cf..c8e0fb3 100644
--- a/string/memmem.c
+++ b/string/memmem.c
@@ -24,17 +24,10 @@
/* Specification of memmem. */
#include <string.h>
-#ifndef _LIBC
-# define __builtin_expect(expr, val) (expr)
-# define __memmem memmem
-#endif
-
#define RETURN_TYPE void *
#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
#include "str-two-way.h"
-#undef memmem
-
/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
HAYSTACK. */
diff --git a/string/str-two-way.h b/string/str-two-way.h
index cd26058..61b67c2 100644
--- a/string/str-two-way.h
+++ b/string/str-two-way.h
@@ -17,31 +17,27 @@
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
-/* Before including this file, you need to include <string.h> (and
- <config.h> before that, if not part of libc), and define:
- RETURN_TYPE A macro that expands to the return type.
+/* Before including this file, you need to include <config.h> and
+ <string.h>, and define:
+ RESULT_TYPE A macro that expands to the return type.
AVAILABLE(h, h_l, j, n_l)
- A macro that returns nonzero if there are
- at least N_L bytes left starting at H[J].
- H is 'unsigned char *', H_L, J, and N_L
- are 'size_t'; H_L is an lvalue. For
- NUL-terminated searches, H_L can be
- modified each iteration to avoid having
- to compute the end of H up front.
+ A macro that returns nonzero if there are
+ at least N_L bytes left starting at H[J].
+ H is 'unsigned char *', H_L, J, and N_L
+ are 'size_t'; H_L is an lvalue. For
+ NUL-terminated searches, H_L can be
+ modified each iteration to avoid having
+ to compute the end of H up front.
For case-insensitivity, you may optionally define:
CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L
- characters of P1 and P2 are equal.
+ characters of P1 and P2 are equal.
CANON_ELEMENT(c) A macro that canonicalizes an element right after
- it has been fetched from one of the two strings.
- The argument is an 'unsigned char'; the result
- must be an 'unsigned char' as well.
+ it has been fetched from one of the two strings.
+ The argument is an 'unsigned char'; the result
+ must be an 'unsigned char' as well.
- Other macros you may optionally define:
- RET0_IF_0(a) Documented below at default definition.
- CHECK_EOL Same.
-
- This file undefines the macros listed above, and defines
+ This file undefines the macros documented above, and defines
LONG_NEEDLE_THRESHOLD.
*/
@@ -49,14 +45,15 @@
#include <stdint.h>
#include <sys/param.h> /* Defines MAX. */
-/* We use the Two-Way string matching algorithm, which guarantees
- linear complexity with constant space. Additionally, for long
- needles, we also use a bad character shift table similar to the
- Boyer-Moore algorithm to achieve improved (potentially sub-linear)
- performance.
+/* We use the Two-Way string matching algorithm (also known as
+ Chrochemore-Perrin), which guarantees linear complexity with
+ constant space. Additionally, for long needles, we also use a bad
+ character shift table similar to the Boyer-Moore algorithm to
+ achieve improved (potentially sub-linear) performance.
- See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
- and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
+ See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260,
+ https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm,
+ https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.6641&rep=rep1&type=pdf
*/
/* Point at which computing a bad-byte shift table is likely to be
@@ -72,6 +69,10 @@
# define LONG_NEEDLE_THRESHOLD SIZE_MAX
#endif
+#ifndef MAX
+# define MAX(a, b) ((a < b) ? (b) : (a))
+#endif
+
#ifndef CANON_ELEMENT
# define CANON_ELEMENT(c) c
#endif
@@ -79,18 +80,6 @@
# define CMP_FUNC memcmp
#endif
-/* Check for end-of-line in strstr and strcasestr routines.
- We piggy-back matching procedure for detecting EOL where possible,
- and use AVAILABLE macro otherwise. */
-#ifndef CHECK_EOL
-# define CHECK_EOL (0)
-#endif
-
-/* Return NULL if argument is '\0'. */
-#ifndef RET0_IF_0
-# define RET0_IF_0(a) /* nothing */
-#endif
-
/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
Return the index of the first byte in the right half, and set
*PERIOD to the global period of the right half.
@@ -108,15 +97,18 @@
A critical factorization has the property that the local period
equals the global period. All strings have at least one critical
factorization with the left half smaller than the global period.
+ And while some strings have more than one critical factorization,
+ it is provable that with an ordered alphabet, at least one of the
+ critical factorizations corresponds to a maximal suffix.
Given an ordered alphabet, a critical factorization can be computed
in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
- larger of two ordered maximal suffixes. The ordered maximal
- suffixes are determined by lexicographic comparison of
+ shorter of two ordered maximal suffixes. The ordered maximal
+ suffixes are determined by lexicographic comparison while tracking
periodicity. */
static size_t
critical_factorization (const unsigned char *needle, size_t needle_len,
- size_t *period)
+ size_t *period)
{
/* Index of last byte of left half, or SIZE_MAX. */
size_t max_suffix, max_suffix_rev;
@@ -125,6 +117,14 @@ critical_factorization (const unsigned char *needle, size_t needle_len,
size_t p; /* Intermediate period. */
unsigned char a, b; /* Current comparison bytes. */
+ /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
+ out 0-length needles. */
+ if (needle_len < 3)
+ {
+ *period = 1;
+ return needle_len - 1;
+ }
+
/* Invariants:
0 <= j < NEEDLE_LEN - 1
-1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
@@ -143,29 +143,29 @@ critical_factorization (const unsigned char *needle, size_t needle_len,
a = CANON_ELEMENT (needle[j + k]);
b = CANON_ELEMENT (needle[max_suffix + k]);
if (a < b)
- {
- /* Suffix is smaller, period is entire prefix so far. */
- j += k;
- k = 1;
- p = j - max_suffix;
- }
+ {
+ /* Suffix is smaller, period is entire prefix so far. */
+ j += k;
+ k = 1;
+ p = j - max_suffix;
+ }
else if (a == b)
- {
- /* Advance through repetition of the current period. */
- if (k != p)
- ++k;
- else
- {
- j += p;
- k = 1;
- }
- }
+ {
+ /* Advance through repetition of the current period. */
+ if (k != p)
+ ++k;
+ else
+ {
+ j += p;
+ k = 1;
+ }
+ }
else /* b < a */
- {
- /* Suffix is larger, start over from current location. */
- max_suffix = j++;
- k = p = 1;
- }
+ {
+ /* Suffix is larger, start over from current location. */
+ max_suffix = j++;
+ k = p = 1;
+ }
}
*period = p;
@@ -178,33 +178,45 @@ critical_factorization (const unsigned char *needle, size_t needle_len,
a = CANON_ELEMENT (needle[j + k]);
b = CANON_ELEMENT (needle[max_suffix_rev + k]);
if (b < a)
- {
- /* Suffix is smaller, period is entire prefix so far. */
- j += k;
- k = 1;
- p = j - max_suffix_rev;
- }
+ {
+ /* Suffix is smaller, period is entire prefix so far. */
+ j += k;
+ k = 1;
+ p = j - max_suffix_rev;
+ }
else if (a == b)
- {
- /* Advance through repetition of the current period. */
- if (k != p)
- ++k;
- else
- {
- j += p;
- k = 1;
- }
- }
+ {
+ /* Advance through repetition of the current period. */
+ if (k != p)
+ ++k;
+ else
+ {
+ j += p;
+ k = 1;
+ }
+ }
else /* a < b */
- {
- /* Suffix is larger, start over from current location. */
- max_suffix_rev = j++;
- k = p = 1;
- }
+ {
+ /* Suffix is larger, start over from current location. */
+ max_suffix_rev = j++;
+ k = p = 1;
+ }
}
- /* Choose the longer suffix. Return the first byte of the right
- half, rather than the last byte of the left half. */
+ /* Choose the shorter suffix. Return the index of the first byte of
+ the right half, rather than the last byte of the left half.
+
+ For some examples, 'banana' has two critical factorizations, both
+ exposed by the two lexicographic extreme suffixes of 'anana' and
+ 'nana', where both suffixes have a period of 2. On the other
+ hand, with 'aab' and 'bba', both strings have a single critical
+ factorization of the last byte, with the suffix having a period
+ of 1. While the maximal lexicographic suffix of 'aab' is 'b',
+ the maximal lexicographic suffix of 'bba' is 'ba', which is not a
+ critical factorization. Conversely, the maximal reverse
+ lexicographic suffix of 'a' works for 'bba', but not 'ab' for
+ 'aab'. The shorter suffix of the two will always be a critical
+ factorization. */
if (max_suffix_rev + 1 < max_suffix + 1)
return max_suffix + 1;
*period = p;
@@ -223,7 +235,7 @@ critical_factorization (const unsigned char *needle, size_t needle_len,
HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
static RETURN_TYPE
two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
- const unsigned char *needle, size_t needle_len)
+ const unsigned char *needle, size_t needle_len)
{
size_t i; /* Index into current byte of NEEDLE. */
size_t j; /* Index into current window of HAYSTACK. */
@@ -239,137 +251,67 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
first. */
if (CMP_FUNC (needle, needle + period, suffix) == 0)
{
- /* Entire needle is periodic; a mismatch can only advance by the
- period, so use memory to avoid rescanning known occurrences
- of the period. */
+ /* Entire needle is periodic; a mismatch in the left half can
+ only advance by the period, so use memory to avoid rescanning
+ known occurrences of the period in the right half. */
size_t memory = 0;
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);
- 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;
- 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);
- /* No match, so remember how many repetitions of period
- on the right half were scanned. */
- j += period;
- memory = needle_len - period;
- }
- else
- {
- j += i - suffix + 1;
- memory = 0;
- }
- }
+ {
+ /* Scan for matches in right half. */
+ i = MAX (suffix, memory);
+ while (i < needle_len && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ ++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])))
+ --i;
+ if (i + 1 < memory + 1)
+ return (RETURN_TYPE) (haystack + j);
+ /* No match, so remember how many repetitions of period
+ on the right half were scanned. */
+ j += period;
+ memory = needle_len - period;
+ }
+ else
+ {
+ j += i - suffix + 1;
+ memory = 0;
+ }
+ }
}
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]);
-
-#if CHECK_EOL
- /* We start matching from the SUFFIX'th element, so make sure we
- don't hit '\0' before that. */
- if (haystack_len < suffix + 1
- && !AVAILABLE (haystack, haystack_len, 0, suffix + 1))
- return NULL;
-#endif
-
/* The two halves of needle are distinct; no extra memory is
- required, and any mismatch results in a maximal shift. */
+ required, and any mismatch results in a maximal shift. */
period = MAX (suffix, needle_len - suffix) + 1;
j = 0;
- while (1
-#if !CHECK_EOL
- && AVAILABLE (haystack, haystack_len, j, needle_len)
-#endif
- )
- {
- unsigned char haystack_char;
- 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
- != (haystack_char = CANON_ELEMENT (*phaystack++)))
- {
- RET0_IF_0 (haystack_char);
-#if !CHECK_EOL
- ++j;
-#endif
- continue;
- }
-
-#if CHECK_EOL
- /* Calculate J if it wasn't kept up-to-date in the first-character
- loop. */
- j = phaystack - &haystack[suffix] - 1;
-#endif
-
- /* Scan for matches in right half. */
- i = suffix + 1;
- pneedle = &needle[i];
- while (i < needle_len)
- {
- if (CANON_ELEMENT (*pneedle++)
- != (haystack_char = CANON_ELEMENT (*phaystack++)))
- {
- RET0_IF_0 (haystack_char);
- break;
- }
- ++i;
- }
- if (needle_len <= i)
- {
- /* Scan for matches in left half. */
- i = suffix - 1;
- pneedle = &needle[i];
- phaystack = &haystack[i + j];
- while (i != SIZE_MAX)
- {
- if (CANON_ELEMENT (*pneedle--)
- != (haystack_char = CANON_ELEMENT (*phaystack--)))
- {
- RET0_IF_0 (haystack_char);
- break;
- }
- --i;
- }
- if (i == SIZE_MAX)
- return (RETURN_TYPE) (haystack + j);
- j += period;
- }
- else
- j += i - suffix + 1;
-
-#if CHECK_EOL
- if (!AVAILABLE (haystack, haystack_len, j, needle_len))
- break;
-#endif
-
- phaystack = &haystack[suffix + j];
- }
+ while (AVAILABLE (haystack, haystack_len, j, needle_len))
+ {
+ /* Scan for matches in right half. */
+ i = suffix;
+ while (i < needle_len && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ ++i;
+ if (needle_len <= i)
+ {
+ /* Scan for matches in left half. */
+ i = suffix - 1;
+ while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ --i;
+ if (i == SIZE_MAX)
+ return (RETURN_TYPE) (haystack + j);
+ j += period;
+ }
+ else
+ j += i - suffix + 1;
+ }
}
- ret0: __attribute__ ((unused))
return NULL;
}
@@ -387,7 +329,7 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
sublinear performance is not possible. */
static RETURN_TYPE
two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
- const unsigned char *needle, size_t needle_len)
+ const unsigned char *needle, size_t needle_len)
{
size_t i; /* Index into current byte of NEEDLE. */
size_t j; /* Index into current window of HAYSTACK. */
@@ -413,108 +355,94 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
first. */
if (CMP_FUNC (needle, needle + period, suffix) == 0)
{
- /* Entire needle is periodic; a mismatch can only advance by the
- period, so use memory to avoid rescanning known occurrences
- of the period. */
+ /* Entire needle is periodic; a mismatch in the left half can
+ only advance by the period, so use memory to avoid rescanning
+ known occurrences of the period in the right half. */
size_t memory = 0;
size_t shift;
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])];
- if (0 < shift)
- {
- if (memory && shift < period)
- {
- /* Since needle is periodic, but the last period has
- a byte out of place, there can be no match until
- after the mismatch. */
- shift = needle_len - period;
- }
- memory = 0;
- j += shift;
- continue;
- }
- /* Scan for matches in right half. The last byte has
- already been matched, by virtue of the shift table. */
- i = MAX (suffix, memory);
- 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;
- 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);
- /* No match, so remember how many repetitions of period
- on the right half were scanned. */
- j += period;
- memory = needle_len - period;
- }
- else
- {
- j += i - suffix + 1;
- memory = 0;
- }
- }
+ {
+ /* 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])];
+ if (0 < shift)
+ {
+ if (memory && shift < period)
+ {
+ /* Since needle is periodic, but the last period has
+ a byte out of place, there can be no match until
+ after the mismatch. */
+ shift = needle_len - period;
+ }
+ memory = 0;
+ j += shift;
+ continue;
+ }
+ /* 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])))
+ ++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])))
+ --i;
+ if (i + 1 < memory + 1)
+ return (RETURN_TYPE) (haystack + j);
+ /* No match, so remember how many repetitions of period
+ on the right half were scanned. */
+ j += period;
+ memory = needle_len - period;
+ }
+ else
+ {
+ j += i - suffix + 1;
+ memory = 0;
+ }
+ }
}
else
{
/* The two halves of needle are distinct; no extra memory is
- required, and any mismatch results in a maximal shift. */
+ required, and any mismatch results in a maximal shift. */
size_t shift;
period = MAX (suffix, needle_len - suffix) + 1;
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])];
- if (0 < shift)
- {
- j += shift;
- continue;
- }
- /* Scan for matches in right half. The last byte has
- already been matched, by virtue of the shift table. */
- i = suffix;
- 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;
- 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);
- j += period;
- }
- else
- j += i - suffix + 1;
- }
+ {
+ /* 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])];
+ if (0 < shift)
+ {
+ j += shift;
+ continue;
+ }
+ /* 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])))
+ ++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])))
+ --i;
+ if (i == SIZE_MAX)
+ return (RETURN_TYPE) (haystack + j);
+ j += period;
+ }
+ else
+ j += i - suffix + 1;
+ }
}
return NULL;
}
@@ -522,6 +450,5 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
#undef AVAILABLE
#undef CANON_ELEMENT
#undef CMP_FUNC
-#undef RET0_IF_0
+#undef MAX
#undef RETURN_TYPE
-#undef CHECK_EOL
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 90ba189..1a2c713 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -16,15 +16,6 @@
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
-/*
- * My personal strstr() implementation that beats most other algorithms.
- * Until someone tells me otherwise, I assume that this is the
- * fastest implementation of strstr() in C.
- * I deliberately chose not to comment it. You should have at least
- * as much fun trying to understand it, as I had to write it :-).
- *
- * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */
-
/* Specification. */
#include <string.h>
@@ -32,28 +23,22 @@
#include <stdbool.h>
#include <strings.h>
-#define TOLOWER(Ch) tolower (Ch)
+#define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
/* Two-Way algorithm. */
#define RETURN_TYPE char *
#define AVAILABLE(h, h_l, j, n_l) \
(!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
&& ((h_l) = (j) + (n_l)))
-#define CHECK_EOL (1)
-#define RET0_IF_0(a) if (!a) goto ret0
#define CANON_ELEMENT(c) TOLOWER (c)
#define CMP_FUNC(p1, p2, l) \
__strncasecmp ((const char *) (p1), (const char *) (p2), l)
#include "str-two-way.h"
-#undef strcasestr
-#undef __strcasestr
-
#ifndef STRCASESTR
#define STRCASESTR __strcasestr
#endif
-
/* Find the first occurrence of NEEDLE in HAYSTACK, using
case-insensitive comparison. This function gives unspecified
results in multibyte locales. */
diff --git a/string/strstr.c b/string/strstr.c
index b3b5deb..eb30fe7 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -27,20 +27,12 @@
#include <stdbool.h>
-#ifndef _LIBC
-# define __builtin_expect(expr, val) (expr)
-#endif
-
#define RETURN_TYPE char *
-#define AVAILABLE(h, h_l, j, n_l) \
- (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
+#define AVAILABLE(h, h_l, j, n_l) \
+ (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
&& ((h_l) = (j) + (n_l)))
-#define CHECK_EOL (1)
-#define RET0_IF_0(a) if (!a) goto ret0
#include "str-two-way.h"
-#undef strstr
-
#ifndef STRSTR
#define STRSTR strstr
#endif
-----------------------------------------------------------------------
hooks/post-receive
--
GNU C Library master sources
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic