lib/strstr.c

   1 /* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007,2008 Free Software
   2    Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License along
  16    with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /* This particular implementation was written by Eric Blake, 2008.  */
  20
  21 #ifndef _LIBC
  22 # include <config.h>
  23 #endif
  24
  25 /* Specification of strstr.  */
  26 #include <string.h>
  27
  28 #include <limits.h>
  29 #include <stdbool.h>
  30 #include <stddef.h>
  31 #include <stdint.h>
  32
  33 #ifndef _LIBC
  34 # define __builtin_expect(expr, val)   (expr)
  35 #endif
  36
  37 /* We use the Two-Way string matching algorithm, which guarantees
  38    linear complexity with constant space.  Additionally, for long
  39    needles, we also use a bad character shift table similar to the
  40    Boyer-Moore algorithm to achieve better performance.
  41
  42    See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
  43    and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
  44 */
  45
  46 /* Point at which computing a bad-byte shift table is likely to be
  47    worthwhile.  Small needles should not compute a table, since it
  48    adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
  49    speedup no greater than a factor of NEEDLE_LEN.  The larger the
  50    needle, the better the potential performance gain.  On the other
  51    hand, on non-POSIX systems with CHAR_BIT larger than eight, the
  52    memory required for the table is prohibitive.  */
  53 #if CHAR_BIT < 10
  54 # define LONG_NEEDLE_THRESHOLD 32U
  55 #else
  56 # define LONG_NEEDLE_THRESHOLD SIZE_MAX
  57 #endif
  58
  59 #define MAX(a, b) ((a < b) ? (b) : (a))
  60
  61 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
  62    Return the index of the first byte in the right half, and set
  63    *PERIOD to the global period of the right half.
  64
  65    The global period of a string is the smallest index (possibly its
  66    length) at which all remaining bytes in the string are repetitions
  67    of the prefix (the last repetition may be a subset of the prefix).
  68
  69    When NEEDLE is factored into two halves, a local period is the
  70    length of the smallest word that shares a suffix with the left half
  71    and shares a prefix with the right half.  All factorizations of a
  72    non-empty NEEDLE have a local period of at least 1 and no greater
  73    than NEEDLE_LEN.
  74
  75    A critical factorization has the property that the local period
  76    equals the global period.  All strings have at least one critical
  77    factorization with the left half smaller than the global period.
  78
  79    Given an ordered alphabet, a critical factorization can be computed
  80    in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
  81    larger of two ordered maximal suffixes.  The ordered maximal
  82    suffixes are determined by lexicographic comparison of
  83    periodicity.  */
  84 static size_t
  85 critical_factorization (const unsigned char *needle, size_t needle_len,
  86                         size_t *period)
  87 {
  88   /* Index of last byte of left half, or SIZE_MAX.  */
  89   size_t max_suffix, max_suffix_rev;
  90   size_t j; /* Index into NEEDLE for current candidate suffix.  */
  91   size_t k; /* Offset into current period.  */
  92   size_t p; /* Intermediate period.  */
  93   unsigned char a, b; /* Current comparison bytes.  */
  94
  95   /* Invariants:
  96      0 <= j < NEEDLE_LEN - 1
  97      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
  98      min(max_suffix, max_suffix_rev) < global period of NEEDLE
  99      1 <= p <= global period of NEEDLE
 100      p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
 101      1 <= k <= p
 102   */
 103
 104   /* Perform lexicographic search.  */
 105   max_suffix = SIZE_MAX;
 106   j = 0;
 107   k = p = 1;
 108   while (j + k < needle_len)
 109     {
 110       a = needle[j + k];
 111       b = needle[max_suffix + k];
 112       if (a < b)
 113         {
 114           /* Suffix is smaller, period is entire prefix so far.  */
 115           j += k;
 116           k = 1;
 117           p = j - max_suffix;
 118         }
 119       else if (a == b)
 120         {
 121           /* Advance through repetition of the current period.  */
 122           if (k != p)
 123             ++k;
 124           else
 125             {
 126               j += p;
 127               k = 1;
 128             }
 129         }
 130       else /* b < a */
 131         {
 132           /* Suffix is larger, start over from current location.  */
 133           max_suffix = j++;
 134           k = p = 1;
 135         }
 136     }
 137   *period = p;
 138
 139   /* Perform reverse lexicographic search.  */
 140   max_suffix_rev = SIZE_MAX;
 141   j = 0;
 142   k = p = 1;
 143   while (j + k < needle_len)
 144     {
 145       a = needle[j + k];
 146       b = needle[max_suffix_rev + k];
 147       if (b < a)
 148         {
 149           /* Suffix is smaller, period is entire prefix so far.  */
 150           j += k;
 151           k = 1;
 152           p = j - max_suffix_rev;
 153         }
 154       else if (a == b)
 155         {
 156           /* Advance through repetition of the current period.  */
 157           if (k != p)
 158             ++k;
 159           else
 160             {
 161               j += p;
 162               k = 1;
 163             }
 164         }
 165       else /* a < b */
 166         {
 167           /* Suffix is larger, start over from current location.  */
 168           max_suffix_rev = j++;
 169           k = p = 1;
 170         }
 171     }
 172
 173   /* Choose the longer suffix.  Return the first byte of the right
 174      half, rather than the last byte of the left half.  */
 175   if (max_suffix_rev + 1 < max_suffix + 1)
 176     return max_suffix + 1;
 177   *period = p;
 178   return max_suffix_rev + 1;
 179 }
 180
 181 /* Return the first location of NEEDLE within HAYSTACK, or NULL.  This
 182    method requires 0 < NEEDLE_LEN <= HAYSTACK_LEN, and is optimized
 183    for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.  Performance is linear,
 184    with 2 * NEEDLE_LEN comparisons in preparation, and at most 3 *
 185    HAYSTACK_LEN - NEEDLE_LEN comparisons in searching.  */
 186 static char *
 187 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 188                       const unsigned char *needle, size_t needle_len)
 189 {
 190   size_t i; /* Index into current byte of NEEDLE.  */
 191   size_t j; /* Index into current window of HAYSTACK.  */
 192   size_t period; /* The period of the right half of needle.  */
 193   size_t suffix; /* The index of the right half of needle.  */
 194
 195   /* Factor the needle into two halves, such that the left half is
 196      smaller than the global period, and the right half is
 197      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 198   suffix = critical_factorization (needle, needle_len, &period);
 199
 200   /* Perform the search.  Each iteration compares the right half
 201      first.  */
 202   if (memcmp (needle, needle + period, suffix) == 0)
 203     {
 204       /* Entire needle is periodic; a mismatch can only advance by the
 205          period, so use memory to avoid rescanning known occurrences
 206          of the period.  */
 207       size_t memory = 0;
 208       j = 0;
 209       while (!memchr (&haystack[haystack_len], '\0',
 210                       j + needle_len - haystack_len)
 211              && (haystack_len = j + needle_len))
 212         {
 213           /* Scan for matches in right half.  */
 214           i = MAX (suffix, memory);
 215           while (i < needle_len && needle[i] == haystack[i + j])
 216             ++i;
 217           if (needle_len <= i)
 218             {
 219               /* Scan for matches in left half.  */
 220               i = suffix - 1;
 221               while (memory < i + 1 && needle[i] == haystack[i + j])
 222                 --i;
 223               if (i + 1 < memory + 1)
 224                 return (char *) (haystack + j);
 225               /* No match, so remember how many repetitions of period
 226                  on the right half were scanned.  */
 227               j += period;
 228               memory = needle_len - period;
 229             }
 230           else
 231             {
 232               j += i - suffix + 1;
 233               memory = 0;
 234             }
 235         }
 236     }
 237   else
 238     {
 239       /* The two halves of needle are distinct; no extra memory is
 240          required, and any mismatch results in a maximal shift.  */
 241       period = MAX (suffix, needle_len - suffix) + 1;
 242       j = 0;
 243       while (!memchr (&haystack[haystack_len], '\0',
 244                       j + needle_len - haystack_len)
 245              && (haystack_len = j + needle_len))
 246         {
 247           /* Scan for matches in right half.  */
 248           i = suffix;
 249           while (i < needle_len && needle[i] == haystack[i + j])
 250             ++i;
 251           if (needle_len <= i)
 252             {
 253               /* Scan for matches in left half.  */
 254               i = suffix - 1;
 255               while (i != SIZE_MAX && needle[i] == haystack[i + j])
 256                 --i;
 257               if (i == SIZE_MAX)
 258                 return (char *) (haystack + j);
 259               j += period;
 260             }
 261           else
 262             j += i - suffix + 1;
 263         }
 264     }
 265   return NULL;
 266 }
 267
 268 /* Return the first location of NEEDLE within HAYSTACK, or NULL.  This
 269    method requires 0 < NEEDLE_LEN <= HAYSTACK_LEN, and is optimized
 270    for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.  Performance is linear,
 271    with 3 * NEEDLE_LEN + (1U << CHAR_BIT) operations in preparation,
 272    and at most 3 * HAYSTACK_LEN - NEEDLE_LEN comparisons in searching.
 273    The extra initialization cost allows for as few as HAYSTACK_LEN +
 274    HAYSTACK_LEN / NEEDLE_LEN.  */
 275 static char *
 276 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 277                      const unsigned char *needle, size_t needle_len)
 278 {
 279   size_t i; /* Index into current byte of NEEDLE.  */
 280   size_t j; /* Index into current window of HAYSTACK.  */
 281   size_t period; /* The period of the right half of needle.  */
 282   size_t suffix; /* The index of the right half of needle.  */
 283   size_t shift_table[1U << CHAR_BIT]; /* See below.  */
 284
 285   /* Factor the needle into two halves, such that the left half is
 286      smaller than the global period, and the right half is
 287      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 288   suffix = critical_factorization (needle, needle_len, &period);
 289
 290   /* Populate shift_table.  For each possible byte value c,
 291      shift_table[c] is the distance from the last occurrence of c to
 292      the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
 293      shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */
 294   for (i = 0; i < 1U << CHAR_BIT; i++)
 295     shift_table[i] = needle_len;
 296   for (i = 0; i < needle_len; i++)
 297     shift_table[needle[i]] = needle_len - i - 1;
 298
 299   /* Perform the search.  Each iteration compares the right half
 300      first.  */
 301   if (memcmp (needle, needle + period, suffix) == 0)
 302     {
 303       /* Entire needle is periodic; a mismatch can only advance by the
 304          period, so use memory to avoid rescanning known occurrences
 305          of the period.  */
 306       size_t memory = 0;
 307       j = 0;
 308       while (!memchr (&haystack[haystack_len], '\0',
 309                       j + needle_len - haystack_len)
 310              && (haystack_len = j + needle_len))
 311         {
 312           /* Check the last byte first; if it does not match, then
 313              shift to the next possible match location.  */
 314           size_t shift = shift_table[haystack[j + needle_len - 1]];
 315           if (0 < shift)
 316             {
 317               if (memory && shift < period)
 318                 {
 319                   /* Since needle is periodic, but the last period has
 320                      a byte out of place, there can be no match until
 321                      after the mismatch.  */
 322                   shift = needle_len - period;
 323                   memory = 0;
 324                 }
 325               j += shift;
 326               continue;
 327             }
 328           /* Scan for matches in right half.  The last byte has
 329              already been matched, by virtue of the shift table.  */
 330           i = MAX (suffix, memory);
 331           while (i < needle_len - 1 && needle[i] == haystack[i + j])
 332             ++i;
 333           if (needle_len - 1 <= i)
 334             {
 335               /* Scan for matches in left half.  */
 336               i = suffix - 1;
 337               while (memory < i + 1 && needle[i] == haystack[i + j])
 338                 --i;
 339               if (i + 1 < memory + 1)
 340                 return (char *) (haystack + j);
 341               /* No match, so remember how many repetitions of period
 342                  on the right half were scanned.  */
 343               j += period;
 344               memory = needle_len - period;
 345             }
 346           else
 347             {
 348               j += i - suffix + 1;
 349               memory = 0;
 350             }
 351         }
 352     }
 353   else
 354     {
 355       /* The two halves of needle are distinct; no extra memory is
 356          required, and any mismatch results in a maximal shift.  */
 357       period = MAX (suffix, needle_len - suffix) + 1;
 358       j = 0;
 359       while (!memchr (&haystack[haystack_len], '\0',
 360                       j + needle_len - haystack_len)
 361              && (haystack_len = j + needle_len))
 362         {
 363           /* Check the last byte first; if it does not match, then
 364              shift to the next possible match location.  */
 365           size_t shift = shift_table[haystack[j + needle_len - 1]];
 366           if (0 < shift)
 367             {
 368               j += shift;
 369               continue;
 370             }
 371           /* Scan for matches in right half.  The last byte has
 372              already been matched, by virtue of the shift table.  */
 373           i = suffix;
 374           while (i < needle_len - 1 && needle[i] == haystack[i + j])
 375             ++i;
 376           if (needle_len - 1 <= i)
 377             {
 378               /* Scan for matches in left half.  */
 379               i = suffix - 1;
 380               while (i != SIZE_MAX && needle[i] == haystack[i + j])
 381                 --i;
 382               if (i == SIZE_MAX)
 383                 return (char *) (haystack + j);
 384               j += period;
 385             }
 386           else
 387             j += i - suffix + 1;
 388         }
 389     }
 390   return NULL;
 391 }
 392
 393 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
 394    if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
 395    HAYSTACK.  */
 396 char *
 397 strstr (const char *haystack_start, const char *needle_start)
 398 {
 399   const char *haystack = haystack_start;
 400   const char *needle = needle_start;
 401   size_t needle_len; /* Length of NEEDLE.  */
 402   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
 403   bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
 404
 405   /* Determine length of NEEDLE, and in the process, make sure
 406      HAYSTACK is at least as long (no point processing all of a long
 407      NEEDLE if HAYSTACK is too short).  */
 408   while (*haystack && *needle)
 409     ok &= *haystack++ == *needle++;
 410   if (*needle)
 411     return NULL;
 412   if (ok)
 413     return (char *) haystack_start;
 414
 415   /* Reduce the size of haystack using strchr, since it has a smaller
 416      linear coefficient than the Two-Way algorithm.  */
 417   needle_len = needle - needle_start;
 418   haystack = strchr (haystack_start + 1, *needle_start);
 419   if (!haystack || __builtin_expect (needle_len == 1, 0))
 420     return (char *) haystack;
 421   needle -= needle_len;
 422   haystack_len = (haystack > haystack_start + needle_len ? 1
 423                   : needle_len + haystack_start - haystack);
 424
 425   /* Perform the search.  Abstract memory is considered to be an array
 426      of 'unsigned char' values, not an array of 'char' values.  See
 427      ISO C 99 section 6.2.6.1.  */
 428   if (needle_len < LONG_NEEDLE_THRESHOLD)
 429     return two_way_short_needle ((const unsigned char *) haystack,
 430                                  haystack_len,
 431                                  (const unsigned char *) needle, needle_len);
 432   return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
 433                               (const unsigned char *) needle, needle_len);
 434 }
 435
 436 #undef LONG_NEEDLE_THRESHOLD
 437 #undef MAX