1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* |
3 | * lib/ts_bm.c Boyer-Moore text search implementation |
4 | * |
5 | * Authors: Pablo Neira Ayuso <pablo@eurodev.net> |
6 | * |
7 | * ========================================================================== |
8 | * |
9 | * Implements Boyer-Moore string matching algorithm: |
10 | * |
11 | * [1] A Fast String Searching Algorithm, R.S. Boyer and Moore. |
12 | * Communications of the Association for Computing Machinery, |
13 | * 20(10), 1977, pp. 762-772. |
14 | * https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf |
15 | * |
16 | * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 |
17 | * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf |
18 | * |
19 | * Note: Since Boyer-Moore (BM) performs searches for matchings from right |
20 | * to left, it's still possible that a matching could be spread over |
21 | * multiple blocks, in that case this algorithm won't find any coincidence. |
22 | * |
23 | * If you're willing to ensure that such thing won't ever happen, use the |
24 | * Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose |
25 | * the proper string search algorithm depending on your setting. |
26 | * |
27 | * Say you're using the textsearch infrastructure for filtering, NIDS or |
28 | * any similar security focused purpose, then go KMP. Otherwise, if you |
29 | * really care about performance, say you're classifying packets to apply |
30 | * Quality of Service (QoS) policies, and you don't mind about possible |
31 | * matchings spread over multiple fragments, then go BM. |
32 | */ |
33 | |
34 | #include <linux/kernel.h> |
35 | #include <linux/module.h> |
36 | #include <linux/types.h> |
37 | #include <linux/string.h> |
38 | #include <linux/ctype.h> |
39 | #include <linux/textsearch.h> |
40 | |
41 | /* Alphabet size, use ASCII */ |
42 | #define ASIZE 256 |
43 | |
44 | #if 0 |
45 | #define DEBUGP printk |
46 | #else |
47 | #define DEBUGP(args, format...) |
48 | #endif |
49 | |
50 | struct ts_bm |
51 | { |
52 | u8 * pattern; |
53 | unsigned int patlen; |
54 | unsigned int bad_shift[ASIZE]; |
55 | unsigned int good_shift[]; |
56 | }; |
57 | |
58 | static unsigned int matchpat(const u8 *pattern, unsigned int patlen, |
59 | const u8 *text, bool icase) |
60 | { |
61 | unsigned int i; |
62 | |
63 | for (i = 0; i < patlen; i++) { |
64 | u8 t = *(text-i); |
65 | |
66 | if (icase) |
67 | t = toupper(t); |
68 | |
69 | if (t != *(pattern-i)) |
70 | break; |
71 | } |
72 | |
73 | return i; |
74 | } |
75 | |
76 | static unsigned int bm_find(struct ts_config *conf, struct ts_state *state) |
77 | { |
78 | struct ts_bm *bm = ts_config_priv(conf); |
79 | unsigned int i, text_len, consumed = state->offset; |
80 | const u8 *text; |
81 | int bs; |
82 | const u8 icase = conf->flags & TS_IGNORECASE; |
83 | |
84 | for (;;) { |
85 | int shift = bm->patlen - 1; |
86 | |
87 | text_len = conf->get_next_block(consumed, &text, conf, state); |
88 | |
89 | if (unlikely(text_len == 0)) |
90 | break; |
91 | |
92 | while (shift < text_len) { |
93 | DEBUGP("Searching in position %d (%c)\n" , |
94 | shift, text[shift]); |
95 | |
96 | i = matchpat(pattern: &bm->pattern[bm->patlen-1], patlen: bm->patlen, |
97 | text: &text[shift], icase); |
98 | if (i == bm->patlen) { |
99 | /* London calling... */ |
100 | DEBUGP("found!\n" ); |
101 | return consumed + (shift-(bm->patlen-1)); |
102 | } |
103 | |
104 | bs = bm->bad_shift[text[shift-i]]; |
105 | |
106 | /* Now jumping to... */ |
107 | shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]); |
108 | } |
109 | consumed += text_len; |
110 | } |
111 | |
112 | return UINT_MAX; |
113 | } |
114 | |
115 | static int subpattern(u8 *pattern, int i, int j, int g) |
116 | { |
117 | int x = i+g-1, y = j+g-1, ret = 0; |
118 | |
119 | while(pattern[x--] == pattern[y--]) { |
120 | if (y < 0) { |
121 | ret = 1; |
122 | break; |
123 | } |
124 | if (--g == 0) { |
125 | ret = pattern[i-1] != pattern[j-1]; |
126 | break; |
127 | } |
128 | } |
129 | |
130 | return ret; |
131 | } |
132 | |
133 | static void compute_prefix_tbl(struct ts_bm *bm, int flags) |
134 | { |
135 | int i, j, g; |
136 | |
137 | for (i = 0; i < ASIZE; i++) |
138 | bm->bad_shift[i] = bm->patlen; |
139 | for (i = 0; i < bm->patlen - 1; i++) { |
140 | bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i; |
141 | if (flags & TS_IGNORECASE) |
142 | bm->bad_shift[tolower(bm->pattern[i])] |
143 | = bm->patlen - 1 - i; |
144 | } |
145 | |
146 | /* Compute the good shift array, used to match reocurrences |
147 | * of a subpattern */ |
148 | bm->good_shift[0] = 1; |
149 | for (i = 1; i < bm->patlen; i++) |
150 | bm->good_shift[i] = bm->patlen; |
151 | for (i = bm->patlen-1, g = 1; i > 0; g++, i--) { |
152 | for (j = i-1; j >= 1-g ; j--) |
153 | if (subpattern(pattern: bm->pattern, i, j, g)) { |
154 | bm->good_shift[g] = bm->patlen-j-g; |
155 | break; |
156 | } |
157 | } |
158 | } |
159 | |
160 | static struct ts_config *bm_init(const void *pattern, unsigned int len, |
161 | gfp_t gfp_mask, int flags) |
162 | { |
163 | struct ts_config *conf; |
164 | struct ts_bm *bm; |
165 | int i; |
166 | unsigned int prefix_tbl_len = len * sizeof(unsigned int); |
167 | size_t priv_size = sizeof(*bm) + len + prefix_tbl_len; |
168 | |
169 | conf = alloc_ts_config(payload: priv_size, gfp_mask); |
170 | if (IS_ERR(ptr: conf)) |
171 | return conf; |
172 | |
173 | conf->flags = flags; |
174 | bm = ts_config_priv(conf); |
175 | bm->patlen = len; |
176 | bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len; |
177 | if (flags & TS_IGNORECASE) |
178 | for (i = 0; i < len; i++) |
179 | bm->pattern[i] = toupper(((u8 *)pattern)[i]); |
180 | else |
181 | memcpy(bm->pattern, pattern, len); |
182 | compute_prefix_tbl(bm, flags); |
183 | |
184 | return conf; |
185 | } |
186 | |
187 | static void *bm_get_pattern(struct ts_config *conf) |
188 | { |
189 | struct ts_bm *bm = ts_config_priv(conf); |
190 | return bm->pattern; |
191 | } |
192 | |
193 | static unsigned int bm_get_pattern_len(struct ts_config *conf) |
194 | { |
195 | struct ts_bm *bm = ts_config_priv(conf); |
196 | return bm->patlen; |
197 | } |
198 | |
199 | static struct ts_ops bm_ops = { |
200 | .name = "bm" , |
201 | .find = bm_find, |
202 | .init = bm_init, |
203 | .get_pattern = bm_get_pattern, |
204 | .get_pattern_len = bm_get_pattern_len, |
205 | .owner = THIS_MODULE, |
206 | .list = LIST_HEAD_INIT(bm_ops.list) |
207 | }; |
208 | |
209 | static int __init init_bm(void) |
210 | { |
211 | return textsearch_register(&bm_ops); |
212 | } |
213 | |
214 | static void __exit exit_bm(void) |
215 | { |
216 | textsearch_unregister(&bm_ops); |
217 | } |
218 | |
219 | MODULE_LICENSE("GPL" ); |
220 | |
221 | module_init(init_bm); |
222 | module_exit(exit_bm); |
223 | |