sysdeps/x86_64/multiarch/strcspn-c.c

   1 /* strcspn with SSE4.2 intrinsics
   2    Copyright (C) 2009, 2010 Free Software Foundation, Inc.
   3    Contributed by Intel Corporation.
   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 <nmmintrin.h>
  22 #include <string.h>
  23 #include "varshift.h"
  24
  25 /* We use 0x2:
  26         _SIDD_SBYTE_OPS
  27         | _SIDD_CMP_EQUAL_ANY
  28         | _SIDD_POSITIVE_POLARITY
  29         | _SIDD_LEAST_SIGNIFICANT
  30    on pcmpistri to compare xmm/mem128
  31
  32    0 1 2 3 4 5 6 7 8 9 A B C D E F
  33    X X X X X X X X X X X X X X X X
  34
  35    against xmm
  36
  37    0 1 2 3 4 5 6 7 8 9 A B C D E F
  38    A A A A A A A A A A A A A A A A
  39
  40    to find out if the first 16byte data element has any byte A and
  41    the offset of the first byte.  There are 3 cases:
  42
  43    1. The first 16byte data element has the byte A at the offset X.
  44    2. The first 16byte data element has EOS and doesn't have the byte A.
  45    3. The first 16byte data element is valid and doesn't have the byte A.
  46
  47    Here is the table of ECX, CFlag, ZFlag and SFlag for 2 cases:
  48
  49     1            X        1      0/1      0
  50     2           16        0       1       0
  51     3           16        0       0       0
  52
  53    We exit from the loop for cases 1 and 2 with jbe which branches
  54    when either CFlag or ZFlag is 1.  If CFlag == 1, ECX has the offset
  55    X for case 1.  */
  56
  57 #ifndef STRCSPN_SSE2
  58 # define STRCSPN_SSE2 __strcspn_sse2
  59 # define STRCSPN_SSE42 __strcspn_sse42
  60 #endif
  61
  62 #ifdef USE_AS_STRPBRK
  63 # define RETURN(val1, val2) return val1
  64 #else
  65 # define RETURN(val1, val2) return val2
  66 #endif
  67
  68 extern
  69 #ifdef USE_AS_STRPBRK
  70 char *
  71 #else
  72 size_t
  73 #endif
  74 STRCSPN_SSE2 (const char *, const char *);
  75
  76
  77 #ifdef USE_AS_STRPBRK
  78 char *
  79 #else
  80 size_t
  81 #endif
  82 __attribute__ ((section (".text.sse4.2")))
  83 STRCSPN_SSE42 (const char *s, const char *a)
  84 {
  85   if (*a == 0)
  86     RETURN (NULL, strlen (s));
  87
  88   const char *aligned;
  89   __m128i mask;
  90   int offset = (int) ((size_t) a & 15);
  91   if (offset != 0)
  92     {
  93       /* Load masks.  */
  94       aligned = (const char *) ((size_t) a & -16L);
  95       __m128i mask0 = _mm_load_si128 ((__m128i *) aligned);
  96
  97       mask = __m128i_shift_right (mask0, offset);
  98
  99       /* Find where the NULL terminator is.  */
 100       int length = _mm_cmpistri (mask, mask, 0x3a);
 101       if (length == 16 - offset)
 102         {
 103           /* There is no NULL terminator.  */
 104           __m128i mask1 = _mm_load_si128 ((__m128i *) (aligned + 16));
 105           int index = _mm_cmpistri (mask1, mask1, 0x3a);
 106           length += index;
 107
 108           /* Don't use SSE4.2 if the length of A > 16.  */
 109           if (length > 16)
 110             return STRCSPN_SSE2 (s, a);
 111
 112           if (index != 0)
 113             {
 114               /* Combine mask0 and mask1.  We could play games with
 115                  palignr, but frankly this data should be in L1 now
 116                  so do the merge via an unaligned load.  */
 117               mask = _mm_loadu_si128 ((__m128i *) a);
 118             }
 119         }
 120     }
 121   else
 122     {
 123       /* A is aligned.  */
 124       mask = _mm_load_si128 ((__m128i *) a);
 125
 126       /* Find where the NULL terminator is.  */
 127       int length = _mm_cmpistri (mask, mask, 0x3a);
 128       if (length == 16)
 129         {
 130           /* There is no NULL terminator.  Don't use SSE4.2 if the length
 131              of A > 16.  */
 132           if (a[16] != 0)
 133             return STRCSPN_SSE2 (s, a);
 134         }
 135     }
 136
 137   offset = (int) ((size_t) s & 15);
 138   if (offset != 0)
 139     {
 140       /* Check partial string.  */
 141       aligned = (const char *) ((size_t) s & -16L);
 142       __m128i value = _mm_load_si128 ((__m128i *) aligned);
 143
 144       value = __m128i_shift_right (value, offset);
 145
 146       int length = _mm_cmpistri (mask, value, 0x2);
 147       /* No need to check ZFlag since ZFlag is always 1.  */
 148       int cflag = _mm_cmpistrc (mask, value, 0x2);
 149       if (cflag)
 150         RETURN ((char *) (s + length), length);
 151       /* Find where the NULL terminator is.  */
 152       int index = _mm_cmpistri (value, value, 0x3a);
 153       if (index < 16 - offset)
 154         RETURN (NULL, index);
 155       aligned += 16;
 156     }
 157   else
 158     aligned = s;
 159
 160   while (1)
 161     {
 162       __m128i value = _mm_load_si128 ((__m128i *) aligned);
 163       int index = _mm_cmpistri (mask, value, 0x2);
 164       int cflag = _mm_cmpistrc (mask, value, 0x2);
 165       int zflag = _mm_cmpistrz (mask, value, 0x2);
 166       if (cflag)
 167         RETURN ((char *) (aligned + index), (size_t) (aligned + index - s));
 168       if (zflag)
 169         RETURN (NULL,
 170                 /* Find where the NULL terminator is.  */
 171                 (size_t) (aligned + _mm_cmpistri (value, value, 0x3a) - s));
 172       aligned += 16;
 173     }
 174 }