1 /* strchr (str, ch) -- Return pointer to first occurrence of CH in STR.
3 Copyright (C) 2002, 2005 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see
18 <http://www.gnu.org/licenses/>. */
20 #include "_glibc_inc.h"
22 /* Seems to be unrolled too much */
25 ENTRY (BP_SYM (strchr))
27 /* Before we start with the main loop we process single bytes
28 until the source pointer is aligned. This has two reasons:
29 1. aligned 64-bit memory access is faster
31 2. we process in the main loop 64 bit in one step although
32 we don't know the end of the string. But accessing at
33 8-byte alignment guarantees that we never access illegal
34 memory if this would not also be done by the trivial
35 implementation (this is because all processor inherent
36 boundaries are multiples of 8). */
39 andl $7, %edx /* Mask alignment bits */
40 movq %rdi, %rax /* duplicate destination. */
41 jz 1f /* aligned => start loop */
43 addl $8, %edx /* Align to 8 bytes. */
45 /* Search the first bytes directly. */
46 0: movb (%rax), %cl /* load byte */
47 cmpb %cl,%sil /* compare byte. */
48 je 6f /* target found */
49 testb %cl,%cl /* is byte NUL? */
50 je 7f /* yes => return NULL */
51 incq %rax /* increment pointer */
57 /* At the moment %rsi contains C. What we need for the
58 algorithm is C in all bytes of the register. Avoid
59 operations on 16 bit words because these require an
60 prefix byte (and one more cycle). */
61 /* Populate 8 bit data to full 64-bit. */
62 movabs $0x0101010101010101,%r9
66 movq $0xfefefefefefefeff, %r8 /* Save magic. */
68 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
69 change any of the hole bits of LONGWORD.
71 1) Is this safe? Will it catch all the zero bytes?
72 Suppose there is a byte with all zeros. Any carry bits
73 propagating from its left will fall into the hole at its
74 least significant bit and stop. Since there will be no
75 carry from its most significant bit, the LSB of the
76 byte to the left will be unchanged, and the zero will be
79 2) Is this worthwhile? Will it ignore everything except
80 zero bytes? Suppose every byte of QUARDWORD has a bit set
81 somewhere. There will be a carry into bit 8. If bit 8
82 is set, this will carry into bit 16. If bit 8 is clear,
83 one of bits 9-15 must be set, so there will be a carry
84 into bit 16. Similarly, there will be a carry into bit
85 24 tec.. If one of bits 54-63 is set, there will be a carry
86 into bit 64 (=carry flag), so all of the hole bits will
89 3) But wait! Aren't we looking for C, not zero?
90 Good point. So what we do is XOR LONGWORD with a longword,
91 each of whose bytes is C. This turns each byte that is C
94 /* Next 3 insns are 10 bytes total, make sure we decode them in one go */
97 /* Main Loop is unrolled 4 times. */
99 movq (%rax), %rcx /* get double word (= 8 bytes) in question */
100 addq $8,%rax /* adjust pointer for next word */
101 movq %r8, %rdx /* magic value */
102 xorq %r9, %rcx /* XOR with qword c|...|c => bytes of str == c
104 addq %rcx, %rdx /* add the magic value to the word. We get
105 carry bits reported for each byte which
107 jnc 3f /* highest byte is NUL => return pointer */
108 xorq %rcx, %rdx /* (word+magic)^word */
109 orq %r8, %rdx /* set all non-carry bits */
110 incq %rdx /* add 1: if one carry bit was *not* set
111 the addition will not result in 0. */
112 jnz 3f /* found c => return pointer */
114 /* The quadword we looked at does not contain the value we're looking
115 for. Let's search now whether we have reached the end of the
117 xorq %r9, %rcx /* restore original dword without reload */
118 movq %r8, %rdx /* magic value */
119 addq %rcx, %rdx /* add the magic value to the word. We get
120 carry bits reported for each byte which
122 jnc 7f /* highest byte is NUL => return NULL */
123 xorq %rcx, %rdx /* (word+magic)^word */
124 orq %r8, %rdx /* set all non-carry bits */
125 incq %rdx /* add 1: if one carry bit was *not* set
126 the addition will not result in 0. */
127 jnz 7f /* found NUL => return NULL */
130 movq (%rax), %rcx /* get double word (= 8 bytes) in question */
131 addq $8,%rax /* adjust pointer for next word */
132 movq %r8, %rdx /* magic value */
133 xorq %r9, %rcx /* XOR with qword c|...|c => bytes of str == c
135 addq %rcx, %rdx /* add the magic value to the word. We get
136 carry bits reported for each byte which
138 jnc 3f /* highest byte is NUL => return pointer */
139 xorq %rcx, %rdx /* (word+magic)^word */
140 orq %r8, %rdx /* set all non-carry bits */
141 incq %rdx /* add 1: if one carry bit was *not* set
142 the addition will not result in 0. */
143 jnz 3f /* found c => return pointer */
145 /* The quadword we looked at does not contain the value we're looking
146 for. Let's search now whether we have reached the end of the
148 xorq %r9, %rcx /* restore original dword without reload */
149 movq %r8, %rdx /* magic value */
150 addq %rcx, %rdx /* add the magic value to the word. We get
151 carry bits reported for each byte which
153 jnc 7f /* highest byte is NUL => return NULL */
154 xorq %rcx, %rdx /* (word+magic)^word */
155 orq %r8, %rdx /* set all non-carry bits */
156 incq %rdx /* add 1: if one carry bit was *not* set
157 the addition will not result in 0. */
158 jnz 7f /* found NUL => return NULL */
160 movq (%rax), %rcx /* get double word (= 8 bytes) in question */
161 addq $8,%rax /* adjust pointer for next word */
162 movq %r8, %rdx /* magic value */
163 xorq %r9, %rcx /* XOR with qword c|...|c => bytes of str == c
165 addq %rcx, %rdx /* add the magic value to the word. We get
166 carry bits reported for each byte which
168 jnc 3f /* highest byte is NUL => return pointer */
169 xorq %rcx, %rdx /* (word+magic)^word */
170 orq %r8, %rdx /* set all non-carry bits */
171 incq %rdx /* add 1: if one carry bit was *not* set
172 the addition will not result in 0. */
173 jnz 3f /* found c => return pointer */
175 /* The quadword we looked at does not contain the value we're looking
176 for. Let's search now whether we have reached the end of the
178 xorq %r9, %rcx /* restore original dword without reload */
179 movq %r8, %rdx /* magic value */
180 addq %rcx, %rdx /* add the magic value to the word. We get
181 carry bits reported for each byte which
183 jnc 7f /* highest byte is NUL => return NULL */
184 xorq %rcx, %rdx /* (word+magic)^word */
185 orq %r8, %rdx /* set all non-carry bits */
186 incq %rdx /* add 1: if one carry bit was *not* set
187 the addition will not result in 0. */
188 jnz 7f /* found NUL => return NULL */
190 movq (%rax), %rcx /* get double word (= 8 bytes) in question */
191 addq $8,%rax /* adjust pointer for next word */
192 movq %r8, %rdx /* magic value */
193 xorq %r9, %rcx /* XOR with qword c|...|c => bytes of str == c
195 addq %rcx, %rdx /* add the magic value to the word. We get
196 carry bits reported for each byte which
198 jnc 3f /* highest byte is NUL => return pointer */
199 xorq %rcx, %rdx /* (word+magic)^word */
200 orq %r8, %rdx /* set all non-carry bits */
201 incq %rdx /* add 1: if one carry bit was *not* set
202 the addition will not result in 0. */
203 jnz 3f /* found c => return pointer */
205 /* The quadword we looked at does not contain the value we're looking
206 for. Let's search now whether we have reached the end of the
208 xorq %r9, %rcx /* restore original dword without reload */
209 movq %r8, %rdx /* magic value */
210 addq %rcx, %rdx /* add the magic value to the word. We get
211 carry bits reported for each byte which
213 jnc 7f /* highest byte is NUL => return NULL */
214 xorq %rcx, %rdx /* (word+magic)^word */
215 orq %r8, %rdx /* set all non-carry bits */
216 incq %rdx /* add 1: if one carry bit was *not* set
217 the addition will not result in 0. */
218 jz 4b /* no NUL found => restart loop */
221 7: /* Return NULL. */
226 /* We now scan for the byte in which the character was matched.
227 But we have to take care of the case that a NUL char is
228 found before this in the dword. Note that we XORed %rcx
229 with the byte we're looking for, therefore the tests below look
233 /* Align, it's a jump target. */
234 /* Next 3 insns are 9 bytes total, make sure we decode them in one go */
237 movq %r9,%rdx /* move to %rdx so that we can access bytes */
238 subq $8,%rax /* correct pointer increment. */
239 testb %cl, %cl /* is first byte C? */
240 jz 6f /* yes => return pointer */
241 cmpb %dl, %cl /* is first byte NUL? */
242 je 7b /* yes => return NULL */
243 incq %rax /* increment pointer */
245 testb %ch, %ch /* is second byte C? */
246 jz 6f /* yes => return pointer */
247 cmpb %dl, %ch /* is second byte NUL? */
248 je 7b /* yes => return NULL? */
249 incq %rax /* increment pointer */
251 shrq $16, %rcx /* make upper bytes accessible */
252 testb %cl, %cl /* is third byte C? */
253 jz 6f /* yes => return pointer */
254 cmpb %dl, %cl /* is third byte NUL? */
255 je 7b /* yes => return NULL */
256 incq %rax /* increment pointer */
258 testb %ch, %ch /* is fourth byte C? */
259 jz 6f /* yes => return pointer */
260 cmpb %dl, %ch /* is fourth byte NUL? */
261 je 7b /* yes => return NULL? */
262 incq %rax /* increment pointer */
264 shrq $16, %rcx /* make upper bytes accessible */
265 testb %cl, %cl /* is fifth byte C? */
266 jz 6f /* yes => return pointer */
267 cmpb %dl, %cl /* is fifth byte NUL? */
268 je 7b /* yes => return NULL */
269 incq %rax /* increment pointer */
271 testb %ch, %ch /* is sixth byte C? */
272 jz 6f /* yes => return pointer */
273 cmpb %dl, %ch /* is sixth byte NUL? */
274 je 7b /* yes => return NULL? */
275 incq %rax /* increment pointer */
277 shrq $16, %rcx /* make upper bytes accessible */
278 testb %cl, %cl /* is seventh byte C? */
279 jz 6f /* yes => return pointer */
280 cmpb %dl, %cl /* is seventh byte NUL? */
281 je 7b /* yes => return NULL */
283 /* It must be in the eigth byte and it cannot be NUL. */
289 END (BP_SYM (strchr))
291 libc_hidden_def(strchr)
292 #ifdef __UCLIBC_SUSV3_LEGACY__
293 strong_alias (BP_SYM (strchr), BP_SYM (index))