sysdeps/i386/strrchr.S

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