sysdeps/x86_64/multiarch/strchr.S

   1 /* strchr with SSE4.2
   2    Copyright (C) 2009 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, write to the Free
  17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  18    02111-1307 USA.  */
  19
  20 #include <sysdep.h>
  21 #include <ifunc-defines.h>
  22
  23
  24 /* Define multiple versions only for the definition in libc.  */
  25 #ifndef NOT_IN_libc
  26         .text
  27 ENTRY(strchr)
  28         .type   strchr, @gnu_indirect_function
  29         cmpl    $0, __cpu_features+KIND_OFFSET(%rip)
  30         jne     1f
  31         call    __init_cpu_features
  32 1:      leaq    __strchr_sse2(%rip), %rax
  33         testl   $(1<<20), __cpu_features+CPUID_OFFSET+COMMON_CPUID_INDEX_1*CPUID_SIZE+CPUID_ECX_OFFSET(%rip)
  34         jz      2f
  35         leaq    __strchr_sse42(%rip), %rax
  36 2:      ret
  37 END(strchr)
  38
  39
  40 /*
  41    This implementation uses SSE4 instructions to compare up to 16 bytes
  42    at a time looking for the first occurrence of the character c in the
  43    string s:
  44
  45    char *strchr (const char *s, int c);
  46
  47    We use 0xa:
  48         _SIDD_SBYTE_OPS
  49         | _SIDD_CMP_EQUAL_EACH
  50         | _SIDD_LEAST_SIGNIFICANT
  51    on pcmpistri to compare xmm/mem128
  52
  53    0 1 2 3 4 5 6 7 8 9 A B C D E F
  54    X X X X X X X X X X X X X X X X
  55
  56    against xmm
  57
  58    0 1 2 3 4 5 6 7 8 9 A B C D E F
  59    C C C C C C C C C C C C C C C C
  60
  61    to find out if the first 16byte data element has a byte C and the
  62    offset of the first byte.  There are 3 cases:
  63
  64    1. The first 16byte data element has the byte C at the offset X.
  65    2. The first 16byte data element has EOS and doesn't have the byte C.
  66    3. The first 16byte data element is valid and doesn't have the byte C.
  67
  68    Here is the table of ECX, CFlag, ZFlag and SFlag for 3 cases:
  69
  70    case         ECX     CFlag   ZFlag   SFlag
  71     1            X        1      0/1      0
  72     2           16        0       1       0
  73     3           16        0       0       0
  74
  75    We exit from the loop for cases 1 and 2 with jbe which branches
  76    when either CFlag or ZFlag is 1.  If CFlag == 1, ECX has the offset
  77    X for case 1.  */
  78
  79         .section .text.sse4.2,"ax",@progbits
  80         .align  16
  81         .type   __strchr_sse42, @function
  82 __strchr_sse42:
  83         cfi_startproc
  84         CALL_MCOUNT
  85         testb   %sil, %sil
  86         je      __strend_sse4
  87         pxor    %xmm2, %xmm2
  88         movd    %esi, %xmm1
  89         movl    %edi, %ecx
  90         andl    $15, %ecx
  91         movq    %rdi, %r8
  92         je      L(aligned_start)
  93
  94 /* Handle unaligned string.  */
  95         andq    $-16, %r8
  96         pshufb  %xmm2, %xmm1
  97         movdqa  (%r8), %xmm0
  98         pcmpeqb  %xmm0, %xmm2
  99         pcmpeqb  %xmm1, %xmm0
 100         /* Find where NULL is.  */
 101         pmovmskb %xmm2, %edx
 102         /* Check if there is a match.  */
 103         pmovmskb %xmm0, %esi
 104         /* Remove the leading  bytes.  */
 105         sarl    %cl, %edx
 106         sarl    %cl, %esi
 107         testl   %esi, %esi
 108         je      L(unaligned_no_match)
 109         /* Check which byte is a match.  */
 110         bsfl    %esi, %eax
 111         /* Is there a NULL? */
 112         testl   %edx, %edx
 113         je      L(unaligned_match)
 114         bsfl    %edx, %esi
 115         cmpl    %esi, %eax
 116         /* Return NULL if NULL comes first.  */
 117         ja      L(return_null)
 118 L(unaligned_match):
 119         addq    %rdi, %rax
 120         ret
 121
 122         .p2align 4
 123 L(unaligned_no_match):
 124         testl   %edx, %edx
 125         jne     L(return_null)
 126
 127 /* Loop start on aligned string.  */
 128 L(loop):
 129         addq    $16, %r8
 130 L(aligned_start):
 131         pcmpistri       $0x2, (%r8), %xmm1
 132         jbe     L(wrap)
 133         addq    $16, %r8
 134         pcmpistri       $0x2, (%r8), %xmm1
 135         jbe     L(wrap)
 136         addq    $16, %r8
 137         pcmpistri       $0x2, (%r8), %xmm1
 138         jbe     L(wrap)
 139         addq    $16, %r8
 140         pcmpistri       $0x2, (%r8), %xmm1
 141         jbe     L(wrap)
 142         jmp     L(loop)
 143 L(wrap):
 144         jc      L(loop_exit)
 145
 146 /* Return NULL.  */
 147 L(return_null):
 148         xorl    %eax, %eax
 149         ret
 150
 151 /* Loop exit.  */
 152         .p2align 4
 153 L(loop_exit):
 154         leaq    (%r8,%rcx), %rax
 155         ret
 156         cfi_endproc
 157         .size   __strchr_sse42, .-__strchr_sse42
 158
 159
 160 # undef ENTRY
 161 # define ENTRY(name) \
 162         .type __strchr_sse2, @function; \
 163         .align 16; \
 164         __strchr_sse2: cfi_startproc; \
 165         CALL_MCOUNT
 166 # undef END
 167 # define END(name) \
 168         cfi_endproc; .size __strchr_sse2, .-__strchr_sse2
 169 # undef libc_hidden_builtin_def
 170 /* It doesn't make sense to send libc-internal strchr calls through a PLT.
 171    The speedup we get from using SSE4.2 instruction is likely eaten away
 172    by the indirect call in the PLT.  */
 173 # define libc_hidden_builtin_def(name) \
 174         .globl __GI_strchr; __GI_strchr = __strchr_sse2
 175 #endif
 176
 177 #include "../strchr.S"