[thirdparty/glibc.git] / string / strchr.c

/* Copyright (C) 1991-2014 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
   with help from Dan Sahlin (dan@sics.se) and
   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
   and implemented by Roland McGrath (roland@ai.mit.edu).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, see
   <http://www.gnu.org/licenses/>.  */

#include <string.h>
#include <memcopy.h>
#include <stdlib.h>

#undef strchr

/* Find the first occurrence of C in S.  */
char *
strchr (s, c_in)
     const char *s;
     int c_in;
{
  const unsigned char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, magic_bits, charmask;
  unsigned char c;

  c = (unsigned char) c_in;

  /* 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 = (const unsigned char *) s;
       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == c)
      return (void *) char_ptr;
    else if (*char_ptr == '\0')
      return NULL;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  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.  */
  switch (sizeof (longword))
    {
    case 4: magic_bits = 0x7efefeffL; break;
    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
    default:
      abort ();
    }

  /* Set up a longword, each of whose bytes is C.  */
  charmask = c | (c << 8);
  charmask |= charmask << 16;
  if (sizeof (longword) > 4)
    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
    charmask |= (charmask << 16) << 16;
  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.  */
  for (;;)
    {
      /* 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.

	 3) But wait!  Aren't we looking for C as well as zero?
	 Good point.  So what we do is XOR LONGWORD with a longword,
	 each of whose bytes is C.  This turns each byte that is C
	 into a zero.  */

      longword = *longword_ptr++;

      /* Add MAGIC_BITS to LONGWORD.  */
      if ((((longword + magic_bits)

	    /* Set those bits that were unchanged by the addition.  */
	    ^ ~longword)

	   /* Look at only the hole bits.  If any of the hole bits
	      are unchanged, most likely one of the bytes was a
	      zero.  */
	   & ~magic_bits) != 0 ||

	  /* That caught zeroes.  Now test for C.  */
	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
	   & ~magic_bits) != 0)
	{
	  /* Which of the bytes was C or zero?
	     If none of them were, it was a misfire; continue the search.  */

	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);

	  if (*cp == c)
	    return (char *) cp;
	  else if (*cp == '\0')
	    return NULL;
	  if (*++cp == c)
	    return (char *) cp;
	  else if (*cp == '\0')
	    return NULL;
	  if (*++cp == c)
	    return (char *) cp;
	  else if (*cp == '\0')
	    return NULL;
	  if (*++cp == c)
	    return (char *) cp;
	  else if (*cp == '\0')
	    return NULL;
	  if (sizeof (longword) > 4)
	    {
	      if (*++cp == c)
		return (char *) cp;
	      else if (*cp == '\0')
		return NULL;
	      if (*++cp == c)
		return (char *) cp;
	      else if (*cp == '\0')
		return NULL;
	      if (*++cp == c)
		return (char *) cp;
	      else if (*cp == '\0')
		return NULL;
	      if (*++cp == c)
		return (char *) cp;
	      else if (*cp == '\0')
		return NULL;
	    }
	}
    }

  return NULL;
}

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