lib/memmem.c

   1 /* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License along
  15    with this program; if not, write to the Free Software Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  17
  18 #ifndef _LIBC
  19 # include <config.h>
  20 #endif
  21
  22 #include <stddef.h>
  23 #include <string.h>
  24 #include <stdbool.h>
  25
  26 #include "malloca.h"
  27
  28 #ifndef _LIBC
  29 # define __builtin_expect(expr, val)   (expr)
  30 #endif
  31
  32 /* Knuth-Morris-Pratt algorithm.
  33    See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  34    Return a boolean indicating success.  */
  35
  36 static bool
  37 knuth_morris_pratt (const char *haystack, const char *last_haystack,
  38                     const char *needle, size_t m,
  39                     const char **resultp)
  40 {
  41   /* Allocate the table.  */
  42   size_t *table = (size_t *) malloca (m * sizeof (size_t));
  43   if (table == NULL)
  44     return false;
  45   /* Fill the table.
  46      For 0 < i < m:
  47        0 < table[i] <= i is defined such that
  48        rhaystack[0..i-1] == needle[0..i-1] and rhaystack[i] != needle[i]
  49        implies
  50        forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1],
  51        and table[i] is as large as possible with this property.
  52      table[0] remains uninitialized.  */
  53   {
  54     size_t i, j;
  55
  56     table[1] = 1;
  57     j = 0;
  58     for (i = 2; i < m; i++)
  59       {
  60         unsigned char b = (unsigned char) needle[i - 1];
  61
  62         for (;;)
  63           {
  64             if (b == (unsigned char) needle[j])
  65               {
  66                 table[i] = i - ++j;
  67                 break;
  68               }
  69             if (j == 0)
  70               {
  71                 table[i] = i;
  72                 break;
  73               }
  74             j = j - table[j];
  75           }
  76       }
  77   }
  78
  79   /* Search, using the table to accelerate the processing.  */
  80   {
  81     size_t j;
  82     const char *rhaystack;
  83     const char *phaystack;
  84
  85     *resultp = NULL;
  86     j = 0;
  87     rhaystack = haystack;
  88     phaystack = haystack;
  89     /* Invariant: phaystack = rhaystack + j.  */
  90     while (phaystack != last_haystack)
  91       if ((unsigned char) needle[j] == (unsigned char) *phaystack)
  92         {
  93           j++;
  94           phaystack++;
  95           if (j == m)
  96             {
  97               /* The entire needle has been found.  */
  98               *resultp = rhaystack;
  99               break;
 100             }
 101         }
 102       else if (j > 0)
 103         {
 104           /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 105           rhaystack += table[j];
 106           j -= table[j];
 107         }
 108       else
 109         {
 110           /* Found a mismatch at needle[0] already.  */
 111           rhaystack++;
 112           phaystack++;
 113         }
 114   }
 115
 116   freea (table);
 117   return true;
 118 }
 119
 120 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
 121    if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
 122    HAYSTACK.  */
 123 void *
 124 memmem (const void *haystack, size_t haystack_len,
 125         const void *needle, size_t needle_len)
 126 {
 127   /* Operating with void * is awkward.  */
 128   const char *Haystack = (const char *) haystack;
 129   const char *Needle = (const char *) needle;
 130   const char *last_haystack = Haystack + haystack_len;
 131   const char *last_needle = Needle + needle_len;
 132
 133   if (needle_len == 0)
 134     /* The first occurrence of the empty string is deemed to occur at
 135        the beginning of the string.  */
 136     return (void *) haystack;
 137
 138   /* Sanity check, otherwise the loop might search through the whole
 139      memory.  */
 140   if (__builtin_expect (haystack_len < needle_len, 0))
 141     return NULL;
 142
 143   /* Use optimizations in memchr when possible.  */
 144   if (__builtin_expect (needle_len == 1, 0))
 145     return memchr (haystack, (unsigned char) *Needle, haystack_len);
 146
 147   /* Minimizing the worst-case complexity:
 148      Let n = haystack_len, m = needle_len.
 149      The naïve algorithm is O(n*m) worst-case.
 150      The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 151      memory allocation.
 152      To achieve linear complexity and yet amortize the cost of the
 153      memory allocation, we activate the Knuth-Morris-Pratt algorithm
 154      only once the naïve algorithm has already run for some time; more
 155      precisely, when
 156        - the outer loop count is >= 10,
 157        - the average number of comparisons per outer loop is >= 5,
 158        - the total number of comparisons is >= m.
 159      But we try it only once.  If the memory allocation attempt failed,
 160      we don't retry it.  */
 161   {
 162     bool try_kmp = true;
 163     size_t outer_loop_count = 0;
 164     size_t comparison_count = 0;
 165
 166     /* Speed up the following searches of needle by caching its first
 167        character.  */
 168     char b = *Needle++;
 169
 170     for (;; Haystack++)
 171       {
 172         if (Haystack == last_haystack)
 173           /* No match.  */
 174           return NULL;
 175
 176         /* See whether it's advisable to use an asymptotically faster
 177            algorithm.  */
 178         if (try_kmp
 179             && outer_loop_count >= 10
 180             && comparison_count >= 5 * outer_loop_count)
 181           {
 182             /* See if needle + comparison_count now reaches the end of
 183                needle.  */
 184             if (comparison_count >= needle_len)
 185               {
 186                 /* Try the Knuth-Morris-Pratt algorithm.  */
 187                 const char *result;
 188                 if (knuth_morris_pratt (Haystack, last_haystack,
 189                                         Needle - 1, needle_len, &result))
 190                   return (void *) result;
 191                 try_kmp = false;
 192               }
 193           }
 194
 195         outer_loop_count++;
 196         comparison_count++;
 197         if (*Haystack == b)
 198           /* The first character matches.  */
 199           {
 200             const char *rhaystack = Haystack + 1;
 201             const char *rneedle = Needle;
 202
 203             for (;; rhaystack++, rneedle++)
 204               {
 205                 if (rneedle == last_needle)
 206                   /* Found a match.  */
 207                   return (void *) Haystack;
 208                 if (rhaystack == last_haystack)
 209                   /* No match.  */
 210                   return NULL;
 211                 comparison_count++;
 212                 if (*rhaystack != *rneedle)
 213                   /* Nothing in this round.  */
 214                   break;
 215               }
 216           }
 217       }
 218   }
 219
 220   return NULL;
 221 }