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