sysdeps/i386/strchr.S

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