Mon Jun 24 19:57:01 1996 Roland McGrath <roland@delasyd.gnu.ai.mit.edu>
[kopensolaris-gnu/glibc.git] / sysdeps / i386 / memchr.S
1 /* memchr (str, ch, n) -- Return pointer to first occurrence of CH in STR less
2    than N.
3 For Intel 80x86, x>=3.
4 Copyright (C) 1994, 1995 Free Software Foundation, Inc.
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 file is part of the GNU C Library.
8
9 This version is developed using the same algorithm as the fast C
10 version which carries the following introduction:
11
12 Based on strlen implemention by Torbjorn Granlund (tege@sics.se),
13 with help from Dan Sahlin (dan@sics.se) and
14 commentary by Jim Blandy (jimb@ai.mit.edu);
15 adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
16 and implemented by Roland McGrath (roland@ai.mit.edu).
17
18 The GNU C Library is free software; you can redistribute it and/or
19 modify it under the terms of the GNU Library General Public License as
20 published by the Free Software Foundation; either version 2 of the
21 License, or (at your option) any later version.
22
23 The GNU C Library is distributed in the hope that it will be useful,
24 but WITHOUT ANY WARRANTY; without even the implied warranty of
25 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
26 Library General Public License for more details.
27
28 You should have received a copy of the GNU Library General Public
29 License along with the GNU C Library; see the file COPYING.LIB.  If
30 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
31 Boston, MA 02111-1307, USA.  */
32
33 #include <sysdep.h>
34 #include "asm-syntax.h"
35
36 /*
37    INPUT PARAMETERS:
38    str          (sp + 4)
39    c            (sp + 8)
40    len          (sp + 12)
41 */
42
43         .text
44 ENTRY (memchr)
45         /* Save callee-safe registers used in this function.  */
46         pushl %esi
47         pushl %edi
48
49         /* Load parameters into registers.  */
50         movl 12(%esp), %eax     /* str: pointer to memory block.  */
51         movl 16(%esp), %edx     /* c: byte we are looking for.  */
52         movl 20(%esp), %esi     /* len: length of memory block.  */
53
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 L3
58
59         /* At the moment %edx contains C.  What we need for the
60            algorithm is C 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 */
67
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.  */
72
73         testb $3, %eax          /* correctly aligned ? */
74         je L2                   /* yes => begin loop */
75         cmpb %dl, (%eax)        /* compare byte */
76         je L9                   /* target found => return */
77         incl %eax               /* increment source pointer */
78         decl %esi               /* decrement length counter */
79         je L4                   /* len==0 => return NULL */
80
81         testb $3, %eax          /* correctly aligned ? */
82         je L2                   /* yes => begin loop */
83         cmpb %dl, (%eax)        /* compare byte */
84         je L9                   /* target found => return */
85         incl %eax               /* increment source pointer */
86         decl %esi               /* decrement length counter */
87         je L4                   /* len==0 => return NULL */
88
89         testb $3, %eax          /* correctly aligned ? */
90         je L2                   /* yes => begin loop */
91         cmpb %dl, (%eax)        /* compare byte */
92         je L9                   /* 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 L2
98
99       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
100          change any of the hole bits of LONGWORD.
101
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.
109
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.
119
120          3) But wait!  Aren't we looking for C, not zero?
121          Good point.  So what we do is XOR LONGWORD with a longword,
122          each of whose bytes is C.  This turns each byte that is C
123          into a zero.  */
124
125
126         /* Each round the main loop processes 16 bytes.  */
127
128         ALIGN (4)
129
130 L1:     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 */
137
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 occured in the last byte => it was 0.  */
144         jnc L8
145
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) */
149
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.  */
154
155         /* If at least one byte of the word is C we don't get 0 in %edi.  */
156         jnz L8                  /* found it => return pointer */
157
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.  */
164
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 L7                  /* 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 L7                  /* found it => return pointer */
178
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 L6                  /* highest byte is C => 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 L6                  /* found it => return pointer */
192
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 L5                  /* highest byte is C => 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 L5                  /* found it => return pointer */
206
207         /* Adjust both counters for a full round, i.e. 16 bytes.  */
208         addl $16, %eax
209 L2:     subl $16, %esi
210         jae L1                  /* Still more than 16 bytes remaining */
211
212         /* Process remaining bytes separately.  */
213         cmpl $4-16, %esi        /* rest < 4 bytes? */
214         jb L3                   /* yes, than test byte by byte */
215
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 L8                  /* highest byte is C => 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 L8                  /* found it => return pointer */
229         addl $4, %eax           /* adjust source pointer */
230
231         cmpl $8-16, %esi        /* rest < 8 bytes? */
232         jb L3                   /* yes, than test byte by byte */
233
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 L8                  /* highest byte is C => 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 L8                  /* found it => return pointer */
247         addl $4, %eax           /* adjust source pointer */
248
249         cmpl $12-16, %esi       /* rest < 12 bytes? */
250         jb L3                   /* yes, than test byte by byte */
251
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 L8                  /* highest byte is C => 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 L8                  /* found it => return pointer */
265         addl $4, %eax           /* adjust source pointer */
266
267         /* Check the remaining bytes one by one.  */
268 L3:     andl $3, %esi           /* mask out uninteresting bytes */
269         jz L4                   /* no remaining bytes => return NULL */
270
271         cmpb %dl, (%eax)        /* compare byte with C */
272         je L9                   /* equal, than return pointer */
273         incl %eax               /* increment source pointer */
274         decl %esi               /* decrement length */
275         jz L4                   /* no remaining bytes => return NULL */
276
277         cmpb %dl, (%eax)        /* compare byte with C */
278         je L9                   /* equal, than return pointer */
279         incl %eax               /* increment source pointer */
280         decl %esi               /* decrement length */
281         jz L4                   /* no remaining bytes => return NULL */
282
283         cmpb %dl, (%eax)        /* compare byte with C */
284         je L9                   /* equal, than return pointer */
285
286 L4:     /* no byte found => return NULL */
287         xorl %eax, %eax
288         jmp L9
289
290         /* add missing source pointer increments */
291 L5:     addl $4, %eax
292 L6:     addl $4, %eax
293 L7:     addl $4, %eax
294
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 L8:     testb %cl, %cl          /* test first byte in dword */
299         jz L9                   /* if zero => return pointer */
300         incl %eax               /* increment source pointer */
301
302         testb %ch, %ch          /* test second byte in dword */
303         jz L9                   /* if zero => return pointer */
304         incl %eax               /* increment source pointer */
305
306         testl $0xff0000, %ecx   /* test third byte in dword */
307         jz L9                   /* if zero => return pointer */
308         incl %eax               /* increment source pointer */
309
310         /* No further test needed we we known it is one of the four byytes.  */
311
312 L9:     popl %edi               /* pop saved registers */
313         popl %esi
314
315         ret