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