libc/string/x86_64/strchr.S

   1 /* strchr (str, ch) -- Return pointer to first occurrence of CH in STR.
   2    For AMD x86-64.
   3    Copyright (C) 2002, 2005 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    <http://www.gnu.org/licenses/>.  */
  19
  20 #include "_glibc_inc.h"
  21
  22 /* Seems to be unrolled too much */
  23
  24         .text
  25 ENTRY (BP_SYM (strchr))
  26
  27         /* Before we start with the main loop we process single bytes
  28            until the source pointer is aligned.  This has two reasons:
  29            1. aligned 64-bit memory access is faster
  30            and (more important)
  31            2. we process in the main loop 64 bit in one step although
  32               we don't know the end of the string.  But accessing at
  33               8-byte alignment guarantees that we never access illegal
  34               memory if this would not also be done by the trivial
  35               implementation (this is because all processor inherent
  36               boundaries are multiples of 8).  */
  37
  38         movq    %rdi, %rdx
  39         andl    $7, %edx        /* Mask alignment bits  */
  40         movq    %rdi, %rax      /* duplicate destination.  */
  41         jz      1f              /* aligned => start loop */
  42         neg     %edx
  43         addl    $8, %edx        /* Align to 8 bytes.  */
  44
  45         /* Search the first bytes directly.  */
  46 0:      movb    (%rax), %cl     /* load byte  */
  47         cmpb    %cl,%sil        /* compare byte.  */
  48         je      6f              /* target found */
  49         testb   %cl,%cl         /* is byte NUL? */
  50         je      7f              /* yes => return NULL */
  51         incq    %rax            /* increment pointer */
  52         decl    %edx
  53         jnz     0b
  54
  55
  56 1:
  57         /* At the moment %rsi contains C.  What we need for the
  58            algorithm is C in all bytes of the register.  Avoid
  59            operations on 16 bit words because these require an
  60            prefix byte (and one more cycle).  */
  61         /* Populate 8 bit data to full 64-bit.  */
  62         movabs  $0x0101010101010101,%r9
  63         movzbl  %sil,%edx
  64         imul    %rdx,%r9
  65
  66         movq $0xfefefefefefefeff, %r8 /* Save magic.  */
  67
  68       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
  69          change any of the hole bits of LONGWORD.
  70
  71          1) Is this safe?  Will it catch all the zero bytes?
  72          Suppose there is a byte with all zeros.  Any carry bits
  73          propagating from its left will fall into the hole at its
  74          least significant bit and stop.  Since there will be no
  75          carry from its most significant bit, the LSB of the
  76          byte to the left will be unchanged, and the zero will be
  77          detected.
  78
  79          2) Is this worthwhile?  Will it ignore everything except
  80          zero bytes?  Suppose every byte of QUARDWORD has a bit set
  81          somewhere.  There will be a carry into bit 8.  If bit 8
  82          is set, this will carry into bit 16.  If bit 8 is clear,
  83          one of bits 9-15 must be set, so there will be a carry
  84          into bit 16.  Similarly, there will be a carry into bit
  85          24 tec..  If one of bits 54-63 is set, there will be a carry
  86          into bit 64 (=carry flag), so all of the hole bits will
  87          be changed.
  88
  89          3) But wait!  Aren't we looking for C, not zero?
  90          Good point.  So what we do is XOR LONGWORD with a longword,
  91          each of whose bytes is C.  This turns each byte that is C
  92          into a zero.  */
  93
  94         /* Next 3 insns are 10 bytes total, make sure we decode them in one go */
  95         .p2align 4,,10
  96 4:
  97         /* Main Loop is unrolled 4 times.  */
  98         /* First unroll.  */
  99         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
 100         addq $8,%rax            /* adjust pointer for next word */
 101         movq %r8, %rdx          /* magic value */
 102         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
 103                                    are now 0 */
 104         addq %rcx, %rdx         /* add the magic value to the word.  We get
 105                                    carry bits reported for each byte which
 106                                    is *not* 0 */
 107         jnc 3f                  /* highest byte is NUL => return pointer */
 108         xorq %rcx, %rdx         /* (word+magic)^word */
 109         orq %r8, %rdx           /* set all non-carry bits */
 110         incq %rdx               /* add 1: if one carry bit was *not* set
 111                                    the addition will not result in 0.  */
 112         jnz 3f                  /* found c => return pointer */
 113
 114         /* The quadword we looked at does not contain the value we're looking
 115            for.  Let's search now whether we have reached the end of the
 116            string.  */
 117         xorq %r9, %rcx          /* restore original dword without reload */
 118         movq %r8, %rdx          /* magic value */
 119         addq %rcx, %rdx         /* add the magic value to the word.  We get
 120                                    carry bits reported for each byte which
 121                                    is *not* 0 */
 122         jnc 7f                  /* highest byte is NUL => return NULL */
 123         xorq %rcx, %rdx         /* (word+magic)^word */
 124         orq %r8, %rdx           /* set all non-carry bits */
 125         incq %rdx               /* add 1: if one carry bit was *not* set
 126                                    the addition will not result in 0.  */
 127         jnz 7f                  /* found NUL => return NULL */
 128
 129         /* Second unroll.  */
 130         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
 131         addq $8,%rax            /* adjust pointer for next word */
 132         movq %r8, %rdx          /* magic value */
 133         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
 134                                    are now 0 */
 135         addq %rcx, %rdx         /* add the magic value to the word.  We get
 136                                    carry bits reported for each byte which
 137                                    is *not* 0 */
 138         jnc 3f                  /* highest byte is NUL => return pointer */
 139         xorq %rcx, %rdx         /* (word+magic)^word */
 140         orq %r8, %rdx           /* set all non-carry bits */
 141         incq %rdx               /* add 1: if one carry bit was *not* set
 142                                    the addition will not result in 0.  */
 143         jnz 3f                  /* found c => return pointer */
 144
 145         /* The quadword we looked at does not contain the value we're looking
 146            for.  Let's search now whether we have reached the end of the
 147            string.  */
 148         xorq %r9, %rcx          /* restore original dword without reload */
 149         movq %r8, %rdx          /* magic value */
 150         addq %rcx, %rdx         /* add the magic value to the word.  We get
 151                                    carry bits reported for each byte which
 152                                    is *not* 0 */
 153         jnc 7f                  /* highest byte is NUL => return NULL */
 154         xorq %rcx, %rdx         /* (word+magic)^word */
 155         orq %r8, %rdx           /* set all non-carry bits */
 156         incq %rdx               /* add 1: if one carry bit was *not* set
 157                                    the addition will not result in 0.  */
 158         jnz 7f                  /* found NUL => return NULL */
 159         /* Third unroll.  */
 160         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
 161         addq $8,%rax            /* adjust pointer for next word */
 162         movq %r8, %rdx          /* magic value */
 163         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
 164                                    are now 0 */
 165         addq %rcx, %rdx         /* add the magic value to the word.  We get
 166                                    carry bits reported for each byte which
 167                                    is *not* 0 */
 168         jnc 3f                  /* highest byte is NUL => return pointer */
 169         xorq %rcx, %rdx         /* (word+magic)^word */
 170         orq %r8, %rdx           /* set all non-carry bits */
 171         incq %rdx               /* add 1: if one carry bit was *not* set
 172                                    the addition will not result in 0.  */
 173         jnz 3f                  /* found c => return pointer */
 174
 175         /* The quadword we looked at does not contain the value we're looking
 176            for.  Let's search now whether we have reached the end of the
 177            string.  */
 178         xorq %r9, %rcx          /* restore original dword without reload */
 179         movq %r8, %rdx          /* magic value */
 180         addq %rcx, %rdx         /* add the magic value to the word.  We get
 181                                    carry bits reported for each byte which
 182                                    is *not* 0 */
 183         jnc 7f                  /* highest byte is NUL => return NULL */
 184         xorq %rcx, %rdx         /* (word+magic)^word */
 185         orq %r8, %rdx           /* set all non-carry bits */
 186         incq %rdx               /* add 1: if one carry bit was *not* set
 187                                    the addition will not result in 0.  */
 188         jnz 7f                  /* found NUL => return NULL */
 189         /* Fourth unroll.  */
 190         movq (%rax), %rcx       /* get double word (= 8 bytes) in question */
 191         addq $8,%rax            /* adjust pointer for next word */
 192         movq %r8, %rdx          /* magic value */
 193         xorq %r9, %rcx          /* XOR with qword c|...|c => bytes of str == c
 194                                    are now 0 */
 195         addq %rcx, %rdx         /* add the magic value to the word.  We get
 196                                    carry bits reported for each byte which
 197                                    is *not* 0 */
 198         jnc 3f                  /* highest byte is NUL => return pointer */
 199         xorq %rcx, %rdx         /* (word+magic)^word */
 200         orq %r8, %rdx           /* set all non-carry bits */
 201         incq %rdx               /* add 1: if one carry bit was *not* set
 202                                    the addition will not result in 0.  */
 203         jnz 3f                  /* found c => return pointer */
 204
 205         /* The quadword we looked at does not contain the value we're looking
 206            for.  Let's search now whether we have reached the end of the
 207            string.  */
 208         xorq %r9, %rcx          /* restore original dword without reload */
 209         movq %r8, %rdx          /* magic value */
 210         addq %rcx, %rdx         /* add the magic value to the word.  We get
 211                                    carry bits reported for each byte which
 212                                    is *not* 0 */
 213         jnc 7f                  /* highest byte is NUL => return NULL */
 214         xorq %rcx, %rdx         /* (word+magic)^word */
 215         orq %r8, %rdx           /* set all non-carry bits */
 216         incq %rdx               /* add 1: if one carry bit was *not* set
 217                                    the addition will not result in 0.  */
 218         jz 4b                   /* no NUL found => restart loop */
 219
 220
 221 7:      /* Return NULL.  */
 222         xorl %eax, %eax
 223         retq
 224
 225
 226         /* We now scan for the byte in which the character was matched.
 227            But we have to take care of the case that a NUL char is
 228            found before this in the dword.  Note that we XORed %rcx
 229            with the byte we're looking for, therefore the tests below look
 230            reversed.  */
 231
 232
 233         /* Align, it's a jump target.  */
 234         /* Next 3 insns are 9 bytes total, make sure we decode them in one go */
 235         .p2align 4,,9
 236 3:
 237         movq    %r9,%rdx        /* move to %rdx so that we can access bytes */
 238         subq    $8,%rax         /* correct pointer increment.  */
 239         testb %cl, %cl          /* is first byte C? */
 240         jz 6f                   /* yes => return pointer */
 241         cmpb %dl, %cl           /* is first byte NUL? */
 242         je 7b                   /* yes => return NULL */
 243         incq %rax               /* increment pointer */
 244
 245         testb %ch, %ch          /* is second byte C? */
 246         jz 6f                   /* yes => return pointer */
 247         cmpb %dl, %ch           /* is second byte NUL? */
 248         je 7b                   /* yes => return NULL? */
 249         incq %rax               /* increment pointer */
 250
 251         shrq $16, %rcx          /* make upper bytes accessible */
 252         testb %cl, %cl          /* is third byte C? */
 253         jz 6f                   /* yes => return pointer */
 254         cmpb %dl, %cl           /* is third byte NUL? */
 255         je 7b                   /* yes => return NULL */
 256         incq %rax               /* increment pointer */
 257
 258         testb %ch, %ch          /* is fourth byte C? */
 259         jz 6f                   /* yes => return pointer */
 260         cmpb %dl, %ch           /* is fourth byte NUL? */
 261         je 7b                   /* yes => return NULL? */
 262         incq %rax               /* increment pointer */
 263
 264         shrq $16, %rcx          /* make upper bytes accessible */
 265         testb %cl, %cl          /* is fifth byte C? */
 266         jz 6f                   /* yes => return pointer */
 267         cmpb %dl, %cl           /* is fifth byte NUL? */
 268         je 7b                   /* yes => return NULL */
 269         incq %rax               /* increment pointer */
 270
 271         testb %ch, %ch          /* is sixth byte C? */
 272         jz 6f                   /* yes => return pointer */
 273         cmpb %dl, %ch           /* is sixth byte NUL? */
 274         je 7b                   /* yes => return NULL? */
 275         incq %rax               /* increment pointer */
 276
 277         shrq $16, %rcx          /* make upper bytes accessible */
 278         testb %cl, %cl          /* is seventh byte C? */
 279         jz 6f                   /* yes => return pointer */
 280         cmpb %dl, %cl           /* is seventh byte NUL? */
 281         je 7b                   /* yes => return NULL */
 282
 283         /* It must be in the eigth byte and it cannot be NUL.  */
 284         incq %rax
 285
 286 6:
 287         /* nop - huh?? */
 288         retq
 289 END (BP_SYM (strchr))
 290
 291 libc_hidden_def(strchr)
 292 #ifdef __UCLIBC_SUSV3_LEGACY__
 293 strong_alias (BP_SYM (strchr), BP_SYM (index))
 294 #endif