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