sysdeps/x86_64/multiarch/strcspn-c.c

   1 /* strcspn with SSE4.2 intrinsics
   2    Copyright (C) 2009 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
  24 /* We use 0x2:
  25         _SIDD_SBYTE_OPS
  26         | _SIDD_CMP_EQUAL_ANY
  27         | _SIDD_POSITIVE_POLARITY
  28         | _SIDD_LEAST_SIGNIFICANT
  29    on pcmpistri to compare xmm/mem128
  30
  31    0 1 2 3 4 5 6 7 8 9 A B C D E F
  32    X X X X X X X X X X X X X X X X
  33
  34    against xmm
  35
  36    0 1 2 3 4 5 6 7 8 9 A B C D E F
  37    A A A A A A A A A A A A A A A A
  38
  39    to find out if the first 16byte data element has any byte A and
  40    the offset of the first byte.  There are 3 cases:
  41
  42    1. The first 16byte data element has the byte A at the offset X.
  43    2. The first 16byte data element has EOS and doesn't have the byte A.
  44    3. The first 16byte data element is valid and doesn't have the byte A.
  45
  46    Here is the table of ECX, CFlag, ZFlag and SFlag for 2 cases:
  47
  48     1            X        1      0/1      0
  49     2           16        0       1       0
  50     3           16        0       0       0
  51
  52    We exit from the loop for cases 1 and 2 with jbe which branches
  53    when either CFlag or ZFlag is 1.  If CFlag == 1, ECX has the offset
  54    X for case 1.  */
  55
  56 #ifndef STRCSPN_SSE2
  57 # define STRCSPN_SSE2 __strcspn_sse2
  58 # define STRCSPN_SSE42 __strcspn_sse42
  59 #endif
  60
  61 #ifdef USE_AS_STRPBRK
  62 # define RETURN(val1, val2) return val1
  63 #else
  64 # define RETURN(val1, val2) return val2
  65 #endif
  66
  67 extern
  68 #ifdef USE_AS_STRPBRK
  69 char *
  70 #else
  71 size_t
  72 #endif
  73 STRCSPN_SSE2 (const char *, const char *);
  74
  75
  76 #ifdef USE_AS_STRPBRK
  77 char *
  78 #else
  79 size_t
  80 #endif
  81 __attribute__ ((section (".text.sse4.2")))
  82 STRCSPN_SSE42 (const char *s, const char *a)
  83 {
  84   if (*a == 0)
  85     RETURN (NULL, strlen (s));
  86
  87   const char *aligned;
  88   __m128i mask;
  89   int offset = (int) ((size_t) a & 15);
  90   if (offset != 0)
  91     {
  92       /* Load masks.  */
  93       aligned = (const char *) ((size_t) a & -16L);
  94       __m128i mask0 = _mm_load_si128 ((__m128i *) aligned);
  95
  96       switch (offset)
  97         {
  98         case 1:
  99           mask = _mm_srli_si128 (mask0, 1);
 100           break;
 101         case 2:
 102           mask = _mm_srli_si128 (mask0, 2);
 103           break;
 104         case 3:
 105           mask = _mm_srli_si128 (mask0, 3);
 106           break;
 107         case 4:
 108           mask = _mm_srli_si128 (mask0, 4);
 109           break;
 110         case 5:
 111           mask = _mm_srli_si128 (mask0, 5);
 112           break;
 113         case 6:
 114           mask = _mm_srli_si128 (mask0, 6);
 115           break;
 116         case 7:
 117           mask = _mm_srli_si128 (mask0, 7);
 118           break;
 119         case 8:
 120           mask = _mm_srli_si128 (mask0, 8);
 121           break;
 122         case 9:
 123           mask = _mm_srli_si128 (mask0, 9);
 124           break;
 125         case 10:
 126           mask = _mm_srli_si128 (mask0, 10);
 127           break;
 128         case 11:
 129           mask = _mm_srli_si128 (mask0, 11);
 130           break;
 131         case 12:
 132           mask = _mm_srli_si128 (mask0, 12);
 133           break;
 134         case 13:
 135           mask = _mm_srli_si128 (mask0, 13);
 136           break;
 137         case 14:
 138           mask = _mm_srli_si128 (mask0, 14);
 139           break;
 140         case 15:
 141           mask = _mm_srli_si128 (mask0, 15);
 142           break;
 143         }
 144
 145       /* Find where the NULL terminator is.  */
 146       int length = _mm_cmpistri (mask, mask, 0x3a);
 147       if (length == 16 - offset)
 148         {
 149           /* There is no NULL terminator.  */
 150           __m128i mask1 = _mm_load_si128 ((__m128i *) (aligned + 16));
 151           int index = _mm_cmpistri (mask1, mask1, 0x3a);
 152           length += index;
 153
 154           /* Don't use SSE4.2 if the length of A > 16.  */
 155           if (length > 16)
 156             return STRCSPN_SSE2 (s, a);
 157
 158           if (index != 0)
 159             {
 160               /* Combine mask0 and mask1.  */
 161               switch (offset)
 162                 {
 163                 case 1:
 164                   mask = _mm_alignr_epi8 (mask1, mask0, 1);
 165                   break;
 166                 case 2:
 167                   mask = _mm_alignr_epi8 (mask1, mask0, 2);
 168                   break;
 169                 case 3:
 170                   mask = _mm_alignr_epi8 (mask1, mask0, 3);
 171                   break;
 172                 case 4:
 173                   mask = _mm_alignr_epi8 (mask1, mask0, 4);
 174                   break;
 175                 case 5:
 176                   mask = _mm_alignr_epi8 (mask1, mask0, 5);
 177                   break;
 178                 case 6:
 179                   mask = _mm_alignr_epi8 (mask1, mask0, 6);
 180                   break;
 181                 case 7:
 182                   mask = _mm_alignr_epi8 (mask1, mask0, 7);
 183                   break;
 184                 case 8:
 185                   mask = _mm_alignr_epi8 (mask1, mask0, 8);
 186                   break;
 187                 case 9:
 188                   mask = _mm_alignr_epi8 (mask1, mask0, 9);
 189                   break;
 190                 case 10:
 191                   mask = _mm_alignr_epi8 (mask1, mask0, 10);
 192                   break;
 193                 case 11:
 194                   mask = _mm_alignr_epi8 (mask1, mask0, 11);
 195                   break;
 196                 case 12:
 197                   mask = _mm_alignr_epi8 (mask1, mask0, 12);
 198                   break;
 199                 case 13:
 200                   mask = _mm_alignr_epi8 (mask1, mask0, 13);
 201                   break;
 202                 case 14:
 203                   mask = _mm_alignr_epi8 (mask1, mask0, 14);
 204                   break;
 205                 case 15:
 206                   mask = _mm_alignr_epi8 (mask1, mask0, 15);
 207                   break;
 208                 }
 209             }
 210         }
 211     }
 212   else
 213     {
 214       /* A is aligned.  */
 215       mask = _mm_load_si128 ((__m128i *) a);
 216
 217       /* Find where the NULL terminator is.  */
 218       int length = _mm_cmpistri (mask, mask, 0x3a);
 219       if (length == 16)
 220         {
 221           /* There is no NULL terminator.  Don't use SSE4.2 if the length
 222              of A > 16.  */
 223           if (a[16] != 0)
 224             return STRCSPN_SSE2 (s, a);
 225         }
 226     }
 227
 228   offset = (int) ((size_t) s & 15);
 229   if (offset != 0)
 230     {
 231       /* Check partial string.  */
 232       aligned = (const char *) ((size_t) s & -16L);
 233       __m128i value = _mm_load_si128 ((__m128i *) aligned);
 234
 235       switch (offset)
 236         {
 237         case 1:
 238           value = _mm_srli_si128 (value, 1);
 239           break;
 240         case 2:
 241           value = _mm_srli_si128 (value, 2);
 242           break;
 243         case 3:
 244           value = _mm_srli_si128 (value, 3);
 245           break;
 246         case 4:
 247           value = _mm_srli_si128 (value, 4);
 248           break;
 249         case 5:
 250           value = _mm_srli_si128 (value, 5);
 251           break;
 252         case 6:
 253           value = _mm_srli_si128 (value, 6);
 254           break;
 255         case 7:
 256           value = _mm_srli_si128 (value, 7);
 257           break;
 258         case 8:
 259           value = _mm_srli_si128 (value, 8);
 260           break;
 261         case 9:
 262           value = _mm_srli_si128 (value, 9);
 263           break;
 264         case 10:
 265           value = _mm_srli_si128 (value, 10);
 266           break;
 267         case 11:
 268           value = _mm_srli_si128 (value, 11);
 269           break;
 270         case 12:
 271           value = _mm_srli_si128 (value, 12);
 272           break;
 273         case 13:
 274           value = _mm_srli_si128 (value, 13);
 275           break;
 276         case 14:
 277           value = _mm_srli_si128 (value, 14);
 278           break;
 279         case 15:
 280           value = _mm_srli_si128 (value, 15);
 281           break;
 282         }
 283
 284       int length = _mm_cmpistri (mask, value, 0x2);
 285       /* No need to check ZFlag since ZFlag is always 1.  */
 286       int cflag = _mm_cmpistrc (mask, value, 0x2);
 287       if (cflag)
 288         RETURN ((char *) (s + length), length);
 289       /* Find where the NULL terminator is.  */
 290       int index = _mm_cmpistri (value, value, 0x3a);
 291       if (index < 16 - offset)
 292         RETURN (NULL, index);
 293       aligned += 16;
 294     }
 295   else
 296     aligned = s;
 297
 298   while (1)
 299     {
 300       __m128i value = _mm_load_si128 ((__m128i *) aligned);
 301       int index = _mm_cmpistri (mask, value, 0x2);
 302       int cflag = _mm_cmpistrc (mask, value, 0x2);
 303       int zflag = _mm_cmpistrz (mask, value, 0x2);
 304       if (cflag)
 305         RETURN ((char *) (aligned + index), (size_t) (aligned + index - s));
 306       if (zflag)
 307         RETURN (NULL,
 308                 /* Find where the NULL terminator is.  */
 309                 (size_t) (aligned + _mm_cmpistri (value, value, 0x3a) - s));
 310       aligned += 16;
 311     }
 312 }