memmem speedup

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've finished my implementation of a Two-Way plus Boyer-Moore hybrid
string search algorithm for the memmmem module.  This patch has passed
everything I've thrown at it so far, and it has the nice properties of
avoiding alloca/malloc (hence it is async-safe), as well as allowing
sub-linear complexity for long needles (the added test in test-memmem.c
fails with the KMP algorithm but passes with my Two-Way+BM hybrid).  It
guarantees fewer than 2N comparisons, and can determine misses as quickly
as N/M.  I chose a threshold of 128 bytes in the needle before attempting
the BM bad-character shift table, since constructing a 256-entry table is
expensive up front with little gain for short needles.

In my web searches, I've never seen this hybrid approach documented, so I
may well have written the fastest string search algorithm to date.

I'd appreciate any reviews before checking it in.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHgC2V84KuGfSFAYARAioOAJsF8ww7BZwEzah1ebKWG5cCqVMrJACgnlWm
N1cTTDrPqrQM2HGnCEDLpXI=
=95ja
-----END PGP SIGNATURE-----

>From 16c4539a08e1427f831745c6809064daf3b03c64 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Sat, 5 Jan 2008 14:09:11 -0700
Subject: [PATCH] Rewrite memmem to guarantee linear complexity without malloc.

* lib/memmem.c (memmem): Use Two-Way rather than
Knuth-Morris-Pratt, to allow O(1) space usage.
(critical_factorization, two_way_short_needle)
(two_way_long_needle): New functions.
(knuth_morris_pratt): Delete.
* modules/memmem (Depends-on): No longer need malloca or stdbool.
Add stdint.
* tests/test-memmem.c (main): Add test for sublinear performance.
* doc/functions/memmem.texi (memmem): Document cygwin deficiency.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog                 |   11 +
 doc/functions/memmem.texi |    2 +-
 lib/memmem.c              |  523 +++++++++++++++++++++++++++++----------------
 modules/memmem            |    3 +-
 tests/test-memmem.c       |   27 +++
 5 files changed, 374 insertions(+), 192 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index bdc357a..4c6db8e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,16 @@
 2008-01-05  Eric Blake  <address@hidden>
 
+       Rewrite memmem to guarantee linear complexity without malloc.
+       * lib/memmem.c (memmem): Use Two-Way rather than
+       Knuth-Morris-Pratt, to allow O(1) space usage.
+       (critical_factorization, two_way_short_needle)
+       (two_way_long_needle): New functions.
+       (knuth_morris_pratt): Delete.
+       * modules/memmem (Depends-on): No longer need malloca or stdbool.
+       Add stdint.
+       * tests/test-memmem.c (main): Add test for sublinear performance.
+       * doc/functions/memmem.texi (memmem): Document cygwin deficiency.
+
        Avoid quadratic system memmem.
        * m4/memmem.m4 (gl_FUNC_MEMMEM): Check for quadratic memmem.
        Reported by Ralf Wildenhues.
diff --git a/doc/functions/memmem.texi b/doc/functions/memmem.texi
index 50d73fd..e51b640 100644
--- a/doc/functions/memmem.texi
+++ b/doc/functions/memmem.texi
@@ -16,7 +16,7 @@ Cygwin 1.5.x
 @item
 This function has quadratic instead of linear complexity on some
 platforms:
-glibc <= 2.6.1
+glibc <= 2.6.1, cygwin
 
 @item
 This function is missing on some platforms:
diff --git a/lib/memmem.c b/lib/memmem.c
index 5aa704c..fb65ca7 100644
--- a/lib/memmem.c
+++ b/lib/memmem.c
@@ -1,4 +1,5 @@
-/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007,2008 Free Software 
Foundation, Inc.
+/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007,2008 Free Software
+   Foundation, Inc.
    This file is part of the GNU C Library.
 
    This program is free software; you can redistribute it and/or modify
@@ -19,136 +20,341 @@
 # include <config.h>
 #endif
 
-#include <stddef.h>
+/* Specification of memmem.  */
 #include <string.h>
-#include <stdbool.h>
 
-#include "malloca.h"
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
 
 #ifndef _LIBC
 # define __builtin_expect(expr, val)   (expr)
 #endif
 
-/* Knuth-Morris-Pratt algorithm.
-   See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
-   Return a boolean indicating success.  */
+/* 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 acheive sub-linear performance.
 
-static bool
-knuth_morris_pratt (const unsigned char *haystack,
-                    const unsigned char *last_haystack,
-                    const unsigned char *needle, size_t m,
-                    const unsigned char **resultp)
-{
-  /* Allocate the table.  */
-  size_t *table = (size_t *) nmalloca (m, sizeof (size_t));
-  if (table == NULL)
-    return false;
-  /* Fill the table.
-     For 0 < i < m:
-       0 < table[i] <= i is defined such that
-       forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
-       and table[i] is as large as possible with this property.
-     This implies:
-     1) For 0 < i < m:
-          If table[i] < i,
-          needle[table[i]..i-1] = needle[0..i-1-table[i]].
-     2) For 0 < i < m:
-          rhaystack[0..i-1] == needle[0..i-1]
-          and exists h, i <= h < m: rhaystack[h] != needle[h]
-          implies
-          forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
-     table[0] remains uninitialized.  */
-  {
-    size_t i, j;
+   See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
+   and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
+*/
+
+/* Point at which computing a bad-byte shift table is likely to be
+   worthwhile.  */
+#define LONG_NEEDLE_THRESHOLD (1 << (CHAR_BIT - 1))
 
-    /* i = 1: Nothing to verify for x = 0.  */
-    table[1] = 1;
-    j = 0;
+#define MAX(a, b) ((a < b) ? (b) : (a))
 
-    for (i = 2; i < m; i++)
-      {
-       /* Here: j = i-1 - table[i-1].
-          The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
-          for x < table[i-1], by induction.
-          Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
-       unsigned char b = needle[i - 1];
+/* Peform 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.
 
-       for (;;)
-         {
-           /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
-              is known to hold for x < i-1-j.
-              Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
-           if (b == needle[j])
-             {
-               /* Set table[i] := i-1-j.  */
-               table[i] = i - ++j;
-               break;
-             }
-           /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
-              for x = i-1-j, because
-                needle[i-1] != needle[j] = needle[i-1-x].  */
-           if (j == 0)
-             {
-               /* The inequality holds for all possible x.  */
-               table[i] = i;
-               break;
-             }
-           /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
-              for i-1-j < x < i-1-j+table[j], because for these x:
-                needle[x..i-2]
-                = needle[x-(i-1-j)..j-1]
-                != needle[0..j-1-(x-(i-1-j))]  (by definition of table[j])
-                   = needle[0..i-2-x],
-              hence needle[x..i-1] != needle[0..i-1-x].
-              Furthermore
-                needle[i-1-j+table[j]..i-2]
-                = needle[table[j]..j-1]
-                = needle[0..j-1-table[j]]  (by definition of table[j]).  */
-           j = j - table[j];
-         }
-       /* Here: j = i - table[i].  */
-      }
-  }
+   The global period of a string is the smallest index (possibly its
+   length) at which all remaining bytes in the string are repetitions
+   of the prefix (the last repetition may be a subset of the prefix).
 
-  /* Search, using the table to accelerate the processing.  */
-  {
-    size_t j;
-    const unsigned char *rhaystack;
-    const unsigned char *phaystack;
+   When NEEDLE is factored into two halves, a local period is the
+   length of the smallest word that shares a suffix with the left half
+   and shares a prefix with the right half.  All factorizations of a
+   non-empty NEEDLE have a local period of at least 1 and no greater
+   than NEEDLE_LEN.
 
-    *resultp = NULL;
-    j = 0;
-    rhaystack = haystack;
-    phaystack = haystack;
-    /* Invariant: phaystack = rhaystack + j.  */
-    while (phaystack != last_haystack)
-      if (needle[j] == *phaystack)
+   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.
+
+   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
+   periodicity.  */
+static size_t
+critical_factorization (const unsigned char *needle, size_t needle_len,
+                       size_t *period)
+{
+  /* Index of last byte of left half, or SIZE_MAX.  */
+  size_t max_suffix, max_suffix_rev;
+  size_t j, k; /* Indices for iteration over NEEDLE.  */
+  unsigned char a, b; /* Current comparison bytes.  */
+  size_t p; /* Intermediate period.  */
+
+  /* Perform lexicographic search.  */
+  max_suffix = SIZE_MAX;
+  j = 0;
+  k = p = 1;
+  while (j + k < needle_len)
+    {
+      a = needle[j + k];
+      b = needle[max_suffix + k];
+      if (a < b)
+       {
+         /* Suffix is smaller, period is entire prefix so far.  */
+         j += k;
+         k = 1;
+         p = j - max_suffix;
+       }
+      else if (a == b)
        {
-         j++;
-         phaystack++;
-         if (j == m)
+         /* Advance through repetition of the current period.  */
+         if (k != p)
+           ++k;
+         else
            {
-             /* The entire needle has been found.  */
-             *resultp = rhaystack;
-             break;
+             j += p;
+             k = 1;
            }
        }
-      else if (j > 0)
+      else /* b < a */
+       {
+         /* Suffix is larger, start over from current location.  */
+         max_suffix = j++;
+         k = p = 1;
+       }
+    }
+  *period = p;
+
+  /* Perform reverse lexicographic search.  */
+  max_suffix_rev = SIZE_MAX;
+  j = 0;
+  k = p = 1;
+  while (j + k < needle_len)
+    {
+      a = needle[j + k];
+      b = 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;
+       }
+      else if (a == b)
        {
-         /* Found a match of needle[0..j-1], mismatch at needle[j].  */
-         rhaystack += table[j];
-         j -= table[j];
+         /* Advance through repetition of the current period.  */
+         if (k != p)
+           ++k;
+         else
+           {
+             j += p;
+             k = 1;
+           }
        }
-      else
+      else /* a < b */
        {
-         /* Found a mismatch at needle[0] already.  */
-         rhaystack++;
-         phaystack++;
+         /* Suffix is larger, start over from current location.  */
+         max_suffix_rev = j++;
+         k = p = 1;
+       }
+    }
+
+  /* Choose the longer suffix.  */
+  if (max_suffix_rev + 1 < max_suffix + 1)
+    return max_suffix + 1;
+  *period = p;
+  return max_suffix_rev + 1;
+}
+
+/* Return the first location of NEEDLE within HAYSTACK, or NULL.  This
+   method requires 0 < NEEDLE_LEN <= HAYSTACK_LEN, and is optimized
+   for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.  Performance is linear,
+   with 2 * NEEDLE_LEN comparisons in preparation, and at most 2 *
+   HAYSTACK_LEN - NEEDLE_LEN comparisons in searching.  */
+static void *
+two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
+                     const unsigned char *needle, size_t needle_len)
+{
+  size_t i, j; /* Indices into haystack.  */
+  size_t period; /* The period of the right half of needle.  */
+  size_t suffix; /* The index of the right half of needle.  */
+
+  /* Factor the needle into two halves, such that the left half is
+     smaller than the global period, and the right half is
+     periodic.  */
+  suffix = critical_factorization (needle, needle_len, &period);
+
+  /* Perform the search.  Each iteration compares the right half
+     first.  */
+  if (memcmp (needle, needle + period, suffix) == 0)
+    {
+      /* Needle is periodic; a mismatch can only advance by the
+        period, so use memory to avoid rescanning known occurrences
+        of the period.  */
+      size_t memory = 0;
+      j = 0;
+      while (j <= haystack_len - needle_len)
+       {
+         /* Scan for matches in right half.  */
+         i = suffix < memory ? memory : suffix;
+         while (i < needle_len && needle[i] == haystack[i + j])
+           ++i;
+         if (needle_len <= i)
+           {
+             /* Scan for matches in left half.  */
+             i = suffix - 1;
+             while (memory < i + 1 && needle[i] == haystack[i + j])
+               --i;
+             if (i + 1 < memory + 1)
+               return (void *) (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.  */
+      period = MAX (suffix, needle_len - suffix) + 1;
+      j = 0;
+      while (j <= haystack_len - needle_len)
+       {
+         /* Scan for matches in right half.  */
+         i = suffix;
+         while (i < needle_len && needle[i] == haystack[i + j])
+           ++i;
+         if (needle_len <= i)
+           {
+             /* Scan for matches in left half.  */
+             i = suffix - 1;
+             while (i != SIZE_MAX && needle[i] == haystack[i + j])
+               --i;
+             if (i == SIZE_MAX)
+               return (void *) (haystack + j);
+             j += period;
+           }
+         else
+           j += i - suffix + 1;
        }
-  }
+    }
+  return NULL;
+}
+
+/* Return the first location of NEEDLE within HAYSTACK, or NULL.  This
+   method requires 0 < NEEDLE_LEN <= HAYSTACK_LEN, and is optimized
+   for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.  Performance is linear,
+   with 3 * NEEDLE_LEN operations in preparation, and at most 2 *
+   HAYSTACK_LEN - NEEDLE_LEN comparisons in searching.  The extra
+   initialization cost allows for potential sublinear performance
+   O(HAYSTACK_LEN / NEEDLE_LEN).  */
+static void *
+two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
+                    const unsigned char *needle, size_t needle_len)
+{
+  size_t i, j; /* Indices into haystack.  */
+  size_t period; /* The period of the right half of needle.  */
+  size_t suffix; /* The index of the right half of needle.  */
+  size_t shift_table[1 << CHAR_BIT];
+
+  /* Factor the needle into two halves, such that the left half is
+     smaller than the global period, and the right half is
+     periodic.  */
+  suffix = critical_factorization (needle, needle_len, &period);
 
-  freea (table);
-  return true;
+  /* Populate shift_table.  For each possible byte value c,
+     shift_table[c] is the distance from the last occurrence of c to
+     the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
+     shift_table[needle[needle_len - 1]] contains the only 0.  */
+  for (i = 0; i < 1 << CHAR_BIT; i++)
+    shift_table[i] = needle_len;
+  for (i = 0; i < needle_len; i++)
+    shift_table[needle[i]] = needle_len - i - 1;
+
+  /* Perform the search.  Each iteration compares the right half
+     first.  */
+  if (memcmp (needle, needle + period, suffix) == 0)
+    {
+      /* Needle is periodic; a mismatch can only advance by the
+        period, so use memory to avoid rescanning known occurrences
+        of the period.  */
+      size_t memory = 0;
+      j = 0;
+      while (j <= haystack_len - needle_len)
+       {
+         /* Check the last byte first; if it does not match, then
+            shift to the next possible match location.  */
+         size_t shift = shift_table[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 = suffix < memory ? memory : suffix;
+         while (i < needle_len - 1 && needle[i] == haystack[i + j])
+           ++i;
+         if (needle_len - 1 <= i)
+           {
+             /* Scan for matches in left half.  */
+             i = suffix - 1;
+             while (memory < i + 1 && needle[i] == haystack[i + j])
+               --i;
+             if (i + 1 < memory + 1)
+               return (void *) (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.  */
+      period = MAX (suffix, needle_len - suffix) + 1;
+      j = 0;
+      while (j <= haystack_len - needle_len)
+       {
+         /* Check the last byte first; if it does not match, then
+            shift to the next possible match location.  */
+         size_t shift = shift_table[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 && needle[i] == haystack[i + j])
+           ++i;
+         if (needle_len - 1 <= i)
+           {
+             /* Scan for matches in left half.  */
+             i = suffix - 1;
+             while (i != SIZE_MAX && needle[i] == haystack[i + j])
+               --i;
+             if (i == SIZE_MAX)
+               return (void *) (haystack + j);
+             j += period;
+           }
+         else
+           j += i - suffix + 1;
+       }
+    }
+  return NULL;
 }
 
 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
@@ -162,8 +368,6 @@ memmem (const void *haystack_start, size_t haystack_len,
      not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
   const unsigned char *haystack = (const unsigned char *) haystack_start;
   const unsigned char *needle = (const unsigned char *) needle_start;
-  const unsigned char *last_haystack = haystack + haystack_len;
-  const unsigned char *last_needle = needle + needle_len;
 
   if (needle_len == 0)
     /* The first occurrence of the empty string is deemed to occur at
@@ -175,82 +379,23 @@ memmem (const void *haystack_start, size_t haystack_len,
   if (__builtin_expect (haystack_len < needle_len, 0))
     return NULL;
 
-  /* Use optimizations in memchr when possible.  */
-  if (__builtin_expect (needle_len == 1, 0))
-    return memchr (haystack, *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
-       byte.  */
-    unsigned 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 unsigned 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 byte matches.  */
-         {
-           const unsigned char *rhaystack = haystack + 1;
-           const unsigned 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;
+  /* Use optimizations in memchr when possible, to reduce the search
+     size of haystack using a linear algorithm with a smaller
+     coefficient.  However, avoid memchr for long needles, since we
+     can often acheive sublinear performance.  */
+  if (needle_len < LONG_NEEDLE_THRESHOLD)
+    {
+      haystack = memchr (haystack, *needle, haystack_len);
+      if (!haystack || __builtin_expect (needle_len == 1, 0))
+       return (void *) haystack;
+      haystack_len -= haystack - (const unsigned char *) haystack_start;
+      if (haystack_len < needle_len)
+       return NULL;
+      return two_way_short_needle (haystack, haystack_len, needle, needle_len);
+    }
+  else
+    return two_way_long_needle (haystack, haystack_len, needle, needle_len);
 }
+
+#undef LONG_NEEDLE_THRESHOLD
+#undef MAX
diff --git a/modules/memmem b/modules/memmem
index 738cd6a..2c02be9 100644
--- a/modules/memmem
+++ b/modules/memmem
@@ -8,8 +8,7 @@ m4/memmem.m4
 Depends-on:
 extensions
 string
-stdbool
-malloca
+stdint
 memchr
 memcmp
 
diff --git a/tests/test-memmem.c b/tests/test-memmem.c
index 976f293..e900e1c 100644
--- a/tests/test-memmem.c
+++ b/tests/test-memmem.c
@@ -152,5 +152,32 @@ main (int argc, char *argv[])
       free (haystack);
   }
 
+  /* Check that a some long needles not present in a haystack can be
+     handled with sublinear speed.  */
+  {
+    size_t repeat = 10000;
+    size_t m = 1000000;
+    size_t n = 1000;
+    char *haystack = (char *) malloc (m);
+    char *needle = (char *) malloc (n);
+    if (haystack != NULL && needle != NULL)
+      {
+       const char *result;
+
+       memset (haystack, 'A', m);
+       memset (needle, 'B', n);
+
+       for (; repeat > 0; repeat--)
+         {
+           result = memmem (haystack, m, needle, n);
+           ASSERT (result == NULL);
+         }
+      }
+    if (haystack != NULL)
+      free (haystack);
+    if (needle != NULL)
+      free (needle);
+  }
+
   return 0;
 }
-- 
1.5.3.5