strstr: revert patches that introduced bug and pessimization
authorEric Blake <eblake@redhat.com>
Fri, 25 Feb 2011 16:10:57 +0000 (09:10 -0700)
committerEric Blake <eblake@redhat.com>
Fri, 25 Feb 2011 16:10:57 +0000 (09:10 -0700)
commit034c875de9bd7c3dd75d5d169b8b1082bd30eb99
treebd7cefb3b42fe16054d7c5ef551557bef89d55de
parent9a29c4d601c340a8329954974386bb3dc7f1ea4d
strstr: revert patches that introduced bug and pessimization

Jim's one-liner solved the bug by pessimizing speed, making the
algorithm shift less per iteration and thus perform more repeated
comparisons.  The real reason for the bug is that my supposed
"optimizations" actually resulted in cases on certain periodic needles
where critical_factorization returned a factorization that was equal
to, rather than less than the period of the needle.  This makes the
CMP_FUNC choose the wrong branch, since a periodic needle must be
handled differently than one where the left half of the needle does
not overlap the right half.

Thankfully, the flawed "optimization" was only present in gnulib, and
was never ported to glibc or cygwin (the only two known
implementations that use the two-way algorithm), so no additional m4
check is needed to detect the bug in the wild.

* lib/str-two-way.h: Add another reference.
(two_way_short_needle, two_way_long_needle): Revert changes from
2011-02-24; they pessimize search speed.
(critical_factorization): Partially revert changes from
2010-06-22; they violate the requirement that the left half of the
needle be smaller than the period of the needle.

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