string/str-two-way.h

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