[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
memmem issues
From: |
Eric Blake |
Subject: |
memmem issues |
Date: |
Wed, 19 Dec 2007 23:15:29 +0000 (UTC) |
User-agent: |
Loom/3.14 (http://gmane.org/) |
I'm trying to convert m4 to transparently handle embedded NUL. In the process,
I need to move from strstr to memmem (if m4 were fully i18n already, I would
instead be moving from mbsstr to the length-based analog of mbsstr that
tolerates embedded NUL - is there such a thing?)
Several issues with memmem:
- It uses memcmp without depending on the memcmp module, making it needlessly
fail on some older platforms. But memcmp is currently licensed LGPL; is it
okay with everyone that this patch relicenses it as LGPLv2+? (Or are such
platforms so obsolete that we can delete the memcmp module?)
- It passed up on using optimizations built into memchr when needle_len is 1.
Is it okay with everyone that this patch relicenses memchr as LGPLv2+?
- test-memmem.c was flat-out broken (calling memmem with 3 instead of 4
arguments). The reason it was never compiled was the lack of a memmem-tests
module.
- There are platform-specific bugs in existing memmem implementations. Cygwin,
for example, returns NULL instead of haystack for memmem(haystack,len,"",0).
How best do I document platform bugs in non-standardized functions?
- The implementation was naively quadratic in the worst-case complexity. I
lifted Bruno's KMP ideas in mbsstr to make it linear+delayed allocation. glibc
still uses the naive implementation - should we file a bug with them to fix
it? Should we update memmem.m4 to reject known-quadratic implementations?
Here's a patch for these issues; it breaks sync with glibc (and hence loses the
K&R declaration). Tested on cygwin (where memmem is broken) and mingw (where
memmem is missing). Okay to apply?
From: Eric Blake <address@hidden>
Date: Wed, 19 Dec 2007 16:09:03 -0700
Subject: [PATCH] Fix memmem to avoid O(n^2) worst-case complexity.
* lib/memmem.c (knuth_morris_pratt): New function.
(memmem): Use it if first few naive iterations fail.
* m4/memmem.m4 (gl_FUNC_MEMMEM): Detect cygwin bug.
* modules/memcmp (License): Set to LGPLv2+, not LGPL.
* modules/memchr (License): Likewise.
* modules/memmem (Depends-on): Add memcmp, memchr, stdbool, and
malloca.
* tests/test-memmem.c: Rewrite, borrowing ideas from
test-mbsstr1.c; the old version wouldn't even compile!
* modules/memmem-tests: New file.
* lib/string.in.h (rpl_memmem): Add declaration.
* modules/string (Makefile.am): Substitute REPLACE_MEMMEM.
* m4/string_h.m4 (gl_HEADER_STRING_H_DEFAULTS): Default for
REPLACE_MEMMEM.
Signed-off-by: Eric Blake <address@hidden>
---
ChangeLog | 18 +++++
lib/memmem.c | 192 +++++++++++++++++++++++++++++++++++++++++++++----
lib/string.in.h | 5 +-
m4/memmem.m4 | 14 ++++-
m4/string_h.m4 | 3 +
modules/memchr | 2 +-
modules/memcmp | 2 +-
modules/memmem | 4 +
modules/memmem-tests | 12 +++
modules/string | 1 +
tests/test-memmem.c | 147 +++++++++++++++++++++++++++++++--------
11 files changed, 351 insertions(+), 49 deletions(-)
create mode 100644 modules/memmem-tests
diff --git a/ChangeLog b/ChangeLog
index d52195d..280c7ca 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,21 @@
+2007-12-19 Eric Blake <address@hidden>
+
+ Fix memmem to avoid O(n^2) worst-case complexity.
+ * lib/memmem.c (knuth_morris_pratt): New function.
+ (memmem): Use it if first few naive iterations fail.
+ * m4/memmem.m4 (gl_FUNC_MEMMEM): Detect cygwin bug.
+ * modules/memcmp (License): Set to LGPLv2+, not LGPL.
+ * modules/memchr (License): Likewise.
+ * modules/memmem (Depends-on): Add memcmp, memchr, stdbool, and
+ malloca.
+ * tests/test-memmem.c: Rewrite, borrowing ideas from
+ test-mbsstr1.c; the old version wouldn't even compile!
+ * modules/memmem-tests: New file.
+ * lib/string.in.h (rpl_memmem): Add declaration.
+ * modules/string (Makefile.am): Substitute REPLACE_MEMMEM.
+ * m4/string_h.m4 (gl_HEADER_STRING_H_DEFAULTS): Default for
+ REPLACE_MEMMEM.
+
2007-12-18 Paul Eggert <address@hidden>
Fix problem with _GL_JUST_INCLUDE_SYSTEM_INTTYPES_H on VMS.
diff --git a/lib/memmem.c b/lib/memmem.c
index e882222..69d2edc 100644
--- a/lib/memmem.c
+++ b/lib/memmem.c
@@ -21,24 +21,114 @@
#include <stddef.h>
#include <string.h>
+#include <stdbool.h>
+
+#include "malloca.h"
#ifndef _LIBC
# define __builtin_expect(expr, val) (expr)
#endif
-#undef memmem
+/* Knuth-Morris-Pratt algorithm.
+ See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
+ Return a boolean indicating success. */
+
+static bool
+knuth_morris_pratt (const char *haystack, const char *last_haystack,
+ const char *needle, size_t m,
+ const char **resultp)
+{
+ /* Allocate the table. */
+ size_t *table = (size_t *) malloca (m * sizeof (size_t));
+ if (table == NULL)
+ return false;
+ /* Fill the table.
+ For 0 < i < m:
+ 0 < table[i] <= i is defined such that
+ rhaystack[0..i-1] == needle[0..i-1] and rhaystack[i] != needle[i]
+ implies
+ forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1],
+ and table[i] is as large as possible with this property.
+ table[0] remains uninitialized. */
+ {
+ size_t i, j;
+
+ table[1] = 1;
+ j = 0;
+ for (i = 2; i < m; i++)
+ {
+ unsigned char b = (unsigned char) needle[i - 1];
-/* Return the first occurrence of NEEDLE in HAYSTACK. */
+ for (;;)
+ {
+ if (b == (unsigned char) needle[j])
+ {
+ table[i] = i - ++j;
+ break;
+ }
+ if (j == 0)
+ {
+ table[i] = i;
+ break;
+ }
+ j = j - table[j];
+ }
+ }
+ }
+
+ /* Search, using the table to accelerate the processing. */
+ {
+ size_t j;
+ const char *rhaystack;
+ const char *phaystack;
+
+ *resultp = NULL;
+ j = 0;
+ rhaystack = haystack;
+ phaystack = haystack;
+ /* Invariant: phaystack = rhaystack + j. */
+ while (phaystack != last_haystack)
+ if ((unsigned char) needle[j] == (unsigned char) *phaystack)
+ {
+ j++;
+ phaystack++;
+ if (j == m)
+ {
+ /* The entire needle has been found. */
+ *resultp = rhaystack;
+ break;
+ }
+ }
+ else if (j > 0)
+ {
+ /* Found a match of needle[0..j-1], mismatch at needle[j]. */
+ rhaystack += table[j];
+ j -= table[j];
+ }
+ else
+ {
+ /* Found a mismatch at needle[0] already. */
+ rhaystack++;
+ phaystack++;
+ }
+ }
+
+ freea (table);
+ return true;
+}
+
+/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
+ if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
+ HAYSTACK. */
void *
-memmem (haystack, haystack_len, needle, needle_len)
- const void *haystack;
- size_t haystack_len;
- const void *needle;
- size_t needle_len;
+memmem (const void *haystack, size_t haystack_len,
+ const void *needle, size_t needle_len)
{
- const char *begin;
- const char *const last_possible
- = (const char *) haystack + haystack_len - needle_len;
+ /* Operating with void * is awkward. */
+ const char *Haystack = (const char *) haystack;
+ const char *Needle = (const char *) needle;
+ const char *last_haystack = Haystack + haystack_len;
+ const char *last_needle = Needle + needle_len;
if (needle_len == 0)
/* The first occurrence of the empty string is deemed to occur at
@@ -50,12 +140,82 @@ memmem (haystack, haystack_len, needle, needle_len)
if (__builtin_expect (haystack_len < needle_len, 0))
return NULL;
- for (begin = (const char *) haystack; begin <= last_possible; ++begin)
- if (begin[0] == ((const char *) needle)[0] &&
- !memcmp ((const void *) &begin[1],
- (const void *) ((const char *) needle + 1),
- needle_len - 1))
- return (void *) begin;
+ /* Use optimizations in memchr when possible. */
+ if (__builtin_expect (needle_len == 1, 0))
+ return memchr (haystack, (unsigned char) *Needle, haystack_len);
+
+ /* Minimizing the worst-case complexity:
+ Let n = haystack_len, m = needle_len.
+ The naïve algorithm is O(n*m) worst-case.
+ The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
+ memory allocation.
+ To achieve linear complexity and yet amortize the cost of the
+ memory allocation, we activate the Knuth-Morris-Pratt algorithm
+ only once the naïve algorithm has already run for some time; more
+ precisely, when
+ - the outer loop count is >= 10,
+ - the average number of comparisons per outer loop is >= 5,
+ - the total number of comparisons is >= m.
+ But we try it only once. If the memory allocation attempt failed,
+ we don't retry it. */
+ {
+ bool try_kmp = true;
+ size_t outer_loop_count = 0;
+ size_t comparison_count = 0;
+
+ /* Speed up the following searches of needle by caching its first
+ character. */
+ char b = *Needle++;
+
+ for (;; Haystack++)
+ {
+ if (Haystack == last_haystack)
+ /* No match. */
+ return NULL;
+
+ /* See whether it's advisable to use an asymptotically faster
+ algorithm. */
+ if (try_kmp
+ && outer_loop_count >= 10
+ && comparison_count >= 5 * outer_loop_count)
+ {
+ /* See if needle + comparison_count now reaches the end of
+ needle. */
+ if (comparison_count >= needle_len)
+ {
+ /* Try the Knuth-Morris-Pratt algorithm. */
+ const char *result;
+ if (knuth_morris_pratt (Haystack, last_haystack,
+ Needle - 1, needle_len, &result))
+ return (void *) result;
+ try_kmp = false;
+ }
+ }
+
+ outer_loop_count++;
+ comparison_count++;
+ if (*Haystack == b)
+ /* The first character matches. */
+ {
+ const char *rhaystack = Haystack + 1;
+ const char *rneedle = Needle;
+
+ for (;; rhaystack++, rneedle++)
+ {
+ if (rneedle == last_needle)
+ /* Found a match. */
+ return (void *) Haystack;
+ if (rhaystack == last_haystack)
+ /* No match. */
+ return NULL;
+ comparison_count++;
+ if (*rhaystack != *rneedle)
+ /* Nothing in this round. */
+ break;
+ }
+ }
+ }
+ }
return NULL;
}
diff --git a/lib/string.in.h b/lib/string.in.h
index c60e2f3..09205e7 100644
--- a/lib/string.in.h
+++ b/lib/string.in.h
@@ -35,7 +35,10 @@ extern "C" {
/* Return the first occurrence of NEEDLE in HAYSTACK. */
#if @GNULIB_MEMMEM@
-# if ! @HAVE_DECL_MEMMEM@
+# if @REPLACE_MEMMEM@
+# define memmem rpl_memmem
+# endif
+# if ! @HAVE_DECL_MEMMEM@ || @REPLACE_MEMMEM@
extern void *memmem (void const *__haystack, size_t __haystack_len,
void const *__needle, size_t __needle_len);
# endif
diff --git a/m4/memmem.m4 b/m4/memmem.m4
index e6a3da1..a529af3 100644
--- a/m4/memmem.m4
+++ b/m4/memmem.m4
@@ -1,4 +1,4 @@
-# memmem.m4 serial 5
+# memmem.m4 serial 6
dnl Copyright (C) 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
dnl This file is free software; the Free Software Foundation
dnl gives unlimited permission to copy and/or distribute it,
@@ -14,6 +14,18 @@ AC_DEFUN([gl_FUNC_MEMMEM],
AC_CHECK_DECLS_ONCE(memmem)
if test $ac_cv_have_decl_memmem = no; then
HAVE_DECL_MEMMEM=0
+ else
+ AC_CACHE_CHECK([whether memmem works], [gl_cv_func_memmem_works],
+ [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>],
+ [return !memmem ("a", 1, NULL, 0);])],
+ [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no],
+ [dnl pessimistically assume the worst, since even glibc 2.6.1
+ dnl has quadratic complexity in its memmem
+ gl_cv_func_memmem_works=no])])
+ if test $gl_cv_func_memmem_works = no; then
+ REPLACE_MEMMEM=1
+ AC_LIBOBJ([memmem])
+ fi
fi
gl_PREREQ_MEMMEM
])
diff --git a/m4/string_h.m4 b/m4/string_h.m4
index 8371179..99a0dab 100644
--- a/m4/string_h.m4
+++ b/m4/string_h.m4
@@ -5,6 +5,8 @@
# gives unlimited permission to copy and/or distribute it,
# with or without modifications, as long as this notice is preserved.
+# serial 2
+
# Written by Paul Eggert.
AC_DEFUN([gl_HEADER_STRING_H],
@@ -75,4 +77,5 @@ AC_DEFUN([gl_HEADER_STRING_H_DEFAULTS],
HAVE_DECL_STRTOK_R=1; AC_SUBST([HAVE_DECL_STRTOK_R])
HAVE_DECL_STRERROR=1; AC_SUBST([HAVE_DECL_STRERROR])
REPLACE_STRERROR=0; AC_SUBST([REPLACE_STRERROR])
+ REPLACE_MEMMEM=0; AC_SUBST([REPLACE_MEMMEM])
])
diff --git a/modules/memchr b/modules/memchr
index 3b18a1c..5e908d2 100644
--- a/modules/memchr
+++ b/modules/memchr
@@ -16,7 +16,7 @@ Include:
<string.h>
License:
-LGPL
+LGPLv2+
Maintainer:
Jim Meyering, glibc
diff --git a/modules/memcmp b/modules/memcmp
index fc85d85..e6b74e5 100644
--- a/modules/memcmp
+++ b/modules/memcmp
@@ -16,7 +16,7 @@ Include:
<string.h>
License:
-LGPL
+LGPLv2+
Maintainer:
Jim Meyering, glibc
diff --git a/modules/memmem b/modules/memmem
index c51ee30..738cd6a 100644
--- a/modules/memmem
+++ b/modules/memmem
@@ -8,6 +8,10 @@ m4/memmem.m4
Depends-on:
extensions
string
+stdbool
+malloca
+memchr
+memcmp
configure.ac:
gl_FUNC_MEMMEM
diff --git a/modules/memmem-tests b/modules/memmem-tests
new file mode 100644
index 0000000..3d79e47
--- /dev/null
+++ b/modules/memmem-tests
@@ -0,0 +1,12 @@
+Files:
+tests/test-memmem.c
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-memmem
+TESTS_ENVIRONMENT += EXEEXT='@EXEEXT@'
+check_PROGRAMS += test-memmem
+
diff --git a/modules/string b/modules/string
index 505ae6a..6f3226d 100644
--- a/modules/string
+++ b/modules/string
@@ -66,6 +66,7 @@ string.h: string.in.h
-e 's|@''HAVE_STRCASESTR''@|$(HAVE_STRCASESTR)|g' \
-e 's|@''HAVE_DECL_STRTOK_R''@|$(HAVE_DECL_STRTOK_R)|g' \
-e 's|@''HAVE_DECL_STRERROR''@|$(HAVE_DECL_STRERROR)|g' \
+ -e 's|@''REPLACE_MEMMEM''@|$(REPLACE_MEMMEM)|g' \
-e 's|@''REPLACE_STRERROR''@|$(REPLACE_STRERROR)|g' \
-e '/definition of GL_LINK_WARNING/r $(LINK_WARNING_H)' \
< $(srcdir)/string.in.h; \
diff --git a/tests/test-memmem.c b/tests/test-memmem.c
index 65980c2..935edbb 100644
--- a/tests/test-memmem.c
+++ b/tests/test-memmem.c
@@ -19,39 +19,128 @@
#include <stdio.h>
#include <string.h>
+#include <stdlib.h>
+
+#define ASSERT(expr) \
+ do \
+ { \
+ if (!(expr)) \
+ { \
+ fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
+ abort (); \
+ } \
+ } \
+ while (0)
int
main (int argc, char *argv[])
{
- const char *big = "foo-bar-baz";
- char *p;
-
- p = memmem (big, "foo", strlen (big));
- if (p != big)
- {
- fprintf (stderr, "memmem FAILURE 1\n");
- return 1;
- }
-
- p = memmem (big, "baz", strlen (big));
- if (p != big + strlen (big) - 3)
- {
- fprintf (stderr, "memmem FAILURE 2\n");
- return 1;
-
- p = memmem (big, "-", strlen (big));
- if (p != big + 3)
- {
- fprintf (stderr, "memmem FAILURE 3\n");
- return 1;
- }
-
- p = memmem (big, "baz", strlen (big) - 1);
- if (p != NULL)
- {
- fprintf (stderr, "memmem FAILURE 4\n");
- return 1;
- }
+ {
+ const char input[] = "foo";
+ const char *result = memmem (input, strlen (input), "", 0);
+ ASSERT (result == input);
+ }
+
+ {
+ const char input[] = "foo";
+ const char *result = memmem (input, strlen (input), "o", 1);
+ ASSERT (result == input + 1);
+ }
+
+ {
+ const char input[] = "ABC ABCDAB ABCDABCDABDE";
+ const char *result = memmem (input, strlen (input), "ABCDABD", 7);
+ ASSERT (result == input + 15);
+ }
+
+ {
+ const char input[] = "ABC ABCDAB ABCDABCDABDE";
+ const char *result = memmem (input, strlen (input), "ABCDABE", 7);
+ ASSERT (result == NULL);
+ }
+
+ /* Check that length 0 does not dereference NULL. */
+ {
+ const char *result = memmem (NULL, 0, "foo", 3);
+ ASSERT (result == NULL);
+ }
+
+ {
+ const char input[] = "foo";
+ const char *result = memmem (input, strlen (input), NULL, 0);
+ ASSERT (result == input);
+ }
+
+ /* Check that a very long haystack is handled quickly if the needle is
+ short and occurs near the beginning. */
+ {
+ size_t repeat = 10000;
+ size_t m = 1000000;
+ char *needle =
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
+ size_t n = strlen (needle);
+ char *haystack = (char *) malloc (m + 1);
+ if (haystack != NULL)
+ {
+ memset (haystack, 'A', m);
+ haystack[0] = 'B';
+
+ for (; repeat > 0; repeat--)
+ {
+ ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
+ }
+
+ free (haystack);
+ }
+ }
+
+ /* Check that a very long needle is discarded quickly if the haystack is
+ short. */
+ {
+ size_t repeat = 10000;
+ size_t m = 1000000;
+ char *haystack =
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
+ "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
+ size_t n = strlen (haystack);
+ char *needle = (char *) malloc (m + 1);
+ if (needle != NULL)
+ {
+ memset (needle, 'A', m);
+
+ for (; repeat > 0; repeat--)
+ {
+ ASSERT (memmem (haystack, n, needle, m) == NULL);
+ }
+
+ free (needle);
+ }
+ }
+
+ /* Check that the asymptotic worst-case complexity is not quadratic. */
+ {
+ size_t m = 1000000;
+ char *haystack = (char *) malloc (2 * m + 1);
+ char *needle = (char *) malloc (m + 1);
+ if (haystack != NULL && needle != NULL)
+ {
+ const char *result;
+
+ memset (haystack, 'A', 2 * m);
+ haystack[2 * m] = 'B';
+
+ memset (needle, 'A', m);
+ needle[m] = 'B';
+
+ result = memmem (haystack, 2 * m + 1, needle, m + 1);
+ ASSERT (result == haystack + m);
+ }
+ if (needle != NULL)
+ free (needle);
+ if (haystack != NULL)
+ free (haystack);
+ }
return 0;
}
--
1.5.3.5
- memmem issues,
Eric Blake <=