diff mbox

[07/11] Improve generic strnlen

Message ID 20161217065729.28561-8-rth@twiddle.net
State New
Headers show

Commit Message

Richard Henderson Dec. 17, 2016, 6:57 a.m. UTC
* string/strnlen.c: Use haszero.h, whichzero.h.
---
 string/strnlen.c | 125 +++++++++----------------------------------------------
 1 file changed, 19 insertions(+), 106 deletions(-)

Comments

Adhemerval Zanella Netto Dec. 19, 2016, 2:59 p.m. UTC | #1
On 17/12/2016 04:57, Richard Henderson wrote:
>         * string/strnlen.c: Use haszero.h, whichzero.h.

As for strchr, since you already optimizing memchr why not base
strnlen on memchr instead:

--
size_t
__strnlen (const char *str, size_t maxlen)
{
  const char *char_str = memchr (str, 0, maxlen);
  return char_str ? char_str  - s : maxlen;
}
--

> ---
>  string/strnlen.c | 125 +++++++++----------------------------------------------
>  1 file changed, 19 insertions(+), 106 deletions(-)
> 
> diff --git a/string/strnlen.c b/string/strnlen.c
> index b2b0664..9927b9d 100644
> --- a/string/strnlen.c
> +++ b/string/strnlen.c
> @@ -21,7 +21,9 @@
>     not, see <http://www.gnu.org/licenses/>.  */
>  
>  #include <string.h>
> -#include <stdlib.h>
> +#include <stdint.h>
> +#include <haszero.h>
> +#include <whichzero.h>
>  
>  /* Find the length of S, but scan at most MAXLEN characters.  If no
>     '\0' terminator is found in that many characters, return MAXLEN.  */
> @@ -33,11 +35,12 @@
>  size_t
>  __strnlen (const char *str, size_t maxlen)
>  {
> -  const char *char_ptr, *end_ptr = str + maxlen;
> +  const char *char_ptr = str, *end_ptr = str + maxlen;
>    const unsigned long int *longword_ptr;
> -  unsigned long int longword, himagic, lomagic;
> +  unsigned long int longword;
> +  size_t i, align;
>  
> -  if (maxlen == 0)
> +  if (__glibc_unlikely (maxlen == 0))
>      return 0;
>  
>    if (__glibc_unlikely (end_ptr < str))
> @@ -45,116 +48,26 @@ __strnlen (const char *str, size_t maxlen)
>  
>    /* 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)
> +  align = -(uintptr_t)char_ptr % sizeof(longword);
> +  for (i = 0; i < align; ++i, ++char_ptr)
>      if (*char_ptr == '\0')
> -      {
> -	if (char_ptr > end_ptr)
> -	  char_ptr = end_ptr;
> -	return char_ptr - str;
> -      }
> +      goto found;
>  
> -  /* All these elucidatory comments refer to 4-byte longwords,
> -     but the theory applies equally well to 8-byte longwords.  */
> +  longword_ptr = (const unsigned long int *) char_ptr;
> +  char_ptr = end_ptr;
>  
> -  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)
> +  while (longword_ptr < (const unsigned long int *) end_ptr)
>      {
> -      /* 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)
> +      longword = *longword_ptr;
> +      if (haszero (longword))
>  	{
> -	  /* 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 = (const char *) longword_ptr + whichzero (longword);
> +	  break;
>  	}
> -      char_ptr = end_ptr;
> +      longword_ptr++;
>      }
>  
> + found:
>    if (char_ptr > end_ptr)
>      char_ptr = end_ptr;
>    return char_ptr - str;
>
Richard Henderson Dec. 19, 2016, 7:32 p.m. UTC | #2
On 12/19/2016 06:59 AM, Adhemerval Zanella wrote:
> As for strchr, since you already optimizing memchr why not base
> strnlen on memchr instead:
> 
> --
> size_t
> __strnlen (const char *str, size_t maxlen)
> {
>   const char *char_str = memchr (str, 0, maxlen);
>   return char_str ? char_str  - s : maxlen;
> }
> --

Yes, I think this is the right thing here.  Unlike strchr, strnlen is a lesser
used function.


r~
diff mbox

Patch

diff --git a/string/strnlen.c b/string/strnlen.c
index b2b0664..9927b9d 100644
--- a/string/strnlen.c
+++ b/string/strnlen.c
@@ -21,7 +21,9 @@ 
    not, see <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
+#include <stdint.h>
+#include <haszero.h>
+#include <whichzero.h>
 
 /* Find the length of S, but scan at most MAXLEN characters.  If no
    '\0' terminator is found in that many characters, return MAXLEN.  */
@@ -33,11 +35,12 @@ 
 size_t
 __strnlen (const char *str, size_t maxlen)
 {
-  const char *char_ptr, *end_ptr = str + maxlen;
+  const char *char_ptr = str, *end_ptr = str + maxlen;
   const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
+  unsigned long int longword;
+  size_t i, align;
 
-  if (maxlen == 0)
+  if (__glibc_unlikely (maxlen == 0))
     return 0;
 
   if (__glibc_unlikely (end_ptr < str))
@@ -45,116 +48,26 @@  __strnlen (const char *str, size_t maxlen)
 
   /* 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)
+  align = -(uintptr_t)char_ptr % sizeof(longword);
+  for (i = 0; i < align; ++i, ++char_ptr)
     if (*char_ptr == '\0')
-      {
-	if (char_ptr > end_ptr)
-	  char_ptr = end_ptr;
-	return char_ptr - str;
-      }
+      goto found;
 
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
+  longword_ptr = (const unsigned long int *) char_ptr;
+  char_ptr = end_ptr;
 
-  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)
+  while (longword_ptr < (const unsigned long int *) end_ptr)
     {
-      /* 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)
+      longword = *longword_ptr;
+      if (haszero (longword))
 	{
-	  /* 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 = (const char *) longword_ptr + whichzero (longword);
+	  break;
 	}
-      char_ptr = end_ptr;
+      longword_ptr++;
     }
 
+ found:
   if (char_ptr > end_ptr)
     char_ptr = end_ptr;
   return char_ptr - str;