1 /* Find character CH in a NUL terminated string.
2 Highly optimized version for ix85, x>=5.
3 Copyright (C) 1995-2013 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 Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 2.1 of the 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 Lesser General Public License for more details.
17 You should have received a copy of the GNU Lesser General Public
18 License along with the GNU C Library; if not, see
19 <http://www.gnu.org/licenses/>. */
22 #include "asm-syntax.h"
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 execute 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
37 #define PARMS 4+16 /* space for 4 saved regs */
45 pushl %edi /* Save callee-safe registers. */
46 cfi_adjust_cfa_offset (-4)
48 cfi_adjust_cfa_offset (-4)
51 cfi_adjust_cfa_offset (-4)
53 cfi_adjust_cfa_offset (-4)
58 movl %eax, %edi /* duplicate string pointer for later */
59 cfi_rel_offset (edi, 12)
60 xorl %ecx, %ecx /* clear %ecx */
62 /* At the moment %edx contains C. What we need for the
63 algorithm is C in all bytes of the dword. Avoid
64 operations on 16 bit words because these require an
65 prefix byte (and one more cycle). */
66 movb %dl, %dh /* now it is 0|0|c|c */
67 movb %dl, %cl /* we construct the lower half in %ecx */
69 shll $16, %edx /* now %edx is c|c|0|0 */
70 movb %cl, %ch /* now %ecx is 0|0|c|c */
72 orl %ecx, %edx /* and finally c|c|c|c */
73 andl $3, %edi /* mask alignment bits */
75 jz L(11) /* alignment is 0 => start loop */
77 movb %dl, %cl /* 0 is needed below */
78 jp L(0) /* exactly two bits set */
80 xorb (%eax), %cl /* is byte the one we are looking for? */
81 jz L(out) /* yes => return pointer */
83 xorb %dl, %cl /* load single byte and test for NUL */
84 je L(3) /* yes => return NULL */
86 movb 1(%eax), %cl /* load single byte */
89 cmpb %cl, %dl /* is byte == C? */
90 je L(out) /* aligned => return pointer */
92 cmpb $0, %cl /* is byte NUL? */
93 je L(3) /* yes => return NULL */
100 L(0): movb (%eax), %cl /* load single byte */
102 cmpb %cl, %dl /* is byte == C? */
103 je L(out) /* aligned => return pointer */
105 cmpb $0, %cl /* is byte NUL? */
106 je L(3) /* yes => return NULL */
108 incl %eax /* increment pointer */
110 cfi_rel_offset (esi, 8)
111 cfi_rel_offset (ebx, 4)
112 cfi_rel_offset (ebp, 0)
114 /* The following code is the preparation for the loop. The
115 four instruction up to `L1' will not be executed in the loop
116 because the same code is found at the end of the loop, but
117 there it is executed in parallel with other instructions. */
118 L(11): movl (%eax), %ecx
124 /* The main loop: it looks complex and indeed it is. I would
125 love to say `it was hard to write, so it should he hard to
126 read' but I will give some more hints. To fully understand
127 this code you should first take a look at the i486 version.
128 The basic algorithm is the same, but here the code organized
129 in a way which permits to use both pipelines all the time.
131 I tried to make it a bit more understandable by indenting
132 the code according to stage in the algorithm. It goes as
134 check for 0 in 1st word
135 check for C in 1st word
136 check for 0 in 2nd word
137 check for C in 2nd word
138 check for 0 in 3rd word
139 check for C in 3rd word
140 check for 0 in 4th word
141 check for C in 4th word
143 Please note that doing the test for NUL before the test for
144 C allows us to overlap the test for 0 in the next word with
147 L(1): xorl %ecx, %ebp /* (word^magic) */
148 addl %ecx, %edi /* add magic word */
150 leal 4(%eax), %eax /* increment pointer */
151 jnc L(4) /* previous addl caused overflow? */
153 movl %ecx, %ebx /* duplicate original word */
154 orl $magic, %ebp /* (word^magic)|magic */
156 addl $1, %ebp /* (word^magic)|magic == 0xffffffff? */
157 jne L(4) /* yes => we found word with NUL */
159 movl $magic, %esi /* load magic value */
160 xorl %edx, %ebx /* clear words which are C */
163 addl %ebx, %esi /* (word+magic) */
166 jnc L(5) /* previous addl caused overflow? */
169 xorl %ebx, %esi /* (word+magic)^word */
172 orl $magic, %esi /* ((word+magic)^word)|magic */
174 addl $1, %esi /* ((word+magic)^word)|magic==0xf..f?*/
175 jne L(5) /* yes => we found word with C */
268 /* We know there is no NUL byte but a C byte in the word.
269 %ebx contains NUL in this particular byte. */
270 L(5): subl $4, %eax /* adjust pointer */
271 testb %bl, %bl /* first byte == C? */
273 jz L(out) /* yes => return pointer */
275 incl %eax /* increment pointer */
276 testb %bh, %bh /* second byte == C? */
278 jz L(out) /* yes => return pointer */
280 shrl $16, %ebx /* make upper bytes accessible */
281 incl %eax /* increment pointer */
283 cmp $0, %bl /* third byte == C */
284 je L(out) /* yes => return pointer */
286 incl %eax /* increment pointer */
288 L(out): popl %ebp /* restore saved registers */
289 cfi_adjust_cfa_offset (-4)
292 cfi_adjust_cfa_offset (-4)
296 cfi_adjust_cfa_offset (-4)
299 cfi_adjust_cfa_offset (-4)
304 cfi_adjust_cfa_offset (16)
305 cfi_rel_offset (edi, 12)
306 cfi_rel_offset (esi, 8)
307 cfi_rel_offset (ebx, 4)
308 cfi_rel_offset (ebp, 0)
309 /* We know there is a NUL byte in the word. But we have to test
310 whether there is an C byte before it in the word. */
311 L(4): subl $4, %eax /* adjust pointer */
312 cmpb %dl, %cl /* first byte == C? */
314 je L(out) /* yes => return pointer */
316 cmpb $0, %cl /* first byte == NUL? */
317 je L(3) /* yes => return NULL */
319 incl %eax /* increment pointer */
321 cmpb %dl, %ch /* second byte == C? */
322 je L(out) /* yes => return pointer */
324 cmpb $0, %ch /* second byte == NUL? */
325 je L(3) /* yes => return NULL */
327 shrl $16, %ecx /* make upper bytes accessible */
328 incl %eax /* increment pointer */
330 cmpb %dl, %cl /* third byte == C? */
331 je L(out) /* yes => return pointer */
333 cmpb $0, %cl /* third byte == NUL? */
334 je L(3) /* yes => return NULL */
336 incl %eax /* increment pointer */
338 /* The test four the fourth byte is necessary! */
339 cmpb %dl, %ch /* fourth byte == C? */
340 je L(out) /* yes => return pointer */
342 L(3): xorl %eax, %eax
347 weak_alias (strchr, index)
348 libc_hidden_builtin_def (strchr)