sysdeps/i386/strchrnul.S

   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-2024 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
  30 ENTRY (__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
 119 L(1):   addl $16, %eax          /* adjust pointer for whole round */
 120
 121 L(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
 240 L(73):  addl $4, %eax           /* adjust pointer */
 241 L(72):  addl $4, %eax
 242 L(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
 248 L(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
 269 L(6):   popl %edi               /* restore saved register content */
 270         cfi_adjust_cfa_offset (-4)
 271         cfi_restore (edi)
 272
 273         ret
 274 END (__strchrnul)
 275
 276 libc_hidden_def (__strchrnul)
 277 weak_alias (__strchrnul, strchrnul)