wcsmbs/wcs-two-way.h

   1 /* Wide character substring search, using the Two-Way algorithm.
   2    Copyright (C) 2008-2024 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 /* Before including this file, you need to include <string.h> (and
  20    <config.h> before that, if not part of libc), and define:
  21      AVAILABLE(h, h_l, j, n_l)
  22                              A macro that returns nonzero if there are
  23                              at least N_L characters left starting at H[J].
  24                              H is 'wchar_t *', H_L, J, and N_L are 'size_t';
  25                              H_L is an lvalue.  For NUL-terminated searches,
  26                              H_L can be modified each iteration to avoid
  27                              having to compute the end of H up front.
  28
  29   For case-insensitivity, you may optionally define:
  30      CMP_FUNC(p1, p2, l)     A macro that returns 0 iff the first L
  31                              characters of P1 and P2 are equal.
  32      CANON_ELEMENT(c)        A macro that canonicalizes an element right after
  33                              it has been fetched from one of the two strings.
  34                              The argument is an 'wchar_t'; the result must
  35                              be an 'wchar_t' as well.
  36 */
  37
  38 #include <limits.h>
  39 #include <stdint.h>
  40 #include <sys/param.h>                  /* Defines MAX.  */
  41
  42 /* We use the Two-Way string matching algorithm, which guarantees
  43    linear complexity with constant space.
  44
  45    See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
  46    and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
  47 */
  48
  49 #ifndef CANON_ELEMENT
  50 # define CANON_ELEMENT(c) c
  51 #endif
  52 #ifndef CMP_FUNC
  53 # define CMP_FUNC __wmemcmp
  54 #endif
  55
  56 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
  57    Return the index of the first character in the right half, and set
  58    *PERIOD to the global period of the right half.
  59
  60    The global period of a string is the smallest index (possibly its
  61    length) at which all remaining bytes in the string are repetitions
  62    of the prefix (the last repetition may be a subset of the prefix).
  63
  64    When NEEDLE is factored into two halves, a local period is the
  65    length of the smallest word that shares a suffix with the left half
  66    and shares a prefix with the right half.  All factorizations of a
  67    non-empty NEEDLE have a local period of at least 1 and no greater
  68    than NEEDLE_LEN.
  69
  70    A critical factorization has the property that the local period
  71    equals the global period.  All strings have at least one critical
  72    factorization with the left half smaller than the global period.
  73
  74    Given an ordered alphabet, a critical factorization can be computed
  75    in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
  76    larger of two ordered maximal suffixes.  The ordered maximal
  77    suffixes are determined by lexicographic comparison of
  78    periodicity.  */
  79 static size_t
  80 critical_factorization (const wchar_t *needle, size_t needle_len,
  81                         size_t *period)
  82 {
  83   /* Index of last character of left half, or SIZE_MAX.  */
  84   size_t max_suffix, max_suffix_rev;
  85   size_t j; /* Index into NEEDLE for current candidate suffix.  */
  86   size_t k; /* Offset into current period.  */
  87   size_t p; /* Intermediate period.  */
  88   wchar_t a, b; /* Current comparison bytes.  */
  89
  90   /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
  91      out 0-length needles.  */
  92   if (needle_len < 3)
  93     {
  94       *period = 1;
  95       return needle_len - 1;
  96     }
  97
  98   /* Invariants:
  99      0 <= j < NEEDLE_LEN - 1
 100      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
 101      min(max_suffix, max_suffix_rev) < global period of NEEDLE
 102      1 <= p <= global period of NEEDLE
 103      p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
 104      1 <= k <= p
 105   */
 106
 107   /* Perform lexicographic search.  */
 108   max_suffix = SIZE_MAX;
 109   j = 0;
 110   k = p = 1;
 111   while (j + k < needle_len)
 112     {
 113       a = CANON_ELEMENT (needle[j + k]);
 114       b = CANON_ELEMENT (needle[max_suffix + k]);
 115       if (a < b)
 116         {
 117           /* Suffix is smaller, period is entire prefix so far.  */
 118           j += k;
 119           k = 1;
 120           p = j - max_suffix;
 121         }
 122       else if (a == b)
 123         {
 124           /* Advance through repetition of the current period.  */
 125           if (k != p)
 126             ++k;
 127           else
 128             {
 129               j += p;
 130               k = 1;
 131             }
 132         }
 133       else /* b < a */
 134         {
 135           /* Suffix is larger, start over from current location.  */
 136           max_suffix = j++;
 137           k = p = 1;
 138         }
 139     }
 140   *period = p;
 141
 142   /* Perform reverse lexicographic search.  */
 143   max_suffix_rev = SIZE_MAX;
 144   j = 0;
 145   k = p = 1;
 146   while (j + k < needle_len)
 147     {
 148       a = CANON_ELEMENT (needle[j + k]);
 149       b = CANON_ELEMENT (needle[max_suffix_rev + k]);
 150       if (b < a)
 151         {
 152           /* Suffix is smaller, period is entire prefix so far.  */
 153           j += k;
 154           k = 1;
 155           p = j - max_suffix_rev;
 156         }
 157       else if (a == b)
 158         {
 159           /* Advance through repetition of the current period.  */
 160           if (k != p)
 161             ++k;
 162           else
 163             {
 164               j += p;
 165               k = 1;
 166             }
 167         }
 168       else /* a < b */
 169         {
 170           /* Suffix is larger, start over from current location.  */
 171           max_suffix_rev = j++;
 172           k = p = 1;
 173         }
 174     }
 175
 176   /* Choose the shorter suffix.  Return the first character of the right
 177      half, rather than the last character of the left half.  */
 178   if (max_suffix_rev + 1 < max_suffix + 1)
 179     return max_suffix + 1;
 180   *period = p;
 181   return max_suffix_rev + 1;
 182 }
 183
 184 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
 185    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.
 186
 187    If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
 188    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
 189    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
 190    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
 191 static inline wchar_t *
 192 two_way_short_needle (const wchar_t *haystack, size_t haystack_len,
 193                       const wchar_t *needle, size_t needle_len)
 194 {
 195   size_t i; /* Index into current character of NEEDLE.  */
 196   size_t j; /* Index into current window of HAYSTACK.  */
 197   size_t period; /* The period of the right half of needle.  */
 198   size_t suffix; /* The index of the right half of needle.  */
 199
 200   /* Factor the needle into two halves, such that the left half is
 201      smaller than the global period, and the right half is
 202      periodic (with a period as large as NEEDLE_LEN - suffix).  */
 203   suffix = critical_factorization (needle, needle_len, &period);
 204
 205   /* Perform the search.  Each iteration compares the right half
 206      first.  */
 207   if (CMP_FUNC (needle, needle + period, suffix) == 0)
 208     {
 209       /* Entire needle is periodic; a mismatch can only advance by the
 210          period, so use memory to avoid rescanning known occurrences
 211          of the period.  */
 212       size_t memory = 0;
 213       j = 0;
 214       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 215         {
 216           const wchar_t *pneedle;
 217           const wchar_t *phaystack;
 218
 219           /* Scan for matches in right half.  */
 220           i = MAX (suffix, memory);
 221           pneedle = &needle[i];
 222           phaystack = &haystack[i + j];
 223           while (i < needle_len && (CANON_ELEMENT (*pneedle++)
 224                                     == CANON_ELEMENT (*phaystack++)))
 225             ++i;
 226           if (needle_len <= i)
 227             {
 228               /* Scan for matches in left half.  */
 229               i = suffix - 1;
 230               pneedle = &needle[i];
 231               phaystack = &haystack[i + j];
 232               while (memory < i + 1 && (CANON_ELEMENT (*pneedle--)
 233                                         == CANON_ELEMENT (*phaystack--)))
 234                 --i;
 235               if (i + 1 < memory + 1)
 236                 return (wchar_t *) (haystack + j);
 237               /* No match, so remember how many repetitions of period
 238                  on the right half were scanned.  */
 239               j += period;
 240               memory = needle_len - period;
 241             }
 242           else
 243             {
 244               j += i - suffix + 1;
 245               memory = 0;
 246             }
 247         }
 248     }
 249   else
 250     {
 251       const wchar_t *phaystack;
 252       /* The comparison always starts from needle[suffix], so cache it
 253          and use an optimized first-character loop.  */
 254       wchar_t needle_suffix = CANON_ELEMENT (needle[suffix]);
 255
 256       /* The two halves of needle are distinct; no extra memory is
 257          required, and any mismatch results in a maximal shift.  */
 258       period = MAX (suffix, needle_len - suffix) + 1;
 259       j = 0;
 260       while (AVAILABLE (haystack, haystack_len, j, needle_len))
 261         {
 262           wchar_t haystack_char;
 263           const wchar_t *pneedle;
 264
 265           phaystack = &haystack[suffix + j];
 266
 267           while (needle_suffix
 268               != (haystack_char = CANON_ELEMENT (*phaystack++)))
 269             {
 270               ++j;
 271               if (!AVAILABLE (haystack, haystack_len, j, needle_len))
 272                 goto ret0;
 273             }
 274
 275           /* Scan for matches in right half.  */
 276           i = suffix + 1;
 277           pneedle = &needle[i];
 278           while (i < needle_len)
 279             {
 280               if (CANON_ELEMENT (*pneedle++)
 281                   != (haystack_char = CANON_ELEMENT (*phaystack++)))
 282                 break;
 283               ++i;
 284             }
 285           if (needle_len <= i)
 286             {
 287               /* Scan for matches in left half.  */
 288               i = suffix - 1;
 289               pneedle = &needle[i];
 290               phaystack = &haystack[i + j];
 291               while (i != SIZE_MAX)
 292                 {
 293                   if (CANON_ELEMENT (*pneedle--)
 294                       != (haystack_char = CANON_ELEMENT (*phaystack--)))
 295                     break;
 296                   --i;
 297                 }
 298               if (i == SIZE_MAX)
 299                 return (wchar_t *) (haystack + j);
 300               j += period;
 301             }
 302           else
 303             j += i - suffix + 1;
 304         }
 305     }
 306 ret0: __attribute__ ((unused))
 307   return NULL;
 308 }
 309
 310 #undef AVAILABLE
 311 #undef CANON_ELEMENT
 312 #undef CMP_FUNC