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