string/str-two-way.h

   1 /* Byte-wise substring search, using the Two-Way algorithm.
   2    Copyright (C) 2008, 2010 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, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 /* Before including this file, you need to include <string.h> (and
  22    <config.h> before that, if not part of libc), and define:
  23      RESULT_TYPE             A macro that expands to the return type.
  24      AVAILABLE(h, h_l, j, n_l)
  25                              A macro that returns nonzero if there are
  26                              at least N_L bytes left starting at H[J].
  27                              H is 'unsigned char *', H_L, J, and N_L
  28                              are 'size_t'; H_L is an lvalue.  For
  29                              NUL-terminated searches, H_L can be
  30                              modified each iteration to avoid having
  31                              to compute the end of H up front.
  32
  33   For case-insensitivity, you may optionally define:
  34      CMP_FUNC(p1, p2, l)     A macro that returns 0 iff the first L
  35                              characters of P1 and P2 are equal.
  36      CANON_ELEMENT(c)        A macro that canonicalizes an element right after
  37                              it has been fetched from one of the two strings.
  38                              The argument is an 'unsigned char'; the result
  39                              must be an 'unsigned char' as well.
  40
  41   This file undefines the macros documented above, and defines
  42   LONG_NEEDLE_THRESHOLD.
  43 */
  44
  45 #include <limits.h>
  46 #include <stdint.h>
  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 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
 100    Given an ordered alphabet, a critical factorization can be computed
 101    in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
 102    larger of two ordered maximal suffixes.  The ordered maximal
 103    suffixes are determined by lexicographic comparison of
 104    periodicity.  */
 105 static size_t
 106 critical_factorization (const unsigned char *needle, size_t needle_len,
 107                         size_t *period)
 108 {
 109   /* Index of last byte of left half, or SIZE_MAX.  */
 110   size_t max_suffix, max_suffix_rev;
 111   size_t j; /* Index into NEEDLE for current candidate suffix.  */
 112   size_t k; /* Offset into current period.  */
 113   size_t p; /* Intermediate period.  */
 114   unsigned char a, b; /* Current comparison bytes.  */
 115
 116   /* Invariants:
 117      0 <= j < NEEDLE_LEN - 1
 118      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
 119      min(max_suffix, max_suffix_rev) < global period of NEEDLE
 120      1 <= p <= global period of NEEDLE
 121      p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
 122      1 <= k <= p
 123   */
 124
 125   /* Perform lexicographic search.  */
 126   max_suffix = SIZE_MAX;
 127   j = 0;
 128   k = p = 1;
 129   while (j + k < needle_len)
 130     {
 131       a = CANON_ELEMENT (needle[j + k]);
 132       b = CANON_ELEMENT (needle[max_suffix + k]);
 133       if (a < b)
 134         {
 135           /* Suffix is smaller, period is entire prefix so far.  */
 136           j += k;
 137           k = 1;
 138           p = j - max_suffix;
 139         }
 140       else if (a == b)
 141         {
 142           /* Advance through repetition of the current period.  */
 143           if (k != p)
 144             ++k;
 145           else
 146             {
 147               j += p;
 148               k = 1;
 149             }
 150         }
 151       else /* b < a */
 152         {
 153           /* Suffix is larger, start over from current location.  */
 154           max_suffix = j++;
 155           k = p = 1;
 156         }
 157     }
 158   *period = p;
 159
 160   /* Perform reverse lexicographic search.  */
 161   max_suffix_rev = SIZE_MAX;
 162   j = 0;
 163   k = p = 1;
 164   while (j + k < needle_len)
 165     {
 166       a = CANON_ELEMENT (needle[j + k]);
 167       b = CANON_ELEMENT (needle[max_suffix_rev + k]);
 168       if (b < a)
 169         {
 170           /* Suffix is smaller, period is entire prefix so far.  */
 171           j += k;
 172           k = 1;
 173           p = j - max_suffix_rev;
 174         }
 175       else if (a == b)
 176         {
 177           /* Advance through repetition of the current period.  */
 178           if (k != p)
 179             ++k;
 180           else
 181             {
 182               j += p;
 183               k = 1;
 184             }
 185         }
 186       else /* a < b */
 187         {
 188           /* Suffix is larger, start over from current location.  */
 189           max_suffix_rev = j++;
 190           k = p = 1;
 191         }
 192     }
 193
 194   /* Choose the longer suffix.  Return the first byte of the right
 195      half, rather than the last byte of the left half.  */
 196   if (max_suffix_rev + 1 < max_suffix + 1)
 197     return max_suffix + 1;
 198   *period = p;
 199   return max_suffix_rev + 1;
 200 }
 201
 202 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 203    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
 204    method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
 205    Performance is guaranteed to be linear, with an initialization cost
 206    of 2 * NEEDLE_LEN comparisons.
 207
 208    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 209    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
 210    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 211    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
 212 static RETURN_TYPE
 213 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 214                       const unsigned char *needle, size_t needle_len)
 215 {
 216   size_t i; /* Index into current byte of NEEDLE.  */
 217   size_t j; /* Index into current window of HAYSTACK.  */
 218   size_t period; /* The period of the right half of needle.  */
 219   size_t suffix; /* The index of the right half of needle.  */
 220
 221   /* Factor the needle into two halves, such that the left half is
 222      smaller than the global period, and the right half is
 223      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 224   suffix = critical_factorization (needle, needle_len, &period);
 225
 226   /* Perform the search.  Each iteration compares the right half
 227      first.  */
 228   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 229     {
 230       /* Entire needle is periodic; a mismatch can only advance by the
 231          period, so use memory to avoid rescanning known occurrences
 232          of the period.  */
 233       size_t memory = 0;
 234       j = 0;
 235       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 236         {
 237           /* Scan for matches in right half.  */
 238           i = MAX (suffix, memory);
 239           while (i < needle_len && (CANON_ELEMENT (needle[i])
 240                                     == CANON_ELEMENT (haystack[i + j])))
 241             ++i;
 242           if (needle_len <= i)
 243             {
 244               /* Scan for matches in left half.  */
 245               i = suffix - 1;
 246               while (memory < i + 1 && (CANON_ELEMENT (needle[i])
 247                                         == CANON_ELEMENT (haystack[i + j])))
 248                 --i;
 249               if (i + 1 < memory + 1)
 250                 return (RETURN_TYPE) (haystack + j);
 251               /* No match, so remember how many repetitions of period
 252                  on the right half were scanned.  */
 253               j += period;
 254               memory = needle_len - period;
 255             }
 256           else
 257             {
 258               j += i - suffix + 1;
 259               memory = 0;
 260             }
 261         }
 262     }
 263   else
 264     {
 265       /* The two halves of needle are distinct; no extra memory is
 266          required, and any mismatch results in a maximal shift.  */
 267       period = MAX (suffix, needle_len - suffix) + 1;
 268       j = 0;
 269       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 270         {
 271           /* Scan for matches in right half.  */
 272           i = suffix;
 273           while (i < needle_len && (CANON_ELEMENT (needle[i])
 274                                     == CANON_ELEMENT (haystack[i + j])))
 275             ++i;
 276           if (needle_len <= i)
 277             {
 278               /* Scan for matches in left half.  */
 279               i = suffix - 1;
 280               while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
 281                                        == CANON_ELEMENT (haystack[i + j])))
 282                 --i;
 283               if (i == SIZE_MAX)
 284                 return (RETURN_TYPE) (haystack + j);
 285               j += period;
 286             }
 287           else
 288             j += i - suffix + 1;
 289         }
 290     }
 291   return NULL;
 292 }
 293
 294 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 295    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
 296    method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
 297    Performance is guaranteed to be linear, with an initialization cost
 298    of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
 299
 300    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 301    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
 302    and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
 303    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 304    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
 305    sublinear performance is not possible.  */
 306 static RETURN_TYPE
 307 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 308                      const unsigned char *needle, size_t needle_len)
 309 {
 310   size_t i; /* Index into current byte of NEEDLE.  */
 311   size_t j; /* Index into current window of HAYSTACK.  */
 312   size_t period; /* The period of the right half of needle.  */
 313   size_t suffix; /* The index of the right half of needle.  */
 314   size_t shift_table[1U << CHAR_BIT]; /* See below.  */
 315
 316   /* Factor the needle into two halves, such that the left half is
 317      smaller than the global period, and the right half is
 318      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 319   suffix = critical_factorization (needle, needle_len, &period);
 320
 321   /* Populate shift_table.  For each possible byte value c,
 322      shift_table[c] is the distance from the last occurrence of c to
 323      the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
 324      shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */
 325   for (i = 0; i < 1U << CHAR_BIT; i++)
 326     shift_table[i] = needle_len;
 327   for (i = 0; i < needle_len; i++)
 328     shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
 329
 330   /* Perform the search.  Each iteration compares the right half
 331      first.  */
 332   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 333     {
 334       /* Entire needle is periodic; a mismatch can only advance by the
 335          period, so use memory to avoid rescanning known occurrences
 336          of the period.  */
 337       size_t memory = 0;
 338       size_t shift;
 339       j = 0;
 340       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 341         {
 342           /* Check the last byte first; if it does not match, then
 343              shift to the next possible match location.  */
 344           shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
 345           if (0 < shift)
 346             {
 347               if (memory && shift < period)
 348                 {
 349                   /* Since needle is periodic, but the last period has
 350                      a byte out of place, there can be no match until
 351                      after the mismatch.  */
 352                   shift = needle_len - period;
 353                 }
 354               memory = 0;
 355               j += shift;
 356               continue;
 357             }
 358           /* Scan for matches in right half.  The last byte has
 359              already been matched, by virtue of the shift table.  */
 360           i = MAX (suffix, memory);
 361           while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
 362                                         == CANON_ELEMENT (haystack[i + j])))
 363             ++i;
 364           if (needle_len - 1 <= i)
 365             {
 366               /* Scan for matches in left half.  */
 367               i = suffix - 1;
 368               while (memory < i + 1 && (CANON_ELEMENT (needle[i])
 369                                         == CANON_ELEMENT (haystack[i + j])))
 370                 --i;
 371               if (i + 1 < memory + 1)
 372                 return (RETURN_TYPE) (haystack + j);
 373               /* No match, so remember how many repetitions of period
 374                  on the right half were scanned.  */
 375               j += period;
 376               memory = needle_len - period;
 377             }
 378           else
 379             {
 380               j += i - suffix + 1;
 381               memory = 0;
 382             }
 383         }
 384     }
 385   else
 386     {
 387       /* The two halves of needle are distinct; no extra memory is
 388          required, and any mismatch results in a maximal shift.  */
 389       size_t shift;
 390       period = MAX (suffix, needle_len - suffix) + 1;
 391       j = 0;
 392       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 393         {
 394           /* Check the last byte first; if it does not match, then
 395              shift to the next possible match location.  */
 396           shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
 397           if (0 < shift)
 398             {
 399               j += shift;
 400               continue;
 401             }
 402           /* Scan for matches in right half.  The last byte has
 403              already been matched, by virtue of the shift table.  */
 404           i = suffix;
 405           while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
 406                                         == CANON_ELEMENT (haystack[i + j])))
 407             ++i;
 408           if (needle_len - 1 <= i)
 409             {
 410               /* Scan for matches in left half.  */
 411               i = suffix - 1;
 412               while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
 413                                        == CANON_ELEMENT (haystack[i + j])))
 414                 --i;
 415               if (i == SIZE_MAX)
 416                 return (RETURN_TYPE) (haystack + j);
 417               j += period;
 418             }
 419           else
 420             j += i - suffix + 1;
 421         }
 422     }
 423   return NULL;
 424 }
 425
 426 #undef AVAILABLE
 427 #undef CANON_ELEMENT
 428 #undef CMP_FUNC
 429 #undef RETURN_TYPE