memmem: slight optimization
authorEric Blake <eblake@redhat.com>
Mon, 21 Jun 2010 22:16:44 +0000 (16:16 -0600)
committerEric Blake <eblake@redhat.com>
Tue, 22 Jun 2010 14:32:03 +0000 (08:32 -0600)
commitfffd5faca72521880531fdebe05675828fad0628
treebf82bcc2be3aab0fb4583e6d29585915ceac5fa4
parent12619428c2ef7601f014af01048a28274de7a36c
memmem: slight optimization

For any needle, the factorization 0/n has a local period of 1, so it
is a critical factorization iff the entire needle consists only of a
single repeated byte, in which case 1/n-1 would also be critical.
Starting with a comparison of x[0] and x[1] in the maximal suffix
check will either find the 0/n case or move on to something else, so
we can optimize and start with the x[1] vs. x[2] case to begin with.

To avoid out-of-bounds references, we must then special case needles
of length two or less.  However, for these cases, we can determine a
critical factorization without any probes of the needle (we already
require a non-empty needle; a 1-byte needle can factor as either 0/1
or 1/0 but the rest of our code assumes a non-empty suffix; and of the
two 2-byte needle patterns, "aa" can factor as either 0/2 or 1/1 but
with best performance for 1/1, and "ab" must be factored as 1/1).

* lib/str-two-way.h (critical_factorization): Update comments.
Reduce work during factorization phase.
Reported by Carlos Bueno <carlos@bueno.org>.

Signed-off-by: Eric Blake <eblake@redhat.com>
ChangeLog
lib/str-two-way.h