kc3-lang/gnulib

2011-02-25T09:10:57

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>