1 /* strchr -- find character CH in a NUL terminated string.
2 Highly optimized version for ix85, x>=5.
3 Copyright (C) 1995, 1996 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
5 Contributed by Ulrich Drepper, <drepper@gnu.ai.mit.edu>.
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public License as
9 published by the Free Software Foundation; either version 2 of the
10 License, or (at your option) any later version.
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 Library General Public License for more details.
17 You should have received a copy of the GNU Library General Public
18 License along with the GNU C Library; see the file COPYING.LIB. If
19 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 /* This version is especially optimized for the i586 (and following?)
25 processors. This is mainly done by using the two pipelines. The
26 version optimized for i486 is weak in this aspect because to get
27 as much parallelism we have to executs some *more* instructions.
29 The code below is structured to reflect the pairing of the instructions
30 as *I think* it is. I have no processor data book to verify this.
31 If you find something you think is incorrect let me know. */
34 /* The magic value which is used throughout in the whole code. */
35 #define magic 0xfefefeff
45 pushl %edi /* Save callee-safe registers. */
51 movl 20(%esp), %eax /* get string pointer */
52 movl 24(%esp), %edx /* get character we are looking for */
54 movl %eax, %edi /* duplicate string pointer for later */
55 xorl %ecx, %ecx /* clear %ecx */
57 /* At the moment %edx contains C. What we need for the
58 algorithm is C in all bytes of the dword. Avoid
59 operations on 16 bit words because these require an
60 prefix byte (and one more cycle). */
61 movb %dl, %dh /* now it is 0|0|c|c */
62 movb %dl, %cl /* we construct the lower half in %ecx */
64 shll $16, %edx /* now %edx is c|c|0|0 */
65 movb %cl, %ch /* now %ecx is 0|0|c|c */
67 orl %ecx, %edx /* and finally c|c|c|c */
68 andl $3, %edi /* mask alignment bits */
70 jz L11 /* alignment is 0 => start loop */
72 movb %dl, %cl /* 0 is needed below */
73 jp L0 /* exactly two bits set */
75 xorb (%eax), %cl /* is byte the one we are looking for? */
76 jz L2 /* yes => return pointer */
78 xorb %dl, %cl /* load single byte and test for NUL */
79 je L3 /* yes => return NULL */
81 movb 1(%eax), %cl /* load single byte */
84 cmpb %cl, %dl /* is byte == C? */
85 je L2 /* aligned => return pointer */
87 cmpb $0, %cl /* is byte NUL? */
88 je L3 /* yes => return NULL */
95 L0: movb (%eax), %cl /* load single byte */
97 cmpb %cl, %dl /* is byte == C? */
98 je L2 /* aligned => return pointer */
100 cmpb $0, %cl /* is byte NUL? */
101 je L3 /* yes => return NULL */
103 incl %eax /* increment pointer */
105 /* The following code is the preparation for the loop. The
106 four instruction up to `L1' will not be executed in the loop
107 because the same code is found at the end of the loop, but
108 there it is executed in parallel with other instructions. */
109 L11: movl (%eax), %ecx
115 /* The main loop: it looks complex and indeed it is. I would
116 love to say `it was hard to write, so it should he hard to
117 read' but I will give some more hints. To fully understand
118 this code you should first take a look at the i486 version.
119 The basic algorithm is the same, but here the code organized
120 in a way which permits to use both pipelines all the time.
122 I tried to make it a bit more understandable by indenting
123 the code according to stage in the algorithm. It goes as
125 check for 0 in 1st word
126 check for C in 1st word
127 check for 0 in 2nd word
128 check for C in 2nd word
129 check for 0 in 3rd word
130 check for C in 3rd word
131 check for 0 in 4th word
132 check for C in 4th word
134 Please note that doing the test for NUL before the test for
135 C allows us to overlap the test for 0 in the next word with
138 L1: xorl %ecx, %ebp /* (word^magic) */
139 addl %ecx, %edi /* add magic word */
141 leal 4(%eax), %eax /* increment pointer */
142 jnc L4 /* previous addl caused overflow? */
144 movl %ecx, %ebx /* duplicate original word */
145 orl $magic, %ebp /* (word^magic)|magic */
147 addl $1, %ebp /* (word^magic)|magic == 0xffffffff? */
148 jne L4 /* yes => we found word with NUL */
150 movl $magic, %esi /* load magic value */
151 xorl %edx, %ebx /* clear words which are C */
154 addl %ebx, %esi /* (word+magic) */
157 jnc L5 /* previous addl caused overflow? */
160 xorl %ebx, %esi /* (word+magic)^word */
163 orl $magic, %esi /* ((word+magic)^word)|magic */
165 addl $1, %esi /* ((word+magic)^word)|magic==0xf..f?*/
166 jne L5 /* yes => we found word with C */
259 /* We know there is no NUL byte but a C byte in the word.
260 %ebx contains NUL in this particular byte. */
261 L5: subl $4, %eax /* adjust pointer */
262 testb %bl, %bl /* first byte == C? */
264 jz L2 /* yes => return pointer */
266 incl %eax /* increment pointer */
267 testb %bh, %bh /* second byte == C? */
269 jz L2 /* yes => return pointer */
271 shrl $16, %ebx /* make upper bytes accessible */
272 incl %eax /* increment pointer */
274 cmp $0, %bl /* third byte == C */
275 je L2 /* yes => return pointer */
277 incl %eax /* increment pointer */
279 L2: popl %ebp /* restore saved registers */
287 /* We know there is a NUL byte in the word. But we have to test
288 whether there is an C byte before it in the word. */
289 L4: subl $4, %eax /* adjust pointer */
290 cmpb %dl, %cl /* first byte == C? */
292 je L2 /* yes => return pointer */
294 cmpb $0, %cl /* first byte == NUL? */
295 je L3 /* yes => return NULL */
297 incl %eax /* increment pointer */
299 cmpb %dl, %ch /* second byte == C? */
300 je L2 /* yes => return pointer */
302 cmpb $0, %ch /* second byte == NUL? */
303 je L3 /* yes => return NULL */
305 shrl $16, %ecx /* make upper bytes accessible */
306 incl %eax /* increment pointer */
308 cmpb %dl, %cl /* third byte == C? */
309 je L2 /* yes => return pointer */
311 cmpb $0, %cl /* third byte == NUL? */
312 je L3 /* yes => return NULL */
314 incl %eax /* increment pointer */
316 /* The test four the fourth byte is necessary! */
317 cmpb %dl, %ch /* fourth byte == C? */
318 je L2 /* yes => return pointer */
320 L3: xorl %eax, %eax /* set return value = NULL */
322 popl %ebp /* restore saved registers */
332 weak_alias (strchr, index)