string/str-two-way.h

   1 /* Byte-wise substring search, using the Two-Way algorithm.
   2    Copyright (C) 2008-2013 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 /* Check for end-of-line in strstr and strcasestr routines.
  79    We piggy-back matching procedure for detecting EOL where possible,
  80    and use AVAILABLE macro otherwise.  */
  81 #ifndef CHECK_EOL
  82 # define CHECK_EOL (0)
  83 #endif
  84
  85 /* Return NULL if argument is '\0'.  */
  86 #ifndef RET0_IF_0
  87 # define RET0_IF_0(a) /* nothing */
  88 #endif
  89
  90 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
  91    Return the index of the first byte in the right half, and set
  92    *PERIOD to the global period of the right half.
  93
  94    The global period of a string is the smallest index (possibly its
  95    length) at which all remaining bytes in the string are repetitions
  96    of the prefix (the last repetition may be a subset of the prefix).
  97
  98    When NEEDLE is factored into two halves, a local period is the
  99    length of the smallest word that shares a suffix with the left half
 100    and shares a prefix with the right half.  All factorizations of a
 101    non-empty NEEDLE have a local period of at least 1 and no greater
 102    than NEEDLE_LEN.
 103
 104    A critical factorization has the property that the local period
 105    equals the global period.  All strings have at least one critical
 106    factorization with the left half smaller than the global period.
 107
 108    Given an ordered alphabet, a critical factorization can be computed
 109    in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
 110    larger of two ordered maximal suffixes.  The ordered maximal
 111    suffixes are determined by lexicographic comparison of
 112    periodicity.  */
 113 static size_t
 114 critical_factorization (const unsigned char *needle, size_t needle_len,
 115                         size_t *period)
 116 {
 117   /* Index of last byte of left half, or SIZE_MAX.  */
 118   size_t max_suffix, max_suffix_rev;
 119   size_t j; /* Index into NEEDLE for current candidate suffix.  */
 120   size_t k; /* Offset into current period.  */
 121   size_t p; /* Intermediate period.  */
 122   unsigned char a, b; /* Current comparison bytes.  */
 123
 124   /* Invariants:
 125      0 <= j < NEEDLE_LEN - 1
 126      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
 127      min(max_suffix, max_suffix_rev) < global period of NEEDLE
 128      1 <= p <= global period of NEEDLE
 129      p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
 130      1 <= k <= p
 131   */
 132
 133   /* Perform lexicographic search.  */
 134   max_suffix = SIZE_MAX;
 135   j = 0;
 136   k = p = 1;
 137   while (j + k < needle_len)
 138     {
 139       a = CANON_ELEMENT (needle[j + k]);
 140       b = CANON_ELEMENT (needle[max_suffix + k]);
 141       if (a < b)
 142         {
 143           /* Suffix is smaller, period is entire prefix so far.  */
 144           j += k;
 145           k = 1;
 146           p = j - max_suffix;
 147         }
 148       else if (a == b)
 149         {
 150           /* Advance through repetition of the current period.  */
 151           if (k != p)
 152             ++k;
 153           else
 154             {
 155               j += p;
 156               k = 1;
 157             }
 158         }
 159       else /* b < a */
 160         {
 161           /* Suffix is larger, start over from current location.  */
 162           max_suffix = j++;
 163           k = p = 1;
 164         }
 165     }
 166   *period = p;
 167
 168   /* Perform reverse lexicographic search.  */
 169   max_suffix_rev = SIZE_MAX;
 170   j = 0;
 171   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 longer suffix.  Return the first byte of the right
 203      half, rather than the last byte of the left half.  */
 204   if (max_suffix_rev + 1 < max_suffix + 1)
 205     return max_suffix + 1;
 206   *period = p;
 207   return max_suffix_rev + 1;
 208 }
 209
 210 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 211    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
 212    method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
 213    Performance is guaranteed to be linear, with an initialization cost
 214    of 2 * NEEDLE_LEN comparisons.
 215
 216    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 217    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
 218    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 219    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
 220 static RETURN_TYPE
 221 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 222                       const unsigned char *needle, size_t needle_len)
 223 {
 224   size_t i; /* Index into current byte of NEEDLE.  */
 225   size_t j; /* Index into current window of HAYSTACK.  */
 226   size_t period; /* The period of the right half of needle.  */
 227   size_t suffix; /* The index of the right half of needle.  */
 228
 229   /* Factor the needle into two halves, such that the left half is
 230      smaller than the global period, and the right half is
 231      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 232   suffix = critical_factorization (needle, needle_len, &period);
 233
 234   /* Perform the search.  Each iteration compares the right half
 235      first.  */
 236   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 237     {
 238       /* Entire needle is periodic; a mismatch can only advance by the
 239          period, so use memory to avoid rescanning known occurrences
 240          of the period.  */
 241       size_t memory = 0;
 242       j = 0;
 243       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 244         {
 245           const unsigned char *pneedle;
 246           const unsigned char *phaystack;
 247
 248           /* Scan for matches in right half.  */
 249           i = MAX (suffix, memory);
 250           pneedle = &needle[i];
 251           phaystack = &haystack[i + j];
 252           while (i < needle_len && (CANON_ELEMENT (*pneedle++)
 253                                     == CANON_ELEMENT (*phaystack++)))
 254             ++i;
 255           if (needle_len <= i)
 256             {
 257               /* Scan for matches in left half.  */
 258               i = suffix - 1;
 259               pneedle = &needle[i];
 260               phaystack = &haystack[i + j];
 261               while (memory < i + 1 && (CANON_ELEMENT (*pneedle--)
 262                                         == CANON_ELEMENT (*phaystack--)))
 263                 --i;
 264               if (i + 1 < memory + 1)
 265                 return (RETURN_TYPE) (haystack + j);
 266               /* No match, so remember how many repetitions of period
 267                  on the right half were scanned.  */
 268               j += period;
 269               memory = needle_len - period;
 270             }
 271           else
 272             {
 273               j += i - suffix + 1;
 274               memory = 0;
 275             }
 276         }
 277     }
 278   else
 279     {
 280       const unsigned char *phaystack = &haystack[suffix];
 281       /* The comparison always starts from needle[suffix], so cache it
 282          and use an optimized first-character loop.  */
 283       unsigned char needle_suffix = CANON_ELEMENT (needle[suffix]);
 284
 285 #if CHECK_EOL
 286       /* We start matching from the SUFFIX'th element, so make sure we
 287          don't hit '\0' before that.  */
 288       if (haystack_len < suffix + 1
 289           && !AVAILABLE (haystack, haystack_len, 0, suffix + 1))
 290         return NULL;
 291 #endif
 292
 293       /* The two halves of needle are distinct; no extra memory is
 294          required, and any mismatch results in a maximal shift.  */
 295       period = MAX (suffix, needle_len - suffix) + 1;
 296       j = 0;
 297       while (1
 298 #if !CHECK_EOL
 299              && AVAILABLE (haystack, haystack_len, j, needle_len)
 300 #endif
 301              )
 302         {
 303           unsigned char haystack_char;
 304           const unsigned char *pneedle;
 305
 306           /* TODO: The first-character loop can be sped up by adapting
 307              longword-at-a-time implementation of memchr/strchr.  */
 308           if (needle_suffix
 309               != (haystack_char = CANON_ELEMENT (*phaystack++)))
 310             {
 311               RET0_IF_0 (haystack_char);
 312 #if !CHECK_EOL
 313               ++j;
 314 #endif
 315               continue;
 316             }
 317
 318 #if CHECK_EOL
 319           /* Calculate J if it wasn't kept up-to-date in the first-character
 320              loop.  */
 321           j = phaystack - &haystack[suffix] - 1;
 322 #endif
 323
 324           /* Scan for matches in right half.  */
 325           i = suffix + 1;
 326           pneedle = &needle[i];
 327           while (i < needle_len)
 328             {
 329               if (CANON_ELEMENT (*pneedle++)
 330                   != (haystack_char = CANON_ELEMENT (*phaystack++)))
 331                 {
 332                   RET0_IF_0 (haystack_char);
 333                   break;
 334                 }
 335               ++i;
 336             }
 337           if (needle_len <= i)
 338             {
 339               /* Scan for matches in left half.  */
 340               i = suffix - 1;
 341               pneedle = &needle[i];
 342               phaystack = &haystack[i + j];
 343               while (i != SIZE_MAX)
 344                 {
 345                   if (CANON_ELEMENT (*pneedle--)
 346                       != (haystack_char = CANON_ELEMENT (*phaystack--)))
 347                     {
 348                       RET0_IF_0 (haystack_char);
 349                       break;
 350                     }
 351                   --i;
 352                 }
 353               if (i == SIZE_MAX)
 354                 return (RETURN_TYPE) (haystack + j);
 355               j += period;
 356             }
 357           else
 358             j += i - suffix + 1;
 359
 360 #if CHECK_EOL
 361           if (!AVAILABLE (haystack, haystack_len, j, needle_len))
 362             break;
 363 #endif
 364
 365           phaystack = &haystack[suffix + j];
 366         }
 367     }
 368  ret0: __attribute__ ((unused))
 369   return NULL;
 370 }
 371
 372 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 373    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
 374    method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
 375    Performance is guaranteed to be linear, with an initialization cost
 376    of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
 377
 378    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 379    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
 380    and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
 381    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 382    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
 383    sublinear performance is not possible.  */
 384 static RETURN_TYPE
 385 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 386                      const unsigned char *needle, size_t needle_len)
 387 {
 388   size_t i; /* Index into current byte of NEEDLE.  */
 389   size_t j; /* Index into current window of HAYSTACK.  */
 390   size_t period; /* The period of the right half of needle.  */
 391   size_t suffix; /* The index of the right half of needle.  */
 392   size_t shift_table[1U << CHAR_BIT]; /* See below.  */
 393
 394   /* Factor the needle into two halves, such that the left half is
 395      smaller than the global period, and the right half is
 396      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 397   suffix = critical_factorization (needle, needle_len, &period);
 398
 399   /* Populate shift_table.  For each possible byte value c,
 400      shift_table[c] is the distance from the last occurrence of c to
 401      the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
 402      shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */
 403   for (i = 0; i < 1U << CHAR_BIT; i++)
 404     shift_table[i] = needle_len;
 405   for (i = 0; i < needle_len; i++)
 406     shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
 407
 408   /* Perform the search.  Each iteration compares the right half
 409      first.  */
 410   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 411     {
 412       /* Entire needle is periodic; a mismatch can only advance by the
 413          period, so use memory to avoid rescanning known occurrences
 414          of the period.  */
 415       size_t memory = 0;
 416       size_t shift;
 417       j = 0;
 418       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 419         {
 420           const unsigned char *pneedle;
 421           const unsigned char *phaystack;
 422
 423           /* Check the last byte first; if it does not match, then
 424              shift to the next possible match location.  */
 425           shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
 426           if (0 < shift)
 427             {
 428               if (memory && shift < period)
 429                 {
 430                   /* Since needle is periodic, but the last period has
 431                      a byte out of place, there can be no match until
 432                      after the mismatch.  */
 433                   shift = needle_len - period;
 434                 }
 435               memory = 0;
 436               j += shift;
 437               continue;
 438             }
 439           /* Scan for matches in right half.  The last byte has
 440              already been matched, by virtue of the shift table.  */
 441           i = MAX (suffix, memory);
 442           pneedle = &needle[i];
 443           phaystack = &haystack[i + j];
 444           while (i < needle_len - 1 && (CANON_ELEMENT (*pneedle++)
 445                                         == CANON_ELEMENT (*phaystack++)))
 446             ++i;
 447           if (needle_len - 1 <= i)
 448             {
 449               /* Scan for matches in left half.  */
 450               i = suffix - 1;
 451               pneedle = &needle[i];
 452               phaystack = &haystack[i + j];
 453               while (memory < i + 1 && (CANON_ELEMENT (*pneedle--)
 454                                         == CANON_ELEMENT (*phaystack--)))
 455                 --i;
 456               if (i + 1 < memory + 1)
 457                 return (RETURN_TYPE) (haystack + j);
 458               /* No match, so remember how many repetitions of period
 459                  on the right half were scanned.  */
 460               j += period;
 461               memory = needle_len - period;
 462             }
 463           else
 464             {
 465               j += i - suffix + 1;
 466               memory = 0;
 467             }
 468         }
 469     }
 470   else
 471     {
 472       /* The two halves of needle are distinct; no extra memory is
 473          required, and any mismatch results in a maximal shift.  */
 474       size_t shift;
 475       period = MAX (suffix, needle_len - suffix) + 1;
 476       j = 0;
 477       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 478         {
 479           const unsigned char *pneedle;
 480           const unsigned char *phaystack;
 481
 482           /* Check the last byte first; if it does not match, then
 483              shift to the next possible match location.  */
 484           shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
 485           if (0 < shift)
 486             {
 487               j += shift;
 488               continue;
 489             }
 490           /* Scan for matches in right half.  The last byte has
 491              already been matched, by virtue of the shift table.  */
 492           i = suffix;
 493           pneedle = &needle[i];
 494           phaystack = &haystack[i + j];
 495           while (i < needle_len - 1 && (CANON_ELEMENT (*pneedle++)
 496                                         == CANON_ELEMENT (*phaystack++)))
 497             ++i;
 498           if (needle_len - 1 <= i)
 499             {
 500               /* Scan for matches in left half.  */
 501               i = suffix - 1;
 502               pneedle = &needle[i];
 503               phaystack = &haystack[i + j];
 504               while (i != SIZE_MAX && (CANON_ELEMENT (*pneedle--)
 505                                        == CANON_ELEMENT (*phaystack--)))
 506                 --i;
 507               if (i == SIZE_MAX)
 508                 return (RETURN_TYPE) (haystack + j);
 509               j += period;
 510             }
 511           else
 512             j += i - suffix + 1;
 513         }
 514     }
 515   return NULL;
 516 }
 517
 518 #undef AVAILABLE
 519 #undef AVAILABLE1
 520 #undef AVAILABLE2
 521 #undef AVAILABLE1_USES_J
 522 #undef CANON_ELEMENT
 523 #undef CMP_FUNC
 524 #undef RET0_IF_0
 525 #undef RETURN_TYPE