]>
Commit | Line | Data |
---|---|---|
569c558c | 1 | /* strrchr (str, ch) -- Return pointer to last occurrence of CH in STR. |
6d52618b | 2 | For Intel 80x86, x>=3. |
04277e02 | 3 | Copyright (C) 1994-2019 Free Software Foundation, Inc. |
6d52618b UD |
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> | |
7 | ||
8 | The GNU C Library is free software; you can redistribute it and/or | |
41bdb6e2 AJ |
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. | |
6d52618b UD |
12 | |
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 | |
41bdb6e2 | 16 | Lesser General Public License for more details. |
6d52618b | 17 | |
41bdb6e2 | 18 | You should have received a copy of the GNU Lesser General Public |
59ba27a6 | 19 | License along with the GNU C Library; if not, see |
5a82c748 | 20 | <https://www.gnu.org/licenses/>. */ |
8f5ca04b RM |
21 | |
22 | #include <sysdep.h> | |
23 | #include "asm-syntax.h" | |
24 | ||
2366713d | 25 | #define PARMS 4+8 /* space for 2 saved regs */ |
3f02f778 | 26 | #define RTN PARMS |
2366713d JM |
27 | #define STR RTN |
28 | #define CHR STR+4 | |
8f5ca04b RM |
29 | |
30 | .text | |
2366713d | 31 | ENTRY (strrchr) |
3f02f778 | 32 | |
8f5ca04b | 33 | pushl %edi /* Save callee-safe registers used here. */ |
1ad9da69 UD |
34 | cfi_adjust_cfa_offset (4) |
35 | cfi_rel_offset (edi, 0) | |
8f5ca04b | 36 | pushl %esi |
1ad9da69 | 37 | cfi_adjust_cfa_offset (4) |
8f5ca04b RM |
38 | |
39 | xorl %eax, %eax | |
3f02f778 | 40 | movl STR(%esp), %esi |
1ad9da69 | 41 | cfi_rel_offset (esi, 0) |
3f02f778 | 42 | movl CHR(%esp), %ecx |
8f5ca04b RM |
43 | |
44 | /* At the moment %ecx contains C. What we need for the | |
45 | algorithm is C in all bytes of the dword. Avoid | |
46 | operations on 16 bit words because these require an | |
47 | prefix byte (and one more cycle). */ | |
48 | movb %cl, %ch /* now it is 0|0|c|c */ | |
49 | movl %ecx, %edx | |
50 | shll $16, %ecx /* now it is c|c|0|0 */ | |
51 | movw %dx, %cx /* and finally c|c|c|c */ | |
52 | ||
53 | /* Before we start with the main loop we process single bytes | |
54 | until the source pointer is aligned. This has two reasons: | |
55 | 1. aligned 32-bit memory access is faster | |
56 | and (more important) | |
57 | 2. we process in the main loop 32 bit in one step although | |
58 | we don't know the end of the string. But accessing at | |
59 | 4-byte alignment guarantees that we never access illegal | |
60 | memory if this would not also be done by the trivial | |
6d52618b | 61 | implementation (this is because all processor inherent |
8f5ca04b RM |
62 | boundaries are multiples of 4. */ |
63 | ||
f8adc70c | 64 | testl $3, %esi /* correctly aligned ? */ |
5929563f | 65 | jz L(19) /* yes => begin loop */ |
8f5ca04b RM |
66 | movb (%esi), %dl /* load byte in question (we need it twice) */ |
67 | cmpb %dl, %cl /* compare byte */ | |
5929563f | 68 | jne L(11) /* target found => return */ |
8f5ca04b | 69 | movl %esi, %eax /* remember pointer as possible result */ |
5929563f UD |
70 | L(11): orb %dl, %dl /* is NUL? */ |
71 | jz L(2) /* yes => return NULL */ | |
8f5ca04b RM |
72 | incl %esi /* increment pointer */ |
73 | ||
f8adc70c | 74 | testl $3, %esi /* correctly aligned ? */ |
5929563f | 75 | jz L(19) /* yes => begin loop */ |
8f5ca04b RM |
76 | movb (%esi), %dl /* load byte in question (we need it twice) */ |
77 | cmpb %dl, %cl /* compare byte */ | |
5929563f | 78 | jne L(12) /* target found => return */ |
8f5ca04b | 79 | movl %esi, %eax /* remember pointer as result */ |
5929563f UD |
80 | L(12): orb %dl, %dl /* is NUL? */ |
81 | jz L(2) /* yes => return NULL */ | |
8f5ca04b RM |
82 | incl %esi /* increment pointer */ |
83 | ||
f8adc70c | 84 | testl $3, %esi /* correctly aligned ? */ |
5929563f | 85 | jz L(19) /* yes => begin loop */ |
8f5ca04b RM |
86 | movb (%esi), %dl /* load byte in question (we need it twice) */ |
87 | cmpb %dl, %cl /* compare byte */ | |
5929563f | 88 | jne L(13) /* target found => return */ |
8f5ca04b | 89 | movl %esi, %eax /* remember pointer as result */ |
5929563f UD |
90 | L(13): orb %dl, %dl /* is NUL? */ |
91 | jz L(2) /* yes => return NULL */ | |
8f5ca04b RM |
92 | incl %esi /* increment pointer */ |
93 | ||
94 | /* No we have reached alignment. */ | |
5929563f | 95 | jmp L(19) /* begin loop */ |
8f5ca04b RM |
96 | |
97 | /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to | |
98 | change any of the hole bits of LONGWORD. | |
99 | ||
100 | 1) Is this safe? Will it catch all the zero bytes? | |
101 | Suppose there is a byte with all zeros. Any carry bits | |
102 | propagating from its left will fall into the hole at its | |
103 | least significant bit and stop. Since there will be no | |
104 | carry from its most significant bit, the LSB of the | |
105 | byte to the left will be unchanged, and the zero will be | |
106 | detected. | |
107 | ||
108 | 2) Is this worthwhile? Will it ignore everything except | |
109 | zero bytes? Suppose every byte of LONGWORD has a bit set | |
110 | somewhere. There will be a carry into bit 8. If bit 8 | |
111 | is set, this will carry into bit 16. If bit 8 is clear, | |
112 | one of bits 9-15 must be set, so there will be a carry | |
113 | into bit 16. Similarly, there will be a carry into bit | |
114 | 24. If one of bits 24-31 is set, there will be a carry | |
115 | into bit 32 (=carry flag), so all of the hole bits will | |
116 | be changed. | |
117 | ||
118 | 3) But wait! Aren't we looking for C, not zero? | |
119 | Good point. So what we do is XOR LONGWORD with a longword, | |
120 | each of whose bytes is C. This turns each byte that is C | |
121 | into a zero. */ | |
122 | ||
123 | /* Each round the main loop processes 16 bytes. */ | |
124 | ||
125 | /* Jump to here when the character is detected. We chose this | |
126 | way around because the character one is looking for is not | |
127 | as frequent as the rest and taking a conditional jump is more | |
128 | expensive than ignoring it. | |
129 | ||
130 | Some more words to the code below: it might not be obvious why | |
131 | we decrement the source pointer here. In the loop the pointer | |
132 | is not pre-incremented and so it still points before the word | |
133 | we are looking at. But you should take a look at the instruction | |
134 | which gets executed before we get into the loop: `addl $16, %esi'. | |
135 | This makes the following subs into adds. */ | |
136 | ||
137 | /* These fill bytes make the main loop be correctly aligned. | |
138 | We cannot use align because it is not the following instruction | |
139 | which should be aligned. */ | |
569c558c UD |
140 | .byte 0, 0 |
141 | #ifndef PROF | |
142 | /* Profiling adds some code and so changes the alignment. */ | |
143 | .byte 0 | |
144 | #endif | |
8f5ca04b | 145 | |
5929563f UD |
146 | L(4): subl $4, %esi /* adjust pointer */ |
147 | L(41): subl $4, %esi | |
148 | L(42): subl $4, %esi | |
149 | L(43): testl $0xff000000, %edx /* is highest byte == C? */ | |
150 | jnz L(33) /* no => try other bytes */ | |
8f5ca04b | 151 | leal 15(%esi), %eax /* store address as result */ |
5929563f | 152 | jmp L(1) /* and start loop again */ |
8f5ca04b | 153 | |
5929563f UD |
154 | L(3): subl $4, %esi /* adjust pointer */ |
155 | L(31): subl $4, %esi | |
156 | L(32): subl $4, %esi | |
157 | L(33): testl $0xff0000, %edx /* is C in third byte? */ | |
158 | jnz L(51) /* no => try other bytes */ | |
8f5ca04b | 159 | leal 14(%esi), %eax /* store address as result */ |
5929563f | 160 | jmp L(1) /* and start loop again */ |
8f5ca04b | 161 | |
5929563f | 162 | L(51): |
8f5ca04b RM |
163 | /* At this point we know that the byte is in one of the lower bytes. |
164 | We make a guess and correct it if necessary. This reduces the | |
165 | number of necessary jumps. */ | |
166 | leal 12(%esi), %eax /* guess address of lowest byte as result */ | |
167 | testb %dh, %dh /* is guess correct? */ | |
5929563f | 168 | jnz L(1) /* yes => start loop */ |
8f5ca04b RM |
169 | leal 13(%esi), %eax /* correct guess to second byte */ |
170 | ||
5929563f | 171 | L(1): addl $16, %esi /* increment pointer for full round */ |
8f5ca04b | 172 | |
5929563f | 173 | L(19): movl (%esi), %edx /* get word (= 4 bytes) in question */ |
8f5ca04b RM |
174 | movl $0xfefefeff, %edi /* magic value */ |
175 | addl %edx, %edi /* add the magic value to the word. We get | |
176 | carry bits reported for each byte which | |
177 | is *not* 0 */ | |
178 | ||
179 | /* According to the algorithm we had to reverse the effect of the | |
180 | XOR first and then test the overflow bits. But because the | |
181 | following XOR would destroy the carry flag and it would (in a | |
182 | representation with more than 32 bits) not alter then last | |
183 | overflow, we can now test this condition. If no carry is signaled | |
6d52618b | 184 | no overflow must have occurred in the last byte => it was 0. */ |
8f5ca04b | 185 | |
5929563f | 186 | jnc L(20) /* found NUL => check last word */ |
8f5ca04b RM |
187 | |
188 | /* We are only interested in carry bits that change due to the | |
189 | previous add, so remove original bits */ | |
190 | xorl %edx, %edi /* (word+magic)^word */ | |
191 | ||
192 | /* Now test for the other three overflow bits. */ | |
193 | orl $0xfefefeff, %edi /* set all non-carry bits */ | |
194 | incl %edi /* add 1: if one carry bit was *not* set | |
195 | the addition will not result in 0. */ | |
196 | ||
197 | /* If at least one byte of the word is C we don't get 0 in %edi. */ | |
5929563f | 198 | jnz L(20) /* found NUL => check last word */ |
8f5ca04b RM |
199 | |
200 | /* Now we made sure the dword does not contain the character we are | |
201 | looking for. But because we deal with strings we have to check | |
202 | for the end of string before testing the next dword. */ | |
203 | ||
204 | xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c | |
205 | are now 0 */ | |
206 | movl $0xfefefeff, %edi /* magic value */ | |
207 | addl %edx, %edi /* add the magic value to the word. We get | |
208 | carry bits reported for each byte which | |
209 | is *not* 0 */ | |
5929563f | 210 | jnc L(4) /* highest byte is C => examine dword */ |
8f5ca04b RM |
211 | xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */ |
212 | orl $0xfefefeff, %edi /* set all non-carry bits */ | |
213 | incl %edi /* add 1: if one carry bit was *not* set | |
214 | the addition will not result in 0. */ | |
5929563f | 215 | jnz L(3) /* C is detected in the word => examine it */ |
8f5ca04b RM |
216 | |
217 | movl 4(%esi), %edx /* get word (= 4 bytes) in question */ | |
218 | movl $0xfefefeff, %edi /* magic value */ | |
219 | addl %edx, %edi /* add the magic value to the word. We get | |
220 | carry bits reported for each byte which | |
221 | is *not* 0 */ | |
5929563f | 222 | jnc L(21) /* found NUL => check last word */ |
8f5ca04b RM |
223 | xorl %edx, %edi /* (word+magic)^word */ |
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. */ | |
5929563f | 227 | jnz L(21) /* found NUL => check last word */ |
8f5ca04b RM |
228 | xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c |
229 | are now 0 */ | |
230 | movl $0xfefefeff, %edi /* magic value */ | |
231 | addl %edx, %edi /* add the magic value to the word. We get | |
232 | carry bits reported for each byte which | |
233 | is *not* 0 */ | |
5929563f | 234 | jnc L(41) /* highest byte is C => examine dword */ |
8f5ca04b RM |
235 | xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */ |
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. */ | |
5929563f | 239 | jnz L(31) /* C is detected in the word => examine it */ |
8f5ca04b RM |
240 | |
241 | movl 8(%esi), %edx /* get word (= 4 bytes) in question */ | |
242 | movl $0xfefefeff, %edi /* magic value */ | |
243 | addl %edx, %edi /* add the magic value to the word. We get | |
244 | carry bits reported for each byte which | |
245 | is *not* 0 */ | |
5929563f | 246 | jnc L(22) /* found NUL => check last word */ |
8f5ca04b RM |
247 | xorl %edx, %edi /* (word+magic)^word */ |
248 | orl $0xfefefeff, %edi /* set all non-carry bits */ | |
249 | incl %edi /* add 1: if one carry bit was *not* set | |
250 | the addition will not result in 0. */ | |
5929563f | 251 | jnz L(22) /* found NUL => check last word */ |
8f5ca04b RM |
252 | xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c |
253 | are now 0 */ | |
254 | movl $0xfefefeff, %edi /* magic value */ | |
255 | addl %edx, %edi /* add the magic value to the word. We get | |
256 | carry bits reported for each byte which | |
257 | is *not* 0 */ | |
5929563f | 258 | jnc L(42) /* highest byte is C => examine dword */ |
8f5ca04b RM |
259 | xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */ |
260 | orl $0xfefefeff, %edi /* set all non-carry bits */ | |
261 | incl %edi /* add 1: if one carry bit was *not* set | |
262 | the addition will not result in 0. */ | |
5929563f | 263 | jnz L(32) /* C is detected in the word => examine it */ |
8f5ca04b RM |
264 | |
265 | movl 12(%esi), %edx /* get word (= 4 bytes) in question */ | |
266 | movl $0xfefefeff, %edi /* magic value */ | |
267 | addl %edx, %edi /* add the magic value to the word. We get | |
268 | carry bits reported for each byte which | |
269 | is *not* 0 */ | |
5929563f | 270 | jnc L(23) /* found NUL => check last word */ |
8f5ca04b RM |
271 | xorl %edx, %edi /* (word+magic)^word */ |
272 | orl $0xfefefeff, %edi /* set all non-carry bits */ | |
273 | incl %edi /* add 1: if one carry bit was *not* set | |
274 | the addition will not result in 0. */ | |
5929563f | 275 | jnz L(23) /* found NUL => check last word */ |
8f5ca04b RM |
276 | xorl %ecx, %edx /* XOR with word c|c|c|c => bytes of str == c |
277 | are now 0 */ | |
278 | movl $0xfefefeff, %edi /* magic value */ | |
279 | addl %edx, %edi /* add the magic value to the word. We get | |
280 | carry bits reported for each byte which | |
281 | is *not* 0 */ | |
5929563f | 282 | jnc L(43) /* highest byte is C => examine dword */ |
8f5ca04b RM |
283 | xorl %edx, %edi /* ((word^charmask)+magic)^(word^charmask) */ |
284 | orl $0xfefefeff, %edi /* set all non-carry bits */ | |
285 | incl %edi /* add 1: if one carry bit was *not* set | |
286 | the addition will not result in 0. */ | |
5929563f UD |
287 | jz L(1) /* C is not detected => restart loop */ |
288 | jmp L(33) /* examine word */ | |
8f5ca04b | 289 | |
5929563f UD |
290 | L(23): addl $4, %esi /* adjust pointer */ |
291 | L(22): addl $4, %esi | |
292 | L(21): addl $4, %esi | |
8f5ca04b RM |
293 | |
294 | /* What remains to do is to test which byte the NUL char is and | |
295 | whether the searched character appears in one of the bytes | |
296 | before. A special case is that the searched byte maybe NUL. | |
297 | In this case a pointer to the terminating NUL char has to be | |
298 | returned. */ | |
299 | ||
5929563f | 300 | L(20): cmpb %cl, %dl /* is first byte == C? */ |
1ad9da69 | 301 | jne L(24) /* no => skip */ |
8f5ca04b | 302 | movl %esi, %eax /* store address as result */ |
5929563f UD |
303 | L(24): testb %dl, %dl /* is first byte == NUL? */ |
304 | jz L(2) /* yes => return */ | |
8f5ca04b RM |
305 | |
306 | cmpb %cl, %dh /* is second byte == C? */ | |
1ad9da69 | 307 | jne L(25) /* no => skip */ |
8f5ca04b | 308 | leal 1(%esi), %eax /* store address as result */ |
5929563f UD |
309 | L(25): testb %dh, %dh /* is second byte == NUL? */ |
310 | jz L(2) /* yes => return */ | |
8f5ca04b RM |
311 | |
312 | shrl $16,%edx /* make upper bytes accessible */ | |
313 | cmpb %cl, %dl /* is third byte == C */ | |
1ad9da69 | 314 | jne L(26) /* no => skip */ |
8f5ca04b | 315 | leal 2(%esi), %eax /* store address as result */ |
5929563f UD |
316 | L(26): testb %dl, %dl /* is third byte == NUL */ |
317 | jz L(2) /* yes => return */ | |
8f5ca04b RM |
318 | |
319 | cmpb %cl, %dh /* is fourth byte == C */ | |
5929563f | 320 | jne L(2) /* no => skip */ |
8f5ca04b RM |
321 | leal 3(%esi), %eax /* store address as result */ |
322 | ||
92945b52 | 323 | L(2): popl %esi /* restore saved register content */ |
1ad9da69 UD |
324 | cfi_adjust_cfa_offset (-4) |
325 | cfi_restore (esi) | |
8f5ca04b | 326 | popl %edi |
1ad9da69 UD |
327 | cfi_adjust_cfa_offset (-4) |
328 | cfi_restore (edi) | |
8f5ca04b | 329 | |
2366713d JM |
330 | ret |
331 | END (strrchr) | |
8f5ca04b | 332 | |
2366713d | 333 | weak_alias (strrchr, rindex) |
85dd1003 | 334 | libc_hidden_builtin_def (strrchr) |