1 /* stringlib: fastsearch implementation */ 2 3 #define STRINGLIB_FASTSEARCH_H 4 5 /* fast search/count implementation, based on a mix between boyer- 6 moore and horspool, with a few more bells and whistles on the top. 7 for some more background, see: http://effbot.org/zone/stringlib.htm */ 8 9 /* note: fastsearch may access s[n], which isn't a problem when using 10 Python's ordinary string types, but may cause problems if you're 11 using this code in other contexts. also, the count mode returns -1 12 if there cannot possible be a match in the target string, and 0 if 13 it has actually checked for matches, but didn't find any. callers 14 beware! */ 15 16 #define FAST_COUNT 0 17 #define FAST_SEARCH 1 18 #define FAST_RSEARCH 2 19 20 #if LONG_BIT >= 128 21 #define STRINGLIB_BLOOM_WIDTH 128 22 #elif LONG_BIT >= 64 23 #define STRINGLIB_BLOOM_WIDTH 64 24 #elif LONG_BIT >= 32 25 #define STRINGLIB_BLOOM_WIDTH 32 26 #else 27 #error "LONG_BIT is smaller than 32" 28 #endif 29 30 #define STRINGLIB_BLOOM_ADD(mask, ch) \ 31 ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) 32 #define STRINGLIB_BLOOM(mask, ch) \ 33 ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) 34 35 #if STRINGLIB_SIZEOF_CHAR == 1 36 # define MEMCHR_CUT_OFF 15 37 #else 38 # define MEMCHR_CUT_OFF 40 39 #endif 40 41 Py_LOCAL_INLINE(Py_ssize_t) STRINGLIB(find_char)42 STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch) 43 { 44 const STRINGLIB_CHAR *p, *e; 45 46 p = s; 47 e = s + n; 48 if (n > MEMCHR_CUT_OFF) { 49 #if STRINGLIB_SIZEOF_CHAR == 1 50 p = memchr(s, ch, n); 51 if (p != NULL) 52 return (p - s); 53 return -1; 54 #else 55 /* use memchr if we can choose a needle without too many likely 56 false positives */ 57 const STRINGLIB_CHAR *s1, *e1; 58 unsigned char needle = ch & 0xff; 59 /* If looking for a multiple of 256, we'd have too 60 many false positives looking for the '\0' byte in UCS2 61 and UCS4 representations. */ 62 if (needle != 0) { 63 do { 64 void *candidate = memchr(p, needle, 65 (e - p) * sizeof(STRINGLIB_CHAR)); 66 if (candidate == NULL) 67 return -1; 68 s1 = p; 69 p = (const STRINGLIB_CHAR *) 70 _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR)); 71 if (*p == ch) 72 return (p - s); 73 /* False positive */ 74 p++; 75 if (p - s1 > MEMCHR_CUT_OFF) 76 continue; 77 if (e - p <= MEMCHR_CUT_OFF) 78 break; 79 e1 = p + MEMCHR_CUT_OFF; 80 while (p != e1) { 81 if (*p == ch) 82 return (p - s); 83 p++; 84 } 85 } 86 while (e - p > MEMCHR_CUT_OFF); 87 } 88 #endif 89 } 90 while (p < e) { 91 if (*p == ch) 92 return (p - s); 93 p++; 94 } 95 return -1; 96 } 97 98 Py_LOCAL_INLINE(Py_ssize_t) STRINGLIB(rfind_char)99 STRINGLIB(rfind_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch) 100 { 101 const STRINGLIB_CHAR *p; 102 #ifdef HAVE_MEMRCHR 103 /* memrchr() is a GNU extension, available since glibc 2.1.91. 104 it doesn't seem as optimized as memchr(), but is still quite 105 faster than our hand-written loop below */ 106 107 if (n > MEMCHR_CUT_OFF) { 108 #if STRINGLIB_SIZEOF_CHAR == 1 109 p = memrchr(s, ch, n); 110 if (p != NULL) 111 return (p - s); 112 return -1; 113 #else 114 /* use memrchr if we can choose a needle without too many likely 115 false positives */ 116 const STRINGLIB_CHAR *s1; 117 Py_ssize_t n1; 118 unsigned char needle = ch & 0xff; 119 /* If looking for a multiple of 256, we'd have too 120 many false positives looking for the '\0' byte in UCS2 121 and UCS4 representations. */ 122 if (needle != 0) { 123 do { 124 void *candidate = memrchr(s, needle, 125 n * sizeof(STRINGLIB_CHAR)); 126 if (candidate == NULL) 127 return -1; 128 n1 = n; 129 p = (const STRINGLIB_CHAR *) 130 _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR)); 131 n = p - s; 132 if (*p == ch) 133 return n; 134 /* False positive */ 135 if (n1 - n > MEMCHR_CUT_OFF) 136 continue; 137 if (n <= MEMCHR_CUT_OFF) 138 break; 139 s1 = p - MEMCHR_CUT_OFF; 140 while (p > s1) { 141 p--; 142 if (*p == ch) 143 return (p - s); 144 } 145 n = p - s; 146 } 147 while (n > MEMCHR_CUT_OFF); 148 } 149 #endif 150 } 151 #endif /* HAVE_MEMRCHR */ 152 p = s + n; 153 while (p > s) { 154 p--; 155 if (*p == ch) 156 return (p - s); 157 } 158 return -1; 159 } 160 161 #undef MEMCHR_CUT_OFF 162 163 Py_LOCAL_INLINE(Py_ssize_t) FASTSEARCH(const STRINGLIB_CHAR * s,Py_ssize_t n,const STRINGLIB_CHAR * p,Py_ssize_t m,Py_ssize_t maxcount,int mode)164 FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n, 165 const STRINGLIB_CHAR* p, Py_ssize_t m, 166 Py_ssize_t maxcount, int mode) 167 { 168 unsigned long mask; 169 Py_ssize_t skip, count = 0; 170 Py_ssize_t i, j, mlast, w; 171 172 w = n - m; 173 174 if (w < 0 || (mode == FAST_COUNT && maxcount == 0)) 175 return -1; 176 177 /* look for special cases */ 178 if (m <= 1) { 179 if (m <= 0) 180 return -1; 181 /* use special case for 1-character strings */ 182 if (mode == FAST_SEARCH) 183 return STRINGLIB(find_char)(s, n, p[0]); 184 else if (mode == FAST_RSEARCH) 185 return STRINGLIB(rfind_char)(s, n, p[0]); 186 else { /* FAST_COUNT */ 187 for (i = 0; i < n; i++) 188 if (s[i] == p[0]) { 189 count++; 190 if (count == maxcount) 191 return maxcount; 192 } 193 return count; 194 } 195 } 196 197 mlast = m - 1; 198 skip = mlast - 1; 199 mask = 0; 200 201 if (mode != FAST_RSEARCH) { 202 const STRINGLIB_CHAR *ss = s + m - 1; 203 const STRINGLIB_CHAR *pp = p + m - 1; 204 205 /* create compressed boyer-moore delta 1 table */ 206 207 /* process pattern[:-1] */ 208 for (i = 0; i < mlast; i++) { 209 STRINGLIB_BLOOM_ADD(mask, p[i]); 210 if (p[i] == p[mlast]) 211 skip = mlast - i - 1; 212 } 213 /* process pattern[-1] outside the loop */ 214 STRINGLIB_BLOOM_ADD(mask, p[mlast]); 215 216 for (i = 0; i <= w; i++) { 217 /* note: using mlast in the skip path slows things down on x86 */ 218 if (ss[i] == pp[0]) { 219 /* candidate match */ 220 for (j = 0; j < mlast; j++) 221 if (s[i+j] != p[j]) 222 break; 223 if (j == mlast) { 224 /* got a match! */ 225 if (mode != FAST_COUNT) 226 return i; 227 count++; 228 if (count == maxcount) 229 return maxcount; 230 i = i + mlast; 231 continue; 232 } 233 /* miss: check if next character is part of pattern */ 234 if (!STRINGLIB_BLOOM(mask, ss[i+1])) 235 i = i + m; 236 else 237 i = i + skip; 238 } else { 239 /* skip: check if next character is part of pattern */ 240 if (!STRINGLIB_BLOOM(mask, ss[i+1])) 241 i = i + m; 242 } 243 } 244 } else { /* FAST_RSEARCH */ 245 246 /* create compressed boyer-moore delta 1 table */ 247 248 /* process pattern[0] outside the loop */ 249 STRINGLIB_BLOOM_ADD(mask, p[0]); 250 /* process pattern[:0:-1] */ 251 for (i = mlast; i > 0; i--) { 252 STRINGLIB_BLOOM_ADD(mask, p[i]); 253 if (p[i] == p[0]) 254 skip = i - 1; 255 } 256 257 for (i = w; i >= 0; i--) { 258 if (s[i] == p[0]) { 259 /* candidate match */ 260 for (j = mlast; j > 0; j--) 261 if (s[i+j] != p[j]) 262 break; 263 if (j == 0) 264 /* got a match! */ 265 return i; 266 /* miss: check if previous character is part of pattern */ 267 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) 268 i = i - m; 269 else 270 i = i - skip; 271 } else { 272 /* skip: check if previous character is part of pattern */ 273 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) 274 i = i - m; 275 } 276 } 277 } 278 279 if (mode != FAST_COUNT) 280 return -1; 281 return count; 282 } 283 284