strstr()
Tor Myklebust
tmyklebu@caffeine.csclub.uwaterloo.ca
Sun Jul 9 00:39:00 GMT 2006
The strstr() in glibc at the moment appears to take quadratic time in the
worst case. This is bad; the following little C program takes
non-negligible time to execute, for instance:
#include <stdio.h>
#include <string.h>
int main() {
char foo[77777];
memset(foo,0,sizeof(foo));
memset(foo,'a',77770);
char bar[77777];
memset(bar,0,sizeof(bar));
memset(bar,'a',27770);
bar[10000] = 'b';
printf("%p\n", strstr(foo, bar));
}
The strstr() presently in glibc is a very good implementation of the naive
algorithm, but, as demonstrated above, it should probably not be the
default strstr() implementation in the standard C library.
I've attached a strstr() implementation that uses the present code on
short patterns but switches over to a linear-time, constant-space
algorithm on longer patterns. It was made against the glibc-2.3.2 package
from Debian sarge. I've tested this patch extensively on both an i386
machine and an AMD64 machine, and have found no problems. (It is, of
course, possible that I have overlooked all of its bugs.)
Tor Myklebust
-------------- next part --------------
--- sysdeps/generic/strstr.c.tm 2006-07-08 20:09:16.000000000 -0400
+++ sysdeps/generic/strstr.c 2006-07-08 20:10:52.000000000 -0400
@@ -17,19 +17,14 @@
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
-/*
- * 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 */
-
#if HAVE_CONFIG_H
# include <config.h>
#endif
+#if defined _LIBC || defined HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+
#if defined _LIBC || defined HAVE_STRING_H
# include <string.h>
#endif
@@ -38,8 +33,8 @@
#undef strstr
-char *
-strstr (phaystack, pneedle)
+static char *
+svdb_strstr (phaystack, pneedle)
const char *phaystack;
const char *pneedle;
{
@@ -120,3 +115,133 @@
ret0:
return 0;
}
+
+/* String matching by maximal suffices. */
+char*strstr(const char*haystack, const char*needle) {
+ size_t ul;
+ if (!*needle) return (char*)haystack;
+ if (!needle[1]) return strchr(haystack, *needle);
+
+ /* Here follow some heuristics for finding a reasonable place to start
+ * the search, since this code is slower by a decently large constant factor
+ * than Stephen van den Berg's code in easy cases, particularly on short
+ * strings.
+ */
+ {
+ size_t s;
+ /* use naive algorithm on short patterns. */
+ for (s = 2; s < 8; s++)
+ if (!needle[s]) return svdb_strstr(haystack, needle);
+
+ /* find the first occurrence of needle as a subsequence of haystack. */
+ for (s = 0; needle[s]; s++) {
+ while (haystack[s] != needle[s] && haystack[s]) haystack++;
+ if (!haystack[s]) return NULL;
+ }
+
+ /* look for the first 7 chars of needle in haystack. */
+ char foo[8];
+ for (s = 0; s < 7; s++) foo[s] = needle[s];
+ foo[7] = 0;
+ haystack = (const char*)svdb_strstr(haystack, foo);
+ if (haystack == NULL) return NULL;
+ }
+
+ const char *v;
+ /* find a maximal suffix of needle, and store it in v. */
+ {
+ size_t i, j = 0, p;
+ while (1) {
+ /* find the longest self-maximal prefix of needle[j...strlen(needle)].
+ * i is its end, and p is its period. */
+ for (i = j+1, p = 1; needle[i]; i++) {
+ if (needle[i] < needle[i - p]) p = i - j + 1;
+ else if (needle[i] > needle[i - p]) break;
+ }
+ /* needle[j...i-1] is the longest self-maximal prefix of needle+j. */
+ if (needle[i]) j = i - (i - j) % p;
+ else break;
+ }
+ v = needle + j;
+ ul = j;
+ }
+
+ /* use Stephen's code for short v. */
+ if (strlen(v) < 10) {
+ const char *prev = haystack;
+ const char *hay = haystack + ul;
+ while (1) {
+ hay = svdb_strstr(hay, v);
+ if (hay == NULL) goto retnull;
+ if (hay - prev >= ul && !memcmp(hay - ul, needle, ul))
+ return (char*)(hay - ul);
+ prev = hay;
+ hay++;
+ }
+ }
+
+ /* now do the searching. */
+ {
+ size_t p = 1, j = 0;
+ const char *hi = haystack+ul;
+ const char *prev = haystack;
+
+ while (1) {
+ /* match pattern characters against text characters. */
+ while (v[j] == hi[j] && v[j]) {
+ /* The character v[j] breaks the periodicity of v.
+ * We therefore have the situation depicted in the following cartoon:
+ *
+ * /---p---\ j
+ * v: [a b c d|a b c d|a b c d|a b x.............]
+ *
+ * The period of this string is at least j, so we update p accordingly.
+ *
+ * Why can't it be less than j?
+ * Suppose that the period of v[0...j] were less than j, even though
+ * v[j] != v[j - p]. There are two cases:
+ * Case 1: v[j] > v[j - p]
+ * Then v[0...j] is less than v[p...j], since
+ * v[0...j-p-1] = v[p...j-1] while v[j] > v[j-p], a contradiction.
+ * Case 2: v[j] < v[j - p]
+ * Let q be the actual period of v[0...j].
+ * Then v[j % q] < v[j - p].
+ * Thus, v[j - p - (j % q)...j] > v[0...j], since
+ * v[j - p - (j % q)...j - p - 1] = v[0...(j % q) - 1]
+ * while v[j - p] > v[j] = v[j % q].
+ * This is again a contradiction.
+ */
+ if (j > p && v[j] != v[j-p])
+ p = j;
+ j++;
+ }
+
+ if (!v[j]) { /* v matches. */
+ if (hi >= prev) {
+ if (!memcmp(hi-ul, needle, ul)) /* whole string matches. */
+ return (char*)(hi-ul);
+ /* u doesn't match. */
+ }
+ /* else, u cannot possibly match since v was a maximal suffix. */
+ prev = hi+ul; /* u doesn't match. set prev accordingly. */
+ }
+ else if (!hi[j]) goto retnull;
+
+ /* We know that v[0...j] has period p. We also know that j characters of
+ * the text match. We can therefore shift the pattern over by p, since at
+ * least the first p characters of haystack+i must match the first p
+ * characters of v.
+ */
+ hi += p;
+ /* Similarly, if we matched the first 2p characters of v, we must match
+ * the first p characters of the needle against the first p characters of
+ * the haystack, so we shift v by p.
+ */
+ if (j >= p+p) j -= p;
+ else p=1, j = 0;
+ }
+ }
+
+ retnull:
+ return NULL;
+}
More information about the Libc-alpha
mailing list