Commit | Line | Data |
---|---|---|
6408f79c TG |
1 | /* |
2 | * lib/ts_fsm.c A naive finite state machine text search approach | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or | |
5 | * modify it under the terms of the GNU General Public License | |
6 | * as published by the Free Software Foundation; either version | |
7 | * 2 of the License, or (at your option) any later version. | |
8 | * | |
9 | * Authors: Thomas Graf <tgraf@suug.ch> | |
10 | * | |
11 | * ========================================================================== | |
12 | * | |
13 | * A finite state machine consists of n states (struct ts_fsm_token) | |
14 | * representing the pattern as a finite automation. The data is read | |
1497b274 | 15 | * sequentially on an octet basis. Every state token specifies the number |
6408f79c TG |
16 | * of recurrences and the type of value accepted which can be either a |
17 | * specific character or ctype based set of characters. The available | |
18 | * type of recurrences include 1, (0|1), [0 n], and [1 n]. | |
19 | * | |
1497b274 AM |
20 | * The algorithm differs between strict/non-strict mode specifying |
21 | * whether the pattern has to start at the first octet. Strict mode | |
6408f79c TG |
22 | * is enabled by default and can be disabled by inserting |
23 | * TS_FSM_HEAD_IGNORE as the first token in the chain. | |
24 | * | |
25 | * The runtime performance of the algorithm should be around O(n), | |
26 | * however while in strict mode the average runtime can be better. | |
27 | */ | |
28 | ||
6408f79c TG |
29 | #include <linux/module.h> |
30 | #include <linux/types.h> | |
31 | #include <linux/string.h> | |
32 | #include <linux/ctype.h> | |
33 | #include <linux/textsearch.h> | |
34 | #include <linux/textsearch_fsm.h> | |
35 | ||
36 | struct ts_fsm | |
37 | { | |
38 | unsigned int ntokens; | |
39 | struct ts_fsm_token tokens[0]; | |
40 | }; | |
41 | ||
42 | /* other values derived from ctype.h */ | |
43 | #define _A 0x100 /* ascii */ | |
44 | #define _W 0x200 /* wildcard */ | |
45 | ||
46 | /* Map to _ctype flags and some magic numbers */ | |
1497b274 | 47 | static const u16 token_map[TS_FSM_TYPE_MAX+1] = { |
6408f79c TG |
48 | [TS_FSM_SPECIFIC] = 0, |
49 | [TS_FSM_WILDCARD] = _W, | |
50 | [TS_FSM_CNTRL] = _C, | |
51 | [TS_FSM_LOWER] = _L, | |
52 | [TS_FSM_UPPER] = _U, | |
53 | [TS_FSM_PUNCT] = _P, | |
54 | [TS_FSM_SPACE] = _S, | |
55 | [TS_FSM_DIGIT] = _D, | |
56 | [TS_FSM_XDIGIT] = _D | _X, | |
57 | [TS_FSM_ALPHA] = _U | _L, | |
58 | [TS_FSM_ALNUM] = _U | _L | _D, | |
59 | [TS_FSM_PRINT] = _P | _U | _L | _D | _SP, | |
60 | [TS_FSM_GRAPH] = _P | _U | _L | _D, | |
61 | [TS_FSM_ASCII] = _A, | |
62 | }; | |
63 | ||
1497b274 | 64 | static const u16 token_lookup_tbl[256] = { |
6408f79c TG |
65 | _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 0- 3 */ |
66 | _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 4- 7 */ | |
67 | _W|_A|_C, _W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C|_S, /* 8- 11 */ | |
68 | _W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C, _W|_A|_C, /* 12- 15 */ | |
69 | _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 16- 19 */ | |
70 | _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 20- 23 */ | |
71 | _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 24- 27 */ | |
72 | _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 28- 31 */ | |
73 | _W|_A|_S|_SP, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 32- 35 */ | |
74 | _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 36- 39 */ | |
75 | _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 40- 43 */ | |
76 | _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 44- 47 */ | |
77 | _W|_A|_D, _W|_A|_D, _W|_A|_D, _W|_A|_D, /* 48- 51 */ | |
78 | _W|_A|_D, _W|_A|_D, _W|_A|_D, _W|_A|_D, /* 52- 55 */ | |
79 | _W|_A|_D, _W|_A|_D, _W|_A|_P, _W|_A|_P, /* 56- 59 */ | |
80 | _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 60- 63 */ | |
81 | _W|_A|_P, _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U|_X, /* 64- 67 */ | |
82 | _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U, /* 68- 71 */ | |
83 | _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 72- 75 */ | |
84 | _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 76- 79 */ | |
85 | _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 80- 83 */ | |
86 | _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 84- 87 */ | |
87 | _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_P, /* 88- 91 */ | |
88 | _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 92- 95 */ | |
89 | _W|_A|_P, _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L|_X, /* 96- 99 */ | |
90 | _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L, /* 100-103 */ | |
91 | _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 104-107 */ | |
92 | _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 108-111 */ | |
93 | _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 112-115 */ | |
94 | _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 116-119 */ | |
95 | _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_P, /* 120-123 */ | |
96 | _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_C, /* 124-127 */ | |
97 | _W, _W, _W, _W, /* 128-131 */ | |
98 | _W, _W, _W, _W, /* 132-135 */ | |
99 | _W, _W, _W, _W, /* 136-139 */ | |
100 | _W, _W, _W, _W, /* 140-143 */ | |
101 | _W, _W, _W, _W, /* 144-147 */ | |
102 | _W, _W, _W, _W, /* 148-151 */ | |
103 | _W, _W, _W, _W, /* 152-155 */ | |
104 | _W, _W, _W, _W, /* 156-159 */ | |
105 | _W|_S|_SP, _W|_P, _W|_P, _W|_P, /* 160-163 */ | |
106 | _W|_P, _W|_P, _W|_P, _W|_P, /* 164-167 */ | |
107 | _W|_P, _W|_P, _W|_P, _W|_P, /* 168-171 */ | |
108 | _W|_P, _W|_P, _W|_P, _W|_P, /* 172-175 */ | |
109 | _W|_P, _W|_P, _W|_P, _W|_P, /* 176-179 */ | |
110 | _W|_P, _W|_P, _W|_P, _W|_P, /* 180-183 */ | |
111 | _W|_P, _W|_P, _W|_P, _W|_P, /* 184-187 */ | |
112 | _W|_P, _W|_P, _W|_P, _W|_P, /* 188-191 */ | |
113 | _W|_U, _W|_U, _W|_U, _W|_U, /* 192-195 */ | |
114 | _W|_U, _W|_U, _W|_U, _W|_U, /* 196-199 */ | |
115 | _W|_U, _W|_U, _W|_U, _W|_U, /* 200-203 */ | |
116 | _W|_U, _W|_U, _W|_U, _W|_U, /* 204-207 */ | |
117 | _W|_U, _W|_U, _W|_U, _W|_U, /* 208-211 */ | |
118 | _W|_U, _W|_U, _W|_U, _W|_P, /* 212-215 */ | |
119 | _W|_U, _W|_U, _W|_U, _W|_U, /* 216-219 */ | |
120 | _W|_U, _W|_U, _W|_U, _W|_L, /* 220-223 */ | |
121 | _W|_L, _W|_L, _W|_L, _W|_L, /* 224-227 */ | |
122 | _W|_L, _W|_L, _W|_L, _W|_L, /* 228-231 */ | |
123 | _W|_L, _W|_L, _W|_L, _W|_L, /* 232-235 */ | |
124 | _W|_L, _W|_L, _W|_L, _W|_L, /* 236-239 */ | |
125 | _W|_L, _W|_L, _W|_L, _W|_L, /* 240-243 */ | |
126 | _W|_L, _W|_L, _W|_L, _W|_P, /* 244-247 */ | |
127 | _W|_L, _W|_L, _W|_L, _W|_L, /* 248-251 */ | |
128 | _W|_L, _W|_L, _W|_L, _W|_L}; /* 252-255 */ | |
129 | ||
130 | static inline int match_token(struct ts_fsm_token *t, u8 d) | |
131 | { | |
132 | if (t->type) | |
133 | return (token_lookup_tbl[d] & t->type) != 0; | |
134 | else | |
135 | return t->value == d; | |
136 | } | |
137 | ||
138 | static unsigned int fsm_find(struct ts_config *conf, struct ts_state *state) | |
139 | { | |
140 | struct ts_fsm *fsm = ts_config_priv(conf); | |
141 | struct ts_fsm_token *cur = NULL, *next; | |
142 | unsigned int match_start, block_idx = 0, tok_idx; | |
143 | unsigned block_len = 0, strict, consumed = state->offset; | |
144 | const u8 *data; | |
145 | ||
146 | #define GET_NEXT_BLOCK() \ | |
147 | ({ consumed += block_idx; \ | |
148 | block_idx = 0; \ | |
149 | block_len = conf->get_next_block(consumed, &data, conf, state); }) | |
150 | ||
151 | #define TOKEN_MISMATCH() \ | |
152 | do { \ | |
153 | if (strict) \ | |
154 | goto no_match; \ | |
155 | block_idx++; \ | |
156 | goto startover; \ | |
157 | } while(0) | |
158 | ||
159 | #define end_of_data() unlikely(block_idx >= block_len && !GET_NEXT_BLOCK()) | |
160 | ||
161 | if (end_of_data()) | |
162 | goto no_match; | |
163 | ||
164 | strict = fsm->tokens[0].recur != TS_FSM_HEAD_IGNORE; | |
165 | ||
166 | startover: | |
167 | match_start = consumed + block_idx; | |
168 | ||
169 | for (tok_idx = 0; tok_idx < fsm->ntokens; tok_idx++) { | |
170 | cur = &fsm->tokens[tok_idx]; | |
171 | ||
172 | if (likely(tok_idx < (fsm->ntokens - 1))) | |
173 | next = &fsm->tokens[tok_idx + 1]; | |
174 | else | |
175 | next = NULL; | |
176 | ||
177 | switch (cur->recur) { | |
178 | case TS_FSM_SINGLE: | |
179 | if (end_of_data()) | |
180 | goto no_match; | |
181 | ||
182 | if (!match_token(cur, data[block_idx])) | |
183 | TOKEN_MISMATCH(); | |
184 | break; | |
185 | ||
186 | case TS_FSM_PERHAPS: | |
187 | if (end_of_data() || | |
188 | !match_token(cur, data[block_idx])) | |
189 | continue; | |
190 | break; | |
191 | ||
192 | case TS_FSM_MULTI: | |
193 | if (end_of_data()) | |
194 | goto no_match; | |
195 | ||
196 | if (!match_token(cur, data[block_idx])) | |
197 | TOKEN_MISMATCH(); | |
198 | ||
199 | block_idx++; | |
200 | /* fall through */ | |
201 | ||
202 | case TS_FSM_ANY: | |
203 | if (next == NULL) | |
204 | goto found_match; | |
205 | ||
206 | if (end_of_data()) | |
207 | continue; | |
208 | ||
209 | while (!match_token(next, data[block_idx])) { | |
210 | if (!match_token(cur, data[block_idx])) | |
211 | TOKEN_MISMATCH(); | |
212 | block_idx++; | |
213 | if (end_of_data()) | |
214 | goto no_match; | |
215 | } | |
216 | continue; | |
217 | ||
218 | /* | |
219 | * Optimization: Prefer small local loop over jumping | |
220 | * back and forth until garbage at head is munched. | |
221 | */ | |
222 | case TS_FSM_HEAD_IGNORE: | |
223 | if (end_of_data()) | |
224 | continue; | |
225 | ||
226 | while (!match_token(next, data[block_idx])) { | |
227 | /* | |
228 | * Special case, don't start over upon | |
229 | * a mismatch, give the user the | |
230 | * chance to specify the type of data | |
231 | * allowed to be ignored. | |
232 | */ | |
233 | if (!match_token(cur, data[block_idx])) | |
234 | goto no_match; | |
235 | ||
236 | block_idx++; | |
237 | if (end_of_data()) | |
238 | goto no_match; | |
239 | } | |
240 | ||
241 | match_start = consumed + block_idx; | |
242 | continue; | |
243 | } | |
244 | ||
245 | block_idx++; | |
246 | } | |
247 | ||
248 | if (end_of_data()) | |
249 | goto found_match; | |
250 | ||
251 | no_match: | |
252 | return UINT_MAX; | |
253 | ||
254 | found_match: | |
255 | state->offset = consumed + block_idx; | |
256 | return match_start; | |
257 | } | |
258 | ||
259 | static struct ts_config *fsm_init(const void *pattern, unsigned int len, | |
dd0fc66f | 260 | gfp_t gfp_mask) |
6408f79c TG |
261 | { |
262 | int i, err = -EINVAL; | |
263 | struct ts_config *conf; | |
264 | struct ts_fsm *fsm; | |
265 | struct ts_fsm_token *tokens = (struct ts_fsm_token *) pattern; | |
266 | unsigned int ntokens = len / sizeof(*tokens); | |
267 | size_t priv_size = sizeof(*fsm) + len; | |
268 | ||
269 | if (len % sizeof(struct ts_fsm_token) || ntokens < 1) | |
270 | goto errout; | |
271 | ||
272 | for (i = 0; i < ntokens; i++) { | |
273 | struct ts_fsm_token *t = &tokens[i]; | |
274 | ||
275 | if (t->type > TS_FSM_TYPE_MAX || t->recur > TS_FSM_RECUR_MAX) | |
276 | goto errout; | |
277 | ||
278 | if (t->recur == TS_FSM_HEAD_IGNORE && | |
279 | (i != 0 || i == (ntokens - 1))) | |
280 | goto errout; | |
281 | } | |
282 | ||
283 | conf = alloc_ts_config(priv_size, gfp_mask); | |
284 | if (IS_ERR(conf)) | |
285 | return conf; | |
286 | ||
287 | fsm = ts_config_priv(conf); | |
288 | fsm->ntokens = ntokens; | |
289 | memcpy(fsm->tokens, pattern, len); | |
290 | ||
291 | for (i = 0; i < fsm->ntokens; i++) { | |
292 | struct ts_fsm_token *t = &fsm->tokens[i]; | |
293 | t->type = token_map[t->type]; | |
294 | } | |
295 | ||
296 | return conf; | |
297 | ||
298 | errout: | |
299 | return ERR_PTR(err); | |
300 | } | |
301 | ||
302 | static void *fsm_get_pattern(struct ts_config *conf) | |
303 | { | |
304 | struct ts_fsm *fsm = ts_config_priv(conf); | |
305 | return fsm->tokens; | |
306 | } | |
307 | ||
308 | static unsigned int fsm_get_pattern_len(struct ts_config *conf) | |
309 | { | |
310 | struct ts_fsm *fsm = ts_config_priv(conf); | |
311 | return fsm->ntokens * sizeof(struct ts_fsm_token); | |
312 | } | |
313 | ||
314 | static struct ts_ops fsm_ops = { | |
315 | .name = "fsm", | |
316 | .find = fsm_find, | |
317 | .init = fsm_init, | |
318 | .get_pattern = fsm_get_pattern, | |
319 | .get_pattern_len = fsm_get_pattern_len, | |
320 | .owner = THIS_MODULE, | |
321 | .list = LIST_HEAD_INIT(fsm_ops.list) | |
322 | }; | |
323 | ||
324 | static int __init init_fsm(void) | |
325 | { | |
326 | return textsearch_register(&fsm_ops); | |
327 | } | |
328 | ||
329 | static void __exit exit_fsm(void) | |
330 | { | |
331 | textsearch_unregister(&fsm_ops); | |
332 | } | |
333 | ||
334 | MODULE_LICENSE("GPL"); | |
335 | ||
336 | module_init(init_fsm); | |
337 | module_exit(exit_fsm); |