Mon Jun 24 19:57:01 1996 Roland McGrath <roland@delasyd.gnu.ai.mit.edu>
[kopensolaris-gnu/glibc.git] / sysdeps / i386 / strchr.S
1 /* strchr (str, ch) -- Return pointer to first occurrence of CH in STR.
2 For Intel 80x86, x>=3.
3 Copyright (C) 1994, 1995 Free Software Foundation, Inc.
4 Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>
5 Some optimisations by Alan Modra <Alan@SPRI.Levels.UniSA.Edu.Au>
6 This file is part of the GNU C Library.
7
8 The GNU C Library is free software; you can redistribute it and/or
9 modify it under the terms of the GNU Library General Public License as
10 published by the Free Software Foundation; either version 2 of the
11 License, or (at your option) any later version.
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
16 Library General Public License for more details.
17
18 You should have received a copy of the GNU Library General Public
19 License along with the GNU C Library; see the file COPYING.LIB.  If
20 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA.  */
22
23 #include <sysdep.h>
24 #include "asm-syntax.h"
25
26 /*
27    INPUT PARAMETERS:
28    str          (sp + 4)
29    ch           (sp + 8)
30 */
31
32         .text
33 ENTRY (strchr)
34         pushl %edi              /* Save callee-safe registers used here.  */
35
36         movl 8(%esp), %eax      /* get string pointer */
37         movl 12(%esp), %edx     /* get character we are looking for */
38
39         /* At the moment %edx contains C.  What we need for the
40            algorithm is C 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 inherant
57               boundaries are multiples of 4.  */
58
59         testb $3, %eax          /* correctly aligned ? */
60         jz L11                  /* yes => begin loop */
61         movb (%eax), %cl        /* load byte in question (we need it twice) */
62         cmpb %cl, %dl           /* compare byte */
63         je L6                   /* target found => return */
64         testb %cl, %cl          /* is NUL? */
65         jz L2                   /* yes => return NULL */
66         incl %eax               /* increment pointer */
67
68         testb $3, %eax          /* correctly aligned ? */
69         jz L11                  /* yes => begin loop */
70         movb (%eax), %cl        /* load byte in question (we need it twice) */
71         cmpb %cl, %dl           /* compare byte */
72         je L6                   /* target found => return */
73         testb %cl, %cl          /* is NUL? */
74         jz L2                   /* yes => return NULL */
75         incl %eax               /* increment pointer */
76
77         testb $3, %eax          /* correctly aligned ? */
78         jz L11                  /* yes => begin loop */
79         movb (%eax), %cl        /* load byte in question (we need it twice) */
80         cmpb %cl, %dl           /* compare byte */
81         je L6                   /* target found => return */
82         testb %cl, %cl          /* is NUL? */
83         jz L2                   /* yes => return NULL */
84         incl %eax               /* increment pointer */
85
86         /* No we have reached alignment.  */
87         jmp L11                 /* 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 C, not zero?
111          Good point.  So what we do is XOR LONGWORD with a longword,
112          each of whose bytes is C.  This turns each byte that is C
113          into a zero.  */
114
115         /* Each round the main loop processes 16 bytes.  */
116
117         ALIGN(4)
118
119 L1:     addl $16, %eax          /* adjust pointer for whole round */
120
121 L11:    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* C */
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 occured in the last byte => it was 0.  */
135         jnc L7
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 C we don't get 0 in %edi.  */
147         jnz L7                  /* 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 L2                  /* 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 L2                  /* 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* C */
172         jnc L71                 /* highest byte is C => 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 L71                 /* 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 L2                  /* 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 L2                  /* 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* C */
197         jnc L72                 /* highest byte is C => 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 L72                 /* 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 L2                  /* 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 L2                  /* 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* C */
222         jnc L73                 /* highest byte is C => 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 L73                 /* 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 L2                  /* 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 L1                   /* no NUL found => restart loop */
239
240 L2:     /* Return NULL.  */
241         xorl %eax, %eax         /* load NULL in return value register */
242         popl %edi               /* restore saved register content */
243         ret
244
245 L73:    addl $4, %eax           /* adjust pointer */
246 L72:    addl $4, %eax
247 L71:    addl $4, %eax
248
249         /* We now scan for the byte in which the character was matched.
250            But we have to take care of the case that a NUL char is
251            found before this in the dword.  */
252
253 L7:     testb %cl, %cl          /* is first byte C? */
254         jz L6                   /* yes => return pointer */
255         cmpb %dl, %cl           /* is first byte NUL? */
256         je L2                   /* yes => return NULL */
257         incl %eax               /* it's not in the first byte */
258
259         testb %ch, %ch          /* is second byte C? */
260         jz L6                   /* yes => return pointer */
261         cmpb %dl, %ch           /* is second byte NUL? */
262         je L2                   /* yes => return NULL? */
263         incl %eax               /* it's not in the second byte */
264
265         shrl $16, %ecx          /* make upper byte accessible */
266         testb %cl, %cl          /* is third byte C? */
267         jz L6                   /* yes => return pointer */
268         cmpb %dl, %cl           /* is third byte NUL? */
269         je L2                   /* yes => return NULL */
270
271         /* It must be in the fourth byte and it cannot be NUL.  */
272         incl %eax
273
274 L6:     popl %edi               /* restore saved register content */
275
276         ret
277
278 weak_alias (strchr, index)