1 /* Searching in a string. -*- coding: utf-8 -*-
2 Copyright (C) 2005-2023 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2005.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation, either version 3 of the
8 License, or (at your option) any later version.
9
10 This file 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
13 GNU Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 /* Specification. */
21 #include <string.h>
22
23 #include <stddef.h> /* for NULL, in case a nonstandard string.h lacks it */
24 #include <stdlib.h>
25
26 #include "malloca.h"
27
28 #if GNULIB_MCEL_PREFER
29 # include "mcel.h"
30 typedef mcel_t mbchar_t;
31 static bool mb_equal (mcel_t a, mcel_t b) { return mcel_cmp (a, b) == 0; }
32 #else
33 # include "mbuiter.h"
34 #endif
35
36 /* Knuth-Morris-Pratt algorithm. */
37 #define UNIT unsigned char
38 #define CANON_ELEMENT(c) c
39 #include "str-kmp.h"
40
41 /* Knuth-Morris-Pratt algorithm.
42 See https://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
43 Return a boolean indicating success:
44 Return true and set *RESULTP if the search was completed.
45 Return false if it was aborted because not enough memory was available. */
46 static bool
47 knuth_morris_pratt_multibyte (const char *haystack, const char *needle,
48 const char **resultp)
49 {
50 size_t m = mbslen (needle);
51 mbchar_t *needle_mbchars;
52 size_t extra_align = (alignof (mbchar_t) < alignof (size_t)
53 ? alignof (size_t) - alignof (mbchar_t)
54 : 0);
55
56 /* Allocate room for needle_mbchars and the table. */
57 void *memory = nmalloca (m + !!extra_align,
58 sizeof (mbchar_t) + sizeof (size_t));
59 void *table_memory;
60 if (memory == NULL)
61 return false;
62 needle_mbchars = memory;
63 table_memory = needle_mbchars + m;
64 char *aligned = table_memory;
65 aligned += extra_align;
66 aligned -= (uintptr_t) aligned % alignof (size_t);
67 size_t *table = table_memory = aligned;
68
69 /* Fill needle_mbchars. */
70 #if GNULIB_MCEL_PREFER
71 for (size_t j = 0; *needle; needle += needle_mbchars[j++].len)
72 needle_mbchars[j] = mcel_scanz (needle);
73 #else
74 {
75 mbui_iterator_t iter;
76 size_t j;
77
78 j = 0;
79 for (mbui_init (iter, needle); mbui_avail (iter); mbui_advance (iter), j++)
80 mb_copy (&needle_mbchars[j], &mbui_cur (iter));
81 }
82 #endif
83
84 /* Fill the table.
85 For 0 < i < m:
86 0 < table[i] <= i is defined such that
87 forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
88 and table[i] is as large as possible with this property.
89 This implies:
90 1) For 0 < i < m:
91 If table[i] < i,
92 needle[table[i]..i-1] = needle[0..i-1-table[i]].
93 2) For 0 < i < m:
94 rhaystack[0..i-1] == needle[0..i-1]
95 and exists h, i <= h < m: rhaystack[h] != needle[h]
96 implies
97 forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
98 table[0] remains uninitialized. */
99 {
100 size_t i, j;
101
102 /* i = 1: Nothing to verify for x = 0. */
103 table[1] = 1;
104 j = 0;
105
106 for (i = 2; i < m; i++)
107 {
108 /* Here: j = i-1 - table[i-1].
109 The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
110 for x < table[i-1], by induction.
111 Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1]. */
112 mbchar_t *b = &needle_mbchars[i - 1];
113
114 for (;;)
115 {
116 /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
117 is known to hold for x < i-1-j.
118 Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1]. */
119 if (mb_equal (*b, needle_mbchars[j]))
120 {
121 /* Set table[i] := i-1-j. */
122 table[i] = i - ++j;
123 break;
124 }
125 /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
126 for x = i-1-j, because
127 needle[i-1] != needle[j] = needle[i-1-x]. */
128 if (j == 0)
129 {
130 /* The inequality holds for all possible x. */
131 table[i] = i;
132 break;
133 }
134 /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
135 for i-1-j < x < i-1-j+table[j], because for these x:
136 needle[x..i-2]
137 = needle[x-(i-1-j)..j-1]
138 != needle[0..j-1-(x-(i-1-j))] (by definition of table[j])
139 = needle[0..i-2-x],
140 hence needle[x..i-1] != needle[0..i-1-x].
141 Furthermore
142 needle[i-1-j+table[j]..i-2]
143 = needle[table[j]..j-1]
144 = needle[0..j-1-table[j]] (by definition of table[j]). */
145 j = j - table[j];
146 }
147 /* Here: j = i - table[i]. */
148 }
149 }
150
151 /* Search, using the table to accelerate the processing. */
152 {
153 #if GNULIB_MCEL_PREFER
154 size_t j;
155 char const *rhaystack = haystack;
156 char const *phaystack = haystack;
157
158 j = 0;
159 /* Invariant: phaystack = rhaystack + j. */
160 for (;;)
161 {
162 if (!*phaystack)
163 {
164 rhaystack = NULL;
165 break;
166 }
167 mcel_t g = mcel_scanz (phaystack);
168 if (mcel_cmp (needle_mbchars[j], g) == 0)
169 {
170 j++;
171 /* Exit loop successfully if the entire needle has been found. */
172 if (j == m)
173 break;
174 phaystack += g.len;
175 }
176 else if (j == 0)
177 {
178 /* Found a mismatch at needle[0] already. */
179 rhaystack += mcel_scanz (rhaystack).len;
180 phaystack += g.len;
181 }
182 else
183 {
184 /* Found a match of needle[0..j-1], mismatch at needle[j]. */
185 size_t count = table[j];
186 j -= count;
187 for (; count != 0; count--)
188 rhaystack += mcel_scanz (rhaystack).len;
189 }
190 }
191 *resultp = rhaystack;
192 #else
193 size_t j;
194 mbui_iterator_t rhaystack;
195 mbui_iterator_t phaystack;
196
197 *resultp = NULL;
198 j = 0;
199 mbui_init (rhaystack, haystack);
200 mbui_init (phaystack, haystack);
201 /* Invariant: phaystack = rhaystack + j. */
202 while (mbui_avail (phaystack))
203 if (mb_equal (needle_mbchars[j], mbui_cur (phaystack)))
204 {
205 j++;
206 mbui_advance (phaystack);
207 if (j == m)
208 {
209 /* The entire needle has been found. */
210 *resultp = mbui_cur_ptr (rhaystack);
211 break;
212 }
213 }
214 else if (j > 0)
215 {
216 /* Found a match of needle[0..j-1], mismatch at needle[j]. */
217 size_t count = table[j];
218 j -= count;
219 for (; count > 0; count--)
220 {
221 if (!mbui_avail (rhaystack))
222 abort ();
223 mbui_advance (rhaystack);
224 }
225 }
226 else
227 {
228 /* Found a mismatch at needle[0] already. */
229 if (!mbui_avail (rhaystack))
230 abort ();
231 mbui_advance (rhaystack);
232 mbui_advance (phaystack);
233 }
234 #endif
235 }
236
237 freea (memory);
238 return true;
239 }
240
241 /* Find the first occurrence of the character string NEEDLE in the character
242 string HAYSTACK. Return NULL if NEEDLE is not found in HAYSTACK. */
243 char *
244 mbsstr (const char *haystack, const char *needle)
245 {
246 /* Be careful not to look at the entire extent of haystack or needle
247 until needed. This is useful because of these two cases:
248 - haystack may be very long, and a match of needle found early,
249 - needle may be very long, and not even a short initial segment of
250 needle may be found in haystack. */
251 if (MB_CUR_MAX > 1)
252 {
253 #if GNULIB_MCEL_PREFER
254 if (!*needle)
255 return (char *) haystack;
256
257 mcel_t ng = mcel_scanz (needle);
258
259 /* Minimizing the worst-case complexity:
260 Let n = mbslen(haystack), m = mbslen(needle).
261 The naïve algorithm is O(n*m) worst-case.
262 The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
263 memory allocation.
264 To achieve linear complexity and yet amortize the cost of the
265 memory allocation, we activate the Knuth-Morris-Pratt algorithm
266 only once the naïve algorithm has already run for some time; more
267 precisely, when
268 - the outer loop count is >= 10,
269 - the average number of comparisons per outer loop is >= 5,
270 - the total number of comparisons is >= m.
271 But we try it only once. If the memory allocation attempt failed,
272 we don't retry it. */
273 bool try_kmp = true;
274 size_t outer_loop_count = 0;
275 size_t comparison_count = 0;
276
277 /* Last comparison count, and needle + last_ccount. */
278 size_t last_ccount = 0;
279 char const *iter_needle_last_ccount = needle;
280
281 char const *iter_haystack = haystack;
282
283 for (mcel_t hg; *iter_haystack; iter_haystack += hg.len)
284 {
285 /* See whether it's advisable to use an asymptotically faster
286 algorithm. */
287 if (try_kmp
288 && outer_loop_count >= 10
289 && comparison_count >= 5 * outer_loop_count)
290 {
291 /* See if needle + comparison_count now reaches the end of
292 needle. */
293 size_t count = comparison_count - last_ccount;
294 for (;
295 count > 0 && *iter_needle_last_ccount;
296 count--)
297 iter_needle_last_ccount
298 += mcel_scanz (iter_needle_last_ccount).len;
299 last_ccount = comparison_count;
300 if (!*iter_needle_last_ccount)
301 {
302 char const *result;
303 if (knuth_morris_pratt_multibyte (haystack, needle,
304 &result))
305 return (char *) result;
306 try_kmp = false;
307 }
308 }
309
310 outer_loop_count++;
311 comparison_count++;
312 hg = mcel_scanz (iter_haystack);
313 if (mcel_cmp (hg, ng) == 0)
314 /* The first character matches. */
315 {
316 char const *rhaystack = iter_haystack + hg.len;
317 char const *rneedle = needle + ng.len;
318 mcel_t rhg, rng;
319 do
320 {
321 if (!*rneedle)
322 return (char *) iter_haystack;
323 if (!*rhaystack)
324 return NULL;
325 rhg = mcel_scanz (rhaystack); rhaystack += rhg.len;
326 rng = mcel_scanz (rneedle); rneedle += rng.len;
327 comparison_count++;
328 }
329 while (mcel_cmp (rhg, rng) == 0);
330 }
331 }
332
333 return NULL;
334 #else
335 mbui_iterator_t iter_needle;
336
337 mbui_init (iter_needle, needle);
338 if (mbui_avail (iter_needle))
339 {
340 /* Minimizing the worst-case complexity:
341 Let n = mbslen(haystack), m = mbslen(needle).
342 The naïve algorithm is O(n*m) worst-case.
343 The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
344 memory allocation.
345 To achieve linear complexity and yet amortize the cost of the
346 memory allocation, we activate the Knuth-Morris-Pratt algorithm
347 only once the naïve algorithm has already run for some time; more
348 precisely, when
349 - the outer loop count is >= 10,
350 - the average number of comparisons per outer loop is >= 5,
351 - the total number of comparisons is >= m.
352 But we try it only once. If the memory allocation attempt failed,
353 we don't retry it. */
354 bool try_kmp = true;
355 size_t outer_loop_count = 0;
356 size_t comparison_count = 0;
357 size_t last_ccount = 0; /* last comparison count */
358 mbui_iterator_t iter_needle_last_ccount; /* = needle + last_ccount */
359
360 mbui_iterator_t iter_haystack;
361
362 mbui_init (iter_needle_last_ccount, needle);
363 mbui_init (iter_haystack, haystack);
364 for (;; mbui_advance (iter_haystack))
365 {
366 if (!mbui_avail (iter_haystack))
367 /* No match. */
368 return NULL;
369
370 /* See whether it's advisable to use an asymptotically faster
371 algorithm. */
372 if (try_kmp
373 && outer_loop_count >= 10
374 && comparison_count >= 5 * outer_loop_count)
375 {
376 /* See if needle + comparison_count now reaches the end of
377 needle. */
378 size_t count = comparison_count - last_ccount;
379 for (;
380 count > 0 && mbui_avail (iter_needle_last_ccount);
381 count--)
382 mbui_advance (iter_needle_last_ccount);
383 last_ccount = comparison_count;
384 if (!mbui_avail (iter_needle_last_ccount))
385 {
386 /* Try the Knuth-Morris-Pratt algorithm. */
387 const char *result;
388 bool success =
389 knuth_morris_pratt_multibyte (haystack, needle,
390 &result);
391 if (success)
392 return (char *) result;
393 try_kmp = false;
394 }
395 }
396
397 outer_loop_count++;
398 comparison_count++;
399 if (mb_equal (mbui_cur (iter_haystack), mbui_cur (iter_needle)))
400 /* The first character matches. */
401 {
402 mbui_iterator_t rhaystack;
403 mbui_iterator_t rneedle;
404
405 memcpy (&rhaystack, &iter_haystack, sizeof (mbui_iterator_t));
406 mbui_advance (rhaystack);
407
408 mbui_init (rneedle, needle);
409 if (!mbui_avail (rneedle))
410 abort ();
411 mbui_advance (rneedle);
412
413 for (;; mbui_advance (rhaystack), mbui_advance (rneedle))
414 {
415 if (!mbui_avail (rneedle))
416 /* Found a match. */
417 return (char *) mbui_cur_ptr (iter_haystack);
418 if (!mbui_avail (rhaystack))
419 /* No match. */
420 return NULL;
421 comparison_count++;
422 if (!mb_equal (mbui_cur (rhaystack), mbui_cur (rneedle)))
423 /* Nothing in this round. */
424 break;
425 }
426 }
427 }
428 }
429 else
430 return (char *) haystack;
431 #endif
432 }
433 else
434 {
435 if (*needle != '\0')
436 {
437 /* Minimizing the worst-case complexity:
438 Let n = strlen(haystack), m = strlen(needle).
439 The naïve algorithm is O(n*m) worst-case.
440 The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
441 memory allocation.
442 To achieve linear complexity and yet amortize the cost of the
443 memory allocation, we activate the Knuth-Morris-Pratt algorithm
444 only once the naïve algorithm has already run for some time; more
445 precisely, when
446 - the outer loop count is >= 10,
447 - the average number of comparisons per outer loop is >= 5,
448 - the total number of comparisons is >= m.
449 But we try it only once. If the memory allocation attempt failed,
450 we don't retry it. */
451 bool try_kmp = true;
452 size_t outer_loop_count = 0;
453 size_t comparison_count = 0;
454 size_t last_ccount = 0; /* last comparison count */
455 const char *needle_last_ccount = needle; /* = needle + last_ccount */
456
457 /* Speed up the following searches of needle by caching its first
458 character. */
459 char b = *needle++;
460
461 for (;; haystack++)
462 {
463 if (*haystack == '\0')
464 /* No match. */
465 return NULL;
466
467 /* See whether it's advisable to use an asymptotically faster
468 algorithm. */
469 if (try_kmp
470 && outer_loop_count >= 10
471 && comparison_count >= 5 * outer_loop_count)
472 {
473 /* See if needle + comparison_count now reaches the end of
474 needle. */
475 if (needle_last_ccount != NULL)
476 {
477 needle_last_ccount +=
478 strnlen (needle_last_ccount,
479 comparison_count - last_ccount);
480 if (*needle_last_ccount == '\0')
481 needle_last_ccount = NULL;
482 last_ccount = comparison_count;
483 }
484 if (needle_last_ccount == NULL)
485 {
486 /* Try the Knuth-Morris-Pratt algorithm. */
487 const unsigned char *result;
488 bool success =
489 knuth_morris_pratt ((const unsigned char *) haystack,
490 (const unsigned char *) (needle - 1),
491 strlen (needle - 1),
492 &result);
493 if (success)
494 return (char *) result;
495 try_kmp = false;
496 }
497 }
498
499 outer_loop_count++;
500 comparison_count++;
501 if (*haystack == b)
502 /* The first character matches. */
503 {
504 const char *rhaystack = haystack + 1;
505 const char *rneedle = needle;
506
507 for (;; rhaystack++, rneedle++)
508 {
509 if (*rneedle == '\0')
510 /* Found a match. */
511 return (char *) haystack;
512 if (*rhaystack == '\0')
513 /* No match. */
514 return NULL;
515 comparison_count++;
516 if (*rhaystack != *rneedle)
517 /* Nothing in this round. */
518 break;
519 }
520 }
521 }
522 }
523 else
524 return (char *) haystack;
525 }
526 }