faster strchr [was: rawmemchr]

[Eric Blake <ebb9 at byu dot net>]

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)?

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;
  }