1/* strchrnul (str, chr) -- Return pointer to first occurrence of CHR in STR 2 or the final NUL byte. 3 For Intel 80x86, x>=3. 4 Copyright (C) 1994-2022 Free Software Foundation, Inc. 5 This file is part of the GNU C Library. 6 7 The GNU C Library is free software; you can redistribute it and/or 8 modify it under the terms of the GNU Lesser General Public 9 License as published by the Free Software Foundation; either 10 version 2.1 of the License, or (at your option) any later version. 11 12 The GNU C Library is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Lesser General Public License for more details. 16 17 You should have received a copy of the GNU Lesser General Public 18 License along with the GNU C Library; if not, see 19 <https://www.gnu.org/licenses/>. */ 20 21#include <sysdep.h> 22#include "asm-syntax.h" 23 24#define PARMS 4+4 /* space for 1 saved reg */ 25#define RTN PARMS 26#define STR RTN 27#define CHR STR+4 28 29 .text 30ENTRY (__strchrnul) 31 32 pushl %edi /* Save callee-safe registers used here. */ 33 cfi_adjust_cfa_offset (4) 34 cfi_rel_offset (edi, 0) 35 36 movl STR(%esp), %eax 37 movl CHR(%esp), %edx 38 39 /* At the moment %edx contains CHR. What we need for the 40 algorithm is CHR in all bytes of the dword. Avoid 41 operations on 16 bit words because these require an 42 prefix byte (and one more cycle). */ 43 movb %dl, %dh /* now it is 0|0|c|c */ 44 movl %edx, %ecx 45 shll $16, %edx /* now it is c|c|0|0 */ 46 movw %cx, %dx /* and finally c|c|c|c */ 47 48 /* Before we start with the main loop we process single bytes 49 until the source pointer is aligned. This has two reasons: 50 1. aligned 32-bit memory access is faster 51 and (more important) 52 2. we process in the main loop 32 bit in one step although 53 we don't know the end of the string. But accessing at 54 4-byte alignment guarantees that we never access illegal 55 memory if this would not also be done by the trivial 56 implementation (this is because all processor inherent 57 boundaries are multiples of 4. */ 58 59 testb $3, %al /* correctly aligned ? */ 60 jz L(11) /* yes => begin loop */ 61 movb (%eax), %cl /* load byte in question (we need it twice) */ 62 cmpb %cl, %dl /* compare byte */ 63 je L(6) /* target found => return */ 64 testb %cl, %cl /* is NUL? */ 65 jz L(6) /* yes => return NULL */ 66 incl %eax /* increment pointer */ 67 68 testb $3, %al /* correctly aligned ? */ 69 jz L(11) /* yes => begin loop */ 70 movb (%eax), %cl /* load byte in question (we need it twice) */ 71 cmpb %cl, %dl /* compare byte */ 72 je L(6) /* target found => return */ 73 testb %cl, %cl /* is NUL? */ 74 jz L(6) /* yes => return NULL */ 75 incl %eax /* increment pointer */ 76 77 testb $3, %al /* correctly aligned ? */ 78 jz L(11) /* yes => begin loop */ 79 movb (%eax), %cl /* load byte in question (we need it twice) */ 80 cmpb %cl, %dl /* compare byte */ 81 je L(6) /* target found => return */ 82 testb %cl, %cl /* is NUL? */ 83 jz L(6) /* yes => return NULL */ 84 incl %eax /* increment pointer */ 85 86 /* No we have reached alignment. */ 87 jmp L(11) /* begin loop */ 88 89 /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to 90 change any of the hole bits of LONGWORD. 91 92 1) Is this safe? Will it catch all the zero bytes? 93 Suppose there is a byte with all zeros. Any carry bits 94 propagating from its left will fall into the hole at its 95 least significant bit and stop. Since there will be no 96 carry from its most significant bit, the LSB of the 97 byte to the left will be unchanged, and the zero will be 98 detected. 99 100 2) Is this worthwhile? Will it ignore everything except 101 zero bytes? Suppose every byte of LONGWORD has a bit set 102 somewhere. There will be a carry into bit 8. If bit 8 103 is set, this will carry into bit 16. If bit 8 is clear, 104 one of bits 9-15 must be set, so there will be a carry 105 into bit 16. Similarly, there will be a carry into bit 106 24. If one of bits 24-31 is set, there will be a carry 107 into bit 32 (=carry flag), so all of the hole bits will 108 be changed. 109 110 3) But wait! Aren't we looking for CHR, not zero? 111 Good point. So what we do is XOR LONGWORD with a longword, 112 each of whose bytes is CHR. This turns each byte that is CHR 113 into a zero. */ 114 115 /* Each round the main loop processes 16 bytes. */ 116 117 ALIGN(4) 118 119L(1): addl $16, %eax /* adjust pointer for whole round */ 120 121L(11): movl (%eax), %ecx /* get word (= 4 bytes) in question */ 122 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c 123 are now 0 */ 124 movl $0xfefefeff, %edi /* magic value */ 125 addl %ecx, %edi /* add the magic value to the word. We get 126 carry bits reported for each byte which 127 is *not* CHR */ 128 129 /* According to the algorithm we had to reverse the effect of the 130 XOR first and then test the overflow bits. But because the 131 following XOR would destroy the carry flag and it would (in a 132 representation with more than 32 bits) not alter then last 133 overflow, we can now test this condition. If no carry is signaled 134 no overflow must have occurred in the last byte => it was 0. */ 135 jnc L(7) 136 137 /* We are only interested in carry bits that change due to the 138 previous add, so remove original bits */ 139 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */ 140 141 /* Now test for the other three overflow bits. */ 142 orl $0xfefefeff, %edi /* set all non-carry bits */ 143 incl %edi /* add 1: if one carry bit was *not* set 144 the addition will not result in 0. */ 145 146 /* If at least one byte of the word is CHR we don't get 0 in %edi. */ 147 jnz L(7) /* found it => return pointer */ 148 149 /* Now we made sure the dword does not contain the character we are 150 looking for. But because we deal with strings we have to check 151 for the end of string before testing the next dword. */ 152 153 xorl %edx, %ecx /* restore original dword without reload */ 154 movl $0xfefefeff, %edi /* magic value */ 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(7) /* highest byte is NUL => return NULL */ 159 xorl %ecx, %edi /* (word+magic)^word */ 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(7) /* found NUL => return NULL */ 164 165 movl 4(%eax), %ecx /* get word (= 4 bytes) in question */ 166 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c 167 are now 0 */ 168 movl $0xfefefeff, %edi /* magic value */ 169 addl %ecx, %edi /* add the magic value to the word. We get 170 carry bits reported for each byte which 171 is *not* CHR */ 172 jnc L(71) /* 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(71) /* found it => return pointer */ 178 xorl %edx, %ecx /* restore original dword without reload */ 179 movl $0xfefefeff, %edi /* magic value */ 180 addl %ecx, %edi /* add the magic value to the word. We get 181 carry bits reported for each byte which 182 is *not* 0 */ 183 jnc L(71) /* highest byte is NUL => return NULL */ 184 xorl %ecx, %edi /* (word+magic)^word */ 185 orl $0xfefefeff, %edi /* set all non-carry bits */ 186 incl %edi /* add 1: if one carry bit was *not* set 187 the addition will not result in 0. */ 188 jnz L(71) /* found NUL => return NULL */ 189 190 movl 8(%eax), %ecx /* get word (= 4 bytes) in question */ 191 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c 192 are now 0 */ 193 movl $0xfefefeff, %edi /* magic value */ 194 addl %ecx, %edi /* add the magic value to the word. We get 195 carry bits reported for each byte which 196 is *not* CHR */ 197 jnc L(72) /* highest byte is CHR => return pointer */ 198 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */ 199 orl $0xfefefeff, %edi /* set all non-carry bits */ 200 incl %edi /* add 1: if one carry bit was *not* set 201 the addition will not result in 0. */ 202 jnz L(72) /* found it => return pointer */ 203 xorl %edx, %ecx /* restore original dword without reload */ 204 movl $0xfefefeff, %edi /* magic value */ 205 addl %ecx, %edi /* add the magic value to the word. We get 206 carry bits reported for each byte which 207 is *not* 0 */ 208 jnc L(72) /* highest byte is NUL => return NULL */ 209 xorl %ecx, %edi /* (word+magic)^word */ 210 orl $0xfefefeff, %edi /* set all non-carry bits */ 211 incl %edi /* add 1: if one carry bit was *not* set 212 the addition will not result in 0. */ 213 jnz L(72) /* found NUL => return NULL */ 214 215 movl 12(%eax), %ecx /* get word (= 4 bytes) in question */ 216 xorl %edx, %ecx /* XOR with word c|c|c|c => bytes of str == c 217 are now 0 */ 218 movl $0xfefefeff, %edi /* magic value */ 219 addl %ecx, %edi /* add the magic value to the word. We get 220 carry bits reported for each byte which 221 is *not* CHR */ 222 jnc L(73) /* highest byte is CHR => return pointer */ 223 xorl %ecx, %edi /* ((word^charmask)+magic)^(word^charmask) */ 224 orl $0xfefefeff, %edi /* set all non-carry bits */ 225 incl %edi /* add 1: if one carry bit was *not* set 226 the addition will not result in 0. */ 227 jnz L(73) /* found it => return pointer */ 228 xorl %edx, %ecx /* restore original dword without reload */ 229 movl $0xfefefeff, %edi /* magic value */ 230 addl %ecx, %edi /* add the magic value to the word. We get 231 carry bits reported for each byte which 232 is *not* 0 */ 233 jnc L(73) /* highest byte is NUL => return NULL */ 234 xorl %ecx, %edi /* (word+magic)^word */ 235 orl $0xfefefeff, %edi /* set all non-carry bits */ 236 incl %edi /* add 1: if one carry bit was *not* set 237 the addition will not result in 0. */ 238 jz L(1) /* no NUL found => restart loop */ 239 240L(73): addl $4, %eax /* adjust pointer */ 241L(72): addl $4, %eax 242L(71): addl $4, %eax 243 244 /* We now scan for the byte in which the character was matched. 245 But we have to take care of the case that a NUL char is 246 found before this in the dword. */ 247 248L(7): testb %cl, %cl /* is first byte CHR? */ 249 jz L(6) /* yes => return pointer */ 250 cmpb %dl, %cl /* is first byte NUL? */ 251 je L(6) /* yes => return NULL */ 252 incl %eax /* it's not in the first byte */ 253 254 testb %ch, %ch /* is second byte CHR? */ 255 jz L(6) /* yes => return pointer */ 256 cmpb %dl, %ch /* is second byte NUL? */ 257 je L(6) /* yes => return NULL? */ 258 incl %eax /* it's not in the second byte */ 259 260 shrl $16, %ecx /* make upper byte accessible */ 261 testb %cl, %cl /* is third byte CHR? */ 262 jz L(6) /* yes => return pointer */ 263 cmpb %dl, %cl /* is third byte NUL? */ 264 je L(6) /* yes => return NULL */ 265 266 /* It must be in the fourth byte and it cannot be NUL. */ 267 incl %eax 268 269L(6): popl %edi /* restore saved register content */ 270 cfi_adjust_cfa_offset (-4) 271 cfi_restore (edi) 272 273 ret 274END (__strchrnul) 275 276weak_alias (__strchrnul, strchrnul) 277