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