1 /* rawmemchr (str, ch) -- Return pointer to first occurrence of CH in STR.
3 Copyright (C) 1994-2000,2002,2005 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
5 Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>
6 Optimised a little by Alan Modra <Alan@SPRI.Levels.UniSA.Edu.Au>
7 This version is developed using the same algorithm as the fast C
8 version which carries the following introduction:
9 Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
10 with help from Dan Sahlin (dan@sics.se) and
11 commentary by Jim Blandy (jimb@ai.mit.edu);
12 adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
13 and implemented by Roland McGrath (roland@ai.mit.edu).
15 The GNU C Library is free software; you can redistribute it and/or
16 modify it under the terms of the GNU Lesser General Public
17 License as published by the Free Software Foundation; either
18 version 2.1 of the License, or (at your option) any later version.
20 The GNU C Library is distributed in the hope that it will be useful,
21 but WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 Lesser General Public License for more details.
25 You should have received a copy of the GNU Lesser General Public
26 License along with the GNU C Library; if not, see
27 <http://www.gnu.org/licenses/>. */
30 #include "asm-syntax.h"
34 #define PARMS LINKAGE+4 /* space for 1 saved reg */
36 #define STR RTN+RTN_SIZE
37 #define CHR STR+PTR_SIZE
40 ENTRY (BP_SYM (__rawmemchr))
43 /* Save callee-safe register used in this function. */
45 cfi_adjust_cfa_offset (4)
46 cfi_rel_offset (edi, 0)
48 /* Load parameters into registers. */
51 CHECK_BOUNDS_LOW (%eax, STR(%esp))
53 /* At the moment %edx contains C. What we need for the
54 algorithm is C in all bytes of the dword. Avoid
55 operations on 16 bit words because these require an
56 prefix byte (and one more cycle). */
57 movb %dl, %dh /* Now it is 0|0|c|c */
59 shll $16, %edx /* Now c|c|0|0 */
60 movw %cx, %dx /* And finally c|c|c|c */
62 /* Better performance can be achieved if the word (32
63 bit) memory access is aligned on a four-byte-boundary.
64 So process first bytes one by one until boundary is
65 reached. Don't use a loop for better performance. */
67 testb $3, %al /* correctly aligned ? */
68 je L(1) /* yes => begin loop */
69 cmpb %dl, (%eax) /* compare byte */
70 je L(9) /* target found => return */
71 incl %eax /* increment source pointer */
73 testb $3, %al /* correctly aligned ? */
74 je L(1) /* yes => begin loop */
75 cmpb %dl, (%eax) /* compare byte */
76 je L(9) /* target found => return */
77 incl %eax /* increment source pointer */
79 testb $3, %al /* correctly aligned ? */
80 je L(1) /* yes => begin loop */
81 cmpb %dl, (%eax) /* compare byte */
82 je L(9) /* target found => return */
83 incl %eax /* increment source pointer */
85 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
86 change any of the hole bits of LONGWORD.
88 1) Is this safe? Will it catch all the zero bytes?
89 Suppose there is a byte with all zeros. Any carry bits
90 propagating from its left will fall into the hole at its
91 least significant bit and stop. Since there will be no
92 carry from its most significant bit, the LSB of the
93 byte to the left will be unchanged, and the zero will be
96 2) Is this worthwhile? Will it ignore everything except
97 zero bytes? Suppose every byte of LONGWORD has a bit set
98 somewhere. There will be a carry into bit 8. If bit 8
99 is set, this will carry into bit 16. If bit 8 is clear,
100 one of bits 9-15 must be set, so there will be a carry
101 into bit 16. Similarly, there will be a carry into bit
102 24. If one of bits 24-31 is set, there will be a carry
103 into bit 32 (=carry flag), so all of the hole bits will
106 3) But wait! Aren't we looking for C, not zero?
107 Good point. So what we do is XOR LONGWORD with a longword,
108 each of whose bytes is C. This turns each byte that is C
112 /* Each round the main loop processes 16 bytes. */
115 L(1): movl (%eax), %ecx /* get word (= 4 bytes) in question */
116 movl $0xfefefeff, %edi /* magic value */
117 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
119 addl %ecx, %edi /* add the magic value to the word. We get
120 carry bits reported for each byte which
123 /* According to the algorithm we had to reverse the effect of the
124 XOR first and then test the overflow bits. But because the
125 following XOR would destroy the carry flag and it would (in a
126 representation with more than 32 bits) not alter then last
127 overflow, we can now test this condition. If no carry is signaled
128 no overflow must have occurred in the last byte => it was 0. */
131 /* We are only interested in carry bits that change due to the
132 previous add, so remove original bits */
133 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
135 /* Now test for the other three overflow bits. */
136 orl $0xfefefeff, %edi /* set all non-carry bits */
137 incl %edi /* add 1: if one carry bit was *not* set
138 the addition will not result in 0. */
140 /* If at least one byte of the word is C we don't get 0 in %edi. */
141 jnz L(8) /* found it => return pointer */
143 /* This process is unfolded four times for better performance.
144 we don't increment the source pointer each time. Instead we
145 use offsets and increment by 16 in each run of the loop. But
146 before probing for the matching byte we need some extra code
147 (following LL(13) below). Even the len can be compared with
148 constants instead of decrementing each time. */
150 movl 4(%eax), %ecx /* get word (= 4 bytes) in question */
151 movl $0xfefefeff, %edi /* magic value */
152 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
154 addl %ecx, %edi /* add the magic value to the word. We get
155 carry bits reported for each byte which
157 jnc L(7) /* highest byte is C => return pointer */
158 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
159 orl $0xfefefeff, %edi /* set all non-carry bits */
160 incl %edi /* add 1: if one carry bit was *not* set
161 the addition will not result in 0. */
162 jnz L(7) /* found it => return pointer */
164 movl 8(%eax), %ecx /* get word (= 4 bytes) in question */
165 movl $0xfefefeff, %edi /* magic value */
166 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
168 addl %ecx, %edi /* add the magic value to the word. We get
169 carry bits reported for each byte which
171 jnc L(6) /* highest byte is C => return pointer */
172 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
173 orl $0xfefefeff, %edi /* set all non-carry bits */
174 incl %edi /* add 1: if one carry bit was *not* set
175 the addition will not result in 0. */
176 jnz L(6) /* found it => return pointer */
178 movl 12(%eax), %ecx /* get word (= 4 bytes) in question */
179 movl $0xfefefeff, %edi /* magic value */
180 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
182 addl %ecx, %edi /* add the magic value to the word. We get
183 carry bits reported for each byte which
185 jnc L(5) /* highest byte is C => return pointer */
186 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
187 orl $0xfefefeff, %edi /* set all non-carry bits */
188 incl %edi /* add 1: if one carry bit was *not* set
189 the addition will not result in 0. */
190 jnz L(5) /* found it => return pointer */
192 /* Adjust both counters for a full round, i.e. 16 bytes. */
195 /* add missing source pointer increments */
200 /* Test for the matching byte in the word. %ecx contains a NUL
201 char in the byte which originally was the byte we are looking
203 L(8): testb %cl, %cl /* test first byte in dword */
204 jz L(9) /* if zero => return pointer */
205 incl %eax /* increment source pointer */
207 testb %ch, %ch /* test second byte in dword */
208 jz L(9) /* if zero => return pointer */
209 incl %eax /* increment source pointer */
211 testl $0xff0000, %ecx /* test third byte in dword */
212 jz L(9) /* if zero => return pointer */
213 incl %eax /* increment source pointer */
215 /* No further test needed we we know it is one of the four bytes. */
218 CHECK_BOUNDS_HIGH (%eax, STR(%esp), jb)
219 RETURN_BOUNDED_POINTER (STR(%esp))
220 popl %edi /* pop saved register */
221 cfi_adjust_cfa_offset (-4)
226 END (BP_SYM (__rawmemchr))
228 libc_hidden_def (BP_SYM (__rawmemchr))
229 weak_alias (BP_SYM (__rawmemchr), BP_SYM (rawmemchr))