2006-02-24 Roland McGrath <roland@redhat.com>
[kopensolaris-gnu/glibc.git] / sysdeps / x86_64 / strchr.S
1 /* strchr (str, ch) -- Return pointer to first occurrence of CH in STR.
2    For AMD x86-64.
3    Copyright (C) 2002, 2005 Free Software Foundation, Inc.
4    This file is part of the GNU C Library.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, write to the Free
18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19    02111-1307 USA.  */
20
21 #include <sysdep.h>
22 #include "asm-syntax.h"
23 #include "bp-sym.h"
24 #include "bp-asm.h"
25
26
27         .text
28 ENTRY (BP_SYM (strchr))
29
30         /* Before we start with the main loop we process single bytes
31            until the source pointer is aligned.  This has two reasons:
32            1. aligned 64-bit memory access is faster
33            and (more important)
34            2. we process in the main loop 64 bit in one step although
35               we don't know the end of the string.  But accessing at
36               8-byte alignment guarantees that we never access illegal
37               memory if this would not also be done by the trivial
38               implementation (this is because all processor inherent
39               boundaries are multiples of 8).  */
40
41         movq    %rdi, %rdx
42         andl    $7, %edx        /* Mask alignment bits  */
43         movq    %rdi, %rax      /* duplicate destination.  */
44         jz      1f              /* aligned => start loop */
45         neg     %edx
46         addl    $8, %edx        /* Align to 8 bytes.  */
47
48         /* Search the first bytes directly.  */
49 0:      movb    (%rax), %cl     /* load byte  */
50         cmpb    %cl,%sil        /* compare byte.  */
51         je      6f              /* target found */
52         testb   %cl,%cl         /* is byte NUL? */
53         je      7f              /* yes => return NULL */
54         incq    %rax            /* increment pointer */
55         decl    %edx
56         jnz     0b
57
58
59 1:
60         /* At the moment %rsi contains C.  What we need for the
61            algorithm is C in all bytes of the register.  Avoid
62            operations on 16 bit words because these require an
63            prefix byte (and one more cycle).  */
64         /* Populate 8 bit data to full 64-bit.  */
65         movabs  $0x0101010101010101,%r9
66         movzbl  %sil,%edx
67         imul    %rdx,%r9
68
69         movq $0xfefefefefefefeff, %r8 /* Save magic.  */
70
71       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
72          change any of the hole bits of LONGWORD.
73
74          1) Is this safe?  Will it catch all the zero bytes?
75          Suppose there is a byte with all zeros.  Any carry bits
76          propagating from its left will fall into the hole at its
77          least significant bit and stop.  Since there will be no
78          carry from its most significant bit, the LSB of the
79          byte to the left will be unchanged, and the zero will be
80          detected.
81
82          2) Is this worthwhile?  Will it ignore everything except
83          zero bytes?  Suppose every byte of QUARDWORD has a bit set
84          somewhere.  There will be a carry into bit 8.  If bit 8
85          is set, this will carry into bit 16.  If bit 8 is clear,
86          one of bits 9-15 must be set, so there will be a carry
87          into bit 16.  Similarly, there will be a carry into bit
88          24 tec..  If one of bits 54-63 is set, there will be a carry
89          into bit 64 (=carry flag), so all of the hole bits will
90          be changed.
91
92          3) But wait!  Aren't we looking for C, not zero?
93          Good point.  So what we do is XOR LONGWORD with a longword,
94          each of whose bytes is C.  This turns each byte that is C
95          into a zero.  */
96
97         .p2align 4
98 4:
99         /* Main Loop is unrolled 4 times.  */
100         /* First unroll.  */
101         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
102         addq $8,%rax            /* adjust pointer for next word */
103         movq %r8, %rdx          /* magic value */
104         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
105                                    are now 0 */
106         addq %rcx, %rdx         /* add the magic value to the word.  We get
107                                    carry bits reported for each byte which
108                                    is *not* 0 */
109         jnc 3f                  /* highest byte is NUL => return pointer */
110         xorq %rcx, %rdx         /* (word+magic)^word */
111         orq %r8, %rdx           /* set all non-carry bits */
112         incq %rdx               /* add 1: if one carry bit was *not* set
113                                    the addition will not result in 0.  */
114         jnz 3f                  /* found c => return pointer */
115
116         /* The quadword we looked at does not contain the value we're looking
117            for.  Let's search now whether we have reached the end of the
118            string.  */
119         xorq %r9, %rcx          /* restore original dword without reload */
120         movq %r8, %rdx          /* magic value */
121         addq %rcx, %rdx         /* add the magic value to the word.  We get
122                                    carry bits reported for each byte which
123                                    is *not* 0 */
124         jnc 7f                  /* highest byte is NUL => return NULL */
125         xorq %rcx, %rdx         /* (word+magic)^word */
126         orq %r8, %rdx           /* set all non-carry bits */
127         incq %rdx               /* add 1: if one carry bit was *not* set
128                                    the addition will not result in 0.  */
129         jnz 7f                  /* found NUL => return NULL */
130
131         /* Second unroll.  */
132         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
133         addq $8,%rax            /* adjust pointer for next word */
134         movq %r8, %rdx          /* magic value */
135         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
136                                    are now 0 */
137         addq %rcx, %rdx         /* add the magic value to the word.  We get
138                                    carry bits reported for each byte which
139                                    is *not* 0 */
140         jnc 3f                  /* highest byte is NUL => return pointer */
141         xorq %rcx, %rdx         /* (word+magic)^word */
142         orq %r8, %rdx           /* set all non-carry bits */
143         incq %rdx               /* add 1: if one carry bit was *not* set
144                                    the addition will not result in 0.  */
145         jnz 3f                  /* found c => return pointer */
146
147         /* The quadword we looked at does not contain the value we're looking
148            for.  Let's search now whether we have reached the end of the
149            string.  */
150         xorq %r9, %rcx          /* restore original dword without reload */
151         movq %r8, %rdx          /* magic value */
152         addq %rcx, %rdx         /* add the magic value to the word.  We get
153                                    carry bits reported for each byte which
154                                    is *not* 0 */
155         jnc 7f                  /* highest byte is NUL => return NULL */
156         xorq %rcx, %rdx         /* (word+magic)^word */
157         orq %r8, %rdx           /* set all non-carry bits */
158         incq %rdx               /* add 1: if one carry bit was *not* set
159                                    the addition will not result in 0.  */
160         jnz 7f                  /* found NUL => return NULL */
161         /* Third unroll.  */
162         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
163         addq $8,%rax            /* adjust pointer for next word */
164         movq %r8, %rdx          /* magic value */
165         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
166                                    are now 0 */
167         addq %rcx, %rdx         /* add the magic value to the word.  We get
168                                    carry bits reported for each byte which
169                                    is *not* 0 */
170         jnc 3f                  /* highest byte is NUL => return pointer */
171         xorq %rcx, %rdx         /* (word+magic)^word */
172         orq %r8, %rdx           /* set all non-carry bits */
173         incq %rdx               /* add 1: if one carry bit was *not* set
174                                    the addition will not result in 0.  */
175         jnz 3f                  /* found c => return pointer */
176
177         /* The quadword we looked at does not contain the value we're looking
178            for.  Let's search now whether we have reached the end of the
179            string.  */
180         xorq %r9, %rcx          /* restore original dword without reload */
181         movq %r8, %rdx          /* magic value */
182         addq %rcx, %rdx         /* add the magic value to the word.  We get
183                                    carry bits reported for each byte which
184                                    is *not* 0 */
185         jnc 7f                  /* highest byte is NUL => return NULL */
186         xorq %rcx, %rdx         /* (word+magic)^word */
187         orq %r8, %rdx           /* set all non-carry bits */
188         incq %rdx               /* add 1: if one carry bit was *not* set
189                                    the addition will not result in 0.  */
190         jnz 7f                  /* found NUL => return NULL */
191         /* Fourth unroll.  */
192         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
193         addq $8,%rax            /* adjust pointer for next word */
194         movq %r8, %rdx          /* magic value */
195         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
196                                    are now 0 */
197         addq %rcx, %rdx         /* add the magic value to the word.  We get
198                                    carry bits reported for each byte which
199                                    is *not* 0 */
200         jnc 3f                  /* highest byte is NUL => return pointer */
201         xorq %rcx, %rdx         /* (word+magic)^word */
202         orq %r8, %rdx           /* set all non-carry bits */
203         incq %rdx               /* add 1: if one carry bit was *not* set
204                                    the addition will not result in 0.  */
205         jnz 3f                  /* found c => return pointer */
206
207         /* The quadword we looked at does not contain the value we're looking
208            for.  Let's search now whether we have reached the end of the
209            string.  */
210         xorq %r9, %rcx          /* restore original dword without reload */
211         movq %r8, %rdx          /* magic value */
212         addq %rcx, %rdx         /* add the magic value to the word.  We get
213                                    carry bits reported for each byte which
214                                    is *not* 0 */
215         jnc 7f                  /* highest byte is NUL => return NULL */
216         xorq %rcx, %rdx         /* (word+magic)^word */
217         orq %r8, %rdx           /* set all non-carry bits */
218         incq %rdx               /* add 1: if one carry bit was *not* set
219                                    the addition will not result in 0.  */
220         jz 4b                   /* no NUL found => restart loop */
221
222
223 7:      /* Return NULL.  */
224         xorl %eax, %eax
225         retq
226
227
228         /* We now scan for the byte in which the character was matched.
229            But we have to take care of the case that a NUL char is
230            found before this in the dword.  Note that we XORed %rcx
231            with the byte we're looking for, therefore the tests below look
232            reversed.  */
233
234
235         .p2align 4              /* Align, it's a jump target.  */
236 3:      movq    %r9,%rdx        /* move to %rdx so that we can access bytes */
237         subq    $8,%rax         /* correct pointer increment.  */
238         testb %cl, %cl          /* is first byte C? */
239         jz 6f                   /* yes => return pointer */
240         cmpb %dl, %cl           /* is first byte NUL? */
241         je 7b                   /* yes => return NULL */
242         incq %rax               /* increment pointer */
243
244         testb %ch, %ch          /* is second byte C? */
245         jz 6f                   /* yes => return pointer */
246         cmpb %dl, %ch           /* is second byte NUL? */
247         je 7b                   /* yes => return NULL? */
248         incq %rax               /* increment pointer */
249
250         shrq $16, %rcx          /* make upper bytes accessible */
251         testb %cl, %cl          /* is third byte C? */
252         jz 6f                   /* yes => return pointer */
253         cmpb %dl, %cl           /* is third byte NUL? */
254         je 7b                   /* yes => return NULL */
255         incq %rax               /* increment pointer */
256
257         testb %ch, %ch          /* is fourth byte C? */
258         jz 6f                   /* yes => return pointer */
259         cmpb %dl, %ch           /* is fourth byte NUL? */
260         je 7b                   /* yes => return NULL? */
261         incq %rax               /* increment pointer */
262
263         shrq $16, %rcx          /* make upper bytes accessible */
264         testb %cl, %cl          /* is fifth byte C? */
265         jz 6f                   /* yes => return pointer */
266         cmpb %dl, %cl           /* is fifth byte NUL? */
267         je 7b                   /* yes => return NULL */
268         incq %rax               /* increment pointer */
269
270         testb %ch, %ch          /* is sixth byte C? */
271         jz 6f                   /* yes => return pointer */
272         cmpb %dl, %ch           /* is sixth byte NUL? */
273         je 7b                   /* yes => return NULL? */
274         incq %rax               /* increment pointer */
275
276         shrq $16, %rcx          /* make upper bytes accessible */
277         testb %cl, %cl          /* is seventh byte C? */
278         jz 6f                   /* yes => return pointer */
279         cmpb %dl, %cl           /* is seventh byte NUL? */
280         je 7b                   /* yes => return NULL */
281
282         /* It must be in the eigth byte and it cannot be NUL.  */
283         incq %rax
284
285 6:
286         nop
287         retq
288 END (BP_SYM (strchr))
289
290 weak_alias (BP_SYM (strchr), BP_SYM (index))
291 libc_hidden_builtin_def (strchr)