Re: memmem issues

[Bruno Haible]

Eric Blake wrote:
> +     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.

While considering to submit a modified version of this code to glibc
for inclusion, I found it good to make the code adhere better to
GNU coding conventions:
  - use lower cased local variable names,
  - use tab indentation (my fault).


2007-12-23  Bruno Haible  <address@hidden>

        * lib/memmem.c (memmem): Use lowercase variable names. Tab
        indentation.

*** lib/memmem.c.orig   2007-12-23 21:31:31.000000000 +0100
--- lib/memmem.c        2007-12-23 21:31:03.000000000 +0100
***************
*** 154,167 ****
     if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
     HAYSTACK.  */
  void *
! memmem (const void *haystack, size_t haystack_len,
!         const void *needle, size_t 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
--- 154,167 ----
     if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
     HAYSTACK.  */
  void *
! memmem (const void *haystack_start, size_t haystack_len,
!       const void *needle_start, size_t needle_len)
  {
    /* Operating with void * is awkward.  */
!   const char *haystack = (const char *) haystack_start;
!   const char *needle = (const char *) needle_start;
!   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
***************
*** 175,181 ****
  
    /* 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.
--- 175,181 ----
  
    /* 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.
***************
*** 198,252 ****
  
      /* Speed up the following searches of needle by caching its first
         byte.  */
!     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 byte 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;
!               }
!           }
        }
    }
  
--- 198,252 ----
  
      /* Speed up the following searches of needle by caching its first
         byte.  */
!     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 byte 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;
!             }
!         }
        }
    }