@@ -1,112 +1,56 @@
-/* Return the offset of one string within another.
- Copyright (C) 1994,1996,1997,2000,2001,2003 Free Software Foundation, Inc.
- This file is part of the GNU C Library.
-
- The GNU C Library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
-
- The GNU C Library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- 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 :-).
+ * Copyright (C) 2002 Manuel Novoa III
+ * Copyright (C) 2000-2005 Erik Andersen <andersen@uclibc.org>
+ * Copyright (C) 2015 Jody Bruchon <jody@jodybruchon.com>
*
- * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */
+ * Licensed under the LGPL v2.1, see the file COPYING.LIB in this tarball.
+ */
#include <string.h>
-
-typedef unsigned chartype;
-
-char *strstr (const char *phaystack, const char *pneedle)
+/*
+ * Rewritten "two-way" strstr() by Jody Bruchon
+ * This new strstr() implementation scans for the substring in both
+ * directions instead of scanning from start to end. Benchmarks for
+ * strstr() from libc-bench (http://www.etalabs.net/libc-bench.html)
+ * indicate this implementation is ~5-10x faster than the "naive"
+ * one it replaces.
+ */
+char *strstr(const char *s1, const char *s2)
{
- const unsigned char *haystack, *needle;
- chartype b;
- const unsigned char *rneedle;
-
- haystack = (const unsigned char *) phaystack;
-
- if ((b = *(needle = (const unsigned char *) pneedle)))
- {
- chartype c;
- haystack--; /* possible ANSI violation */
+ register const char *haystack = s1;
+ register const char *needle = s2;
+ int pos = 0;
+ register int cnt;
+ size_t hay_len;
+ size_t n_len;
+
+ if (!*needle) return (char *) s1;
+ n_len = strlen(needle);
+ hay_len = strlen(haystack);
+
+ cnt = n_len;
+ do {
+ /* Give up if needle is longer than remaining haystack */
+ if ((pos + n_len - 1) > hay_len) return NULL;
+
+ /* Scan for match in both directions */
+ while (*needle == *haystack) {
+ cnt--;
+ if (!cnt) return (char *) (s1 + pos);
+ if (*(needle + cnt) == *(haystack + cnt)) {
+ cnt--;
+ if (!cnt) return (char *) (s1 + pos);
+ } else break;
+ needle++;
+ haystack++;
+ }
+ pos++;
+ haystack = s1 + pos;
+ needle = s2;
+ cnt = n_len;
+ } while (1);
- {
- chartype a;
- do
- if (!(a = *++haystack))
- goto ret0;
- while (a != b);
- }
-
- if (!(c = *++needle))
- goto foundneedle;
- ++needle;
- goto jin;
-
- for (;;)
- {
- {
- chartype a;
- if (0)
- jin:{
- if ((a = *++haystack) == c)
- goto crest;
- }
- else
- a = *++haystack;
- do
- {
- for (; a != b; a = *++haystack)
- {
- if (!a)
- goto ret0;
- if ((a = *++haystack) == b)
- break;
- if (!a)
- goto ret0;
- }
- }
- while ((a = *++haystack) != c);
- }
- crest:
- {
- chartype a;
- {
- const unsigned char *rhaystack;
- if (*(rhaystack = haystack-- + 1) == (a = *(rneedle = needle)))
- do
- {
- if (!a)
- goto foundneedle;
- if (*++rhaystack != (a = *++needle))
- break;
- if (!a)
- goto foundneedle;
- }
- while (*++rhaystack == (a = *++needle));
- needle = rneedle; /* took the register-poor aproach */
- }
- if (!a)
- break;
- }
- }
- }
-foundneedle:
- return (char *) haystack;
-ret0:
- return 0;
}
+
libc_hidden_def(strstr)
@@ -1,6 +1,7 @@
/*
* Copyright (C) 2002 Manuel Novoa III
* Copyright (C) 2000-2005 Erik Andersen <andersen@uclibc.org>
+ * Copyright (C) 2015 Jody Bruchon <jody@jodybruchon.com>
*
* Licensed under the LGPL v2.1, see the file COPYING.LIB in this tarball.
*/
@@ -13,29 +14,51 @@
# define Wstrstr strstr
#endif
-/* NOTE: This is the simple-minded O(len(s1) * len(s2)) worst-case approach. */
-
+/*
+ * Rewritten "two-way" strstr() by Jody Bruchon
+ * This new strstr() implementation scans for the substring in both
+ * directions instead of scanning from start to end. Benchmarks for
+ * strstr() from libc-bench (http://www.etalabs.net/libc-bench.html)
+ * indicate this implementation is ~5-10x faster than the "naive"
+ * one it replaces.
+ */
Wchar *Wstrstr(const Wchar *s1, const Wchar *s2)
{
- register const Wchar *s = s1;
- register const Wchar *p = s2;
-
- do {
- if (!*p) {
- return (Wchar *) s1;;
- }
- if (*p == *s) {
- ++p;
- ++s;
- } else {
- p = s2;
- if (!*s) {
- return NULL;
- }
- s = ++s1;
- }
- } while (1);
+ register const Wchar *haystack = s1;
+ register const Wchar *needle = s2;
+ int pos = 0;
+ register int cnt;
+ size_t hay_len;
+ size_t n_len;
+
+ if (!*needle) return (Wchar *) s1;
+ n_len = wcslen(needle);
+ hay_len = wcslen(haystack);
+
+ cnt = n_len;
+ do {
+ /* Give up if needle is longer than remaining haystack */
+ if ((pos + n_len - 1) > hay_len) return NULL;
+
+ /* Scan for match in both directions */
+ while (*needle == *haystack) {
+ cnt--;
+ if (!cnt) return (Wchar *) (s1 + pos);
+ if (*(needle + cnt) == *(haystack + cnt)) {
+ cnt--;
+ if (!cnt) return (Wchar *) (s1 + pos);
+ } else break;
+ needle++;
+ haystack++;
+ }
+ pos++;
+ haystack = s1 + pos;
+ needle = s2;
+ cnt = n_len;
+ } while (1);
+
}
+
#ifndef WANT_WIDE
libc_hidden_def(strstr)
#elif defined __UCLIBC_SUSV3_LEGACY__