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