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

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