| Message ID | 20230111204558.2402155-10-adhemerval.zanella@linaro.org |
|---|---|
| State | New |
| Headers | show |
| Series | [v7,01/17] Parameterize op_t from memcopy.h | expand |
On Wed, Jan 11, 2023 at 12:46 PM Adhemerval Zanella <adhemerval.zanella@linaro.org> wrote: > > From: Adhemerval Zanella Netto <adhemerval.zanella@linaro.org> > > New generic implementation tries to use word operations along with > the new string-fz{b,i} functions even for inputs with different > alignments (with still uses aligned access plus merge operation > to get a correct word by word comparison). > > Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, > and powerpc-linux-gnu by removing the arch-specific assembly > implementation and disabling multi-arch (it covers both LE and BE > for 64 and 32 bits). > > Co-authored-by: Richard Henderson <richard.henderson@linaro.org> > --- > string/strcmp.c | 119 +++++++++++++++++++++++++++++++++++++++++------- > 1 file changed, 103 insertions(+), 16 deletions(-) > > diff --git a/string/strcmp.c b/string/strcmp.c > index 053f5a8d2b..fafd967567 100644 > --- a/string/strcmp.c > +++ b/string/strcmp.c > @@ -15,33 +15,120 @@ > License along with the GNU C Library; if not, see > <https://www.gnu.org/licenses/>. */ > > +#include <stdint.h> > +#include <string-extbyte.h> > +#include <string-fzb.h> > +#include <string-fzi.h> > #include <string.h> > +#include <memcopy.h> > > -#undef strcmp > - > -#ifndef STRCMP > -# define STRCMP strcmp > +#ifdef STRCMP > +# define strcmp STRCMP > #endif > > +static inline int > +final_cmp (const op_t w1, const op_t w2) > +{ > + /* It can not use index_first_zero_ne because it must not compare past the > + final '/0' is present (and final_cmp is called before has_zero check). > + */ > + for (size_t i = 0; i < sizeof (op_t); i++) > + { > + unsigned char c1 = extractbyte (w1, i); > + unsigned char c2 = extractbyte (w2, i); > + if (c1 == '\0' || c1 != c2) > + return c1 - c2; > + } > + return 0; > +} > + > +/* Aligned loop: if a difference is found, exit to compare the bytes. Else > + if a zero is found we have equal strings. */ > +static inline int > +strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1) > +{ > + op_t w2 = *x2++; > + > + while (w1 == w2) > + { > + if (has_zero (w1)) > + return 0; > + w1 = *x1++; > + w2 = *x2++; > + } > + > + return final_cmp (w1, w2); > +} > + > +/* Unaligned loop: align the first partial of P2, with 0xff for the rest of > + the bytes so that we can also apply the has_zero test to see if we have > + already reached EOS. If we have, then we can simply fall through to the > + final comparison. */ > +static inline int > +strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) > +{ > + op_t w2a = *x2++; > + uintptr_t sh_1 = ofs * CHAR_BIT; > + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; > + > + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); > + if (!has_zero (w2)) > + { > + op_t w2b; > + > + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, > + does not contain end-of-string. Therefore it is safe (and necessary) > + to read another word from each while we do not have a difference. */ > + while (1) > + { > + w2b = *x2++; > + w2 = MERGE (w2a, sh_1, w2b, sh_2); > + if (w1 != w2) > + return final_cmp (w1, w2); > + if (has_zero (w2b)) > + break; > + w1 = *x1++; > + w2a = w2b; > + } > + > + /* Zero found in the second partial of P2. If we had EOS in the aligned > + word, we have equality. */ > + if (has_zero (w1)) Can't the zero in w1 and w2b be at different bytes? I.e even though they both contain zero the strings are not-equal? Imo it would be make more sense to just replace the `if (has_zero(w2b)) break` above with `if(has_zero (w1)) return 0;` and entirely remove the tail. > + return 0; > + > + /* Load the final word of P1 and align the final partial of P2. */ > + w1 = *x1++; > + w2 = MERGE (w2b, sh_1, 0, sh_2); > + } > + > + return final_cmp (w1, w2); > +} > + > /* Compare S1 and S2, returning less than, equal to or > greater than zero if S1 is lexicographically less than, > equal to or greater than S2. */ > int > -STRCMP (const char *p1, const char *p2) > +strcmp (const char *p1, const char *p2) > { > - const unsigned char *s1 = (const unsigned char *) p1; > - const unsigned char *s2 = (const unsigned char *) p2; > - unsigned char c1, c2; > - > - do > + /* Handle the unaligned bytes of p1 first. */ > + uintptr_t n = -(uintptr_t)p1 % sizeof(op_t); > + for (int i = 0; i < n; ++i) > { > - c1 = (unsigned char) *s1++; > - c2 = (unsigned char) *s2++; > - if (c1 == '\0') > - return c1 - c2; > + unsigned char c1 = *p1++; > + unsigned char c2 = *p2++; > + int diff = c1 - c2; > + if (c1 == '\0' || diff != 0) > + return diff; > } > - while (c1 == c2); > > - return c1 - c2; > + /* P1 is now aligned to unsigned long. P2 may or may not be. */ > + const op_t *x1 = (const op_t *) p1; > + op_t w1 = *x1++; > + uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t); > + return ofs == 0 > + ? strcmp_aligned_loop (x1, (const op_t *)p2, w1) > + : strcmp_unaligned_loop (x1, (const op_t *)(p2 - ofs), w1, ofs); > } > +#ifndef STRCMP > libc_hidden_builtin_def (strcmp) > +#endif > -- > 2.34.1 >
On Wed, 11 Jan 2023 at 17:48, Adhemerval Zanella via Libc-alpha <libc-alpha@sourceware.org> wrote: > > From: Adhemerval Zanella Netto <adhemerval.zanella@linaro.org> > > +static inline int > +final_cmp (const op_t w1, const op_t w2) > +{ > + /* It can not use index_first_zero_ne because it must not compare past the > + final '/0' is present (and final_cmp is called before has_zero check). > + */ Minor comment typo: '\0'
On 12/01/23 14:26, Carlos Seo wrote: > On Wed, 11 Jan 2023 at 17:48, Adhemerval Zanella via Libc-alpha > <libc-alpha@sourceware.org> wrote: >> >> From: Adhemerval Zanella Netto <adhemerval.zanella@linaro.org> >> >> +static inline int >> +final_cmp (const op_t w1, const op_t w2) >> +{ >> + /* It can not use index_first_zero_ne because it must not compare past the >> + final '/0' is present (and final_cmp is called before has_zero check). >> + */ > > Minor comment typo: '\0' Ack.
diff --git a/string/strcmp.c b/string/strcmp.c index 053f5a8d2b..fafd967567 100644 --- a/string/strcmp.c +++ b/string/strcmp.c @@ -15,33 +15,120 @@ License along with the GNU C Library; if not, see <https://www.gnu.org/licenses/>. */ +#include <stdint.h> +#include <string-extbyte.h> +#include <string-fzb.h> +#include <string-fzi.h> #include <string.h> +#include <memcopy.h> -#undef strcmp - -#ifndef STRCMP -# define STRCMP strcmp +#ifdef STRCMP +# define strcmp STRCMP #endif +static inline int +final_cmp (const op_t w1, const op_t w2) +{ + /* It can not use index_first_zero_ne because it must not compare past the + final '/0' is present (and final_cmp is called before has_zero check). + */ + for (size_t i = 0; i < sizeof (op_t); i++) + { + unsigned char c1 = extractbyte (w1, i); + unsigned char c2 = extractbyte (w2, i); + if (c1 == '\0' || c1 != c2) + return c1 - c2; + } + return 0; +} + +/* Aligned loop: if a difference is found, exit to compare the bytes. Else + if a zero is found we have equal strings. */ +static inline int +strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1) +{ + op_t w2 = *x2++; + + while (w1 == w2) + { + if (has_zero (w1)) + return 0; + w1 = *x1++; + w2 = *x2++; + } + + return final_cmp (w1, w2); +} + +/* Unaligned loop: align the first partial of P2, with 0xff for the rest of + the bytes so that we can also apply the has_zero test to see if we have + already reached EOS. If we have, then we can simply fall through to the + final comparison. */ +static inline int +strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) +{ + op_t w2a = *x2++; + uintptr_t sh_1 = ofs * CHAR_BIT; + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; + + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); + if (!has_zero (w2)) + { + op_t w2b; + + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, + does not contain end-of-string. Therefore it is safe (and necessary) + to read another word from each while we do not have a difference. */ + while (1) + { + w2b = *x2++; + w2 = MERGE (w2a, sh_1, w2b, sh_2); + if (w1 != w2) + return final_cmp (w1, w2); + if (has_zero (w2b)) + break; + w1 = *x1++; + w2a = w2b; + } + + /* Zero found in the second partial of P2. If we had EOS in the aligned + word, we have equality. */ + if (has_zero (w1)) + return 0; + + /* Load the final word of P1 and align the final partial of P2. */ + w1 = *x1++; + w2 = MERGE (w2b, sh_1, 0, sh_2); + } + + return final_cmp (w1, w2); +} + /* Compare S1 and S2, returning less than, equal to or greater than zero if S1 is lexicographically less than, equal to or greater than S2. */ int -STRCMP (const char *p1, const char *p2) +strcmp (const char *p1, const char *p2) { - const unsigned char *s1 = (const unsigned char *) p1; - const unsigned char *s2 = (const unsigned char *) p2; - unsigned char c1, c2; - - do + /* Handle the unaligned bytes of p1 first. */ + uintptr_t n = -(uintptr_t)p1 % sizeof(op_t); + for (int i = 0; i < n; ++i) { - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0') - return c1 - c2; + unsigned char c1 = *p1++; + unsigned char c2 = *p2++; + int diff = c1 - c2; + if (c1 == '\0' || diff != 0) + return diff; } - while (c1 == c2); - return c1 - c2; + /* P1 is now aligned to unsigned long. P2 may or may not be. */ + const op_t *x1 = (const op_t *) p1; + op_t w1 = *x1++; + uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t); + return ofs == 0 + ? strcmp_aligned_loop (x1, (const op_t *)p2, w1) + : strcmp_unaligned_loop (x1, (const op_t *)(p2 - ofs), w1, ofs); } +#ifndef STRCMP libc_hidden_builtin_def (strcmp) +#endif
From: Adhemerval Zanella Netto <adhemerval.zanella@linaro.org> New generic implementation tries to use word operations along with the new string-fz{b,i} functions even for inputs with different alignments (with still uses aligned access plus merge operation to get a correct word by word comparison). Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, and powerpc-linux-gnu by removing the arch-specific assembly implementation and disabling multi-arch (it covers both LE and BE for 64 and 32 bits). Co-authored-by: Richard Henderson <richard.henderson@linaro.org> --- string/strcmp.c | 119 +++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 103 insertions(+), 16 deletions(-)