9  * 1. Redistributions of source code must retain the above copyright notice,
10  * this list of conditions and the following disclaimer.
13  * this list of conditions and the following disclaimer in the documentation
16  * 3. Neither the name of the copyright holder nor the names of its
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30  * POSSIBILITY OF SUCH DAMAGE.
48 				avoid having to compute the end of H
53 				characters of P1 and P2 are equal.
56 				one of the two strings.  The argument
79    adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
80    speedup no greater than a factor of NEEDLE_LEN.  The larger the
99 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
100    Return the index of the first byte in the right half, and set
101    *PERIOD to the global period of the right half.
103    The global period of a string is the smallest index (possibly its
105    of the prefix (the last repetition may be a subset of the prefix).
108    length of the smallest word that shares a suffix with the left half
109    and shares a prefix with the right half.  All factorizations of a
110    non-empty NEEDLE have a local period of at least 1 and no greater
119    larger of two ordered maximal suffixes.  The ordered maximal
120    suffixes are determined by lexicographic comparison of
126   /* Index of last byte of left half, or SIZE_MAX.  */  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()
159 	  /* Advance through repetition of the current period.  */  in critical_factorization()
194 	  /* Advance through repetition of the current period.  */  in critical_factorization()
211   /* Choose the longer suffix.  Return the first byte of the right  in critical_factorization()
212      half, rather than the last byte of the left half.  */  in critical_factorization()
219 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
220    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
223    of 2 * NEEDLE_LEN comparisons.
233   size_t i; /* Index into current byte of NEEDLE.  */  in two_way_short_needle()
234   size_t j; /* Index into current window of HAYSTACK.  */  in two_way_short_needle()
235   size_t period; /* The period of the right half of needle.  */  in two_way_short_needle()
236   size_t suffix; /* The index of the right half of needle.  */  in two_way_short_needle()
249 	 of the period.  */  in two_way_short_needle()
268 	      /* No match, so remember how many repetitions of period  in two_way_short_needle()
282       /* The two halves of needle are distinct; no extra memory is  in two_way_short_needle()
311 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
312    NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This
315    of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
327   size_t i; /* Index into current byte of NEEDLE.  */  in two_way_long_needle()
328   size_t j; /* Index into current window of HAYSTACK.  */  in two_way_long_needle()
329   size_t period; /* The period of the right half of needle.  */  in two_way_long_needle()
330   size_t suffix; /* The index of the right half of needle.  */  in two_way_long_needle()
339      shift_table[c] is the distance from the last occurrence of c to  in two_way_long_needle()
340      the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.  in two_way_long_needle()
353 	 of the period.  */  in two_way_long_needle()
367 		     a byte out of place, there can be no match until  in two_way_long_needle()
376 	     already been matched, by virtue of the shift table.  */  in two_way_long_needle()
390 	      /* No match, so remember how many repetitions of period  in two_way_long_needle()
404       /* The two halves of needle are distinct; no extra memory is  in two_way_long_needle()
420 	     already been matched, by virtue of the shift table.  */  in two_way_long_needle()