1 /* strrchr (str, ch) -- Return pointer to last occurrence of CH in STR.
3 Copyright (C) 1994-1997, 2000, 2003 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
5 Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>
6 Some optimisations by Alan Modra <Alan@SPRI.Levels.UniSA.Edu.Au>
8 The GNU C Library is free software; you can redistribute it and/or
9 modify it under the terms of the GNU Lesser General Public
10 License as published by the Free Software Foundation; either
11 version 2.1 of the License, or (at your option) any later version.
13 The GNU C Library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public
19 License along with the GNU C Library; if not, write to the Free
20 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
24 #include "asm-syntax.h"
28 #define PARMS LINKAGE+8 /* space for 2 saved regs */
30 #define STR RTN+RTN_SIZE
31 #define CHR STR+PTR_SIZE
34 ENTRY (BP_SYM (strrchr))
37 pushl %edi /* Save callee-safe registers used here. */
43 CHECK_BOUNDS_LOW (%esi, STR(%esp))
45 /* At the moment %ecx contains C. What we need for the
46 algorithm is C in all bytes of the dword. Avoid
47 operations on 16 bit words because these require an
48 prefix byte (and one more cycle). */
49 movb %cl, %ch /* now it is 0|0|c|c */
51 shll $16, %ecx /* now it is c|c|0|0 */
52 movw %dx, %cx /* and finally c|c|c|c */
54 /* Before we start with the main loop we process single bytes
55 until the source pointer is aligned. This has two reasons:
56 1. aligned 32-bit memory access is faster
58 2. we process in the main loop 32 bit in one step although
59 we don't know the end of the string. But accessing at
60 4-byte alignment guarantees that we never access illegal
61 memory if this would not also be done by the trivial
62 implementation (this is because all processor inherent
63 boundaries are multiples of 4. */
65 testl $3, %esi /* correctly aligned ? */
66 jz L(19) /* yes => begin loop */
67 movb (%esi), %dl /* load byte in question (we need it twice) */
68 cmpb %dl, %cl /* compare byte */
69 jne L(11) /* target found => return */
70 movl %esi, %eax /* remember pointer as possible result */
71 L(11): orb %dl, %dl /* is NUL? */
72 jz L(2) /* yes => return NULL */
73 incl %esi /* increment pointer */
75 testl $3, %esi /* correctly aligned ? */
76 jz L(19) /* yes => begin loop */
77 movb (%esi), %dl /* load byte in question (we need it twice) */
78 cmpb %dl, %cl /* compare byte */
79 jne L(12) /* target found => return */
80 movl %esi, %eax /* remember pointer as result */
81 L(12): orb %dl, %dl /* is NUL? */
82 jz L(2) /* yes => return NULL */
83 incl %esi /* increment pointer */
85 testl $3, %esi /* correctly aligned ? */
86 jz L(19) /* yes => begin loop */
87 movb (%esi), %dl /* load byte in question (we need it twice) */
88 cmpb %dl, %cl /* compare byte */
89 jne L(13) /* target found => return */
90 movl %esi, %eax /* remember pointer as result */
91 L(13): orb %dl, %dl /* is NUL? */
92 jz L(2) /* yes => return NULL */
93 incl %esi /* increment pointer */
95 /* No we have reached alignment. */
96 jmp L(19) /* begin loop */
98 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
99 change any of the hole bits of LONGWORD.
101 1) Is this safe? Will it catch all the zero bytes?
102 Suppose there is a byte with all zeros. Any carry bits
103 propagating from its left will fall into the hole at its
104 least significant bit and stop. Since there will be no
105 carry from its most significant bit, the LSB of the
106 byte to the left will be unchanged, and the zero will be
109 2) Is this worthwhile? Will it ignore everything except
110 zero bytes? Suppose every byte of LONGWORD has a bit set
111 somewhere. There will be a carry into bit 8. If bit 8
112 is set, this will carry into bit 16. If bit 8 is clear,
113 one of bits 9-15 must be set, so there will be a carry
114 into bit 16. Similarly, there will be a carry into bit
115 24. If one of bits 24-31 is set, there will be a carry
116 into bit 32 (=carry flag), so all of the hole bits will
119 3) But wait! Aren't we looking for C, not zero?
120 Good point. So what we do is XOR LONGWORD with a longword,
121 each of whose bytes is C. This turns each byte that is C
124 /* Each round the main loop processes 16 bytes. */
126 /* Jump to here when the character is detected. We chose this
127 way around because the character one is looking for is not
128 as frequent as the rest and taking a conditional jump is more
129 expensive than ignoring it.
131 Some more words to the code below: it might not be obvious why
132 we decrement the source pointer here. In the loop the pointer
133 is not pre-incremented and so it still points before the word
134 we are looking at. But you should take a look at the instruction
135 which gets executed before we get into the loop: `addl $16, %esi'.
136 This makes the following subs into adds. */
138 /* These fill bytes make the main loop be correctly aligned.
139 We cannot use align because it is not the following instruction
140 which should be aligned. */
143 /* Profiling adds some code and so changes the alignment. */
147 L(4): subl $4, %esi /* adjust pointer */
150 L(43): testl $0xff000000, %edx /* is highest byte == C? */
151 jnz L(33) /* no => try other bytes */
152 leal 15(%esi), %eax /* store address as result */
153 jmp L(1) /* and start loop again */
155 L(3): subl $4, %esi /* adjust pointer */
158 L(33): testl $0xff0000, %edx /* is C in third byte? */
159 jnz L(51) /* no => try other bytes */
160 leal 14(%esi), %eax /* store address as result */
161 jmp L(1) /* and start loop again */
164 /* At this point we know that the byte is in one of the lower bytes.
165 We make a guess and correct it if necessary. This reduces the
166 number of necessary jumps. */
167 leal 12(%esi), %eax /* guess address of lowest byte as result */
168 testb %dh, %dh /* is guess correct? */
169 jnz L(1) /* yes => start loop */
170 leal 13(%esi), %eax /* correct guess to second byte */
172 L(1): addl $16, %esi /* increment pointer for full round */
174 L(19): movl (%esi), %edx /* get word (= 4 bytes) in question */
175 movl $0xfefefeff, %edi /* magic value */
176 addl %edx, %edi /* add the magic value to the word. We get
177 carry bits reported for each byte which
180 /* According to the algorithm we had to reverse the effect of the
181 XOR first and then test the overflow bits. But because the
182 following XOR would destroy the carry flag and it would (in a
183 representation with more than 32 bits) not alter then last
184 overflow, we can now test this condition. If no carry is signaled
185 no overflow must have occurred in the last byte => it was 0. */
187 jnc L(20) /* found NUL => check last word */
189 /* We are only interested in carry bits that change due to the
190 previous add, so remove original bits */
191 xorl %edx, %edi /* (word+magic)^word */
193 /* Now test for the other three overflow bits. */
194 orl $0xfefefeff, %edi /* set all non-carry bits */
195 incl %edi /* add 1: if one carry bit was *not* set
196 the addition will not result in 0. */
198 /* If at least one byte of the word is C we don't get 0 in %edi. */
199 jnz L(20) /* found NUL => check last word */
201 /* Now we made sure the dword does not contain the character we are
202 looking for. But because we deal with strings we have to check
203 for the end of string before testing the next dword. */
205 xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c
207 movl $0xfefefeff, %edi /* magic value */
208 addl %edx, %edi /* add the magic value to the word. We get
209 carry bits reported for each byte which
211 jnc L(4) /* highest byte is C => examine dword */
212 xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */
213 orl $0xfefefeff, %edi /* set all non-carry bits */
214 incl %edi /* add 1: if one carry bit was *not* set
215 the addition will not result in 0. */
216 jnz L(3) /* C is detected in the word => examine it */
218 movl 4(%esi), %edx /* get word (= 4 bytes) in question */
219 movl $0xfefefeff, %edi /* magic value */
220 addl %edx, %edi /* add the magic value to the word. We get
221 carry bits reported for each byte which
223 jnc L(21) /* found NUL => check last word */
224 xorl %edx, %edi /* (word+magic)^word */
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(21) /* found NUL => check last word */
229 xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c
231 movl $0xfefefeff, %edi /* magic value */
232 addl %edx, %edi /* add the magic value to the word. We get
233 carry bits reported for each byte which
235 jnc L(41) /* highest byte is C => examine dword */
236 xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */
237 orl $0xfefefeff, %edi /* set all non-carry bits */
238 incl %edi /* add 1: if one carry bit was *not* set
239 the addition will not result in 0. */
240 jnz L(31) /* C is detected in the word => examine it */
242 movl 8(%esi), %edx /* get word (= 4 bytes) in question */
243 movl $0xfefefeff, %edi /* magic value */
244 addl %edx, %edi /* add the magic value to the word. We get
245 carry bits reported for each byte which
247 jnc L(22) /* found NUL => check last word */
248 xorl %edx, %edi /* (word+magic)^word */
249 orl $0xfefefeff, %edi /* set all non-carry bits */
250 incl %edi /* add 1: if one carry bit was *not* set
251 the addition will not result in 0. */
252 jnz L(22) /* found NUL => check last word */
253 xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c
255 movl $0xfefefeff, %edi /* magic value */
256 addl %edx, %edi /* add the magic value to the word. We get
257 carry bits reported for each byte which
259 jnc L(42) /* highest byte is C => examine dword */
260 xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */
261 orl $0xfefefeff, %edi /* set all non-carry bits */
262 incl %edi /* add 1: if one carry bit was *not* set
263 the addition will not result in 0. */
264 jnz L(32) /* C is detected in the word => examine it */
266 movl 12(%esi), %edx /* get word (= 4 bytes) in question */
267 movl $0xfefefeff, %edi /* magic value */
268 addl %edx, %edi /* add the magic value to the word. We get
269 carry bits reported for each byte which
271 jnc L(23) /* found NUL => check last word */
272 xorl %edx, %edi /* (word+magic)^word */
273 orl $0xfefefeff, %edi /* set all non-carry bits */
274 incl %edi /* add 1: if one carry bit was *not* set
275 the addition will not result in 0. */
276 jnz L(23) /* found NUL => check last word */
277 xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c
279 movl $0xfefefeff, %edi /* magic value */
280 addl %edx, %edi /* add the magic value to the word. We get
281 carry bits reported for each byte which
283 jnc L(43) /* highest byte is C => examine dword */
284 xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */
285 orl $0xfefefeff, %edi /* set all non-carry bits */
286 incl %edi /* add 1: if one carry bit was *not* set
287 the addition will not result in 0. */
288 jz L(1) /* C is not detected => restart loop */
289 jmp L(33) /* examine word */
291 L(23): addl $4, %esi /* adjust pointer */
295 /* What remains to do is to test which byte the NUL char is and
296 whether the searched character appears in one of the bytes
297 before. A special case is that the searched byte maybe NUL.
298 In this case a pointer to the terminating NUL char has to be
301 L(20): cmpb %cl, %dl /* is first byte == C? */
302 jne L(24) /* no => skip */
303 movl %esi, %eax /* store address as result */
304 L(24): testb %dl, %dl /* is first byte == NUL? */
305 jz L(2) /* yes => return */
307 cmpb %cl, %dh /* is second byte == C? */
308 jne L(25) /* no => skip */
309 leal 1(%esi), %eax /* store address as result */
310 L(25): testb %dh, %dh /* is second byte == NUL? */
311 jz L(2) /* yes => return */
313 shrl $16,%edx /* make upper bytes accessible */
314 cmpb %cl, %dl /* is third byte == C */
315 jne L(26) /* no => skip */
316 leal 2(%esi), %eax /* store address as result */
317 L(26): testb %dl, %dl /* is third byte == NUL */
318 jz L(2) /* yes => return */
320 cmpb %cl, %dh /* is fourth byte == C */
321 jne L(2) /* no => skip */
322 leal 3(%esi), %eax /* store address as result */
324 L(2): CHECK_BOUNDS_HIGH (%eax, STR(%esp), jb)
325 RETURN_BOUNDED_POINTER (STR(%esp))
326 popl %esi /* restore saved register content */
331 END (BP_SYM (strrchr))
333 weak_alias (BP_SYM (strrchr), BP_SYM (rindex))
334 libc_hidden_builtin_def (strrchr)