lib/str-two-way.h

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