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