1/* rawmemchr (str, ch) -- Return pointer to first occurrence of CH in STR.
2 For Intel 80x86, x>=3.
3 Copyright (C) 1994-2022 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, see
18 <https://www.gnu.org/licenses/>. */
19
20#include <sysdep.h>
21#include "asm-syntax.h"
22
23#define PARMS 4+4 /* space for 1 saved reg */
24#define RTN PARMS
25#define STR RTN
26#define CHR STR+4
27
28 .text
29ENTRY (__rawmemchr)
30
31 /* Save callee-safe register used in this function. */
32 pushl %edi
33 cfi_adjust_cfa_offset (4)
34 cfi_rel_offset (edi, 0)
35
36 /* Load parameters into registers. */
37 movl STR(%esp), %eax
38 movl CHR(%esp), %edx
39
40 /* At the moment %edx contains C. What we need for the
41 algorithm is C in all bytes of the dword. Avoid
42 operations on 16 bit words because these require an
43 prefix byte (and one more cycle). */
44 movb %dl, %dh /* Now it is 0|0|c|c */
45 movl %edx, %ecx
46 shll $16, %edx /* Now c|c|0|0 */
47 movw %cx, %dx /* And finally c|c|c|c */
48
49 /* Better performance can be achieved if the word (32
50 bit) memory access is aligned on a four-byte-boundary.
51 So process first bytes one by one until boundary is
52 reached. Don't use a loop for better performance. */
53
54 testb $3, %al /* correctly aligned ? */
55 je L(1) /* yes => begin loop */
56 cmpb %dl, (%eax) /* compare byte */
57 je L(9) /* target found => return */
58 incl %eax /* increment source pointer */
59
60 testb $3, %al /* correctly aligned ? */
61 je L(1) /* yes => begin loop */
62 cmpb %dl, (%eax) /* compare byte */
63 je L(9) /* target found => return */
64 incl %eax /* increment source pointer */
65
66 testb $3, %al /* correctly aligned ? */
67 je L(1) /* yes => begin loop */
68 cmpb %dl, (%eax) /* compare byte */
69 je L(9) /* target found => return */
70 incl %eax /* increment source pointer */
71
72 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
73 change any of the hole bits of LONGWORD.
74
75 1) Is this safe? Will it catch all the zero bytes?
76 Suppose there is a byte with all zeros. Any carry bits
77 propagating from its left will fall into the hole at its
78 least significant bit and stop. Since there will be no
79 carry from its most significant bit, the LSB of the
80 byte to the left will be unchanged, and the zero will be
81 detected.
82
83 2) Is this worthwhile? Will it ignore everything except
84 zero bytes? Suppose every byte of LONGWORD has a bit set
85 somewhere. There will be a carry into bit 8. If bit 8
86 is set, this will carry into bit 16. If bit 8 is clear,
87 one of bits 9-15 must be set, so there will be a carry
88 into bit 16. Similarly, there will be a carry into bit
89 24. If one of bits 24-31 is set, there will be a carry
90 into bit 32 (=carry flag), so all of the hole bits will
91 be changed.
92
93 3) But wait! Aren't we looking for C, not zero?
94 Good point. So what we do is XOR LONGWORD with a longword,
95 each of whose bytes is C. This turns each byte that is C
96 into a zero. */
97
98
99 /* Each round the main loop processes 16 bytes. */
100 ALIGN (4)
101
102L(1): movl (%eax), %ecx /* get word (= 4 bytes) in question */
103 movl $0xfefefeff, %edi /* magic value */
104 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
105 are now 0 */
106 addl %ecx, %edi /* add the magic value to the word. We get
107 carry bits reported for each byte which
108 is *not* 0 */
109
110 /* According to the algorithm we had to reverse the effect of the
111 XOR first and then test the overflow bits. But because the
112 following XOR would destroy the carry flag and it would (in a
113 representation with more than 32 bits) not alter then last
114 overflow, we can now test this condition. If no carry is signaled
115 no overflow must have occurred in the last byte => it was 0. */
116 jnc L(8)
117
118 /* We are only interested in carry bits that change due to the
119 previous add, so remove original bits */
120 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
121
122 /* Now test for the other three overflow bits. */
123 orl $0xfefefeff, %edi /* set all non-carry bits */
124 incl %edi /* add 1: if one carry bit was *not* set
125 the addition will not result in 0. */
126
127 /* If at least one byte of the word is C we don't get 0 in %edi. */
128 jnz L(8) /* found it => return pointer */
129
130 /* This process is unfolded four times for better performance.
131 we don't increment the source pointer each time. Instead we
132 use offsets and increment by 16 in each run of the loop. But
133 before probing for the matching byte we need some extra code
134 (following LL(13) below). Even the len can be compared with
135 constants instead of decrementing each time. */
136
137 movl 4(%eax), %ecx /* get word (= 4 bytes) in question */
138 movl $0xfefefeff, %edi /* magic value */
139 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
140 are now 0 */
141 addl %ecx, %edi /* add the magic value to the word. We get
142 carry bits reported for each byte which
143 is *not* 0 */
144 jnc L(7) /* highest byte is C => return pointer */
145 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
146 orl $0xfefefeff, %edi /* set all non-carry bits */
147 incl %edi /* add 1: if one carry bit was *not* set
148 the addition will not result in 0. */
149 jnz L(7) /* found it => return pointer */
150
151 movl 8(%eax), %ecx /* get word (= 4 bytes) in question */
152 movl $0xfefefeff, %edi /* magic value */
153 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c
154 are now 0 */
155 addl %ecx, %edi /* add the magic value to the word. We get
156 carry bits reported for each byte which
157 is *not* 0 */
158 jnc L(6) /* highest byte is C => return pointer */
159 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */
160 orl $0xfefefeff, %edi /* set all non-carry bits */
161 incl %edi /* add 1: if one carry bit was *not* set
162 the addition will not result in 0. */
163 jnz L(6) /* found it => return pointer */
164
165 movl 12(%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(5) /* 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 L(5) /* found it => return pointer */
178
179 /* Adjust both counters for a full round, i.e. 16 bytes. */
180 addl $16, %eax
181 jmp L(1)
182 /* add missing source pointer increments */
183L(5): addl $4, %eax
184L(6): addl $4, %eax
185L(7): addl $4, %eax
186
187 /* Test for the matching byte in the word. %ecx contains a NUL
188 char in the byte which originally was the byte we are looking
189 at. */
190L(8): testb %cl, %cl /* test first byte in dword */
191 jz L(9) /* if zero => return pointer */
192 incl %eax /* increment source pointer */
193
194 testb %ch, %ch /* test second byte in dword */
195 jz L(9) /* if zero => return pointer */
196 incl %eax /* increment source pointer */
197
198 testl $0xff0000, %ecx /* test third byte in dword */
199 jz L(9) /* if zero => return pointer */
200 incl %eax /* increment source pointer */
201
202 /* No further test needed we we know it is one of the four bytes. */
203
204L(9):
205 popl %edi /* pop saved register */
206 cfi_adjust_cfa_offset (-4)
207 cfi_restore (edi)
208
209 ret
210END (__rawmemchr)
211
212libc_hidden_def (__rawmemchr)
213weak_alias (__rawmemchr, rawmemchr)
214

source code of glibc/sysdeps/i386/rawmemchr.S