Re: bug in autoconf-2.64

[Eric Blake]

[dropping bug-autoconf, bug-m4]

On 02/24/2011 09:04 AM, Jim Meyering wrote:
> FYI,
> 
> Here's a much-reduced test case for the short-needle case:
> 
>     const char *needle = ".d.";
>     const char *haystack = "..d.";
>     const char* p = strstr (haystack, needle);
>     ASSERT (p && p - haystack == 1);
> 
> Interestingly, it doesn't trigger a failure in glibc's
> slightly different implementation.  Eric mentioned
> privately that glibc does not yet have gnulib's commit
> fffd5faca, and that affects periodicity detection.

Not quite right.  But Jim and I did discover:

needle "." and haystack "..wi.d." fails with gnulib.

Definitely the fault of commit fffd5faca; the comments state that
critical_factorization() will set period to something less than the
global period of the needle.  When starting the search at index 0 (as in
glibc or pre-"optimization"), this statement is true.  But when starting
the search at index 1 (post-patch), then critical_factorization() can
sometimes pick a factorization equal to rather than less than the
needle's global period, and the rest of the code was not prepared for this.

I'm still inspecting whether this optimization still makes sense (that
is, does Jim's one-liner change to remove the +1 re-computation of the
shifting period always works, or should fffd5faca be reverted).  And at
this point, I'm fairly confident that both glibc and cygwin are immune,
since neither of them borrowed from gnulib's optimization), but not
necessarily optimal.

-- 
Eric Blake   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature