| blob | f82e894ca459f143932e32d3e5a2cd5a76bc7211 |
1 /* memchr (str, chr, len) -- Return pointer to first occurrence of CHR in STR
2 less than LEN. For Intel 80x86, x>=3.
3 Copyright (C) 1994-2014 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/>. */
29 #include <sysdep.h>
30 #include "asm-syntax.h"
32 #define PARMS 4+8 /* space for 2 saved regs */
33 #define RTN PARMS
34 #define STR RTN
35 #define CHR STR+4
36 #define LEN CHR+4
38 .text
39 ENTRY (__memchr)
41 /* Save callee-safe registers used in this function. */
42 pushl %esi
43 cfi_adjust_cfa_offset (4)
44 pushl %edi
45 cfi_adjust_cfa_offset (4)
46 cfi_rel_offset (edi, 0)
48 /* Load parameters into registers. */
49 movl STR(%esp), %eax /* str: pointer to memory block. */
50 movl CHR(%esp), %edx /* c: byte we are looking for. */
51 movl LEN(%esp), %esi /* len: length of memory block. */
52 cfi_rel_offset (esi, 4)
54 /* If my must not test more than three characters test
55 them one by one. This is especially true for 0. */
56 cmpl $4, %esi
57 jb L(3)
59 /* At the moment %edx contains CHR. What we need for the
60 algorithm is CHR in all bytes of the dword. Avoid
61 operations on 16 bit words because these require an
62 prefix byte (and one more cycle). */
63 movb %dl, %dh /* Now it is 0|0|c|c */
64 movl %edx, %ecx
65 shll $16, %edx /* Now c|c|0|0 */
66 movw %cx, %dx /* And finally c|c|c|c */
68 /* Better performance can be achieved if the word (32
69 bit) memory access is aligned on a four-byte-boundary.
70 So process first bytes one by one until boundary is
71 reached. Don't use a loop for better performance. */
73 testb $3, %al /* correctly aligned ? */
74 je L(2) /* yes => begin loop */
75 cmpb %dl, (%eax) /* compare byte */
76 je L(9) /* target found => return */
77 incl %eax /* increment source pointer */
78 decl %esi /* decrement length counter */
79 je L(4) /* len==0 => return NULL */
81 testb $3, %al /* correctly aligned ? */
82 je L(2) /* yes => begin loop */
83 cmpb %dl, (%eax) /* compare byte */
84 je L(9) /* target found => return */
85 incl %eax /* increment source pointer */
86 decl %esi /* decrement length counter */
87 je L(4) /* len==0 => return NULL */
89 testb $3, %al /* correctly aligned ? */
90 je L(2) /* yes => begin loop */
91 cmpb %dl, (%eax) /* compare byte */
92 je L(9) /* target found => return */
93 incl %eax /* increment source pointer */
94 decl %esi /* decrement length counter */
95 /* no test for len==0 here, because this is done in the
96 loop head */
97 jmp L(2)
99 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
100 change any of the hole bits of LONGWORD.
102 1) Is this safe? Will it catch all the zero bytes?
103 Suppose there is a byte with all zeros. Any carry bits
104 propagating from its left will fall into the hole at its
105 least significant bit and stop. Since there will be no
106 carry from its most significant bit, the LSB of the
107 byte to the left will be unchanged, and the zero will be
108 detected.
110 2) Is this worthwhile? Will it ignore everything except
111 zero bytes? Suppose every byte of LONGWORD has a bit set
112 somewhere. There will be a carry into bit 8. If bit 8
113 is set, this will carry into bit 16. If bit 8 is clear,
114 one of bits 9-15 must be set, so there will be a carry
115 into bit 16. Similarly, there will be a carry into bit
116 24. If one of bits 24-31 is set, there will be a carry
117 into bit 32 (=carry flag), so all of the hole bits will
118 be changed.
120 3) But wait! Aren't we looking for CHR, not zero?
121 Good point. So what we do is XOR LONGWORD with a longword,
122 each of whose bytes is CHR. This turns each byte that is CHR
123 into a zero. */
126 /* Each round the main loop processes 16 bytes. */
128 ALIGN (4)
130 L(1): movl (%eax), %ecx /* get word (= 4 bytes) in question */
131 movl $0xfefefeff, %edi /* magic value */
132 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
133 are now 0 */
134 addl %ecx, %edi /* add the magic value to the word. We get
135 carry bits reported for each byte which
136 is *not* 0 */
138 /* According to the algorithm we had to reverse the effect of the
139 XOR first and then test the overflow bits. But because the
140 following XOR would destroy the carry flag and it would (in a
141 representation with more than 32 bits) not alter then last
142 overflow, we can now test this condition. If no carry is signaled
143 no overflow must have occurred in the last byte => it was 0. */
144 jnc L(8)
146 /* We are only interested in carry bits that change due to the
147 previous add, so remove original bits */
148 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
150 /* Now test for the other three overflow bits. */
151 orl $0xfefefeff, %edi /* set all non-carry bits */
152 incl %edi /* add 1: if one carry bit was *not* set
153 the addition will not result in 0. */
155 /* If at least one byte of the word is CHR we don't get 0 in %edi. */
156 jnz L(8) /* found it => return pointer */
158 /* This process is unfolded four times for better performance.
159 we don't increment the source pointer each time. Instead we
160 use offsets and increment by 16 in each run of the loop. But
161 before probing for the matching byte we need some extra code
162 (following LL(13) below). Even the len can be compared with
163 constants instead of decrementing each time. */
165 movl 4(%eax), %ecx /* get word (= 4 bytes) in question */
166 movl $0xfefefeff, %edi /* magic value */
167 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
168 are now 0 */
169 addl %ecx, %edi /* add the magic value to the word. We get
170 carry bits reported for each byte which
171 is *not* 0 */
172 jnc L(7) /* highest byte is CHR => 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 L(7) /* found it => return pointer */
179 movl 8(%eax), %ecx /* get word (= 4 bytes) in question */
180 movl $0xfefefeff, %edi /* magic value */
181 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
182 are now 0 */
183 addl %ecx, %edi /* add the magic value to the word. We get
184 carry bits reported for each byte which
185 is *not* 0 */
186 jnc L(6) /* highest byte is CHR => return pointer */
187 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
188 orl $0xfefefeff, %edi /* set all non-carry bits */
189 incl %edi /* add 1: if one carry bit was *not* set
190 the addition will not result in 0. */
191 jnz L(6) /* found it => return pointer */
193 movl 12(%eax), %ecx /* get word (= 4 bytes) in question */
194 movl $0xfefefeff, %edi /* magic value */
195 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
196 are now 0 */
197 addl %ecx, %edi /* add the magic value to the word. We get
198 carry bits reported for each byte which
199 is *not* 0 */
200 jnc L(5) /* highest byte is CHR => return pointer */
201 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
202 orl $0xfefefeff, %edi /* set all non-carry bits */
203 incl %edi /* add 1: if one carry bit was *not* set
204 the addition will not result in 0. */
205 jnz L(5) /* found it => return pointer */
207 /* Adjust both counters for a full round, i.e. 16 bytes. */
208 addl $16, %eax
209 L(2): subl $16, %esi
210 jae L(1) /* Still more than 16 bytes remaining */
212 /* Process remaining bytes separately. */
213 cmpl $4-16, %esi /* rest < 4 bytes? */
214 jb L(3) /* yes, than test byte by byte */
216 movl (%eax), %ecx /* get word (= 4 bytes) in question */
217 movl $0xfefefeff, %edi /* magic value */
218 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
219 are now 0 */
220 addl %ecx, %edi /* add the magic value to the word. We get
221 carry bits reported for each byte which
222 is *not* 0 */
223 jnc L(8) /* highest byte is CHR => return pointer */
224 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
225 orl $0xfefefeff, %edi /* set all non-carry bits */
226 incl %edi /* add 1: if one carry bit was *not* set
227 the addition will not result in 0. */
228 jne L(8) /* found it => return pointer */
229 addl $4, %eax /* adjust source pointer */
231 cmpl $8-16, %esi /* rest < 8 bytes? */
232 jb L(3) /* yes, than test byte by byte */
234 movl (%eax), %ecx /* get word (= 4 bytes) in question */
235 movl $0xfefefeff, %edi /* magic value */
236 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
237 are now 0 */
238 addl %ecx, %edi /* add the magic value to the word. We get
239 carry bits reported for each byte which
240 is *not* 0 */
241 jnc L(8) /* highest byte is CHR => return pointer */
242 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
243 orl $0xfefefeff, %edi /* set all non-carry bits */
244 incl %edi /* add 1: if one carry bit was *not* set
245 the addition will not result in 0. */
246 jne L(8) /* found it => return pointer */
247 addl $4, %eax /* adjust source pointer */
249 cmpl $12-16, %esi /* rest < 12 bytes? */
250 jb L(3) /* yes, than test byte by byte */
252 movl (%eax), %ecx /* get word (= 4 bytes) in question */
253 movl $0xfefefeff, %edi /* magic value */
254 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
255 are now 0 */
256 addl %ecx, %edi /* add the magic value to the word. We get
257 carry bits reported for each byte which
258 is *not* 0 */
259 jnc L(8) /* highest byte is CHR => return pointer */
260 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
261 orl $0xfefefeff, %edi /* set all non-carry bits */
262 incl %edi /* add 1: if one carry bit was *not* set
263 the addition will not result in 0. */
264 jne L(8) /* found it => return pointer */
265 addl $4, %eax /* adjust source pointer */
267 /* Check the remaining bytes one by one. */
268 L(3): andl $3, %esi /* mask out uninteresting bytes */
269 jz L(4) /* no remaining bytes => return NULL */
271 cmpb %dl, (%eax) /* compare byte with CHR */
272 je L(9) /* equal, than return pointer */
273 incl %eax /* increment source pointer */
274 decl %esi /* decrement length */
275 jz L(4) /* no remaining bytes => return NULL */
277 cmpb %dl, (%eax) /* compare byte with CHR */
278 je L(9) /* equal, than return pointer */
279 incl %eax /* increment source pointer */
280 decl %esi /* decrement length */
281 jz L(4) /* no remaining bytes => return NULL */
283 cmpb %dl, (%eax) /* compare byte with CHR */
284 je L(9) /* equal, than return pointer */
286 L(4): /* no byte found => return NULL */
287 xorl %eax, %eax
288 jmp L(9)
290 /* add missing source pointer increments */
291 L(5): addl $4, %eax
292 L(6): addl $4, %eax
293 L(7): addl $4, %eax
295 /* Test for the matching byte in the word. %ecx contains a NUL
296 char in the byte which originally was the byte we are looking
297 at. */
298 L(8): testb %cl, %cl /* test first byte in dword */
299 jz L(9) /* if zero => return pointer */
300 incl %eax /* increment source pointer */
302 testb %ch, %ch /* test second byte in dword */
303 jz L(9) /* if zero => return pointer */
304 incl %eax /* increment source pointer */
306 testl $0xff0000, %ecx /* test third byte in dword */
307 jz L(9) /* if zero => return pointer */
308 incl %eax /* increment source pointer */
310 /* No further test needed we we know it is one of the four bytes. */
311 L(9): popl %edi /* pop saved registers */
312 cfi_adjust_cfa_offset (-4)
313 cfi_restore (edi)
314 popl %esi
315 cfi_adjust_cfa_offset (-4)
316 cfi_restore (esi)
318 ret
319 END (__memchr)
321 weak_alias (__memchr, memchr)
322 libc_hidden_builtin_def (memchr)