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