• Eric Blake's avatar
    memmem: slight optimization · fffd5fac
    Eric Blake authored
    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: default avatarEric Blake <eblake@redhat.com>
    fffd5fac
str-two-way.h 17 KB