optimized memchr (and probably other string functions)

[Wolfgang Solfrank <Wolfgang%Solfrank.net@localhost>]

Hello,

by accident I stepped over the "optimized" implementation of memchr
in src/common/lib/lic/arch/x86_64/memchr.S.  The code in there blindly
copies the logic from src/common/lib/libc/arch/x86_64/strlen.S without
consideration of the comments in that code.

(The same holds for the equivalent code in src/common/lib/lic/arch/i386,
from which the code for x86_64 was probably stolen.  Therefor the
cross-posting.)

The comment in the strlen code tells us about 3 alternative algorithms
to find the terminating NUL character.  The third alternative, while
requiring the least instructions, doesn't always terminate the main loop
with a word known to have a NUL character in it, but "it also evaluates
to a non-zero value" (which indicates the presence of a NUL character
in it) "when none of the bytes in the original word is zero."  It
argues that these are "rare cases", because "the false positive can
only occur if the most significant bit of a byte within the word is set.
The expression will never fail for typical 7-bit ASCII strings."

Now it could be argued for strlen that the "typical 7-bit ASCII strings"
aren't that typical anymore nowadays, but I'd probably still take that
as a given.  However, in the case of memchr, where you normally search
in random binary data, this argument doesn't hold any longer.  The false
positives are quite likely here (i.e. one byte out of 8 (4 in the case
of i386) with the high bit set.)  In this case the algorithm, after
doing the check of the whole word, checks every byte of the word for
a match, i.e. in many cases the optimization doesn't optimize the
memchr function at all.

Therefor I'd like the memchr function to use one of the other two
alternative algorithms, probably the second one, described in the
comment in strlen.S.

Comments?

Ciao,
Wolfgang
--
Wolfgang%Solfrank.net@localhost                         Wolfgang Solfrank