[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 [email protected] +1-801-349-2682 Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
