/* * Copyright (C) 2009-2010 Intel Corporation. * * SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception */ /*** *strstr.c - search for one string inside another * *Purpose: * defines strstr() - search for one string inside another * *******************************************************************************/ #include #include #include // These flags select the operation performed by _mm_cmp?str? functions. // PCMPxSTRx character type #define f_pcmp_ub 0x00 #define f_pcmp_uw 0x01 #define f_pcmp_sb 0x02 #define f_pcmp_sw 0x03 // PCMPxSTRx aggregation operation #define f_pcmp_ea 0x00 #define f_pcmp_rng 0x04 #define f_pcmp_ee 0x08 #define f_pcmp_eo 0x0C // PCMPxSTRx result polarity #define f_pcmp_pp 0x00 #define f_pcmp_np 0x10 #define f_pcmp_mp 0x20 #define f_pcmp_mn 0x30 // PCMPxSTRI index order #define f_pcmp_ls 0x00 #define f_pcmp_ms 0x40 // PCMPxSTRM result unit size #define f_pcmp_bit 0x00 #define f_pcmp_byte 0x40 // Define flag combinations to use. #define f_srch_sub (f_pcmp_ub | f_pcmp_eo | f_pcmp_pp | f_pcmp_ls) #define XMM_SIZE sizeof(__m128i) #define XMM_CHARS (XMM_SIZE / sizeof(char)) #define XMM_OFFSET(p) ((sizeof(__m128i) - 1) & (intptr_t)(p)) #define XMM_ALIGNED(p) (0 == XMM_OFFSET(p)) #define PAGE_SIZE ((intptr_t)0x1000) #define PAGE_OFFSET(p) ((PAGE_SIZE-1) & (intptr_t)(p)) #define XMM_PAGE_SAFE(p) (PAGE_OFFSET(p) <= (PAGE_SIZE - XMM_SIZE)) /*** *char *strstr(string1, string2) - search for string2 in string1 * *Purpose: * finds the first occurrence of string2 in string1 * *Entry: * char *string1 - string to search in * char *string2 - string to search for * *Exit: * returns a pointer to the first occurrence of string2 in * string1, or NULL if string2 does not occur in string1 * *Uses: * *Exceptions: * *******************************************************************************/ _Check_return_ _Ret_maybenull_ char * __cdecl strstr ( _In_z_ const char * str1, _In_z_ const char * str2 ) { const char *stmp1, *stmp2; __m128i zero, pattern, characters1, characters2; // An empty search string matches everything. if (0 == *str2) return (char *)str1; if (__isa_available < __ISA_AVAILABLE_SSE42) { unsigned mask; unsigned long offset; // Build search pattern and zero pattern. Search pattern is // XMMWORD with the initial character of the search string // in every position. Zero pattern has a zero termination // character in every position. pattern = _mm_cvtsi32_si128((unsigned char)str2[0] | ((unsigned char)str2[0] << CHAR_BIT)); pattern = _mm_shufflelo_epi16(pattern, 0); pattern = _mm_shuffle_epi32(pattern, 0); zero = _mm_set1_epi32(0); // Main loop for searching str1. We look for the next character that // matches the first character of the search string then compare to // the end of the search string. for (;;) { // If string pointer is page safe look for the next possible match // or end. If none are found we can immediately check the next block, // otherwise set the string pointer to the address of the significant // character. if (XMM_PAGE_SAFE(str1)) { characters1 = _mm_loadu_si128((__m128i*)str1); characters2 = _mm_cmpeq_epi8(characters1, zero); characters1 = _mm_cmpeq_epi8(characters1, pattern); characters1 = _mm_or_si128(characters1, characters2); mask = _mm_movemask_epi8(characters1); // If no character match or end found try next XMMWORD. if (0 == mask) { str1 += XMM_SIZE; continue; } // Advance str1 pointer to next possible match or end. _BitScanForward(&offset, mask); str1 += offset; } // If at the end of str1, then no match found. if (0 == str1[0]) return NULL; // If a first-character match is found compare strings to look for // a complete match. if (str2[0] == str1[0]) { stmp1 = str1; stmp2 = str2; for (;;) { // If search string is aligned and searched string is page-safe // check a character block for differences or the end of string2. // If nothing is found then go immediately to the next block. if (XMM_PAGE_SAFE(stmp2) && XMM_PAGE_SAFE(stmp1)) { characters1 = _mm_loadu_si128((__m128i*)stmp1); characters2 = _mm_loadu_si128((__m128i*)stmp2); characters1 = _mm_cmpeq_epi8(characters1, characters2); characters2 = _mm_cmpeq_epi8(characters2, zero); characters1 = _mm_cmpeq_epi8(characters1, zero); characters2 = _mm_or_si128(characters1, characters2); mask = _mm_movemask_epi8(characters2); // If no character difference or end found try next XMMWORD. if (0 == mask) { stmp1 += XMM_SIZE; stmp2 += XMM_SIZE; continue; } // Advance string pointers to next significant character. _BitScanForward(&offset, mask); stmp1 += offset; stmp2 += offset; } // If we've reached the end of str2 then a match has been found. if (0 == stmp2[0]) return (char *)str1; // If we've reached a difference then no match was found. if (stmp1[0] != stmp2[0]) break; // Otherwise advance to next character and try again. ++stmp1; ++stmp2; } } // Current character wasn't a match, try next character. ++str1; } } else { // SSE 4.2 supported, search & compare 16 bytes at a time if possible. char c; unsigned i; // Load XMM with first characters of str2. if (XMM_PAGE_SAFE(str2)) { pattern = _mm_loadu_si128((__m128i*)str2); } else { pattern = _mm_set1_epi32(0); c = *(stmp2 = str2); for (i = 0; i < XMM_CHARS; ++i) { pattern = _mm_srli_si128(pattern, sizeof(char)); pattern = _mm_insert_epi8(pattern, c, (XMM_CHARS-1)); if (0 != c) c = *++stmp2; } } for(;;) { // Check for partial match, if none step forward and continue. if (XMM_PAGE_SAFE(str1)) { characters1 = _mm_loadu_si128((__m128i*)str1); // If no potential match or end found, try next XMMWORD. if (_mm_cmpistra(pattern, characters1, f_srch_sub)) { str1 += XMM_CHARS; continue; } // If end found there was no match. else if (!_mm_cmpistrc(pattern, characters1, f_srch_sub)) { return NULL; } // Get position of potential match. str1 += _mm_cmpistri(pattern, characters1, f_srch_sub); } else { // If end of string found there was no match. if (0 == *str1) { return NULL; } // If current character doesn't match first character // of search string try next character. if (*str1 != *str2) { ++str1; continue; } } // Potential match, compare to check for full match. stmp1 = str1; stmp2 = str2; for (;;) { // If next XMMWORD is page-safe for each string // do a XMMWORD comparison. if (XMM_PAGE_SAFE(stmp1) && XMM_PAGE_SAFE(stmp2)) { characters1 = _mm_loadu_si128((__m128i*)stmp1); characters2 = _mm_loadu_si128((__m128i*)stmp2); // If unequal then no match found. if (!_mm_cmpistro(characters2, characters1, f_srch_sub)) { break; } // If end of search string then match found. else if (_mm_cmpistrs(characters2, characters1, f_srch_sub)) { return (char *)str1; } stmp1 += XMM_CHARS; stmp2 += XMM_CHARS; } // Compare next character. else { // If end of search string then match found. if (0 == *stmp2) { return (char *)str1; } // If unequal then no match found. if (*stmp1 != *stmp2) { break; } // Character matched - try next character. ++stmp1; ++stmp2; } } // Match not found at current position, try next. ++str1; } } }