1 /* Byte-wise substring search, using the Two-Way algorithm.
14 				lvalue.  For NUL-terminated searches,
19   For case-insensitivity, you may optionally define:
35 /* We use the Two-Way string matching algorithm, which guarantees
38    Boyer-Moore algorithm to achieve improved (potentially sub-linear)
41    See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
42    and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
45 /* Point at which computing a bad-byte shift table is likely to be
50    hand, on non-POSIX systems with CHAR_BIT larger than eight, the
78    non-empty NEEDLE have a local period of at least 1 and no greater
102      0 <= j < NEEDLE_LEN - 1  in critical_factorization()
103      -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)  in critical_factorization()
123 	  p = j - max_suffix;  in critical_factorization()
158 	  p = j - max_suffix_rev;  in critical_factorization()
187 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
194    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
196    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
201   size_t i; /* Index into current byte of NEEDLE.  */  in two_way_short_needle()  local
208      periodic (with a period as large as NEEDLE_LEN - suffix).  */  in two_way_short_needle()
223 	  i = MAX (suffix, memory);  in two_way_short_needle()
224 	  while (i < needle_len && (CANON_ELEMENT (needle[i])  in two_way_short_needle()
225 				    == CANON_ELEMENT (haystack[i + j])))  in two_way_short_needle()
226 	    ++i;  in two_way_short_needle()
227 	  if (needle_len <= i)  in two_way_short_needle()
230 	      i = suffix - 1;  in two_way_short_needle()
231 	      while (memory < i + 1 && (CANON_ELEMENT (needle[i])  in two_way_short_needle()
232 					== CANON_ELEMENT (haystack[i + j])))  in two_way_short_needle()
233 		--i;  in two_way_short_needle()
234 	      if (i + 1 < memory + 1)  in two_way_short_needle()
239 	      memory = needle_len - period;  in two_way_short_needle()
243 	      j += i - suffix + 1;  in two_way_short_needle()
252       period = MAX (suffix, needle_len - suffix) + 1;  in two_way_short_needle()
257 	  i = suffix;  in two_way_short_needle()
258 	  while (i < needle_len && (CANON_ELEMENT (needle[i])  in two_way_short_needle()
259 				    == CANON_ELEMENT (haystack[i + j])))  in two_way_short_needle()
260 	    ++i;  in two_way_short_needle()
261 	  if (needle_len <= i)  in two_way_short_needle()
264 	      i = suffix - 1;  in two_way_short_needle()
265 	      while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])  in two_way_short_needle()
266 				       == CANON_ELEMENT (haystack[i + j])))  in two_way_short_needle()
267 		--i;  in two_way_short_needle()
268 	      if (i == SIZE_MAX)  in two_way_short_needle()
273 	    j += i - suffix + 1;  in two_way_short_needle()
279 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
286    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
289    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
295   size_t i; /* Index into current byte of NEEDLE.  */  in two_way_long_needle()  local
303      periodic (with a period as large as NEEDLE_LEN - suffix).  */  in two_way_long_needle()
309      shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */  in two_way_long_needle()
310   for (i = 0; i < 1U << CHAR_BIT; i++)  in two_way_long_needle()
311     shift_table[i] = needle_len;  in two_way_long_needle()
312   for (i = 0; i < needle_len; i++)  in two_way_long_needle()
313     shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;  in two_way_long_needle()
329 	  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];  in two_way_long_needle()
337 		  shift = needle_len - period;  in two_way_long_needle()
345 	  i = MAX (suffix, memory);  in two_way_long_needle()
346 	  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])  in two_way_long_needle()
347 					== CANON_ELEMENT (haystack[i + j])))  in two_way_long_needle()
348 	    ++i;  in two_way_long_needle()
349 	  if (needle_len - 1 <= i)  in two_way_long_needle()
352 	      i = suffix - 1;  in two_way_long_needle()
353 	      while (memory < i + 1 && (CANON_ELEMENT (needle[i])  in two_way_long_needle()
354 					== CANON_ELEMENT (haystack[i + j])))  in two_way_long_needle()
355 		--i;  in two_way_long_needle()
356 	      if (i + 1 < memory + 1)  in two_way_long_needle()
361 	      memory = needle_len - period;  in two_way_long_needle()
365 	      j += i - suffix + 1;  in two_way_long_needle()
375       period = MAX (suffix, needle_len - suffix) + 1;  in two_way_long_needle()
381 	  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];  in two_way_long_needle()
389 	  i = suffix;  in two_way_long_needle()
390 	  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])  in two_way_long_needle()
391 					== CANON_ELEMENT (haystack[i + j])))  in two_way_long_needle()
392 	    ++i;  in two_way_long_needle()
393 	  if (needle_len - 1 <= i)  in two_way_long_needle()
396 	      i = suffix - 1;  in two_way_long_needle()
397 	      while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])  in two_way_long_needle()
398 				       == CANON_ELEMENT (haystack[i + j])))  in two_way_long_needle()
399 		--i;  in two_way_long_needle()
400 	      if (i == SIZE_MAX)  in two_way_long_needle()
405 	    j += i - suffix + 1;  in two_way_long_needle()