lh | 9ed821d | 2023-04-07 01:36:19 -0700 | [diff] [blame] | 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-2015 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). |
| 14 | |
| 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. |
| 19 | |
| 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. |
| 24 | |
| 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/>. */ |
| 28 | |
| 29 | #include <sysdep.h> |
| 30 | #include "asm-syntax.h" |
| 31 | |
| 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 |
| 37 | |
| 38 | .text |
| 39 | ENTRY (__memchr) |
| 40 | |
| 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) |
| 47 | |
| 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) |
| 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 L(3) |
| 58 | |
| 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 */ |
| 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, %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 */ |
| 80 | |
| 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 */ |
| 88 | |
| 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) |
| 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 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. */ |
| 124 | |
| 125 | |
| 126 | /* Each round the main loop processes 16 bytes. */ |
| 127 | |
| 128 | ALIGN (4) |
| 129 | |
| 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 */ |
| 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 occurred in the last byte => it was 0. */ |
| 144 | jnc L(8) |
| 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 CHR we don't get 0 in %edi. */ |
| 156 | jnz L(8) /* 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 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 */ |
| 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 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 */ |
| 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 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 */ |
| 206 | |
| 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 */ |
| 211 | |
| 212 | /* Process remaining bytes separately. */ |
| 213 | cmpl $4-16, %esi /* rest < 4 bytes? */ |
| 214 | jb L(3) /* 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 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 */ |
| 230 | |
| 231 | cmpl $8-16, %esi /* rest < 8 bytes? */ |
| 232 | jb L(3) /* 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 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 */ |
| 248 | |
| 249 | cmpl $12-16, %esi /* rest < 12 bytes? */ |
| 250 | jb L(3) /* 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 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 */ |
| 266 | |
| 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 */ |
| 270 | |
| 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 */ |
| 276 | |
| 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 */ |
| 282 | |
| 283 | cmpb %dl, (%eax) /* compare byte with CHR */ |
| 284 | je L(9) /* equal, than return pointer */ |
| 285 | |
| 286 | L(4): /* no byte found => return NULL */ |
| 287 | xorl %eax, %eax |
| 288 | jmp L(9) |
| 289 | |
| 290 | /* add missing source pointer increments */ |
| 291 | L(5): addl $4, %eax |
| 292 | L(6): addl $4, %eax |
| 293 | L(7): 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 | L(8): testb %cl, %cl /* test first byte in dword */ |
| 299 | jz L(9) /* if zero => return pointer */ |
| 300 | incl %eax /* increment source pointer */ |
| 301 | |
| 302 | testb %ch, %ch /* test second byte in dword */ |
| 303 | jz L(9) /* if zero => return pointer */ |
| 304 | incl %eax /* increment source pointer */ |
| 305 | |
| 306 | testl $0xff0000, %ecx /* test third byte in dword */ |
| 307 | jz L(9) /* if zero => return pointer */ |
| 308 | incl %eax /* increment source pointer */ |
| 309 | |
| 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) |
| 317 | |
| 318 | ret |
| 319 | END (__memchr) |
| 320 | |
| 321 | weak_alias (__memchr, memchr) |
| 322 | libc_hidden_builtin_def (memchr) |