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) 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 two 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) 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 two 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) 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 return -1; 196 } 197 198 mlast = m - 1; 199 skip = mlast - 1; 200 mask = 0; 201 202 if (mode != FAST_RSEARCH) { 203 const STRINGLIB_CHAR *ss = s + m - 1; 204 const STRINGLIB_CHAR *pp = p + m - 1; 205 206 /* create compressed boyer-moore delta 1 table */ 207 208 /* process pattern[:-1] */ 209 for (i = 0; i < mlast; i++) { 210 STRINGLIB_BLOOM_ADD(mask, p[i]); 211 if (p[i] == p[mlast]) 212 skip = mlast - i - 1; 213 } 214 /* process pattern[-1] outside the loop */ 215 STRINGLIB_BLOOM_ADD(mask, p[mlast]); 216 217 for (i = 0; i <= w; i++) { 218 /* note: using mlast in the skip path slows things down on x86 */ 219 if (ss[i] == pp[0]) { 220 /* candidate match */ 221 for (j = 0; j < mlast; j++) 222 if (s[i+j] != p[j]) 223 break; 224 if (j == mlast) { 225 /* got a match! */ 226 if (mode != FAST_COUNT) 227 return i; 228 count++; 229 if (count == maxcount) 230 return maxcount; 231 i = i + mlast; 232 continue; 233 } 234 /* miss: check if next character is part of pattern */ 235 if (!STRINGLIB_BLOOM(mask, ss[i+1])) 236 i = i + m; 237 else 238 i = i + skip; 239 } else { 240 /* skip: check if next character is part of pattern */ 241 if (!STRINGLIB_BLOOM(mask, ss[i+1])) 242 i = i + m; 243 } 244 } 245 } else { /* FAST_RSEARCH */ 246 247 /* create compressed boyer-moore delta 1 table */ 248 249 /* process pattern[0] outside the loop */ 250 STRINGLIB_BLOOM_ADD(mask, p[0]); 251 /* process pattern[:0:-1] */ 252 for (i = mlast; i > 0; i--) { 253 STRINGLIB_BLOOM_ADD(mask, p[i]); 254 if (p[i] == p[0]) 255 skip = i - 1; 256 } 257 258 for (i = w; i >= 0; i--) { 259 if (s[i] == p[0]) { 260 /* candidate match */ 261 for (j = mlast; j > 0; j--) 262 if (s[i+j] != p[j]) 263 break; 264 if (j == 0) 265 /* got a match! */ 266 return i; 267 /* miss: check if previous character is part of pattern */ 268 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) 269 i = i - m; 270 else 271 i = i - skip; 272 } else { 273 /* skip: check if previous character is part of pattern */ 274 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) 275 i = i - m; 276 } 277 } 278 } 279 280 if (mode != FAST_COUNT) 281 return -1; 282 return count; 283 } 284 285
