1 /* SPDX-License-Identifier: BSD-3-Clause */
3  * Copyright (c) 1994-2009  Red Hat, Inc.
33 /* Byte-wise substring search, using the Two-Way algorithm.
46 				lvalue.  For NUL-terminated searches,
51   For case-insensitivity, you may optionally define:
67 /* We use the Two-Way string matching algorithm, which guarantees
70    Boyer-Moore algorithm to achieve improved (potentially sub-linear)
73    See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
74    and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
77 /* Point at which computing a bad-byte shift table is likely to be
82    hand, on non-POSIX systems with CHAR_BIT larger than eight, the
101    *PERIOD to the global period of the right half.
103    The global period of a string is the smallest index (possibly its
110    non-empty NEEDLE have a local period of at least 1 and no greater
114    equals the global period.  All strings have at least one critical
115    factorization with the left half smaller than the global period.
134      0 <= j < NEEDLE_LEN - 1  in critical_factorization()
135      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)  in critical_factorization()
136      min(max_suffix, max_suffix_rev) < global period of NEEDLE  in critical_factorization()
137      1 <= p <= global period of NEEDLE  in critical_factorization()
138      p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]  in critical_factorization()
155 	  p = j - max_suffix;  in critical_factorization()
190 	  p = j - max_suffix_rev;  in critical_factorization()
219 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
226    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
228    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
239      smaller than the global period, and the right half is  in two_way_short_needle()
240      periodic (with a period as large as NEEDLE_LEN - suffix).  */  in two_way_short_needle()
262 	      i = suffix - 1;  in two_way_short_needle()
265 		--i;  in two_way_short_needle()
271 	      memory = needle_len - period;  in two_way_short_needle()
275 	      j += i - suffix + 1;  in two_way_short_needle()
284       period = MAX (suffix, needle_len - suffix) + 1;  in two_way_short_needle()
296 	      i = suffix - 1;  in two_way_short_needle()
299 		--i;  in two_way_short_needle()
305 	    j += i - suffix + 1;  in two_way_short_needle()
311 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
318    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
321    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
334      smaller than the global period, and the right half is  in two_way_long_needle()
335      periodic (with a period as large as NEEDLE_LEN - suffix).  */  in two_way_long_needle()
341      shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */  in two_way_long_needle()
345     shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;  in two_way_long_needle()
361 	  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];  in two_way_long_needle()
369 		  shift = needle_len - period;  in two_way_long_needle()
378 	  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])  in two_way_long_needle()
381 	  if (needle_len - 1 <= i)  in two_way_long_needle()
384 	      i = suffix - 1;  in two_way_long_needle()
387 		--i;  in two_way_long_needle()
393 	      memory = needle_len - period;  in two_way_long_needle()
397 	      j += i - suffix + 1;  in two_way_long_needle()
407       period = MAX (suffix, needle_len - suffix) + 1;  in two_way_long_needle()
413 	  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];  in two_way_long_needle()
422 	  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])  in two_way_long_needle()
425 	  if (needle_len - 1 <= i)  in two_way_long_needle()
428 	      i = suffix - 1;  in two_way_long_needle()
431 		--i;  in two_way_long_needle()
437 	    j += i - suffix + 1;  in two_way_long_needle()