← Back to branch summary

~vorlon/ubuntu/natty/eglibc/multiarch

« back to all changes in this revision

Viewing changes to sysdeps/x86_64/multiarch/strstr.c

  • Committer: Steve Langasek
  • Date: 2011-02-18 21:18:44 UTC
  • mfrom: (103.1.7 eglibc)
  • Revision ID: steve.langasek@linaro.org-20110218211844-lodmi8b1qhyq3f3x
Tags: 2.13~pre1-0ubuntu1+multiarch.1
merge from natty

Show diffs side-by-side

added added

removed removed

Lines of Context:
sysdeps/x86_64/multiarch/strstr.c
1
1
/* strstr with SSE4.2 intrinsics
2
 
   Copyright (C) 2009 Free Software Foundation, Inc.
 
2
   Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3
3
   Contributed by Intel Corporation.
4
4
   This file is part of the GNU C Library.
5
5
 
19
19
   02111-1307 USA.  */
20
20
 
21
21
#include <nmmintrin.h>
 
22
#include "varshift.h"
22
23
 
23
24
#ifndef STRSTR_SSE42
24
25
# define STRSTR_SSE42 __strstr_sse42
67
68
 
68
69
   case         ECX     CFlag   ZFlag   SFlag
69
70
    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
 
71
    4a           0        1       0       0
 
72
    4b           0        1       0       1
 
73
    4c          0 < X     1       0       0/1
 
74
    5           16        0       1       0
74
75
 
75
76
   3. An initial ordered-comparison fragment match, we fix up to do
76
77
      subsequent string comparison
82
83
   5.  failed string compare, go back to scanning
83
84
 */
84
85
 
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
86
/* Simple replacement of movdqu to address 4KB boundary cross issue.
147
87
   If EOS occurs within less than 16B before 4KB boundary, we don't
148
88
   cross to next page.  */
149
89
 
150
 
static __m128i
151
 
__attribute__ ((section (".text.sse4.2")))
 
90
static inline __m128i
152
91
__m128i_strloadu (const unsigned char * p)
153
92
{
154
93
  int offset = ((size_t) p & (16 - 1));
164
103
  return _mm_loadu_si128 ((__m128i *) p);
165
104
}
166
105
 
167
 
#ifdef USE_AS_STRCASESTR
 
106
#if defined USE_AS_STRCASESTR && !defined STRCASESTR_NONASCII
168
107
 
169
108
/* Similar to __m128i_strloadu.  Convert to lower case for POSIX/C
170
109
   locale.  */
171
 
 
172
 
static __m128i
173
 
__attribute__ ((section (".text.sse4.2")))
174
 
__m128i_strloadu_tolower_posix (const unsigned char * p)
 
110
static inline __m128i
 
111
__m128i_strloadu_tolower (const unsigned char *p, __m128i rangeuc,
 
112
                          __m128i u2ldelta)
175
113
{
176
114
  __m128i frag = __m128i_strloadu (p);
177
115
 
178
 
  /* Convert frag to lower case for POSIX/C locale.  */
179
 
  __m128i rangeuc = _mm_set_epi64x (0x0, 0x5a41);
180
 
  __m128i u2ldelta = _mm_set1_epi64x (0xe0e0e0e0e0e0e0e0);
181
 
  __m128i mask1 = _mm_cmpistrm (rangeuc, frag, 0x44);
182
 
  __m128i mask2 = _mm_blendv_epi8 (u2ldelta, frag, mask1);
183
 
  mask2 = _mm_sub_epi8 (mask2, u2ldelta);
184
 
  return  _mm_blendv_epi8 (frag, mask2, mask1);
185
 
}
186
 
 
187
 
/* Similar to __m128i_strloadu.  Convert to lower case for none-POSIX/C
188
 
   locale.  */
189
 
 
190
 
static __m128i
191
 
__attribute__ ((section (".text.sse4.2")))
192
 
__m128i_strloadu_tolower (const unsigned char * p)
193
 
{
194
 
  union
195
 
    {
196
 
      char b[16];
197
 
      __m128i x;
198
 
    } u;
199
 
 
200
 
  for (int i = 0; i < 16; i++)
201
 
    if (p[i] == 0)
202
 
      {
203
 
        u.b[i] = 0;
204
 
        break;
205
 
      }
206
 
    else
207
 
      u.b[i] = tolower (p[i]);
208
 
 
209
 
  return u.x;
210
 
}
 
116
#define UCLOW 0x4040404040404040ULL
 
117
#define UCHIGH 0x5b5b5b5b5b5b5b5bULL
 
118
#define LCQWORD 0x2020202020202020ULL
 
119
  /* Compare if 'Z' > bytes. Inverted way to get a mask for byte <= 'Z'.  */
 
120
  __m128i r2 = _mm_cmpgt_epi8 (_mm_set1_epi64x (UCHIGH), frag);
 
121
  /* Compare if bytes are > 'A' - 1.  */
 
122
  __m128i r1 = _mm_cmpgt_epi8 (frag, _mm_set1_epi64x (UCLOW));
 
123
  /* Mask byte == ff if byte(r2) <= 'Z' and byte(r1) > 'A' - 1.  */
 
124
  __m128i mask = _mm_and_si128 (r2, r1);
 
125
  /* Apply lowercase bit 6 mask for above mask bytes == ff.  */
 
126
  return _mm_or_si128 (frag, _mm_and_si128 (mask, _mm_set1_epi64x (LCQWORD)));
 
127
}
 
128
 
211
129
#endif
212
130
 
213
131
/* Calculate Knuth-Morris-Pratt string searching algorithm (or KMP
214
132
   algorithm) overlap for a fully populated 16B vector.
215
133
   Input parameter: 1st 16Byte loaded from the reference string of a
216
134
                    strstr function.
217
 
   We don't use KMP algorithm if reference string is less than 16B.
218
 
 */
219
 
 
 
135
   We don't use KMP algorithm if reference string is less than 16B.  */
220
136
static int
221
137
__inline__ __attribute__ ((__always_inline__,))
222
138
KMP16Bovrlap (__m128i s2)
236
152
    return 1;
237
153
  else if (!k1)
238
154
    {
239
 
      /* There are al least two ditinct char in s2.  If byte 0 and 1 are
 
155
      /* There are al least two distinct chars in s2.  If byte 0 and 1 are
240
156
         idential and the distinct value lies farther down, we can deduce
241
157
         the next byte offset to restart full compare is least no earlier
242
158
         than byte 3.  */
256
172
#define p1 s1
257
173
  const unsigned char *p2 = s2;
258
174
 
259
 
  if (p2[0] == '\0')
 
175
#ifndef STRCASESTR_NONASCII
 
176
  if (__builtin_expect (p2[0] == '\0', 0))
260
177
    return (char *) p1;
261
178
 
262
 
  if (p1[0] == '\0')
 
179
  if (__builtin_expect (p1[0] == '\0', 0))
263
180
    return NULL;
264
181
 
265
182
  /* Check if p1 length is 1 byte long.  */
266
 
  if (p1[1] == '\0')
 
183
  if (__builtin_expect (p1[1] == '\0', 0))
267
184
    return p2[1] == '\0' && CMPBYTE (p1[0], p2[0]) ? (char *) p1 : NULL;
 
185
#endif
268
186
 
269
187
#ifdef USE_AS_STRCASESTR
270
 
  __m128i (*strloadu) (const unsigned char *);
 
188
# ifndef STRCASESTR_NONASCII
 
189
  if (__builtin_expect (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_NONASCII_CASE)
 
190
                        != 0, 0))
 
191
    return __strcasestr_sse42_nonascii (s1, s2);
271
192
 
272
 
  if (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_NONASCII_CASE) == 0)
273
 
    strloadu = __m128i_strloadu_tolower_posix;
274
 
  else
275
 
    strloadu = __m128i_strloadu_tolower;
 
193
  const __m128i rangeuc = _mm_set_epi64x (0x0, 0x5a41);
 
194
  const __m128i u2ldelta = _mm_set1_epi64x (0xe0e0e0e0e0e0e0e0);
 
195
#  define strloadu(p) __m128i_strloadu_tolower (p, rangeuc, u2ldelta)
 
196
# else
 
197
#  define strloadu __m128i_strloadu_tolower
 
198
# endif
276
199
#else
277
200
# define strloadu __m128i_strloadu
278
201
#endif