faster strchr [was: rawmemchr]

[Jeff Johnston]

Eric Blake wrote:
> Jeff Johnston <jjohnstn <at> redhat.com> writes:
>
>   
>>> So, OK to apply this patch?
>>>
>>>   
>>>       
>> Yes, go ahead.  I assume you have verified that the function still works 
>> correctly.
>>
>>     
>
> Yes - I built cygwin using the improved version, then ran through the test 
> suites of several programs that use strchr.  It passed all my tests whether the 
> byte is found or not, and whether the byte is 0 or not.  So I committed it.
>
> OK for this followon, which changes the generic C code in the same manner (also 
> tested)?
>
>   

Yes, thanks.

-- Jeff J.
> 2008-05-21  Eric Blake  <ebb9@byu.net>
>
> 	Optimize the generic strchr.
> 	* libc/string/strchr.c (strchr): Pre-align data so unaligned
> 	searches aren't penalized.  Special-case searching for 0.
>
> Index: libc/string/strchr.c
> ===================================================================
> RCS file: /cvs/src/src/newlib/libc/string/strchr.c,v
> retrieving revision 1.2
> diff -c -r1.2 strchr.c
> *** libc/string/strchr.c	10 May 2002 17:51:18 -0000	1.2
> --- libc/string/strchr.c	21 May 2008 22:11:18 -0000
> ***************
> *** 63,108 ****
>   	int i)
>   {
>     _CONST unsigned char *s = (_CONST unsigned char *)s1;
> ! #if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
> !   unsigned char c = (unsigned int)i;
>   
> !   while (*s && *s != c)
> !     {
> !       s++;
> !     }
>   
> !   if (*s != c)
>       {
> !       s = NULL;
>       }
>   
> !   return (char *) s;
> ! #else
> !   unsigned char c = (unsigned char)i;
> !   unsigned long mask,j;
> !   unsigned long *aligned_addr;
> ! 
> !   if (!UNALIGNED (s))
>       {
> !       mask = 0;
> !       for (j = 0; j < LBLOCKSIZE; j++)
> !         mask = (mask << 8) | c;
>   
> !       aligned_addr = (unsigned long*)s;
> !       while (!DETECTNULL (*aligned_addr) && !DETECTCHAR (*aligned_addr, mask))
> !         aligned_addr++;
>   
> !       /* The block of bytes currently pointed to by aligned_addr
> !          contains either a null or the target char, or both.  We
> !          catch it using the bytewise search.  */
>   
> !       s = (unsigned char*)aligned_addr;
> !     }
>   
>     while (*s && *s != c)
> !       s++;
>     if (*s == c)
>       return (char *)s;
>     return NULL;
> - #endif /* not PREFER_SIZE_OVER_SPEED */
>   }
> --- 63,123 ----
>   	int i)
>   {
>     _CONST unsigned char *s = (_CONST unsigned char *)s1;
> !   unsigned char c = i;
>   
> ! #if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
> !   unsigned long mask,j;
> !   unsigned long *aligned_addr;
>   
> !   /* Special case for finding 0.  */
> !   if (!c)
>       {
> !       while (UNALIGNED (s))
> !         {
> !           if (!*s)
> !             return (char *) s;
> !           s++;
> !         }
> !       /* Operate a word at a time.  */
> !       aligned_addr = (unsigned long *) s;
> !       while (!DETECTNULL (*aligned_addr))
> !         aligned_addr++;
> !       /* Found the end of string.  */
> !       s = (const unsigned char *) aligned_addr;
> !       while (*s)
> !         s++;
> !       return (char *) s;
>       }
>   
> !   /* All other bytes.  Align the pointer, then search a long at a time.  */
> !   while (UNALIGNED (s))
>       {
> !       if (!*s)
> !         return NULL;
> !       if (*s == c)
> !         return (char *) s;
> !       s++;
> !     }
>   
> !   mask = c;
> !   for (j = 8; j < LBLOCKSIZE * 8; j <<= 1)
> !     mask = (mask << j) | mask;
> ! 
> !   aligned_addr = (unsigned long *) s;
> !   while (!DETECTNULL (*aligned_addr) && !DETECTCHAR (*aligned_addr, mask))
> !     aligned_addr++;
> ! 
> !   /* The block of bytes currently pointed to by aligned_addr
> !      contains either a null or the target char, or both.  We
> !      catch it using the bytewise search.  */
>   
> !   s = (unsigned char *) aligned_addr;
>   
> ! #endif /* not PREFER_SIZE_OVER_SPEED */
>   
>     while (*s && *s != c)
> !     s++;
>     if (*s == c)
>       return (char *)s;
>     return NULL;
>   }
>
>
>
>