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;
  43   if ((size_t) -1 / sizeof (size_t) < m)
  44     return false;
  45   table = (size_t *) malloca (m * sizeof (size_t));
  46   if (table == NULL)
  47     return false;
  48   /* Fill the table.
  49      For 0 < i < m:
  50        0 < table[i] <= i is defined such that
  51        forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
  52        and table[i] is as large as possible with this property.
  53      This implies:
  54      1) For 0 < i < m:
  55           If table[i] < i,
  56           needle[table[i]..i-1] = needle[0..i-1-table[i]].
  57      2) For 0 < i < m:
  58           rhaystack[0..i-1] == needle[0..i-1]
  59           and exists h, i <= h < m: rhaystack[h] != needle[h]
  60           implies
  61           forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
  62      table[0] remains uninitialized.  */
  63   {
  64     size_t i, j;
  65
  66     /* i = 1: Nothing to verify for x = 0.  */
  67     table[1] = 1;
  68     j = 0;
  69
  70     for (i = 2; i < m; i++)
  71       {
  72         /* Here: j = i-1 - table[i-1].
  73            The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
  74            for x < table[i-1], by induction.
  75            Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
  76         unsigned char b = (unsigned char) needle[i - 1];
  77
  78         for (;;)
  79           {
  80             /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
  81                is known to hold for x < i-1-j.
  82                Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
  83             if (b == (unsigned char) needle[j])
  84               {
  85                 /* Set table[i] := i-1-j.  */
  86                 table[i] = i - ++j;
  87                 break;
  88               }
  89             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
  90                for x = i-1-j, because
  91                  needle[i-1] != needle[j] = needle[i-1-x].  */
  92             if (j == 0)
  93               {
  94                 /* The inequality holds for all possible x.  */
  95                 table[i] = i;
  96                 break;
  97               }
  98             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
  99                for i-1-j < x < i-1-j+table[j], because for these x:
 100                  needle[x..i-2]
 101                  = needle[x-(i-1-j)..j-1]
 102                  != needle[0..j-1-(x-(i-1-j))]  (by definition of table[j])
 103                     = needle[0..i-2-x],
 104                hence needle[x..i-1] != needle[0..i-1-x].
 105                Furthermore
 106                  needle[i-1-j+table[j]..i-2]
 107                  = needle[table[j]..j-1]
 108                  = needle[0..j-1-table[j]]  (by definition of table[j]).  */
 109             j = j - table[j];
 110           }
 111         /* Here: j = i - table[i].  */
 112       }
 113   }
 114
 115   /* Search, using the table to accelerate the processing.  */
 116   {
 117     size_t j;
 118     const char *rhaystack;
 119     const char *phaystack;
 120
 121     *resultp = NULL;
 122     j = 0;
 123     rhaystack = haystack;
 124     phaystack = haystack;
 125     /* Invariant: phaystack = rhaystack + j.  */
 126     while (phaystack != last_haystack)
 127       if ((unsigned char) needle[j] == (unsigned char) *phaystack)
 128         {
 129           j++;
 130           phaystack++;
 131           if (j == m)
 132             {
 133               /* The entire needle has been found.  */
 134               *resultp = rhaystack;
 135               break;
 136             }
 137         }
 138       else if (j > 0)
 139         {
 140           /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 141           rhaystack += table[j];
 142           j -= table[j];
 143         }
 144       else
 145         {
 146           /* Found a mismatch at needle[0] already.  */
 147           rhaystack++;
 148           phaystack++;
 149         }
 150   }
 151
 152   freea (table);
 153   return true;
 154 }
 155
 156 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
 157    if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
 158    HAYSTACK.  */
 159 void *
 160 memmem (const void *haystack_start, size_t haystack_len,
 161         const void *needle_start, size_t needle_len)
 162 {
 163   /* Operating with void * is awkward.  */
 164   const char *haystack = (const char *) haystack_start;
 165   const char *needle = (const char *) needle_start;
 166   const char *last_haystack = haystack + haystack_len;
 167   const char *last_needle = needle + needle_len;
 168
 169   if (needle_len == 0)
 170     /* The first occurrence of the empty string is deemed to occur at
 171        the beginning of the string.  */
 172     return (void *) haystack;
 173
 174   /* Sanity check, otherwise the loop might search through the whole
 175      memory.  */
 176   if (__builtin_expect (haystack_len < needle_len, 0))
 177     return NULL;
 178
 179   /* Use optimizations in memchr when possible.  */
 180   if (__builtin_expect (needle_len == 1, 0))
 181     return memchr (haystack, (unsigned char) *needle, haystack_len);
 182
 183   /* Minimizing the worst-case complexity:
 184      Let n = haystack_len, m = needle_len.
 185      The naïve algorithm is O(n*m) worst-case.
 186      The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 187      memory allocation.
 188      To achieve linear complexity and yet amortize the cost of the
 189      memory allocation, we activate the Knuth-Morris-Pratt algorithm
 190      only once the naïve algorithm has already run for some time; more
 191      precisely, when
 192        - the outer loop count is >= 10,
 193        - the average number of comparisons per outer loop is >= 5,
 194        - the total number of comparisons is >= m.
 195      But we try it only once.  If the memory allocation attempt failed,
 196      we don't retry it.  */
 197   {
 198     bool try_kmp = true;
 199     size_t outer_loop_count = 0;
 200     size_t comparison_count = 0;
 201
 202     /* Speed up the following searches of needle by caching its first
 203        byte.  */
 204     char b = *needle++;
 205
 206     for (;; haystack++)
 207       {
 208         if (haystack == last_haystack)
 209           /* No match.  */
 210           return NULL;
 211
 212         /* See whether it's advisable to use an asymptotically faster
 213            algorithm.  */
 214         if (try_kmp
 215             && outer_loop_count >= 10
 216             && comparison_count >= 5 * outer_loop_count)
 217           {
 218             /* See if needle + comparison_count now reaches the end of
 219                needle.  */
 220             if (comparison_count >= needle_len)
 221               {
 222                 /* Try the Knuth-Morris-Pratt algorithm.  */
 223                 const char *result;
 224                 if (knuth_morris_pratt (haystack, last_haystack,
 225                                         needle - 1, needle_len, &result))
 226                   return (void *) result;
 227                 try_kmp = false;
 228               }
 229           }
 230
 231         outer_loop_count++;
 232         comparison_count++;
 233         if (*haystack == b)
 234           /* The first byte matches.  */
 235           {
 236             const char *rhaystack = haystack + 1;
 237             const char *rneedle = needle;
 238
 239             for (;; rhaystack++, rneedle++)
 240               {
 241                 if (rneedle == last_needle)
 242                   /* Found a match.  */
 243                   return (void *) haystack;
 244                 if (rhaystack == last_haystack)
 245                   /* No match.  */
 246                   return NULL;
 247                 comparison_count++;
 248                 if (*rhaystack != *rneedle)
 249                   /* Nothing in this round.  */
 250                   break;
 251               }
 252           }
 253       }
 254   }
 255
 256   return NULL;
 257 }