1 /* strchrnul (str, ch) -- Return pointer to first occurrence of CH in STR
4 Copyright (C) 1994, 1995, 1996, 1997, 1999 Free Software Foundation, Inc.
5 This file is part of the GNU C Library.
6 Contributed by Ulrich Drepper <drepper@gnu.org>
7 Some optimisations by Alan Modra <Alan@SPRI.Levels.UniSA.Edu.Au>
9 The GNU C Library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Library General Public License as
11 published by the Free Software Foundation; either version 2 of the
12 License, or (at your option) any later version.
14 The GNU C Library is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Library General Public License for more details.
19 You should have received a copy of the GNU Library General Public
20 License along with the GNU C Library; see the file COPYING.LIB. If not,
21 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
22 Boston, MA 02111-1307, USA. */
25 #include "asm-syntax.h"
35 pushl %edi /* Save callee-safe registers used here. */
37 movl 8(%esp), %eax /* get string pointer */
38 movl 12(%esp), %edx /* get character we are looking for */
40 /* At the moment %edx contains C. What we need for the
41 algorithm is C in all bytes of the dword. Avoid
42 operations on 16 bit words because these require an
43 prefix byte (and one more cycle). */
44 movb %dl, %dh /* now it is 0|0|c|c */
46 shll $16, %edx /* now it is c|c|0|0 */
47 movw %cx, %dx /* and finally c|c|c|c */
49 /* Before we start with the main loop we process single bytes
50 until the source pointer is aligned. This has two reasons:
51 1. aligned 32-bit memory access is faster
53 2. we process in the main loop 32 bit in one step although
54 we don't know the end of the string. But accessing at
55 4-byte alignment guarantees that we never access illegal
56 memory if this would not also be done by the trivial
57 implementation (this is because all processor inherent
58 boundaries are multiples of 4. */
60 testb $3, %eax /* correctly aligned ? */
61 jz L(11) /* yes => begin loop */
62 movb (%eax), %cl /* load byte in question (we need it twice) */
63 cmpb %cl, %dl /* compare byte */
64 je L(6) /* target found => return */
65 testb %cl, %cl /* is NUL? */
66 jz L(6) /* yes => return NULL */
67 incl %eax /* increment pointer */
69 testb $3, %eax /* correctly aligned ? */
70 jz L(11) /* yes => begin loop */
71 movb (%eax), %cl /* load byte in question (we need it twice) */
72 cmpb %cl, %dl /* compare byte */
73 je L(6) /* target found => return */
74 testb %cl, %cl /* is NUL? */
75 jz L(6) /* yes => return NULL */
76 incl %eax /* increment pointer */
78 testb $3, %eax /* correctly aligned ? */
79 jz L(11) /* yes => begin loop */
80 movb (%eax), %cl /* load byte in question (we need it twice) */
81 cmpb %cl, %dl /* compare byte */
82 je L(6) /* target found => return */
83 testb %cl, %cl /* is NUL? */
84 jz L(6) /* yes => return NULL */
85 incl %eax /* increment pointer */
87 /* No we have reached alignment. */
88 jmp L(11) /* begin loop */
90 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
91 change any of the hole bits of LONGWORD.
93 1) Is this safe? Will it catch all the zero bytes?
94 Suppose there is a byte with all zeros. Any carry bits
95 propagating from its left will fall into the hole at its
96 least significant bit and stop. Since there will be no
97 carry from its most significant bit, the LSB of the
98 byte to the left will be unchanged, and the zero will be
101 2) Is this worthwhile? Will it ignore everything except
102 zero bytes? Suppose every byte of LONGWORD has a bit set
103 somewhere. There will be a carry into bit 8. If bit 8
104 is set, this will carry into bit 16. If bit 8 is clear,
105 one of bits 9-15 must be set, so there will be a carry
106 into bit 16. Similarly, there will be a carry into bit
107 24. If one of bits 24-31 is set, there will be a carry
108 into bit 32 (=carry flag), so all of the hole bits will
111 3) But wait! Aren't we looking for C, not zero?
112 Good point. So what we do is XOR LONGWORD with a longword,
113 each of whose bytes is C. This turns each byte that is C
116 /* Each round the main loop processes 16 bytes. */
120 L(1): addl $16, %eax /* adjust pointer for whole round */
122 L(11): movl (%eax), %ecx /* get word (= 4 bytes) in question */
123 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
125 movl $0xfefefeff, %edi /* magic value */
126 addl %ecx, %edi /* add the magic value to the word. We get
127 carry bits reported for each byte which
130 /* According to the algorithm we had to reverse the effect of the
131 XOR first and then test the overflow bits. But because the
132 following XOR would destroy the carry flag and it would (in a
133 representation with more than 32 bits) not alter then last
134 overflow, we can now test this condition. If no carry is signaled
135 no overflow must have occurred in the last byte => it was 0. */
138 /* We are only interested in carry bits that change due to the
139 previous add, so remove original bits */
140 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
142 /* Now test for the other three overflow bits. */
143 orl $0xfefefeff, %edi /* set all non-carry bits */
144 incl %edi /* add 1: if one carry bit was *not* set
145 the addition will not result in 0. */
147 /* If at least one byte of the word is C we don't get 0 in %edi. */
148 jnz L(7) /* found it => return pointer */
150 /* Now we made sure the dword does not contain the character we are
151 looking for. But because we deal with strings we have to check
152 for the end of string before testing the next dword. */
154 xorl %edx, %ecx /* restore original dword without reload */
155 movl $0xfefefeff, %edi /* magic value */
156 addl %ecx, %edi /* add the magic value to the word. We get
157 carry bits reported for each byte which
159 jnc L(7) /* highest byte is NUL => return NULL */
160 xorl %ecx, %edi /* (word+magic)^word */
161 orl $0xfefefeff, %edi /* set all non-carry bits */
162 incl %edi /* add 1: if one carry bit was *not* set
163 the addition will not result in 0. */
164 jnz L(7) /* found NUL => return NULL */
166 movl 4(%eax), %ecx /* get word (= 4 bytes) in question */
167 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
169 movl $0xfefefeff, %edi /* magic value */
170 addl %ecx, %edi /* add the magic value to the word. We get
171 carry bits reported for each byte which
173 jnc L(71) /* highest byte is C => return pointer */
174 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
175 orl $0xfefefeff, %edi /* set all non-carry bits */
176 incl %edi /* add 1: if one carry bit was *not* set
177 the addition will not result in 0. */
178 jnz L(71) /* found it => return pointer */
179 xorl %edx, %ecx /* restore original dword without reload */
180 movl $0xfefefeff, %edi /* magic value */
181 addl %ecx, %edi /* add the magic value to the word. We get
182 carry bits reported for each byte which
184 jnc L(71) /* highest byte is NUL => return NULL */
185 xorl %ecx, %edi /* (word+magic)^word */
186 orl $0xfefefeff, %edi /* set all non-carry bits */
187 incl %edi /* add 1: if one carry bit was *not* set
188 the addition will not result in 0. */
189 jnz L(71) /* found NUL => return NULL */
191 movl 8(%eax), %ecx /* get word (= 4 bytes) in question */
192 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
194 movl $0xfefefeff, %edi /* magic value */
195 addl %ecx, %edi /* add the magic value to the word. We get
196 carry bits reported for each byte which
198 jnc L(72) /* highest byte is C => return pointer */
199 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
200 orl $0xfefefeff, %edi /* set all non-carry bits */
201 incl %edi /* add 1: if one carry bit was *not* set
202 the addition will not result in 0. */
203 jnz L(72) /* found it => return pointer */
204 xorl %edx, %ecx /* restore original dword without reload */
205 movl $0xfefefeff, %edi /* magic value */
206 addl %ecx, %edi /* add the magic value to the word. We get
207 carry bits reported for each byte which
209 jnc L(72) /* highest byte is NUL => return NULL */
210 xorl %ecx, %edi /* (word+magic)^word */
211 orl $0xfefefeff, %edi /* set all non-carry bits */
212 incl %edi /* add 1: if one carry bit was *not* set
213 the addition will not result in 0. */
214 jnz L(72) /* found NUL => return NULL */
216 movl 12(%eax), %ecx /* get word (= 4 bytes) in question */
217 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
219 movl $0xfefefeff, %edi /* magic value */
220 addl %ecx, %edi /* add the magic value to the word. We get
221 carry bits reported for each byte which
223 jnc L(73) /* highest byte is C => return pointer */
224 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
225 orl $0xfefefeff, %edi /* set all non-carry bits */
226 incl %edi /* add 1: if one carry bit was *not* set
227 the addition will not result in 0. */
228 jnz L(73) /* found it => return pointer */
229 xorl %edx, %ecx /* restore original dword without reload */
230 movl $0xfefefeff, %edi /* magic value */
231 addl %ecx, %edi /* add the magic value to the word. We get
232 carry bits reported for each byte which
234 jnc L(73) /* highest byte is NUL => return NULL */
235 xorl %ecx, %edi /* (word+magic)^word */
236 orl $0xfefefeff, %edi /* set all non-carry bits */
237 incl %edi /* add 1: if one carry bit was *not* set
238 the addition will not result in 0. */
239 jz L(1) /* no NUL found => restart loop */
241 L(73): addl $4, %eax /* adjust pointer */
245 /* We now scan for the byte in which the character was matched.
246 But we have to take care of the case that a NUL char is
247 found before this in the dword. */
249 L(7): testb %cl, %cl /* is first byte C? */
250 jz L(6) /* yes => return pointer */
251 cmpb %dl, %cl /* is first byte NUL? */
252 je L(6) /* yes => return NULL */
253 incl %eax /* it's not in the first byte */
255 testb %ch, %ch /* is second byte C? */
256 jz L(6) /* yes => return pointer */
257 cmpb %dl, %ch /* is second byte NUL? */
258 je L(6) /* yes => return NULL? */
259 incl %eax /* it's not in the second byte */
261 shrl $16, %ecx /* make upper byte accessible */
262 testb %cl, %cl /* is third byte C? */
263 jz L(6) /* yes => return pointer */
264 cmpb %dl, %cl /* is third byte NUL? */
265 je L(6) /* yes => return NULL */
267 /* It must be in the fourth byte and it cannot be NUL. */
270 L(6): popl %edi /* restore saved register content */
275 weak_alias (__strchrnul, strchrnul)