lib/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    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    This program 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
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License along
  17    with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 /* Before including this file, you need to include <config.h> and
  21    <string.h>, 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
  47 /* We use the Two-Way string matching algorithm (also known as
  48    Chrochemore-Perrin), which guarantees linear complexity with
  49    constant space.  Additionally, for long needles, we also use a bad
  50    character shift table similar to the Boyer-Moore algorithm to
  51    achieve improved (potentially sub-linear) performance.
  52
  53    See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260,
  54    http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm,
  55    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.6641&rep=rep1&type=pdf
  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 MAX
  72 # define MAX(a, b) ((a < b) ? (b) : (a))
  73 #endif
  74
  75 #ifndef CANON_ELEMENT
  76 # define CANON_ELEMENT(c) c
  77 #endif
  78 #ifndef CMP_FUNC
  79 # define CMP_FUNC memcmp
  80 #endif
  81
  82 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
  83    Return the index of the first byte in the right half, and set
  84    *PERIOD to the global period of the right half.
  85
  86    The global period of a string is the smallest index (possibly its
  87    length) at which all remaining bytes in the string are repetitions
  88    of the prefix (the last repetition may be a subset of the prefix).
  89
  90    When NEEDLE is factored into two halves, a local period is the
  91    length of the smallest word that shares a suffix with the left half
  92    and shares a prefix with the right half.  All factorizations of a
  93    non-empty NEEDLE have a local period of at least 1 and no greater
  94    than NEEDLE_LEN.
  95
  96    A critical factorization has the property that the local period
  97    equals the global period.  All strings have at least one critical
  98    factorization with the left half smaller than the global period.
  99    And while some strings have more than one critical factorization,
 100    it is provable that with an ordered alphabet, at least one of the
 101    critical factorizations corresponds to a maximal suffix.
 102
 103    Given an ordered alphabet, a critical factorization can be computed
 104    in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
 105    shorter of two ordered maximal suffixes.  The ordered maximal
 106    suffixes are determined by lexicographic comparison while tracking
 107    periodicity.  */
 108 static size_t
 109 critical_factorization (const unsigned char *needle, size_t needle_len,
 110                         size_t *period)
 111 {
 112   /* Index of last byte of left half, or SIZE_MAX.  */
 113   size_t max_suffix, max_suffix_rev;
 114   size_t j; /* Index into NEEDLE for current candidate suffix.  */
 115   size_t k; /* Offset into current period.  */
 116   size_t p; /* Intermediate period.  */
 117   unsigned char a, b; /* Current comparison bytes.  */
 118
 119   /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
 120      out 0-length needles.  */
 121   if (needle_len < 3)
 122     {
 123       *period = 1;
 124       return needle_len - 1;
 125     }
 126
 127   /* Invariants:
 128      0 <= j < NEEDLE_LEN - 1
 129      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
 130      min(max_suffix, max_suffix_rev) < global period of NEEDLE
 131      1 <= p <= global period of NEEDLE
 132      p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
 133      1 <= k <= p
 134   */
 135
 136   /* Perform lexicographic search.  */
 137   max_suffix = SIZE_MAX;
 138   j = 0;
 139   k = p = 1;
 140   while (j + k < needle_len)
 141     {
 142       a = CANON_ELEMENT (needle[j + k]);
 143       b = CANON_ELEMENT (needle[max_suffix + k]);
 144       if (a < b)
 145         {
 146           /* Suffix is smaller, period is entire prefix so far.  */
 147           j += k;
 148           k = 1;
 149           p = j - max_suffix;
 150         }
 151       else if (a == b)
 152         {
 153           /* Advance through repetition of the current period.  */
 154           if (k != p)
 155             ++k;
 156           else
 157             {
 158               j += p;
 159               k = 1;
 160             }
 161         }
 162       else /* b < a */
 163         {
 164           /* Suffix is larger, start over from current location.  */
 165           max_suffix = j++;
 166           k = p = 1;
 167         }
 168     }
 169   *period = p;
 170
 171   /* Perform reverse lexicographic search.  */
 172   max_suffix_rev = SIZE_MAX;
 173   j = 0;
 174   k = p = 1;
 175   while (j + k < needle_len)
 176     {
 177       a = CANON_ELEMENT (needle[j + k]);
 178       b = CANON_ELEMENT (needle[max_suffix_rev + k]);
 179       if (b < a)
 180         {
 181           /* Suffix is smaller, period is entire prefix so far.  */
 182           j += k;
 183           k = 1;
 184           p = j - max_suffix_rev;
 185         }
 186       else if (a == b)
 187         {
 188           /* Advance through repetition of the current period.  */
 189           if (k != p)
 190             ++k;
 191           else
 192             {
 193               j += p;
 194               k = 1;
 195             }
 196         }
 197       else /* a < b */
 198         {
 199           /* Suffix is larger, start over from current location.  */
 200           max_suffix_rev = j++;
 201           k = p = 1;
 202         }
 203     }
 204
 205   /* Choose the shorter suffix.  Return the index of the first byte of
 206      the right half, rather than the last byte of the left half.
 207
 208      For some examples, 'banana' has two critical factorizations, both
 209      exposed by the two lexicographic extreme suffixes of 'anana' and
 210      'nana', where both suffixes have a period of 2.  On the other
 211      hand, with 'aab' and 'bba', both strings have a single critical
 212      factorization of the last byte, with the suffix having a period
 213      of 1.  While the maximal lexicographic suffix of 'aab' is 'b',
 214      the maximal lexicographic suffix of 'bba' is 'ba', which is not a
 215      critical factorization.  Conversely, the maximal reverse
 216      lexicographic suffix of 'a' works for 'bba', but not 'ab' for
 217      'aab'.  The shorter suffix of the two will always be a critical
 218      factorization.  */
 219   if (max_suffix_rev + 1 < max_suffix + 1)
 220     return max_suffix + 1;
 221   *period = p;
 222   return max_suffix_rev + 1;
 223 }
 224
 225 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 226    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
 227    method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
 228    Performance is guaranteed to be linear, with an initialization cost
 229    of 2 * NEEDLE_LEN comparisons.
 230
 231    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 232    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
 233    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 234    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
 235 static RETURN_TYPE
 236 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 237                       const unsigned char *needle, size_t needle_len)
 238 {
 239   size_t i; /* Index into current byte of NEEDLE.  */
 240   size_t j; /* Index into current window of HAYSTACK.  */
 241   size_t period; /* The period of the right half of needle.  */
 242   size_t suffix; /* The index of the right half of needle.  */
 243
 244   /* Factor the needle into two halves, such that the left half is
 245      smaller than the global period, and the right half is
 246      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 247   suffix = critical_factorization (needle, needle_len, &period);
 248
 249   /* Perform the search.  Each iteration compares the right half
 250      first.  */
 251   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 252     {
 253       /* Entire needle is periodic; a mismatch in the left half can
 254          only advance by the period, so use memory to avoid rescanning
 255          known occurrences of the period in the right half.  */
 256       size_t memory = 0;
 257       j = 0;
 258       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 259         {
 260           /* Scan for matches in right half.  */
 261           i = MAX (suffix, memory);
 262           while (i < needle_len && (CANON_ELEMENT (needle[i])
 263                                     == CANON_ELEMENT (haystack[i + j])))
 264             ++i;
 265           if (needle_len <= i)
 266             {
 267               /* Scan for matches in left half.  */
 268               i = suffix - 1;
 269               while (memory < i + 1 && (CANON_ELEMENT (needle[i])
 270                                         == CANON_ELEMENT (haystack[i + j])))
 271                 --i;
 272               if (i + 1 < memory + 1)
 273                 return (RETURN_TYPE) (haystack + j);
 274               /* No match, so remember how many repetitions of period
 275                  on the right half were scanned.  */
 276               j += period;
 277               memory = needle_len - period;
 278             }
 279           else
 280             {
 281               j += i - suffix + 1;
 282               memory = 0;
 283             }
 284         }
 285     }
 286   else
 287     {
 288       /* The two halves of needle are distinct; no extra memory is
 289          required, and any mismatch results in a maximal shift.  */
 290       period = MAX (suffix, needle_len - suffix) + 1;
 291       j = 0;
 292       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 293         {
 294           /* Scan for matches in right half.  */
 295           i = suffix;
 296           while (i < needle_len && (CANON_ELEMENT (needle[i])
 297                                     == CANON_ELEMENT (haystack[i + j])))
 298             ++i;
 299           if (needle_len <= i)
 300             {
 301               /* Scan for matches in left half.  */
 302               i = suffix - 1;
 303               while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
 304                                        == CANON_ELEMENT (haystack[i + j])))
 305                 --i;
 306               if (i == SIZE_MAX)
 307                 return (RETURN_TYPE) (haystack + j);
 308               j += period;
 309             }
 310           else
 311             j += i - suffix + 1;
 312         }
 313     }
 314   return NULL;
 315 }
 316
 317 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 318    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
 319    method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
 320    Performance is guaranteed to be linear, with an initialization cost
 321    of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
 322
 323    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 324    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
 325    and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
 326    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 327    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
 328    sublinear performance is not possible.  */
 329 static RETURN_TYPE
 330 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 331                      const unsigned char *needle, size_t needle_len)
 332 {
 333   size_t i; /* Index into current byte of NEEDLE.  */
 334   size_t j; /* Index into current window of HAYSTACK.  */
 335   size_t period; /* The period of the right half of needle.  */
 336   size_t suffix; /* The index of the right half of needle.  */
 337   size_t shift_table[1U << CHAR_BIT]; /* See below.  */
 338
 339   /* Factor the needle into two halves, such that the left half is
 340      smaller than the global period, and the right half is
 341      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 342   suffix = critical_factorization (needle, needle_len, &period);
 343
 344   /* Populate shift_table.  For each possible byte value c,
 345      shift_table[c] is the distance from the last occurrence of c to
 346      the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
 347      shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */
 348   for (i = 0; i < 1U << CHAR_BIT; i++)
 349     shift_table[i] = needle_len;
 350   for (i = 0; i < needle_len; i++)
 351     shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
 352
 353   /* Perform the search.  Each iteration compares the right half
 354      first.  */
 355   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 356     {
 357       /* Entire needle is periodic; a mismatch in the left half can
 358          only advance by the period, so use memory to avoid rescanning
 359          known occurrences of the period in the right half.  */
 360       size_t memory = 0;
 361       size_t shift;
 362       j = 0;
 363       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 364         {
 365           /* Check the last byte first; if it does not match, then
 366              shift to the next possible match location.  */
 367           shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
 368           if (0 < shift)
 369             {
 370               if (memory && shift < period)
 371                 {
 372                   /* Since needle is periodic, but the last period has
 373                      a byte out of place, there can be no match until
 374                      after the mismatch.  */
 375                   shift = needle_len - period;
 376                 }
 377               memory = 0;
 378               j += shift;
 379               continue;
 380             }
 381           /* Scan for matches in right half.  The last byte has
 382              already been matched, by virtue of the shift table.  */
 383           i = MAX (suffix, memory);
 384           while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
 385                                         == CANON_ELEMENT (haystack[i + j])))
 386             ++i;
 387           if (needle_len - 1 <= i)
 388             {
 389               /* Scan for matches in left half.  */
 390               i = suffix - 1;
 391               while (memory < i + 1 && (CANON_ELEMENT (needle[i])
 392                                         == CANON_ELEMENT (haystack[i + j])))
 393                 --i;
 394               if (i + 1 < memory + 1)
 395                 return (RETURN_TYPE) (haystack + j);
 396               /* No match, so remember how many repetitions of period
 397                  on the right half were scanned.  */
 398               j += period;
 399               memory = needle_len - period;
 400             }
 401           else
 402             {
 403               j += i - suffix + 1;
 404               memory = 0;
 405             }
 406         }
 407     }
 408   else
 409     {
 410       /* The two halves of needle are distinct; no extra memory is
 411          required, and any mismatch results in a maximal shift.  */
 412       size_t shift;
 413       period = MAX (suffix, needle_len - suffix) + 1;
 414       j = 0;
 415       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 416         {
 417           /* Check the last byte first; if it does not match, then
 418              shift to the next possible match location.  */
 419           shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
 420           if (0 < shift)
 421             {
 422               j += shift;
 423               continue;
 424             }
 425           /* Scan for matches in right half.  The last byte has
 426              already been matched, by virtue of the shift table.  */
 427           i = suffix;
 428           while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
 429                                         == CANON_ELEMENT (haystack[i + j])))
 430             ++i;
 431           if (needle_len - 1 <= i)
 432             {
 433               /* Scan for matches in left half.  */
 434               i = suffix - 1;
 435               while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
 436                                        == CANON_ELEMENT (haystack[i + j])))
 437                 --i;
 438               if (i == SIZE_MAX)
 439                 return (RETURN_TYPE) (haystack + j);
 440               j += period;
 441             }
 442           else
 443             j += i - suffix + 1;
 444         }
 445     }
 446   return NULL;
 447 }
 448
 449 #undef AVAILABLE
 450 #undef CANON_ELEMENT
 451 #undef CMP_FUNC
 452 #undef MAX
 453 #undef RETURN_TYPE