ReactOS 0.4.16-dev-732-g2d1144a
strspn.c
Go to the documentation of this file.
1/***
2*strspn.c - find length of initial substring of chars from a control string
3*
4* Copyright (c) Microsoft Corporation. All rights reserved.
5*
6*Purpose:
7* defines strspn() - finds the length of the initial substring of
8* a string consisting entirely of characters from a control string.
9*
10* defines strcspn()- finds the length of the initial substring of
11* a string consisting entirely of characters not in a control string.
12*
13* defines strpbrk()- finds the index of the first character in a string
14* that is not in a control string
15*
16*******************************************************************************/
17
18#include <string.h>
19
20#pragma warning(disable:__WARNING_POTENTIAL_BUFFER_OVERFLOW_NULLTERMINATED) // 26018 Prefast doesn't understand reading past buffer but staying on same page.
21#pragma warning(disable:__WARNING_RETURNING_BAD_RESULT) // 28196
22
23/* Determine which routine we're compiling for (default to STRSPN) */
24#define _STRSPN 1
25#define _STRCSPN 2
26#define _STRPBRK 3
27
28#if defined (SSTRCSPN)
29 #define ROUTINE _STRCSPN
30#elif defined (SSTRPBRK)
31 #define ROUTINE _STRPBRK
32#else
33 #define ROUTINE _STRSPN
34 #define STRSPN_USE_SSE2
35#endif
36
37/***
38*int strspn(string, control) - find init substring of control chars
39*
40*Purpose:
41* Finds the index of the first character in string that does belong
42* to the set of characters specified by control. This is
43* equivalent to the length of the initial substring of string that
44* consists entirely of characters from control. The '\0' character
45* that terminates control is not considered in the matching process.
46*
47*Entry:
48* char *string - string to search
49* char *control - string containing characters not to search for
50*
51*Exit:
52* returns index of first char in string not in control
53*
54*Exceptions:
55*
56*******************************************************************************/
57
58/***
59*int strcspn(string, control) - search for init substring w/o control chars
60*
61*Purpose:
62* returns the index of the first character in string that belongs
63* to the set of characters specified by control. This is equivalent
64* to the length of the length of the initial substring of string
65* composed entirely of characters not in control. Null chars not
66* considered.
67*
68*Entry:
69* char *string - string to search
70* char *control - set of characters not allowed in init substring
71*
72*Exit:
73* returns the index of the first char in string
74* that is in the set of characters specified by control.
75*
76*Exceptions:
77*
78*******************************************************************************/
79
80/***
81*char *strpbrk(string, control) - scans string for a character from control
82*
83*Purpose:
84* Finds the first occurence in string of any character from
85* the control string.
86*
87*Entry:
88* char *string - string to search in
89* char *control - string containing characters to search for
90*
91*Exit:
92* returns a pointer to the first character from control found
93* in string.
94* returns NULL if string and control have no characters in common.
95*
96*Exceptions:
97*
98*******************************************************************************/
99
100
101
102/* Routine prototype */
103#if ROUTINE == _STRSPN
104#if defined(STRSPN_USE_SSE2)
106static size_t __cdecl fallbackMethod(
107#else
108size_t __cdecl strspn (
109#endif
110#elif ROUTINE == _STRCSPN
111#if defined(STRSPN_USE_SSE2)
113static size_t __cdecl fallbackMethod(
114#else
115size_t __cdecl strcspn (
116#endif
117#else /* ROUTINE == _STRCSPN */
118#if defined(STRSPN_USE_SSE2)
120static char * __cdecl fallbackMethod(
121#else
122char * __cdecl strpbrk (
123#endif
124#endif /* ROUTINE == _STRCSPN */
125 const char * string,
126 const char * control
127 )
128{
129 const unsigned char *str = (unsigned char const*)string;
130 const unsigned char *ctrl = (unsigned char const*)control;
131
132 unsigned char map[32];
133 int count;
134
135 /* Clear out bit map */
136 for (count=0; count<32; count++)
137 map[count] = 0;
138
139 /* Set bits in control map */
140 while (*ctrl)
141 {
142 map[*ctrl >> 3] |= (1 << (*ctrl & 7));
143 ctrl++;
144 }
145
146#if ROUTINE == _STRSPN
147
148 /* 1st char NOT in control map stops search */
149 if (*str)
150 {
151 count=0;
152 while (map[*str >> 3] & (1 << (*str & 7)))
153 {
154 count++;
155 str++;
156 }
157 return(count);
158 }
159 return(0);
160
161#elif ROUTINE == _STRCSPN
162
163 /* 1st char in control map stops search */
164 count=0;
165 map[0] |= 1; /* null chars not considered */
166 while (!(map[*str >> 3] & (1 << (*str & 7))))
167 {
168 count++;
169 str++;
170 }
171 return(count);
172
173#else /* ROUTINE == _STRCSPN */
174
175 /* 1st char in control map stops search */
176 while (*str)
177 {
178 if (map[*str >> 3] & (1 << (*str & 7)))
179 return((char *)str);
180 str++;
181 }
182 return(NULL);
183
184#endif /* ROUTINE == _STRCSPN */
185
186}
187
188#if defined(STRSPN_USE_SSE2)
189#include <emmintrin.h>
190#include <intrin.h>
191#pragma intrinsic(_BitScanForward)
192#pragma optimize("t", on)
193
194/* Routine prototype */
195#if ROUTINE == _STRSPN
197#elif ROUTINE == _STRCSPN
198size_t __cdecl strcspn (
199#else /* ROUTINE == _STRCSPN */
200char * __cdecl strpbrk (
201
202#endif /* ROUTINE == _STRCSPN */
203const char * string, const char * control)
204{
205 unsigned long long shift = (unsigned long long) control & 0xf;
206
207 // Mask off the lower bits of the address to get a 16-byte aligned pointer
208 char * alignedControl = (char *) control - shift;
209
210 // Load 16 bytes. This will not cross a page boundary but will have spurious data
211 __m128i search = _mm_loadu_si128((__m128i *) alignedControl);
212 __m128i zero = _mm_xor_si128(zero, zero);
213 __m128i temp, tempMask, smearedChar;
214 unsigned int mask, terminatorSeen = 0;
215 unsigned long bitCount;
216
217 // Sse2 provides immediate shifts of the full 128 bit register.
218 // Shift out the spurious data on the right and shift in zeros.
219 switch (shift)
220 {
221 case 1:
223 break;
224 case 2:
226 break;
227 case 3:
229 break;
230 case 4:
232 break;
233 case 5:
235 break;
236 case 6:
238 break;
239 case 7:
241 break;
242 case 8:
244 break;
245 case 9:
247 break;
248 case 10:
250 break;
251 case 11:
253 break;
254 case 12:
256 break;
257 case 13:
259 break;
260 case 14:
262 break;
263 case 15:
265 break;
266 case 0:
267 default:
268 break;
269 }
270
271 // Search for zero bytes in this initial string
274
275 if (mask)
276 {
277 // We found zeros and now need to mask away the spurious data that may follow
278 (void) _BitScanForward(&bitCount, mask);
279
280 terminatorSeen = (shift == 0) ? 1 : (bitCount < (16 - shift));
281
282 switch (16 - bitCount)
283 {
284 case 1:
287 break;
288 case 2:
291 break;
292 case 3:
295 break;
296 case 4:
299 break;
300 case 5:
303 break;
304 case 6:
307 break;
308 case 7:
311 break;
312 case 8:
315 break;
316 case 9:
319 break;
320 case 10:
323 break;
324 case 11:
327 break;
328 case 12:
331 break;
332 case 13:
335 break;
336 case 14:
339 break;
340 case 15:
343 break;
344 case 16:
345 search = zero;
346 break;
347 }
348 }
349 else if (shift == 0)
350 {
351 // We loaded 16 bytes and found no zero. Check if the first byte in
352 // the next 16-byte aligned block is zero. This load will not page fault
353 // on a correct program since we have not see the terminator.
354 if (*(alignedControl + 1) == 0)
355 {
356 terminatorSeen = 1;
357 }
358 else
359 {
360 // We already have 16 bytes and have not seen the terminator. Fallback to
361 // non-Sse2 version.
362 return fallbackMethod(string, control);
363 }
364 }
365
366 // If was have not seen the string terminator, attempt to piece-together a search
367 // mask of bytes from those in the next 16-byte aligned group that follows.
368 // We will allow at most 16 bytes in the search string.
369 if (!terminatorSeen)
370 {
371 // Go get the next 16 bytes, again this will not page fault.
372 alignedControl += 16;
373 temp = _mm_loadu_si128((__m128i *) alignedControl);
374
375 tempMask = _mm_cmpeq_epi8(temp, zero);
376 terminatorSeen = _mm_movemask_epi8(tempMask);
377
378 if (!terminatorSeen)
379 {
380 return fallbackMethod(string, control);
381 }
382
383 (void) _BitScanForward(&bitCount, terminatorSeen);
384
385 if ((16 - shift + bitCount) > 16)
386 {
387 return fallbackMethod(string, control);
388 }
389
390 // Shift the 2nd part of the search mask into place with the 16 bytes
391 switch (16 - bitCount)
392 {
393 case 1:
395 break;
396 case 2:
398 break;
399 case 3:
401 break;
402 case 4:
404 break;
405 case 5:
407 break;
408 case 6:
410 break;
411 case 7:
413 break;
414 case 8:
416 break;
417 case 9:
419 break;
420 case 10:
421 temp = _mm_slli_si128(temp, 10);
422 break;
423 case 11:
424 temp = _mm_slli_si128(temp, 11);
425 break;
426 case 12:
427 temp = _mm_slli_si128(temp, 12);
428 break;
429 case 13:
430 temp = _mm_slli_si128(temp, 13);
431 break;
432 case 14:
433 temp = _mm_slli_si128(temp, 14);
434 break;
435 case 15:
436 temp = _mm_slli_si128(temp, 15);
437 break;
438 case 16:
439 temp = zero;
440 break;
441
442 }
443
444 // Or the two parts together to obtain a single up-to 16-byte search mask
446 }
447
448 // Now loop through the string do a 16-compare with our search mask
449#if (ROUTINE == _STRSPN) || (ROUTINE == _STRCSPN)
450 size_t count = 0;
451#endif
452 while (*string)
453 {
454 int smear = (int) *string;
455 // Get the byte in a register
456 smearedChar = _mm_cvtsi32_si128(smear);
457
458 // The following 3 instructions smear this one character through each byte of the 16-byte register
459 smearedChar = _mm_unpacklo_epi8(smearedChar, smearedChar);
460 smearedChar = _mm_unpacklo_epi8(smearedChar, smearedChar);
461 smearedChar = _mm_shuffle_epi32(smearedChar, 0);
462
463 // Look for a match
464 temp = _mm_cmpeq_epi8(search, smearedChar);
466
467#if (ROUTINE == _STRSPN)
468 // Break if no match
469 if (!mask)
470 {
471 break;
472 }
473
474 string++;
475 count++;
476#elif (ROUTINE == _STRCSPN)
477 // Break on first match
478 if (mask)
479 {
480 break;
481 }
482
483 string++;
484 count++;
485#else // strpbrk case
486 // Return current string location on a match
487 if (mask)
488 {
489 return (char *) string;
490 }
491
492 string++;
493#endif
494 }
495
496#if (ROUTINE == _STRSPN) || (ROUTINE == _STRCSPN)
497 return count;
498#else
499 return NULL;
500#endif
501}
502#endif
char * strpbrk(const char *String, const char *Delimiters)
Definition: utclib.c:302
#define __cdecl
Definition: accygwin.h:79
Definition: _map.h:48
#define NULL
Definition: types.h:112
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
#define noinline
Definition: types.h:64
__m128i _mm_slli_si128(__m128i a, int i)
Definition: emmintrin.h:1352
__m128i _mm_xor_si128(__m128i a, __m128i b)
Definition: emmintrin.h:1343
__m128i _mm_cmpeq_epi8(__m128i a, __m128i b)
Definition: emmintrin.h:1448
__m128i _mm_cvtsi32_si128(int a)
Definition: emmintrin.h:1533
__m128i _mm_or_si128(__m128i a, __m128i b)
Definition: emmintrin.h:1338
int _mm_movemask_epi8(__m128i a)
Definition: emmintrin.h:1786
__m128i _mm_srli_si128(__m128i a, int imm)
Definition: emmintrin.h:1412
__m128i _mm_unpacklo_epi8(__m128i a, __m128i b)
Definition: emmintrin.h:1840
#define _mm_shuffle_epi32(a, imm)
Definition: emmintrin.h:1791
__m128i _mm_loadu_si128(__m128i_u const *p)
Definition: emmintrin.h:1559
void __declspec(noinline) __cdecl _free_base(void *const block)
Definition: free_base.cpp:98
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum GLint GLuint mask
Definition: glext.h:6028
unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:57
char string[160]
Definition: util.h:11
#define shift
Definition: input.c:1755
#define ctrl
Definition: input.c:1756
static short search(int val, const short *table, int size)
Definition: msg711.c:255
#define long
Definition: qsort.c:33
const WCHAR * str
static calc_node_t temp
Definition: rpn_ieee.c:38
_Check_return_ _CRTIMP size_t __cdecl strcspn(_In_z_ const char *_Str, _In_z_ const char *_Control)
int zero
Definition: sehframes.cpp:29
Definition: dialog.c:52
#define ROUTINE
Definition: strspn.c:33
#define _STRCSPN
Definition: strspn.c:25
#define STRSPN_USE_SSE2
Definition: strspn.c:34
size_t __cdecl strspn(const char *string, const char *control)
Definition: strspn.c:196