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