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