sysdeps/generic/strchr.c

   1 /* Copyright (C) 1991, 1993, 1994, 1995, 1996 Free Software Foundation, Inc.
   2    Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
   3    with help from Dan Sahlin (dan@sics.se) and
   4    bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
   5    adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
   6    and implemented by Roland McGrath (roland@ai.mit.edu).
   7
   8    The GNU C Library is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU Library General Public License as
  10    published by the Free Software Foundation; either version 2 of the
  11    License, or (at your option) any later version.
  12
  13    The GNU C Library is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    Library General Public License for more details.
  17
  18    You should have received a copy of the GNU Library General Public
  19    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  20    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  21    Boston, MA 02111-1307, USA.  */
  22
  23 #include <ansidecl.h>
  24 #include <string.h>
  25
  26
  27 /* Find the first occurrence of C in S.  */
  28
  29 char *
  30 DEFUN(strchr, (s, c), CONST char *s AND int c)
  31 {
  32   CONST unsigned char *char_ptr;
  33   CONST unsigned long int *longword_ptr;
  34   unsigned long int longword, magic_bits, charmask;
  35
  36   c = (unsigned char) c;
  37
  38   /* Handle the first few characters by reading one character at a time.
  39      Do this until CHAR_PTR is aligned on a longword boundary.  */
  40   for (char_ptr = s; ((unsigned long int) char_ptr
  41                       & (sizeof (longword) - 1)) != 0;
  42        ++char_ptr)
  43     if (*char_ptr == c)
  44       return (PTR) char_ptr;
  45     else if (*char_ptr == '\0')
  46       return NULL;
  47
  48   /* All these elucidatory comments refer to 4-byte longwords,
  49      but the theory applies equally well to 8-byte longwords.  */
  50
  51   longword_ptr = (unsigned long int *) char_ptr;
  52
  53   /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
  54      the "holes."  Note that there is a hole just to the left of
  55      each byte, with an extra at the end:
  56
  57      bits:  01111110 11111110 11111110 11111111
  58      bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
  59
  60      The 1-bits make sure that carries propagate to the next 0-bit.
  61      The 0-bits provide holes for carries to fall into.  */
  62   switch (sizeof (longword))
  63     {
  64     case 4: magic_bits = 0x7efefeffL; break;
  65     case 8: magic_bits = (0x7efefefeL << 32) | 0xfefefeffL; break;
  66     default:
  67       abort ();
  68     }
  69
  70   /* Set up a longword, each of whose bytes is C.  */
  71   charmask = c | (c << 8);
  72   charmask |= charmask << 16;
  73   if (sizeof (longword) > 4)
  74     charmask |= charmask << 32;
  75   if (sizeof (longword) > 8)
  76     abort ();
  77
  78   /* Instead of the traditional loop which tests each character,
  79      we will test a longword at a time.  The tricky part is testing
  80      if *any of the four* bytes in the longword in question are zero.  */
  81   for (;;)
  82     {
  83       /* We tentatively exit the loop if adding MAGIC_BITS to
  84          LONGWORD fails to change any of the hole bits of LONGWORD.
  85
  86          1) Is this safe?  Will it catch all the zero bytes?
  87          Suppose there is a byte with all zeros.  Any carry bits
  88          propagating from its left will fall into the hole at its
  89          least significant bit and stop.  Since there will be no
  90          carry from its most significant bit, the LSB of the
  91          byte to the left will be unchanged, and the zero will be
  92          detected.
  93
  94          2) Is this worthwhile?  Will it ignore everything except
  95          zero bytes?  Suppose every byte of LONGWORD has a bit set
  96          somewhere.  There will be a carry into bit 8.  If bit 8
  97          is set, this will carry into bit 16.  If bit 8 is clear,
  98          one of bits 9-15 must be set, so there will be a carry
  99          into bit 16.  Similarly, there will be a carry into bit
 100          24.  If one of bits 24-30 is set, there will be a carry
 101          into bit 31, so all of the hole bits will be changed.
 102
 103          The one misfire occurs when bits 24-30 are clear and bit
 104          31 is set; in this case, the hole at bit 31 is not
 105          changed.  If we had access to the processor carry flag,
 106          we could close this loophole by putting the fourth hole
 107          at bit 32!
 108
 109          So it ignores everything except 128's, when they're aligned
 110          properly.
 111
 112          3) But wait!  Aren't we looking for C as well as zero?
 113          Good point.  So what we do is XOR LONGWORD with a longword,
 114          each of whose bytes is C.  This turns each byte that is C
 115          into a zero.  */
 116
 117       longword = *longword_ptr++;
 118
 119       /* Add MAGIC_BITS to LONGWORD.  */
 120       if ((((longword + magic_bits)
 121
 122             /* Set those bits that were unchanged by the addition.  */
 123             ^ ~longword)
 124
 125            /* Look at only the hole bits.  If any of the hole bits
 126               are unchanged, most likely one of the bytes was a
 127               zero.  */
 128            & ~magic_bits) != 0 ||
 129
 130           /* That caught zeroes.  Now test for C.  */
 131           ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
 132            & ~magic_bits) != 0)
 133         {
 134           /* Which of the bytes was C or zero?
 135              If none of them were, it was a misfire; continue the search.  */
 136
 137           CONST unsigned char *cp = (CONST unsigned char *) (longword_ptr - 1);
 138
 139           if (*cp == c)
 140             return (char *) cp;
 141           else if (*cp == '\0')
 142             return NULL;
 143           if (*++cp == c)
 144             return (char *) cp;
 145           else if (*cp == '\0')
 146             return NULL;
 147           if (*++cp == c)
 148             return (char *) cp;
 149           else if (*cp == '\0')
 150             return NULL;
 151           if (*++cp == c)
 152             return (char *) cp;
 153           else if (*cp == '\0')
 154             return NULL;
 155           if (sizeof (longword) > 4)
 156             {
 157               if (*++cp == c)
 158                 return (char *) cp;
 159               else if (*cp == '\0')
 160                 return NULL;
 161               if (*++cp == c)
 162                 return (char *) cp;
 163               else if (*cp == '\0')
 164                 return NULL;
 165               if (*++cp == c)
 166                 return (char *) cp;
 167               else if (*cp == '\0')
 168                 return NULL;
 169               if (*++cp == c)
 170                 return (char *) cp;
 171               else if (*cp == '\0')
 172                 return NULL;
 173             }
 174         }
 175     }
 176
 177   return NULL;
 178 }
 179
 180 #ifdef weak_alias
 181 #undef index
 182 weak_alias (strchr, index)
 183 #endif