diff mbox series

[v7,09/17] string: Improve generic strcmp

Message ID 20230111204558.2402155-10-adhemerval.zanella@linaro.org
State Superseded
Headers
Series Improve generic string routines |

Checks

Context Check Description
dj/TryBot-apply_patch success Patch applied to master at the time it was sent

Commit Message

Adhemerval Zanella Netto Jan. 11, 2023, 8:45 p.m. UTC 
  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(-)

Comments

Noah Goldstein Jan. 12, 2023, 5:20 p.m. UTC | #1 
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
>
Carlos Seo Jan. 12, 2023, 5:26 p.m. UTC | #2 
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'
Adhemerval Zanella Netto Jan. 13, 2023, 6:25 p.m. UTC | #3 
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 mbox series

Patch

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