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