1/* strchr (str, ch) -- Return pointer to first occurrence of CH in STR.
2 For Intel 80x86, x>=3.
3 Copyright (C) 1994-2022 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
5
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.
10
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.
15
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 <https://www.gnu.org/licenses/>. */
19
20#include <sysdep.h>
21#include "asm-syntax.h"
22
23#define PARMS 4+4 /* space for 1 saved reg */
24#define RTN PARMS
25#define STR RTN
26#define CHR STR+4
27
28 .text
29ENTRY (strchr)
30
31 pushl %edi /* Save callee-safe registers used here. */
32 cfi_adjust_cfa_offset (4)
33 cfi_rel_offset (edi, 0)
34 movl STR(%esp), %eax
35 movl CHR(%esp), %edx
36
37 /* At the moment %edx contains C. What we need for the
38 algorithm is C in all bytes of the dword. Avoid
39 operations on 16 bit words because these require an
40 prefix byte (and one more cycle). */
41 movb %dl, %dh /* now it is 0|0|c|c */
42 movl %edx, %ecx
43 shll $16, %edx /* now it is c|c|0|0 */
44 movw %cx, %dx /* and finally c|c|c|c */
45
46 /* Before we start with the main loop we process single bytes
47 until the source pointer is aligned. This has two reasons:
48 1. aligned 32-bit memory access is faster
49 and (more important)
50 2. we process in the main loop 32 bit in one step although
51 we don't know the end of the string. But accessing at
52 4-byte alignment guarantees that we never access illegal
53 memory if this would not also be done by the trivial
54 implementation (this is because all processor inherent
55 boundaries are multiples of 4. */
56
57 testb $3, %al /* correctly aligned ? */
58 jz L(11) /* yes => begin loop */
59 movb (%eax), %cl /* load byte in question (we need it twice) */
60 cmpb %cl, %dl /* compare byte */
61 je L(6) /* target found => return */
62 testb %cl, %cl /* is NUL? */
63 jz L(2) /* yes => return NULL */
64 incl %eax /* increment pointer */
65
66 testb $3, %al /* correctly aligned ? */
67 jz L(11) /* yes => begin loop */
68 movb (%eax), %cl /* load byte in question (we need it twice) */
69 cmpb %cl, %dl /* compare byte */
70 je L(6) /* target found => return */
71 testb %cl, %cl /* is NUL? */
72 jz L(2) /* yes => return NULL */
73 incl %eax /* increment pointer */
74
75 testb $3, %al /* correctly aligned ? */
76 jz L(11) /* yes => begin loop */
77 movb (%eax), %cl /* load byte in question (we need it twice) */
78 cmpb %cl, %dl /* compare byte */
79 je L(6) /* target found => return */
80 testb %cl, %cl /* is NUL? */
81 jz L(2) /* yes => return NULL */
82 incl %eax /* increment pointer */
83
84 /* No we have reached alignment. */
85 jmp L(11) /* begin loop */
86
87 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
88 change any of the hole bits of LONGWORD.
89
90 1) Is this safe? Will it catch all the zero bytes?
91 Suppose there is a byte with all zeros. Any carry bits
92 propagating from its left will fall into the hole at its
93 least significant bit and stop. Since there will be no
94 carry from its most significant bit, the LSB of the
95 byte to the left will be unchanged, and the zero will be
96 detected.
97
98 2) Is this worthwhile? Will it ignore everything except
99 zero bytes? Suppose every byte of LONGWORD has a bit set
100 somewhere. There will be a carry into bit 8. If bit 8
101 is set, this will carry into bit 16. If bit 8 is clear,
102 one of bits 9-15 must be set, so there will be a carry
103 into bit 16. Similarly, there will be a carry into bit
104 24. If one of bits 24-31 is set, there will be a carry
105 into bit 32 (=carry flag), so all of the hole bits will
106 be changed.
107
108 3) But wait! Aren't we looking for C, not zero?
109 Good point. So what we do is XOR LONGWORD with a longword,
110 each of whose bytes is C. This turns each byte that is C
111 into a zero. */
112
113 /* Each round the main loop processes 16 bytes. */
114
115 ALIGN(4)
116
117L(1): addl $16, %eax /* adjust pointer for whole round */
118
119L(11): movl (%eax), %ecx /* get word (= 4 bytes) in question */
120 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
121 are now 0 */
122 movl $0xfefefeff, %edi /* magic value */
123 addl %ecx, %edi /* add the magic value to the word. We get
124 carry bits reported for each byte which
125 is *not* C */
126
127 /* According to the algorithm we had to reverse the effect of the
128 XOR first and then test the overflow bits. But because the
129 following XOR would destroy the carry flag and it would (in a
130 representation with more than 32 bits) not alter then last
131 overflow, we can now test this condition. If no carry is signaled
132 no overflow must have occurred in the last byte => it was 0. */
133 jnc L(7)
134
135 /* We are only interested in carry bits that change due to the
136 previous add, so remove original bits */
137 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
138
139 /* Now test for the other three overflow bits. */
140 orl $0xfefefeff, %edi /* set all non-carry bits */
141 incl %edi /* add 1: if one carry bit was *not* set
142 the addition will not result in 0. */
143
144 /* If at least one byte of the word is C we don't get 0 in %edi. */
145 jnz L(7) /* found it => return pointer */
146
147 /* Now we made sure the dword does not contain the character we are
148 looking for. But because we deal with strings we have to check
149 for the end of string before testing the next dword. */
150
151 xorl %edx, %ecx /* restore original dword without reload */
152 movl $0xfefefeff, %edi /* magic value */
153 addl %ecx, %edi /* add the magic value to the word. We get
154 carry bits reported for each byte which
155 is *not* 0 */
156 jnc L(2) /* highest byte is NUL => return NULL */
157 xorl %ecx, %edi /* (word+magic)^word */
158 orl $0xfefefeff, %edi /* set all non-carry bits */
159 incl %edi /* add 1: if one carry bit was *not* set
160 the addition will not result in 0. */
161 jnz L(2) /* found NUL => return NULL */
162
163 movl 4(%eax), %ecx /* get word (= 4 bytes) in question */
164 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
165 are now 0 */
166 movl $0xfefefeff, %edi /* magic value */
167 addl %ecx, %edi /* add the magic value to the word. We get
168 carry bits reported for each byte which
169 is *not* C */
170 jnc L(71) /* highest byte is C => return pointer */
171 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
172 orl $0xfefefeff, %edi /* set all non-carry bits */
173 incl %edi /* add 1: if one carry bit was *not* set
174 the addition will not result in 0. */
175 jnz L(71) /* found it => return pointer */
176 xorl %edx, %ecx /* restore original dword without reload */
177 movl $0xfefefeff, %edi /* magic value */
178 addl %ecx, %edi /* add the magic value to the word. We get
179 carry bits reported for each byte which
180 is *not* 0 */
181 jnc L(2) /* highest byte is NUL => return NULL */
182 xorl %ecx, %edi /* (word+magic)^word */
183 orl $0xfefefeff, %edi /* set all non-carry bits */
184 incl %edi /* add 1: if one carry bit was *not* set
185 the addition will not result in 0. */
186 jnz L(2) /* found NUL => return NULL */
187
188 movl 8(%eax), %ecx /* get word (= 4 bytes) in question */
189 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
190 are now 0 */
191 movl $0xfefefeff, %edi /* magic value */
192 addl %ecx, %edi /* add the magic value to the word. We get
193 carry bits reported for each byte which
194 is *not* C */
195 jnc L(72) /* highest byte is C => return pointer */
196 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
197 orl $0xfefefeff, %edi /* set all non-carry bits */
198 incl %edi /* add 1: if one carry bit was *not* set
199 the addition will not result in 0. */
200 jnz L(72) /* found it => return pointer */
201 xorl %edx, %ecx /* restore original dword without reload */
202 movl $0xfefefeff, %edi /* magic value */
203 addl %ecx, %edi /* add the magic value to the word. We get
204 carry bits reported for each byte which
205 is *not* 0 */
206 jnc L(2) /* highest byte is NUL => return NULL */
207 xorl %ecx, %edi /* (word+magic)^word */
208 orl $0xfefefeff, %edi /* set all non-carry bits */
209 incl %edi /* add 1: if one carry bit was *not* set
210 the addition will not result in 0. */
211 jnz L(2) /* found NUL => return NULL */
212
213 movl 12(%eax), %ecx /* get word (= 4 bytes) in question */
214 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
215 are now 0 */
216 movl $0xfefefeff, %edi /* magic value */
217 addl %ecx, %edi /* add the magic value to the word. We get
218 carry bits reported for each byte which
219 is *not* C */
220 jnc L(73) /* highest byte is C => return pointer */
221 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
222 orl $0xfefefeff, %edi /* set all non-carry bits */
223 incl %edi /* add 1: if one carry bit was *not* set
224 the addition will not result in 0. */
225 jnz L(73) /* found it => return pointer */
226 xorl %edx, %ecx /* restore original dword without reload */
227 movl $0xfefefeff, %edi /* magic value */
228 addl %ecx, %edi /* add the magic value to the word. We get
229 carry bits reported for each byte which
230 is *not* 0 */
231 jnc L(2) /* highest byte is NUL => return NULL */
232 xorl %ecx, %edi /* (word+magic)^word */
233 orl $0xfefefeff, %edi /* set all non-carry bits */
234 incl %edi /* add 1: if one carry bit was *not* set
235 the addition will not result in 0. */
236 jz L(1) /* no NUL found => restart loop */
237
238L(2): /* Return NULL. */
239 xorl %eax, %eax
240 popl %edi /* restore saved register content */
241 cfi_adjust_cfa_offset (-4)
242 cfi_restore (edi)
243
244 ret
245
246 cfi_adjust_cfa_offset (4)
247 cfi_rel_offset (edi, 0)
248L(73): addl $4, %eax /* adjust pointer */
249L(72): addl $4, %eax
250L(71): addl $4, %eax
251
252 /* We now scan for the byte in which the character was matched.
253 But we have to take care of the case that a NUL char is
254 found before this in the dword. Note that we XORed %ecx
255 with the byte we're looking for, therefore the tests below look
256 reversed. */
257
258L(7): testb %cl, %cl /* is first byte C? */
259 jz L(6) /* yes => return pointer */
260 cmpb %dl, %cl /* is first byte NUL? */
261 je L(2) /* yes => return NULL */
262 incl %eax /* it's not in the first byte */
263
264 testb %ch, %ch /* is second byte C? */
265 jz L(6) /* yes => return pointer */
266 cmpb %dl, %ch /* is second byte NUL? */
267 je L(2) /* yes => return NULL? */
268 incl %eax /* it's not in the second byte */
269
270 shrl $16, %ecx /* make upper byte accessible */
271 testb %cl, %cl /* is third byte C? */
272 jz L(6) /* yes => return pointer */
273 cmpb %dl, %cl /* is third byte NUL? */
274 je L(2) /* yes => return NULL */
275
276 /* It must be in the fourth byte and it cannot be NUL. */
277 incl %eax
278
279L(6):
280 popl %edi /* restore saved register content */
281 cfi_adjust_cfa_offset (-4)
282 cfi_restore (edi)
283
284 ret
285END (strchr)
286
287weak_alias (strchr, index)
288libc_hidden_builtin_def (strchr)
289

source code of glibc/sysdeps/i386/strchr.S