[PATCH 2/*] Optimize generic strchrnul and strchr

[PATCH 2/*] Optimize generic strchrnul and strchr

[Ondřej Bílka]

This is my generic strchr algorithm resubmitted to use skeleton.

Idea to split into cases c<128 and c>128 didn't change.

So comments? How this perform on different architectures?

	* string/strchr.c: Use skeleton.
	* string/strchrnul.c: Likewise.


diff --git a/string/strchr.c b/string/strchr.c
index 5f90075..566ebab 100644
--- a/string/strchr.c
+++ b/string/strchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,162 +16,17 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
-
 #undef strchr
 
-/* Find the first occurrence of C in S.  */
+#define AS_STRCHR
+#define STRCHRNUL static_strchrnul
+#include "string/strchrnul.c"
+
 char *
-strchr (const char *s, int c_in)
+strchr (const char *s, int c)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-    else if (*char_ptr == '\0')
-      return NULL;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	    }
-	}
-    }
-
-  return NULL;
+  char *r = STRCHRNUL (s, c);
+  return (*r == c) ? r : NULL;
 }
 
 #ifdef weak_alias
diff --git a/string/strchrnul.c b/string/strchrnul.c
index 2678f1d..11c3bf6 100644
--- a/string/strchrnul.c
+++ b/string/strchrnul.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,153 +16,63 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 #include <stdlib.h>
 
-#undef __strchrnul
 #undef strchrnul
+#undef __strchrnul
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
+
+/* Here idea is still use the result of expression
+   contains_zero (*p) | contains_zero (*p ^ cmask)
+   but we can optimize it by using commutativity of operations.  */
+
+#include "string/common.h"
+#define EXPRESSION(s, cmask) (((((s & add) + add) & (((s & add) ^ cmask) + add)) | s) ^ high_bits) & high_bits
+
+#include "string/skeleton.h"
 
 #ifndef STRCHRNUL
 # define STRCHRNUL __strchrnul
 #endif
 
-/* Find the first occurrence of C in S or the final NUL byte.  */
+#ifdef AS_STRCHR
+static __always_inline
+#endif
 char *
-STRCHRNUL (s, c_in)
-     const char *s;
-     int c_in;
+STRCHRNUL (const char *s_in, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c || *char_ptr == '\0')
-      return (void *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
+  char *s_aligned;
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  unsigned long int cmask = c * ones;
+
+  if (__glibc_unlikely (c > 127))
     {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	    }
-	}
+      s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (contains_zero(*lptr) | contains_zero (*lptr ^ cmask))
+             >> (8 * (s_aligned - s));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      while (1)
+        {
+          s_aligned += LSIZE;
+          lptr = (const unsigned long int *) s_aligned;
+          mask = contains_zero(*lptr) | contains_zero (*lptr ^ cmask);
+          if (mask)
+            return s_aligned + first_nonzero_byte (mask);
+        }
     }
-
-  /* This should never happen.  */
-  return NULL;
+  else
+    return string_skeleton (s, c, 0);
 }
 
+#ifndef AS_STRCHR
 weak_alias (__strchrnul, strchrnul)
+#endif

[PATCH 1/*] Generic string function optimization: Add skeleton

[Ondřej Bílka]

Hi,

As i mentioned improving generic string functions this is my second
attempt. As lot of functions will be optimized in same way this uses
generic code flow. Functions will vary just by expression to check and
how interpret return value.

Performance gains of using this are from loop unrolling and better
header that doesn't have to check start byte-by-byte.

Unrolling migth be excessive but its better to tune it in skeleton than
try manually and risk introducing errors.

This implementation would probably be faster than assembly on other
architectures as this will beat it unless you used hardware specific
instruction or gcc messes up compilation and generates suboptimal code.

Comments?

	* string/common.h: New file.
	* string/skeleton.h: Likewise.

---
 string/common.h   |  35 +++++++++++++
 string/skeleton.h | 145 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 180 insertions(+)
 create mode 100644 string/common.h
 create mode 100644 string/skeleton.h

diff --git a/string/common.h b/string/common.h
new file mode 100644
index 0000000..09f950f
--- /dev/null
+++ b/string/common.h
@@ -0,0 +1,35 @@
+#include <stdint.h>
+
+static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
+static const unsigned long int add = 127 * (~0UL / 255);
+static const unsigned long int high_bits = 128 * (~0UL / 255);
+
+/* Use vector arithmetic tricks. Idea is to take expression works on
+   unsigned byte and evaluates 0 for nozero byte and nonzero on zero byte.
+   Our expression is  (((s & 127) + 127) ^ 128) & 128 & ~s
+   Now we evaluate this expression on each byte in parallel and on first 
+   nonzero byte our expression will have nonzero value. */
+
+static __always_inline
+unsigned long int 
+contains_zero (unsigned long int s)
+{
+  return (((s & add) + add) ^ high_bits) & high_bits & ~s;
+}
+
+#define LSIZE sizeof (unsigned long int)
+#define CROSS_PAGE(x, n) (((uintptr_t)x) % 4096 >= 4096 - n)
+
+static __always_inline
+size_t
+first_nonzero_byte (unsigned long int u)
+{
+#ifdef FAST_FFS
+  return ffsl (u) / 8 - 1;
+#else
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+#endif
+}
diff --git a/string/skeleton.h b/string/skeleton.h
new file mode 100644
index 0000000..42bab9a
--- /dev/null
+++ b/string/skeleton.h
@@ -0,0 +1,145 @@
+/* Skeleton of generic string functions.
+   Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+
+static __always_inline
+int
+found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+{
+  const unsigned long int *lptr = (const unsigned long int *) s;
+  unsigned long int mask = EXPRESSION(*lptr, cmask);
+  if (mask)
+    {
+      *result = s + first_nonzero_byte (mask);
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, int c_in, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  char *r;
+  unsigned long int cmask = c * ones;
+
+#if _STRING_ARCH_unaligned
+  /* We fetch 32 bytes while not crossing page boundary. 
+     Most strings in practice are of that size and we avoid a loop.
+     This looks as best in practice, alternative below uses aligned load 
+     but is slower when string starts just few 
+     bytes before 32 byte boundary. A tradeoff is that we rarely could 
+     fetch extra cache line without needing it but this optimization 
+     does pay for that. */
+  if (!CROSS_PAGE(s, 32))
+    {
+      if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+            return r;
+        }
+
+      if (BOUND (s + 32))
+        return NULL;
+    }
+  else
+    {
+#endif
+  /* We need use aligned loads. For first load we read some bytes before 
+     start that we discard by shifting them down. */
+ 
+      char *s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (EXPRESSION (*lptr, cmask)) >> (8 * (s_aligned - s));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      if (BOUND (s_aligned + 1 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 2 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 3 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 4 * LSIZE))
+        return NULL;
+#if _STRING_ARCH_unaligned
+    }
+#endif
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s_loop = PTR_ALIGN_DOWN (s, 4 * LSIZE);
+  while (!BOUND (s_loop + 4 * LSIZE))
+    {
+      s_loop += 4 * LSIZE;
+      lptr = (const unsigned long int *) (s_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s_loop + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 2 * LSIZE, cmask, &r))
+            return r;
+
+          return s_loop + 3 * LSIZE + first_nonzero_byte (mask);
+        }
+    }
+ return NULL;
+}
-- 

[PATCH 1/* v2] Generic string function optimization: Add skeleton

[Ondřej Bílka]

After testing I found that I added typo in conversion to skeleton. This
fixes it. Here is correct version.

	* string/common.h: New file.
	* string/skeleton.h: Likewise.

diff --git a/string/common.h b/string/common.h
new file mode 100644
index 0000000..3b239dd
--- /dev/null
+++ b/string/common.h
@@ -0,0 +1,35 @@
+#include <stdint.h>
+
+static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
+static const unsigned long int add = 127 * (~0UL / 255);
+static const unsigned long int high_bits = 128 * (~0UL / 255);
+
+/* Use vector arithmetic tricks. Idea is to take expression works on
+   unsigned byte and evaluates 0 for nozero byte and nonzero on zero byte.
+   Our expression is ((s + 127) & (~s)) & 128  
+   Now we evaluate this expression on each byte in parallel and on first 
+   nonzero byte our expression will have nonzero value. */
+
+static __always_inline
+unsigned long int 
+contains_zero (unsigned long int s)
+{
+  return (((s & add) + add) ^ high_bits) & high_bits & ~s;
+}
+
+#define LSIZE sizeof (unsigned long int)
+#define CROSS_PAGE(x, n) (((uintptr_t)x) % 4096 > 4096 - n)
+
+static __always_inline
+size_t
+first_nonzero_byte (unsigned long int u)
+{
+#ifdef FAST_FFS
+  return ffsl (u) / 8 - 1;
+#else
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+#endif
+}
diff --git a/string/skeleton.h b/string/skeleton.h
new file mode 100644
index 0000000..563e6e4
--- /dev/null
+++ b/string/skeleton.h
@@ -0,0 +1,145 @@
+/* Skeleton of generic string functions.
+   Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+
+static __always_inline
+int
+found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+{
+  const unsigned long int *lptr = (const unsigned long int *) s;
+  unsigned long int mask = EXPRESSION(*lptr, cmask);
+  if (mask)
+    {
+      *result = s + first_nonzero_byte (mask);
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, int c_in, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  char *r;
+  unsigned long int cmask = c * ones;
+
+#if _STRING_ARCH_unaligned
+  /* We fetch 32 bytes while not crossing page boundary. 
+     Most strings in practice are of that size and we avoid a loop.
+     This looks as best in practice, alternative below uses aligned load 
+     but is slower when string starts just few 
+     bytes before 32 byte boundary. A tradeoff is that we rarely could 
+     fetch extra cache line without needing it but this optimization 
+     does pay for that. */
+  if (!CROSS_PAGE(s, 32))
+    {
+      if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s + 5 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 6 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 7 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 8 * LSIZE, cmask, &r))
+            return r;
+        }
+
+      if (BOUND (s + 32))
+        return NULL;
+    }
+  else
+    {
+#endif
+  /* We need use aligned loads. For first load we read some bytes before 
+     start that we discard by shifting them down. */
+ 
+      char *s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (EXPRESSION (*lptr, cmask)) >> (8 * (s - s_aligned));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      if (BOUND (s_aligned + 1 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 1 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 2 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 2 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 3 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 3 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 4 * LSIZE))
+        return NULL;
+#if _STRING_ARCH_unaligned
+    }
+#endif
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s_loop = PTR_ALIGN_DOWN (s, 4 * LSIZE);
+  while (!BOUND (s_loop + 4 * LSIZE))
+    {
+      s_loop += 4 * LSIZE;
+      lptr = (const unsigned long int *) (s_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s_loop + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 2 * LSIZE, cmask, &r))
+            return r;
+
+          return s_loop + 3 * LSIZE + first_nonzero_byte (mask);
+        }
+    }
+ return NULL;
+}

[PATCH 2/* v2] Optimize generic strchrnul and strchr

[Ondřej Bílka]

On Wed, May 27, 2015 at 08:35:44AM +0200, Ondřej Bílka wrote:
> This is my generic strchr algorithm resubmitted to use skeleton.
> 
> Idea to split into cases c<128 and c>128 didn't change.
> 
> So comments? How this perform on different architectures?
> 
This also needed to change as I used older strchr wrapper. Here is
correct one.

 	* string/strchr.c: Use skeleton.
 	* string/strchrnul.c: Likewise.


diff --git a/string/strchr.c b/string/strchr.c
index 5f90075..e7c2e4c 100644
--- a/string/strchr.c
+++ b/string/strchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,166 +16,21 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
-
 #undef strchr
+#undef index
+
+#define AS_STRCHR
+#define STRCHRNUL strchrnul_static
+#include "string/strchrnul.c"
+
 
-/* Find the first occurrence of C in S.  */
 char *
 strchr (const char *s, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-    else if (*char_ptr == '\0')
-      return NULL;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	    }
-	}
-    }
-
-  return NULL;
+  unsigned char c = (unsigned char) c_in;
+  unsigned char *r = (unsigned char *) STRCHRNUL (s, c);
+  return (*r == c) ? (char *) r : NULL;
 }
 
-#ifdef weak_alias
-#undef index
 weak_alias (strchr, index)
-#endif
 libc_hidden_builtin_def (strchr)
diff --git a/string/strchrnul.c b/string/strchrnul.c
index 2678f1d..95fa11d 100644
--- a/string/strchrnul.c
+++ b/string/strchrnul.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,153 +16,63 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 #include <stdlib.h>
 
-#undef __strchrnul
 #undef strchrnul
+#undef __strchrnul
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
+
+/* Here idea is still use the result of expression
+   contains_zero (*p) | contains_zero (*p ^ cmask)
+   but we can optimize it by using commutativity of operations.  */
+
+#include "string/common.h"
+/* #define EXPRESSION(s, cmask) (((((s & add) + add) & (((s & add) ^ cmask) + add)) | s) ^ high_bits) & high_bits */
+
+#define EXPRESSION(s, cmask) (contains_zero(s) | contains_zero (s ^ cmask))
+#include "string/skeleton.h"
 
 #ifndef STRCHRNUL
 # define STRCHRNUL __strchrnul
 #endif
 
-/* Find the first occurrence of C in S or the final NUL byte.  */
+#ifdef AS_STRCHR
+static __always_inline
+#endif
 char *
-STRCHRNUL (s, c_in)
-     const char *s;
-     int c_in;
+STRCHRNUL (const char *s_in, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c || *char_ptr == '\0')
-      return (void *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
+  char *s_aligned;
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  unsigned long int cmask = c * ones;
+  if (__glibc_unlikely (c > 127))
     {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	    }
-	}
+      s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (contains_zero(*lptr) | contains_zero (*lptr ^ cmask))
+             >> (8 * (s - s_aligned));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      while (1)
+        {
+          s_aligned += LSIZE;
+          lptr = (const unsigned long int *) s_aligned;
+          mask = contains_zero(*lptr) | contains_zero (*lptr ^ cmask);
+          if (mask)
+            return s_aligned + first_nonzero_byte (mask);
+        }
     }
-
-  /* This should never happen.  */
-  return NULL;
+  else
+    return string_skeleton (s, c, 0);
 }
 
+#ifndef AS_STRCHR
 weak_alias (__strchrnul, strchrnul)
+#endif

[PATCH 3/* v2] Generic string strlen and rawmemchr

[Ondřej Bílka]

With strlen and rawmemchr I use same idea.

As one could get rawmemchr with strlen by first xoring input and
strlen from rawmemchr by letting gcc optimize rawmemchr(x,0) these
belong together. I keep them separate now but it could change if you
want it.

 	* string/strlen.c: Use skeleton.
 	* string/rawmemchr.c: Likewise.

diff --git a/string/rawmemchr.c b/string/rawmemchr.c
index 05b22be..4aeaf03 100644
--- a/string/rawmemchr.c
+++ b/string/rawmemchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,166 +15,23 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
+#include <string.h>
+#include <stdlib.h>
 
-#undef __ptr_t
-#define __ptr_t void *
+#undef rawmemchr
+#undef __rawmemchr
 
-#if defined (_LIBC)
-# include <string.h>
-# include <memcopy.h>
-# include <stdlib.h>
-#endif
 
-#if defined (HAVE_LIMITS_H) || defined (_LIBC)
-# include <limits.h>
-#endif
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#include "string/skeleton.h"
 
-#define LONG_MAX_32_BITS 2147483647
-
-#ifndef LONG_MAX
-#define LONG_MAX LONG_MAX_32_BITS
-#endif
-
-#include <sys/types.h>
-
-#undef memchr
-
-#ifndef RAWMEMCHR
-# define RAWMEMCHR __rawmemchr
-#endif
-
-/* Find the first occurrence of C in S.  */
-__ptr_t
-RAWMEMCHR (s, c_in)
-     const __ptr_t s;
-     int c_in;
+void *
+__rawmemchr (const void *s, int c)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (__ptr_t) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-
-  if (sizeof (longword) != 4 && sizeof (longword) != 8)
-    abort ();
-
-#if LONG_MAX <= LONG_MAX_32_BITS
-  magic_bits = 0x7efefeff;
-#else
-  magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
-#endif
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-#if LONG_MAX > LONG_MAX_32_BITS
-  charmask |= charmask << 32;
-#endif
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (1)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C, not zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++ ^ charmask;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (cp[0] == c)
-	    return (__ptr_t) cp;
-	  if (cp[1] == c)
-	    return (__ptr_t) &cp[1];
-	  if (cp[2] == c)
-	    return (__ptr_t) &cp[2];
-	  if (cp[3] == c)
-	    return (__ptr_t) &cp[3];
-#if LONG_MAX > 2147483647
-	  if (cp[4] == c)
-	    return (__ptr_t) &cp[4];
-	  if (cp[5] == c)
-	    return (__ptr_t) &cp[5];
-	  if (cp[6] == c)
-	    return (__ptr_t) &cp[6];
-	  if (cp[7] == c)
-	    return (__ptr_t) &cp[7];
-#endif
-	}
-    }
+  return (void *) string_skeleton (s, c, NULL);
 }
+
 libc_hidden_def (__rawmemchr)
 weak_alias (__rawmemchr, rawmemchr)
+
diff --git a/string/strlen.c b/string/strlen.c
index d066bde..2cc0369 100644
--- a/string/strlen.c
+++ b/string/strlen.c
@@ -1,8 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -25,81 +22,15 @@
 
 /* Return the length of the null-terminated string STR.  Scan for
    the null terminator quickly by testing four bytes at a time.  */
+
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p))
+#include "string/skeleton.h"
+
 size_t
 strlen (const char *str)
 {
-  const char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      return char_ptr - str;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      longword = *longword_ptr++;
-
-      if (((longword - lomagic) & ~longword & himagic) != 0)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  if (cp[0] == 0)
-	    return cp - str;
-	  if (cp[1] == 0)
-	    return cp - str + 1;
-	  if (cp[2] == 0)
-	    return cp - str + 2;
-	  if (cp[3] == 0)
-	    return cp - str + 3;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (cp[4] == 0)
-		return cp - str + 4;
-	      if (cp[5] == 0)
-		return cp - str + 5;
-	      if (cp[6] == 0)
-		return cp - str + 6;
-	      if (cp[7] == 0)
-		return cp - str + 7;
-	    }
-	}
-    }
+  return string_skeleton (str, 0, 0) - str;
 }
+
 libc_hidden_builtin_def (strlen)

[PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

Here we first deal with functions that use size bound.
Main technical complication is pointer wraparound for large n so it
needs to be handled accordingly. Otherwise its almost same as rawmemchr.

As I wrote before that we could optimize  memchr(x,0,n) to strnlen
opposite is also true. Here strnlen uses memchr and lets gcc simply
that.

Comments?

	* string/memchr.c: Use skeleton.
	* string/strnlen.c: Likewise.

diff --git a/string/memchr.c b/string/memchr.c
index 6896465..fede01a 100644
--- a/string/memchr.c
+++ b/string/memchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,143 +15,41 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifndef _LIBC
-# include <config.h>
-#endif
-
 #include <string.h>
-
-#include <stddef.h>
-
-#include <limits.h>
+#include <stdlib.h>
 
 #undef __memchr
-#ifdef _LIBC
-# undef memchr
-#endif
+#undef memchr
 
-#ifndef weak_alias
-# define __memchr memchr
-#endif
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
+
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
+#include "string/skeleton.h"
 
 #ifndef MEMCHR
 # define MEMCHR __memchr
 #endif
 
-/* Search no more than N bytes of S for C.  */
+#ifdef STATIC
+static __always_inline
+#endif
 void *
-MEMCHR (void const *s, int c_in, size_t n)
+MEMCHR (const void *_str, int c, size_t n)
 {
-  /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
-     long instead of a 64-bit uintmax_t tends to give better
-     performance.  On 64-bit hardware, unsigned long is generally 64
-     bits already.  Change this typedef to experiment with
-     performance.  */
-  typedef unsigned long int longword;
-
-  const unsigned char *char_ptr;
-  const longword *longword_ptr;
-  longword repeated_one;
-  longword repeated_c;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few bytes by reading one byte at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
-       --n, ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-
-  longword_ptr = (const longword *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to any size longwords.  */
-
-  /* Compute auxiliary longword values:
-     repeated_one is a value which has a 1 in every byte.
-     repeated_c has c in every byte.  */
-  repeated_one = 0x01010101;
-  repeated_c = c | (c << 8);
-  repeated_c |= repeated_c << 16;
-  if (0xffffffffU < (longword) -1)
-    {
-      repeated_one |= repeated_one << 31 << 1;
-      repeated_c |= repeated_c << 31 << 1;
-      if (8 < sizeof (longword))
-	{
-	  size_t i;
-
-	  for (i = 64; i < sizeof (longword) * 8; i *= 2)
-	    {
-	      repeated_one |= repeated_one << i;
-	      repeated_c |= repeated_c << i;
-	    }
-	}
-    }
-
-  /* Instead of the traditional loop which tests each byte, we will test a
-     longword at a time.  The tricky part is testing if *any of the four*
-     bytes in the longword in question are equal to c.  We first use an xor
-     with repeated_c.  This reduces the task to testing whether *any of the
-     four* bytes in longword1 is zero.
-
-     We compute tmp =
-       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
-     That is, we perform the following operations:
-       1. Subtract repeated_one.
-       2. & ~longword1.
-       3. & a mask consisting of 0x80 in every byte.
-     Consider what happens in each byte:
-       - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
-	 and step 3 transforms it into 0x80.  A carry can also be propagated
-	 to more significant bytes.
-       - If a byte of longword1 is nonzero, let its lowest 1 bit be at
-	 position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
-	 the byte ends in a single bit of value 0 and k bits of value 1.
-	 After step 2, the result is just k bits of value 1: 2^k - 1.  After
-	 step 3, the result is 0.  And no carry is produced.
-     So, if longword1 has only non-zero bytes, tmp is zero.
-     Whereas if longword1 has a zero byte, call j the position of the least
-     significant zero byte.  Then the result has a zero at positions 0, ...,
-     j-1 and a 0x80 at position j.  We cannot predict the result at the more
-     significant bytes (positions j+1..3), but it does not matter since we
-     already have a non-zero bit at position 8*j+7.
-
-     So, the test whether any byte in longword1 is zero is equivalent to
-     testing whether tmp is nonzero.  */
-
-  while (n >= sizeof (longword))
-    {
-      longword longword1 = *longword_ptr ^ repeated_c;
-
-      if ((((longword1 - repeated_one) & ~longword1)
-	   & (repeated_one << 7)) != 0)
-	break;
-      longword_ptr++;
-      n -= sizeof (longword);
-    }
-
-  char_ptr = (const unsigned char *) longword_ptr;
-
-  /* At this point, we know that either n < sizeof (longword), or one of the
-     sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
-     machines, we could determine the first such byte without any further
-     memory accesses, just by looking at the tmp result from the last loop
-     iteration.  But this does not work on big-endian machines.  Choose code
-     that works in both cases.  */
-
-  for (; n > 0; --n, ++char_ptr)
-    {
-      if (*char_ptr == c)
-	return (void *) char_ptr;
-    }
-
-  return NULL;
+  if (n == 0)
+    return NULL;
+  char *str = (char *) _str;
+  char *end = (char *) (((uintptr_t) str) + n);
+  if ((uintptr_t) end < (uintptr_t) str)
+    end = (char *) UINTPTR_MAX;
+  char *ret = string_skeleton (str, c, end);
+  return (void *)((uintptr_t) ret < (uintptr_t) end ? ret : NULL);
 }
-#ifdef weak_alias
+
+#ifndef STATIC
 weak_alias (__memchr, memchr)
-#endif
 libc_hidden_builtin_def (memchr)
+#endif
diff --git a/string/strnlen.c b/string/strnlen.c
index 803d78b..a5917de 100644
--- a/string/strnlen.c
+++ b/string/strnlen.c
@@ -1,15 +1,10 @@
-/* Find the length of STRING, but scan at most MAXLEN characters.
-   Copyright (C) 1991-2015 Free Software Foundation, Inc.
-   Contributed by Jakub Jelinek <jakub@redhat.com>.
-
-   Based on strlen written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
+/* Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public License as
-   published by the Free Software Foundation; either version 2.1 of the
-   License, or (at your option) any later version.
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
 
    The GNU C Library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -17,149 +12,28 @@
    Lesser General Public License for more details.
 
    You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; see the file COPYING.LIB.  If
-   not, see <http://www.gnu.org/licenses/>.  */
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
 #include <stdlib.h>
 
-/* Find the length of S, but scan at most MAXLEN characters.  If no
-   '\0' terminator is found in that many characters, return MAXLEN.  */
+#undef strlen
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-#ifdef STRNLEN
-# define __strnlen STRNLEN
-#endif
+#define STATIC
+#define MEMCHR memchr_static
+#include "string/memchr.c"
 
 size_t
-__strnlen (const char *str, size_t maxlen)
+__strnlen (const char *str, size_t n)
 {
-  const char *char_ptr, *end_ptr = str + maxlen;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  if (maxlen == 0)
-    return 0;
-
-  if (__glibc_unlikely (end_ptr < str))
-    end_ptr = (const char *) ~0UL;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      {
-	if (char_ptr > end_ptr)
-	  char_ptr = end_ptr;
-	return char_ptr - str;
-      }
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (longword_ptr < (unsigned long int *) end_ptr)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.  */
-
-      longword = *longword_ptr++;
-
-      if ((longword - lomagic) & himagic)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  char_ptr = cp;
-	  if (cp[0] == 0)
-	    break;
-	  char_ptr = cp + 1;
-	  if (cp[1] == 0)
-	    break;
-	  char_ptr = cp + 2;
-	  if (cp[2] == 0)
-	    break;
-	  char_ptr = cp + 3;
-	  if (cp[3] == 0)
-	    break;
-	  if (sizeof (longword) > 4)
-	    {
-	      char_ptr = cp + 4;
-	      if (cp[4] == 0)
-		break;
-	      char_ptr = cp + 5;
-	      if (cp[5] == 0)
-		break;
-	      char_ptr = cp + 6;
-	      if (cp[6] == 0)
-		break;
-	      char_ptr = cp + 7;
-	      if (cp[7] == 0)
-		break;
-	    }
-	}
-      char_ptr = end_ptr;
-    }
-
-  if (char_ptr > end_ptr)
-    char_ptr = end_ptr;
-  return char_ptr - str;
+  char *ret = MEMCHR (str, 0, n); 
+  return ret ? ret - str : n;
 }
-#ifndef STRNLEN
+
 weak_alias (__strnlen, strnlen)
-#endif
 libc_hidden_def (strnlen)
+

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Wed, May 27, 2015 at 08:01:21AM +0200, Ondřej Bílka wrote:
> Hi,
> 
> As i mentioned improving generic string functions this is my second
> attempt. As lot of functions will be optimized in same way this uses
> generic code flow. Functions will vary just by expression to check and
> how interpret return value.
> 
> Performance gains of using this are from loop unrolling and better
> header that doesn't have to check start byte-by-byte.
> 
> Unrolling migth be excessive but its better to tune it in skeleton than
> try manually and risk introducing errors.
> 
> This implementation would probably be faster than assembly on other
> architectures as this will beat it unless you used hardware specific
> instruction or gcc messes up compilation and generates suboptimal code.
> 
> Comments?
> 

Here is a new version of skeleton. I added a big endian support. This
reminded me that when I first wrote it I wanted to use opperations that
dont cause carry, then forgotten about it. As thats needed only for
first aligned load or always on big endian you need to supply expression
twice. one version shouldn't cause carry propagation.

 	* string/common.h: New file.
 	* string/skeleton.h: Likewise.

diff --git a/string/common.h b/string/common.h
new file mode 100644
index 0000000..481c99f
--- /dev/null
+++ b/string/common.h
@@ -0,0 +1,80 @@
+#include <stdint.h>
+
+static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
+static const unsigned long int add = 127 * (~0UL / 255);
+static const unsigned long int high_bits = 128 * (~0UL / 255);
+
+/* Use vector arithmetic tricks. Idea is to take expression works on
+   unsigned byte and evaluates 0 for nozero byte and nonzero on zero byte.
+   Our expression is ((s - 1) & (~s)) & 128  
+   Now we evaluate this expression on each byte in parallel and on first 
+   nonzero byte our expression will have nonzero value. 
+
+   We need to provide version of expression that doesn't cause carry 
+   propagation and opperations could be done in parallel. However its
+   not needed on little endian architectures as we end on first byte 
+   that succeeds and we don't care that next ones could be corrupted.
+  */
+
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+static __always_inline
+unsigned long int 
+contains_zero (unsigned long int s)
+{
+  return (s - ones) & ~s & high_bits;
+}
+#else
+#define contains_zero contains_zero_nocarry
+#endif
+
+static __always_inline
+unsigned long int 
+contains_zero_nocarry (unsigned long int s)
+{
+  return (((s | high_bits) - ones) ^ high_bits) & ~s & high_bits;
+}
+
+#define LSIZE sizeof (unsigned long int)
+#define CROSS_PAGE(x, n) (((uintptr_t) x) % 4096 > 4096 - n)
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+#define SHIFT_BYTES(x, n) ((x) << (8 * (n)))
+#else
+#define SHIFT_BYTES(x, n) ((x) >> (8 * (n)))
+#endif
+
+static __always_inline
+size_t
+first_nonzero_byte (unsigned long int u)
+{
+#if __BYTE_ORDER == __BIG_ENDIAN
+# ifdef FAST_CLZ
+  return clz (u) / 8;
+# else
+#  ifdef NEED BITWISE
+  u = u | (u >> 1);
+  u = u | (u >> 2);
+  u = u | (u >> 4);
+#  else
+  u = u >> 7;
+#  endif
+  u = u | (u >> 8);
+  u = u | (u >> 16);
+  u = u | (u >> 32);
+#  ifdef NEED_BITWISE
+  u = u & ones;
+#  endif
+  u = u * ones;
+  return 8 - (u >> (8 * LSIZE - 8));
+# endif
+#else
+# ifdef FAST_FFS
+  return (ffsl (u) - 1) / 8;
+# else
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+# endif
+#endif
+}
diff --git a/string/skeleton.h b/string/skeleton.h
new file mode 100644
index 0000000..76bd08f
--- /dev/null
+++ b/string/skeleton.h
@@ -0,0 +1,150 @@
+/* Skeleton of generic string functions.
+   Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+/* On high endian an positive could cause false positive in previous byte.  */
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+#undef EXPRESSION
+#define EXPRESSION(x,y) EXPRESSION_NOCARRY(x,y)
+#endif
+
+static __always_inline
+int
+found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+{
+  const unsigned long int *lptr = (const unsigned long int *) s;
+  unsigned long int mask = EXPRESSION(*lptr, cmask);
+  if (mask)
+    {
+      *result = s + first_nonzero_byte (mask);
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, int c_in, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  char *r;
+  unsigned long int __attribute__ ((unused)) cmask = c * ones;
+
+#if _STRING_ARCH_unaligned
+  /* We fetch 32 bytes while not crossing page boundary. 
+     Most strings in practice are of that size and we avoid a loop.
+     This looks as best in practice, alternative below uses aligned load 
+     but is slower when string starts just few 
+     bytes before 32 byte boundary. A tradeoff is that we rarely could 
+     fetch extra cache line without needing it but this optimization 
+     does pay for that. */
+  if (!CROSS_PAGE(s, 32))
+    {
+      if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s + 5 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 6 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 7 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 8 * LSIZE, cmask, &r))
+            return r;
+        }
+
+      if (BOUND (s + 32))
+        return NULL;
+    }
+  else
+    {
+#endif
+  /* We need use aligned loads. For first load we read some bytes before 
+     start that we discard by shifting them down. */
+ 
+      char *s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      /* We need be careful here as bytes before start can corrupt it.  */
+      mask = SHIFT_BYTES ((EXPRESSION_NOCARRY (*lptr, cmask)), s - s_aligned);
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      if (BOUND (s_aligned + 1 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 1 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 2 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 2 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 3 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 3 * LSIZE, cmask, &r))
+        return r;
+#if _STRING_ARCH_unaligned
+    }
+#endif
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s_loop = PTR_ALIGN_DOWN (s, 4 * LSIZE);
+  while (!BOUND (s_loop + 4 * LSIZE))
+    {
+      s_loop += 4 * LSIZE;
+      lptr = (const unsigned long int *) (s_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s_loop + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 2 * LSIZE, cmask, &r))
+            return r;
+
+          return s_loop + 3 * LSIZE + first_nonzero_byte (mask);
+        }
+    }
+ return NULL;
+}

Re: [PATCH 2/* v3] Optimize generic strchrnul and strchr

[Ondřej Bílka]

On Wed, May 27, 2015 at 11:11:48AM +0200, Ondřej Bílka wrote:
> On Wed, May 27, 2015 at 08:35:44AM +0200, Ondřej Bílka wrote:
> > This is my generic strchr algorithm resubmitted to use skeleton.
> > 
> > Idea to split into cases c<128 and c>128 didn't change.
> > 
> > So comments? How this perform on different architectures?
> > 
> This also needed to change as I used older strchr wrapper. Here is
> correct one.
> 
And here is updated version with better expression and big endian
support.

  	* string/strchr.c: Use skeleton.
  	* string/strchrnul.c: Likewise.

diff --git a/string/strchr.c b/string/strchr.c
index 5f90075..e7c2e4c 100644
--- a/string/strchr.c
+++ b/string/strchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,166 +16,21 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
-
 #undef strchr
+#undef index
+
+#define AS_STRCHR
+#define STRCHRNUL strchrnul_static
+#include "string/strchrnul.c"
+
 
-/* Find the first occurrence of C in S.  */
 char *
 strchr (const char *s, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-    else if (*char_ptr == '\0')
-      return NULL;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	    }
-	}
-    }
-
-  return NULL;
+  unsigned char c = (unsigned char) c_in;
+  unsigned char *r = (unsigned char *) STRCHRNUL (s, c);
+  return (*r == c) ? (char *) r : NULL;
 }
 
-#ifdef weak_alias
-#undef index
 weak_alias (strchr, index)
-#endif
 libc_hidden_builtin_def (strchr)
diff --git a/string/strchrnul.c b/string/strchrnul.c
index 2678f1d..e1aebf4 100644
--- a/string/strchrnul.c
+++ b/string/strchrnul.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,153 +16,69 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 #include <stdlib.h>
 
-#undef __strchrnul
 #undef strchrnul
+#undef __strchrnul
 
-#ifndef STRCHRNUL
-# define STRCHRNUL __strchrnul
-#endif
-
-/* Find the first occurrence of C in S or the final NUL byte.  */
-char *
-STRCHRNUL (s, c_in)
-     const char *s;
-     int c_in;
-{
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c || *char_ptr == '\0')
-      return (void *) char_ptr;
+/* Here idea is still use the result of expression
+   contains_zero (*p) | contains_zero (*p ^ cmask)
+   but we can optimize it by using commutativity of operations.  */
 
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
+#include "string/common.h"
+#define EXPRESSION(s, cmask) ((((s) - ones) | (((s) ^ cmask) - ones)) \
+			      & high_bits & (~s))
 
-  longword_ptr = (unsigned long int *) char_ptr;
+/* TODO simplify.  */
+#define EXPRESSION_NOCARRY(s, cmask) contains_zero_nocarry (s) \
+				     | contains_zero_nocarry (s ^ cmask)
 
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
 
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
+#include "string/skeleton.h"
 
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
+#ifndef STRCHRNUL
+# define STRCHRNUL __strchrnul
+#endif
 
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
+#ifdef AS_STRCHR
+static __always_inline
+#endif
+char *
+STRCHRNUL (const char *s_in, int c_in)
+{
+  char *s_aligned;
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  unsigned long int cmask = c * ones;
+  if (__glibc_unlikely (c > 127))
     {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	    }
-	}
+      s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = SHIFT_BYTES (contains_zero_nocarry (*lptr)
+                          | contains_zero_nocarry (*lptr ^ cmask),
+                          s - s_aligned);
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      while (1)
+        {
+          s_aligned += LSIZE;
+          lptr = (const unsigned long int *) s_aligned;
+          mask = contains_zero(*lptr) | contains_zero (*lptr ^ cmask);
+          if (mask)
+            return s_aligned + first_nonzero_byte (mask);
+        }
     }
-
-  /* This should never happen.  */
-  return NULL;
+  else
+    return string_skeleton (s, c, 0);
 }
 
+#ifndef AS_STRCHR
 weak_alias (__strchrnul, strchrnul)
+#endif

Re: [PATCH 3/* v2] Generic string strlen and rawmemchr

[Ondřej Bílka]

On Wed, May 27, 2015 at 11:18:58AM +0200, Ondřej Bílka wrote:
> With strlen and rawmemchr I use same idea.
> 
> As one could get rawmemchr with strlen by first xoring input and
> strlen from rawmemchr by letting gcc optimize rawmemchr(x,0) these
> belong together. I keep them separate now but it could change if you
> want it.
>
Again resending with added big endian expression. 

  	* string/strlen.c: Use skeleton.
  	* string/rawmemchr.c: Likewise.

diff --git a/string/rawmemchr.c b/string/rawmemchr.c
index 05b22be..aa6fc06 100644
--- a/string/rawmemchr.c
+++ b/string/rawmemchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,166 +15,25 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
+#include <string.h>
+#include <stdlib.h>
 
-#undef __ptr_t
-#define __ptr_t void *
+#undef rawmemchr
+#undef __rawmemchr
 
-#if defined (_LIBC)
-# include <string.h>
-# include <memcopy.h>
-# include <stdlib.h>
-#endif
 
-#if defined (HAVE_LIMITS_H) || defined (_LIBC)
-# include <limits.h>
-#endif
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#define EXPRESSION_NOCARRY(p, c) (contains_zero_nocarry (p ^ c))
 
-#define LONG_MAX_32_BITS 2147483647
+#include "string/skeleton.h"
 
-#ifndef LONG_MAX
-#define LONG_MAX LONG_MAX_32_BITS
-#endif
-
-#include <sys/types.h>
-
-#undef memchr
-
-#ifndef RAWMEMCHR
-# define RAWMEMCHR __rawmemchr
-#endif
-
-/* Find the first occurrence of C in S.  */
-__ptr_t
-RAWMEMCHR (s, c_in)
-     const __ptr_t s;
-     int c_in;
+void *
+__rawmemchr (const void *s, int c)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (__ptr_t) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-
-  if (sizeof (longword) != 4 && sizeof (longword) != 8)
-    abort ();
-
-#if LONG_MAX <= LONG_MAX_32_BITS
-  magic_bits = 0x7efefeff;
-#else
-  magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
-#endif
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-#if LONG_MAX > LONG_MAX_32_BITS
-  charmask |= charmask << 32;
-#endif
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (1)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C, not zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++ ^ charmask;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (cp[0] == c)
-	    return (__ptr_t) cp;
-	  if (cp[1] == c)
-	    return (__ptr_t) &cp[1];
-	  if (cp[2] == c)
-	    return (__ptr_t) &cp[2];
-	  if (cp[3] == c)
-	    return (__ptr_t) &cp[3];
-#if LONG_MAX > 2147483647
-	  if (cp[4] == c)
-	    return (__ptr_t) &cp[4];
-	  if (cp[5] == c)
-	    return (__ptr_t) &cp[5];
-	  if (cp[6] == c)
-	    return (__ptr_t) &cp[6];
-	  if (cp[7] == c)
-	    return (__ptr_t) &cp[7];
-#endif
-	}
-    }
+  return (void *) string_skeleton (s, c, NULL);
 }
+
 libc_hidden_def (__rawmemchr)
 weak_alias (__rawmemchr, rawmemchr)
+
diff --git a/string/strlen.c b/string/strlen.c
index d066bde..621196c 100644
--- a/string/strlen.c
+++ b/string/strlen.c
@@ -1,8 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -25,81 +22,16 @@
 
 /* Return the length of the null-terminated string STR.  Scan for
    the null terminator quickly by testing four bytes at a time.  */
+
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p))
+#define EXPRESSION_NOCARRY(p, c) (contains_zero_nocarry (p))
+#include "string/skeleton.h"
+
 size_t
 strlen (const char *str)
 {
-  const char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      return char_ptr - str;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      longword = *longword_ptr++;
-
-      if (((longword - lomagic) & ~longword & himagic) != 0)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  if (cp[0] == 0)
-	    return cp - str;
-	  if (cp[1] == 0)
-	    return cp - str + 1;
-	  if (cp[2] == 0)
-	    return cp - str + 2;
-	  if (cp[3] == 0)
-	    return cp - str + 3;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (cp[4] == 0)
-		return cp - str + 4;
-	      if (cp[5] == 0)
-		return cp - str + 5;
-	      if (cp[6] == 0)
-		return cp - str + 6;
-	      if (cp[7] == 0)
-		return cp - str + 7;
-	    }
-	}
-    }
+  return string_skeleton (str, 0, 0) - str;
 }
+
 libc_hidden_builtin_def (strlen)

Re: [PATCH 4/* v2] Generic string memchr and strnlen

[Ondřej Bílka]

On Wed, May 27, 2015 at 01:42:01PM +0200, Ondřej Bílka wrote:
> Here we first deal with functions that use size bound.
> Main technical complication is pointer wraparound for large n so it
> needs to be handled accordingly. Otherwise its almost same as rawmemchr.
> 
> As I wrote before that we could optimize  memchr(x,0,n) to strnlen
> opposite is also true. Here strnlen uses memchr and lets gcc simply
> that.
> 
> Comments?
> 
Again added big endian.

 	* string/memchr.c: Use skeleton.
 	* string/strnlen.c: Likewise.


diff --git a/string/memchr.c b/string/memchr.c
index 6896465..42a6c27 100644
--- a/string/memchr.c
+++ b/string/memchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,143 +15,43 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifndef _LIBC
-# include <config.h>
-#endif
-
 #include <string.h>
+#include <stdlib.h>
 
-#include <stddef.h>
+#undef __memchr
+#undef memchr
 
-#include <limits.h>
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-#undef __memchr
-#ifdef _LIBC
-# undef memchr
-#endif
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#define EXPRESSION_NOCARRY(p, c) (contains_zero_nocarry (p ^ c))
 
-#ifndef weak_alias
-# define __memchr memchr
-#endif
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
+#include "string/skeleton.h"
 
 #ifndef MEMCHR
 # define MEMCHR __memchr
 #endif
 
-/* Search no more than N bytes of S for C.  */
+#ifdef STATIC
+static __always_inline
+#endif
 void *
-MEMCHR (void const *s, int c_in, size_t n)
+MEMCHR (const void *_str, int c, size_t n)
 {
-  /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
-     long instead of a 64-bit uintmax_t tends to give better
-     performance.  On 64-bit hardware, unsigned long is generally 64
-     bits already.  Change this typedef to experiment with
-     performance.  */
-  typedef unsigned long int longword;
-
-  const unsigned char *char_ptr;
-  const longword *longword_ptr;
-  longword repeated_one;
-  longword repeated_c;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few bytes by reading one byte at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
-       --n, ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-
-  longword_ptr = (const longword *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to any size longwords.  */
-
-  /* Compute auxiliary longword values:
-     repeated_one is a value which has a 1 in every byte.
-     repeated_c has c in every byte.  */
-  repeated_one = 0x01010101;
-  repeated_c = c | (c << 8);
-  repeated_c |= repeated_c << 16;
-  if (0xffffffffU < (longword) -1)
-    {
-      repeated_one |= repeated_one << 31 << 1;
-      repeated_c |= repeated_c << 31 << 1;
-      if (8 < sizeof (longword))
-	{
-	  size_t i;
-
-	  for (i = 64; i < sizeof (longword) * 8; i *= 2)
-	    {
-	      repeated_one |= repeated_one << i;
-	      repeated_c |= repeated_c << i;
-	    }
-	}
-    }
-
-  /* Instead of the traditional loop which tests each byte, we will test a
-     longword at a time.  The tricky part is testing if *any of the four*
-     bytes in the longword in question are equal to c.  We first use an xor
-     with repeated_c.  This reduces the task to testing whether *any of the
-     four* bytes in longword1 is zero.
-
-     We compute tmp =
-       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
-     That is, we perform the following operations:
-       1. Subtract repeated_one.
-       2. & ~longword1.
-       3. & a mask consisting of 0x80 in every byte.
-     Consider what happens in each byte:
-       - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
-	 and step 3 transforms it into 0x80.  A carry can also be propagated
-	 to more significant bytes.
-       - If a byte of longword1 is nonzero, let its lowest 1 bit be at
-	 position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
-	 the byte ends in a single bit of value 0 and k bits of value 1.
-	 After step 2, the result is just k bits of value 1: 2^k - 1.  After
-	 step 3, the result is 0.  And no carry is produced.
-     So, if longword1 has only non-zero bytes, tmp is zero.
-     Whereas if longword1 has a zero byte, call j the position of the least
-     significant zero byte.  Then the result has a zero at positions 0, ...,
-     j-1 and a 0x80 at position j.  We cannot predict the result at the more
-     significant bytes (positions j+1..3), but it does not matter since we
-     already have a non-zero bit at position 8*j+7.
-
-     So, the test whether any byte in longword1 is zero is equivalent to
-     testing whether tmp is nonzero.  */
-
-  while (n >= sizeof (longword))
-    {
-      longword longword1 = *longword_ptr ^ repeated_c;
-
-      if ((((longword1 - repeated_one) & ~longword1)
-	   & (repeated_one << 7)) != 0)
-	break;
-      longword_ptr++;
-      n -= sizeof (longword);
-    }
-
-  char_ptr = (const unsigned char *) longword_ptr;
-
-  /* At this point, we know that either n < sizeof (longword), or one of the
-     sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
-     machines, we could determine the first such byte without any further
-     memory accesses, just by looking at the tmp result from the last loop
-     iteration.  But this does not work on big-endian machines.  Choose code
-     that works in both cases.  */
-
-  for (; n > 0; --n, ++char_ptr)
-    {
-      if (*char_ptr == c)
-	return (void *) char_ptr;
-    }
-
-  return NULL;
+  if (n == 0)
+    return NULL;
+  char *str = (char *) _str;
+  char *end = (char *) (((uintptr_t) str) + n);
+  if ((uintptr_t) end < (uintptr_t) str)
+    end = (char *) UINTPTR_MAX;
+  char *ret = string_skeleton (str, c, end);
+  return (void *)((uintptr_t) ret < (uintptr_t) end ? ret : NULL);
 }
-#ifdef weak_alias
+
+#ifndef STATIC
 weak_alias (__memchr, memchr)
-#endif
 libc_hidden_builtin_def (memchr)
+#endif
diff --git a/string/strnlen.c b/string/strnlen.c
index 803d78b..9a71e4d 100644
--- a/string/strnlen.c
+++ b/string/strnlen.c
@@ -1,15 +1,10 @@
-/* Find the length of STRING, but scan at most MAXLEN characters.
-   Copyright (C) 1991-2015 Free Software Foundation, Inc.
-   Contributed by Jakub Jelinek <jakub@redhat.com>.
-
-   Based on strlen written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
+/* Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public License as
-   published by the Free Software Foundation; either version 2.1 of the
-   License, or (at your option) any later version.
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
 
    The GNU C Library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -17,149 +12,27 @@
    Lesser General Public License for more details.
 
    You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; see the file COPYING.LIB.  If
-   not, see <http://www.gnu.org/licenses/>.  */
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
 #include <stdlib.h>
 
-/* Find the length of S, but scan at most MAXLEN characters.  If no
-   '\0' terminator is found in that many characters, return MAXLEN.  */
+#undef strlen
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-#ifdef STRNLEN
-# define __strnlen STRNLEN
-#endif
+#define STATIC
+#define MEMCHR memchr_static
+#include "string/memchr.c"
 
 size_t
-__strnlen (const char *str, size_t maxlen)
+__strnlen (const char *str, size_t n)
 {
-  const char *char_ptr, *end_ptr = str + maxlen;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  if (maxlen == 0)
-    return 0;
-
-  if (__glibc_unlikely (end_ptr < str))
-    end_ptr = (const char *) ~0UL;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      {
-	if (char_ptr > end_ptr)
-	  char_ptr = end_ptr;
-	return char_ptr - str;
-      }
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (longword_ptr < (unsigned long int *) end_ptr)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.  */
-
-      longword = *longword_ptr++;
-
-      if ((longword - lomagic) & himagic)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  char_ptr = cp;
-	  if (cp[0] == 0)
-	    break;
-	  char_ptr = cp + 1;
-	  if (cp[1] == 0)
-	    break;
-	  char_ptr = cp + 2;
-	  if (cp[2] == 0)
-	    break;
-	  char_ptr = cp + 3;
-	  if (cp[3] == 0)
-	    break;
-	  if (sizeof (longword) > 4)
-	    {
-	      char_ptr = cp + 4;
-	      if (cp[4] == 0)
-		break;
-	      char_ptr = cp + 5;
-	      if (cp[5] == 0)
-		break;
-	      char_ptr = cp + 6;
-	      if (cp[6] == 0)
-		break;
-	      char_ptr = cp + 7;
-	      if (cp[7] == 0)
-		break;
-	    }
-	}
-      char_ptr = end_ptr;
-    }
-
-  if (char_ptr > end_ptr)
-    char_ptr = end_ptr;
-  return char_ptr - str;
+  char *ret = MEMCHR (str, 0, n);
+  return ret ? ret - str : n;
 }
-#ifndef STRNLEN
+
 weak_alias (__strnlen, strnlen)
-#endif
 libc_hidden_def (strnlen)

[PATCH 5/*] Generic string function optimization: strcmp and strncmp

[Ondřej Bílka]

This adds a platform generic optimization of strcmp and strncmp.
I adapted a x64 skeleton from strcmp. I correctly added end checks which 
I didn't do before so I will also send optimized strncmp.

 	* string/diff_skeleton.h: New file.
 	* string/strcmp.c: Use diff skeleton.
	* string/strncmp.c: Likewise. 

diff --git a/string/diff_skeleton.h b/string/diff_skeleton.h
new file mode 100644
index 0000000..a2cdccc
--- /dev/null
+++ b/string/diff_skeleton.h
@@ -0,0 +1,181 @@
+/* Skeleton of *cmp string functions.
+   Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+
+static __always_inline
+int
+found_in_long_bytes(char *s1, char *s2, char **r1, char **r2)
+{
+  const unsigned long int *lptr1 = (const unsigned long int *) s1;
+  const unsigned long int *lptr2 = (const unsigned long int *) s2;
+
+  unsigned long int mask = EXPRESSION(*lptr1, *lptr2);
+  if (mask)
+    {
+      size_t found = first_nonzero_byte (mask);
+      *r1 = s1 + found;
+      *r2 = s2 + found;
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+int
+diff_skeleton (char **p1, char **p2, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr1, *lptr2;
+  char *s1 = *p1, *s2 = *p2;
+
+
+#if _STRING_ARCH_unaligned == 0
+  /* We don't optimize for architectures without aligned load yet.
+     Problem is that header is hot and you need different tricks 
+     with aligned load. However loop would be relatively easy by 
+     emulating loads with mix of byte shifts. */
+
+  size_t i = byte_loop(s1, s2, SIZE_MAX, end);
+  *p1 = s1 + i;
+  *p2 = s2 + i;
+  return i != SIZE_MAX;
+#endif
+
+  /* We fetch 32 bytes while not crossing page boundary. 
+     Most strings in practice are of that size and we avoid a loop.
+     This looks as best in practice, alternative below uses aligned load 
+     but is slower when string starts just few 
+     bytes before 32 byte boundary. A tradeoff is that we rarely could 
+     fetch extra cache line without needing it but this optimization 
+     does pay for that. */
+  if (!CROSS_PAGE (s1, 32) && !CROSS_PAGE (s2, 32))
+    {
+      if (found_in_long_bytes (s1 + 0 * LSIZE, s2 + 0 * LSIZE, p1, p2))
+        return 1;
+      if (found_in_long_bytes (s1 + 1 * LSIZE, s2 + 1 * LSIZE, p1, p2))
+        return 1;
+      if (found_in_long_bytes (s1 + 2 * LSIZE, s2 + 2 * LSIZE, p1, p2))
+        return 1;
+      if (found_in_long_bytes (s1 + 3 * LSIZE, s2 + 3 * LSIZE, p1, p2))
+        return 1;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s1 + 4 * LSIZE, s2 + 4 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1 + 5 * LSIZE, s2 + 5 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1 + 6 * LSIZE, s2 + 6 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1 + 7 * LSIZE, s2 + 7 * LSIZE, p1, p2))
+            return 1;
+        }
+
+      if (BOUND (s1 + 32))
+        return 0;
+    }
+  else
+    {
+      size_t i = byte_loop(s1, s2, 32, end);
+
+      if (i==SIZE_MAX)
+        return 0;
+
+      if (i < 32)
+        {
+          *p1 = s1 + i;
+	  *p2 = s2 + i;
+          return 1;
+        }    
+    }
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s1_loop = PTR_ALIGN_DOWN (s1, 4 * LSIZE);
+  char *s2_loop = s2 - (s1 - s1_loop);
+  int until_cross_page = (4096 - (((uintptr_t) (s2_loop + 4 * LSIZE)) % 4096))\
+                         / (4 * LSIZE);
+
+#ifdef COALIGN_HELP
+  if (((uintptr_t)s2_loop)%32==0)
+    until_cross_page = 1000000;
+#endif
+  while (!BOUND (s1_loop + 4 * LSIZE))
+    {
+      s1_loop += 4 * LSIZE;
+      s2_loop += 4 * LSIZE;
+
+
+      if (until_cross_page == 0)
+        {
+          uintptr_t shift = ((uintptr_t) s2_loop) % (4 * LSIZE);
+          if (found_in_long_bytes (s1_loop - shift + 0 * LSIZE, 
+                                   s2_loop - shift + 0 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop - shift + 1 * LSIZE, 
+                                   s2_loop - shift + 1 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop - shift + 2 * LSIZE, 
+                                   s2_loop - shift + 2 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop - shift + 3 * LSIZE, 
+                                   s2_loop - shift + 3 * LSIZE, p1, p2))
+            return 1;
+
+          until_cross_page = 4096 / (4 * LSIZE);
+          if (BOUND (s1_loop + 4 * LSIZE - shift))
+            return 0;
+        }
+
+      until_cross_page--;
+
+      lptr1 = (const unsigned long int *) (s1_loop + 0 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr1, *lptr2);
+      lptr1 = (const unsigned long int *) (s1_loop + 1 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr1, *lptr2);
+      lptr1 = (const unsigned long int *) (s1_loop + 2 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr1, *lptr2);
+      lptr1 = (const unsigned long int *) (s1_loop + 3 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr1, *lptr2);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s1_loop + 0 * LSIZE, s2_loop + 0 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop + 1 * LSIZE, s2_loop + 1 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop + 2 * LSIZE, s2_loop + 2 * LSIZE, p1, p2))
+            return 1;
+
+          found_in_long_bytes (s1_loop + 3 * LSIZE, s2_loop + 3 * LSIZE, p1, p2);
+          return 1;
+        }
+    }
+ return 0;
+}
diff --git a/string/strcmp.c b/string/strcmp.c
index 4d4c044..c1d4c22 100644
--- a/string/strcmp.c
+++ b/string/strcmp.c
@@ -16,28 +16,37 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-
 #undef strcmp
 
 /* 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.  */
+
+#include "string/common.h"
+#define EXPRESSION(c1, c2) (c1 ^ c2) | contains_zero (c2)
+
+static __always_inline
+size_t 
+byte_loop(char *x, char *y, size_t n, char *end)
+{
+  size_t i;
+  for (i = 0; i < n; i++)
+    if (x[i] == '\0' || x[i] != y[i])
+      return i;
+
+  return n;
+}
+
+#include "string/diff_skeleton.h"
+
 int
-strcmp (const char *p1, const char *p2)
+strcmp (const char *s1_start, const char *s2_start)
 {
-  const unsigned char *s1 = (const unsigned char *) p1;
-  const unsigned char *s2 = (const unsigned char *) p2;
-  unsigned char c1, c2;
-
-  do
-    {
-      c1 = (unsigned char) *s1++;
-      c2 = (unsigned char) *s2++;
-      if (c1 == '\0')
-	return c1 - c2;
-    }
-  while (c1 == c2);
-
-  return c1 - c2;
+  unsigned char *p1 = (unsigned char *) s1_start;
+  unsigned char *p2 = (unsigned char *) s2_start;
+
+  diff_skeleton ((char **) &p1, (char **) &p2, NULL); 
+
+  return *p1 - *p2;
 }
 libc_hidden_builtin_def (strcmp)
diff --git a/string/strncmp.c b/string/strncmp.c
index 2a1137a..4c4e9f7 100644
--- a/string/strncmp.c
+++ b/string/strncmp.c
@@ -16,59 +16,55 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 
 #undef strncmp
 
-#ifndef STRNCMP
-#define STRNCMP strncmp
-#endif
+/* 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.  */
 
-/* Compare no more than N characters of 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
-STRNCMP (const char *s1, const char *s2, size_t n)
-{
-  unsigned char c1 = '\0';
-  unsigned char c2 = '\0';
+#include "string/common.h"
+#define EXPRESSION(c1, c2) (c1 ^ c2) | contains_zero (c2)
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
 
-  if (n >= 4)
+static __always_inline
+size_t 
+byte_loop(char *x, char *y, size_t c, char *end)
+{
+  size_t i;
+  for (i = 0; i < c; i++)
     {
-      size_t n4 = n >> 2;
-      do
-	{
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	} while (--n4 > 0);
-      n &= 3;
+      if (x + i == end)
+        return SIZE_MAX;
+      if (x[i] == '\0' || x[i] != y[i])
+        return i;
     }
 
-  while (n > 0)
+  return c;
+}
+
+#include "string/diff_skeleton.h"
+
+int
+strncmp (const char *s1_start, const char *s2_start, size_t n)
+{
+  unsigned char *p1 = (unsigned char *) s1_start;
+  unsigned char *p2 = (unsigned char *) s2_start;
+  char *end = (char *) (((uintptr_t) p1) + n);
+  if ((uintptr_t) end <= (uintptr_t) p1)
     {
-      c1 = (unsigned char) *s1++;
-      c2 = (unsigned char) *s2++;
-      if (c1 == '\0' || c1 != c2)
-	return c1 - c2;
-      n--;
+      if (n == 0)
+        return 0;
+      end = (char *) UINTPTR_MAX;
     }
 
-  return c1 - c2;
-}
+  if (!diff_skeleton ((char **) &p1, (char **) &p2, end))
+    return 0;
 
-libc_hidden_builtin_def (STRNCMP)
+  if (BOUND (p1))
+    return 0;
+
+
+  return *p1 - *p2;
+}
+libc_hidden_builtin_def (strncmp)

[PATCH 6/*] Generic string function optimization: strcasestr

[Ondřej Bílka]

Hi,

Here I made wrong assumption for long time that prevented me to see
optimization in strcasestr. Now I realized that looking for leading pair
would likely work. I though that it would be necessary to construct
table that assigns to each characters list of characters in same
equivalence class.

I don't have to do that if like in strchr will check if its ascii. Then
I could approximate toupper(x) = toupper(c) by expression 
(x == toupper (c)) | (x == tolower (c)) | (x > 128)
which is easily evaluable in parallel, then and it with shifted
expression for second character.

I added it now just as simple heuristic, a more buy-or-rent approach
will follow in next patch.

I also needed to remove test/bench-strcasestr as I need locale check for
ascii-compatibility of towlower map.

Comments?

	* benchtests/bench-strcasestr.c: Remove simple_strcasestr.
	* string/test-strcasestr.c: Likewise.
	* string/skeleton.h: Customize cmask parameter with CMASK_PARAM macro
	* string/strcasestr.c: Optimize by fast search of leading digraph.

diff --git a/benchtests/bench-strcasestr.c b/benchtests/bench-strcasestr.c
index 33531a4..6c6309f 100644
--- a/benchtests/bench-strcasestr.c
+++ b/benchtests/bench-strcasestr.c
@@ -21,10 +21,6 @@
 #include "bench-string.h"
 
 
-#define STRCASESTR simple_strcasestr
-#define NO_ALIAS
-#define __strncasecmp strncasecmp
-#include "../string/strcasestr.c"
 
 
 static char *
@@ -53,7 +49,6 @@ stupid_strcasestr (const char *s1, const char *s2)
 typedef char *(*proto_t) (const char *, const char *);
 
 IMPL (stupid_strcasestr, 0)
-IMPL (simple_strcasestr, 0)
 IMPL (strcasestr, 1)
 
 
diff --git a/string/skeleton.h b/string/skeleton.h
index 26f2d9f..74d4b9f 100644
--- a/string/skeleton.h
+++ b/string/skeleton.h
@@ -31,9 +31,17 @@
 #define EXPRESSION(x,y) EXPRESSION_NOCARRY(x,y)
 #endif
 
+#ifdef CUSTOM_CMASK
+#define CMASK_PARAM_MASK CMASK_PARAM
+#else
+#define CMASK_PARAM int c_in
+#define CMASK_PARAM_MASK unsigned long int cmask
+#endif
+
+
 static __always_inline
 int
-found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+found_in_long_bytes(char *s, CMASK_PARAM_MASK, char **result)
 {
   const unsigned long int *lptr = (const unsigned long int *) s;
   unsigned long int mask = EXPRESSION(*lptr, cmask);
@@ -46,16 +54,21 @@ found_in_long_bytes(char *s, unsigned long int cmask, char **result)
     return 0;
 }
 
+
+
+
 static __always_inline
 char *
-string_skeleton (const char *s_in, int c_in, char *end)
+string_skeleton (const char *s_in, CMASK_PARAM, char *end)
 {
   unsigned long int mask;
   const unsigned long int *lptr;
   char *s = (char *) s_in;
-  unsigned char c = (unsigned char) c_in;
   char *r;
+#ifndef CUSTOM_CMASK
+  unsigned char c = (unsigned char) c_in;
   unsigned long int __attribute__ ((unused)) cmask = c * ones;
+#endif
 
 #if _STRING_ARCH_unaligned
   /* We fetch 32 bytes while not crossing page boundary. 
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 400fab8..7c984c8 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -57,6 +57,37 @@
 #define STRCASESTR __strcasestr
 #endif
 
+#include "string/common.h"
+
+struct cmask
+{
+  unsigned long int l0, u0, l1, u1;
+};
+#define CUSTOM_CMASK
+#define CMASK_PARAM struct cmask cmask
+
+#define EXPRESSION(x, cmask) (\
+ ( contains_zero ((x >> 8) ^ cmask.l0) \
+   | contains_zero ((x >> 8) ^ cmask.u0) \
+   | (x >> 8)) \
+   | (1UL << (8 * LSIZE - 1)) \
+ & (contains_zero (x ^ cmask.l1) \
+    | contains_zero (x ^ cmask.l1) \
+    | x))
+#define EXPRESSION_NOCARRY(x,cmask) (\
+ ( contains_zero_nocarry ((x >> 8) ^ cmask.l0) \
+   | contains_zero_nocarry ((x >> 8) ^ cmask.u0) \
+   | (x >> 8)) \
+   | (1UL << (8 * LSIZE - 1)) \
+ & (contains_zero_nocarry (x ^ cmask.l1) \
+    | contains_zero_nocarry (x ^ cmask.l1) \
+    | x))
+
+#include "string/skeleton.h"
+
+#include "../locale/localeinfo.h"
+
+
 
 /* Find the first occurrence of NEEDLE in HAYSTACK, using
    case-insensitive comparison.  This function gives unspecified
@@ -70,6 +101,23 @@ STRCASESTR (const char *haystack_start, const char *needle_start)
   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
   bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
 
+  __locale_t loc = _NL_CURRENT_LOCALE;
+  struct __locale_data *ctype = loc->__locales[LC_CTYPE];
+  int nonascii = ctype->values[_NL_ITEM_INDEX (_NL_CTYPE_NONASCII_CASE)].word;
+
+  unsigned char *n = (unsigned char *) needle;  
+  if (!nonascii && haystack[0] != 0 && n[0] != 0 && n[0] < 128 
+                                    && n[1] != 0 && n[1] < 128)
+    {
+      struct cmask cmask;
+      cmask.l0 = tolower (n[0]) * ones;
+      cmask.u0 = toupper (n[0]) * ones;
+      cmask.l1 = tolower (n[1]) * ones;
+      cmask.u1 = toupper (n[1]) * ones;
+      haystack = string_skeleton (haystack + 1, cmask, NULL) - 1;
+    }
+
+
   /* Determine length of NEEDLE, and in the process, make sure
      HAYSTACK is at least as long (no point processing all of a long
      NEEDLE if HAYSTACK is too short).  */
diff --git a/string/test-strcasestr.c b/string/test-strcasestr.c
index 489dc84..3c01881 100644
--- a/string/test-strcasestr.c
+++ b/string/test-strcasestr.c
@@ -25,7 +25,6 @@
 #define STRCASESTR simple_strcasestr
 #define NO_ALIAS
 #define __strncasecmp strncasecmp
-#include "strcasestr.c"
 
 
 static char *
@@ -54,7 +53,6 @@ stupid_strcasestr (const char *s1, const char *s2)
 typedef char *(*proto_t) (const char *, const char *);
 
 IMPL (stupid_strcasestr, 0)
-IMPL (simple_strcasestr, 0)
 IMPL (strcasestr, 1)
 
 

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Richard Henderson]

On 05/28/2015 07:29 AM, Ondřej Bílka wrote:
> Here is a new version of skeleton. I added a big endian support. This
> reminded me that when I first wrote it I wanted to use opperations that
> dont cause carry, then forgotten about it. As thats needed only for
> first aligned load or always on big endian you need to supply expression
> twice. one version shouldn't cause carry propagation.
>
>   	* string/common.h: New file.
>   	* string/skeleton.h: Likewise.

I like the idea of this common header for implementing these algorithms. 
Though I'd like to see it not placed in string/, but sysdeps/generic/, so that 
one can provide specialized versions for different targets.

> +static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
> +static const unsigned long int add = 127 * (~0UL / 255);
> +static const unsigned long int high_bits = 128 * (~0UL / 255);

We're still using C, not C++.  These are objects requiring static allocation, 
not abstract constants.  Please just use #defines.

> +static __always_inline
> +unsigned long int
> +contains_zero (unsigned long int s)
> +{
> +  return (s - ones) & ~s & high_bits;
> +}

On Alpha or PPC, the target-specific header could use cmpbge or cmpb insns 
respectively.

On armv6t2/armv7, this can be done with the vector saturating addition, uqadd8, 
by adding 0xfe and then inverting.  Of course, this works on other targets for 
which vector insns exist, but on arm uqadd8 works on normal integer registers.

> +#define CROSS_PAGE(x, n) (((uintptr_t) x) % 4096 > 4096 - n)

Certainly different targets would like to override the minimal page size.

> +# ifdef FAST_FFS
> +  return (ffsl (u) - 1) / 8;
> +# else

Why are you stuck on ffs instead of ctz?  The later avoids all the -1 adjustments.

> +    }
> +  else
> +    {
> +#endif
...
> +#if _STRING_ARCH_unaligned
> +    }
> +#endif

Better placement of the first #endif means you don't need the second.


r~

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Thu, May 28, 2015 at 10:48:29AM -0700, Richard Henderson wrote:
> On 05/28/2015 07:29 AM, Ondřej Bílka wrote:
> >Here is a new version of skeleton. I added a big endian support. This
> >reminded me that when I first wrote it I wanted to use opperations that
> >dont cause carry, then forgotten about it. As thats needed only for
> >first aligned load or always on big endian you need to supply expression
> >twice. one version shouldn't cause carry propagation.
> >
> >  	* string/common.h: New file.
> >  	* string/skeleton.h: Likewise.
> 
> I like the idea of this common header for implementing these
> algorithms. Though I'd like to see it not placed in string/, but
> sysdeps/generic/, so that one can provide specialized versions for
> different targets.
>
Will do.

> >+static __always_inline
> >+unsigned long int
> >+contains_zero (unsigned long int s)
> >+{
> >+  return (s - ones) & ~s & high_bits;
> >+}
> 
> On Alpha or PPC, the target-specific header could use cmpbge or cmpb
> insns respectively.
> 
> On armv6t2/armv7, this can be done with the vector saturating
> addition, uqadd8, by adding 0xfe and then inverting.  Of course,
> this works on other targets for which vector insns exist, but on arm
> uqadd8 works on normal integer registers.
> 
> >+# ifdef FAST_FFS
> >+  return (ffsl (u) - 1) / 8;
> >+# else
> 
> Why are you stuck on ffs instead of ctz?  The later avoids all the -1 adjustments.
>
Both comments are correct. We should do it generically and surround
these functions with ifdef to supply arch-specific versions. 

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Joseph Myers]

[-- Attachment #1: Type: text/plain, Size: 511 bytes --]

On Thu, 28 May 2015, Ondřej Bílka wrote:

> Both comments are correct. We should do it generically and surround
> these functions with ifdef to supply arch-specific versions. 

#if, not #ifdef, please, for all architecture choices in these functions.  
The sysdeps/generic version of the header architectures can use to change 
the default choices should have detailed comments on the default 
definitions of all the relevant macros to explain their semantics.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> On Thu, 28 May 2015, Ondřej Bílka wrote:
> 
> > Both comments are correct. We should do it generically and surround
> > these functions with ifdef to supply arch-specific versions. 
> 
> #if, not #ifdef, please, for all architecture choices in these functions.  
> The sysdeps/generic version of the header architectures can use to change 
> the default choices should have detailed comments on the default 
> definitions of all the relevant macros to explain their semantics.
> 
For what purpose? Its pointless except that you would need to have
additional header say precommon.h, then undef and redefine macro when
you want change.

And it doesn't help to catch any errors. If you misspell define then you
will get error with duplicate definition.

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Joseph Myers]

[-- Attachment #1: Type: text/plain, Size: 2157 bytes --]

On Fri, 29 May 2015, Ondřej Bílka wrote:

> On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> > On Thu, 28 May 2015, Ondřej Bílka wrote:
> > 
> > > Both comments are correct. We should do it generically and surround
> > > these functions with ifdef to supply arch-specific versions. 
> > 
> > #if, not #ifdef, please, for all architecture choices in these functions.  
> > The sysdeps/generic version of the header architectures can use to change 
> > the default choices should have detailed comments on the default 
> > definitions of all the relevant macros to explain their semantics.
> > 
> For what purpose? Its pointless except that you would need to have
> additional header say precommon.h, then undef and redefine macro when
> you want change.

The general principle is that macro uses should be typo-proof.  That means 
avoiding #ifdef, #ifndef and #undef where possible.

The principle of documenting macro semantics applies even if there's a 
good reason typo-proof conventions are problematic in a particular case.  
There should *never* be any sort of architecture hook without clear 
documentation of the semantics of the hook (written from the perspective 
of an architecture maintainer wanting to know how to set the hook for 
their architecture, not from the perspective of the person writing the 
code using the hook).  I always advise writing documentation early in the 
process of developing a patch - the documentation is as important as the 
rest of the code.

> And it doesn't help to catch any errors. If you misspell define then you
> will get error with duplicate definition.

If the code does

#ifdef MACRO

or

#ifndef MACRO

then if an architecture does

#define MCARO

(with or without #undef) that will silently be ignored.

If, instead, the code does

#if MACRO

and there's a sysdeps/generic header that defines MACRO one way, if an 
architecture overrides that header with one that misspells the name, a 
-Wundef warning will be immediately visible (though we still need to fix 
the -Wundef warnings in the testsuite and remove the -Wno-error=undef).

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Fri, May 29, 2015 at 10:42:17AM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> > > On Thu, 28 May 2015, Ondřej Bílka wrote:
> > > 
> > > > Both comments are correct. We should do it generically and surround
> > > > these functions with ifdef to supply arch-specific versions. 
> > > 
> > > #if, not #ifdef, please, for all architecture choices in these functions.  
> > > The sysdeps/generic version of the header architectures can use to change 
> > > the default choices should have detailed comments on the default 
> > > definitions of all the relevant macros to explain their semantics.
> > > 
> > For what purpose? Its pointless except that you would need to have
> > additional header say precommon.h, then undef and redefine macro when
> > you want change.
> 
> The general principle is that macro uses should be typo-proof.  That means 
> avoiding #ifdef, #ifndef and #undef where possible.
> 
> The principle of documenting macro semantics applies even if there's a 
> good reason typo-proof conventions are problematic in a particular case.  
> There should *never* be any sort of architecture hook without clear 
> documentation of the semantics of the hook (written from the perspective 
> of an architecture maintainer wanting to know how to set the hook for 
> their architecture, not from the perspective of the person writing the 
> code using the hook).  I always advise writing documentation early in the 
> process of developing a patch - the documentation is as important as the 
> rest of the code.
> 
> > And it doesn't help to catch any errors. If you misspell define then you
> > will get error with duplicate definition.
> 
> If the code does
> 
> #ifdef MACRO
> 
> or
> 
> #ifndef MACRO
> 
> then if an architecture does
> 
> #define MCARO
> 
> (with or without #undef) that will silently be ignored.
> 
> If, instead, the code does
> 
> #if MACRO
> 
> and there's a sysdeps/generic header that defines MACRO one way, if an 
> architecture overrides that header with one that misspells the name, a 
> -Wundef warning will be immediately visible (though we still need to fix 
> the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> 
Joseph, read previous mail before writing. Your suggestion is pointless.

For a code

#ifndef CUSTOM_FOO
int foo()
{
}
#endif

If architecture does
#define CUTSOM_FOO
int foo()
{
}

Then it gets error with redefinition of foo.

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Joseph Myers]

[-- Attachment #1: Type: text/plain, Size: 2624 bytes --]

On Fri, 29 May 2015, Ondřej Bílka wrote:

> > If, instead, the code does
> > 
> > #if MACRO
> > 
> > and there's a sysdeps/generic header that defines MACRO one way, if an 
> > architecture overrides that header with one that misspells the name, a 
> > -Wundef warning will be immediately visible (though we still need to fix 
> > the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> > 
> Joseph, read previous mail before writing. Your suggestion is pointless.

Which previous mail?  As far as I can tell, your last patch posting adding 
common.h is <https://sourceware.org/ml/libc-alpha/2015-05/msg00751.html>, 
which has a range of within-function #ifdefs (some completely untested, 
e.g. "#  ifdef NEED BITWISE", and all completely undocumented).  Anyway, 
when we have conventions in glibc (such as preferring #if to #ifdef) you 
should follow them unless there is a strong justification for doing 
otherwise (presented in every patch submission).  Likewise, even early 
patches should follow normal glibc formatting conventions.

Throwing out a series of untested, undocumented patches is not a helpful 
way of proposing changes to glibc.  I strongly recommend, in any 
complicated case such as this, that:

(a) each patch submission is self-contained - has the full self-contained 
write-up of the patch itself with the rationale for the patch and all the 
choices made, that would go in the commit message, followed by the 
description of changes from the previous version, rather than requiring a 
trail of previous messages to be followed to get the full rationale; and

(b) the documentation is more important than the code (write first for 
humans to read, only then for computers to execute); documenting the 
interfaces (such as FAST_CLZ and NEED_BITWISE) should be a very early step 
before any patches are sent to the list, not an afterthought, and the same 
applies to each internal function and macro in the code, even those that 
are not interfaces for architectures to reimplement.

> For a code
> 
> #ifndef CUSTOM_FOO
> int foo()
> {
> }
> #endif
> 
> If architecture does
> #define CUTSOM_FOO
> int foo()
> {
> }
> 
> Then it gets error with redefinition of foo.

Or you could avoid making readers think about whether the #ifndef is OK in 
a particular case by simply following normal glibc practices and have a 
sysdeps/generic/string-foo.h header that has a default definition with a 
careful comment explaining the semantics, and then architectures can have 
their own version to replace it as needed; no macros needed at all.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Fri, May 29, 2015 at 11:38:51AM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > > If, instead, the code does
> > > 
> > > #if MACRO
> > > 
> > > and there's a sysdeps/generic header that defines MACRO one way, if an 
> > > architecture overrides that header with one that misspells the name, a 
> > > -Wundef warning will be immediately visible (though we still need to fix 
> > > the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> > > 
> > Joseph, read previous mail before writing. Your suggestion is pointless.
> 
> Which previous mail?  As far as I can tell, your last patch posting adding 
> common.h is <https://sourceware.org/ml/libc-alpha/2015-05/msg00751.html>,

This one. I already explained that for using if you would need
additional header to be able to undefine macros.

https://sourceware.org/ml/libc-alpha/2015-05/msg00812.html


> 
> (a) each patch submission is self-contained - has the full self-contained 
> write-up of the patch itself with the rationale for the patch and all the 
> choices made, that would go in the commit message, followed by the 
> description of changes from the previous version, rather than requiring a 
> trail of previous messages to be followed to get the full rationale; and
>
Almost nobody does that for good reason, see that most v2 on lists are
shorter than previous. You should write mostly what changed. Sure, I
could copy-paste three pages from original mail with rationale but most
readers would skip it as its duplicate and would skip changes made into
it.

I could make recapitulation once per while but for incremental
improvements its best to keep just increments.
 
> (b) the documentation is more important than the code (write first for 
> humans to read, only then for computers to execute); documenting the 
> interfaces (such as FAST_CLZ and NEED_BITWISE) should be a very early step 
> before any patches are sent to the list, not an afterthought, and the same 
> applies to each internal function and macro in the code, even those that 
> are not interfaces for architectures to reimplement.
> 
Thats not completely true as purpose of this is get every bit of
performance before you need to go into assembly. It depends how
technical my interface will become, with strcmp I found that I need
handle another primitive. As documentation its better to have good
overview than overly verbose one. Some macros there are just there for
optimizer to try both branches and select better one.


> > For a code
> > 
> > #ifndef CUSTOM_FOO
> > int foo()
> > {
> > }
> > #endif
> > 
> > If architecture does
> > #define CUTSOM_FOO
> > int foo()
> > {
> > }
> > 
> > Then it gets error with redefinition of foo.
> 
> Or you could avoid making readers think about whether the #ifndef is OK in 
> a particular case by simply following normal glibc practices and have a 
> sysdeps/generic/string-foo.h header that has a default definition with a 
> careful comment explaining the semantics, and then architectures can have 
> their own version to replace it as needed; no macros needed at all.
> 
First its too typo-prone. Architecture maintainer would create
string_foo.h file and never notice that it was silently ignored.


Then why didn't you said that directly? That saves time instead
suggesting if when you mean separate file. Thats correct as there are
several variants and you need to run benchmark to select correct one.