sysdeps/x86_64/multiarch/strstr.c

   1 /* strstr 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
  23 #ifndef STRSTR_SSE42
  24 # define STRSTR_SSE42 __strstr_sse42
  25 #endif
  26
  27 #ifdef USE_AS_STRCASESTR
  28 # include <ctype.h>
  29 # include <locale/localeinfo.h>
  30
  31 # define LOADBYTE(C)            tolower (C)
  32 # define CMPBYTE(C1, C2)        (tolower (C1) == tolower (C2))
  33 #else
  34 # define LOADBYTE(C)            (C)
  35 # define CMPBYTE(C1, C2)        ((C1) == (C2))
  36 #endif
  37
  38 /* We use 0xe ordered-compare:
  39         _SIDD_SBYTE_OPS
  40         | _SIDD_CMP_EQUAL_ORDER
  41         | _SIDD_LEAST_SIGNIFICANT
  42    on pcmpistri to do the scanning and string comparsion requirements of
  43    sub-string match.  In the scanning phase, we process Cflag and ECX
  44    index to locate the first fragment match; once the first fragment
  45    match position has been identified, we do comparison of subsequent
  46    string fragments until we can conclude false or true match; whe
  47    n concluding a false match, we may need to repeat scanning process
  48    from next relevant offset in the target string.
  49
  50    In the scanning phase we have 4 cases:
  51    case         ECX     CFlag   ZFlag   SFlag
  52     1           16        0       0       0
  53     2a          16        0       0       1
  54     2b          16        0       1       0
  55     2c          16        0       1       1
  56
  57    1. No ordered-comparison match, both 16B fragments are valid, so
  58       continue to next fragment.
  59    2. No ordered-comparison match, there is EOS in either fragment,
  60    2a. Zflg = 0, Sflg = 1, we continue
  61    2b. Zflg = 1, Sflg = 0, we conclude no match and return.
  62    2c. Zflg = 1, sflg = 1, lenth determine match or no match
  63
  64    In the string comparison phase, the 1st fragment match is fixed up
  65    to produce ECX = 0.  Subsequent fragment compare of nonzero index
  66    and no match conclude a false match.
  67
  68    case         ECX     CFlag   ZFlag   SFlag
  69     3            X        1       0       0/1
  70     4a           0        1       0       0
  71     4b           0        1       0       1
  72     4c          0 < X     1       0       0/1
  73     5           16        0       1       0
  74
  75    3. An initial ordered-comparison fragment match, we fix up to do
  76       subsequent string comparison
  77    4a. Continuation of fragment comparison of a string compare.
  78    4b. EOS reached in the reference string, we conclude true match and
  79        return
  80    4c. String compare failed if index is nonzero, we need to go back to
  81        scanning
  82    5.  failed string compare, go back to scanning
  83  */
  84
  85 /* Fix-up of removal of unneeded data due to 16B aligned load
  86    parameters:
  87      value: 16B data loaded from 16B aligned address.
  88      offset: Offset of target data address relative to 16B aligned load
  89              address.
  90  */
  91
  92 static __inline__ __m128i
  93 __m128i_shift_right (__m128i value, int offset)
  94 {
  95   switch (offset)
  96     {
  97     case 1:
  98       value = _mm_srli_si128 (value, 1);
  99       break;
 100     case 2:
 101       value = _mm_srli_si128 (value, 2);
 102       break;
 103     case 3:
 104       value = _mm_srli_si128 (value, 3);
 105       break;
 106     case 4:
 107       value = _mm_srli_si128 (value, 4);
 108       break;
 109     case 5:
 110       value = _mm_srli_si128 (value, 5);
 111       break;
 112     case 6:
 113       value = _mm_srli_si128 (value, 6);
 114       break;
 115     case 7:
 116       value = _mm_srli_si128 (value, 7);
 117       break;
 118     case 8:
 119       value = _mm_srli_si128 (value, 8);
 120       break;
 121     case 9:
 122       value = _mm_srli_si128 (value, 9);
 123       break;
 124     case 10:
 125       value = _mm_srli_si128 (value, 10);
 126       break;
 127     case 11:
 128       value = _mm_srli_si128 (value, 11);
 129       break;
 130     case 12:
 131       value = _mm_srli_si128 (value, 12);
 132       break;
 133     case 13:
 134       value = _mm_srli_si128 (value, 13);
 135       break;
 136     case 14:
 137       value = _mm_srli_si128 (value, 14);
 138       break;
 139     case 15:
 140       value = _mm_srli_si128 (value, 15);
 141       break;
 142     }
 143   return value;
 144 }
 145
 146 /* Simple replacement of movdqu to address 4KB boundary cross issue.
 147    If EOS occurs within less than 16B before 4KB boundary, we don't
 148    cross to next page.  */
 149
 150 static inline __m128i
 151 __m128i_strloadu (const unsigned char * p)
 152 {
 153   int offset = ((size_t) p & (16 - 1));
 154
 155   if (offset && (int) ((size_t) p & 0xfff) > 0xff0)
 156     {
 157       __m128i a = _mm_load_si128 ((__m128i *) (p - offset));
 158       __m128i zero = _mm_setzero_si128 ();
 159       int bmsk = _mm_movemask_epi8 (_mm_cmpeq_epi8 (a, zero));
 160       if ((bmsk >> offset) != 0)
 161         return __m128i_shift_right (a, offset);
 162     }
 163   return _mm_loadu_si128 ((__m128i *) p);
 164 }
 165
 166 #if defined USE_AS_STRCASESTR && !defined STRCASESTR_NONASCII
 167
 168 /* Similar to __m128i_strloadu.  Convert to lower case for POSIX/C
 169    locale.  */
 170 static inline __m128i
 171 __m128i_strloadu_tolower (const unsigned char * p)
 172 {
 173   __m128i frag = __m128i_strloadu (p);
 174
 175   /* Convert frag to lower case for POSIX/C locale.  */
 176   __m128i rangeuc = _mm_set_epi64x (0x0, 0x5a41);
 177   __m128i u2ldelta = _mm_set1_epi64x (0xe0e0e0e0e0e0e0e0);
 178   __m128i mask1 = _mm_cmpistrm (rangeuc, frag, 0x44);
 179   __m128i mask2 = _mm_blendv_epi8 (u2ldelta, frag, mask1);
 180   mask2 = _mm_sub_epi8 (mask2, u2ldelta);
 181   return  _mm_blendv_epi8 (frag, mask2, mask1);
 182 }
 183
 184 #endif
 185
 186 /* Calculate Knuth-Morris-Pratt string searching algorithm (or KMP
 187    algorithm) overlap for a fully populated 16B vector.
 188    Input parameter: 1st 16Byte loaded from the reference string of a
 189                     strstr function.
 190    We don't use KMP algorithm if reference string is less than 16B.  */
 191 static int
 192 __inline__ __attribute__ ((__always_inline__,))
 193 KMP16Bovrlap (__m128i s2)
 194 {
 195   __m128i b = _mm_unpacklo_epi8 (s2, s2);
 196   __m128i a = _mm_unpacklo_epi8 (b, b);
 197   a = _mm_shuffle_epi32 (a, 0);
 198   b = _mm_srli_si128 (s2, sizeof (char));
 199   int bmsk = _mm_movemask_epi8 (_mm_cmpeq_epi8 (b, a));
 200
 201   /* _BitScanForward(&k1, bmsk); */
 202   int k1;
 203   __asm ("bsfl %[bmsk], %[k1]" : [k1] "=r" (k1) : [bmsk] "r" (bmsk));
 204   if (!bmsk)
 205     return 16;
 206   else if (bmsk == 0x7fff)
 207     return 1;
 208   else if (!k1)
 209     {
 210       /* There are al least two distinct chars in s2.  If byte 0 and 1 are
 211          idential and the distinct value lies farther down, we can deduce
 212          the next byte offset to restart full compare is least no earlier
 213          than byte 3.  */
 214       return 3;
 215     }
 216   else
 217     {
 218       /* Byte 1 is not degenerated to byte 0.  */
 219       return k1 + 1;
 220     }
 221 }
 222
 223 char *
 224 __attribute__ ((section (".text.sse4.2")))
 225 STRSTR_SSE42 (const unsigned char *s1, const unsigned char *s2)
 226 {
 227 #define p1 s1
 228   const unsigned char *p2 = s2;
 229
 230 #ifndef STRCASESTR_NONASCII
 231   if (__builtin_expect (p2[0] == '\0', 0))
 232     return (char *) p1;
 233
 234   if (__builtin_expect (p1[0] == '\0', 0))
 235     return NULL;
 236
 237   /* Check if p1 length is 1 byte long.  */
 238   if (__builtin_expect (p1[1] == '\0', 0))
 239     return p2[1] == '\0' && CMPBYTE (p1[0], p2[0]) ? (char *) p1 : NULL;
 240 #endif
 241
 242 #ifdef USE_AS_STRCASESTR
 243 # ifndef STRCASESTR_NONASCII
 244   if (__builtin_expect (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_NONASCII_CASE)
 245                         != 0, 0))
 246     return __strcasestr_sse42_nonascii (s1, s2);
 247 # endif
 248
 249 # define strloadu __m128i_strloadu_tolower
 250 #else
 251 # define strloadu __m128i_strloadu
 252 #endif
 253
 254   /* p1 > 1 byte long.  Load up to 16 bytes of fragment.  */
 255   __m128i frag1 = strloadu (p1);
 256
 257   __m128i frag2;
 258   if (p2[1] != '\0')
 259     /* p2 is > 1 byte long.  */
 260     frag2 = strloadu (p2);
 261   else
 262     frag2 = _mm_insert_epi8 (_mm_setzero_si128 (), LOADBYTE (p2[0]), 0);
 263
 264   /* Unsigned bytes, equal order, does frag2 has null?  */
 265   int cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 266   int cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 267   int cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 268   int cmp_s = _mm_cmpistrs (frag2, frag1, 0x0c);
 269   if (cmp_s & cmp_c)
 270     {
 271       int bmsk = _mm_movemask_epi8 (_mm_cmpeq_epi8 (frag2,
 272                                                     _mm_setzero_si128 ()));
 273       int len;
 274       __asm ("bsfl %[bmsk], %[len]"
 275              : [len] "=r" (len) : [bmsk] "r" (bmsk));
 276       p1 += cmp;
 277       if ((len + cmp) <= 16)
 278         return (char *) p1;
 279
 280       /* Load up to 16 bytes of fragment.  */
 281       frag1 = strloadu (p1);
 282       cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 283       cmp_s = _mm_cmpistrs (frag2, frag1, 0x0c);
 284       cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 285       cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 286       if ((len + cmp) <= 16)
 287         return (char *) p1 + cmp;
 288     }
 289
 290   if (cmp_s)
 291     {
 292       /* Adjust addr for 16B alginment in ensuing loop.  */
 293       while (!cmp_z)
 294         {
 295           p1 += cmp;
 296           /* Load up to 16 bytes of fragment.  */
 297           frag1 = strloadu (p1);
 298           cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 299           cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 300           cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 301           /* Because s2 < 16 bytes and we adjusted p1 by non-zero cmp
 302              once already, this time cmp will be zero and we can exit.  */
 303           if ((!cmp) & cmp_c)
 304             break;
 305         }
 306
 307       if (!cmp_c)
 308         return NULL;
 309
 310       /* Since s2 is less than 16 bytes, com_c is definitive
 311          determination of full match.  */
 312       return (char *) p1 + cmp;
 313     }
 314
 315   /* General case, s2 is at least 16 bytes or more.
 316      First, the common case of false-match at first byte of p2.  */
 317   const unsigned char *pt = NULL;
 318   int kmp_fwd = 0;
 319 re_trace:
 320   while (!cmp_c)
 321     {
 322       /* frag1 has null. */
 323       if (cmp_z)
 324         return NULL;
 325
 326       /* frag 1 has no null, advance 16 bytes.  */
 327       p1 += 16;
 328       /* Load up to 16 bytes of fragment.  */
 329       frag1 = strloadu (p1);
 330       /* Unsigned bytes, equal order, is there a partial match?  */
 331       cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 332       cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 333       cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 334     }
 335
 336   /* Next, handle initial positive match as first byte of p2.  We have
 337      a partial fragment match, make full determination until we reached
 338      end of s2.  */
 339   if (!cmp)
 340     {
 341       if (cmp_z)
 342         return (char *) p1;
 343
 344       pt = p1;
 345       p1 += 16;
 346       p2 += 16;
 347       /* Load up to 16 bytes of fragment.  */
 348       frag2 = strloadu (p2);
 349     }
 350   else
 351     {
 352       /* Adjust 16B alignment.  */
 353       p1 += cmp;
 354       pt = p1;
 355     }
 356
 357   /* Load up to 16 bytes of fragment.  */
 358   frag1 = strloadu (p1);
 359
 360   /* Unsigned bytes, equal order, does frag2 has null?  */
 361   cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 362   cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 363   cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 364   cmp_s = _mm_cmpistrs (frag2, frag1, 0x0c);
 365   while (!(cmp | cmp_z | cmp_s))
 366     {
 367       p1 += 16;
 368       p2 += 16;
 369       /* Load up to 16 bytes of fragment.  */
 370       frag2 = strloadu (p2);
 371       /* Load up to 16 bytes of fragment.  */
 372       frag1 = strloadu (p1);
 373       /* Unsigned bytes, equal order, does frag2 has null?  */
 374       cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 375       cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 376       cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 377       cmp_s = _mm_cmpistrs (frag2, frag1, 0x0c);
 378     }
 379
 380   /* Full determination yielded a false result, retrace s1 to next
 381      starting position.
 382      Zflg       1      0      1                 0/1
 383      Sflg       0      1      1                 0/1
 384      cmp        na     0      0                 >0
 385      action   done   done   continue    continue if s2 < s1
 386               false  match  retrace s1     else false
 387    */
 388
 389   if (cmp_s & !cmp)
 390     return (char *) pt;
 391   if (cmp_z)
 392     {
 393       if (!cmp_s)
 394         return NULL;
 395
 396       /* Handle both zero and sign flag set and s1 is shorter in
 397          length.  */
 398       __m128i zero = _mm_setzero_si128 ();
 399       int bmsk = _mm_movemask_epi8 (_mm_cmpeq_epi8 (zero, frag2));
 400       int bmsk1 = _mm_movemask_epi8 (_mm_cmpeq_epi8 (zero, frag1));
 401       int len;
 402       int len1;
 403       __asm ("bsfl %[bmsk], %[len]"
 404              : [len] "=r" (len) : [bmsk] "r" (bmsk));
 405       __asm ("bsfl %[bmsk1], %[len1]"
 406              : [len1] "=r" (len1) : [bmsk1] "r" (bmsk1));
 407       if (len >= len1)
 408         return NULL;
 409     }
 410   else if (!cmp)
 411     return (char *) pt;
 412
 413   /* Otherwise, we have to retrace and continue.  Default of multiple
 414      paths that need to retrace from next byte in s1.  */
 415   p2 = s2;
 416   frag2 = strloadu (p2);
 417
 418   if (!kmp_fwd)
 419     kmp_fwd = KMP16Bovrlap (frag2);
 420
 421   /* KMP algorithm predicted overlap needs to be corrected for
 422      partial fragment compare.  */
 423   p1 = pt + (kmp_fwd > cmp ? cmp : kmp_fwd);
 424
 425   /* Since s2 is at least 16 bytes long, we're certain there is no
 426      match.  */
 427   if (p1[0] == '\0')
 428     return NULL;
 429
 430   /* Load up to 16 bytes of fragment.  */
 431   frag1 = strloadu (p1);
 432
 433   /* Unsigned bytes, equal order, is there a partial match?  */
 434   cmp_c = _mm_cmpistrc (frag2, frag1, 0x0c);
 435   cmp = _mm_cmpistri (frag2, frag1, 0x0c);
 436   cmp_z = _mm_cmpistrz (frag2, frag1, 0x0c);
 437   goto re_trace;
 438 }