• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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