Re: [PATCH 05/11] Improve generic strrchr

[Adhemerval Zanella <adhemerval dot zanella at linaro dot org>]

As for strchr and and strnlen, I think default strrchr can be changed 
use already optimized symbols:

--
#ifndef STRRCHR
# define STRRCHR strrchr
#endif

/* Find the last occurrence of C in S.  */
char *
STRRCHR (const char *s, int int_c)
{
  return __memrchr (s, int_c, strlen (s) + 1);
}
--

On 17/12/2016 04:57, Richard Henderson wrote:
>      * string/strrchr.c: Use haszero.h.
> ---
>  string/strrchr.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 56 insertions(+), 11 deletions(-)
> 
> diff --git a/string/strrchr.c b/string/strrchr.c
> index a07457e..bea7d76 100644
> --- a/string/strrchr.c
> +++ b/string/strrchr.c
> @@ -16,6 +16,10 @@
>     <http://www.gnu.org/licenses/>.  */
>  
>  #include <string.h>
> +#include <stdint.h>
> +#include <haszero.h>
> +#include <whichzero.h>
> +#include <extractbyte.h>
>  
>  #undef strrchr
>  
> @@ -25,25 +29,66 @@
>  
>  /* Find the last occurrence of C in S.  */
>  char *
> -STRRCHR (const char *s, int c)
> +STRRCHR (const char *s, int int_c)
>  {
> -  const char *found, *p;
> +  const unsigned char *found_c = NULL, *ptr_c;
> +  const unsigned long int *found_w = NULL, *ptr_w;
> +  unsigned long int longword, repeated_c;
> +  uintptr_t i, align;
> +  unsigned char c;
>  
> -  c = (unsigned char) c;
> +  c = (unsigned char) int_c;
> +  ptr_c = (const unsigned char *) s;
>  
> -  /* Since strchr is fast, we use it rather than the obvious loop.  */
> +  /* Handle the first few characters by reading one character at a time.
> +     Do this until CHAR_PTR is aligned on a longword boundary.  */
> +  align = -(uintptr_t)ptr_c % sizeof(longword);
> +  for (i = 0; i < align; ++i, ++ptr_c)
> +    {
> +      unsigned char this_c = *ptr_c;
> +      if (this_c == c)
> +        found_c = ptr_c;
> +      if (this_c == '\0')
> +        goto done;
> +    }
> +
> +  /* Set up a longword, each of whose bytes is C.  */
> +  repeated_c = (-1ul / 0xff) * c;
> +
> +  /* Search words for C.  At this point, merely record the last word
> +     that contained the character.  Stop when we find EOS.  */
> +  ptr_w = (const unsigned long int *) ptr_c;
> +  while (1)
> +    {
> +      longword = *ptr_w;
> +      if (haszero (longword))
> +	break;
> +      if (haszero (longword ^ repeated_c))
> +	found_w = ptr_w;
> +      ptr_w++;
> +    }
>  
> -  if (c == '\0')
> -    return strchr (s, '\0');
> +  /* Check to see if we've got C in the last longword.  */
> +  i = whichzero2 (longword, longword ^ repeated_c);
> +  if (extractbyte (longword, i) == c)
> +    found_w = ptr_w;
>  
> -  found = NULL;
> -  while ((p = strchr (s, c)) != NULL)
> +  /* If we found a word containing C, go back and search it byte by byte.  */
> +  if (found_w)
>      {
> -      found = p;
> -      s = p + 1;
> +      ptr_c = (const unsigned char *) found_w;
> +      for (i = 0; i < sizeof(longword); ++i, ++ptr_c)
> +	{
> +	  unsigned char this_c = *ptr_c;
> +	  if (this_c == c)
> +	    found_c = ptr_c;
> +	  if (this_c == '\0')
> +	    break;
> +	}
>      }
>  
> -  return (char *) found;
> + done:
> +  return (char *) found_c;
>  }
>  
>  #ifdef weak_alias
>