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